7.7. Реализация декодеров для двоичных БЧХ-кодов

Как уже отмечалось в разд. 7.2, декодер для двоичного БЧХ-кода может быть сконструирован по общему принципу разд. 5.5 (рис. 5.14). Остановимся сейчас на макете устройства центрального GF-оператора для конструкции рис. 5.14. Он состоит из одного главного арифметического и управляющего блока и t + i отдельных вспомогательных

блоков. Команды на входы вспомогательных блоков подаются непосредственно с блока управления. Главный блок посылает на все вспомогательные блоки идентичные команды. Все вспомогательные блоки одинаковы. Каждый из них содержит пять регистров, а также аппаратуру для умножения двух из них и хранения результата во вспомогательном накопителе. Все вспомогательные накопители

(( + 2)/

- -* вспомогательный блок t-1

Вспомогательный (Хлок t

-*ваютгатель--* ный блок 2

вспомогательный блок 1

* вспомогшаель --*ный блок Г -

ывный арифмвти ческий и управляющий блок

Р и с. 7.3. Общий вид Gf-оператора для декодера двоичного БЧХ-кода.

связаны С главным сумматором, выход которого поступает в главный блок. Слова могут передаваться только из каждого вспомогательного блока в соответствующий регистр соседнего вспомогательного блока. Аппаратура, с помощью которой главный блок может передавать данные в любой из вспомогательных блоков, здесь не нужна. Главный арифметический блок может вычислять мультипликативные обратные, но ни один из вспомогательных блоков этого не делает.

Пунктирные линии на рис. 7.3 показывают, что как только из канала связи поступает последний символ входного слова, остатки /•1) {х), г() {х), . . ., Н) (х) перемещаются из регистров, расположенных слева на рис. 5.14, в соответствующие вспомогательные блоки. После этого вспомогательный блок, содержащий остаток г() (х), с помощью регистра, умножающего на а, вычисляет

пока он, наконец, не накопит степенную симметрическую функцию

до тех пор,

Для иллюстрации алгоритма 7.64 рассмотрим следующий пример.

7.68. Пример. Рассмотрим двоичный БЧХ-код с блоковой длиной 31, исправляющий три ошибки. Будем полагать, что элементы поля совпадают с многочленами от а степени <5, где

„5 + «2 + 1 = 0.

Таблицы логарифмов и антилогарифмов для этого поля приведены в приложении А. Предположим, что = 11101 = а*, = = 10000 = а*, 5 = 00010 = а\

1 + 5 = 1 + a"z + az + + az* + az + ah + . .., o(0) = 1, xC) = 1, (1 + S) oC) = 1 + a"z mod z

a(2) = 1 + a"z, t<2) = a"z, (1 + 5) o(2) = 1 + (a* + all) 23 mod z*,

a* =10000 = 00111

10111 = a2 = a-5,

o(*) = 1 + a" z + aV, t(*) = az + az, (1 + S) o(*) s 1 + aV + (a + a» + a") z mod z«,

a = 00010 «8 = 01101 a" = 11011

10100 = a,

(j(6) = 1 4- ai*z + Oz + aV, t(«) = az + az + aV. Эти вычисления можно подытожить следующим образом:

sh = г(*) (а*). Если все вспомогательные блоки работают одновременно, то время, необходимое для вычисления степенрых симметрических функций si, iSai . . ., sf, п т -1 раз больше времен, инеоб-ходимого для реализации умножения в поле Галуа. Аналогичным образом во вспомогательных блоках вычисляется и вторая половина степенных симметрических функций st+i, st+2, . . st-i- Все необходимые величины sj вычисляются, таким образом, в соответствующих вспомогательных регистрах, как показано на рис. 7.4, и главный блок управления может приступать к реализации алгоритмов 7.64 или 7.4.

Каждый шаг алгоритмов 7.4 или 7.64 может быть выполнен с помощью изображенного на рис. 7.3 вычислительного устройства. На рис. 7.4 показано состояние вспомогательных регистров на типичном шаге алгоритма. Четыре левых регистра нулевого вспомогательного блока содержат sk+i--2, "a+i, 1 и 0; четыре левых регистра первого вспомогательного блока содержат su+t+i, "ft, и т*"). Затем в каждом вспомогательном блоке вычисляется произведение его второго и третьего регистров, которое записывается в крайний правый регистр. Сумма всех вспомогательных правых регистров накапливается в главном накопителе. Эта сумма определяет величину AJ\ После этого содержимое регистров, соответствующих на рис. 7.5 столбцу т, сдвигается вверх в соответствующие регистры соседних блоков. Величина Aj перемещается в регистр умножителя главного блока. После этого на каждый вспомогательный блок подается команда умножения содержимого регистра т на содержимое главного умножителя. К результату прибавляется содержимое регистра о и, таким образом, формируются коэффициенты многочлена

Затем в зависимости от того, будет ли Ai = О или Af > " , главное управляющее устройство сдвигает или не сдвигает многочлен а") из столбца а в столбец т. Далее коэффициенты а("+) переводятся в столбец т. Многочлен, записанный в столбце т и представляющий собой о<") или т(>, используется для вычисления многочлена т(+), который записывается затем в столбец т. Главное управляющее устройство вычисляет величину D (к 4-1), сдвигает столбцы s вверх, и начинается следующая итерация алгоритма.

Когда алгоритмическое вычисление многочлена ошибок о() закончено, он переводится из вспомогательных регистров в оператор Ченя, а вычислительное устройство рис. 7.3 подготовлено к декодированию следующего полученного слова.

Декодер, блок-схема которого описывается рисунками 5.14 и 7.3, достаточно легко реализуем для БЧХ-кодов с даже сравнительно большой длиной. Вобщем случае стоимость декодера для двоичного БЧХ-кода с блоковой, длиной = 2™ - 1, исправляющего кpaт-

спомогательный регистр 3 ост)шатт,ный. кгистрг

