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

Ранее каждая схема кодирования описывалась таблицами, задающими кодовое слово длины n для каждого исходного слова длины m. Для блоков большой длины этот способ требует большого объема памяти и поэтому непрактичен. Например, для (16, 33)-кода потребуется 33 * 2¹⁶ = 2 162 688 бит.

Гораздо меньшего объема памяти требует матричное кодирование. Пусть E матрица размерности m × n, состоящая из элементов e_ij, где i — это номер строки, а j — номер столбца. Каждый из элементов матрицы e_ij может быть либо 0, либо 1. Кодирование реализуется операцией b = аЕ или где кодовые слова рассматриваются как векторы, т.е как матрицы-строки
размера 1 × n.

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

Тогда кодирование задается такими отображениями: 000 → 000000, 001 → 001111, 010 → 010011, 011 → 011100, 100 → 100110, 101 → 101001, 110 → 110101, 111 → 111010.

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

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

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

Дата добавления: 2014-01-04