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

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

ОГЛАВЛЕНИЕ

Следующая >>




3.6. Синдром циклических кодов и контроль
ошибок
Рассмотрим модель передачи информации (рис.З.Н). При передаче
по каналу связи с шумом к кодовому слову v(X) добавляется мно-
гочлен ошибок е(Х). В результате, многочлен принятого кодового
слова имеет вид:
(3.64)
r(X)=v(X) + e(X)
или
r(X) = a(X)g(X) + s{X), (3.65)
где s(X) представляет собой синдром. Если г(Х) является кодовым
словом, то s(X) - нулевой многочлен.


Кодовый многочлен Принятый многочлен
\ Канал /
v(X)
Кодер —•«(*)
Информационный!
Инфорационный
многочлен
многочлен после
Многочлен ошибок декодирования



Р и с . 3.11. Модель передачи информации.

Синдром s(X) может быть вычислен с помощью алгоритма деле-
ния Евклида. Такое вычисление можно реализовать на простой цепи
(рис. 3.12), во многом схожей с кодером систематического цикличе-
• ского кода (рис. 3.10). В схеме, приведенной на рис. 3.12, опреде-
ляется остаток от деления некоторого многочлена на порождающий
185,
3.6. Синдром циклических кодов и контроль ошибок


многочлен д(Х). Сначала, в декодере производится обнуление дво-
ичных разрядов синдрома so,s\,...,sr_i, и в регистр синдрома за-
носятся г первых принятых из канала бит. Остаток от деления г(Х)
на порождаюгций многочлен д(Х) по алгоритму Евклида заносится
в регистр синдрома. Рассмотрим процедуру вычисления синдрома
s(X) на примере.




Принятое слово Регистр синдрома


Рис. 3.12. Вычисление синдрома систематического (n,fe)-
кода с порождающим многочленом д(Х).


Пример: Вычисление синдрома циклического (7,4)-кода Хэм-
минга.
В качестве примера, рассмотрим уже известный циклический (7,4)-
код Хэмминга с порождающим многочленом д(Х) = 1 + X + X3.
Пусть информационный вектор и = (1001). Как мы уже знаем из
предыдущего примера, этому вектору соответствует кодовое слово
v = (011 1001).




Регистр синдрома



Р и с . 3.13. Вычисление синдрома систематического (7,4)-
кода по принятому слову в канале без шума.
Глава 3. Циклические коды


При передаче но каналу без шума г = v. Процедура вычисле-
ния синдрома по тактам, в этом случае, представлена на рис. 3.13.
Так как принятое из канала слово является кодовым, мы получим
нулевой синдром.
Пусть, из-за воздействия шума в канале произошла одна ошибка
г = (011 1011). Тогда, в результате вычисления остатка от деления
г(Х) на д(Х) (рис. 3.14), мы уже полу'чаем ненулевой синдром. Та-
ким образом, произошло распознавание ошибки.


Такт л = 3




Регистр синдрома



Р и с . 3.14. Вычисление синдрома систематического (7,4)-
кода при одиночной ошибке в принятом слове.


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

Теорема 3.6.1. Пусть s(X) - синдром принятого из канала слова
г(Х) некоторого циклического (п,/г)-кода. Обозначим через s\(X)
остаток от деления многочлена X • s(X) на порождающий много-
член д{Х). Тогда si(X) является синдромом г^'(Х), т.е. остатком
от деления циклического сдвига г(Х) на порождающий многочлен
д(х).
Доказательство. Рассмотрим многочлен

п-\ (3.66)
г
3.6. Синдром циклических кодов и контроль ошибок I87J

Произведение X • г(Х) имеет вид
2
+ ••• + r n _ i Z " . (3.67)
X • г(Х) = г0Х + пХ

Циклический сдвиг многочлена г(Х) можно записать следующим
образом:

= r n _ i + r 0 X + r 1 X 2 + --- + r n _ 2 X " - I =
r«(X) (3.68)
п
= r n _! • [Х + 1] + X • г(Х).

Запишем г^(Х) в виде r^(X) = a{X)g{X) + s(X), а г(Х) в виде
г(Х) = с(Х)д(Х) + s(X), где s(X) и s(X) синдромы многочленов
г^(Х) и г(Х). Воспользуемся соотношением Хп + 1 = g{X)h{X) из
теоремы 3.2.5, тогда имеем

