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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК Ц 9) 01) М 13/02 ф.1 ъ)п" сПИСАНИЕ ИЗОБРЕТЕНИВТОРСНОМУ СВИДЕТЕЛЬСТВУФсЪс 8)дон 3. Коды,- М.: Мир, 1976,11 7 14 следующем для вычисл бок, и сокращает к исправления двухкр 1,5 раза, где ш - СР (2 ) Галуа. 2 т ия значении ичество тактоных ошибок взмерность полл.,1 ил. ГОСУДАРСТ 8 ЕННЫЙ НОМИТЕТ СССР110 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(54) УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯОШИБОК(57) Изобретение относится к вычислительной технике и может бытьиспользовано при создании устройства, исправляющих ошибки в хранимойили передаваемой по каналам связи информации. Целью изобретения являетсяповышение быстродействия устройства,, Устройство содержит запоминающийблок 1, буферный накопитель 2, блок 3 сумматоров по модулю два, генератор 4 синдромов, накопитель 5 синдромов, вычислитель б элементарных симметрических функций, дешифратор 8ошибок и блок 7 вычисления ошибок,состоящий из элемента И 9, счетчика10 импульсов, четырех регистров 1417, восьми блоков 11-13, 21,26-29постоянной памяти, шести коммутаторов18-20, 30-32, перемножителя 22, двухгрупп 23 и 33 из ш триггеров и двухблоков 24 и 25 оперативной памяти,Введение пяти блоков постоянной памяти, группы из ш триггеров и трехкоммутаторов позволяет реализоватьодновременное определение корней ка- фионического квадратного уравнения ло-каторав, величины, используемой в по- Ц /Изобретение относится к вычислительной технике, и может быть использовано при создании устройств, корректирующих ошибки, возникающие в информационных посылках при их хранении или передаче по каналам связи и предназначено для работы см кодами Гида-Соломона длины и - 2 -1, в каждой кодовой комбинации которого имеется К информационных и и-К проверочных символов, каждый иэ которых содержит ш двоичных разрядов, гдем ш - размерность поля СР (2 ) Галуа. Образующий полином кода для исправления двухкратных ошибок 9(х) =(х+1) (х 4 сЦ (х+ м ) (х+ еГ ), где ое примитивный элемент поля СГ (2 ) Гам луа еЦель изобретения - повышение быст О родействия устройства.На чертеже представлена функциональная схема устройстваУстройство содержит запоминающий блок 1, буферный накопитель 2, блок 25 3 из ш сумматоров по модулю два, гене ратор 4 синдромов, накопитель 5 синдромов, вычислитель 6 элементарных симметричных функций, блок 7 вычисления ошибок и дешифратор 8 ошибок.Ьлок 7 вычисления ошибок состоит из элемента И 9, счетчика О импульсов, блоков 11-13 постоянной памяти, регистров 14-17, коммутаторов 18-20, блока 21 постоянной памяти, перемно 35 жителя 22, группы 23 из ш триггеров, блоков 24 и 25 оперативной памяти, блоков 26-29 постоянной памяти, комму. таторов 30-32 и группы 33 иэ т триггеров. 40Устройство работает следующим образом.В запоминающем блоке 1 с помощью образующего полинома.9(х) записывается закодированная избыточным (п,К) 45 кодом Рида-Соломона кодовая комбинация С(х). При передаче по каналу связи или при считывании с блока 1 на С(х) накладывается вектор ошибок Е(х), в результате чего в буферный накопитель 2 и генератор 4 синдромов поступает в последовательность К(х) =С(х) + Е(х).В генераторе 4 деления К(х) на составные части образующего полинома 9 (х) = (х+1) (х+м) (х+ ое ) (х+ М) получа" ют синдромы Б ,ББ ,Б., которые за" писывают в накопитель 5 синдромов. На выход накопителя 5 подключен де Б+ С,Я = О; Яг+ С,Б= О Б+ С,Я= О;1 = 2 Б+ ЯС+ СгЯ,= О Б + С,Б,+ С,Я,= О. э Последовательность работы вычисли"теля 6 следующая,Если БО, то 1 ь 1 и определяютБ /Бо; Б+ С, Яи Я, С, Б. ЕслиЯ + С,Я,= Я + С,Я = О, то 1 = 1 х Х,=С,; У, = Я, в противном случае -1 ь 2 и вычисляют ч.Последовательность работы блока7 следующая,Локаторы ошибок находят из квадратного уравнения каноническоговида 2г+ г+= О.,(4) где= Сг/С,; ЮС шифратор 8, функционирующий как элемент ИЛИ. Если Б = Б = Б "- Я,то на втором выходе дешифратора 8 появляется сигнал "Нет ошибки" и кодовый блок выдается потребителю путем подачи сигнала "Считывание" на управляющий вход буферного накопителя 2, В противном случае получают остаток от деления, содержащий хотя бы одну 1, тогда на выходе дешифратора 8 появляется сигнал "Ошибка", который дает разрешение для работы вычислителя 6.В вычислителе 6 определяют кратность 1 ошибки и значения Си С элементарных симметрических функций из соотношений1432787 откуда является адресом для блока 29, навходе которого появляется записаннаяпо этому адресу величина 1/С,. Блок 521 памяти подключает с помощью коммутатора 20 выходы блока 29 на входблока 13 памяти. Значение 1/С, явля -ется адресом для блока 13. В результате на выходе блока 13 появляетсязаписанная в нем по этому адресу величина 1/С,. Таким образом, на первых,входах перемножителя 22 появляетсявеличина С ,а на вторых - 1/С,. Од 1новременно блок 21 памяти подключаетчерез коммутатор 30 выход перемножителя 22 на входы блоков 27 и 28 памяти. На этом же такте происходит умножение Сг и 1/С и с выхода перемножителя 22 полученная величиначерез коммутатор 30 подается на блоки27 и 28. Величинаявляется адресомдля блоков 27 и 28, по которому в нихзаписаны соответственно г, и х , Врезультате на выходе блока 27 йоявляется величина гкоторую записывают в блок 23 группы иэ ш триггеров,а на выходе блока 28 - хг, которуюзаписывают в блок 33 и ш триггеров.На втором такте с выходов блока11 на блоки 24 я 25 оперативной памя.ти подаются сигналы записи и выдает"ся адрес, по которому величина а, записывается в блок 24, а г - в блок25.На третьем такте блок 12 с по(5) Х,= гС,; Х = егС 30 о оХ, +,Хг= Б,;40 У= 1+ 80 где я и гг - решение уравнения (4),Так как уравнение (4) имеет ненулевые корни только при определенных значениях , то операцию решения 10(4) просто реализуют табличным способом с помощью блоков 27 и 28 постоянной памяти. Для всех возможных значений, при.которых (4) имеет ненулевые решения, заранее определены величины ги хг и по каждому адресув блок 27 занесены соответствующая величина к а в блок 28 - г, При подаче на адресные входы бло". ков 27 и 28 величины 11 с их выходов 2 О считывают соответствующие величины з,изПосле определения локаторов Хи Хг из (5) производят определение значений У и У ошибок из соотношений (3), которые для кода Рида- Соломона с порождающим многочленом 9(х) = (х+1) (х+с) (х+а,") (х+юс) имеет вид Блок 7 при 1 = 2 работает следующим образом,При обнаружении ошибок из блока 6 45в блок 7 выдается сигнал, который открывает элемент И 9. Через него начинают поступать тактовые импульсыТ на счетчик 1 О. На выходы счетчика10 подключены блоки 11,12,21 и 26постоянной памяти.На первом такте блок 12 подключает с помощью коммутатора 18 на входыперемножителя 22 выходы регистра 16,а выходы регистра 17 через блок 29памяти, коммутатор 20 и блок 13памяти с помощью коммутатора 19 навторую шину перемножителя 22. Значение С, записанное в регистре 17,мощью коммутатора 18 подключает на первые входы перемножителя 22 выходы блока 24, блок 11 выбирает из блока 24 величину г которая подается на входы перемножителя 22. Одновременно блок 12 с помощью коммутатора 1.9 подключает выход регистра 17 на вторые входы перемножителя 22, а блок 26 с помощью коммутаторов 31 и 32 подключает выход перемножителя 22 на входы групп 23 и 33 триггеров. Таким образом, на выходе перемножителя 22 получен локатор ошибок Х, " .г,Г который записывается в триггеры групп 23 и 33.На четвертом такте локатор Х, с помощью блока 11 с группы 23 тригге, ров переписывается в блок 24.На пятом такте блок 11 выбирает из блока 25 величину г, которая с блоком 12 через коммутатор 19 подает. ся на входы перемножителя 22. На входы перемножителя блоком 12 с помощью коммутатора 25 подается вели1432787 Таблица Двоичный вид символа СГ(2 ) 50 О О О О ОО 1. О1 О О О 1 1 55 5чина С, с блока 7. Блок 26 с по"мощью коммутаторов 31 и 32 подключа 6 т выходы перемножителя 22 на входы,Фгрупп 23 и 33 .триггеров. В результате в группу 23 триггеров записываетсялокатор Х С г .В группе 33 триггеров локатор Х складывается по мойДулю два с локатором Х, который быпЗаписан на третьем такте.На шестом такте с помощью блока11 локатор Х с группы 23 триггеровпереписывается в блок 24, а (Х,+ Х)с группы 33 триггеров в блок 25.На седьмом такте блок 26 с помощьюкоммутатора 31 подключает выходы регистра 15 на входы группы 23 триггеров, в которую записывается 8,На восьмом такте блок 11 выбираетиэ блока 24 локатор ошибок Х. Блок12 с помощью коммутатора 18 йодаетна первые входы перемножителя 22 локатор Х, а с помощью коммутатора19 на вторые входы перемножителя22 " синдром Яз. Блок 26 с помощьюкоммутатора 31 подключает выходы перемножителя 22 на входы группы 23триггеров. В результате на выходеперемножителя 22 получают величинуБ Х, которая складывается по модудва с синдромом Б записанным втриггерах 23 группы.На девятом такте полученная величина Б Х+ 8, переписывается в блок24,На десятом Факте блок 2 с помощью коммутатора 18 подключает выходы блока 24 на первые входы перемйожителя 22, а с помощью коммутато" ра 19 - выходы блока 13 на вторые входы перемножителя 22. Одновременно блок 21 о помощью блока 20 коммутирует, подключает выходы блока 25 на вХоды блока 13, блок 26 с помощью коммутатора 32 - выходы перемножителя 22 на входы группы 33 триггеров. Блок 11 выбирает из блока 24 величину 8 Х+ 8, которая поступает на первые: входы перемножителя 22, а из блока 25 - величину Х, + Х , являющуюся адресом для блока 13, по которому записана величина 1/(Х,+ Х), поступающая на вторые входы перемножителя 22, Следовательно, на выходе перемножителя получают значение ошиб 8 Х 2+ 8ки У в в- , которое эаписываХ+Х фется в группу 33 триггеров. На одиннадцатом такте величинаУ, с помощью блока 11 переписывается в блок 25.На двенадцатом такте блок 26 спомощью коммутатора 32 подключаетвыходы регистра.14 на входы группы.33 триггеров, в которую записывается величина 8 , Одновременно локатор 10 Х, являющийся адресом искаженногоэлемента, подается на буферный накопитель 2, в результате разряды искаженного символа с адресом Х подаются на блок 3 сумматоров по модулю 15 два на вторые входы которых подается ошибка с помощью блока 11, Присложении разрядов искаженного символа с У, происходит исправление иисправленный элемент вновь записывается в буферный накопитель 2 потому же адресу.На тринадцатом также, аналогично как и на десятом такте, на входыгруппы триггеров 33 подают величину 25 У которая складывается по модулюдва с величиной 8 , записанной на двенадцатом такте.Полученная в результате величинаУ У+ 8 на четырнадцатом такте 30 переписывается в блок 25.На пятнадцатом такте производятисправление искаженного символа сномером Х аналогично тому, как этоделают на двенадцатом такте.Рассмотрим процесс исправлениядвухкратных ошибок на конкретномпримере для кода Рида-Соломона длины7 с образующим полиномом 9(х) = (х++1) (х+о) (х +м ) (х + о) длиной 7, в 40 котором имеют 3 информационных и 5проверочных, символов поля СР(2 ),каждый из которых содержит 3 двоичных разряда в соответствии с табл.1. 45 Т3Символ поля СР(2 )1432787 С - Я Я+ Яа о 1 +Км Продолжение табл.1 5 2 4Яо Яь ф ф +ф. 1 1 0 1 1 1 1 0 1 5поступают на входы соответственнорегистра 16 и регистра 17. Из блока6 в блок 7 выдается сигнал, открывающий элемент И 9 и через него пос О тупают тактовые импульсы на счетчик10, выходы которого подключены к адресным входам блоков 1,2,21 и 26постоянной памяти.1 Допустим при передаче по каналу связи слова кода Рида-Соломона 001 Ы. М еСЫ на позициях с номерамии Ы = 1 проиэошли ошибки и в буферный накопитель 2 поступает слово 0011 Ы Ы, ЫС выходов блока 5 синдромы ЯЯ.о фЯ ф в Я = О(, и Яз - 1 по дают на входы блока 6. Кроме того, Я и Я записывают соответственно в регистры 14 и 15. С выходов блока 6 величины 15 На первом такте с выхода перемножителя 22 у ==- вв е в двоичном виде 010 поступает на адресные 20входы А А Ав блоков 27 и 28 посотоянной памяти, в которых по адресу для всех возможных значенийзанесены соответствующие им значения Рд, Р Р корней уравнения (4) г, (в блоке 27) и г (в блоке 28) в соответствии с табл.2. Я Я + ЯоЯз Ы,Ы,ф+с(4ЬШ фл )ЫЫ+К Ы Таблица 2 Выход данных блока 27 ДвочиЗначение гв поле СР(2 )ъ вид гР( Двоичный вид ный Значение ( г в полеСР(2 )а Значениев полеСР(2 ) Двоичныйвид Г га о й А )А,/А Ы. 1 0 1 0 1 О 1 0 0 1 1 0 1 0 О.1 1 0 1 1 1. о О 1 0 0 10 виде 010 записывают в триггеры групп23 и 33.На четвертом такте величину Хпереписывают в блок 24.На пятом такте с выходов перемножителя 22 локатор Х = г С,-"й юр 16в двоичном виде 001 записывают вгруппы 23 и 33 триггеров, причем вгруппе 33 триггеров Х и Х сумми руются по модулю два.На шестом такте локаторов Х вдвоичном виде 001 записывают в блок24, а сумму (Х,+ Х ) в двоичном виде 010 - в блок 25. По адресу Ао А А 010 в блоке 27 занесены двоичная последовательность РЭ,Р - 100, что соответствует г 1 = ф , в блоке 28 - 101, что соответствует г= ес . Величина г и г в6двоичном виде записывают соответственно в блок 23 и блок 33 группы из 3 триггеров.На втором такте величину г (1 00) записывают в блок 24, а г (1 01) в блок 25.На третьем такте с выхода перемножителя 22 полученный локатор ошибок Х = г, С, и гг =М,.в двоичном Адресные входы блоков 27, 28 Выход данных блока 28На седьмом такте в группу триггеров 23 записывают Я в двоичном виде 111,. что соответствует значению М которую на восьмом такте в группе 23 суммируют по модулю два с двоичной , последовательностью - 11 О, соответствующей величине Я Хо1 = М,Фпоступающей,.с выхода перемножителя Фф ) 22. Полученную сумму Я Х + Я, Ф ф + + М1 в двоичном ниде 001 переписывают в блок 24На десятом такте с выходов пере- множителя значение ошибки Я Х+ Ьу а Х,+ Х о 6 б в двоичном виде 101 записывают вгруппу 33 триггеров, которую на одиннадцатом такте переписывают в блок 25,20На двенадцатом такте в блоке 3 сумматоров по модулю два проводят сложение искаженного символас номеромо с УЫ и исправленный элемент25символ имеет значение 1 + М = М .Тринадцатый такт аналогичен десятому. При этом в группе 33.триггеров,величина У = о суммируется с величиной Я = Ы ,записанной на двенад,цатом такте. Полученное значениеу ) у + Я об + о 4 ) о 3 на чатырЙ 1 онадцатом такте переписывают в блок 25,На пятнадцатом такте, как и на две,надцатом, производят исправление симовола с номером Х = о = 1 и исправленный символ имеет значение о + К =о еТаким образом, после исправленияв буферном накопителе 2 занесено"очищенное" от двух ошибок слово00 К Ы ос ЫПри возникновении однократныхошибок счетчик 1 О устанавливаетсясигналом "Установка" с второго управляющего входа блока 6 в 16-е состоя 45ние, В этом состоянии блок 26 с помощью коммутатора 31 коммутирует вы"ходы регистра 17 на входы группы 23триггеров, в которые записывается ве"личина Х= С, а с помощью коммутатора 32 - выходы регистра 14 на входы группы 33 триггеров, в которую за"писывается величина У,= Я,На семнадцатом такте производятзапись величины Х, -в блок 24, а вею 1 ичины У - в блок 25, Исправлениеоднократной ошибки осуществляют также, как и двухкратных, Формула изобретения Устройство для исправления ошибок, содержащее запоминающий блок, выходы которого подключены к входам генератора синдромов и первым входам буферного наКопителя, выходы которого подключены к третьим входам блока из ш сумматоров по модулю два, где ш - размерность поля ЦР(2 ) Галуа, выходы которого подключены к вторым входам буферного накопителя и являются информационными выходами устройства, выходы генератора синдромов подключены к входам накопителя синдромов, первые, вторые, третьи и четвертые выходы которого соединены с соответствующими входами вычислителя элементарных симметрических функ-. ций и входами дешифратора ошибки, первый выход которого подключен к пятому входу вычислителя элементарных симметрических функций, второй выход соединен с третьим входом буферного накопителя и является контрольным выходом устройства, блок вычисления ошибок, включающий элемент И, счетчик импульсов, первый - третий коммутаторы, первый - третий блоки постоянной памяти, перемножитель, первую группу из ш триггеров, первый и второй блоки оперативной памяти и первый второй, третий и четвертый регистры, выход элемента И подключен к счетному входу счетчика импульсов, выход которого соединен с входами первого и второго блоков постоянной памяти, выход первого регистра подключен к первому входу второго коммутатора, выходы второго и .третьего регистров подключены соответственно к первому и второму входам первого коммутатора, выход четвертого регистра подключен к третьему входу первого коммутатора и второму входу второго коммутатора, выходы третьего коммутатора подключены к входам третьего блока постоянной памяти, выход которого соединен с третьим входом второго коммутатора, первый и второй выходы второго блока постоянной памяти подключены к четвертым входам соответственно первого и второго коммутаторов, выходы которых соединены с соответствующими входами перемножителя, первый и второй .выходы первого блока постоянной памяти подключены к первым вхоЗаказ 5464/55 Тираж 929 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д. 4/5Производственно-полиграфическое предприятие, г. Ужгород, ул, Проектная, 4 11 1432 дам сОГтветственно первого и второго блоков оперативной памяти, выходы первой группы из ш триггеров подключены к вторым входам первого блока оперативной памяти, выходы которого подключены к пятым входам первого коммутатора и четвертым входам буферного накопителя, выходы второго блока оперативной памяти соединены с первыми входами третьего коммутатора и вторыми входами блока из ш сумматоров по модулю два, первый вход элемента И и установочный вход счетчика импульсов подключены соответственно к первому и второму управляющим выходам вычислителя элементарных симметрических функций, входы первого-четвертого регистров подключены соответственно к первому и второму выходам накопителя синдромов и первому и второму информационным выходам вычислителя элементарных симметрических функций, второй вход элемента И является тактовым входом уст ройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в блок вычисления ошибок введены четвертый - восьмой блоки .постоянной памяти, четвертый - шестой комму- ЗО таторыи вторая группа из ш триггеров, выходы которой подключены к 787 12вторым входам второго блока оперативной памяти, выходы четвертого и пятого блоков постоянной памяти объединены и подключены к выходу счетчика импульсов, первый и второй выходы четвертого блока постоянной памяти подключены соответственно к первому входу четвертого коммутатора и второму входу третьего коммутатора, третий вход которого соединен с выходом пятого блока постоянной памяти, вход которого объединен с первым входом пятого коммутатора и подключен к выходу четвертого регистра, первый вход шестого коммутатора. соединен С выходом первого регистра, выходы перемножителя подключены к вторым входам четвертого - шестого коммутаторов, первый н второй выходы шестого блока постоянной памяти подключены к третьим входам соответственно шестого коммутатора и пятого коммутатора, четвертый вход которого соединен с выходом второго регистра, выход четвертого коммутатора подключен к входам седьмого и восьмого блоков постоянной памяти, выходы которых объединены соответственно с выходами пятого и шестого коммутаторов н подключены к входам первой и второй групп из триггеров.