Нахождение ошибок в циклическом коде

Приветствую! Не уверена, что правильно выбрала раздел для своего вопроса, но суть его в следующем:
Определить в каком разряде кодового вектора 1101011 циклического кода [7,4] имеется ошибка - так звучит задание. Я, само собой, пыталась самостоятельно разобраться, и у меня возникла загвоздка. Разобрала эту статью на хабре, посчитала для своего примера: https://habr.com/ru/post/140611/. Возник вопрос: что делать, если я не знаю, как выглядит правильно переданное сообщение? Я получила сообщение с контрольными битами из неправильного сообщения, но как понять, где ошибка? Вот 0110101011 до чего досчиталась. Я так понимаю это полученное сообщение с контрольными битами на позициях 1,2,4, но в каких из них ошибки, я не могу понять, как вычислить. Подскажите, пожалуйста, что делать дальше или может вообще я неправильно действую изначально? Заранее благодарю!

0

На хабре всё неплохо разжёвано, однако, основные термины считаются сами собой разумеющимися. Типа, "Это происходит вот так, а по какой причине именно так, Вам знать не обязательно".

[7, 4] означает, что в векторе всего 7 символов, 4 из которых информационные.

Код Хэмминга может быть классическим и усечённым.

Количество символов в классическом коде Хэмминга определяется количеством проверочных символов "r". Маркировка какого-либо кода Хэмминга определяется как

[2^r-1, 2^r-1-r]

Часто некоторое количество символов не используется, такие коды Хэмминга называются усечёнными.

У Вас по заданию классический код Хэмминга с r=3, поэтому [2³-1, 2³-1-3] = [7, 4].

На Хабре в примере использован усечённый код Хэмминга [21, 16], который получается из классического кода Хэмминга [31, 26] отсечением десяти символов.

На хабре не объясняется, по какому принципу определяется номер ошибочного символа: собственно, а почему "N через N начиная с N", а не как-то ещё?

Не мудрено, что Вы запутались. Тем не менее, ещё раз перечитайте хабр.

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

Приступим.

Проверочные символы в коде Хэмминга располагаются на позициях, кратных степени числа 2, начиная с нулевой степени, то есть, на позициях 1, 2, 4, 8, 16, 32 и так далее. Остальные символы - информационные. В Вашем случае проверочные символы стоят в позициях 1, 2 и 4.

Ваш вектор, проверочные символы обозначены красным цветом: 1101011.

Посимвольно, в виде таблицы:

Имя символа	i1	i2	i3	i4	i5	i6	i7
Символ	1	1	0	1	0	1	1

Вычислим синдромы (проверочные суммы по модулю 2):



Синдромы удобнее нумеровать по степеням двойки (то есть, 1, 2, 4, 8, 16 и т.д., а не 1, 2, 3, 4 и т.д.), поскольку (если ошибка только одна) каждый из синдромов вычисляет один из двоичных разрядов номера ошибочного символа.

Синдромы - это суммы по модулю 2, те же самые, которые применялись при вычислении проверочных символов, плюс по модулю 2 сами проверочные символы. Если ошибок нет, то, исходя из принципа вычисления проверочных символов, все синдромы будут равны 0.

Для каждого синдрома суммируются те символы, у которых в двоичном представлении их номеров двоичный разряд с весом, равным номеру синдрома, установлен в 1 (это то самое "N через N начиная с N", но не в виде "закономерности", а какое оно есть на самом деле).

Для Вашего случая:

В синдром номер 1 попадают символы с номерами 1, 3, 5, 7, в двоичном представлении 001, 011, 101, 111. Обратите внимание, это все те, у которых 1 в первом (младшем) разряде (пометил синим).

В синдром номер 2 попадают символы с номерами 2, 3, 6, 7, в двоичном представлении 010, 011, 110, 111. Обратите внимание, это все те, у которых 1 во втором разряде (пометил синим).

В синдром номер 4 попадают символы с номерами 4, 5, 6, 7, в двоичном представлении 100, 101, 110, 111. Обратите внимание, это все те, у которых 1 в третьем разряде (пометил синим).

Поэтому, если вектор содержит только одну ошибку, то двоичное число, составленное из синдромов, начиная со старшего (в данном случае S₄S₂S₁=110₍₂₎=6₍₁₀₎), и будет номером ошибочного символа, поскольку распределение символов по суммам синдромов сделано по весам разрядов двоичной системы счисления. Можно (это то же самое, но в "скрытой" форме) сложить номера синдромов, в которых произошло нарушение чётности, и получить номер символа, в котором произошла ошибка: 2+4=6.

Ответ: ошибка в шестом символе, для вычисления верного сообщения нужно инвертировать шестой символ.

Исправленный вектор: 1101001.

2

Большое спасибо за такой развёрнутый ответ!

0