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

ОЮЗ СОВЕТСНИХ ОЦИАЛИСТИЧЕСНИРЕСПУБЛИН 19) 01)(51) 4 Н 03 М 13/00 к ИЯ 1 16,Ф 2,бобщенны1976,3.41,ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ОПИСАНИЕ ИЗОБР АВТОРСКОМУ СВИДЕТЕЛЬСТВ(54) УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯКОДОВ РИДА-СОЛОМОНА(57) Изобретение относится к вычислительной технике. Его использованиев аппаратуре обработки и передачи цифровой информации позволяет повысить быстродействие устройства. Устройство для декодирования кодов РидаСоломона содержит входной блок 1,буферный накопитель 2, блок 3 вычисления многочлена обобщенных проверок,блок 6 вычисления многочлена локаторов ошибок, блок 7 решения ключевогоуравнения, блок 8 коррекции и блок 9сумматоров, Введение входного генератора 4 элементов поля Галуа и входного перемножителя 5, а также соответствующее выполнение блока 3 обеспечивает параллельную обработку всех символов кодового слова, которая заканчивается в такте приема последнегосимвола. 2 ил.1309317 1Изобретение относится к вычислительной технике и может быть использовано в аппаратуре обработки и передачи цифровой информации.Целью изобретения является повыше 5 ние быстродействия устройства.На фиг. 1 представлена блок-схема устройства для декодирования кодов Рида-Соломона; на фиг. 2 - функциональная схема одной секции блока вычисления многочлена обобщенных проверок.Устройство для декодирования кодов Рида-Соломона содержит входной блок 1, буферный накопитель 2, блок 3 вычисления многочлена обобщенных проверок (ВМОП), генератор 4 элементов поля Галуа СР(2 с), перемножитель 5, блок 6 вычисления многочлена локаторов стираний (ВМЛС), блок 2 О 7 решения ключевого уравнения (РКУ), блок 8 коррекции и блок 9 сумматоров.Блок 3 вычисления многочлена обобщенных проверок выполнен на ис одинаковых секциях, где п - общее число 25 символов слова в коде Рида-Соломона, к - число его информационных символов. Каждая секция имеет (фиг. 2) первый перемножитель 10, первый сумматор 11, регистр 12, умножитель 13 на константу, второй сумматор 14, второй перемножитель 15, третий и четвертый сумматоры 16 и 17, третий перемножитель 18, генератор 19 элементов поля Галуа СР(2").35Константой, на которую осуществляет умножение умножитель 13, является для Б-й секции Б-й элемент ВЗ поля Галуа.Блоки 1,2,6-9 выполнены так же, 40 как и известные. Кроме того, устройство имеет входы 20 и выходы 21.Все перемножители и сумматоры являются схемами комбинационного типа и не синхронизируются. 45Регистр 12 выполнен на Э-триггерах и синхронизируется тактовой частотой сопровождающей входные символы. Генераторы 4 и 19 элементов поля Галуа представляют собой сдвиговые регистры с обратной связью. Разрядность сдвиговых регистров, как и разрядность перемножителей, сумматоров.и регистров равна а, причем а и и связаны соотношением и = 2 - 1.С(55Генератор тактируется той же частотой, что и регистр 12 секции блока 3 вычисления многочлена обобщенных проверок. 2Устройство для декодирования кодов Рида-Соломона работает следующимобразом.а-разрядные символы (и = 2 - 1)с входов 20 поступают на входной блок1, который передает символы, принадлежащие алфавиту СР(2 ), на вход накопителя 2, а символы стирания заменяются нулем и также передаются навход буферного накопителя 2, Кромеэтого, блок 1 генерирует локаторыстираний, которые являются элементами поля Галуа СР(2) и номерами поступивших символов стираний. Отсчетведется от максимального элемента кединичному элементу, так как кодовыймногочлен поступает на входы 20 старшими коэффициентами вперед,Покаторы стираний поступают в блок6 вычисления локаторов стираний ина перемножитель 5.Блок 6 на основе поступающих нанего локаторов стираний хе, е = 1,1,где 1 - число стираний, вычисляетмногочлен стираний Б (г)"- по формуле й ( г)= П (1+х," г) =1+ .К 1 г, -,-1 где 6 з " - Б-й коэффициент многочлена (Б = 1,с 1) .Коэффициенты многочлена локаторов стираний, формирующиеся в блоке 6, поступают в блок 3 вычисления многочлена обобщенных проверок и в блок 8 коррекции, причем в блоке 3 используются все промежуточные значения коэффициентов С ,"(=1,п; Б=1,4),Iполучаемые в каждом -м такте, а в блоке 8 используются только последниезначения, т.е. б (Б = 1 с 1)Перемножитель 5 перемножает элементы поля СР(2 ), вырабатываемые геО(нератором 4 и локаторы стираний блока 1. Произведение подается в блок 3.Блок 3 на основе входных символов из блока 1 произведения с перемножителя 5 и промежуточных значений коэффициентов многочлена локаторов стираний из,блока 6 вычисляет значения коэффициентов многочлена обобщенных проверок. На каждую Б-ю секцию блока 3 (фиг. 2) поступают следующие сигналы: й 1 - входной символ из блока 1Э х Я - произведение из перемножителяе5, Р. - Б-й элемент поля Галуа, константа для каждой секции (в умножителе 13), с 1 1 . - значения, получаемые из предыдущей Бсекции блока3 130933,б 5- промежуточные значения 8-1 -го коэффициента многочлена локаторовстираний, поступающие из блока 6.Каждая секция блока 3 вычислениямногочлена обобщенных проверок вычисляет значения коэффициента многочлена обобщенных проверок по формуле5.1Ю5-2+хй (Т . 8 +а + а; ,Уб 81)11:Л 1На третий умножитель 18 подаетсяпромежуточное значение коэффициентамногочлена локаторов стираний 6 . 15и элемент поля Галуа ю 1 с генератора 19, Результат умножения складывается со значением 2 предыдущей сек 5,1ции и подается на вход сумматора 1 6,где складывается с единичной конс т ант ой, и на вход 12 следующей секции .Результат сложения умножается на в тором и ер емножител е 1 5 на входной символ Й; и подается на вход второго сумма тора 1 4 . Предыдущее значение Т 5 ;коэффициента многочлена обобщенныхпроверок, хранимое в регистре 12, умножается на константу 8 на умножителе 13 и подается на другой вход второго сумматора 14. Полученное на вы- ЗОходе второго сумматора 14 значениеЧ 5передается на первый сумматор 11.,Значение о из предыдущей секции5,1умножается на первом умножителе 10на значение хй , одинаковое для всех 35фсекций, и подается на другой входпервого сумматора 11, выход которогоподается на вход регистра 12, запоминающего значение Тз;+ в следующемтакте. В самой первой секциина вход первого перемножителя 10вместо отсутствующего сигнала ц 5,подается "1", а вместо отсутствующихсигналов 5 ,- "0",51,1 345Таким образом, блоки 1-6 заканчивают обработку одновременно с приемом последнего символа кодового слова. Для работы блоков 7, 8 нужны дополнительные такты работы декодера.Число дополнительных тактов зависитот корректирующей способности конкретного кода.Блок 7 на основе поступающих нанего коэффициентовмногочлена Тз,Б =4+ Р,д обобщенных проверок, решает55ключевое уравнение17 где д Формула изобретения Устройство для декодирования кодов Рида-Соломона, содержащее входной ,блок, входы которого являются входами устройства, первые выходы входного блока подключены к соответствующим входам буферного накопителя, выходы которого соединены с первыми входами блока сумматоров, блок решения ключевого уравнения, выходы которого подключены к первым входам блока коррекции, вторые выходы входного блока соединены с входами блока вычисления многочлена локаторов стираний, выходы которого подключены к вторым входам блока коррекции, выходы которого подключены к вторым входам бло 4- число корректирующих символов кода.Результатом решения является многачлен локаторов ошибок 1(г) и многочлен 11 (г) .Блок 8 на основе коэффициентов многочленов Т(г), 1 (г), Й (г), 11(г),поступающих с блоков 3, 6, 7, вычис 1ляет значения поправок У;, суммируемыхв блоке 9 с задержанными в накопителе2 символами. Исправленные символы подаются с блока 9 на выходы 21.Таким образом, в устройстве декодирования кода Рида-Соломона достигается увеличение быстродействия благодаря тому, что значения коэффициентовмногочлена обобщенных проверок наоснове промежуточных значений коэффициентов многочлена локаторов стираний и символов кодового слова вычисляются параллельно с вычислением многочлена локаторов стираний, формируемого в процессе приема кодового слова.Кроме того, при перемножении многочленов дополнительно экономится истактов работы,Сложность блока 3 вычисления многочлена обобщенных проверок растет пропорционально первой степени п-Е, ане квадрату, как в известном устройстве, так что для больших величин и - 1 спредлагаемая структура блока 3 экономичнее, чем известная. Еще однимпреимуществом можно считать отсутствие специальной схемы синхронизации,применяемой в известном устройстведля перемножения многочленов, так каксинхронизация обеспечивается тактовой частотой приема входных символов,1309317 гГ ЧИИПИ Заказ 1804/56 Тираж 902 Подписн Произв.-полигр. пр-тие, г. Ужгород роектная, 4 ка сумматоров, выходы которого являются выходами устройства, блок вычисления многочлена обобщенных проверок, состоящий из и-К секций (л - общее число символов входного кодового сло ва, К - число его информационных символов), каждая из которых содержит последовательно соединенные первый сумматор, регистр и умножитель на константу, шину логического нуля и шину логической единицы, о т л м ч а ю - щ е е с я тем, что, с целью повышения быстродействия устройства, в него введены генератор элементов поля Галуа и перемножитель, в каждую секцию бло 15 ка вычисления многочлена обобщенных проверок введены второй - четвертый сумматоры, первый - третий перемножители и генератор элементов поля Галуа выходы которого соединены с первыми входами третьего перемножителя, выходы которого подключены к первым входам четвертого сумматора, выходы которого подклчючены к первым входам третьего сумматора данной секции и25 к вторым входам четвертого сумматора последующей секции, выходы первого перемножителя соединены с первыми входами первого сумматора, выходы третьего сумматора подключены к первым входам второго перемножителя, выходы которого и выходы умножителя на константу соединены с первыми ивторыми входами второго сумматора, выходы которого подключены к вторымвходам первого сумматора данной секции и к первым входам первого перемножителя последующей секции, первыевходы первого перемножителя первойсекции и вторые взводы третьих сумматоров всех секций объединены и подключены к шине логической единицы,вторые входы четвертого сумматорапервой секции соединены с шиной логического нуля, вторые входы вторых перемножителей всех секций и вторыевходы третьих перемножителей всех секций соответственно объединены и подключены соответственно к первым выходам входного блока и к выходам блокавычисления многочлена локаторов ошибок, выходы второго и четвертого сумматоров последней секции подключенык входам блока решения ключевогоуравнения и третьим входам блока коррекции, выходы генератора элементовполя Галуа соединены с первыми входами перемножителя, вторые входы которого подключены к соответствующимвторым выходам входного блока, выходыперемножителя подключены к вторымвходам первых перемножителей всехсекций блока вычисления многочленаобобщенных проверок,