Category: история

Category was added automatically. Read all entries about "история".

Sidious

А Королёв бы не возражал!

Чего-то в ближайшие дни услышал много негатива по поводу "киноэкипажа", хочу высказать индивидуальное мнение, которое хрен оспоришь. Считаю, что Королёву эта затея бы понравилась.

Во-первых, Королёв и сам очень любил киноэкипажи:

Korolev_with_dog.jpg

"Кино" - от корня "Кинос", собака.

А вот профессиональных космонавтов до мозга костей им. Каманина он как раз недолюбливал, о чём можно прочитать как у Чертока, так и в дневниках Каманина!

Collapse )
doomguy

Ликбез по кватернионам, Дэвенпорт VS Мортари-Маркли!

Часть 1 - история вопроса
Часть 2 - основные операции
Часть 3 - запись вращения через кватернионы
Часть 4 - кватернионы и спиноры; порядок перемножения
Часть 5 - практическая реализация поворота
Часть 5 1/2 - введение метрики, "расстояния" между поворотами
Часть 6 - поворот по кратчайшему пути
Часть 6 1/4 - кратчайший поворот в общем случае
Часть 6 2/4 - поворот, совмещающий два направления
Часть 6 3/4 - кватернион из синуса и косинуса угла
Часть 7 - интегрирование угловых скоростей, углы Эйлера-Крылова
Часть 8 - интегрирование угловых скоростей, матрицы поворота
Часть 8 1/2 - ортонормирование матрицы и уравнения Пуассона
Часть 9 - интегрирование угловых скоростей с помощью кватернионов
Часть 10 - интегрирование угловых скоростей, методы 2-го порядка
Часть 10 1/2 - интегрирование с поддержанием нормы
Часть 11 - интегрирование угловых скоростей, методы высших порядков (в разработке)
Часть 12 - навигационная задача
Часть 13 - Дэвенпорт берёт след!
Часть 14 - линейный метод Мортари-Маркли
Часть 15 - среднее от двух кватернионов
Часть 15 1/2 - проверка и усреднение кватернионов
Часть 16 - разложение кватерниона на повороты
Часть 17 - лидарная задача
Задачка к части 17
Дэвенпорт VS Мортари-Маркли

В прошлый раз мы решили "лидарную задачу", причём для нахождения поворота использовали линейный метод Мортари-Маркли. Но в оригинальной работе [Berthold K. P. Horn - Closed-form solution of absolute orientation using unit quaternions - 1987], по сути, предлагалось использовать метод Дэвенпорта.

Мы составили систему из 3 линейных уравнений с 3 неизвестными, решили её, получив вектор Родрига, и затем преобразовали его в кватернион. Но авторы предлагали составить матрицу 4х4, и найти собственный вектор, соответствующий МАКСИМАЛЬНОМУ собственному значению. Выглядит "посолиднее" - может, именно так и надо поступать? А мы пошли по упрощённому пути и получили ошибку в 0,59°. Вдруг дело не в зашумлённых входных данных, а именно в применённом методе, который не смог этот шум надёжно отфильтровать?

Давайте проверим...
Collapse )

Результат немного неожиданный: я думал, что эти два метода вообще дадут практически идентичные кватернионы, но нет. И в этом конкретном примере метод Дэвенпорта дал ошибку на 11% меньше. Полагаю, что это anecdotal evidence: если поиграться подольше, то окажется: иногда один чуть точнее, иногда другой, тут уж как повезёт. По крайней мере, в статье Мортари-Маркли получается именно так.

Может, как-нибудь ещё с этим делом поковыряюсь, но пока моя точка зрения не изменилась: на практике вполне можно применять метод Мортари-Маркли, он простой до безобразия :) А в той статье использовали Дэвенпорта по простой причине, статья 1987 года (а отдана в редакцию и вовсе в 1986), а метод Мортари-Маркли появился в 2007 году!

PS Впрочем, ещё одну вещь надо проверить: не ухудшает ли работу метода Мортари-Маркли тот факт, что эталонный и измеренный векторы имеют разную длину? Что Дэвенпорту не мешают - никаких сомнений, это видно из структуры матрицы B (см. Дэвенпорт берёт след), где весовой коэффициент можно было бы внести в длину векторов, т.е "чем точнее мы знаем вектор - тем длиннее его сделаем". И пока речь шла о направлениях, т.е единичных векторах, всё хорошо. Но тут-то из-за ошибок измерения и длина может оказываться различной...
ook

Ликбез по кватернионам, задачка к части 17

