Устройство для декодирования кодов Рида-Соломона Советский патент 1987 года по МПК H03M13/05 

113093

Изобретение относится к вычислительной технике и может быть исполь- зовано в аппаратуре обработки и пере- дачи цифровой информации.

Целью изобретения является повышение быстродействия устройства.

На фиг. 1 представлена блок-схема устройства для декодирования кодов Рида-Соломона-, на фиг. 2 - функциональная схема одной секции блока вы- jg числения многочлена обобщенных проверок.

Устройство для декодирования кодов Рида-Соломона содержит входной блок 1, буферный накопитель 2, блок J5 3 вычисления многочлена обобщенных проверок (ВМОП), генератор 4 элеентов поля Галуа GF(2), перемноитель 5, блок 6 вычисления многочлена локаторов стираний (ВМЛС), блок 20 7 решения ключевого уравнения (РКУ), блок 8 коррекции и блок 9 сумматоров.

Блок 3 вычисления многочлена обобенных проверок выполнен на n-k одиаковых секциях, где п - общее число 25 имволов слова в коде Рида-Соломона, - число его информационных симвоов. Каждая секция имеет (фиг. 2) первый перемножитель 10, первый суммаор 11, регистр 12, умножитель 13 на зо константу, второй сумматор 14, втоой перемножитель 15, третий и четвертый сумматоры 16 и 17, третий перемножитель 18, генератор 19 элементов поля Галуа GF(2).

Константой, на которую осуществляет умножение умножитель 13, является для S-й секции S-й элемент В поля Галуа.

Блоки 1,2,6-9 выполнены так же, 0 как и известные. Кроме того, устройство имеет входы 20 и выходы 21.

Все перемножители и сумматоры являются схемами комбинационного типа и не синхронизируются:45

Регистр 12 выполнен на D-триггерах и синхронизируется тактовой частотой сопровождающей входные символы. Генераторы 4 и 19 элементов поля Галуа представляют собой сдвиговые регист- JQ ры с обратной связью. Разрядность сдвиговых регистров, как и разряднсЗсть перемножителей, сумматоров и регистров равна а, причем а и п связаны соотношением п 2 - 1.55

Генератор тактируется той же частотой, что и регистр 12 секции блока 3 вычисления многочлена обобщенных проверок.

35

g

5 0

5 о

0

5

Q 5

5

172

Устройство для декодирования кодов Рида-Соломона работает следующим образом.

а-разрядные символы (п 2 - 1) с входов 20 поступают на входной блок 1, который передает символы, принадлежащие алфавиту GF(2) , на вход накопителя 2, а символы стирания заменяются нулем и также передаются на вход буферного накопителя 2. Кроме этого, блок 1 генерирует локаторы стираний, которые являются элементами поля Галуа CF(2) и номерами поступивших символов стираний. Отсчет ведется от максимального элемента к единичному элементу, так как кодовый многочлен поступает на входы 20 старшими коэффициентами вперед.

Локаторы стираний поступают в блок 6 вычисления локаторов стираний и на перемножитель 5.

Блок 6 на основе поступающих на него локаторов стираний х, е Ij-O, где л) - число стираний, вычисляет многочлен стираний и (z) по формуле

6(z) П ()1+ 21 zS,

fr-1 5 1 5

гдейд - S-й коэффициент многочлена (S 1,d),

Коэффициенты многочлена локаторов стираний, формирующиеся в блоке 6, поступают в блок 3 вычисления многочлена обобщенных проверок и в блок 8 коррекции, причем в блоке 3 используются все промежуточные значения коэффициентов 5 f( ), получаемые в каждом i-м такте, а в блоке 8 используются только последние значения, т.е, (sn(S 1 ,d) .

Перемножитель 5 перемножает элементы поля GF(2), вырабатываемые генератором 4 и локаторы стираний блока 1. Произведение подается в блок 3.

Блок 3 на основе входных символов из блока 1 произведения с перемножителя 5 и промежуточных значений коэффициентов многочлена локаторов стираний из.блока 6 вычисляет значения коэффициентов многочлена обобщенных проверок. На каждую S-ю секцию блока 3 (фиг. 2) поступают следующие сигналы: di - входной символ из блока 1; X Е - произведение из перемножителя 5; Е - S-й элемент поля Галуа, кон- стзгнта для каткдой секции (в умножителе 13), Чд,, g; значения, получаемые из предыдущей S-1 секции блока

313093

3)( промежуточные значения S-1- го коэффициента многочлена локаторов стираний, поступающие из блока 6.

Каждая секция блока 3 вычисления многочлена обобщенных проверок вычис- ляет значения коэффициента многочлена обобщенных проверок по формуле

5--1

, j

,,Ч. Т5;-В -ь а; + а,. 6,-,jB +

5-1г - 0 а, Z:6,-,)

i-1

.

В +а.

На третий умножитель 18 подается промежуточное значение коэффициента многочлена локаторов стираний e.

