nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

Хотел выпендриться

Одно из замечаний к моему протоколу информационного обмена: ДОБАВЬ 16-битные заголовки к каждому сообщению!

Нам могут прислать командное слово с подадресом 1, и это будет обозначать, к примеру, "выдай целевую информацию", либо с подадресом 2 - и это будет "выдай телеметрию", либо с подадресом 3 - и это будет "дамп памяти" (в отладочных целях).

Как положено, к командному слову есть бит чётности, и если он неверен - мы команду игнорируем "от греха подальше". Но им этого кажется недостаточно: вдруг нам так не повезёт, что ошибочно сменилось ДВА бита, и теперь мы решим, что надо выдать целевую информацию, хотя на самом деле заказывали телеметрию!

И далее мы выдадим ответное сообщение без каких-либо ошибок, вот только НЕ ТО! Чтобы этого не произошло, они и хотят, чтобы у каждого ответного сообщения был свой уникальный код. Вот тогда-то они увидят, что они заказывали одно, а мы прислали совсем другое!

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

Но застрял с этим вопросом уже на несколько дней...


Поначалу я задумался, что нужно таких кодов всё-таки "с избытком". Сейчас сообщений введено не так уж много, где-то по 4 "в каждую сторону", но мало ли, ещё чего-нибудь придумаем. Поэтому решил: давайте сообщений будет 32 штуки, это даже больше, чем доступных подадресов в протоколе МКО, он же МКИО, он же Mil-Std 1553. Там их 30, поскольку коды 00000 и 11111 зарезервированы под "команды управления", а в ГОСТе рекомендуют ещё и 11110 зарезервировать под "проверку связи", когда можно присылать сколько угодно слов данных - и оконечное устройство (Remote Terminal) должно их переправить назад, эдакое "эхо".

Далее, не мудрствуя лукаво, ввёл в DuckDuckGo (вместо гугла) "Generate numbers with maximum Hamming distance", и наткнулся на этот вопрос в StackOverflow: https://stackoverflow.com/questions/33175429/generating-numbers-with-high-hamming-distance

В первом ответе советовали просто повторять несколько раз наше число, сколько его там влезет. В нашем случае мы хотим кодировать 32 разных значения - это 5 бит. У нас 16 бит - значит, можно повторить 3 раза подряд одно и то же - ПРОФИТ!

Но как-то это не очень убедительно, там же столько всякого разного насочиняли! Второй ответ был более многообещающим, там предлагалось воспользоваться кодами Рида-Соломона, в результате чего как раз-таки добавится избыточность чуть ли не теоретически наилучшим образом. У вопрошающего был вопрос, очень похожий на мой: как бы так в 64 бита лучше всего втиснуть 10 000 разных значений, чтобы они максимально отличались друг от друга. И ему сказали: чтобы закодировать число от 1 до 10 000, нужно 14 бит (от 0 до 16383), и тогда нужно применить код Рида-Соломона [64,14,51]_2 - и будет нам счастье (дистанция Хэмминга в эти самые 51 бит!!!). И, дескать, самостоятельно его сгенерировать - то ещё удовольствие, а лучше найти что-нибудь готовое.

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

Пришлось копнуть поглубже - и обнаружилось, что собственно коды Рида-Соломона для отдельных битов и не используются, самый частый вариант - работа с байтами, с блоками по 256 штук, причём часть в этом блоке выдаётся именно под коррекцию ошибок. Binary Reed Solomon Encoding - нечто "эзотерическое", в англоязычную википедию переведённое с китайского (а картинку так и не перевели), и концов не сыщешь. Другое упоминание об этом - только на сайте BitcoinWiki, но он почему-то не открывается.