Часть 1 - история вопроса
Часть 2 - основные операции
Часть 3 - запись вращения через кватернионы
Часть 4 - кватернионы и спиноры; порядок перемножения
Часть 5 - практическая реализация поворота
Часть 5 1/2 - введение метрики, "расстояния" между поворотами
Часть 6 - поворот по кратчайшему пути
Часть 6 1/4 - кратчайший поворот в общем случае
Часть 6 2/4 - поворот, совмещающий два направления
Часть 6 3/4 - кватернион из синуса и косинуса угла
Часть 7 - интегрирование угловых скоростей, углы Эйлера-Крылова
Часть 8 - интегрирование угловых скоростей, матрицы поворота
Часть 8 1/2 - ортонормирование матрицы и уравнения Пуассона
Часть 9 - интегрирование угловых скоростей с помощью кватернионов
Часть 10 - интегрирование угловых скоростей, методы 2-го порядка
Часть 10 1/2 - интегрирование с поддержанием нормы
Часть 11 - интегрирование угловых скоростей, методы высших порядков (в разработке)
Часть 12 - навигационная задача
Часть 13 - Дэвенпорт берёт след!
Часть 14 - линейный метод Мортари-Маркли
Часть 15 - среднее от двух кватернионов
Часть 15 1/2 - проверка и усреднение кватернионов
Часть 16 - разложение кватерниона на повороты
Часть 17 - лидарная задача
Задачка к части 17

Хочется опробовать это дело на более-менее реальных данных. Имеется у нас такая вот мишень:

IMG20201021153945.jpg

ну, в реальности вместо светоотражающей плёнки будут уголковые отражатели из кварцевого стекла, а вместо ДСП - алюминиевый сплав АМг6. Не знаю, почему именно его у нас так любят - заклёпками, сваркой, штамповкой не балуемся, исключительно всё выфрезеровываем из цельного куска металла, вроде есть и более прочные и лёгкие для таких случаев. Слышал, что он лучше переносит вибрации и удары - не такой хрупкий, как другие. Может, и так. А скорее всего, просто, как начали - так зачем чего-то менять.

Так вот, координаты центров отражателей в "эталонной" системе координат. Её начало расположено примерно там, где пересекаются две карандашные линии. "На нас" (перпендикулярно доске) - ось X, "слева направо" - ось Y, "снизу вверх" - ось Z. Примерно так:

r1 (60; -104; 0),
r2 (60; 104; 0),
r3 (0; -69; 43),
r4 (0; -84; -51),
r5 (0; -158; 9),
r6 (0; 158; 9),
r7 (0; 69; 43),
r8 (0; 84; -51)

координаты в миллиметрах, без десятых и сотых, для простоты. И немного не соответствует макету (уголки чуть-чуть передвинулись), чтобы сбить с толку вероятного противника.

И давайте мы будем эту хреновину промерять "сбоку":
p4pb14464164.jpg

Лазерный трекер расположится чуть слева. И допустим, мы получили следующие координаты этих 8 точек:

m1 (-1104,1; 439,8; -0,6),
m2 (-896,1; 440,9; 0,5),
m3 (-1068,7; 499; 42,6),
m4 (-1083,4; 500,8; -50,2),
m5 (-1158,7; 500,3; 9,9),
m6 (-841,1; 499; 8,3),
m7 (-931,1; 500,5; 42,8),
m8 (-915,3; 500,7; -50,4)

Тут мы ещё ввели ошибку плюс-минус миллиметр, с округлением до десятых. Да, это очень хреновенький трекер, зато посмотрим, насколько справляется наша математика с усреднением ошибок за счёт большой выборки.

Под катом решение - чему равен поворот, масштаб и параллельный перенос. Если кому хочется попробовать самостоятельно - под кат пока не заглядывайте :)

Collapse )

А ведь работает алгоритм! Прямо-таки чудес не совершает, ошибка в 1 мм это ошибка в 1 мм, а точек здесь не сотни и не тысячи, а всего 8, а избыточности и того меньше. Просто чтобы эта задача однозначно решалась, нужно хотя бы 3 точки. Но всю имеющуюся информацию алгоритм использует по-максимуму!

Для меня практически боевое крещение линейного метода Мортари-Маркли! Я про него написал, тщательно все выкладки провёл, но ни разу не пробовал применить. Работает, и даже со знаками всё правильно. По-хорошему его ещё стоило бы сравнить с методом Дэвенпорта. Я подозреваю, что ответы будут практически идентичными, но одно дело подозревать - другое увидеть воочию.

