8.1.2. Некоторые известные линейные блоковые коды

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

Коды Хемминга. Сюда относятся как двоичные, так и недвоичные коды Хемминга. Мы ограничим обсуждение свойствами двоичных кодов Хемминга. Они включают класс кодов со свойствами

(п,к)(2"-\,2"-\-т), (8.1.16)

где т - некоторое положительное целое число. Например, если т - 3, мы имеем код (7, 4). Проверочная матрица Н кода Хемминга имеет особое свойство, которое позволяет нам существенно облегчить описание кода. Напомним, что проверочная матрица («, к) кода

имеет п-к строк и п столбцов. Для двоичного (w, к) кода Хемминга п-2-1 столбцов состоят из всех возможных двоичных векторов с п-к =т элементами, исключая вектор со всеми нулевыми элементами. Для примера, код (7, 4), рассмотренный в примерах 8.1.1 и 8.1.2, является кодом Хемминга. Его проверочная матрица состоит из семи вектор-столбцов(001), (010), (011), (100), (101), (110), (111).

Если необходимо генерировать систематический код Хемминга, то проверочная матрица Н может легко приводиться к систематической форме (8.1.11). Затем соответствующую порождающую матрицу G можно получить из (8.1.11).

Заметим, что любые два столбца матрицы Н не являются линейно зависимыми, так как иначе эти два столбца были бы идентичными. Однако при т > 1 возможно найти три столбца из Н, которые при сложении дают нуль. Следовательно, для (и, к) кода Хемминга d- = 3.

Путём прибавления ко всем кодовым комбинациям (и, к) кода Хемминга одного проверочного символа получаем расширенный код Хемминга (п+1,к) с d„=4. С другой стороны, (п, к) код Хемминга можно укоротить до (п-/, к-Г) путём удаления / строк порождающей матрицы G и, соответственно, удаления / столбцов в проверочной матрице Н. Распределение весов для класса кодов Хемминга ( , к) известно и выражается в компактной форме посредством следующего весового полинома:

4z)Z4, =-4 (l + -r+"{1 + )"-1--Г" , (8.1.17)

,=0 -rlL J

где А, - число кодовых слов с весом /.

Коды Адамара. Код Адамара получается путём выбора в качестве кодового слова столбцов матрицы Адамара. Матрица Адамара М„-это пхп матрица (н-чётное целое) из единиц и нулей с тем свойством, что один столбец отличается от другого столбца ровно в hi позициях. Один столбец матрицы содержит одни нули. Остальные строки имеют i« нулей и 2 единиц.

Для п = 2 матрица Адамара имеет вид

О о" о I

(8.1.18)

Иногда элементы матрицы Адамара обозначаются -i-l и -1. Тогда строки матрицы Адамара в;пимно ортогональны. Таклсе заметим, что Л/=2* сигналов, полученных из .тдамаровских кодовых слов щтём отображения кгшдого бита кодового слова в двоичный ФМ сигнал, взаимно ортогональны.

Затем из матрицы Адамара М„ можно генерировать матрицу Адамара М согласно соотношению

м. м.

м. м.

(8.1.19)

где М„ означает дополнение матрицы М„ (нули заменятся единицами и наоборот). Так, подставив (8.1.18) в (8.1.19), получим

(8.1.20)

Дополнение к равно

(8.1.21)

Теперь строки из и формируют линейный двоичный код с длиной блока W = 4, имеющий 2и = 8 кодовых слов. Минимальное расстояние кода =hi = 2. Путём повторного применения (8.1.19) мы можем генерировать код Адамара с длиной п = 2".

Л = log2 2« = logj 2" =т+1 и d = 2n-2" , где w - положительное целое число. В

дополнение к важному частному случаю, когда и = 2"*, возможны коды Адамара с другой длиной блока, но эти коды нелинейные.

Код Голея. Код Голея - это двоичный линейный код (23, 12) с J,„ -7. Расширенный двоичный линейный код Голея (24, 12) с „,,„=8 получается из кода Голея путём добавления ко всем кодовым комбинациям проверочного символа. Таблица (8.1.1)-показывает распределение весов кодовых слов кода Голея (23, 12) и расширенного кода Голея (24, 12). Мы обсудим процедуру синтеза кода Голея в разделе 8.1.3.

Таблица 8.1.1. Распределение весов кода Голея (23, 12) и расширенного кода Голея (24, 12)

Число кодовых слов

Источник: Peterson и Weldon (1972)

8.1.3. Циклические коды

Циклические коды - подкласс класса линейных кодов, которые удовлетворяют следующим циклическим свойствам: если С = с„ 2 ...с, Сд] - кодовое слово циклического кода, тогда [с„ 2 с„ 3 ...с полученное циклическим сдвигом элементов кода С, также являются кодовым словом. Все циклические сдвиги С образуют кодовые слова. Как следствие циклического свойства, эти коды обладают значительным количеством структурных удобств, которые можно .использовать при реализации операций кодирования и декодирования. Большое количество алгоритмов эффективных кодеров и декодеров жёстких решений были сделаны посредством циклических кодов, что сделало возможным в практических системах связи строить блоковые коды большой длины с большим количеством кодовых слов. Описание специфических алгоритмов находится вне кругозора этой книги. Наша основная цель - вкратце описать некоторые характеристик циклических кодов.

При работе с циклическими кодами принято связывать с кодовьпл словом С= с„ , с„ 2 ...с, Сд полином С{р) степени <«-1, определённый так

Ф) = с-.Р" + сгР"" + +с,р + с,. (8.1.22)

Для двоичного кода каждый из коэффициентов полинома является или нулем, или единицей.

Теперь предположим, мы формируем полином

рС{р) = с„ у + сР" + +ср. Этот полином не может представить кодовое слово, так как его степень может быть равна п (если =: 1). Однако если мы разделим рС{р) на р" + \,мы получим

-с (8 123

p" + l--p"+V

С, W = с„ ,р"- + с„ ,р"~ +.. .+с,р + .

Заметим, что полином C{p) представляет кодовое слово С, = , с, 3 ...с с„ , , которое как раз образовано из кодового слова С циклическим сдвигом на одну позицию. Поскольку С,(р) представляет собой остаток, полученный делением рС{р) на р"+\, мы говорим, что

С, (р) = рС(р) mod(p +1). (8.1.24)

Аналогичным образом, если С(р) представляет кодовое слово в циклическом коде,

тогда рС{р) mod(/j"+l) также является кодовым словом циклического кода. Так что можно написать

рС(р) = Q(ptp" +1) + С,(р), (8.1.25)

где остаточный полином C,{pj представляет кодовое слово циклического кода, а 0{р) -частное.

Мы можем генерировать циклический {п,к) код, используя порождающий полином g[p) степени п-к с двоичными коэффициентами, который является множителем при факторизации полинома р" + 1. Порождающий полином в общем виде можно записать так

sip) = Р"- + g„-,-P" + +1 • (8.1.26)