Материал: 6593

116

ется на ее выход.

Ниже приведены краткие данные наиболее распространенных систематических кодов.

Код Хэмминга имеет кодовое расстояние, равное трем, и полностью характеризуется числом проверочных символов r. Общее число символов в кодовом слове равно n=2r-1. В качестве столбцов проверочной матрицы Н выбираются всевозможные r- разрядные двоичные числа, исключая число нуль.

Код Рида-Малера полностью характеризуется двумя целыми положительными числами: m≥З и δ<m. Число δ называется порядком кода. Остальные параметры кода определяются из соотношений:

i=1

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

двоичных чисел. Следующие Cm2 строк (базисные векторы вто-

рого порядка) получают, вычисляя поэлементные произведения различных пар базисных векторов первого порядка, и т.д. до получения базисных векторов δ-го порядка.

Циклический код полностью определяется первой строкой производящей матрицы G. Остальные строки получают в результате циклического сдвига первой строки на 1,2,...,k-1 элементов. Таким же циклическим свойством обладает и проверочная матрица Н.

Более удобным является общепринятое описание кодовых комбинаций циклического кода при помощи полиномов. Кодовой комбинации v=(v0,v1,…,vn-1) соответствует полином

v(x)= v0x0+ v1x1+,…,vn-1xn-1. Способы кодирования и декодирования для конкретного кода полностью определяются, если задать производящий полином g(x)=1+g1x+ g2x2+…+ gr-1xr-1+xr.

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

117

РЕШЕНИЕ ТИПОВЫХ ПРИМЕРОВ Пример 4.3.1. Способ кодирования задан кодовой табли-

цей

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

г) Избыточность кода находим из следующих соображений. Для передачи равновероятных сигналов a1, а2, а3, а4 достаточно передавать кодовые слова 00, 10, 01 и 11 соответственно. Такой код не имеет избыточности, но не позволяет обнаруживать и, тем более, исправлять ошибки. Для обнаружения и исправления ошибок введены пять избыточных символов, т.е. количественно

избыточность равна R = (7 −2)7 = 71% .

Пример 4.3.2. Линейный блочный (5,2)-код задан производящей матрицей в систематической (канонической) форме

118

щими методами:

а) по минимуму расстояния; б) вычислением синдрома.

Решение. Если производящая матрица записана в каноническом виде, это значит, что она состоит из двух блоков: диагональной матрицы размера k×k, состоящей из единиц, и прямоугольной матрицы размера r×k. В этом случае первые k символов в любом кодовом слове являются информационными.

Проверочная матрица Н также может быть записана в каноническом виде и состоит из двух блоков. Первый блок есть прямоугольная матрица размера k×r, полученная транспонированием второго блока матрицы G. В качестве второго блока матрицы Н записывают диагональную матрицу размера r×r, состоящую из единиц.

Для заданного кода получаем

10100 Н = 11010 .

01001

Убедимся, что полученная таким образом матрица Н удовлетворяет соотношению (4.3.3). Действительно,

h1g1 = (10100) (10110) = 0, h1g2 = (10100) (01011) = 0,

............................................

h3g2 = (01001) (01011) = 0,

т.е. все 6 элементов матрицы GHT равны нулю.

Построим кодовую таблицу, воспользовавшись правилом образования кодовых слов по формуле (4.3.4):

a1=00000, а2=10110, а3=01011, а4=11101=a2+a3.

Всего кодовая таблица содержит 2k = 4 вектора.

Из кодовой таблицы определяем величину кодового рас-

стояния dкод = 3.

Следовательно, рассматриваемый код обнаруживает однократные и двукратные ошибки и исправляет однократные.

Декодируем принятый вектор b = 00110.

а) Метод декодирования по минимуму расстояния заклю-