1.4 Код Хэмминга для исправления одиночных ошибок и обнаружения двойных ошибок

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

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

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

1.5 Циклические коды

Циклические коды (CRC - Cyclic Redundance Code) – это семейство помехоустойчивых кодов, включающее в себя в качестве одной из разновидностей коды Хэмминга. В целом оно обеспечивает большую гибкость с точки зрения возможности реализации кодов с необходимой способностью обнаружения и исправления ошибок, определяемой параметром d0, по сравнению с кодами Хэмминга (для которых d0=3 или d0=4). Широкое использование циклических кодов на практике обусловлено также простотой реализации соответствующих кодеров и декодеров.

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

Циклические коды задаются с помощью так называемых порождающих полиномов (многочленов) или их корней. Порождающий полином имеет вид

где .

Кроме того, вводятся полином исходного сообщения:

и кодированного сообщения

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

Рассмотрим последовательность кодирования на примере циклического кода (7,4,3), имеющего . Код характеризуется тройкой чисел , где – общее число разрядов в передаваемом сообщении, включая проверочные ( ), – число информационных разрядов, – минимальное кодовое расстояние между разрешенными кодовыми комбинациями, определяемое как минимальное число различающихся бит в этих комбинациях.

1) информационная часть сообщения записывается в виде полинома:

В рассматриваемом примере =4 и для сообщения 0111 получается

2) умножается , что соответствует циклическому сдвигу исходного сообщения на разрядов влево:

3) полученный многочлен делится на :

где – полином-частное с максимальной степенью ;

– полином-остаток с максимальной степенью ;

– обозначение поразрядной операции суммирования по модулю 2 (исключающее ИЛИ). Кодированное сообщение представляется в виде

Таким образом, в этом случае

Передаваемое кодированное сообщение в обычной двоичной форме имеет вид:

0111	010
↔	↔
– бит	– бит

Три порождающих многочлена стали международными стандартами:

CRC-12 = x12 + x11 +x3 + x2 + x1 + 1;

CRC-16 = x16 + x15 + x2 + 1;

CRC-CCITT = x16 + x12 + x5 + 1.

Все три многочлена делятся на x + 1. CRC-12 используется для символов длиной в 6 бит. Остальные применяются для 8-битовых символов. 16-битовые контрольные суммы, такие как CRC-16 и CRC-CCITT, обнаруживают все одинарные и двойные ошибки, все ошибки с нечетным количеством бит, все пакеты ошибок длиной не более 16 бит, 99,997 процента 17-битовых пакетов ошибок и 99,998 процента пакетов ошибок длиной в 18 и более бит.