Обнаружение ошибок при циклическом кодировании

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

Н (х) = F (х) Е (х), (3)

где Е (х) - многочлен ошибок, содержащий в составе столько ненулевых разрядов, сколько кодовых элементов в принимаемой кодовой комбинации не совпадает с переданной.

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

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

Если ошибок в принятой кодовой комбинации нет, то в результате деления принятой кодовой комбинации на образующий полином получим нулевой остаток (остаток R(х) = 0).

Если при делении получится остаток (R (х) 0), то это свидетельствует о наличии ошибок в принятой кодовой комбинации.

Следовательно, многочлен R (х) в циклических кодах играет роль синдрома.

Пусть, например, передана следующая кодовая комбинация:

100000101 = F (х) = х⁸ + х² + 1,

а образующий полином Р (х) = х⁴ + х + 1 = 10011.

В информационной части этой комбинации произошла ошибка, и она принята как

101000101 = Н (х) = х⁸ + х⁶ + х² + 1.

Сложив по модулю 2 вектора переданной и принятой кодовой комбинации, получим вектор ошибки и соответствующий ему многочлен ошибки Е (х).

1 0 0 0 0 0 1 0 1 = F (х) = х⁸ + х² + 1 Передано

1 0 1 0 0 0 1 0 1 = Н (х)= х⁸ + х⁶ + х² + 1 П р и н я т о

001000000 = Е(х)= .

Так как F (х) делится на Р (х) без остатка, то, поделив обе части выражения (3) на Р (х), получим

Произведём операцию обнаружения ошибки.

для данного примера получим re =х³ + х² = 1100

или

101000101 10011

10010101

11100

10011

11111

1100

Наличие остатка 1100= х³ + х² свидетельствует об ошибке, т. е. она обнаружена.

Исправление ошибок и выбор образующего полинома:

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

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

Это однозначное соответствие позволяет по виду синдрома (остатка) определить место ошибки.

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

Однако не все неприводимые полиномы позволяют формировать различных остатков. Этим свойством обладают полиномы только определенного класса - класса «примитивных» многочленов. Полиномы данного класса дают максимальное число различных остатков, равное . Этим свойством определяется их пригодность для построения циклических кодов.

Пусть для кода (15,11) с r=4 имеются два полинома ошибок:

и .

В качестве образующего полинома выберем

(х) = х⁴ + х³ + х² + х+ 1.

Нетрудно видеть, что для = 1 и для х⁵ будет одинаковый остаток (х) = 1 (в двоичном виде = 0001). Если же выбрать , то в первом случае имеем , а во втором- .

При использовании в качестве образующего полинома Р₂ (х) все 15 многочленов Е (х) дают различные остатки.

Итак, в качестве образующих используют примитивные многочлены.

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

делении и , где n - количество элементов в кодовой комбинации.

Между n и r для таких полиномов имеется зависимость 2^r = n - 1.

Здесь r - максимальное количество элементов, при котором число различающихся ненулевых остатков равно n - 1.

Для определения номеров элементов, в которых произошла ошибка, существует несколько методов, основанных на анализе синдрома R(х).

Один из них основан на свойстве, что R(х), полученный при делении принятого многочлена Н(х) на Р(х) степени г, равен R(х), полученному от деления соответствующего многочлена ошибок Е(х) на Р(х) степени г, если

F (х) = Н (х) Е (х).

Это условие справедливо, если код способен исправлять количество ошибок , равное или меньшее веса комбинации Е (х). Синдром не зависит от переданной кодовой комбинации, но в нём сосредоточена вся информация о наличии ошибок. Указанное свойство можно использовать для определения номера искаженного кодового символа.

Пусть ошибка произошла в старшем разряде переданной кодовой комбинации . В этом случае (х) - есть остаток от деления принятой комбинации Н (х) на Р (х).

Такой же остаток (х) получается, если разделить на Р (х) вектор ошибок, т.е. многочлен .

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

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

