Если принятое слово R = [101000101], то синдром равен] S = [1100]. Так как s равен пятому столбцу матрицы сШ, то заклю-> чаем, что

Е = [000010000] С = [101010101].

Если же принятым словом является R = [111001111], то s ==1 = [1101]. Так как s не совпадает ни с одним из столбцов матрицы SS, то происходит отказ от декодирования, обнаруживающий две или; более ошибок в канале.

Зададимся теперь вопросом о наибольшей возможной блоковой длине кода, исправляющего одиночные ошибки и имеющего не более г проверочных позиций. Так как число проверочных позиций равно числу линейно независимых ) строк матрицы S£, то этот вопрос равносилен вопросу о максимальном числе различных ненулевых столбцов двоичной матрицы, содержащей не более г строк. Ответ очевиден: 2 - 1. Столбцы матрицы Se совпадают с 2"-1 ненулевыми двоичными г-мерными векторами, упорядоченными произвольным образом. Линейный код, определяемый такой матрицей, называется кодом Хэмминга.

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

Для выявления конфигураций ошибок веса 2 к коду Хэмминга иногда добавляется еще одна общая проверка на четность. Результирующий код имеет блоковую длину п = 2" и содержит г = пг + 1 проверочных иА; = 2" - 1 - т информационных символов. Например, код Хэмминга с блоковой длиной 15 описывается проверочной матрицей

гО О О О О О О 1 1 1 1 1 1 1 1п 000111100001111 011001100110011 Ll 0101010101010 1,

1) Векторы а, р, . . ., у называются линейно независимыми, если равенство аа + Ьр + . . . -Ь CY = О возможно только при а = b = . . . = с = О,-Прим. перев.

Присоединяя общую проверку на четность, получаем расширенный код Хэмминга с блоковой длиной 16, проверочная матрица которого имеет вид

г1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1п 000000001111111 1-0000111100001111 0011001100110011 .0 101010101010101. В первой строке проверочной матрицы расширенного кода Хэмминга стоят одни единицы, так что первая координата суммы любых двух столбцов всегда равна нулю. Поэтому синдром любого вектора ошибок веса 2 отличен от нуля и любого столбца матрицы SS- Любая конфигурация двух ошибок в канале должна привести к отказу от декодирования. Таким образом, расширенный код Хэмминга исправляет все одиночные ошибки и обнаруживает все двойные ошибки.

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

Код Хэмминга с блоковой длиной п = 2™-1 обеспечивает скорость передачи, равную

р к 2"»-1 -m . т

ге ~" 2»-1 ~~ 2» -1 Можно строить коды Хэмминга все с большей и большей длиной; достаточно длинные коды обеспечивают скорость, близкую к 1.

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

Простота кодов Хэмминга резко контрастирует с относительной сложностью наиболее простых известных двоичных кодов, исправляющих двойные ошибки. Вслед за первой работой Хэмминга [1950] появилось большое число работ по конструктивной теории кодирования. Было предложено много новых кодов. Однако, за исключением нескольких важных случаев, предлагаемые конструкции носили узко специальный характер. Нерешенной оставалась даже следующая простейшая задача - построение двоичных кодов с приемлемой скоростью передачи, позволяющих исправлять любые двойные ошибки. Когда же, наконец, Боуз и Чоудхури в 1959 г. и Хоквингем в 1960 г. построили такие коды, то сразу же было предложено и их обобщение - коды с исправлением t ошибок для любого натурального t.

На самом деле интервал между открытием кодов Хэмминга в 1950 г. и БЧХ-кодов в 1960 г. составляет даже больше, чем десятилетие научных исследований, поскольку большинство результатов Хэмминга было опубликовано в несколько ином контексте еще в 1942 г. в работе Фишера, хорошо известной Боузу!

Как бы то ни было, столь существенный интервал между открытием кодов Хэмминга и БЧХ-кодов с исправлением двойных ошибок является весьма примечательным. Поэтому мы рекомендуем начинающему читателю с особой тщательностью изучить следующий раздел, который, по нашему мнению, является весьма важным.

1.4. Конструктивное введение в теорию БЧХ-кодов, исправляющих двойные ошибки

Мы видели, что линейный код характеризуется своей проверочной матрицей S£. Ранее было показано, что синдром принятого слова равен сумме столбцов матрицы SS, соответствующих искаженным позициям переданного вектора. Следовательно, линейный код позволяет исправлять все одиночные ошибки тогда и только тогда, когда все столбцы матрицы S6 различны и отличны от нуля. Если SS имеет т строк и позволяет исправлять все одиночные ошибки, то ге 2™-1. Коды Хэмминга достигают этой границы.

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

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

и что столбцы матрицы S6 занумерованы так, что i-u столбец дает двоичное представление числа i. Предположим теперь, что требуется исправлять все конфигурации из двух или меньшего числа ошибок. Очевидно, что для этого нужна большая избыточность, так что матрица SS должна иметь больше строк. На первый взгляд, естественно предположить, что для исправления двух ошибок требуется вдвое большее число проверок, чем для исправления одной, и поэтому мы будем искать проверочную матрицу S£ из 2™-1 столбцов и 2"" строк.

Разумно выбирать столбцы матрицы SB по возможности различными. Выберем в качестве первых т строк проверочную матрицу

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