Зато в статье про коды Рида-Соломона узнал, что сейчас вместо них вовсю начали использовать ТУРБОКОДЫ, которые куда легче кодируются и декодируются и очень близко подходят к теоретическому пределу "помехоустойчивости". Решил разобраться с ними - и попал на видеолекцию индийского профессора. Как ни странно, что-то даже понял, а его математика с буквами D (видимо Delay) очень напомнила z-преобразование, только вместо обычной арифметики комплексных чисел тут всё "по модулю два", что даже проще.

И действительно, вроде бы довольно просто: берём 2 одинаковых кодера из регистров и XOR'ов (что-то подобное вычисляет CRC), на один подаём исходные данные, на другой - их же, только основательно перемешанные с помощью Interleaver'а. И потом попросту "передаём" как исходное сообщение, так и два кодированных потока.

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

Я тоже решил с неё и начать. А в качестве interleaver'а просто прочитать свои многострадальные 5 бит задом наперёд. Порисовал всё это дело на бумажке, получил нечто такое:
00000 00000 00000 (ну да, когда у тебя только XOR'ы и задержки, и на входе сплошные нули - единицам взяться неоткуда!)
00001 11111 10000 (сначала исходное число, потом оно пропущенное через "контроль чётности" с одного конца, и потом "задом наперёд")
00010 11110 11000
00011 00001 01000
00100 11100 11100 (ага, это палиндром, поэтому два правых значения вышли одинаковыми)


Посчитал дистанцию Хэмминга ручками (количество отличающихся бит между разными числами) - и чего-то не впечатлился! Получается 4, что не шибко отличается от записи одного и того же числа 3 раза, а потом ещё бит чётности повесить! И то, я ещё не все комбинации проверил...

Решил, что однобитная "проверка чётности" портит мне всё - и нашёл более хитрый драндулет. Написал данный Recursive Systematic Convolution encoder length-4 на верилоге:

module RSC4 (input clk, input sclr, input D, output Q);

reg D1, D2, D3;

always @(posedge clk) begin
	D1 <= sclr? 1'b0 : D^D2^D3;
	D2 <= sclr? 1'b0 : D1;
	D3 <= sclr? 1'b0 : D2;
end

assign Q = D^D1^D2^D3;

endmodule


Дополнил всё это дело сдвиговыми регистрами для "сериализации - десериализации", типа я помещаю 5-битное число, оно посылается по одному биту (на один кодер слева направо, на другой - справа налево), и потом всё это также собирается в итоговое число:



Потом ещё и 16-й бит добавил, "чётности", ну на всякий случай - и вышло следующее:

00000 00000 00000 0 (ну разумеется)
00010 01110 00011 0
00011 00010 00010 0
00100 00111 00111 1


и чего-то снова не впечатляет, и здесь разница не более, чем на 4 бита!

Подумал: а может сделать код Хэмминга? Он обещает исправить 1 ошибку и обнаружить 2 ошибки, тоже не особенно!

А может, просто CRC посчитать? Начал считать CRC-16 от единственного байта, и вижу - НЕЕ, там вообще от силы 2 бита меняются, тоже к такому его судьба не готовила :)

Этот-то отвечающий на StackOverflow "обещал" что аж 11 битов будут отличаться каждый раз. И только тут я задумался: ДА БЫТЬ ТОГО НЕ МОЖЕТ! Да просто я изображу сначала 16 нулей. Как породить другое число, которое аж в 11 разрядах от первого отличается - надо поставить 11 единиц и 5 нулей:

0000 0000 0000 0000
1111 1111 1110 0000

А как сгенерить ещё одно число, отличающееся на 11? Нужно другие нули поставить:

0000 0000 0000 0000
1111 1111 1110 0000
0000 0111 1111 1111


Да вот только два нижних числа отличаются всего на 10. Тоже неплохо, ладно. Четвёртое число ещё худо-бедно построим:
0000 0000 0000 0000
1111 1111 1110 0000
0000 0111 1111 1111
1111 1000 0011 1111


А дальше - нема!

И только тогда наконец вывела меня нелёгкая на Hamming bound. Что нельзя просто добавить 10 лишних бит и надеяться, что они теперь будут различаться минимум на 10.

