Построение линейного систематического кода

Решение

.

Таблица 4.4 – Троичный код Хаффмена для 7-и сообщений

Буква	Вероятность	Дерево	Код
В А Б Г Д Е Ж	0,38 0,24 0,18 0,1 0,06 0,02 0,02		f1 f2 f3f1 f3f2 f3f3f1 f3f3f2 f3f3f3

Полученный код легко декодируется, так как ни один код не начинается с f₁ и f₂, кроме одного одноразрядного кода

Для этого используется образующая матрица P_n,k, состящая из двух матриц U_k – информационной, квадратной k´k, и H_ρ – проверочной, k´ρ:

P_n,k =

U _k H _ρ

Рисунок 4.2 – Производящая матрица

Для построения производящей матрицы удобно U _k брать в виде квадратной единичной:

U _k =

Рисунок 4.3 – Информационная матрица

Тогда матрица P_n,k в канонической форме:

P_n,k =

Рисунок 4.4 – Проверочная матрица

При этом проверочная матрица H _ρ строится так:

· количество единиц в строке должно быть ≥ (d _min - 1);

· Å двух любых строк должна содержать ≥ (d _min - 2) единиц.

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

Для каждой кодовой комбинации нужно составить ρ независимых сумм по mod 2.

Для этого удобно использовать проверочную матрицу Н. Сначала строят подматрицу Н’ – транспонированную матрицу H _ρ:

Н’ =

Рисунок 4.5 – Транспонированная матрица Н’

Затем справа приписывается единичная матрица:

Н =

Рисунок 4.6 – Матрица Н

Проверочные символы по матрице Н находятся так:

· позиции, занимаемые единицами в первой строке подматрицы Н’, определяют информационные разряды, участвующие в формировании первого проверочного разряда кодовой комбинации;

· позиции, занимаемые единицами во второй строке подматрицы Н’, определяют информационные разряды, участвующие в формировании первого проверочного разряда кодовой комбинации и т.д….

Пример: построить линейный систематический код для информационной комбинации 0011 (k = 4) по производящей матрице Р_7,4:

P_7,4 =

Рисунок 4.7 – Образующая матрица Р_7,4

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

Н₃ =

Рисунок 4.8 – Проверочная матрица Н₃

Тогда транспонированная матрица:

Н’ =

Рисунок 4.9 – Транспонированная матрица Н’

Приписываем справа единичную матрицу:

a₁ a₂ a₃ a₄ b₁ b₂ b₃

Н =

Рисунок 4.10 – Матрица Н

Кодовая комбинация должна содержать ρ проверочных символов:

ρ = n – k = 7 – 4 = 3.

Нужно найти три проверочных символа: b₁, b₂, b₃.

Из подматрицы Н’ определяем:

b₁ = a₂ Å a₃ Å a₄

b₂ = a₁ Å a₃ Å a₄

b₃ = a₁ Å a₂ Å a₄

Тогда для нашего сообщения 0011 проверочные символы будут:

b₁ = 0 Å 1 Å 1 = 0

b₂ = 0 Å 1 Å 1 = 0

b₃ = 0 Å 0 Å 1 = 1

a₁ a₂ a₃ a₄ b₁ b₂ b₃

Полная кодовая комбинация будет: 0 0 1 1 0 0 1.

Дата добавления: 2015-08-31