Теория информации


Матричное кодирование


Ранее каждая схема кодирования описывалась таблицами, задающими кодовое слово длины для каждого исходного слова длины . Для блоков большой длины этот способ требует большого объема памяти и поэтому непрактичен. Например, для -кода потребуется

бит.

Гораздо меньшего объема памяти требует матричное кодирование. Пусть матрица размерности , состоящая из элементов , где - это номер строки, а - номер столбца. Каждый из элементов матрицы может быть либо 0, либо 1. Кодирование реализуется операцией или , где кодовые слова рассматриваются как векторы, т.е как матрицы-строки размера .

Пример. Рассмотрим следующую -матрицу:

Тогда кодирование задается такими отображениями: , , , , , , , .

Рассмотренный пример показывает преимущества матричного кодирования: достаточно запомнить кодовых слов вместо слов. Это общий факт.

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

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

Матричные коды называют также линейными кодами. Для линейных -кодов с минимальным расстоянием Хэмминга существует нижняя граница Плоткина (Plotkin)3) для минимального количества контрольных разрядов при ,

Упражнение 39

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

  1)

  20

  2)

  20

  3)

  14

© 2003-2007 INTUIT.ru. Все права защищены.




Начало  Назад