Пусть кодовая комбинация 10110111100 принадлежит коду (11,7).

Здесь последние четыре разряда проверочные и получены на основе использования производящего многочлена Р₍₂₎ = 10011.

Допустим, ошибка произошла в старшем () разряде. Следовательно, принимаемая комбинация = 00110111100. Значит, многочлен ошибки = 10000000000 или х¹⁰.

Разделив на Р₍₂₎, получим

00110111100 10011

10011

10001 11001

10011

10100

10011

Теперь разделим Е₍₂₎ на

0000000000 10011
10011 1001101

11000

10011

10110

10011

10100

10011

Таким образом, убеждаемся, что остатки совпадают.

Теперь предположим, что принимаемая комбинация Н (0, 1) = 10111111100. Определим ошибочно принятый элемент (известно, что код исправляет одну ошибку).

а) Вычисляем R₀(x) как остаток от деления х¹⁰=Е(х)= на
Р (0, 1) = 10011. Произведя деление, получим R ₀ (0, 1) = 0111.

б) Делим принятую комбинацию Н (0, 1) на Р (0, 1) и получаем остаток R₁ (0, 1). Если то ошибка в старшем разряде. Если нет, то дописываем к Н (0, 1) справа нуль (осуществляем сдвиг влево на один разряд) и продолжаем деление. Находим остаток Если R₂(0, l) R₀(0, 1), то дописываем ещё один нуль и т.д. до тех пор, пока остаток не окажется где i - число сдвигов. Номер ошибочно

принятого разряда (отсчёт слева направо) на единицу больше числа приписанных нулей.

Проведём процесс деления, отмечая штрихом получаемые остатки (0, 1),R₂(0, 1), R₃(0, 1),R₄(0, 1):

10111111100

10011

10011

10011

0000011000 (1)

10011

10110 (2)

10011

10100 (3)

10011

0111 (4)

В данном примере пришлось дописать четыре нуля (число сдвигов равно четырём), i = 4 и искажённый разряд .

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

F(0, 1)= 10111111100 00001000000=10110111100.

В общем случае разложение двучлена хⁿ + 1 на неприводимые многочлены удобно представить в виде

xⁿ+l = (4)

Здесь - так называемые минимальные многочлены.

Например, для n = 15

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

· Для кодов, исправляющих одиночные ошибки (d₀ = 3), образующий многочлен Р (х) = .

· Для исправления двойных ошибок ( =5), Р(х) = ,

· тройных ошибок ( = 7)

Р (х) = и т. д.

Циклические коды, образующий многочлен которых построен на основе разложения двучлена xⁿ + 1 по минимальным многочленам, получили название кодов Боуза-Чоудхури-Хоквингема.

Циклический код, образованный многочленом Р(х) степени r, гарантированно обнаруживает все пакеты ошибок длиной .

Длина пакета ошибок - количество элементов, расположенных между старшим и младшим искажёнными разрядами, включая сами эти разряды.

Длину пакета ошибок удобно оценивать по комбинации или многочлену ошибок.

Так, если передавалась кодовая комбинация

F(х)= х⁸ + х² + 1 =100000101, а принята кодовая комбинация Н(х)= х⁸ + х⁵ + х³ + 1 = 100101001, то комбинация ошибки Е(х) = = х⁵ + х³ + х² =000101100. Здесь .

В общем случае разность степеней одночленов старшего и младшего искажённых разрядов j - i =

Вынося в многочлене Е (х) за скобку хⁱ, получаем Е (х) =

Степень многочлена (х), равна -1, т. е. меньше степени r делителя, и, следовательно, (х), а значит, и Е (х) не могут делится без остатка на Р (х), что обеспечивает обнаружение пакетов ошибок длиной .

Декодирование на основе анализа веса:

Для нахождения ошибочных элементов в кодах с d₀ > 5 получили распространение методы, основанные на анализе веса остатка. При этом осуществляются следующие процедуры:

