30. Систематический код. Производящая и проверочная матрица. Уравнения проверки. Опознаватель. Исправляющий вектор.

Систематический код – это групповой m-значный код в котором к символов является информацией, а n-k являются проверочными, избыточными. Они занимают одни и те же позиции. Задание СК производится с помощью производящей матрицы А и проверочной матрицы Н. Производящая матрица позволяет получить все комбинации кодов суммированных по модулю 2.

(n-k) разрядные кодовые комбинации в которых количество единиц не менее чем dmin-1, а сумма любых двух строк по модулю 2 должна содержать «единицу» не менее чем dmin-2. Желательно при этом, чтобы единицы донижались до нуля, чтобы серии единиц были короткие. 2^к – число кодовых комбинации.

Структура производящей матрицы позволяет строить систематический код, у которого первые к-позиции будут пропорциональными, а оставшиеся n-k проверочные, при этом общее число разрешенных кодовых комбинаций равно 2^к и все различные кодовые комбинации могут быть получены в результате линейной операции суммы по |2| любых двух, трех строк производящей матрицы.

Построение проверочной матрицы:

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

,

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

Процесс приема-передачи с корректировкой ошибок:

Формируется информационная часть кодовой комбинации. На основе ее строится проверочная часть с помощью проверочных уравнений. На приемной стороне полученные разряды ставятся в проверочные уравнения, если кодовая комбинация передана без ошибки, то все проверочные уравнения примут значении равное нулю. Если какие либо уравнения примут не нулевое значение, тогда формируют опознаватель для обнаружения и исправления ошибок.

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

31. Код Хэмминга. Уравнения проверки. Уравнения кодирования (определение проверочных разрядов).

Это такой систематически код, у которого опознаватель показывает номер ошибочного разряда. Он служит для поиска однократной ошибки.

Необходимо чтобы каждое проверочное уравнение проверяло цифру с весом какого-либо разряда, т.е. при первой проверки получалась цифра с весом младшего разряда, т.е. 2⁰, при 2-ой проверки цифра с весом 1-го разряда 2¹ и т.д.

2⁰,2¹,…,2ⁿ⁺¹ тогда сумма всех проверок даст номер ошибочного разряда.

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

n=7, log₂7>3=4

Необходимо взять 7 комбинация 4-ехразрядного двоичного кода.

1| 0001 , 2| 0010 , 3| 0011, 4| 0100, 5| 0101, 6| 0110

7| 0111

Проверочные уравнения: первое проверочное уравнение формируется из тех, где в номере между разрядов имеется единица.

r1=a1 a3 a5 a7, r2=a2 a3 a6 a7, r3=a4 a5 a6 a7

Проверочные разряды размещаются внутри кодовых комбинаций на местах соответствующих их номеру. Позиции проверочных разрядов в кодовом слове. Выделяются те разряды, которые появляются одновременно по всей системе проверочных уравнений. Это а1, а2, а4.

а1 а2 а3 а4 а5 а6 а7

Из проверочных уравнений, находи а:

а1=a3 a5 a7

а2=a3 a6 a7

а4=a5 a6 a7

Пусть имеется информационная последовательность:

а3 а5 а6 а7

1 1 0 0

а1=1 1 0=0

а2=1 0 0=1

а4=1 0 0=1

01 11100 – А передающая сторона.

Внесем ошибку в информационную часть:

01 11110

r1=0 1 1 0=0

r2=1 1 0 1

r3=1 1 1 0

r3 r2 r1 – номер ошибочного разряда.

1 1 0

Недостатки помехоустойчивого кода:

1. Трудности реализации, сложность предсказания кратности ошибок в ракельном канале связи.

2. Возникновения ошибок декодирования при кратности ошибок больше заданного.

3. Используется пакетная передача информации, и искажения каналов связи вносится на весь пакет в целом. Для быстрого декодирования необходимо рассматривать не отдельные кодовые слова, а пакет в целом.