Читать в оригинале

<< ПредыдущаяОглавлениеСледующая >>


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

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

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

,                    (8.1.16)

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

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

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

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

,                    (8.1.17)

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

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

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

.                    (8.1.18)

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

,                     (8.1.19)

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

.                     (8.1.20)

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

.                    (8.1.21)

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

Код Голея. Код Голея – это двоичный линейный код  с . Расширенный двоичный линейный код Голея  с  получается из кода Голея путём добавления ко всем кодовым комбинациям проверочного символа. Таблица (8.1.1) показывает распределение весов кодовых слов кода Голея  и расширенного кода Голея . Мы обсудим процедуру синтеза кода Голея в разделе 8.1.3.

Таблица 8.1.1. Распределение весов кода Голея  и расширенного кода Голея

Вес

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

код (23,12)

код (24,12)

0

1

1

7

253

0

8

506

759

11

1288

0

12

1288

2576

15

506

0

16

253

759

23

1

0

24

0

1

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

 



<< ПредыдущаяОглавлениеСледующая >>