Корреляционный код. Кодирующие и декодирующие устройства

 

Корреляционный код является блочным систематическим кодом

(2k, k)-код, в комбинациях которого имеется взаимная связь (корреляция) между символами: каждая единица комбинации исходного кода преобразуется в единицу и нуль, а нуль – в нуль и единицу. Данная взаимосвязь символов в закодированной кодовой комбинации обеспечивает обнаружение большинства ошибок, за исключением случаев, когда ошибки происходят одновременно в двух рядом расположенных символах, соответствующих одному символу исходного кода. Вероятность появления необнаруженной ошибки P_но=С_n/2¹P²q^2n-2. Код имеет большую избыточность – R=r/n=0,5

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

  Пример

Закодировать КК 10110 и 01010 à1001101001 и 0110011001

Кодер

Декодер

Код Хэмминга. Кодирующие и декодир. устройства.

 

Коды Хэмминга с минимальным кодовым расстоянием d_min=3 и d_min=4 относятся к оптимальным систематическим кодам, исправляющим все варианты одиночных ошибок

Оптимальным (n,k)-кодом является такой код, который обеспечивает наименьшую вероятность неправильного декодирования среди всех кодов с теми же значениями n и k. Коды Хэмминга совершенны, т.к. исправляют только все одиночные ошибки. Коды с минимальным кодовым расстоянием d_min=4 образуются на основе кодов с d_min=3 путем введения ещё одного проверочного символа.

Число проверочных символов r, при r=n–k:  2^r≥n+1    2^k≤2ⁿ/(n+1), где n и k могут принимать только целые значения.

Пример Закодировать КК простого кода 10110 (а3=0 а5=1 а6=1 а7=0 а9=1)

а1=a3+a5+a7+a9=0+1+0+1=0 а2=a3+a6+a7=0+1+0=1  а4=a5+a6+a7=1+1+0=0 а8=a9=1=1

Закодированная КК – 110110010

При декодировании принятой КК получается r-импульсный синдром вида S=S₄S₃S₂S₁, элементы КК синдрома получаются на основании проверочных уравнений, которые строятся по линейным уравнениям с добавлением соответствующего проверочного импульса.

S₁=a1+a3+a5+a7+a8     S₂=a2+a3+a6+a7  S₃=a4+a5+a6+a7  S₄=a8+a9

Пример Принята КК вида 111110010, рассчитать синдром и найти ошибку.

S1=0+0+1+1+1=1 S2=1+0+1+1=1 S3=0+1+1+1=1 S4=1+1=0

Синдром 0111 показал, что в 7 разряде ошибка (0111₂=7₁₀).

Кодер

Декодер

Порядок формирования проверочных символов определяется алгоритмом обнаружения и исправления искаженного символа, т.е требованием, предъявляемым к синдрому.

Синдром - двоичное r-разрядное число, записанное по результатам r проверок, указывает номер искаженного символа к.к.

Исходя из изложенного требования к формированию проверочных символов, определяют, какие из символов закодированной к.к. должны охватываться каждой из r проверок.

22.   Линейные коды. Кодирующие и декодирующие устройства.

Линейные коды являются разделимыми и систематическими. На всю совокупность кодовой комбинации накладывается одно ограничение (суммирование по модулю 2 двух разрешенных КК дает нам так же разрешенную). Линейные коды удобно представлять в виде порождающих матриц

;

n – общее количество импульсов закодированной комбинации;

k – информационные импульсы.

Ограничения на порождающую матрицу:

1) Все исходные кодовые комбинации (строки матрицы) должны быть различны, т.к. являются разрешенными КК, если это условие не выполняется, то при сложении 2х одинаковых кодовых комбинаций (строк матрицы) будет получаться нулевая КК;

2) Нулевая КК не должна входить в состав исходных КК порождающей матрицы, т.к. при её сложении с любой строкой порождающей матрицы получаем туже строку;

3) Все исходные КК порождающей матрицы должны быть линейно независимыми;

4) Каждая исходная КК порождающей матрицы, как и любая ненулевая разрешенная КК, должны иметь вес не менее d_min (W ≥d_min);

Любая разрешенная КК должна отстоять от нулевой КК (по кодовому расстоянию) не менее чем на d_min;

5) Кодовое расстояние между любыми парами КК не должно быть менее d_min.

Порождающая матрица в каноническом виде (приведенный ступенчатый вид) имеет вид:

;

Элементы матрицы дополнения должны получаться на основании задаваемых линейных уравнений.

Кодирование исходной комбинации кода осуществляется путем умножения ее на порождающую матрицу. А декодирование путем умножения принятой КК на транспонированную проверочную матрицу.

Кодер

Декодер

Итеративные коды.

Итеративные коды, называются так же матричными, относятся к линейным кодам. Алгоритм их кодирования заключается в добавлении в каждую строку (КК) и каждый столбец (символы с одинаковым порядковым номером) проверочных символов, полученных в соответствии с алгоритмом построения кода.

		Информационные символы					Проверка по строкам
		0	0	0	0	1	1
		1	0	1	0	0	0
		0	1	0	0	0	1
		1	0	1	0	1	1
		1	0	0	0	1	0
		1	1	0	1	0	1
Проверка по столбцам		0	0	0	1	1	0
								Проверка проверок

 . – не обнаружит ошибку

В качестве проверки проводится проверка на четность.

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

=2*2=4

Вероятность появления необнаруженных ошибок находятся из соотношения

P_но=С_n+1²С_L+1²p⁴q^nL-4

где n – длина строки (элемент в строке);

L – общее число строк;

p – вероятность искажения в ЛС;

q – вероятность появления правильного импульса.

Декодирование начинается с проверки на четность единиц по строкам и столбцам. Если в какой-либо строке или столбце не выполняется условие чётности единиц, то в соответствующей строке или столбце имеется ошибка.