go • • 0 go

(1.51)

0 0 ...0 0

k~\A

Линейный блоковый код называется циклическим, если циклический сдвиг кодового слова U = (м;, W)t-i •••"!) Д вектор Ui = - .. . , Wb k) также являющийся кодовым словом. Такой код

порождается с помощью матрицы (1.51).

Проверочная матрица как ортогональный базис линейного блокового кода. Всякая матрица Н размера т X п, ортогональная порождающей матрице G размера кХ {т +/:) =кХ п, называется проверочной или контрольной.

Таким образом, по определению, матрица Н - это ортогональный базис к базису (проверочной матрице) G и

(1.52а) (1.526)

GH =0; HG =0.

Умножив слева на вектор Q соотношение (1.52а) или справа - на вектор соотношение (1.526), получим

QGH =0; HGQ =0.

Откуда с учетом зависимостей (1.47) и (1.48) следует

иН = 0;

ни = 0.

(1.53а) (1.536)

Таким образом, линейный блоковый код может быть определен и как множество векторов [u), удовлетворяющих соотношениям (1-53).

Проверочная матрица Н систематического кода находится по последней матрице в формуле (1.49) и представляется в следующей форме:

Н=[А

(1.54)

Проверочная матрица циклического кода имеет вид

«

.ho • •

(1.55)

1610

Линейный блоковый код тогда и только тогда имеет минимальное кодовое расстояние когда любая совокупность из (i - 1 столбцов проверочной матрицы Н линейно независима.

Следовательно, с помощью (л,/:)-кода можно исправить v произвольных ошибок, если его проверочная матрица Н размера {п - к)Хп состоит из 2и линейно независимых столбцов, где учтено неравенство (1.3).

В частности, (л, А;)-код с проверочной матрицей Н размера тХ п, содержащей все ненулевые двоичные векторы длины ш, имеет кодовое расстояние d = Зи называется кодом Хэмминга.

Минимальное кодовое расстояние d любого линейного блокового (л, А;)-кода связано с его параметрами л и А; неравенством:

л-А;+1=т + 1.

(1.56)

Если d = л-А;+1, то такой код называется максимально разделимым или МДР-кодом. Важный подкласс циклических МДР-кодов рассмотрен в гл. 6.

Заключение. Как мы видели, вектор U является кодовым словом, если и только если он удовлетворяет равенству UH = 0. Ддя обнаружения ошибок проверка произведения UH на равенство нулю является достаточной. Исправление ошибок - существенно более сложная задача.

Если кодовое слово U содержит ошибки, то иНФО. Обозначим произведение UH символом S, а вектор ошибок - символом е = = in-i • • • 1» о)» где согласно неравенству (1.3) количество

ненулевых компонент 6,-, / =0, 1, . .., л - 1, т. е. число ошибок должно быть менее половины кодового расстояния d используемого (л, А;)-кода.

Так как код линеен, то

иН = (и-\-е)Я =иН + еН = вЯ =5, (1.57)

Вектор S = {Sq, Sj, .. ., j) называется синдромом и определенным образом характеризует вектор ошибок е - местоположение (локаторы) ошибок и их величину (вес).

Любой вектор можно представить в виде полинома, например S (z) = So + Siz + 2 + ... + 5 iz" -i. Полином a(z), имеющий корни, обратные локаторам ошибок, называется полиномом локаторов, а полином cj(z), корни которого совпадают с весами ошибок, - полиномом весов или просто - полиномом ошибок. Оба полинома связаны соотношением

5(z)a(z) =cj(z), modz

(1.58)

Итак, первая задача декодирования - вычисление синдрома S. Он вычисляется на основании соотношения (1.57) по принятому, возможно с ошибками, кодовому слову U. Если 5 = О, то на основании принципа максимального правдоподобия считаем, что ошибок нет (или их более

0,5с?, но для их исправления данный код не предназначен). В противном случае, при S Ф О, возникает так называемая проблема декодирования.

Как правило, локаторы ошибок и их веса связаны с синдромами системой нелинейных уравнений. Эта система для большого и важного класса линейных кодов может быть сведена к ганкелевой (теплицевой) системе линейных уравнений относительно коэффициентов полинома a(z). Методы сведения подобной системы к одному уравнению - уравнению локаторов - приведены в гл. 2. Для удобства читателей в этой главе рассматриваются матрицы и полиномы не над конечными полями, используемыми в теории помехоустойчивого кодирования, а над полями вещественных чисел. Материал, позволяющий производить операции над конечными полями приведен в гл. 3.

Таким образом, вторая задача декодирования - составление уравнения локаторов по известному (вычисленному по принятому кодовому слову и) синдрому 5.

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

Третья задача декодирования во временной области - решение уравнения локаторов, что позволяет найти местоположение ошибок в кодовом слове; после этого ошибки могут рассматриваться как стирания.

Четвертая задача декодирования состоит в решении системы линейных уравнений относительно величин ошибок (методы решения уравнений над полями Галуа приведены в гл. 5).

Декодирование в частотной области позволяет не вычислять позиции и величины ошибок независимо друг от друга, а найти (путем продолжения синдрома) спектр конфигурации ошибок. Рекуррентные и безрекуррентные методы вычисления продолжения синдрома, как "особого продолжения" ганкелевой (теплицевой) матрицы, изложены в гл. 2.

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

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

, Примеры кодирования и декодирования для важных классов помехоустойчивых кодов над конечными полями даны в гл. 6.

Читателя, желающего глубже изучить вопросы теории помехоустойчивого кодирования, отсылаем к капитальным трудам [8, 11, 14, 15, 22, 30, 36, 40, 43, 46].