7.1. Коды Хемминга

Коды Хемминга (R. Hamming) – систематические блоковые коды с параметрами:

– длина кодового блока n = 2^r – 1;

– количество информационных символов k = 2^r – r – 1; (7.1)

– число дополнительных символов r = n – k, r = 2, 3, 4;

– кодовое расстояние d_min = 3.

Коды Хемминга – совершенные коды, исправляющие однократные ошибки.

Выбором параметра r = 2, 3, 4 в соответствии с формулами (7.1) можно задать известные двоичные коды Хемминга. Например, при  r = 3 параметры кода Хемминга (7, 4) будут следующими:

– значность кода n = 7;

– количество информационных символов в кодовом блоке k = 4;

– кодовое расстояние d_min = 3;

– скорость кода R_код = (2^r – r – 1)/(2^r – 1) = 4/7.

порождающая и проверочная матрицы этого кода были рассмотрены ранее, в разд. 4.1 (формулы (4.4) и (4.7)). Как было отмечено ранее, этот код позволяет также обнаруживать двухкратные ошибки. Структуры кодера и синдромного декодера кода Хемминга были рассмотрены ранее в разд. 5.1 (рис. 5.1 и рис. 5.2). В соответствии с формулой (5.3) транспонированная проверочная матрица этого кода имеет вид:

(7.2)

Из этой формулы видно, что размер проверочной матрицы кода Хемминга равен kn = n²(1 – R_код). Это позволяет заключить, что сложность алгоритма декодирования кода Хемминга оценивается степенной функцией вида (6.5).

В теории блоковых кодов часто для нахождения новых кодов используют процедуры модификации порождающих матриц известных кодов. Одной из таких процедур является процедура укорочения кода. В частности, любой систематический (n, k) код можно укоротить, перейдя к (n – b, k – b) коду отбрасыванием b информационных символов в каждой разрешенной комбинации на выходе кодера (например, отбрасыванием b старших разрядов). При таком укорочении отбрасываемые символы заменяются нулями, которые не передаются. но при декодировании декодер их восстанавливает, так что декодирование осуществляется на полной длине кода. Если минимальное расстояние исходного кода равно d*_min, то минимальное расстояние укороченного кода будет не меньше d*_min. Сказанное иллюстрируется следующим примером.

Пример 7.1. Укороченный код Хемминга.

Рассмотрим код (7, 4) с порождающей матрицей

(7.8)

Скорость такого кода равна R_код = 4/7. Укоротим код, исключив в этой матрице первую строку (b = 1). Результатом такого укорочения будет матрица:

(7.9)

Видно, что процедура укорочения изменила скорость кода: R*_код = 3/6. при этом минимальные расстояния исходного кода (7.8) и укороченного кода (7.9) совпадают. К укорочению иногда прибегают с целью изменить формат блокового кода (уменьшить длину блока, например), если это не обходимо, чтобы «встроить» комбинации корректирующего кода в поток символов в телекоммуникационной системе, либо согласовать формат данного блокового кода с форматом иного кода.

7.2. Циклические коды

Значительная часть используемых на практике блоковых кодов относится к классу циклических кодов (ЦК).

Это упрощает процедуры кодирования и декодирования на основе использования циклических свойств кодовых комбинаций.

Если b = (b₀,  b₁, ..., b_n) – разрешенная кодовая комбинация ЦК, то ее циклический сдвиг на произвольное число символов также является разрешенной кодовой комбинацией. Например, слово b⁽¹⁾ = (b_n, b₀, b₁,..., b_n–1) соответствует циклическому сдвигу комбинации b = (b₀,  b₁,..., b_n–1, b_n) на один символ вправо. При этом, в соответствии с правилом циклической перестановки, символы комбинации b смещаются на один символ вправо, а крайний правый символ b_n занимает место крайнего левого символа b₀. Свойства ЦК удобно изучать, представляя кодовые слова в виде многочленов по степеням формальной переменной x, коэффициенты которых есть символы кодовой комбинации: b(x) = b₀ + b₁x + b₂x² +...+ b_nxⁿ. Математические операции (сложение, умножение и деление многочленов) производят по правилам алгебры многочленов, изложенным в разд. 5 пособия [3]. Если сложение и умножение многочленов производится по модулю многочлена (xⁿ – 1), то все возможные многочлены степени (n – 1) и меньше образуют алгебраическое кольцо^ многочленов R_n со свойствами, изложенными там же.