/(Ч t

и элемент поля Галуа 1 с генератора 19. Результат умножения складывается со значением Igj предьщущей секции и подается на вход сумматора 16, где складывается с единичной константой, и на вход I j. J следующей секции Результат сложения умножается на втором перемножителе 15 на входной символ d и подается на вход второго сумматора 14. Предьщущее значение Tjj коэффициента многочлена обобщенных проверок, хранимое в регистре 12, умножается на константу и на умножителе 13 и подается на другой вход второго сумматора 14. Полученное на вы- ходе второго сумматора 14 значение q д передается на первьй сумматор 11 Значение q - из предьщущей секции умножается на первом умножителе 10 на значение , одинаковое для всех секций, и подается на другой вход первого сумматора 11, выход которого подается на вход регистра 12, запоминающего значение Tj j в следующем такте. В самой первой секции на вход первого перемножителя 10 вместо отсутствующего сигнала q 5 ( подается 1, а вместо отсутствуюп5их

fsi - О.

сигналов 6. .„ - .

Таким образом, блоки 1-6 заканчивают обработку одновременно с приемом последнего символа кодового слова. Для работы блоков 7, 8 нужны дополнительные такты работы декодера. Число дополнительных тактов зависит от корректирующей способности конкретного кода.

Блок 7 на основе поступающих на него коэффициентов многочлена TgjS }+ P,d обобщенных проверок, рещает ключевое уравнение о1-

. d+HlgZ . ) (z) и (z)mod ,

93

0

5

20 . 30.. 35

17 . 4 . где d - число корректируюп1их символов кода.

Результатом решения является многочлен локаторов ошибок d(z) и многочлен l(z) .

Блок 8 на основе коэффициентов многочленов T(z) , d (z) , d.(z), 1,(z) , поступающих с блоков 3, 6, 7, вычисляет значения поправок У , суммируемых в блоке 9 с задержанными в накопителе 2 символами. Исправленные символы подаются , с блока 9 на выходы 21.

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

Кроме того, при перемножении многочленов дополнительно экономится n-k тактов работы.

Сложность блока 3 вычисления многочлена обобщенных проверок растет пропорционально первой степени n-k, а не квадрату, как в известном устройстве, так что для больших величин n-k предлагаемая структура блока 3 экономичнее, чем известная. Еще одним преимуществом можно считать отсутствие специальной схемы синхронизации, применяемой в известном устройстве для перемножения многочленов, так как синхронизация обеспечивается тактовой частотой приема входных символов.

Формула изобретения

«V

Устройство для декодирования кодов Рида-Соломона, содержащее входной :блок, входы которого являются входами устройства, первые выходы входного блока подключены к соответствующим входам буферного накопителя, выходы которого соединены с первыми входами блока сумматоров , блок решения ключевого уравнения, выходы которого подключены к первым входам блока коррекции, вторые выходы входного блока соединены с входами блока вычисления многочлена локаторов стираний, выходы которого подключены к вторым входам блока коррекции, выходы которого подключены к вторым входам блока сумматоров, выходы которого явля- ются выходами устройст ва, блок вычисления многочлена обобщенных проверок, состоящий из n-k секций (п - общее

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

и перемножитель, в каждую секцию бло- входы третьих перемножителей всех сеК ка вьгаисления многочлена обобщенных Ций соответственно объединены и под- проверок введены второй - четвертый ключены соответственно к первым выхо- сумматоры, первый - третий перемножи- Дам входного блока и к выходам блока тели и генератор элементов поля Галуа вычисления многочлена локаторов оши- выходы которого соединены с первыми 20 ок, выходы второго и четвертог о с ум- входами третьего перемножителя, выходы которого подключены к первым

ва, k - число его информационных символов) , каждая из которых содержит последовательно соединенные первый сумматор, регистр и умножитель на константу, шину логического нуля и шину логической единицы, отллчаю- щ е е с я тем, что, с целью повышения быстродействия устройства, в него введены генератор элементов поля Галуа

маторов последней секции подключены к входам блока решения ключевого уравнения и третьим входам блока коррекции, выходы генератора элементов 25 поля Галуа соединены с первыми входами перемножителя, вторые входы которого подключены к соответствующим вторым выходам входного блока, вькоды перемножителя подключены к вторым

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

ходы третьего сумматора подключены к 30 входам первых перемножителей всех первым входам второго -перемножителя, секций блока вычисления многочлена выходы которого и выходы умножителя

обобщенных проверок.

- ск,

13093176

на константу соединены с первыми и вторыми входами второго сумматора, выходы которого подключены к вторым входам первого сумматора данной секвходы третьих перемножителей всех сеК Ций соответственно объединены и под- ключены соответственно к первым выхо- Дам входного блока и к выходам блока вычисления многочлена локаторов оши- ок, выходы второго и четвертог о с ум-

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

входам первых перемно секций блока вычислен

обобщенных проверок.

Изобретение относится к вычислительной технике. Его использование в аппаратуре обработки и передачи го цифровой информации позволяет повысить быстродействие устройства. Устройство для декодирования кодов Рида- Соломона содержит входной блок 1, буферный накопитель 2, блок 3 вычисления многочлена обобщенных проверок, блок 6 вычисления многочле.на локаторов ошибок, блок 7 решения ключевого уравнения, блок 8 коррекции и блок 9 сумматоров. Введение входного генератора 4 элементов поля Галуа и входного перемножителя 5, а также соответствующее выполнение блока 3 обеспечивает параллельную обработку всех символов кодового слова, которая заканчивается в такте приема последнего символа. 2 ил. (Л Т 21 СО О СО СО Фиг.1