Основные характеристики помехоустойчивых кодов

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

1. Разрядность кода.

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

2. Число информационных символов.

3. Относительная скорость передачи.

Относительная скорость передачи характеризует степень использования в корректирующем коде информационных возможностей двоичных последовательностей длины n.

4. Избыточность кода.

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

5. Минимальное хеммингово расстояние кода.

Степень отличия двух любых кодовых комбинаций характеризуется расстоянием между ними в смысле Хэмминга или просто кодовым расстоянием. Оно выражается числом символов, в которых комбинации отличаются одна от другой, и обозначается через d. Минимальное расстояние, взятое по всем парам кодовых разрешенных комбинаций кода, называют минимальным кодовым расстоянием.

6. Корректирующая способность кода.

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

1. Верность передачи сообщения.

Под верностью передачи сообщения корректирующим кодом понимается степень соответствия между комбинацией на выходе устройства обнаружения и исправления ошибок и комбинацией на входе канала. Верность передачи сообщения характеризуется вероятностью обнаружения ошибки и вероятностью необнаружения ошибки.

Циклические коды.

Из всех разновидностей помехоустойчивых кодов циклические коды получили наибольшее распространение. Это обусловлено их высокими корректирующими свойствами и сравнительно простой реализацией кодирующих и декодирующих устройств, в которых они используются.

При описании свойств циклических кодов пользуются представлением кодовых комбинаций в виде многочленов от фиктивной переменной x, в которых цифры 0 и 1, составляющие кодовые комбинации, являются коэффициентами переменной. Если число элементов кодовой комбинации равно n, то соответствующий ей многочлен F(x) имеет вид:

где c_i, i=0,n-1 – коэффициенты, принимающие значения 0 или 1.

Например, кодовой комбинации 101100011 соответствует многочлен F(x)=x⁸+x⁶+x⁵+x+1.

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

01101 11010 10101 01011.

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

.

В силу свойства цикличности каждый кодовый полином данного кода должен быть кратным минимальному ненулевому кодовому полиному g(x), то есть должно выполняться условие F(x)=g(x)m(x). C другой стороны любой кодовый полином степени (n-k) может быть получен путем умножения полинома g(x) на соответствующий полином m(x). Полином g(x) называется порождающим или образующим полиномом. Таким образом, любой циклический (n-k)-код полностью определяется его порождающим полиномом. В качестве образующих полиномов циклических кодов наибольшее распространение получили:

g(x)=x¹⁶+x¹⁵+x²+1 (CRC-16);

g(x)=x¹⁶+x¹²+x⁵+1 (CRC-CCITT);

g(x)=x¹²+x¹¹+x³+x²+x+1 (CRC-12);

g(x)=x³²+x²⁶+x²³+x¹⁶+x¹²+x¹¹+x¹⁰+x⁸+x⁷+x⁵+x⁴+x²+x+1 (CRC-32).

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

. (1)

Крупным недостатком этого способа является то, что он приводит к неразделимому коду, в котором информационные и проверочные символы не занимают постоянных мест в кодограмме.

Пример 1. Пусть кодированию подлежит m(x)=x+1(0011). Образующий полином g(x)= x³+x²+1(1101). n=7, k=4.

Выполним следующее действие:

0011

0000

F(x)= x⁴+x²+x+1.

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

(2)

Пример 2. m(x)=0011; g(x)=1101; n=7; k=4.

0011 0011000 1101

1000 1101

0000 0010 0010

0000 0000

0000

0011 010

Тогда F(x)=0011010.

Третий способ кодирования основан на том, что циклический код является систематическим (линейным) и его проверочные и информационные символы связаны линейными соотношениями. Представив комбинацию циклического кода в виде (c_n-1, … ,c_n-k, c_n-k-1, … ,c₁,c₀), где (c_n-1, … ,c_n-k)-информационные элементы, (c_n-k-1, … ,c₁,c₀)-проверочные элементы, можно сказать, что j-й проверочный символ определяется соотношением

, (3)

где h_i – коэффициенты проверочного многочлена.

.

Таким образом, любой символ циклического кода является взвешенной суммой k других символов кода ( суммирование выполняется по модулю 2 ).

Пример 3. Вычислим проверочный многочлен

.

Для информационного многочлена m(x)=x+1(0011) имеем

c₆h₀Åc₅h₁Åc₄h₂Åc₃h₃= 0*1Å0*0Å1*1Å1*1=0;

c₅h₀Åc₄h₁Åc₃h₂Åc₂h₃= 0*1Å1*0Å1*1Å0*1=1;

c₄h₀Åc₃h₁Åc₂h₂Åc₁h₃= 1*1Å1*0Å0*1Å1*1=0.

Таким образом, F(x)=0011010.

Основной метод декодирования циклических кодов основан на свойствах делимости многочленов, описывающих кодограммы, на образующий многочлен. Декодирующее устройство осуществляет деление принятой кодограммы на образующий многочлен. Если остаток от деления нулевой, то это указывает на отсутствие ошибки. Если остаток имеет хотя бы один ненулевой коэффициент, то в принятой кодограмме имеют место ошибки. Исправление ошибок осуществляется путем анализа полученного остатка либо на основании проверки выполнения соотношений (3).

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

Варианты заданий

Построить модель кодирующего устройства циклического кода.

Номер варианта	Способ кодирования	n	k	g(x)
				x3+x2+1
				x3+x2+1
				x3+x2+1
				x3+x+1
				x3+x+1
				x3+x+1
				x4+x3+x2+1
				x4+x3+x2+1
				x4+x3+x2+1
				x4+x2+x+1
				x4+x2+x+1
				x4+x2+x+1
				x4+x3+x+1
				x4+x3+x+1
				x4+x3+x+1
				x4+x3+x2
				x4+x3+x2
				x4+x3+x2
				x4+x3+x
				x4+x3+x
				x4+x3+x
				x4+x2+1
				x4+x2+1
				x4+x2+1
				x4+x3+1

Лабораторная работа № 5