Классические итеративные коды

Идея создания рассматриваемых кодов принадлежит П. Элайесу. Каждая из отдельных последовательностей информационных символов кодируется определенным линейным кодом (групповым или циклическим). Получаемый, таким образом, итеративный код так же является линейным. Простейший из таких кодов является двухстепенной (двумерный) код с проверкой на четность по строкам и столбцам, который широко используется на практике для обнаружения ошибок на магнитной ленте. Расположение информационных и проверочных символов приведено на рис. 8.1.

Рис. 8.1

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

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

Исправление при тройной ошибке соответствует внесению новой ошибки, вместо исправления старой (ложное исправление, рис. 8.2, г).

Простейшая не обнаруживаемая ошибка содержит четыре искаженных символа, расположенных в вершинах прямоугольника (рис. 8.2, д).

Рис. 8.2

Число ошибок такого вида В4 для блока из l · n символов равно:

Общее число четырехкратных ошибок составляет:

.

Таким образом, отношение

.

При n = 8; l = 250 имеем:

.

Аналогичный расчет для шестикратных ошибок (рис. 8.3) типа

.

Рис. 8.3

Минимальное кодовое расстояние итеративного кода равно:

где D_γ – кодовое расстояние линейного кода по координате γ.

Коррекция ошибок проводится последовательно. Сначала исправляют ошибки по одной координате, затем осуществляют исправление оставшихся ошибок по другой координате и т.д. http://peredacha-informacii.ru/ Такая процедура проста, но снижает корректирующую способность итеративного кода, поскольку оказывается невозможным исправить часть ошибок кратности (d – 1)/2.

Имеем два кода Хэмминга (7; 4).

Результирующий итеративный код (49; 16) имеет минимальное кодовое расстояние, равное 3 · 3 = 9, и, следовательно, потенциально, как любой линейный код, способен исправлять все ошибки кратности 4 и менее. Однако, применяя указанную выше процедуру декодирования, невозможно исправить четырехкратные ошибки с расположением искаженных символов в вершинах прямоугольника.