masai May 10 2017 at 00:15

Корректирующие коды «на пальцах»

11 min

70K

Algorithms*Mathematics*

Tutorial

+54

Comments 21

aobondar May 10 2017 at 10:39

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

IBAH_II May 10 2017 at 10:51

Респект и уважуха! Какие яркие образы! Просто и со вкусом!
Можно вопрос как художник художнику? Всем художникам задаю, ни кто вразумительно ответить не может…
Почему популярные полиномы CRC, не являются «неприводимыми над полем Галуа»?
Нутро подсказывает «неприводимость» == «максимальное кодовое расстояние »! Корпорации и инженерные сообщества запускающие в мир полиномы так не считают…

sci_nov May 11 2017 at 06:58

Извините за вклинивание, но думаю, что корпорации конструируют многочлены из произведений неприводимых многочленов с большим периодом. Это сродни конструированию любых чисел из произведений простых чисел. Пусть это будет не самым оптимальным с точки зрения максимального периода, но зато будет регулярный способ построения кодов. Например, код Рида-Соломона это и использует, откуда вытекают специальные методы кодирования, декодирования, формулы для кодового расстояния и т.п.
Например, есть два полинома степени 2 с основанием кода 3. Максимальный период у этих полиномов 3^2-1=8. Полином произведение будет иметь период 8*8=64 и степень 4. Но у полинома степени 4 с основанием кода 3 максимальный период 3^4-1=80, что чуть больше 64.

IBAH_II May 11 2017 at 09:45

Основание кода 3 немножечко не к месту… 2 таки привычнее.

Дык 80 всяко больше 64! а (2^8-1) еще больше (2^4-1)*(2^4-1).

Моих знаний алгебры явно не хватает, но смею предположить, что неприводимые полиномы покажут хороший результат только при некоррелированных ошибках, которые в реальных каналах связи практически не встречаются.
Реальные каналы характеризуются групповыми ошибками. Именно на групповые ошибки рассчитаны популярные полиномы. Например, канал связи с ТочМемори от Далас, наиболее вероятная ошибка замена группы бит на 1. Именно на обнаружение подобной ошибки рассчитан полином.

sci_nov May 11 2017 at 11:50

Групповые ошибки декоррелируют перемежением. А вообще, циклические коды хорошо обнаруживают ошибки, например, двоичный код (7, 4) обнаруживает все ошибки кратностей 1, 2, 5, 6 и 80% ошибок кратностей 3 и 4.
Также бороться с групповыми ошибками можно выбирая другое основание кода q > 2. Например, при q=256 и простеньком полиноме (с кодовым расстоянием три) можно обнаруживать парные искажения байтов, когда искажено два байта из n байтов.

inchernar May 10 2017 at 14:03

Спасибо за статью!

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

Да, интересно и весьма доступно!

dimonoid May 10 2017 at 15:57

Очень интересно!

Berzilla May 10 2017 at 15:58

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

TheWind3 May 10 2017 at 15:58

Отличная статья, просто отличная. Не так-то просто просто изложить сложные вещи.

Videoman May 10 2017 at 16:18

Тот редкий случай, когда читаешь, и понимаешь — человек написавший статью досконально разбирается в том что написал. Спасибо вам большое за труд.

unabl4 May 10 2017 at 22:38

Отличная статья! Определённо буду ждать продолжения.

VorontsovIE May 11 2017 at 14:26

Спасибо за статью!

Есть пара моментов, которые мне кажется, стоит скорректировать. Во-первых, в определении поля в плюс к сложению и вычитанию стоит написать про умножение (вероятно, вы опечатались, потому что чуть выше про него сказано).
Во-вторых, когда вы говорите про то, что умножение на матрицу быстрее поиска по табличке — это кажется несколько бездоказательным, и скорее даже неверным. Число строк не превышает двойки в степени числа столбцов N, а значит можно построить решающее дерево, определяющее строку, которое требует не больше N одиночных сравнений. Умножение же матрицы на вектор N действий непременно съест.

masai May 11 2017 at 17:33

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

VorontsovIE May 11 2017 at 17:55

Вроде размер таблицы зависит от размера алфавита, а не сообщения? И размер матрицы по порядку величины будет близок к размеру таблички кодов, ведь там всё зависит от числа переменных N и уравнений (а их, наверняка, достаточно много)?
Я наверное чего-то важного все таки не понял. Можете привести пример какой-нибудь, чтобы было понятно, откуда там экономия памяти?

masai May 11 2017 at 18:07

Там такая идея. Допустим, мы хотим передать 8 бит, мы кодируем их 12 битами и передаём по каналу связи. На том конце мы получаем какое-то сообщение с ошибкой, и чтобы исправить её, ищем самое близкое кодовое слово. Но тогда придётся сравнивать с 2⁸=256 кодовыми словами.

Можно заранее для каждого возможного полученного сообщения найти соответствующее кодовое слово, но тогда в таблице придётся хранить 2¹²=4096 строк. (Зато быстрый поиск.)

И, наконец, третий вариант. Можно найти синдром умножением на матрицу 4×12. У него будет длина 4 разряда, а значит, в таблице синдромов будет всего 16 строк. Экономия.

Может, я неправильно вас понял, и мы о разных таблицах говорим?

masai May 11 2017 at 17:32

Спасибо за отзывы! Сразу хочу извиниться перед всеми, что не сразу отвечаю, просто работы много. Надеюсь, на выходных напишу продолжение, в котором расскажу уже о циклических кодах.

masai May 24 2017 at 19:53

Извините, катастрофический завал на работе, так что с продолжением придется повременить. :(

lazywicked May 12 2017 at 17:34

давным давно, на практике, искали синдромы делением 600 значных чисел для получения кодов файра.
под конец сообразил, как ускорить.

Serjio2888 Feb 8 2020 at 23:33

Отличная статья, третий год жду продолжения.
P.S. Не смог разобраться, как сформирована последняя таблица — соответствия синдрома векторам.

masai Mar 2 2020 at 15:08

Да всё руки не доходят, хотя очень много планов и на продолжение, и на другие статьи. :(

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

punzik Aug 8 2020 at 09:05

Статья супер, спасибо автору! Ждём продолжения.

Show the best of all time