Таблица коэффициентов для atan1

Пора уже добить этот несчастный арктангенс, что-то слишком долго его ковыряю. Мы упоминали, что в оперативной памяти будет лежать таблица в 15 слов: 5 углов и 5 комплексных чисел, им соответствующих. Вопрос был, в каком порядке всё это дело расположить, ну и сами константы "придумать". Пожалуй, вот так:

;таблица поворотов для процедуры atan1
AtanTable:
;завершающая итерация
;пока длина вектора составляет 1,0000032 от исходной (в теории, т.е если коэффициенты заданы ровно эти, но вычисления с абсолютной точностью)
Atan4a	Int16 1608		;pi/32 в формате Q2.14
;если cos(pi/32) и sin(pi/32), это было бы 32610 и 3212.
;если cos(1608/16384) и sin(1608/16384), то 32610 и 3211
;но мы ещё должны поделить на 2, т.к формат 2.14, а вектор был в 1.15
;(и это деление проведём, заменив ADD на DIV2A в конце процедуры)
;а ещё умножить на k=1,00120570556/1,0000032
;в итоге возьмём cos(1608/16384)*k и sin(1608/16384)*k
Atan4x	Int16	32650
Atan4y	Int16	3215


;к этому моменту длина вектора составляет 1,000013 от исходной
Atan3a	Int16 3217		;pi/16 в формате Q2.14
Atan3x	Int16 32138		;exp(i*pi/16) = 0,9808 + 0,1951i
Atan3y	Int16 6393

;к этому моменту длина вектора составляет 1,00000107 от исходной (в теории, это sqrt(23170^2+23171^2)/32768)
Atan2a	Int16 6434		;pi/8 в формате Q2.14
Atan2x	Int16 30274		;exp(i*pi/8) = 0,9239 + 0,3827i
Atan2y	Int16 12540

;к этому моменту длина вектора не менялась
Atan1a	Int16 12868		;pi/4, выраженные в формате Q2.14 (в который влезают значения от -4 до 4)
Atan1x	Int16 23170		;exp(i*pi/4) = 0,7071 + 0,7071i
Atan1y	Int16 23171		;а точнее, exp(i * 12868 / 16384), чтобы осуществить именно тот поворот, что указан в Atan1a

Atan0a	Int16 0
Atan0x	Int16 0		;первый поворот, на +- 90 градусов (0+1i)
Atan0y	Int16 -32768	;взяли знак "-" потому что первый раз мы берём обратный знак (из нуля вычитаем "x")
;длина вектора остаётся прежней


Как всегда, здесь всё задом наперёд!
Collapse )

Наверное, в очередной раз заморочался куда сильнее, чем следовало бы. Очень странная форма перфекционизма - придумать приближённое решение, но потом попытаться выжать из него все-все соки.
QuatCore

Приводим в порядок знаки QuatCore

Громко подумали - теперь пора привести всё в чувства, во многом - вернуть как было! Мы несколько раз отказывались от оригинальной задумки, лишь бы программа, которую в этот момент писали, заработала как надо. Первый раз знаки нас не устроили (а всего-то надо было поменять адресацию - левому операнду i^j, правому i, а не наоборот). Вон, 8 июля 2019 года приводил ровно ту табличку, которую хочу сейчас, но когда дошло дело до реализации 3-го января 2020 года, почему-то она уже поменялась...

Сейчас наш модуль QuatCorePC (Program Counter) выглядит так:


Синим обведён модуль, который пора немножко помучать, NewQuatSigns. Видно, что сейчас он "подключён" к регистрам i,j, но вместо j надо взять k.

Collapse )

Осталось программу переправить, убедиться что "ничего не сломали" - и запустить наш многострадальный арктангенс!
QuatCore

Мучительно пишем atan1

Думаю, будет правильно данную функцию назвать atan1. А то что такое: обычный atan(x) есть, atan2(y,x) есть, а вот atan1(y,x) куда-то делся :) Вот теперь будет! Напомню, это по сути atan(y/x), вот только мы позволяем x принимать нулевые и околонулевые значения и находим правильный ответ, работая в 16-битной целочисленной арифметике.

Мне казалось, что получился очень простой и компактный алгоритм, который прямо "просится" в QuatCore:

Значения x,y воспринимаем как действительную и мнимую части числа V = x + iy
Ответ A (от слова Angle, угол) инициализируем нулём
Для n=1 .. 5
    смотрим знак x
    домножаем V на exp(±i*pi/2n)
    если n>1, то A = A ± pi/2n
    (вместо ± подставляется знак числа x) 