Для построения циклического кода в кольце R_n выбирают подмножество многочленов – идеал I. Многочлен минимальной степени g(x) в этом подмножестве называется порождающим многочленом ЦК. В качестве порождающих многочленов ЦК выбирают неприводимые многочлены^*.

В алгебре многочленов целой степени неприводимые многочлены играют такую же роль, какую простые числа играют в алгебре целых чисел. Подробная таблица порождающих многочленов циклических кодов приведена в приложении А.1. Порождающие многочлены коротких циклических кодов приведены в табл. 7.1.

Таблица 7.1 – Порождающие многочлены коротких циклических кодов

Максимальная степень порождающего многочлена	порождающий многочленg(x)
3	x^3+x^2+1	x^3+x+1
4	x^4+x+1	x^4+x^3+1
5	x^5+x^2+1	x^5+x^3+1	x^5+x^4+x^2+1
6	x^6+x+1	x^6+x^5+1	x^6+x^5+x^3+x^2+1

Все многочлены идеала I, соответствующие разрешенным кодовым комбинациям ЦК, делятся на порождающий многочлен g(x) без остатка, что позволяет формулировать следующее правило кодирования:

правило кодирования несистематического ЦК имеет вид:

b(x) = a(x)·g(x). (7.3)

На практике часто используют систематические циклические коды. Правило кодирования систематического циклического (n, k) кода имеет вид:

b(х) = a(х)·х^n–k + r(х), (7.4)

где r(х) – остаток от деления a(х)·х^n–k на g(x).

правило кодирования (7.4) может быть реализовано таким алгоритмом кодирования систематическим циклическим кодом:

1. К комбинации первичного кода a дописывается справа (п – k) нулей, что эквивалентно умножению многочлена a(х) на х^n–k.

2. Произведение a(х)·х^n–k делится на порождающий многочлен g(x), в результате деления определяется остаток r(х).

3. Вычисленный остаток складывается со смещенной комбинацией a(х)·х^n–k, в результате чего формируется разрешенная кодовая комбинация:

b(х) = a(х)·х^n–k + r(х). (7.5)

Пример 7.2 Формирование кодовой комбинации ЦК (10, 5).

Для заданной первичной кодовой комбинации a = (10110) сформируем кодовую комбинацию циклического кода (10, 5). Многочленное представление заданной комбинации будет: a(x) = x⁴+x²+x.

У заданного ЦК параметры п = 10, k = 5, r = (п – k) = 5. По табл. 7.1 выбираем, например, порождающий многочлен g(х) = x⁵ + x⁴ + x² + 1. Выполним математические операции в соответствии с алгоритмом (7.5):

1) a(х)·х^(n–k) = (x⁴ + x² + x)·x⁵ = x⁹ + x⁷ + x⁶;

2) a(х)·х^(n–k)/ g(x) 

	x^9 + х^7 + x^6		х^5 + х^4 + х^2 + 1
	x^9 + х^8 + x^6 + x^4		х^4 + x^3 + 1
	x^8 + х^7 + x^4
	х^8 + x^7 + x^5 + x^3
	х^5 + x^4 + x^3
	х^5 +x^4 + x^2 + 1
	х^3 + x^2 + 1= r(x)

3) Многочлен разрешенной кодовой комбинации

b(х) = a(х)·х^n–kr(х) = х⁹ + x⁷ + x⁶ + x³ + х² + 1.

