Линейные блоковые коды

Линейным блоковым (n, k) кодом называется множество последовательностей длины над полем Галуа , называемых кодовыми словами. Это поле характеризуется тем, что сумма двух кодовых слов является кодовым словом и произведение любого кодового слова на элемент поля – также кодовое слово.

Если , то линейный код называется групповым, так как кодовые слова образуют математическую структуру, называемую группой. При формировании данного кода линейной операцией является сумма по модулю два ().

Далее рассмотрим один из способов задания линейных блоковых кодов – матричный, который основан на проверке ортогональности кодовых векторов проверочной матрице.

§ Порождающая матрица: , где – единичная матрица, – матрица, составленная из проверочных символов.

§ Проверочная матрица: .

§

Основные свойства линейных кодов:

1. Если – это кодовое слово, то: .

2. Произведение некоторого кодового слова с ошибкой на даст синдром : .

3. .

4. Кодовое расстояние -кода равно минимальному числу линейно зависимых столбцов .

5. Произведение информационного слова на даст кодовое слово.

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

7. Кодовое расстояние любого линейного -кода удовлетворяет неравенству (граница Сингтона). Если выполняется строгое равенство, то данный код называется кодом с максимальным расстоянием.

8. Граница Плоткина для минимального количества контрольных разрядов: при .

 

Пример

Дана следующая порождающая матрица: .

Тогда кодирование задается отображениями: 000→00000, 001→00110, 010→01011, 011→01101, 100→10001, 101→10111, 110→11010, 111→11100.

Например:

Проверочная матрица: .

 

Проверим свойство 1: .

 

Проверим свойство 4: линейно зависимые столбцы в – это 1-ый и 5-ый (например). Значит, . Посмотрим на (*): видим, что минимальное кодовое расстояние кода действительно равно 2.

 

Свойство 7 (граница Сингтона): .●