Вернер М. Основы кодирования (2004) (1151882), страница 29
Текст из файла (страница 29)
На последующих тактах в нижнем регистре вычис-ляются синдромы дляе 6 = 4 1 ' = (000 0001),е 0 = ef] = (100 0000),е, = 4 3 ) = (010 0000),е2 = ef] = (001 0000)и т. д. Наиболее благоприятным с точки зрения затрат на модификацию в схеме рис. 3. 22 является синдром s = (0,0,1). Из таблицы3.6 следует, что этот синдром соответствует вектору ошибкие 2 = 4 4 ) = (001 0000),т.е.
ошибке в компоненте гг- Таким образом, для реализации оптимальной процедуры исправления ошибки и коррекции синдрома всхеме рис. 3.22 необходимо предварительно произвести четыре циклических сдвига верхнего и нижнего регистров (при этом верхнийрегистр должен быть модифицирован: в него должны быть добавлендополнительный разряд г% и цепь обратной связи (Прим.
переводчика)).На примере укороченного (6,3)-кода может показаться, что этизатраты не слишком велики, однако, для используемого в сети GSMкода Файера миллион и более сдвигов плюс затраты на модификацию регистра оказываются технически неприемлемыми. Ниже мытеоретически покажем, что дополнительные затраты такого рода отнюдь не. являются необходимыми. После этого мы рассмотрим построение схемы оптимального декодера укороченного (6,3)-кода.Будем искать схему построения декодера укороченного кода, вкоторой технические затраты на исправление ошибки и коррекциюсиндрома были бы минимальными. Так как базовый (п, &)-код является циклическим, эта схема должна обнаруживать и исправлятьошибку в младшем разряде кодового слова укороченного (п—I, к — I)кода. Многочлен такой ошибки имеет виде{Х) = Хп~1-\(3.92)где I - длина укорочения.Постараемся найти линейную операцию, отображающую е(Х) внекоторый вспомогательный многочлен е'(Х), синдром которого прие(Х) = Хп~1~1 был бы равенs'{X) = Xn-k~l.(3.93)3.12.
Укороченные коды 205JПусть такая операция отображает многочлен е(Х) = Хп~х~1 ве'(Х) = Хп~к-1.(3.94)Так как степень многочлена е'(Х) меньше степени д(Х), равенство(3.93) остается справедливым. Заметим, что е'(Х) = Хп~к~1 можнополучить из многочлена е(Х) = Хп~1~1, г-кратным циклическимсдвигом, то есть.е!(Х) = е^{Х),(3.95)i = п - к + I.(3.96)гдеПри этом после / + 1 первых сдвигов е'(Х) = Х°, а после оставшихсяп — к — 1 сдвигов выполняются равенства (3.94) и (3.93).
Постараемся заменить операцию г-кратного циклического сдвига линейнойоперацией умножения многочленов.Из соотношения (3.9) следует, что в нашем случае справедливоравенствоХ*е{Х) = q(X){Xn + 1) + е«(Х),(3.97)где д(Х) - некоторый многочлен, конкретное значение которого непредставляет для нас интереса. Согласно теореме 3.2.5, порождающий многочлен д(Х) делит Хп + 1 без остатка, поэтому можно записать(Хп + 1) = а1(Х)д(Х).(3.98)Применяя алгоритм деления Евклида, сомножитель X* можно представить в видеХ{ = а2(Х)д(Х) + d(X),(3.99)где deg[d(X)] < deg[g(X)}.Подставляя (3.98) и (3.99) в (3.97), имеем+ e«(X).(3.100)е®(Х) = [q{X)ai(X) + а2(Х)е(Х)]д(Х) + d(X)e(X).(3.101)ЫХ)д(Х)+ d(X)]e(X) - q(X)ai(X)g(X)Из (3.100) следуетРавенство (3.101), на первый взгляд, может показаться довольносложным, однако оно сильно упрощается при вычислении синдромов обоих частей равенства.
Следует заметить, что выражение вГлава 3. Циклические кодыквадратных скобках умножено на д(Х) и, следовательно, это произведение не оказывает влияние на синдром в правой части (3.101).Таким образом, мы имеем[d(X)e(X)\mod g{X) = [e{i)(X)}mod g{X) = s'(X).(3.102)Обобщая все вышесказанное, можно сделать следующие выводы:• Ошибка обнаруживается при ее сдвиге в старший разряд кодового слова укороченного (п — l,k — /)-кода и исправляется наследующем такте работы декодера;• В схеме декодера вычисляется синдром вспомогательного многочлена е.\Х) = e(X)d(X).
В этом случае ошибке е(Х) =Xn-1-i соответствует синдром s'(X) = Хп~к~г, который такжекорректируется на следующем такте;• Многочлен d(X) является остатком от деления Хг на д(Х), гдег определяется длиной укорочения I и степенью производящегомногочлена д(Х);• Так как степень многочлена d(X) всегда меньше степени д(Х),схема умножения е(Х) на d{X) может быть реализована с помощью простых сдвигов.Пример: Укороченный (6,3)-код.Рассмотрим построение оптимального, с точки зрения затрат, декодера'укороченного (6,3)-код. Напомним, что этот код образуетсяукорочением базового циклического (7,4)-кода Хэмминга с порождающим многочленом д(Х) = 1 + X + X3.
В этом случае многочленуошибки е(Х) = X5 должен соответствовать синдром вспомогательного многочлена s'(X) = X2. Так как X2 является четырехкратнымциклическим сдвигом многочлена е(Х) = X5, множитель d(X) определяется какd{X) = [X4] mod {X3 + X + 1) = X2 + X,(3.103)и вспомогательный многочлен е'(Х) равен2d(X)e{X) = Х е(Х) + Хе(Х).(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).Принятое из каналасловоТакт0s«0*|0102111341100050106001011,1Р и с . 3.23.
Модифицированный алгоритм вычисления синдрома с предварительным умножением вектораошибки на d(X) = X2 + X.Схема исправления однократной ошибки и коррекции синдромас использованием вспомогательного многочлена е!{Х) приведена нарис. 3.24. По вычисленному синдрому s' = (0,0,1) происходит обнаружение и исправление ошибки. Одновременно синдром корректируется и, тем самым, устраняется влияние ошибки на последующиешаги декодирования.Принятое из каналаслово^ ВыходнойрегистрИсправлениеошибокМодификациясиндромаЛогическая схемаР и с . 3.24. Декодер Меггитта для укороченного (7,4)-кодаХэмминга с предварительным умножением на2d(X) = X + X.v208Глава 3. Циклические коды,Таблица 3.11.
Вычисление- синдрома неискаженного принятого слова п = (0,1,1,0,1,0).Тактdo0d\di00so0Si0S-20При поступлении старшего разряда вd\ и с?2 регистр синдрома обнуляется1110002000113111114111105000000006Синдром указывает на отсутствиеошибкиТаблица 3.12.
Вычисление синдрома неискаженного принятого слова ri = (0,1,1,0,1,1).Тактdodi0-11soSiS2000При поступлении старшего разряда вdi и di регистр синдрома обнуляется0r10100101G11010000. 1--00011-112-03-14-5-6-Синдром указываетстаршем разрядена ошибку вПроверим работу декодера на трех примерах. Пусть кодовое слово 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). Согласноалгоритму декодирования, такой синдром указывает на ошибку в3.13. Пример применения: ATM209JТаблица 3.13. Вычисление синдрома искаженного принятогослова гз = (0,1,0,0,1,0)Тактdo0di00soSi«2000При поступлении старшего разряда вdi и е<2 регистр синдрома обнуляется1100011200030011141110100.111-.10156-Синдромуказываетна наличиеошибкистаршем разряде слова Г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словоSiS2Декодирование*;слово001 01 011100 120010 030001 141000 150000 0КоментарийОшибка в старшем разряде исправляется и синдроммодифицируетсяОднократная ошибка былаисправленамогут содержать либо 6 замеров оцифрованного голоса либо 6 байтданных.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
