Материал: 636_Nosov_V.I._Seti_radiodostupa_CH.1_

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

Большинство используемых на практике блочных кодов с коррекцией ошибок относятся к категории циклических. Для циклических кодов справедливо следующее: если n-битовая последовательность (c0 ,c1,...,cn 1)

является кодовым словом, то последовательность (cn 1,c0 ,c1,...,cn 2 ) полученная с

помощью циклического сдвига n-битовой последовательности с на одну позицию вправо, также используется в качестве кодового слова. Данный класс кодов можно легко кодировать и декодировать с использованием линейных регистров сдвига с обратной связью (Linear Feedback Shift Register — LFSR). Примерами циклических кодов являются коды Боуза-Чоудхури-Хоквенгема (БЧХ) и коды Рида-Соломона. I

Реализация циклического кодера как регистра LFSR подобна реализации приведенной на рис. 3.9 для кодов обнаружения ошибок. Основное отличие состоит в том, что вход кода CRC имеет произвольную длину и в результате получается контрольный код CRC фиксированной длины, тогда как циклический код с коррекцией ошибок генерирует контрольный код (п - k бит) на основе входной последовательности фиксированной длины (k бит). На рисунках 4.7 и 4.8 представлены реализации в виде LFSR кодера и декодера циклического блочного кода.

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

где каждый из коэффициентов Аi, может принимать значения 0 или 1, что соответствует двоичному разряду в делителе. Например, для Р = 11001

Чтобы синтезировать циклический код (7, 4) можно использовать один из двух порождающих полиномов

Аналогично представлению порождающего полинома последовательность битов данных можно представить полиномом D(Х), а контрольный код – полиномом R(Х) (см. обсуждение циклической проверки четности с избыточностью). Напомним, что контрольный код определяется следующим образом

Т.е. блок данных D(Х) сдвигается влево на (п – k) бит и делится на P(X). В результате получим частное Q(X) и остаток R(Х) длиной (п – k) бит.

Для проведения этой операции ключи П1 и П2 рисунок 4.7 находятся в положении 1 и на вход схемы деления поступают информационные символы D(Х), одновременно эти же символы поступают и на выход. После k тактов работы кодера в его регистре образуется остаток от деления R(Х). На (k+1) такте ключи П1 и П2 переключаются в положение 2 и символы остатка один за другим поступают на выход кодера.

Передаваемый на модулятор блок битов T(X) – это конкатенация D(Х) и

R(Х)

После прохождения канала передачи этот блок поступает на декодер циклического кода рисунок 4.8.

Для декодера входом являются полученные п бит T(X), которые содержат k бит данных D(X) за которыми следуют (п - k) контрольных битов R(X). Ключ П1 находится в положении 1 на время прохождения всех n бит входного блока T(X). При отсутствии ошибок после первых k тактов регистр сдвига порождающего многочлена будет содержать последовательность контрольных битов, идентичную переданной R(X).

117

После прохождения оставшихся (п - k) входных бит регистр сдвига порождающего многочлена будет содержать код-синдром. После прохождения всех n бит входного блока T(X) переключатель П1 переводится в положение 2.

Для декодирования циклического кода используется следующая процедура:

1.С помощью полученных битов вычисляется код-синдром. Вычисления проводятся аналогично тому, как кодер обрабатывает биты данных для получения контрольного кода;

2.Если все биты синдрома равны нулю — ошибки отсутствуют;

3.Если синдром отличен от нуля, производится дополнительная обработка для исправления ошибки.

Рис. 4.8 Структурная схема декодера циклического кода

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

При отсутствии ошибок передачи T(X) должно делиться на порождающий полином P(X) без остатка, что можно легко показать, используя формулы (3.24)

и (3.25)

118

Выражение (3.26) справедливо в соответствии с правилами арифметики по модулю 2 ( a a 0 ). Следовательно, если ошибки отсутствуют, T(X) делится на P(X) без остатка.

Если один или более бит являются ошибочными, полученный на приемной стороне блок бит Z(X) будет иметь вид

где E(X) = (e1, e2, e3, … , en)– n – битовый полином ошибок, содержащий 1 в каждом двоичном разряде , где в Z(X) имеется ошибка. Если Z(X) проходит через регистр порождающего полинома, то фактически в нем производится деление Z(X)/P(X), что в результате дает синдром S(X) = (s1, s2,s3, …, sn-k) длиной

(n-k) бит

где B(X) – частное, S(X) – остаток деления. Следовательно, S(X) является функцией Z(X). Теперь определим, каким образом полученный результат можно использовать для исправления ошибок. Запишем уравнение (4.19) с учетом выражений (4.15) –(4.18) и получим выражение (4.20), из которого видно, что деление E(X)/P(X) дает тот же остаток, что и Z(X)/P(X). Таким образом, значение синдрома S(X) зависит только от ошибочных битов и не зависит от начальной последовательности битов (переданного значения T(X)). Если ошибочные биты E(X) можно получить из синдрома S(X), то ошибки в Z(X) можно исправить с помощью простого сложения

Z(X ) E(X ) T (X ) E(X ) E(X ) T (X ).

Поскольку S(X) зависит только от E(X), возможности блочного циклического кода определить очень легко. Синдром состоит из (n-k) бит, следовательно он может принимать 2n k возможных значений. Если все биты синдрома равны нулю, это указывает на отсутствие ошибок. Следовательно, всего можно исправить 2n k 1 различных ошибочных комбинаций.

119

Чтобы с помощью блочного кода (n, k) можно было исправить все возможные однобитовые ошибки, должно выполняться неравенство n (2n k 1).

Исправление всех 1- и 2-битовых ошибок требует выполнения следующего неравенства

Способ получения E(X) из S(X) может зависеть от используемого кода. Наиболее простой подход – построить таблицу, которая ставила бы в соответствие значениям E(X) значения S(X). После этого потребуется простой способ выполнения поиска в этой таблице.

Пример. Рассмотрим блочный циклический код (7 ,4) с порождающим многочленом P(X ) X 3 X 2 1. В соответствии с (4.21) имеем 7 = 23 -1,

следовательно, с помощью этого кода можно исправить все однобитовые ошибки, что соответствует dmin 3. В таблице 4.4 а приведены все

соответствует кодовому слову 1010001.

Для коррекции ошибок требуется таблица синдромов, приведенная в таблице 4.4 б. Например, для последовательности ошибок 1000000 E(X) будет равно X 6 .

Используя последнюю строку уравнения (4.20) рассчитаем для данной одиночной ошибки еѐ синдром рисунок 4.10.

120