Многочлену b(х) = х⁹ + x⁷ + x⁶ + x³ + х² + 1 соответствует комбинация двоичных символов b = (1011001101), в которой первые четыре символа являются информационными, а остальные – дополнительными.

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

Если (x) = b(x)  e(x) – кодовая комбинация на входе декодера, содержащая многочлен ошибок e(x) = e₀ + e₁x + ...  + e_nxⁿ, то в результате деления получаем:

(x)/g(x) = q(x) + s(x)/g(x). (7.6)

Здесь: q(x) – произвольный многочлен («целое»), s(x) – многочлен синдрома, равный остатку от деления (x) на g(x). Он имеет степень не выше(n – k – 1).

В отсутствие ошибок синдром s(x) = 0. По виду ненулевого синдрома можно установить местоположение ошибок в кодовой комбинации на входе декодера и использовать эту информацию для декодирования с исправлением ошибок.

Пример 7.3. Синдромное декодирование комбинаций циклического кода (7, 4).

Задана кодовая комбинация двоичного первичного кода a = (1010), подлежащая передаче по каналу с ошибками. Выберем циклический код, обеспечивающий безошибочную передачу этой комбинации в этих условиях. По табл. А.1 приложения А определяем, что поставленную задачу можно решить при использовании ЦК с порождающим многочленом g(х) = (x3+x²+1) и параметрами n = 7, k = 4, q_исп = 1. Покажем, как реализуется метод синдромного декодирования для исправления однократных ошибок.

Используя алгоритм кодирования (7.5), сформируем разрешенную комбинацию выбранного ЦК: b(x) = x⁶ + x⁴ + 1. Положим, что в канале действует однократная ошибка e(x) = x⁶. В этом случае комбинация на входе декодера имеет вид (x) = b(x)  e(x) = x⁴ + 1. Используем правило нахождения синдрома (7.6). при синдромном декодировании по виду синдрома можно установить местоположение ошибки (т.е. выполнить синдромное декодирование). Для этого необходимо составить таблицу синдромов и соответствующих им многочленов ошибок. Для составления такой таблицы необходимо воспользоваться равенством, вытекающим из (7.6) при q(x) = 0:

s(x) = e(x)/g(x) (7.7)

В табл.7.2 представлены результаты вычислений по этой формуле многочленов синдрома s(x) для различных многочленов ошибок. В целях наглядности значения синдромов представлены в виде двоичных комбинаций.

Таблица 7.2 – Соответствие между синдромами и многочленами ошибок

Многочлен ошибки e(x)	x^6	x^5	x^4	x^3	x^2	x	1
Синдром s(x)	x^2+x	x + 1	x^2+x + 1	x^2+ 1	x^4	x^2	1
Двоичное представление синдрома s	110	011	111	101	100	010	001

Пусть многочлен принятой из канала комбинации имеет вид (x) = x⁴ + 1. Выполним операцию деления (x)/g(x):

	x^4 + 1		х^3+х^2+1
	x^4 + х^3 + x		х+1
	х^3 +x + 1
	х^3 + x^2 + 1
	x^2 + x = s(x)	– синдром

По табл. 7.2 находим, что такому синдрому соответствует многочлен ошибки e(x) = x⁶. Исправление ошибки состоит в сложении кодовой комбинации на входе декодера с многочленом ошибки , что совпадает с переданной разрешенной комбинацией b(x) = x⁶ + x⁴ + 1. Этому соответствует двоичная комбинация b = (1010101), в которой первые четыре символа есть безошибочно переданные символы первичного кода = (1010) (поскольку используемый ЦК – систематический).

На практике находят применение коды с циклическими свойствами^:

1. Код Голея (Goley) (23, 12) – совершенный циклический код с порождающим многочленом g(x) = x¹¹ + x¹⁰ + x⁶ + x⁵ + x⁴ + x² + 1 и кодовым расстоянием d_min = 7.

