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

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

ОГЛАВЛЕНИЕ

Следующая >>

Таким образом, мы имеем

mod g{X) = [e{i)(X)} mod g{X) = s'(X). (3.102)
[d(X)e(X)\

Обобщая все вышесказанное, можно сделать следующие выводы:

• Ошибка обнаруживается при ее сдвиге в старший разряд кодо-
вого слова укороченного (п — l,k — /)-кода и исправляется на
следующем такте работы декодера;

• В схеме декодера вычисляется синдром вспомогательного мно-
гочлена е.\Х) = e(X)d(X). В этом случае ошибке е(Х) =
Xn-1-i соответствует синдром s'(X) = Хп˜к˜г, который также
корректируется на следующем такте;
г
• Многочлен d(X) является остатком от деления Х на д(Х), где
г определяется длиной укорочения I и степенью производящего
многочлена д(Х);

• Так как степень многочлена d(X) всегда меньше степени д(Х),
схема умножения е(Х) на d{X) может быть реализована с по-
мощью простых сдвигов.

Пример: Укороченный (6,3)-код.
Рассмотрим построение оптимального, с точки зрения затрат, де-
кодера'укороченного (6,3)-код. Напомним, что этот код образуется
укорочением базового циклического (7,4)-кода Хэмминга с порожда-
3
ющим многочленом д(Х) = 1 + X + X . В этом случае многочлену
ошибки е(Х) = X5 должен соответствовать синдром вспомогатель-
ного многочлена s'(X) = X2. Так как X2 является четырехкратным
циклическим сдвигом многочлена е(Х) = X5, множитель d(X) опре-
деляется как

d{X) = [X4] mod {X3 + X + 1) = X2 + X, (3.103)

и вспомогательный многочлен е'(Х) равен

d(X)e{X) = Х2е(Х) + Хе(Х). (3.104)

Заметим, что умножение на d(X) в (3.104) соответствует линейной
комбинации однократного и двукратного сдвигов вектора ошибки.
3.12. Укороченные коды

Таким образом, в схеме рис. 3.23 вектор ошибки через суммато-
ры однавременно подается на разряды s\ и *2 регистра вычисления
синдрома. На рис. 3.23 приведен пример вычисления синдрома для
е = (0,0,0,0,0,1), то есть синдрома ошибки, находящейся в старшем
разряде укороченного (6,3)-кода. Как и следовало ожидать, после
шестого такта мы получаем синдром s' = (0,0,1).

Принятое из канала
Такт *|

слово
0 0 0 0
1 0 1 1
2 1 1 1,
3 1 1
0
4 1 0 0
5 0 1 0
6 0
0 1


Р и с . 3.23. Модифицированный алгоритм вычисления син-
дрома с предварительным умножением вектора
ошибки на d(X) = X2 + X.

Схема исправления однократной ошибки и коррекции синдрома
с использованием вспомогательного многочлена е!{Х) приведена на
рис. 3.24. По вычисленному синдрому s' = (0,0,1) происходит обна-
ружение и исправление ошибки. Одновременно синдром корректи-
руется и, тем самым, устраняется влияние ошибки на последующие
шаги декодирования.

Принятое из канала
^ Выходной
слово
регистр


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

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




Логическая схема


Р и с . 3.24. Декодер Меггитта для укороченного (7,4)-кода
Хэмминга с предварительным умножением на
2
d(X) = X + X.
208 Глава 3. Циклические коды,
v


Таблица 3.11. Вычисление- синдрома неискаженного приня-
того слова п = (0,1,1,0,1,0).

Такт do d\ so
di Si S-2

0 0 0 0 0 0 При поступлении старшего разряда в
d\ и с?2 регистр синдрома обнуляется
1 1
1 0
0 0
1 1
2 0 0
0
1 1 1 1
3 1
1 1 1
4 1 0
0 0 0 0
5 0
0
6 0 0 Синдром указывает на отсутствие
ошибки


Таблица 3.12. Вычисление синдрома неискаженного приня-
того слова ri = (0,1,1,0,1,1).

