Устройство для декодирования кодов рида-соломона

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК .

„„SU„„1309317 А1 (sg 4 Н 03 М 13/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ

Фиг. 7

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3989198/24-24 (22) 12.12.85 (46) 07.05.87. Бюл. Р 17 (72) А.Т.Матикашвили (53) 681.325(088.8) (56) IEEE Spectrum, 1979 v. 16, Ф 2, р. 35, fig 5.

Блох З.Л., Зяблов В.В. Обобщенные каскадные коды. М.: Связь, 1976, с. 98, 109-121, рис. 3 . 28, 3. 41, 3-43-3,45. (54) УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ

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

130931 7

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

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

На фиг. 1 представлена блок-схема устройства для декодирования кодов

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

Устройство для декодирования кодов Рида-Соломона содержит входной блок 1, буферный накопитель 2, блок

3 вычисления многочлена обобщенных проверок (ВМОП), генератор 4 элементов поля Галуа 6Р(2С ), перемножитель 5, блок 6 вычисления многочлена локаторов стираний (ВМЛС), блок Zp

7 решения ключевого уравнения (РКУ), блок 8 коррекции и блок 9 сумматоров.

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

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

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

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

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

C{

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

Устройство для декодирования кодов Рида-Соломона работает следующим образом. а-разрядные символы (n = 2 — 1) с входов 20 поступают на входной блок

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

Покаторы стираний поступают в блок

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

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

Й(z)* = Г1 (1+х:к.) =1+ . «5 *к, (-.-1 е „з где 6З " — $-й коэффициент многочлена (S = 1,d) .

Коэффициенты многочлена локаторов стираний, формирующиеся в блоке

6, поступают в блок 3 вычисления многочлена обобщенных проверок и в блок

8 коррекции, причем в блоке 3 используются все промежуточные значения коэффициентов 1, "(i=1,п; S=1,d), I получаемые в каждом i-м такте, а в блоке 8 используются только последние значения, т.е. 5»(S = 1,d). !

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

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

3 (фиг. 2) поступают следующие сигналы: di — входной символ из блока 1

Э х* Я вЂ” произведение из перемножителя е

5,  — S-й элемент поля Галуа, константа для каждой секции (в умножителе 13), qs,,., I „. — значения, получаемые из предыдущей S 1 секции блока

3 13093

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

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

5 -1

5-2

+ x+<8 (Т . В +а; + а;,5 .6 .8 )

5-л

На третий умножитель 18 подается промежуточное значение коэффициента многочлена локаторов стираний 6>+ ! и элемент поля Галуа ю с генератора 19. Результат умножения складывается со значением 2 предыдущей секS,1 ции и подается на вход сумматора 16, где складывается с единичной констан-20 той, и на вход 1 „ следующей секции.

Результат сложения умножается на втором перемножителе 15 на входной символ d; и подается на вход второго сумматора 14. Предыдущее значение Т ;

I коэффициента многочлена обобщенных проверок, хранимое в регистре 12, умножается на константу 8 на умножителе 13 и подается на другой вход второго сумматора 14. Полученное на вы- З0 ходе второго сумматора 14 значение

q <« „передается на первый сумматор 11 ., Значение q из предыдущей секции

Б, умножается на первом умножителе 10 на значение х Я, одинаковое для всех 35

4 1 секций, и подается на другой вход первого сумматора 11, выход которого подается на вход регистра 12, запоминающего значение Тз;+„в следующем

I такте. В самой первой секции на вход первого перемножителя 10 вместо отсутствующего сигнала q, подается "1", а вместо отсутствующих сигналов,,. — "0", И ii1 45

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

Число дополнительных тактов зависит от корректирующей способности конкретного кода.

Блок 7 на основе поступающих на него коэффициентов многочлена Тз,S =

4+ Р,d обобщенных проверок, решает

55 ключевое уравнение

Д 1 (1+2., Тзк ) $(z) = y(z)mod z

6=4+1

17 где d

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

Устройство для декодирования кодов

Рида-Соломона, содержащее входной

:блок, входы которого являются входами устройства, первые выходы входного блока подключены к соответствующим входам буферного накопителя, выходы которого соединены с первыми входами блока сумматоров, блок решения ключевого уравнения, выходы которого подключены к первым входам блока коррекции, вторые выходы входного блока соединены с входами блока вычисления многочлена локаторов стираний, выходы которого подключены к вторым входам блока коррекции, выходы которого подключены к вторым входам бло4 — число корректирующих символов кода.

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

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

2 символами. Исправленные символы подаются с блока 9 на выходы 21.

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

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

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

1309317

Риг 2

2ЧИИПИ Заказ 1804/56 Тираж 902

Подписное

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

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