<< Предыдущая

стр. 34
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

Глава 3. Циклические коды

Теорема 3.7.1. Циклический (п, /с)-код способен обнаруживать все
пакеты ошибок (в том числе концевые) длины г = п — к и меньше.

Помимо распознавания всех пакетов ошибок длины г и меньше,
циклические коды обладают способностью обнаруживать большую
часть пакетов ошибок, длина которых превосходит г.
Рассмотрим пакет ошибок длины г + 1, начинающийся в j-ой
компоненте. Так как первая и последняя компоненты пакета оши-
Г 1
бок отличны от нуля, всего имеется 2 ˜ возможных конфигураций
ошибок. Необнаружимой является только одна из них, многочлен
которой В(Х) совпадает с д(Х), то есть

е(Х) = XjB(X) = Xjg(X). (3.76)


Теорема 3.7.2. Для циклического (п, &)-кода доля необнаружимых
пакетов ошибок длины / = r + l = n —fc+ 1 равна 2˜(г˜1>,

Рассмотрим пакет ошибок длины l>r + l = n — k + \, начина-
ющийся в j-oib компоненте. Если соответствующий многочлен В(Х)
делится на д(Х) без остатка, то есть

е(Х) = Х^В(Х) = Х*а(Х)д{Х), (3.77)

то такой пакет не может быть обнаружен.
Пусть коэффициенты многочлена а(Х) степени I — г — 1 имеют
вид OQ, а\,...,a;_r_i. Так как пакет ошибок начинается и заканчи-
вается единицей, ао = O(_r_i = 1. Следовательно, существует 2'˜ г ˜ 2
наборов коэффициентов а(Х), приводящих к необнаружимым ошиб-
; 2
кам в (3.77). С другой стороны, существует 2 ˜ различных пакетов
ошибок длины I и, таким образом, верно следующее утверждение.


Теорема 3.7.3. Для циклического (п, А;)-кода доля необнаружимых
пакетов ошибок длины I > г + 1 = п —fc+ 1 равна 1˜Т.

Пример: Распознавание ошибок циклическим (7,4)-кодом Хэм-
минга.

Рассмотрим циклический (7,4)-код Хэмминга из предыдущих при-
меров сг — п — А = 3. Так как минимальное кодовое расстояние кода
;
Хэмминга d m i n = 3, он способен обнаруживать все двойные ошиб-
ки или исправлять одиночные. Рассматриваемый (7,4)-код Хэммин-
га является циклическим кодом и он способен также обнаруживать
S.8. Декодер Меггитта

все пакеты длины г = 3. В частности, любые три следующие друг за
другом ошибки всегда обнаруживаются.
Доля необнаружимых ошибок длины г + 1 = 4 равна 2˜( 3-1 ) =
1/4. При пакетах ошибок с длиной большей 4, не распознается только
3
2˜ = 1/8 из них.
Замечание. На практике, как правило, испдльзуются циклические
коды с довольно большим числом проверочных разрядов, например,
г = п — к = 16. Доля необнаружимых пакетов ошибок такими
кодами достаточна мала. Так, при г = 16, обнаруживается более
чем 99,9969 % пакетов длины Пи 99,9984 % пакетов длины 18 и
выше.


3.8. Декодер Меггитта
Процесс декодирования циклических кодов (как и вообще всех ли-
нейных блоковых кодов) можно разделить на три этапа:
1. Вычисление синдрома;
2. Определение ошибочных компонент принятого слова;
3. Исправление ошибок или выдача сигнала о наличии неиспра-
вимых ошибок.
Оценивая сложность обработки принятого сигнала, можно заме-
тить, что декодирование является «узким местом», в цепи передачи
информации. Это связано с очень большими аппаратными затра-
тами на декодирование длинных кодов с высокой корректирующей
способностью.
Для циклических кодов процедура вычисления синдромов от-
носительно проста. Из рис. 3.12 видно, что сложность вычисления
синдрома мало зависит от длины кодового слова и определяется, в
основном, числом проверочных символов.
Определение ошибочных компонент по синдрому для всех линей-
ных блоковых кодов может быть сделано, в принципе, с помощью
таблицы синдромов. Сложность реализации такого метода декоди-
рования возрастает экспоненциально с ростом длины кодовых слов
и корректирующей способности кода [7]. Здесь на помощь приходят
некоторые особые свойства циклических кодов, которые позволяют
существенно упростить процесс декодирования.
В настоящем разделе мы представляем достаточно простую схему
декодера двоичных циклических (п, &)-кодов в общем виде. Будем
Глава 3. Циклические коды

исходить из модели передачи информации рис. 3.11. В этой схеме
принятый многочлен обозначается через г(Х), кодовый многочлен -
через v(X), а многочлен ошибок - через е.(Х).
Первым шагом декодирования является вычисление синдрома.
Здесь могут возникнуть два случая:

1. Найденный синдром соответствует ошибке в (п — 1)-ой компо-
ненте принятого слова, то есть еп-\ = 1;

2. Синдром не соответствует такой ошибочной компоненте.

В последнем случае процесс, представленный на рис. 3.11 может
быть повторно проделан для сдвинутого слова г^(Х). При этом,
для вычисления s^\X) нет необходимости проводить действия, ана-
логичные нахождению s(X). Согласно теореме 3.6.1, синдром s(X)
преобразуется в синдром s^(X) за один такт с помощью схемы,
представленной на рис. 3.15.
После того, как определен s(X), мы можем последовательно по-
,s( n ˜''(X). Если синдромы не
лучить синдромы s^(X),s^(X),...
корректировать, то через п тактов мы опять придем к первоначаль-
n
ному синдрому s(X) = s( )(X) многочлена г(Х). Однако, если в
процессе работы получен синдром, соответствующий еп-\ = 1, то
некоторая компонента многочлена г(Х) должна быть исправлена.
В этом случае также корректируется еще и некоторый синдром из/
,s("˜l)(X). Рассмотрим про-
последовательности s^(X),s^(X),...
стейший случай. Пусть синдром s(X) сразу же соответствует (п —1)-
ой ошибочной компоненте многочлена г(Х), то есть e n _i = 1. Тогда
скорректированный многочлен т)(Х) будет иметь вид:

7 7 (Х)=го + г 1 Х + --- + ( г п _ 1 + е „ _ 1 ) Х " - 1 . • (3.78)

Заметим, что на последующих шагах декодирования должен ис-
пользоваться синдром модифицированного многочлена из (3.78). Так
как s(X) является синдромом r(X), a s'(X) - синдром многочлена-
е'(Х) = Хп˜г, синдром многочлена т](Х) равен

(3.79)
(X) = s{X) + s'(X).
Sl



Коррекцию синдрома удобнее производить только на следующем так-
те декодирования. В этом случае, после циклического сдвига г(Х)
ошибочной нулевой компоненте будет соответствовать многочлен.
3.8. Декодер Меггитта

е'(Х) = 1, а синдром скорректированного многочлена rf^{X) будет
равен
i}
(3.80)
s[ (X) = sW(X) + l.
Контроль ошибок производится по всем п компонентам принято-
го многочлена г(Х) и найденные ошибки исправляются. Если после
п тактов контроля ошибок синдром отличен от нулевого, то выдается
сигнал о наличии неисправляемых ошибок. Такой алгоритм может
быть, в принципе, использован для декодирования всех циклических
(п, &)-кодов. Его реализация, декодер Меггитта, в общем виде пред-
ставлена на рис. 3.18.

и- разрядный буфер
Принятое из канала
слово
-> Выходной регистр


. Исправление
ошибок



Модификация
' Логическая схема
синдрома




Р и с . 3.18. Декодер Меггитта для двоичного циклического
(га, fcj-кода с порождающим многочленом д{Х).

Перед началом работы оба регистра декодера Меггитта обнуля-
ются. На первых п тактах декодирования принятое слово загружа-
ется в верхний регистр, а в нижнем регистре вычисляется синдром
многочлена г(Х). После этого вход декодера отключается и в тече-
нии последующих п тактов проводится покомпонентное обнаружение
и исправление ошибок. В каждом такте с помощью логической схемы
распознавания ошибок проверяется соответствие текущего синдрома
ошибочной (п — 1)-ой компоненте сдвинутого многочлена г(Х). При
обнаружении такого соответствия на следующем такте декодирова-
пия, ошибка исправляется, а синдром модифицируется.

Пример: Декодер Меггитта циклического (7,4)-кода Хэмминга.
В качестве примера рассмотрим уже знакомый нам циклический
(7,4)-кода Хэмминга с порождающим многочленом д(Х) = 1 + X 4-
X 3 . Напомним, что код Хэмминга позволяет исправлять все одно-
кратные ошибки. Более того, так как (7,4)-код Хэмминга является
совершенным, таблица синдромов однократных ошибок (см. табл.
Глава 3. Циклические коды


3.6) содержит все возможные синдромы от «001» до «111» (синдром
000 интерпретируется как отсутствие ошибок). Для построения де-
кодера Меггитта нам достаточно знать синдром одиночной ошибки
в компоненте г 6 принятого слова. Из таблицы 3.6 следует, что син-
дром одиночной ошибки г 6 = 1 равен «101» или при полиномиальном
представлении \ + Х3. Схема декодера Меггитта циклического (7,4)-
кода Хэмминга приведена на рис. 3.19. Блок распознавания ошибок
может быть построен при помощи логической схемы совпадения «И»
(&) с инверсией входа S\ (в соответствии с синдромом «101» для
г6 = 1).
Принятое из канала
слово
Выхолной регистр




Модификация
синдрома




Р и с . 3.19. Декодер Меггитта циклического (7,4)-кода Хэмминга с
порождающим многочленом д(Х) — 1 + X + X .

Принятое слово

*
o|i|i|i|o|iin
Выходной регистр


Такты 1 -7: В регистр
заносится принятое
слово и вычисляется
его синдром




Р и с . 3.20. Декодер Меггитта циклического (7,4)-кода Хэмминга с
порождающим многочленом д(Х) = 1 + X + X и при-
нятым вектором г (начальная фаза).

Рассмотрим процесс декодирования принятого слова с ошибоч-
ной компонентой г 5 . В 5том случае г = (011 1011). После первых
семи тактов работы декодера слово г(Х) полностью занесено в буф-
ферный регистр, а в нижнем регистре находится синдром s(X) для
I9S,
3.8. Декодер Меггитта


г(Х) (рис. 3.20). В соответствии с таблицей 3.6 этот синдром равен
«111».


Такт 8 '6 = 1 <k=l

Выходной регистр




Такт 9 #5=1^=0
1 Ч - I - I о I Ч Ч | I о 1—»$—-t о I Ч - I- 1-I- I
Выходной регистр




Модификация
синдрома

<< Предыдущая

стр. 34
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>