Алгебры, т. е. множества К с указанными операциями, являются конечными полями,или полями Галуа. Особенности этих алгебр и правила выполнения операций будут рассмотрены далее (вкратце - в § 1.3, а подробнее - в гл. 3). Однако методически удобнее основные принципы кодирования и декодирования с контролем ошибок вначале изложить для сообщений, символы которых принадлежат (бесконечному) полю рациональных чисел с обычными арифметическими операциями. Тогда читатель, недостаточно подготовленный в специальных разделах конечных алгебр, сможет на первом этапе сконцентрировать внимание исключительно на вопросах помехоустойчивого кодирования и проблеме декодирования.

Простейшие блоковые коды над полем рациональных чисел и процедура кодирования. Предположим, что задано сообщение Q = \Qf,

Qk~-\ • • • > 62> Q\\ длины к, образованное из к произвольных рациональных чисел (для простоты - целых). Для того чтобы можно было исправить V ошибок, т.е. обеспечить кодовое расстояние d = 2у+1, необходимо ввести т - 2v проверочных символов. Пусть для определенности к ~ 2, d = 3, тогда m = 2 и сформировано кодовое слово вида

V ={G2GiP2Pi}. (1.4)

Мы рассматриваем линейные блоковые коды, т. е. такие, в которых проверочные символы р2. Pi являются заданными линейными функциями от информационных символов Q2>Qt-

Рг = CI2Q2 + iGi; Pi = 22 + bxQi (1.5)

где , - некоторые, отличные от нуля числа, например целые / - 1,2.

Кодовое слово (1.4), в котором проверочные символы удовлетворяют равенствам (1.5), может быть найдено как скалярное произведение информационного вектора б = {Q2Q1) на матрицу

10 22

0 1 ал bx

(1.6)

а именно: v - QG.

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

G= [Е \ Л] или G[A\ Ej], (1.7)

где £V ~ единичная матрица порядка к; А ~ некоторая матрица размера кХ т.

* Эварист Галуа (Е. Galois, 1811-1832) - гениальный французский математик, основоположник современной алгебры.

Использование матрицы G в форме (1.7) обеспечивает систематическое кодирование, так как информационные символы Q2, Q\ входят в кодовое слово (1.4) в неизменном виде.

Итак, процедура кодирования линейным блоковым кодом сводится к умножению сообщения Q на порождающую матрицу G.

Если числа д-, Ь, z = 1, 2,в соотношениях (1.5), (1.6) произвольны, то информационные символы не могут быть выбраны любыми, а для

каждой пары сообщений - (62» Gi } н бГ) . должно соблю-

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

(1-8)

Ограничительное условие (1.8) получено из предположения, что QlQi и QxQi . Тогда требование d~3 будет обеспечено, если хотя бы для одной пары проверочных символов окажется выполненным неравенство рз Фрг или р\ Ф р i - Учитывая зависимости (1.5), можно получить неравенства (1.8).

Отсутствие свободы в выборе символов является существенным недостатком. Принципиально удобнее ограничения налагать на числа щ, bjy i - 1, 2, в формулах (1.5) и в матрице (1.6). Найдем для чисел а, bf запретные условия, при которых р2 = Р2 и р i = pl, что не обеспечивает требуемого кодового расстояния с? = 3 даже при Q2 Ф Q2

Искомые запретные условия следуют из соотношения (1.8) при замене знаков неравенства на знаки равенства, т. е. при

2/1 = 2/1 или агЬх ~ ауЬг 0.

(1.9)

Левая часть во втором равенстве (1.9) представляет собой определитель Д матрицы Л, входящей в матрицу G (1.7). Следовательно, при Д = О кодовое расстояние с? < 3. Условие Д - О означает, что столбцы (строки) в матрице Л линейно зависимы; наоборот, если они независимы, то As О [33] и

(1.10)

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

Декодирование линейного блокового кода с исправлением одной ошибки. Проверочные символы рг, Pi при ко на основе соотношений (1.5). Таким образом, если кодовое слово - {Q2Q1 Р2 Pi) не искажено помехами, то выполняются тождества;

йггбг - iGi + Р2 =0; -262 biQi + pi =0.

(1.11)

Эти тождества можно трактовать как т проверочных условий; они

могут быть найдены из скалярного произведения слова v = (Q2 G1P2 Pi) на матрицу

аг -fli I 1 О Ь. -bi0 1

(1-12)

Матрицу Н (1Л2) принято называть проверочной или контрольной. Сравнивая (1.11) и (1.12), можно заключить, что проверочная матрица представима в виде

Я= [-Л \е\ или я - \ -Л], (1.13)

где t - символ транспонирования. Формы (1.7) и (1.13) будем называть систематическими.

Из строения матриц G (1.7) и Я (1.12) видно, что

GH =-HG =0.

Скалярное произведение кодового вектора v на проверочную матрицу Н называют вектором-синдромом и обозначают S - (Бщ, 5" ,..., 5i),T.e.5 =vЯ

Ясно, что при отсутствии помех имеем нулевой синдром: 5" = О и 5"! ~ 5*2 = • . = - 0. Предположим теперь, что помехой е искажен какой-либо информационный символ, например Qi. Вследствие линейности кода, а также аддитивности помехи с учетом первого тождества (1.11) можно составить следующие выражения:

2 2 (Qi +е) +aiGl ~ Р2 = 2;

1 = 2 (62+е)- Pi - 2.

Таким образом, 52/2 - \\Ьг или S2/S1 = 2/2- Аналогично при аддитивном искажении символа Qi получили бы Si/ai = е = Si/bi

или S2/S1 = йу/Ъу.

По условию (1.10) 2/1 b2Jby или, что то же самое,2/2 Фс\1Ъ\. Следовательно, линейная независимость к ~ т - 2 столбцов (строк) матриц А, G и Н позволяет при декодировании определить, какой из информационных символов искажен помехой: при Si/Sy = 2/2 это символ Q2, а при S2/Sy = ay/b - символ Qy. Вычитая величину е из соответствующего символа Q (и отбрасывая проверочные символы), восстанавливаем исходное сообщение. Если же ошибочен какой-либо проверочный символ, например р2, то соответствующая ему компонента синдрома отлична от нуля, зато другая - равна нулю. Б этом случае информационные символы считаются достоверными. Проведенные рассуждения справед}швы при любом числе к информационных символов.