Систематические коды

Как уже отмечалось, в настоящее время наиболее широкий класс корректирующих кодов составляют систематические коды. Эти коды относятся к группе разделимых блочных кодов, в которых из n символов, образующих кодовую комбинацию, k символов являются информационными, а остальные n - k - избыточными, предназначенными для проверки. Проверочные символы во всех комбинациях занимают одни и те же позиции.

Все разрешенные кодовые комбинации систематического (n, k) - кода можно получить, располагая k исходными разрешенными кодовыми комбинациями. Исходные кодовые комбинации должны удовлетворять следующим условиям:

1. В число исходных комбинаций не должна входить нулевая.

2. Кодовое расстояние между любыми парами исходных комбинаций не должно быть меньше d _min.

3. Каждая исходная комбинация, как и любая ненулевая разрешенная комбинация, должна содержать количество единиц не менее d _min.

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

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

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

Производящую матрицу образуют путем приписывания справа к единичной квадратной матрице J размера k (информационной матрице) дополнительной матрицы D, содержащей n - k столбцов и k строк, например:

Требования к дополнительной матрице:

1. Количество единиц в строке должно быть не менее d –1 (одна 1 содержится в строке единичной матрицы).

2. Сумма по mod2 двух любых строк должна содержать не менее d –2 единиц(2 единицы содержатся в сумме по mod2 двух строк единичной матрицы).

Проверочные символы образуются за счет линейных операций над информационными символами. Удобно проверочные уравнения составлять с помощью проверочной матрицы Н, которая строится следующим образом:

1. Строится подматрица, являющаяся транспонированной по отношению к дополнительной матрице:

1. Справа к ней приписывается единичная квадратная матрица размера n - k:

Единицы в каждой строке проверочной матрицы соответствуют символам кода (), сумма которых по mod2 должна быть равна 0.

Рассмотрим пример построения кода, исправляющего одиночные ошибки t =1 и имеющего n =7. Определяем кодовое расстояние d =2 t +1=3. Полное число одиночных ошибок равно 7, т.е. Е ₁ = n. Число проверочных символов r вычислим по формуле:

n - k .

Откуда следует и соответственно, число информационных символов k =4.

Строим производящую матрицу, содержащую k - строк, n - k - столбцов. Вид производящей матрицы зависит от вида дополнительной матрицы D.

и т.д.

Возьмем, например, дополнительную матрицу D , тогда производящая матрица А _{7, 4} будет иметь следующий вид:

Определяя суммы по mod2 всех возможных сочетаний строк производящей матрицы, получим 2 ^k -1 ненулевых комбинаций систематического кода, используемых для передачи кодированных информационных сообщений:

1 2=1100110

1 3=1010101

……………….

1 2 3 4=1111111.

Всего имеем таким образом 15 комбинаций.

По производящей матрице строим проверочную матрицу:

Строки дополнительной матрицы являются столбцами транспонированной матрицы .

Из Н получаем следующие уравнения проверки для 1, 2 и 3-ей строк:

r 1= a 2 a 3 a 4 a 5=0, r 2= a 1 a 3 a 4 a 6=0, r 3= a 1 a 2 a 4 a 7=0.

Анализ этих уравнений показывает, что:

элемент а ₁ входит в уравнение 2 и 3;

элемент а ₂ входит в уравнение 1 и 3;

элемент а ₃ входит в уравнение 1 и 2;

элемент а ₄ входит в уравнение 1, 2, 3

и т.д.

Следовательно, искажение одного из элементов а_i нарушает вполне определенные уравнения, по которым можно определить и восстановить искаженный элемент.

Составим таблицу 1 восстановления искаженных символов.

Таблица 1

Соответствие номеров искаженных символов уравнениям проверок

Если r _i = 0, то уравнение не нарушено и искаженных символов нет, если r_i = 1, уравнение нарушено и имеется искаженный символ.

Значения проверочных символов получаем из уравнений проверок для строк:

из r ₁ получим a ₅= a ₂ a ₃ a ₄,

из r ₂ получим a ₆= a ₁ a ₃ a ₄,

из r ₃ получим a ₇= a ₁ a ₂ a ₄.

Пусть источник выдает сообщение в виде кода 1011, которому соответствуют символы (а ₁– а ₄), кодирующее устройство добавляет символы a ₅ =0, a ₆ =1 и a ₇=0. В результате формируется кодовая комбинация 1011010 (а ₁– а ₇), которая передается по каналу. Если на приемной стороне получили искаженную комбинацию 1010010, то решение уравнений проверок:

r ₁= a ₂ a ₃ a ₄ a ₅=1

r ₂= a ₁ a ₃ a ₄ a ₆=1

r ₃= a ₁ a ₂ a ₄ a ₇=1

покажет, что исказился элемент а ₄, т.к. он входит во все уравнения проверок.

Кодовая комбинация вида R_j = r ₁, r ₂, …, r_{n - k} называется контрольной последовательностью, опознавателем или синдромом ошибки.