Тоже на удивление криво всё сформулировано, чтобы никто не догадался. В общем, подставив свои значения, n=16 (сколько доступно бит), q=2 (это именно биты, а не байты, триты или что ещё) и d=7, получается 94 различных "сообщения", которые можно будет отличить друг от друга даже если 7 бит были перепутаны. А если подставить d=9, уже получается 26 сообщений, то есть уже не хватает.

И то, это некое "теоретическое значение", к которому ещё не факт, что подберёшься.

Удивляет только, что к "идеальному коду", на котором граница Хэмминга достигается, относят:
- тривиальный частный случай, обычное сообщение вообще без дублирования (ну да)
- другой тривиальный случай, когда всего один бит повторён сколько угодно раз
- кодирование Хэмминга (внезапно)
- повторение одной и той же последовательности нечётное количество раз!

С последним я чего-то не понимаю, ведь если я просто повторю те же 5 бит в течение 3 раз, я получу дистанцию в 3, но никак не в 7.


В общем, нельзя верить Википедии, и нельзя верить StackOverflow :) И по-моему, повторю я одно 5-битное значение 3 раза, добавлю бит чётности - и скажу, что так и надо!
Tags: ПЛИС, бред, математика, программки, работа, странные девайсы
Subscribe

  • Так есть ли толк в ковариационной матрице?

    Задался этим вопросом применительно к своему прибору чуть более 2 недель назад. Рыл носом землю с попеременным успехом ( раз, два, три, четыре),…

  • Big Data, чтоб их ... (4)

    Наконец-то стряхнул пыль с компьютерной модели сближения, добавил в неё код, чтобы мы могли определить интересующие нас точки, и выписать…

  • Потёмкинская деревня - 2

    В ноябре 2020 года нужно было сделать скриншот несуществующей программы рабочего места под несуществующий прибор, чтобы добавить его в документацию.…

  • Великая Октябрьская резня бензопилой

    Сегодня прокатился прочистить Абрамцевскую просеку. Как обычно, с приключениями. Выезжал на велосипеде, а вернулся на самокате. Первый раз по этим…

  • Очередная несуразность в единицах измерения

    Когда-то я написал программу PhysUnitCalc - калькулятор, умеющий работать с размерностями. Мне казалось, что я наступил уже на все грабли, которые…

  • Big Data, чтоб их... (3)

    "В предыдущих сериях": мой прибор выдаёт 6 значений: 3 координаты и 3 угла, т.е все 6 степеней свободы твёрдого тела. Причём ошибки измерения этих 6…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 15 comments

  • Так есть ли толк в ковариационной матрице?

    Задался этим вопросом применительно к своему прибору чуть более 2 недель назад. Рыл носом землю с попеременным успехом ( раз, два, три, четыре),…

  • Big Data, чтоб их ... (4)

    Наконец-то стряхнул пыль с компьютерной модели сближения, добавил в неё код, чтобы мы могли определить интересующие нас точки, и выписать…

  • Потёмкинская деревня - 2

    В ноябре 2020 года нужно было сделать скриншот несуществующей программы рабочего места под несуществующий прибор, чтобы добавить его в документацию.…

  • Великая Октябрьская резня бензопилой

    Сегодня прокатился прочистить Абрамцевскую просеку. Как обычно, с приключениями. Выезжал на велосипеде, а вернулся на самокате. Первый раз по этим…

  • Очередная несуразность в единицах измерения

    Когда-то я написал программу PhysUnitCalc - калькулятор, умеющий работать с размерностями. Мне казалось, что я наступил уже на все грабли, которые…

  • Big Data, чтоб их... (3)

    "В предыдущих сериях": мой прибор выдаёт 6 значений: 3 координаты и 3 угла, т.е все 6 степеней свободы твёрдого тела. Причём ошибки измерения этих 6…