Двоичные коды, исправляющие ошибки

Как уже упоминалось, s-кратная ошибка принципиально может быть исправлена, если d_min ≥ 2s + 1. Существуют два метода построения кодов с исправлением ошибок: группировка кодов спутников; проверка на четность в определенных разрядах разделимого систематического кода (построение опознавателя ошибок).

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

В разделимых систематических кодах все символы разделяются на информационные n_и и проверочные (защитные) n₃, т.е.

(49.26)

Значения проверочных символов находятся по определенной системе.

Сокращенно разделимые систематические коды обозначаются (n, n_и ), т.е. в скобках указывается суммарное число символов в кодовой комбинации и число информационных символов.

Значение проверочных символов определяется как сумма по модулю 2 определенных информационных символов. Количество проверочных символов совпадает с количеством проверок на четность и должно быть таким, чтобы можно было найти номер искаженного символа (как информационного, так и проверочного). Номер искаженного символа позволяет восстановить исходную кодовую комбинацию. Таким образом, в результате проверок должен формироваться код-опознаватель, указывающий номер искаженного символа.

Код Хэмминга. Этот разделимый систематиче­ский код, например (7, 4), т.е. n = 7, n_и = 4, n₃ = 3. Любой из семи символов кода может быть искажен. В табл. 49.7 даны номера разрядов кодовой комбинации кода Хэмминга и вектора кода-опознавателя, которые указывают номер разряда, в котором символ искажен.

Таблица 49.7

Номер разряда кода Хэмминга	1	2	3	4	5	6	7
Вектор кода- опознавателя	001	010	011	100	101	110	111

Проверки на четность (их число равно n₃, т.е. 3) должны сформировать вектор кода-опознавателя, укатывающего номер искаженного разряда. Из табл. 49.7 ясно, что «1» в первом разряде вектора кода-опознавателя должна иметь место, если искажены символы в разрядах 1, 3, 5 или 7; «1» во втором разряде вектора кода-опознавателя — при ис­кажении разрядов 2, 3,6 или 7; и «1» в третьем разряде кода-опознавателя — при искажении разрядов 4, 5, 6 или 7 в кодовой комбинации кода Хэмминга. Следовательно, условия проверки на четность имеют вид сумм по модулю 2 указанных разрядов кода Хэмминга, т.е.

u₁ u₃ u₅ u₇=0;

u₂ u₃ u₆ u₇=0; (49.27)

u₄ u₅ u₆ u₇=0,

где u_i — содержимое i-го разряда кола Хэмминга. Проверочные разряды должны входить в условия (49.28) по одному разу, т.е. проверочным и являются разряды 1, 2 и 4. Их содержимое определяется из условий (49.27), т.е.

u₁=u₃ u₅ u₇;

u₂= u₃ u₆ u₇; (49.28)

u₄=u₅ u₆ u₇,

Пусть, например, передаваемое сообщение — двоичное число 1011, тогда содержимое информационных разрядов соответствующей кодовой комбинации кода Хэмминга u₃ = 1, u₅ = 1, u₆ = 0, u₇ = 1, а содержимое проверочных разрядов согласно (49.28) u₁ = 1, u₂ = 0, u₄ = 0, т.е. кодовая комбинация имеет вид 1010101.

Циклический код. Защитоспособность циклического кода основана на том, что исходная комбинация безызбыточного двоичного кода на передающем конце умножается на определенное число, а на приемном конце принятая кодовая комбинация делится на то же число. Если деление произошло без остатка, сообщение считается достоверным. При наличии остатка сообщение бракуется.

Циклический код, как и код Хэмминга, представляет собой разделимый систематический код, причем информационные символы занимают старшие, а проверочные символы — младшие разряды кодовой комбинации.

Запись кодовой комбииации циклического кода может быть представлена в виде полинома х, например,

(49.29)

где n — число разрядов кода; a_i(1 или 0) — разрядные коэффициенты. Например, кодовая комбинация 01001 может быть записана как F(x) = x³ + 1.

Циклический код характеризуется образующим (порождающим) полиномом Р(х) степени К = n₃ = п – п_и. Вид Р(х) и его степень определяют корректирующую способность кода. Все рабочие комбинации циклического кода делятся на Р(х) без остатка. При делении на Р(х) запрещенной кодовой комбинации обязательно имеется остаток. По виду остатка возможна корректировка принятого сообщения.

Циклический код может быть образован путем умножения полинома Q(x) степени (п_и - 1), соответствующего кодовой комбинации двоичного безызбыточного кода с числом разрядов n_и, на образующий полином Р(х) степени k, т.е.

(49.30)

Однако при таком способе получения кодовой комбинации циклического кода информационные и проверочные разряды оказываются неразделенными, что затрудняет процесс декодирования (т.е. код оказывается неразделимым). Поэтому используется другой способ формирования кодовых комбина­ций циклического кода. Полином Q(x) умножается на одночлен х^k, а затем делится на образующий полином Р(х):

(49.31)

Частное С(х) имеет ту же степень, что и Q(x) (т.е. п_и - 1). Если Q(x) • х^k не делится на Р(х), появляется остаток R(x), т.е.

(49.32)

Поскольку С(х) имеет ту же степень, что и Q(x), оно является кодовой комбинацией исходного безызбыточного кода.

Степень остатка R(x) не может быть больше степени Р(х). Наивысшая степень R(x) есть (К- 1), следовательно, R(x) имеет число разрядов не более К.

Умножая обе части равенства (49.32) на Р(х) и группируя члены произведения, можно получить следующее выражение для кодовой комбинации циклического кода:

(49.33)

При таком способе формирования циклического кода информационные символы занимают в кодовой комбинации л_и старших разрядов, а проверочные — k = n₃ младших разрядов.

Таблица 49.8

Информационные символы	Проверка по строкам
u11u12…u1j…u1m
u21u22…u2j…u2m
ui1ui2…uij…uim
ul1ul2…ulj…ulm
Проверка по столбцам	Проверка проверок

Итеративный код. Информационные символы в этом коде записываются в виде таблицы с l строками и m столбцами (табл. 49.8). Столбец (m + 1) и строка (l + 1) содержат суммы по модулю 2 информационных символов соответственно строки или столбца. Значение проверки проверок находится как сумма но модулю 2 символов последней (проверочной) строки и столбца.

Приведенный в табл. 49.8 код является простейшим двухступенчатым итеративным кодом (d_min = 4). Передача кодовых комбинаций осуществляется построчно, включая проверочные символы каждой строки. Последней передается строка, состоящая из значений проверок по столбцам и значений проверки проверок. При приеме кодовых комбинаций осуществляется проверка строк и столбцов на четность.

Простейший итеративный код позволяет очень просто корректировать ошибку. Если не выполняется проверка на четность строки i, столбца j, то символ u_ij должен быть заменен на противоположный.

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

d_1mind_2min, d_1min - где минимальное кодовое расстояние между комбинациями по строкам, d_2min —

19