2. Расширенный код Голея (24, 12) с кодовым расстоянием d_min = 8 получают при добавлении общей проверки на четность.

3. Коды Боуза-Чоудхури-Хоквингема (БЧХ) (Bose, Ray-Chaudhuri, Hochuenghem), которые образуют обширный класс ЦК. Двоичные коды БЧХ имеют параметры: n = 2^m – 1, (n – k)m·t, d_min = 2t + 1, где m (m 3) и t – произвольные положительные целые числа.Теоретические сведения о кодах БЧХ приведены в разд. 10.4 учебника [1].

4. Коды Рида-Соломона (РС) (Reed-Solomon) – подкласс недвоичных кодов БЧХ с параметрами: символы кода выбираются из поля GF(q), q = 2^m, m – целое, длина блока (число q-ичных символов) N = (q – 1), количество информационных символов k = (N – 2q_исп), минимальное расстояние d_min= (2q_исп+1). Возможно также расширение кода до N = q либо до N = (q + 1). Алгебраическая структура кода РС описывается с использованием арифметики поля Галуа^** GF(2^m). При фиксированной скорости кода и длине блока коды РС обеспечивают наибольшее минимальное расстояние между словами. Их удобно использовать для исправления пакетов ошибок, а также в каскадных системах кодирования в качестве внешних кодов.

Эффективное использование циклических свойств разрешенных комбинаций циклических кодов позволяет реализовать достаточно простые алгоритмы декодирования ЦК. считается, что сложность реализации алгоритмов декодирования циклических кодов описывается степенной функцией C_д = n^k , где k – малое число, величина которого зависит от конкретной реализации алгоритма. Ниже приведены примеры реализации алгоритмов кодирования и декодирования ЦК. При этом широко используется математический аппарат алгебры степенных многочленов и описания многотактных линейных фильтров, представленные в разд. 5 и 6 рекомендованного учебного пособия [3].

Пример 7.4. Структура кодера систематического ЦК.

Используя алгоритм (7.5) кодирования систематическим ЦК сформируем структурную схему кодера циклического кода (15, 11), с порождающим многочленом g(x) = x⁴ + x + 1, который выбран из табл. 7.1. Схема систематического кодера приведена на рис. 7.1.

В соответствии с алгоритмом (7.5) кодер работает следующим образом. Первоначально переключатели П1 и П2 находятся в положении 1. Одиннадцать информационных символов кодируемой комбинации a(x) вводятся слева в цепь деления на многочлен g(x) = x⁴ + x + 1. Одновременно они через последовательно соединенные элементы задержки поступают на выход кодера, образуя информационную часть разрешенной кодовой комбинации a(х)·х^n–k. За первые четыре такта в ячейках регистра сдвигов схемы делителя на порождающий многочлен образуется остаток от деления r(х).

Затем переключатели П1 и П2 устанавливаются в положение 2, процесс деления прекращается, и остаток считывается с выхода делителя и дописывается в проверочную часть выходной кодовой комбинации b(x)=a(х)·х^n–k + r(х).

Пример 7.5. Структура кодера несистематического ЦК.

Используя правило кодирования (7.3) несистематического ЦК сформируем структурную схему кодера с порождающим многочленом g(x) = x⁴ + x + 1.

Правило кодирования (7.3) предусматривает перемножение многочленов a(x) и g(x). Используя структуру перемножителя многочленов из разд. П.6.1 учебного пособия [3], схему кодера представим на рис. 7.2.

Непременным элементом схем кодеров и декодеров циклических кодов является схема деления многочлена на многочлен для вычисления остатка от деления при кодировании систематическим кодом по алгоритму (7.5), а также для вычисления синдрома при синдромном декодировании по алгоритму (7.6). Структура таких схем делителей рассмотрена в разд. П.6.1 учебного пособия [3].