Устройство для декодирования кодом бчх с исправлением тройных ошибок
Устройство может быть использовано в вычислительной технике и электросвязи на приемной стороне систем связи для кодирования двоичных кодов. В устройство декодирования, содержащее блок вычисления остатков, соединенный с блоком вычисления коэффициентов полинома, который содержит регистр-накопитель, адресный регистр, ПЗУ констант и логарифмов и ОЗУ, а также корректор ошибок, осуществляющий процедуру Ченя с целью коррекции трех и менее ошибок во входной последовательности, для увеличения быстродействия и снижения аппаратурных затрат вводятся матричные схемы получения синдромов и определенных величин для решения полинома, что дает возможность исключить ПЗУ и ОЗУ. 3 ил.
Изобретение относится к вычислительной технике, электросвязи и может быть использовано на приемной стороне систем связи для кодирования двоичных кодов.
Известно устройство декодирования с исправлением не более двух ошибок [1] , содержащее схемы формирования синдромов S1 и S3 из входной кодовой последовательности, схемы вычисления S1 и S3, схему суммирования (S1 + S3), схему процедуры Ченя для решения полинома I (х) = S1x2 + S12x + S13 + S3 с целью коррекции двух и менее ошибок во входной кодовой последовательности. Недостатком этого устройства является ограничение числа исправляемых ошибок. Наиболее близким к предлагаемому является устройство декодирования кодом БЧХ [2] с исправлением тройных ошибок, содержащее блок вычисления остатков, соединенный с блоком вычисления коэффициентов 1, 2, 3, содержащий регистр-накопитель, адресный регистр, ПЗУ констант и логарифмов и ОЗУ, и корректор ошибок, осуществляющий процедуру Ченя с целью коррекции трех и менее ошибок во входной кодовой последовательности. Для этого производится решение полинома (х) = 1 + 1 х + 2 х2 + 3 х3, (1) где 1= S1; 2= (S2S3+S5)/(S1S2+S3); 3= S1S2+S3+[(S2S3+S5)S1/(S1S2+S3)] . Если значение полинома для данной позиции входной кодовой последовательности не равно нулю, то вырабатываемый корректором сигнал коррекции имеет низкий уровень. Если значение полинома равно нулю, то сигнал коррекции имеет высокий уровень. Он суммируется по mod2 с сигналом входной кодовой последовательности и изменяет его значение на противоположное. Недостатком данного устройства является необходимость обращения к ПЗУ и ОЗУ в процессе вычисления коэффициентов 1 , 2, 3 в блоке вычисления коэффициентов, что лимитирует скорость декодирования и требует больших аппаратных затрат на реализацию. Цель изобретения - увеличение быстродействия и снижение аппаратных затрат на реализацию устройства декодирования кодом БЧХ с исправлением тройных и менее ошибок за счет исключения операции нахождения логарифмов и антилогарифмов синдромов S1, S2, S3, S5 при вычислении коэффициентов 1, 2 , 3 , что позволяет отказаться от использования ПЗУ и ОЗУ. Цель достигается тем, что в вычислитель коэффициентов вводятся матричные схемы получения синдромов S2, S3 и S5 и величин (S1S2 + S3)S1, S2S3 + S5 и (S1S2 + S3)2 + +S1(S2S3 + S5) для решения полинома *(x) = A + 1* x + 2 * x2 + 3* x3, (2) где A = S1S2 + S3; 1* = (S1S2 + S3)S1; 2*= S2S3 + S5; 3* = (S1S2 + S3)2 + S1(S2S3 + S5), с целью выполнения процедуры Ченя в корректоре ошибок для коррекции тройных и менее ошибок во входной кодовой последовательности. На фиг. 1 представлена структурная электрическая схема предлагаемого устройства. Устройство содержит блок 1 вычисления остатков, состоящий из регистров 2, 3, 4 с обратными связями, каждый из которых входом подключен к входу устройства, а выходом - к входам буферных регистров 5, 6, 7 хранения остатков, соответственно, блок 8 вычисления коэффициентов, состоящий из матричных умножителей 9, 10, 11 получения синдромов S2, S3, S5 из остатков, умножителей 12, 13 получения произведений S1S2 и S2S3 соответственно, сумматоров 14, 15 получения сумм mod2 S1S2 + S3 и S2S3 + S5 соответственно, умножителей 16, 17 для получения (S1S2 + S3)S1 и (S2S3 + S5)S1 соответственно, схемы 18 возведения в квадрат для получения (S1S2 + S3)2, сумматора 19 mod2 для получения (S1S2 + S3)2 + +(S2S3 + S5)S1, блок 20 корректора ошибок, состоящий из буферов 21, 22, 23, 24, 25 хранения синдрома S1 и коэффициентов A, 1*, 2*, 3*соответственно, схемы 26 управления, умножителей 27, 28, 29, 30, сумматоров 31, 33 mod2 и схем И 32, 34. Устройство работает следующим образом. На вход блока 1 вычисления остатков поступает входная кодовая последовательность и осуществляется деление ее на минимальные многочлены кода. Например, для кода БЧХ длиной 255 [3] m1(x) = x8 + x4 + x3 + x2 + 1; m3(x) = x8 + x6 + x5 + x4 + x2 + x + 1; m5(x) = x8 + x7 + x6 + x5 + x4 + x + 1. Блок содержит три регистра сдвига с обратными связями, реализующие деление на минимальные многочлены, а также буферные регистры для хранения остатков R1, R3, R5 (рис. 1.18 из [2] ). Значения остатков R1, R3, R5 поступают в блок 8 вычисления коэффициентов, состоящий из матриц комбинаторной логики, осуществляющих операции умножения и суммирования mod2 в конечном поле Галуа GF(2m). Матричные умножители 9, 10, 11 для получения синдромов S2, S3, S5 из остатков R1, R3, R5 представляют собой матрицы соединенных между собой ячеек, каждая из которых состоит из вентиля И и сумматора mod2. Например, для получения S2 из R1 в поле GF(28) остаток R1 надо умножить на матрицу1 0 0 0 1 0 1 1
12468101214 ____> 0 0 0 0 0 0 0 1
0 1 0 0 1 1 1 0
0 0 0 0 1 0 1 0
0 0 1 0 1 1 0 1
0 0 0 0 0 1 0 0
0 0 0 1 0 1 1 0
0 0 0 0 0 0 1 0 где - примитивный элемент поля GF(28), построенного по минимальному многочлену m1(x) = x8 + x4 + x3 + x2 + 1. Аналогично, для S3 остаток надо умножить на матрицу
1 0 0 0 1 0 1 1
136912151821 ____> 0 0 0 1 0 1 0 0
0 0 0 0 1 1 1 1
0 1 0 1 1 0 1 0
0 0 0 1 0 0 0 1
0 0 0 1 0 1 1 1
0 0 1 0 1 0 0 1
0 0 0 0 1 0 0 0
Для S5 остаток R5 надо умножить на матрицу
1 0 0 0 0 1 0 0
15101520253035 ____> 0 0 0 1 0 1 0 0
0 0 1 1 1 0 0 1
0 0 0 0 0 0 0 1
0 0 1 0 1 0 0 1
0 1 1 1 1 0 1 0
0 0 1 0 0 0 1 0
0 0 0 0 1 0 0 1
Пример получения S2 из R1 показан на фиг. 2а. На фиг. 2б показана функционально-логическая схема ячейки матричного умножителя. Матрица для получения S1 из R1 оказывается единичной, поэтому S1 совпадает с R1. Синдромы S2, S3 с выходов матричных умножителей 9, 10 и синдром S1 с выхода буферного регистра 5 поступают на схемы матричных умножителей элементов поля (МУПЭ) 12 и 13, осуществляющих умножение синдромов S1S2, S2S3 соответственно. МУПЭ умножает два многочлена, являющихся элементами поля GF(2m) по модулю минимального многочлена m1(x) поля, т. е. одновременно производит умножение двух многочленов и деление их на минимальный многочлен поля. Пример реализации МУПЭ для поля GF(28) показан на фиг. 3 и представляет собой регулярную матрицу ячеек, описанных выше, умножающую два элемента поля b и с. С выходов умножителей 11, 12, 13 результаты умножения поступают на входы сумматоров 14 и 15 mod2, осуществляющих поразрядное суммирование по модулю два без переноса S1S2 + S3 и S2S3 + S5 соответственно. С входов регистра 5 и сумматоров сигналы поступают на входы умножителей 16, 17, выполняющих умножение (S1S2 + S3)S1, (S2S3 + S5)S1, и на вход схемы 18, выполняющей возведение в квадрат величины S1S2 + S3. Эти операции производятся аналогично умножению элементов поля с помощью МУЭП, как описано выше. С выходов умножителя 17 и схемы 18 результаты умножения поступают на вход сумматора 19, где осуществляется поразрядное суммирование mod2 (S1S2 + S3)2 + (S2S3 + S5)S1. Вычисленные значения коэффициентов поступают в блок 20 корректора ошибок, где производится процедура Ченя. Значения S1, A, 1*, 2* , 3* записываются в буферные регистры 21-25. Одновременно в схеме 26 управления анализируется значение суммы S1S2 + S3 и вырабатывается выходной сигнал высокого уровня в случае, когда S1S2 + S3 0. Это означает запрещение ложного сигнала коррекции для случаев, когда произошло менее двух ошибок, и решение полинома (2) оказывается ложным. Для декодирования прореженного кода корректор ошибок должен иметь два режима работы. В режиме одиночного шага на каждом такте в умножителе 27 производится умножение 1* на , в режиме двойного шага - на 2. Аналогично в умножителе 28 производится умножение 2* на 2 или 4, в умножителе 29 - умножение 3 * на 3или 6. Одновременно в умножителе 30 осуществляется умножение S1 на или 2 с целью решения полинома
G(х) = 1 + S1x для случаев, когда произошло менее двух ошибок. Умножители 27-30 состоят из регистров с обратными связями и сумматоров mod 2 (рис. 1.24 из [2] ). С выходов умножителей 27, 28, 29 результаты умножения поступают на сумматор 31 mod2 для вычисления значения полинома (2), на выходе которого появляется сигнал высокого уровня в случае, когда *(х) = 0. Он поступает на схему И 32, формирующую выходной сигнал коррекции в случае, когда на ее второй вход подан сигнал высокого уровня со схемы 26 управления. С выходов умножителя 30 результат умножения поступает на вход сумматора 33 вычисления значения полинома (3), на выходе которого появляется сигнал высокого уровня в случае, когда I(х) = 0. Он поступает на вход схемы И 34, формирующей выходной сигнал коррекции в случаях, когда произошло менее двух ошибок, т. е. когда на второй вход схемы И 34 подан со схемы 26 инверсный сигнал высокого уровня. Таким образом, для каждой кодовой последовательности выходным сигналом коррекции является сигнал с выхода схемы И 32 либо схемы И 34. Использование изобретения позволяет уменьшить аппаратные затраты на устройство декодирования кодом БЧХ с исправлением трех ошибок, что означает возможность реализации декодера на БИС. (56) 1. Питерсон У. , Уэлдон Э. Коды, поправляющие ошибки, М. : Мир, 1976. 2. Исследование группового каналообразующего оборудования передачи и приема цифровых сигналов телевидения и звука. Отчет о научно-исследовательской работе. N Гос. ре. 01880008588, ЛОНИИР, Ленинград. 3. Lanes B. A. , Rushforth C. K. Acellular array multiplier for GF(2). IEEE Trans. of Comp. - 1971, N 12, p. 1573-1575.
Формула изобретения
РИСУНКИ
Рисунок 1, Рисунок 2, Рисунок 3