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

1860 СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК о 17 03 0,13 02 ИСАНИЕ ИЗОБРЕТЕНИЯ титутВ,В.Гвоэ 06 Р 11/10,(56) Патент США 1 Ф 4 опублик. 1986,Авторское свид М 1571773,.кл. Н 03 (54) УСТРОЙСТВО СИНДРОМОВ КОД 84686 тельство СССРМ 13/00, 1988,ДЛЯ ВЫЧИСЛЕНИРИДА - СОЛОМОНА пециализистройствам й памяти, и темах помер к ОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(53) 681.326(088.8) Изобретение относится к вычислительной технике, а именно к сованным вычислительным уоррекции ошибок во внешнеможет быть использовано в сисхоустойчивого кодирования.Известно многофункциональное устройство, содержащее набор регистров, двойной набор блоков умножения на постоянные коэффициенты, многовходовый блок суммирования и мультиплексоры, которое позволяет вычислять синдромы в первом этапе декодирования или значения многочленов локаторов ошибок в третьем этапе декодирования помехоустойчивого кода Рида-Соломона.К недостаткам данного устройства относятся неэффективное использование оборудования в третьем этапе декодирования при вычислении локаторов ошибок, так как при этом не используются около 50;ь регистров и блоков умножения на постоянные коэффициенты, а также отсутствие оперативного аппаратного контроля.(57) Изобретение относится к вычислительной технике. Его использование в системах помехоустойчивого кодирования и системах коррекции ошибок во внешней памяти позволяет повысить информативность устройства за счет параллельного вычисления синдромов, значений многочленов ошибок и их локаторов, а также повысить достоверность контроля устройства, Эта цель Достигается благодаря введению дополнительных блоков, что обеспечивает более полное использование остальных олоков устройства, а также их потактовый контроль.2 ил. Наиболее близким к изобретению является устройство, содержащее набор регистров, набор блоков умножения на постоянные коэффициенты. набор блоков сумматоров по модулю два, двойной набор блоков свертки по модулю два, набор блоков соединений, три сумматора и два триггера, (ЛНедостаток устройства - невозмож- д ность его использования в третьем этапе декодирования для вычисления значений многочлена ошибок,Цель изобретения - повышение информа- Сф тивности устройства за счет параллельного вычисления синдромов, значений многочленов ошибок и их локаторов и повышение до- в стоверности контроля устройства,Поставленная цель достигается тем, что в устройство, содержащее первый - (2 Ц-й регистры (Е - количество исправляемых ошибок кодом Рида-Соломона), первый (2 Ц-й блоки сумматоров по модулю два, первый - (2 Ц-й блоки умножения на постоянные коэффициенты, первый - (2 Ц-й соедините20 30 35 информационные входы которых подключены к выходам одноименных регистров, уп 50 55 ли, первый и второй сумматоры по модулю два, первый и второй триггеры (2.+2)й блок свертки по модулю два, тактовые входы первого и второго триггеров объединены с тактовыми входами первого - (2 Ц-го регистров и являются тактовым входом устройства, входы обнуления всех регистров объединены и являютсяпервым установочным входом устройства, входы обнуления триггеров обьединены и-являются вторым установочным входом устройства, выходы каждого из первого - (2 С)1 о регистров подключены ко входам одноименных блока умножения на постоянный коэффициент и соединителя, выходы которого соединены с входами одноименного блока свертки по модулю два, выходы первого - (21 )-го блоков умножения на постоянный коэффициент подключены к первым входам одноименных блоков сумматоров по модулю два, вторые входы которых и входы (21+1)-го блока свертки по модулю два соответственно объединены и являются информационными входами устройства, выходы блоков сумматоров по модулю два подключены к входам одноименных регистров, (2+2)й блок свертки по модулю двэ, выходы первого - (2+1)-го блоков. свертки по модулю два подключены к соответствующим входам первого сумматора по модулю два, выход которого соединен с информационным входом первого триггера, выход которога подключен к первому входу второго сумматора по модулю два, выход которого соединен с информацйонным входом второго триггера, выход которого является первым выходом устройства, дополнительно введены первый-третий блоки сложения, элемент ИЛИ, счетчик импульсов, блок коммутации и первый - (2)й блоки ключей,равляющие входы которых являются соответственно первым - 2 -цм управляющими входами устройства, управляющие входы всех блоков ключей являются (2+1) ми управляющими входами устройства, выходы всех нечетных и всех четных блоков ключей соединены с соответствующими входами соответственно первого и второго блоков сложения, установочный и счетный входы счетчика импульсов подключены соответственно к второму установочному и тактовому входам устройства, выходы счетчика импульсов соединены с первыми информационными входами блока коммутации, первцй и второй управляющие входы которого являются (2.+2)ым и (2(.+3)ым управляющими входами устройства, выходы первого блока сложения соединены со входами элемента ИЛИ, вторыми информационнц 51015 ми входами блока коммутации и первыми входами третьего блока сложения, выходы которого подключены ко входам (2 Е+2)-го блока свертки по модулю два, выход элемента ИЛИ подключен к управляющему входу счетчика импульсов, выходы второго блока сложения соединены с вторыми входами третьего блока сложения и третьими информационными входами блока коммутации, выходы которого являются вторыми выходами устройства.Информационность устройства повышена за счет применения неиспользуемых в прототипе при выполнении третьего этапа декодирования регистров и блоков умножения на постоянные коэффициенты для выполнения дополнительной функции вычисления значений многочленэ ошибок. Эффективность контроля повышена зэ счет охвата оперативным потактовым контролем сложных многовходовых блоков суммирования, испоьзуемых в третьем этапе декодирования для вычисления значений многочленов ошибок и их локаторов,На фиг. 1 изображена блок-схема устройства для вычисления синдромов кода Рида-Соломона; на фиг. 2 - функциональная схема первого блока сложения,Устройство для вычисления синдромов кода Рида-Соломона (фиг, 1) содержит первый - (2 Ц-й регистры 1,1-1,(2 Ц (1 - возможное количество исправляемых ошибок кодом Рида-Соломона), первый - (2)-й блоки 2,1-2,(21 ) сумматоров по модулю два, первый - (2 )й блоки 3.1-3.(21 ) умножения на постоянные коэффициенты, первый - (2 Ц-й блоки 4,1-4.(21 ) ключей, первый - (21)-й соединители 5.1- 5,(2 ), первый - (21 )-й блоки 6,1-6.(2 ) свертки по модулю два,(2 +1)й блок 6. (2 +1) свертки по модулю 2, первый и второй сумматоры 7, 15 по модулю два, первый, второй и.третий блоки сложения 8, 9, 10, элементы ИЛИ 11, счетчик импульсов 12, (2 +2)й блок 13 свертки по модулю двэ, первый и второй триггеры 14, 16, блок 17 коммутации, На фиг; 1 показан информационный вход 25, тактовый вход 19, первый и второй установочные входы 18, 20, управляющие входы 21,1-21.(2) регистров, управляющие входы 22.1-22,(21 ) блоков ключей, управляющие входы 23, 24 блока коммутации, вйходы 26, 27 устройства,Первый этап декодирования заключается в вычислении синдромов (контрольных сумм) по символам полученного слова,Нахождение синдромов Я ( = 1,г) осуществляется путем вычисления по схеме Горнера значений многочлена полученного слова С(х) в корнях порождающего много- членаЯ = С(а).) =О,г,(2) ое 9 М(х) + с 3 е 9 Рт(х) (г 30 Яз 51 54 . 51+1 Я 5 " 51+2 31 ег Яг Яз Яз 54(4) блока 8, 9 сложения,55 где г - количество корней порождающего многочлена 9(х) кода Рида-Соломона. Вычисление синдромов осуществляется с помощью первого - (2)-го регистров 1.1-1.(23 ) первого - (23 )-го блоков 2.1-2.(2.) сумматоров по модулю два, первого - (2 Ц- го блоков умножения на постоянные коэффициенты.Нахождение значений ошибок У и их локаторов Х 1( = 1 Л) в конечном поле 6 Р(2 ) при декодировании РС-кода сводится к решению системы нелинейных уравненийВХ = Я,=1,2 Р) где 31 - синдромы;т - число ошибок в полученном слове С(х) РС-кода,. Из системы (1) получают систему линейных уравнений для определения коэффициентов ст многочлена локаторов ошибок Й ОдИ 4=33 е,=1,1,3=1 Матрица коэффициентов системы (2) является симметричной ганкелевой матрицей синдромов Зт 51+1 ц 1+2 " 521+1 Существует теорема, что значения 1 ошибок и т их локаторов определяются минорами элементов главных диагоналей определителей Ь = ое 1 Г 1 и 4+1= де 131+1 матриц вида (3) М 1 рр при р = 1 л и, М 1+1,рр при р = 1 д+1,если Ь Ф О, а 6+1 = О, 4+2 = О,.Ь+з = 0 Значения ошибок равны где ее(Х) =Мврр х е , (5) а значения Х 1 локаторов ошибок являютсякорнями многочлена 5 10 15 20 25 1+1Р(х) - )" М 1+1,ррХ(6) р =1 При выборе корней порождающего многочлена 9(х) в виде следующей последовательности степеней примитивного элемента поля 0 Ц 2) = ао, а, а=, сР, .а - оборудование устройства вычисления по схеме Горнера (регистры 1.1-1.(2) и блоки 3,1-3,(2) умножения на постоянные коэффициенты) может быть использовано для последующего одновременного вычисления значений многочленов а 1(а) и Р 1(а ), так как для вычисления первого многочлена по схеме Горнера требуются блоки 3.2, 3,4, 3.6,3.(21.) умножения на нечетные степени примитивного элемента а: а, а, а, , а для второго многочлена - блоки 3,1, 3.3, 3,5, ., 3.(21 ) умножения на четные степени примитивного элемента а; а, сР,а,Причем сумма максимальных степеней указанных многочленов в 1(а 1) и РЕ(а) не должна превышать количества г вычисляемых синдромое ОНа основании этого представляется возможным повысить эффективность использования оборудования устройства в третьем этапе декодирования по сравнению с прОтотипом, Вычисление значений многочлена локаторов ошибок Р 1(х) осуществляется с помощью регистров 1, 1,3,".1.(21-1), блоков 2.1, 2,3, 2.(21-1) сумматоров по модулю два, блоков 3.1, 3,3, ,3.(2 Е) умножения на постоянные коэффициенты, блоков 4,1, 4,3, . 4.(2 Е) ключей и первого блока 8 сложения.Вычисление значений многочлена ошибок в(х) осуществляется с помощью регистров 1.2, 1,4,1,(2), блоков 2,2, 2,4, , 2.(23) сумматоров по модулю два, блоков 3,2, 3,4, , 3.(2 ) умножения на постоянные коэффициенты, блоков 4.2, 4,4, , 4.(21) ключей и второго блока 9 сложения.В соответствии с предложенным повышением информационности устройства для вычисления синдромов в него вводятся два В то же время известная схема аппаратного контроля не может охватить контролем указанные блоки 8,9 сложения, Для охвата оперативным контролем блоков 8 и 9 сложения введен дополнительный блок 10 сложения и блок 13 свертки по модулю два,1751860 Принцип аппаратного контроля устройства для вычисления синдромов основан нэ методе предсказания следующего состояния содержимых регистров 1,1-1.(2 Ц по четности, зная алгебраические правила 5 функционирования схемы Горнера для вычисления значений многочленов в корнях порождающего многочлена РС-кода. В. третьем этапе декодирования содержимое регистров 1,1, 1.2, , 1.(2 -1), 1,(2) в 1-ом 10 такте обозначим соответственно В 1), В 2 ),0)- ВЫ, В)гОпределим содержимое регистров 1,1, 1,2, , 1.(2 Е), 1,(21.) в (+1)-ом такте по ихсодержимому в -ом такте, зная алгебраиче ские правила функционирования схемы Горнера р,+цр,(+1)=В 2 а 7 Вз(" = Вз а В") . = В)2.Устройство для вычисления синдромов30 кода Рида-Соломона работает следующимобразом,Вычисление синдромов в первом этапедекодирования осуществляется. по схемеГорнера.35 В начале цикла содержимое регистров1,1-1.(2 ) по сигналу, поступающему на установочный вход 20 устанавливается в нулевое состояние. Первый и второй триггеры14,16 по сигналу, поступающему на уста 40 новочный вход 18, устанавливаются в нулевое состояние, Каждый цикл работысостоит иэ и тактов, где и - количествосимволов в кодовом слове РС-кода, На всеуправляющие входы блоков ключей 22.145 22,(2) и управляющие входы регистров21.1-21,(2) подается логическая единица,В результате сдвига щ-разрядных словс входов на выходы всех двухтактных реги 50 строе по тактовым синхросигналам т в схеме организуется параллельное вычислениесиндромов ЯО, 31321 за и тактов,В -ом( =1 п) такте работы устройства на5 информационный вход 25 устройства пост- пает очередной символ кодового слова СС помощью первого - 2(Е)-го блоков 3,13.(21) умножения на постоянные коэффициенты, первого - (2)-го блоков 2.1-2,(2) Р а ч в (+1) вз 0+ )(8)В 2.-1 = (В 2.1гг )ВгР) -), (В 2Р. 1)5Четность. содержимою всех регистров1,1, 1,2,1.(2 -1), 1,(21.) определяется последующей фо рмуле: где сР, а, аг, , аг, сР" - значения корнейпорождающего многочлена кода Рида-Соломона: 9(х) =(х + ао) (х + а) (х + сР) , (х + аг ) (х + аг которые являются элементами конечного поля Галуа ОР(2) характеристики два,Используя систему формул (7), определим свертку по модулю два содержимого регистров 1,1, 1,2, ., 1.(2 -1), 1,(2 ) в (+1)-ом такте ( , - условное обозначение свертки по модулю два двоичных разрядов элементов поля ОЦ 2 .+ Х В 2.1+Вг.( где , - обозначение операции суммирования элементов поля ОГ(2 п), Подставляя в правую часть выражения (9) вместо В их выражения их системы формул (8), пол- учим Левую часть формулы (10) реализуют первый, второй и третий блоки 8,9,10 сложения и. (2 +2)-й блок 13 свертки по модулю два, что позволяет охватить их оперативным контролем, Правую часть . формулы 10) реализуют первый - (2)-й соединители 5,1-5,(2), первый - (2)-й блоки 6.1-6.(2) свертки по модулю,два, первый сумматор 7 по модулю два, первый триггер 14. Проверку равенства осуществляет второй сумматор 15 по модулю два.сумматоров по модулю два выполняется очередной этап вычисления синдромов,Блоки 3,1-3.(21 ) умножения на постоянные коэффициенты реализуют процедуру умножения содержимого соответствующих регистров 1.1-1.(2 Ц на коэффициенты ас, а.сР;, сР".На информационных входах регистров1.1-1.(21) формируется информация о следующем состоянии этихрегистров, исходя из формулы (7), С помощью соединителей 5,1-5.(21) и блоков 6,1-6,(21 ) свертки по мо: дулю два на выходе первого сумматора7 по модулю два формируется сигнал четности следующего состояния содержимого регистров 1.1-1,(21) согласно правой части формулы (10), По тактовому сигналу т, поступающему на тактовый вход 19, сигнал четности с выхода первого сумматора 7 по модулю два запоминается в первом триггере 14, и одновременно информация с входов регистров 1;1-1,(21) переписывается в данные регистры.В следующем (+1)-ом такте с помощью.блоков 4,1-4.(2 ) ключей первого, второго и третьего блоков 8,9,10 сложения на выходе (2.+2)-го блока 13 свертки по модулю два формируется сигнал четности содержимого регистров 1,1-1.(2.) согласно левой части формулы (10), Сформированный с помощью этих блоков сигнал четности сравнивается путем суммирования по модулю два во втором сумматоре 15 по модулю:два с ранее сформированным в 1-ом такте сиг. налом четности, хранящимся в первомтриггере 14.Если данные два сигнала четности различны, то на выходе второго сумматора 15 по модулю два формируется сигнал сбоя, который по окончании (+1)-го такта по тактовому.сигналу т, поступающему на тактовый вход 19, запоминается во втором триггере 16. Одновременно в (1+1)-ом такте формируется с помощью блоков 6,1-6,(21.) свертки по модулю два и первого сумматора 7 по модулю два сигнал четности следующего состояния регистров 1.1-1,(21), который по тактовому сигналу т, поступающему на вход 19 запоминается в первом триггере 14.На информационных входах регистров 1,1- 1.(2 Е) формируется информация о следующем состоянии этих регистров аналогично,как в 1-ом такте и так далее. Сигнал сбоя, если сбой имел место, с выхода второго триггера 16 подается на выход 28 устройства.По истечении и тактов сдвиг информации в регистрах 1,1-1,(2 Е) синхросигналамит прекращается, и в дальнейшем регистры 1,1-1.(2) могут использоваться в качестве памяти с произвольным обращением к любому из регистров, Любой из синдромов может быть считан путем опроса соответствующего регистра одним из блоков 4.1-4.(2)ключей и через блоки 8,9 сложения и блок 17коммутации передан на выход 26 устройства. 10 В дальнейшем во втором этапе декодирования на основании этих значений синдромов вычисляются значения диагональных миноров Мрр и Мс+1,рр в отдельном устрой 15 стве вычисления миноров, которое не касается сущности изобретения и на фиг, 1 непоказано,В третьем этапе декодирования длявычисления значений много, членов Р(а) 20 и в(а), = О,пих коэффициенты М 1 рр иМн 1,рр необходимо записать в регистры1,1-1,(2), В режиме записи на входы 22,122.(2) подается логический нуль, а на одиниз входов 21.1-21.(21) загружаемого регистра - логическая единица., разрешающаяприем в регистр значения соответствующего коэффициента, поступающего на вход30 25 устройства.После загрузки всех значений миноровМ 1 рр и М+1 рр в регистры 1.1-1,(21 ) устройст. во вновь переводится в режим аналогичныйвычислению синдромов, но при нулевыхзначениях входных переменных.на входе25, В начале цикла счетчик импульсов 12 посигналу, поступающему на установочныйвход 18, устанавливается в нулевое состояние,В результате сдвигов информации в регистрах 1.1-1.(21) по тактовым синхросигналам т последавательно вычисляются иобразуются в каждом )-ом такте на выходахпервого и второго блоков 8,9 сложения со 45 ответственнозначения многочленов Р 1(а)и в(а), ) = О,п. Если в каком-либо )-омтакте значения Р(а) = О, счет в счетчикеимпульсов 12 прекращается по управляющему сигналу. образующемуся на выходеэлемента ИЛИ 11,Одновременно прекращается сдвиг информации в регистрах 1,1-1,(21 ) по синхросигналухи с помощью блока 17 коммутациивыводится из устройства вначале номер локатора ошибки), образующийся на выходесчетчика импульсов 12, а затем значениемногочлена сй(а) образующееся на выходевторого блока 9 сложения. Далее вновьпродолжаются сдвиги информации по синхросигналу тдо очередного обнуления значения Р(а 1).Контроль правильности функционирования устройства при вычислении локаторов ошибок и значениймногочлена ошибокв третьем этапе декодирования осуществляется аналогично контролю при"вйчйслении синдромов в первом этапе декодирования,Формула изобретения Устройство для вычисления синдромов Рида - Соломона, содержащее первый и второй триггеры, тактовые входы которых объединены с тактовыми входами первого - 21:го регистров ( - количество ошибок, исправляемых кодом Рида - Соломона) и являются тактовым входом устройства, входы обнуления всех регистров объединены и являются первым установочным входом уст-. ройства, входы обнуления триггеров объединены и являются вторым установочным входом устройства, выходы каждого из первого - 21:го регистров подключены к входам однеименных блока умножения на постоянный коэффициент и соединителя, выходы которого соединены с входами одноименного блока свертки по модулю два, выходы первого - 2-го блоков умножения на постоянный коэффициент подключены к первым входам одноименных блоков сумматоров по модулю два, вторые входы которых и входы (21.+1)-го блока свертки по модулю два соответственно объединены и являются информационными входами устройства, (21.+2)-й блок свертки по модулю два, выходы первого - (2 Е+1)-го блоков свертки по , модулю два подключены к соответствующим входам первого сумматора по модулю два, выход которого соединен с информационным входом первого триггера, выход которого подключен к первому входу второго сумматора по модулю два, выход которого соединен с информационным входом второго триггера, выход которого является пер 30 дами элемента ИЛИ, вторыми информаци 40 10152025 вым выходом устройства, о т л и ч а ю щ е ес я тем, что, с целью повышения информативности устройства за счет параллельного вычисления синдромов, значений многочленов ошибок и их локаторов и повышения достоверности контроля устройства, в неговведены первый - третий блоки сложения,элемент ИЛИ, счетчик импульсов, блок коммутации и первый - 21:й блоки ключей, информационные входы которых подключены к выходам одноименных регистров, управляющие входы которых являются соответственно первым -21:и управляющими входами устройства, управляющие входы блоков ключей являются (21+1)-ми управляющими входами устройства, выходы всех нечетных и всех четных блоков ключей соединены с соответствующими входами соответственно первого и второго блоков сложения, установочный и счетный входысчетчика импульсов подключены соответственно к второму установочному и тактовому входам устройства, выходы счетчика импульсов соединены с первыми информационными входами блока коммутации, первый и второй управляющие входы ко- . торого являются (21.+2)-ым и (21.+3)-ым управляющими входами устройства, выходы первого блока сложения соединены с вхоонными входами блока коммутации и первыми входами третьего блока сложения, выходы которого подключены к входам (21.+2)-го блока свертки по модулю два, выход которого подключен к второму входу второго сумматора по модулю два, выход элемента ИЛИ - к управляющему входу счетчика импульсов, выходы второго блока сложения соединены с вторыми входами третьего блока сложения и третьими информационными входами блока коммутации, выходы, которого являются вторыми выходами устройства,1751860 г выдк дакто Производственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина. 1 ф 5 Ф.7 акаэ 2697 ВНИИПИ Госу оставитель Т. Какуринахред М,Моргентал Корректор М. Демчи Тираж Подписноеенного комитета по изобретениям и открытиям при ГКНТ СССР 13035, Москва, Ж, Раушская наб 4/5