A = A + 1,0012x. 



Значений экспоненты нужно всего 5, их можно посчитать заранее и поместить в память. Избавиться от условия внутри цикла также можно, если числа 0, pi/2, pi/4, ... , pi/32 также поместить в таблицу. Аж целых 5 слов на это дело истратим, зато "единообразно".

А ещё в последний элемент таблицы можно включить константу 1,0012, т.е не просто поворот, но и масштабирование, чтоб задействовать возможности комплексных чисел "на максимум". В итоге и в последней строке не нужен множитель, просто прибавляем x.

Но "суровая действительность", как всегда, вносит свои коррективы...

Collapse )

Без сохранения значений регистров в стеке, получается 22 строки кода, или 44 байта :) С сохранениями - 30 строк, или 60 байт. И ещё 15 слов (30 байт) будут зарезервированы в оперативной памяти, для таблицы углов.

Вот только чтобы эту программу можно было откомпилировать и запустить, нужно добавить ещё одну команду в АЛУ, "S", и навести наконец-то порядок со знаками для FMPM! Этим сейчас и займёмся.
QuatCore

О выборе самого подходящего CRC-кода

Каюсь, что в вопросе выбора полинома для CRC я исходил из "моды": взял попросту самый популярный из CRC-16, под названием CCITT, 0x1021. Другие названия (в зависимости от выбора начального значения, инверсии битов на входе и на выходе): AUG-CCITT, GENIBUS, MCRF4XX, RIELLO, TMS37157, CRC-A, KERMIT, X-25 и X-MODEM, и это только то, что знает crccalc.com.

Сейчас решил всё-таки поискать, а в чём же, собственно, разница, и какой было бы лучше всего выбрать мне для поставленной задачи: МКО (Mil-Std 1553) со своими проверками чётности, от 1 до 32 слов данных (каждое слово 16 бит), ошибки предполагаются случайными и довольно редкими (вероятность 10-7).

Бешеную активность в этом направлении (исследование CRC) развил Филипп Купман (https://users.ece.cmu.edu/~koopman/crc/). Информации очень много, она "утрамбована", вроде бы наконец разобрался, что с ней делать.

Основная идея: выбрать такой код, который для твоего размера сообщения даст наибольшую возможную дистанцию Хэмминга, т.е позволит ГАРАНТИРОВАННО обнаружить как можно больше неправильных битов.

Collapse )

В общем, мне повезло: ровно в моём случае этот полином CCITT действительно хорошо подходит. Для более коротких сообщений или для более длинных лучше подошли бы другие. А здесь мы имеем гарантированное обнаружение до 3 ошибок, а также любого их нечётного количества, и вероятность 99,997% обнаружить 4 ошибки.
QuatCore

CRC и полудуплексный UART

Апологеты "модели OSI" скажут, что генерация и проверка CRC (Cyclic Redundancy Codes) - это уже канальный уровень, а не физический, и мешать их между собой не стоит. Дескать, физический уровень - это когда говоришь "передай вот этот байт" - и самому передатчику должно быть пофиг, что это за байт такой, частью чего он является. А всей остальной системе должно быть пофиг, как именно этот байт передаётся - хоть оптикой, хоть медяшкой, хоть по радио.

Но если уж я заранее знаю, что у меня будет на физическом уровне (поначалу, для "обкатки", RS485, позже - МКО, он же ГОСТ Р 52070-2003, он же Mil-Std 1553), и у меня была возможность, исходя из этого, придумать конкретный вид применяемого CRC, то более "тесное" проникновение одного в другое позволяет заметно упростить проект.

Смысл в том, что наиболее простая реализация CRC - когда мы подаём по одному биту за раз, поэтому если уж во время передачи данных они всё равно должны "сериализоваться" - то почему бы этот поток бит и не пустить на CRC. Да и мультиплексировать один бит (поставить ли его из "обычного" сдвигового регистра, или из CRC) получается не так затратно, чем 8-битную шину, а тем более 16-битную.

Сейчас попробуем "прикрутить" к приёмопередатчику, написанному в прошлый раз, генератор CRC, рассмотренный здесь, хотя его тоже придётся несколько причесать.

Для начала раскомментируем выражение isDataBit:
assign isDataBit = (State[3] | State[0])&(~isStopState)&ce;	


И ещё разок смотрим работу передатчика:


Collapse )

