Главная > Помехоустойчивое кодирование > Кодирование информации (двоичные коды)
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

3.18. Коды Плоткина

Коды Плоткина по эффективности достигают теоретической границы Плоткина (см, § 3.1). Получают их из матриц Адамара. Матрицей Адамара называется ортогональная матрица размерности элементами которой являются действительные числа +1 и —1, например:

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

Известна следующая теорема [93]: если существует матрица Адамара размерности то существует двоичный код из символов, образованный векторами, с минимальным кодовым расстоянием

С помощью матриц Адамара могут быть построены коды с большим кодовым расстоянием:

Кодовые векторы образуются строками матрицы Адамара при замене — 1 на 0, а затем строками, получаемыми заменой всех единиц нулями, а нулей — единицами. Например, для матрицы

имеем восемь кодовых векторов (комбинаций):

Построим для этих комбинаций матрицу кодовых расстояний:

(см. скан)

Из матрицы видно, что кодовое расстояние для кода, образованного из матрицы действительно не менее двух, т. е. соблюдается условие (3.59).

Известна теорема: если -матрица Адамара имеет размер то матрица является матрицей Адамара размерности

Многократно применяя эту теорему, можно построить матрицу Адамара размерности для любого целого положительного Соответствующий ей код совпадает с кодом Рида — Маллера первого порядка и с кодом Макдональда.

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

Существует несколько методов построения матриц Адамара. Матрицы Адамара можно построить следующих порядков [131]:

(см. скан)

Здесь нечетное простое число.

Перечисленные выражения дают возможность строить матрицы Адамара размерности для всех кратных четырем и не превосходящих 200, за исключением 184 и 188.

В [65] приведена таблица натуральных чисел для которых существуют матрицы Адамара размерности (до Такие числа принято называть правильными числами.

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

Пример. Построить код Плоткина для Трижды применив приведенную теорему, строим матрицу Адамара из матрицы Адамара

(см. скан)

Заменив в строках матрицы Адамара Ни — 1 на 0, получим первые 16 векторов кода, а затем, заменив во всех строках единицы нулями, а нули единицами, — вторые 16 векторов. Таким образом, имеем 32 кодовые комбинации:

(см. скан)

(см. скан)

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