кода Хэмминга. (Почему бы и нет? Мы действуем в духе Хэмминга.) Например, при m = 5 и ге = 31 хотелось бы получить исправляющий двойные ошибки код с матрицей

(1.41) SB

/i(l) /i(2) /i(3)

/2(1) /2(2) /2(3)

/з(1) /з(2) /з(3)

/4(1) /4(2) /4(3)

L/5(l) /5(2) /5(3)

На этом пути нам надо отыскать функцию / (), отображающую 5-мерные векторы в 5-мерные векторы.

Последние пять строк матрицы будут задавать код Хэмминга тогда и только тогда, когда функция / является перестановкой. Эвристически такая возможность кажется обнадеживающей. Если первые т строк и последние т строк в отдельности позволяют исправлять одиночные ошибки, то возможно, что совместно они позволят исправлять двойные ошибки.

Для исследования возможных выборов функции / нам необходимо разработать некоторый аппарат для операций над двоичными 5-мерными векторами. Мы должны уметь в каком-то смысле складывать, вычитать, умножать и делить 5-мерные векторы. Для этого удобно интерпретировать каждый двоичный 5-мерный вектор как некоторый двоичный многочлен степени 4. Например,

0 0 0 0 0-О О О О Ь 0 0 0 1 0-0 10 11-110 11-

а;"

х* + х

О, 1,

+ Х + 1,

+ x + i.

Как мы и хотели, сложение двух таких двоичных многочленов соответствует сложению векторов. Однако умножение в общем случае приводит к многочленам степени, большей 4. Например,

{а + X + i) {х + 3 + X + i) = = ж + + + Зж* + 2х + + 2х + i = = х + х + х + X* + х + i.

так как при двоичном сложении 2 = О и 3 = 1. Поэтому нам необходим некоторый метод понижения степеней > 4 до степеней 4. Одним известным методом такой редукции является построение вычетов по модулю двоичного многочлена М (х) степени 5; а именно -переход от многочленов к их остаткам отделения на М (х). Например, пусть

М (х) = + а: + 1.

Тогда (двоичное) деление дает

х + х + х + х* ~\-х

+ 1 \х-\-х-{-1

+ х*

+ x-\-i

х+х х

х" +х +1

так что ж + а;" -или

з?-\-х + х

+ а;* + а;2 + 1 = (а: + а; + 1) {з + х" + \) + х + х\х.

+ + ж» + ж* + + 1 = =(аг + ж + ж) mod (х + х + 1).

Символ = читается «сравнимо с». В общем случае говорят, что

Л (х) = а (х) mod М (х)

тогда и только тогда, когда существует такой многочлен с(х), что,

Л (х) = с (х) М (х) + а(х).

Напомним, что операции умножения и сложения многочленов выполняются по модулю два. Некоторые авторы отмечают этот факт, используя запись Л (х) = а (х) mod (2, М (х)). Заметим, что редукции по модулю 2 и по модулю М (х) перестановочны. Следующие свойства показывают, насколько плодотворно понятие сравнения многочленов.

1.42. Свойства сравнений. Если

а(х) = А (х) mod М (х)

Ъ{х)В (х) mod М (х),

а(х)±.Ь (х) = Л (х) ± В (х) mod М (х)

а (х) Ъ{х)А (х) В (х) mod М (х).

Доказательства.

а{х) = с (х) М {х) \- А (х), Ъ{х)=а (X) М{х)+В (х), а{х)±Ъ (х) = [с (х) ± d (х)] М {х) +А (х) ± В (х), а (х) Ъ (х) = [с (х) d (х) М (х) + с (х) В (х) + + d (х) Л (х)] М {х) + А (х) 5 (х). .

Более того, если степени многочленов а {х) тз. А (х) меньше степени М (х), то из формулы а (х) = Л (х) mod М-(х) следует, что а (х) = Л (х). [Доказательство: а (х) - Л (х) = с (х) М (х), и если с (х) =#=0, то степень правой части больше степени левой.]

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

какие-нибудь классы вычетов? Нет, как вытекает из следующего алгоритма.

1.43. Алгоритм деления.

Для чисел 1)

Для данных а и М 3 однозначно определенные числа q и А, такие, что

адМ + А, 0<Л<М

Для многочленов с коэффициентами из некоторого данного поля 2)

Для данных а(х) и М (х) 3 однозначна определенные многочлены д(х) а А (х), такие, что

а(х) = д{х)М{х) + А{х), deg А (х) < deg М (х)

Рассмотрев сложение, вычитание и умножение по модулю М (х), естественно исследовать возможность деления. Ответ на этот вопрос дает алгоритм Евклида.

1.44. Алгоритм Евклида.

Для чисел

Для заданных а и b 3 такие числа А а В, что

aA-i-bB = {a, b),

где (а, Ь)-наиболыпий общий делитель а и Ь.

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

Для заданных а{х) я b (х) 3 такие многочлены А(х) а В {х), что

а (х) А{х)-Ь [х) В (х) = (а (X), Ъ (х)),

где (а (х), 6 (ж))-нормированный 3) общий делитель а(х) и b (х) наибольшей степени.

) Символ 3 означает «существует».

) Полем называется содержащее О и 1 множество элементов, в котором определены операции сложения, вычитания, умножения и деления, удовлетворяющие обычным правилам арифметики. Более детально поля изучаются в гл. 4.

Нормированным называется многочлен с коэффициентом 1 при старшем члене.- Прим. перев.