Ладно, начало неплохое, при передаче CRC ведёт себя прилично. Воспользовались "недокументированным оператором верилога" &~& и ужаснулись возможностям по обфускации кода, которые он открывает :)

Теперь осталось посмотреть работу CRC на приёме, а потом сделать "схему", работающую и на приём, и на передачу.
QuatCore

5576ХС4Т против Cyclone III

Захотелось посмотреть, "до чего дошёл прогресс". Я всё ковыряюсь с 5576ХС4Т, который является функциональным аналогом Flex10k, а если точнее, EPF10K200SRC240-3. Это разработка эдак 1998 года, причём "-3" в названии означает самый медленный кристалл, "-2" быстрее, а "-1" ещё быстрее.

И на таком железе у меня то и дело случается "битва" за 25 МГц, в смысле что фиттер иногда в хорошем расположении духа и "соберёт" схему на частоту до 28 МГц, а иногда из-за малейших изменений он вдруг и до 25 МГц дотянуть не может.

Дома у меня лежит другая отладочная плата, на альтеровский/интеловский Cyclone III, если точнее: EP3C25E144C8. То, что логических элементов там поболее, 24624 против 9984 (почти в 2,5 раза), и памяти побольше, 608 256 бит против 98 304 (более чем в 6 раз) - это я знал. А вот что там по скорости - ни разу не сравнивал.

Попробовал сейчас в своём проекте просто поменять Device. Услышал ругань в свою сторону - "ну снеси ты уже все пины и расставь по-новой", а когда я его послал и всё-таки запустил синтез - получил ошибку: Cyclone III поддерживает только синхронную память!

Collapse )

В результате вся эта штуковина наконец-то синтезируется, и получается такой результат:


Ага, 76 МГц, сразу так в 3 раза "разгон"! А если ещё применить аппаратный перемножитель, коих на третьем циклоне 132 штуки 9-битных, то мои все команды умножения вместо 18 тактов будут занимать эдак 3-4 такта :)

Притом, ядро занимает 546 ЛЭ, т.е 2,2% от полной логической ёмкости этого Циклона. Буквально "на сдачу". NIOS II нервно курит в сторонке! Надо только задокументировать всё как следует, наснимать обучающих видеороликов, набор тестовых программок, чтобы не так страшно было эту штуковину осваивать - и можно попробовать его внедрить поширше :)
QuatCore

Обнаружение точек "вживую" - отладка продолжается

Если подумать, в прошлый раз ничего заработать и не могло, и опять по причине излишней нашей "шустрости".

Процесс запуска сейчас выглядит так: я поворачиваю тумблер (подаю питание) - и в ПЛИС загружается старая прошивка, та, в которой ИК подсветка отключена. Камера получает питание - и настраивает экспозицию худо-бедно.

Когда я прошиваю ПЛИС с компьютера, примерно секунду все её выводы переходят в режим входа с "подтяжкой к +3,3 вольта" резисторами порядка 12 кОм. Этого недостаточно, чтобы включить ИК-подсветку, поэтому и эту секунду она отключена, и камера, как не в чём не бывало продолжает выдавать картинку.

И вот, наконец, начинается работа - первым же делом ИК подсветка включается, и по первому же кадровому синхроимпульсу мы начинаем обрабатывать изображение. И тут никуда не денешься - оно получается ПЕРЕСВЕЧЕННЫМ! Практически весь "экран" белый, любая точка проходит порог обнаружения.

По нашему алгоритму, на первой строке мы "обнаруживаем" одну точку (скорее всего в левом углу), и для второй строки даём уже 2-3 задания на обработку, на каждом из них снова "обнаруживая" по точке, и тут уж действительно либо мы "закопаемся" в обработке каждой из них (а новый пиксель идёт КАЖДЫЙ ТАКТ, тогда как обработка "обнаруженных точек" на процессоре куда медленнее) и тем самым не успеваем "озадачить" видеопроцессор, либо всё-таки успеваем - но быстро забиваем те 32 позиции, которые были выделены в памяти, и получаем Out of heap memory.

"Кто виноват" - понятно. Осталось понять, "что делать"...

Collapse )


Уже что-то!

Мы видим, до какого места дошла обработка, и видим, что запись в статическую память идёт корректно, даже если вместо одного задания на всю строку идёт куча мелких заданий. А ещё видим, что картинка "так себе" - всё ещё пересвеченная, с какими-то бликами, и возможно наш алгоритм для такой действительно неприменим.

Сейчас, наверное, чем-нибудь заслоню плоское зеркало, ещё разок проверю настройки экспозиции - и продолжим...