с(Х)д(Х) + 3(Х) = rn-1h(X)g(X) (3.69)
+ Х[а(Х)д(Х) + s(X)}.

Переставляя слагаемые в (3.69), получим связь между синдромами
ё(Х) и s(X)

X • s(X) = [c(X) + rn^h(X) + Xa(X)}-g(X) + ё{Х) . (3.70)
сомножитель остаток
Из 3.70 непосредственно следует формулировка теоремы. •

Пример: Вычисление синдрома однократных ошибок' для цик-
лического (7,4)-кода Хэмминга.



<
—*\ i H
Ч.Н6
Регистр синдрома

Рис. 3.15. Вычисление синдромов циклических сдвигов
принятого слова.

Продолжим предыдущий пример. Из рис. 3.14 следует, что од-
нократной ошибке в компоненте г§ вектора г = ( г с П , . . . ,г^) соот-
ветствует синдром s = {SQ,S\,S2) = (1,1,1) (такт п = 7). Отключив
входной регистр, получим схему, изображенную на рис. 3.15. Заме-
тим, что исходное состояние на такте п = 0 определяется синдромом
однократной ошибки в компоненте г$. Произведя циклические сдви-
ги регистра синдрома рис. 3.15, мы на каждом такте будем находить
188 Глава 3. Циклические коды
Таблица 3.6. Синдромы однократных ошибок циклического
(7,4)-кода Хэмминга с порождающим многочле-
3
ном д{х) = 1 + X + X .

Такт Ошибочная компонента
so si S2

1
1 1
0 Г5

1 1 1
0 Г6


0
1
2 0 ГО

п
1
3 0 0
1
4 0 0 Г2

0
1 1
5 гз
1 1
0
6




s(X) из (3.70). Последовательность s(X) соответствует синдромам
однократных ошибок в компонентах Гб, го и т.д. (Табл. 3.6). Зна-
чения из таблицы 3.6 полностью совпадают со значениями таблицы
2.3, полученной для проверочной матрицы систематического (7,4)-
кода Хэмминга.
Замечание. В рассмотренном примере вся таблица синдромов од-
нократных ошибок генерируется с помощью простейшей схемы, по-
этому, для кодов большей длины можно хранить в памяти декодера
таблицы синдромов, а не саму проверочную матрицу.

Рассмотрим связь между синдромом s(X) и многочленом ошибок
е(Х). Из модели передачи информации (рис. 3.11) следует

(3.71)

где
v(X) = c(X)g(X) = Xru{X) + b(X). (3.72)
Так как
r(X) = a(X)g(X) + s(X), (3.73)

то
e(X) = [a(X) + c(X)}g(X)+s(X)} (3.74)
'Из (3.74) следует, что e(X)mod(g(X)) = s(X). Так как код Хэмминга исправля-
ет все однократные ошибки, то для построения таблицы синдромов (п, А;)-кода
Хэмминга в качестве е(Х) достаточно перебрать все одночлены Х°, X1,..., Хп˜1
- Прим. перев.
3.7. Пакеты* ошибок

Знание синдрома не позволяет однозначно определить многочлен
е(Х). Так, например, если е(Х) делится без остатка на д[Х), то это-
му случаю соответствует нулевой синдром и ошибка не может быть
распознана. В этом случае говорят о необнаружимой или остаточной
ошибке декодирования.


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

е(Х) = XjB(X). (3.75)



е =(0 ... 0НШН ( ) -0)
Пакет ошибок
Начало пакета ошибок в В(Х) -1+Х +Х '-?Л
j-ой компоненте


Рис. 3.16. Вектор пакета ошибок длины 7.

Если длина пакета ошибок не превосходит величины г = п — к, то
степень многочлена ошибок меньше г. В этом случае е(Х) не делится
на д{Х) без остатка и синдром принятого слова всегда отличен от
нулевого, следовательно, пакет ошибок длины равной или меньшей
г всегда распознается. Из теоремы 3.6.1 следует, что распознается
также любой циклический сдвиг многочлена 5 ( Х ) степени, меньшей
г, т.е. и «концевой» пакет ошибок длины меньшей или равной г (рис.
3.17), всегда распознается.




Циклический сдвиг пакета ошибок


Рис. 3.17. Вектор «концевого» пакета ошибок дайны 7.

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

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

ОГЛАВЛЕНИЕ

Следующая >>