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

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

Гораздо меньшего объема памяти требует матричное кодирование. Пусть \[ E \] матрица размерности \[ m\times n \] , состоящая из элементов \[ e_{ij} \] , где \[ i \] - это номер строки, а \[ j \] - номер столбца. Каждый из элементов матрицы \[ e_{ij} \] может быть либо 0, либо 1. Кодирование реализуется операцией \[ b=aE \] или \[ b_j=a_1e_{1j}+a_2e_{2j}+\cdots+a_me_{mj} \] , где кодовые слова рассматриваются как векторы, т.е как матрицы-строки размера \[ 1\times n \] .

Пример. Рассмотрим следующую \[ 3\times6 \] -матрицу: \[ E=\left\lbrack\matrix{1&0&0&1&1&0\cr 0&1&0&0&1&1\cr 0&0&1&1&1&1\cr}\right\rbrack. \] Тогда кодирование задается такими отображениями: \[ 000\rightarrow000000 \] , \[ 001\rightarrow001111 \] , \[ 010\rightarrow010011 \] , \[ 011\rightarrow011100 \] , \[ 100\rightarrow100110 \] , \[ 101\rightarrow101001 \] , \[ 110\rightarrow110101 \] , \[ 111\rightarrow111010 \] .

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

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

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

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