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

 

В теории и технике помехоустойчивого кодирования первостепенное значение отводится решению двух задач:

- построение кода, создание алгоритма кодирования и его реализация;

- создание алгоритма декодирования и его реализация.

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

В случае линейных блоковых кодов построение кода сводится к получению выражений проверок на четность на позициях символов в кодовом слове. Здесь под проверкой на четность понимается сумма по модулю 2. В дальнейшем знаком суммы «+» обозначим операцию суммирования по модулю 2. Выражения для проверок могут быть представлены в следующем виде:

- уравнений в символьном виде (например, );

- проверочной матрицы;

- порождающей матрицы;

- порождающего многочлена;

- проверочного многочлена.

Наиболее распространены и удобны выражения для проверок в виде порождающих и проверочных матриц, порождающих и проверочных многочленов.

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

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

Пример. Пусть проверочная матрица для кода (7,4) определена следующим образом:

.

(1.6)

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

,

(1.7)

где - первый информационный символ, третий символ в кодовом слове;

- второй информационный символ, пятый символ в кодовом слове;

- третий информационный символ, шестой символ в кодовом слове;

- четвертый информационный символ, седьмой символ в кодовом слове;

- первый проверочный символ, первый символ в кодовом слове;

- второй проверочный символ, второй символ в кодовом слове;

- третий проверочный символ, четвертый символ в кодовом слове.

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

Пример. Для (7,4) (n,k)-кода, кодовое слово которого задается выражением (1.7), а проверочная матрица - выражением (1.6), порождающая матрица имеет вид:

.

(1.8)

Следует заметить, что матричное произведение при этом будет равно нулю, что является показателем правильности построения этих матриц.

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

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

.

(1.9)

Тогда при умножении принятого слова на проверочную матрицу получится вектор синдрома :

.

(1.10)

Из выражения (1.10) видно, что вектор синдрома зависит только от комбинации ошибок и равен нулю в двух случаях:

- когда вектор ошибки равен нулю;

- когда вектор ошибки содержит комбинацию ошибок, совпадающую с кодовым словом.

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

Кроме матричного представления коды могут быть построены с использованием полиномиального представления кодового слова. Суть такого представления состоит в том, чтобы считать элементы кодового слова длины коэффициентами некоторого многочлена степени , т.е. кодовое слово будет представляться многочленом:

.

(1.11)

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

.

(1.12)

Кодовое слово может быть получено тремя путями:

- умножением полиномов и ;

- умножением полинома на коэффициент ; делением полученного произведения на полином и сложением произведения с остатком от деления;

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

При втором способе кодовое слово получается в систематическом виде, т.е. коэффициентов при старших степенях (от до ) определяют информационные символы. Остальные коэффициенты многочлена кодового слова (при степенях …0) - проверочные.

Порождающая матрица на основе полинома g(x) имеет следующий вид (только для циклических кодов):

,

(1.13)

где - коэффициенты порождающего многочлена.

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

Необходимо отметить, что при любом способе кодирования кодовое слово делится на порождающий многочлен без остатка.

Проверочным многочленом называется многочлен степени k, полученный при делении (без остатка) полинома () на g(x). Отсутствие остатка является признаком, того, что код, порождаемый многочленом g(x), является циклическим. Проверочный многочлен h(x) можно получить таким способом только для циклического кода.

Проверочный многочлен может быть использован для получения проверочной матрицы, которая будет иметь вид:

,

(1.14)

где - коэффициенты проверочного многочлена.

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

Синдромным многочленом называется многочлен степени , являющийся остатком от деления принятой последовательности на порождающий многочлен, т.е.

.

(1.15)

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

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

Многочлены принято описывать не в виде (1.11), а в восьмеричной или двоичной форме, т.е. записывая только коэффициенты. Значение степени , при которой находится коэффициент в многочлене, определяет номер разряда, в котором коэффициент записывается в двоичной записи. Для сокращения записи двоичная форма представления многочлена переводится в восьмеричную запись.

Пример. Многочлену соответствует двоичное число 1011 и восьмеричное - 13.