вспомогательный, гистр 1 вспомогательный, регистр о

P и с. 7.4. Состояние вспомогательных регпстров на начальном шаге алгоритмов

Рис. 7.5. Состояния вспомогательных регистров при вычислении

исе конфигурации из не более чем * ошибок и все пакеты из г + 1 последовательных ошибок, не содержащих последней позиции. Для каких значений п л t добавление позиции с общей проверкой на четность позволяет исправлять дополнительно пакеты длины f + 1?

7.4. Пусть 1 + iS (г) - выходная последовательность двоичного регистра с обратной связью а (z), начальное положение которого совпадает с ш (z). Используя алгоритм 7.4, найти многочлены о (г) и ш (z) наименьшей степени для выписанных ниже последовательностей 1 + 5 (z). В каких случаях ответ единствен? В каких случаях применим алгоритм 7.64?

(a) 1 + 0.Z -h l-z + l.z3 + O-z* + O.z + l.z6 + O.z + O-zS + 0.z» + + 1 zo + . . . = 10110010001 . . .,

(b) 10001100101 . . .,

(c) 11000000101 . . .,

(d) 11101001110 ....

7.5. Предполагая, что каждая из последовательностей задачи 7.4 порождается кратчайшим регистром с обратной связью, выписать следующие 5 символов для каждой из последовательностей.

7.6 (Д э й к и н [I960]). Какая доля из qm+n-i церсимметричных матриц над GF (q) имеет ранг, равный г? Указание. См. разд. 7.5.

mouZZZTr.T матрицей называется матрица, диагоналы1ые миноры >рои удовлетворяют условию j..i всякий раз, как только J + / =

которой = к + L

Задачи

Р 7.1. Для функций CT<2ft) и T(2fe) в алгоритме 7.64 показать, что a<2fe) тЬ) - = z> + нечетная функция от z.

7.2. Рассмотрим двоичный БЧХ-код с блоковой длиной 31, исправляющий тройные ошибки. Предположим, что Si = 01010 = а, S3 - ОНИ = а, 5 = 00001 = а». Показать, что а<б> = 1 + az + ah + a"z3.

7.3 (Гр осе [1963]). Показать, что расширенный исправляющий i-кратныв ошибки двоичный БЧХ-код, образованный из циклического БЧХ-кода дописы-] ванием в конце кодовых слов общей проверки на четность, позволяет исправля

ные ошибки, может быть выражена в виде Am + Вп + Cmt, где А, В ж С - постоянные, не зависящие от п ж t. Здесь Am - стоимость главного оператора (содержащего несколько т-ячеечных регистров), Вп - стоимость буфера для запоминания получаемого слова. Величина Cmt включает в себя все другие затраты. Стоимость одного вспомогательного блока, стоимость одного блока оператора Ченя и стоимость регистра, осуществляющего деление входящего слова на один неприводимый множитель порождающего многочлена, пропорциональны т, ж всего имеется t таких составляющих.

Каждый вспомогательный блок устройства рис. 7.3 должен выполнить в среднем t умножений на декодируемый блок, а каждый блок GF-onepaTopa - п умножений на декодируемый блок. Таким образом, время декодирования является вполне приемлемым: на каждую принимаемую позицию оператор Ченя должен выполнить всего одно умножение в поле Галуа и сложение t входов. Другие части декодера могут работать даже еще медленней. Например, если используется 50-наносекундные переключательные устройства, то умножение двух элементов в GF (2") может быть выполнено за 1 микросекунду. Поэтому представляется весьма реальной возможность декодирования любого БЧХ-кода с блоковой длиной 1023, со скоростью декодирования около миллиона двоичных единиц (тысяча блоков) в секунду. Время декодирования не зависит от коли чества t исправляемых ошибок, хотя стоимость декодера возрастает с ростом t.

Конечно, возможны многие модификации и усовершенствования основного устройства, изображенного на рис. 5.14 и 7.3. Можно, например, исключить нулевой вспомогательный блок за счет незначительного усложнения главного блока. Можно, далее, исключить вспомогательные блоки с номерами t а t - i за счет дальнейшего усложнения программы главного блока. Можно также различными] способами интерпретировать вычислительное устройство на рис. 7.3.; Если описывать регистры сдвигов с помощью многочленов, то столб-1 цы на рис. 7.4 и 7.5 дают представления ячеечных регистров сдвига] над GF (2*").