· принятая кодовая комбинация делится на Р (х) степени r;

· подсчитывается вес остатка w (количество единиц в остатке);

· если (t_и - допустимое количество ошибок, которое исправляется кодом), то исправление сводится к сложению принятой кодовой комбинации с остатком;

· если w > t_и, то производят циклический сдвиг принятой кодовой комбинации влево на один разряд, а затем делят её на Р (х) и определяют вес остатка. Если , то делимое суммируют с остатком, а затем производят циклический сдвиг на один элемент вправо. Это и будет исправленная кодовая комбинация;

· если после первого сдвига остаток даёт w , то повторяют операцию сдвига на один разряд влево, а затем деление и определение веса остатка производят до тех пор, пока не будет удовлетворяться условие .

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

Рассмотрим данную методику относительно = 3 и = 1. Передана кодовая комбинация 1001110. Образующий полином Р (х) = х + х + 1.

Ошибка произошла на позиции а₄, т.е. принята кодовая комбинация 1000110.

Определим номер элемента с ошибкой.

1. Находим R(0, 1) от деления 1000110 на Р (0,1) = 1 0 1 1. Итак, R(0, 1) = 011.

2. Сдвигаем 1000110 влево на один разряд, имеем 0001101; a R (0, 1)=110, w=2 > .

3. Сдвигаем влево ещё на разряд (всего на два), имеем 0011010; а R(0,l)=111,

.

4. Повторяем сдвиг влево (всего на три разряда), имеем 0110100, а R(0, 1)= 101,

.

5. Делаем ещё сдвиг (всего на четыре разряда), при этом имеем 1101000. Тогда

.

6. Производим сложение сдвинутой кодовой комбинации с остатком. В результате

имеем 1101000 001=1101001.

7. Сдвигаем эту кодовую комбинацию вправо на четыре разряда и получаем исправленную кодовую комбинацию:

1101001 1110100 0111010 0011101 101110

Матричное представление циклических кодов:

Циклические коды относятся к классу систематических кодов, которые могут быть заданы в виде образующих (производящих) матриц.

Для формирования строк производящей матрицы разделимого циклического кода берут не произвольные комбинации информационного (первичного) кода Q (х), а только те из них, которые содержат единицу в одном разряде (х), где i = 1,..., к.

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

Тогда i-ю строку производящей матрицы записывают в виде .

Матрица, состоящая из этих строк, разбивается также на две подматрицы:

где I_k - единичная подматрица, содержащая (х) комбинаций информационного кода;

-подматрица с числом столбцов r и строк k, образованных остатками от деления (x).

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

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

Производящая матрица содержит k комбинаций циклического кода.

Остальные 2^k - k - 1 комбинаций получают суммированием по модулю 2 строк матрицы во всевозможных сочетаниях.

Последняя комбинация является нулевой.

Рассмотрим в качестве примера код (7, 4)-код с исправлением одиночных ошибок. Так как для этого кода n = 7, к = 4, = 3 и r = n - k = 3, то выберем в качестве образующего многочлен Р (х) = х³ + х + 1; Р(0, 1)= 1011.

Единичная матрица первичного кода .

Каждая строка соответствует Q(x)= х³, а

Найдём остатки от деления:

1000000 1011

1011 1011

0110

0000

1100

1011

1110

1011

Таким образом, матрица циклического (7, 4)-кода может быть записана в виде

.

После перестановки строк матрица может быть записана так:

. (5)

Сложив в (5) первую и третью, а также первую, вторую и четвёртую строки, получим

.

Перестановка строк и их сложение по модулю 2 допустимы, так как эти операции не изменяют структуру кодовых комбинаций.

Первая строка матрицы представляет собой образующий многочлен Р(х) =х³ + х + 1 в двоичном изображении.

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

.

Ненулевые элементы являются коэффициентами образующего многочлена Р(х)=

---

Дата добавления: 2015-07-16