Comments 21
Можно вопрос как художник художнику? Всем художникам задаю, ни кто вразумительно ответить не может…
Почему популярные полиномы CRC, не являются «неприводимыми над полем Галуа»?
Нутро подсказывает «неприводимость» == «максимальное кодовое расстояние »! Корпорации и инженерные сообщества запускающие в мир полиномы так не считают…
Например, есть два полинома степени 2 с основанием кода 3. Максимальный период у этих полиномов 3^2-1=8. Полином произведение будет иметь период 8*8=64 и степень 4. Но у полинома степени 4 с основанием кода 3 максимальный период 3^4-1=80, что чуть больше 64.
Дык 80 всяко больше 64! а (2^8-1) еще больше (2^4-1)*(2^4-1).
Моих знаний алгебры явно не хватает, но смею предположить, что неприводимые полиномы покажут хороший результат только при некоррелированных ошибках, которые в реальных каналах связи практически не встречаются.
Реальные каналы характеризуются групповыми ошибками. Именно на групповые ошибки рассчитаны популярные полиномы. Например, канал связи с ТочМемори от Далас, наиболее вероятная ошибка замена группы бит на 1. Именно на обнаружение подобной ошибки рассчитан полином.
Также бороться с групповыми ошибками можно выбирая другое основание кода q > 2. Например, при q=256 и простеньком полиноме (с кодовым расстоянием три) можно обнаруживать парные искажения байтов, когда искажено два байта из n байтов.
Надеюсь, когда снова будет свободное время, напишу продолжение, в котором расскажу про циклические коды и покажу пример программы для кодирования и декодирования. Если, конечно, почтенной публике это интересно.
Да, интересно и весьма доступно!
Очень интересно!
Так совпало, что именно сегодня зачёт по данной теме и тут вы в Вашей статье так доступно рассказываете то, что не смог донести преподаватель. Всё очень понятно и систематизировано. Спасибо!
Есть пара моментов, которые мне кажется, стоит скорректировать. Во-первых, в определении поля в плюс к сложению и вычитанию стоит написать про умножение (вероятно, вы опечатались, потому что чуть выше про него сказано).
Во-вторых, когда вы говорите про то, что умножение на матрицу быстрее поиска по табличке — это кажется несколько бездоказательным, и скорее даже неверным. Число строк не превышает двойки в степени числа столбцов N, а значит можно построить решающее дерево, определяющее строку, которое требует не больше N одиночных сравнений. Умножение же матрицы на вектор N действий непременно съест.
- Да, определение поля я уточню. Просто поздно ночью писал. :)
- Насчёт таблицы. Я имел в виду не скорость, а потребление памяти. Просто для сколько-нибудь длинного передаваемого сообщения табличка всех возможных случаев получается громоздкой. Если же рассматривать только синдромы, то всё равно нужна таблица, но уже поменьше. (А в циклических кодах и она не нужна.)
Я наверное чего-то важного все таки не понял. Можете привести пример какой-нибудь, чтобы было понятно, откуда там экономия памяти?
Там такая идея. Допустим, мы хотим передать 8 бит, мы кодируем их 12 битами и передаём по каналу связи. На том конце мы получаем какое-то сообщение с ошибкой, и чтобы исправить её, ищем самое близкое кодовое слово. Но тогда придётся сравнивать с 28=256 кодовыми словами.
Можно заранее для каждого возможного полученного сообщения найти соответствующее кодовое слово, но тогда в таблице придётся хранить 212=4096 строк. (Зато быстрый поиск.)
И, наконец, третий вариант. Можно найти синдром умножением на матрицу 4×12. У него будет длина 4 разряда, а значит, в таблице синдромов будет всего 16 строк. Экономия.
Может, я неправильно вас понял, и мы о разных таблицах говорим?
Спасибо за отзывы! Сразу хочу извиниться перед всеми, что не сразу отвечаю, просто работы много. Надеюсь, на выходных напишу продолжение, в котором расскажу уже о циклических кодах.
под конец сообразил, как ускорить.
P.S. Не смог разобраться, как сформирована последняя таблица — соответствия синдрома векторам.
Да всё руки не доходят, хотя очень много планов и на продолжение, и на другие статьи. :(
Формируется в данном случае очень просто. Создаём табличку с пустыми строками, где строки подписаны всеми возможными значениями синдрома. Берём все возможные векторы и вычисляем для них синдром. Каждый вектор записываем в строчку с соответствующим синдромом. Потом просто подчёркиваем векторы, где меньше всего единичек.
Статья супер, спасибо автору! Ждём продолжения.
Корректирующие коды «на пальцах»