Такт do so
di Si S2

0 1 1 0 0 0 При поступлении старшего разряда в
-
di и di регистр синдрома обнуляется

r
1
1 1 0 1
-
1
2 0
0 0 0
-
3 1 1 0 1 G
-
4 1 1 0 1 0
-
-
5 0 0 .1
0 0
1
0
6 - - - 0 Синдром указывает на ошибку в
старшем разряде




Проверим работу декодера на трех примерах. Пусть кодовое сло-
во ri = (0,1,1,0,1,0) (см. табл. 3.9) принято без ошибок. После-
довательность состояний регистра синдрома приведена в табл. 3.11.
После окончания загрузки слова ri в буфферный регистр, в нижнем
регистре также заканчивается вычисление его синдрома. В данном
случае синдром оказывается нулевым.
Теперь в старший разряд слова ri внесем одну ошибку и получим
вектор гг = (0,1,1,0,1,1). После загрузки слова гг в буфферный
регистр, его синдром равен s'2 = (0,0,1) (см. табл. 3.12). Согласно
алгоритму декодирования, такой синдром указывает на ошибку в
209J
3.13. Пример применения: ATM

Таблица 3.13. Вычисление синдрома искаженного принятого
слова гз = (0,1,0,0,1,0)-

Такт do di so Si «2

0 0 0 0 0 0 При поступлении старшего разряда в
di и е 2 регистр синдрома обнуляется
<
1 1 0 0 0
0
2 0 0 1 1
0 0
3 1 1 1
1 1
4 1 1
0
1
5 0 0. 1 1
1
6 - -. 0 1 Синдром указывает на наличие
ошибки




старшем разряде слова Г2-
И, наконец, рассмотрим декодирование принятого слова с ошиб-
кой в третьей компоненте: гз = (0,1,0,0,1,0). Синдром принятого
слова гз равен s 3 = (1,0,1) (см. табл. 3.13). Это означает, что в при-
нятом слове имеется ошибка, но она произошла не в старшем раз-
ряде, поэтому продолжим процедуру вычисления синдромов теперь
уже для сдвигов слова Гз (см. табл. 3.14).
Эта процедура продолжается до тех пор, пока ошибочная ком-
понента гз не займет место старшего разряда. После этого синдром
принимает значение s 3 = (0,0,1) и происходит исправление ошиб-
ки и коррекция синдрома. Далее декодирование происходит уже с
нулевым синдромом, то есть после исправления ошибки в третьей
компоненте мы получили слово (6,3)-кода.


3.13. Пример применения: ATM
Одним из примерив применения CRC кодов является передача дан-
ных но технологии ATM (Assynchronous Transfer Mode - Асинхрон-
ный режим передачи).
Подход, реализованный в технологии ATM, состоит в представ-
лении потока данных от каждого канала любой природы пакетами
фиксированной длины в 53 байта вместе с небольшим заголовком в
5 байт, из которых 3 байта отводятся под номер виртуального соеди-
нения, уникального в пределах всей сети ATM, а остальные 48 байт
^210 Глава З. Циклические коды

Таблица 3.14. Декодирование искаженного принятого слова
г 3 = (0,1,0,0,1,0) после вычисления синдро-
ма.

Такт Принятое so Коментарий
Декодирование*;
Si S2

слово слово
10
0 0 10
1
1 1 0 01
2 0 1
0 00
0
3 0 0 11 Ошибка в старшем разря-
де исправляется и синдром
модифицируется
1
4 0 0 01
0 Однократная ошибка была
5 0 0 00
исправлена




могут содержать либо 6 замеров оцифрованного голоса либо 6 байт
данных. Пакеты ATM называются ячейками - cell. Формат такой
ячейки представлен на рис. 3.25.

1 Байты 5 6 5.'
Ifiinwm Ц Данные пакета
1
--—˜
ЙБит
45
VPI
1 GFC
VCI
2 VPI
3 VCI
CLP

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

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

ОГЛАВЛЕНИЕ

Следующая >>