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

СОЮЗ СОВЕТСКИХООЦМаЮЮеэииРЕСПУБЛИК ГОСУДАРСТВЕККЬ 1 Й КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТВ 1 ИЙ И ОТНРЫТИЙОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ВСРГОИ)рщ р(71) Институт проблем передачи информации АН СССР и Пензенский политехнический институт(56) Авторское свидетельство СССРУ 9 13383, кл. 0 0611/08, 1978.Патент США 9 4142174,кл. О 06 Р 11/12 ь 27.0279(54) УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯ ОШИБОК(57) Изобретение относится к вычислительной технике и может быть ис.801216832 Аш 4 Н 03 М 13/00 пользовано при создании устройств,корректирующих ошибки в передаваемой или хранимой информации. Цельизобретения - повьппение быстродействия. Устройство содержит запоминающий блок, буФерный накопитель, блокиз ш сумматоров по модулю два, генератор синдромов, накопитель синдромов, вычислитель элементарных симметрических функций, дешифраторошибок и блок вычисления ошибок,состоящий из элемента И, трех блоков постоянной памяти, четырех регистров, трех коммутаторов, дешифратора,перемножителя, группы из штриггеров, двух блоков оперативнойпамяти, трех элементов НЕ;и группыиз шсумматоров по модулю два.1 з.п. ф-лы. 2 ил.1 1Изобретение относится к вычислительной технике и может быть применено при созданйи устройств, коррек"тирующих ошибки в передаваемой илихранимой информации.Цель изобретения - повышение быстродействия.На фиг, представлена блок-схема устройства; на фиг.2 - структурная схема блока вычисления ошибок.Устройство содержит запоминающийблок 1, буферный накопитель 2, блок3 из ш сумматоров .по модулю два,генератор 4 синдромов, накопитель 5синдромов, вычислитель 6 элементарных симметрических функций, блок 7вычисления ошибок и дешифратор 8ошибок.Блок 7 вычисления ошибок состоит из элемента И 9, счетчика 10,первого, второго и третьего блоков 11-13 постоянной памяти, первого, второго, третьего и четвепто"го регистров 14-17, первого, второ, го и третьего коммутаторов 18-20,дешифратора 21, перемножителя 22,группы из ш триггеров 23, первого ивторого блоков 24 и 25 оперативнойпамяти, первого, второго и третьегоэлементов НЕ 26-28 и группы из ш сумматоров 29 по модулю два, Входные и выходные шины запоминающегоблока 1, буферного накопителя 2, блока 3 сумматоров по модулю два, генератора 4 синдромов, накопителя5 синдромов, вычислителя б элеменФтарных симметрических функций, блока 7 вычисления ошибок, а такжерегистров 14-17, коммутаторов 18-20перемножителя 22 и блоков 24 и 25оперативной памяти содержат по шцепей, Счетчик 10 имеет пять разрядов, адресные входы первого и второго коммутаторов 18 и 19 содержатпо три разряда.Особенность четвертого регистра17 состоит в обеспечении режимасдвига в сторону последнего ш-горазряда, для чего выход этого разряда соединен с входом первогоразряда этого регистра 17,Шестые и седьмые входы первогокоммутатора 18 двумя младшими разрядами подключены соответственно, к входам и выходам элементов НЕ 27и 28, остальные разряды этих кодовсоединены соответственно с прямамни инверсными выходами сумматоров 29(4) 4Для обнаружения и исправления ошибок необходимо полученную комбинацию символов В(Х) разделить на 9(Х). Из (4) видно, что это . аналогично делению Е(Х) на д(Х), Если деление произведено без остатка, то делается зак 510 по модулю два группы из штакихсумматоров,Устройство предназначено дляработы с кодами Рида-Соломона, вкаждой кодовой комбинации которогоимеется К информационных и и-Кпроверочных символов, каждый из,которых содержит в двоичных разрядов,где в - размерность поля ОГ(2) Галуа, Образующий полином кода дляисправления двухкратных ошибок д (Х) =(Х+1) (Х+ С ) (Х+Ф) (Х+С 1) (1) где с( - примитивный элемент поляОГ(2) Галуа.Длина кода п(2 - 1,В запоминающем блокес помощью образуюшего попинома 9(Х) записывается кодовая комбинация С(Х),При передаче по каналу связи илипри записи и считывании с блока 1на 0(Х) накладывается вектор ошибокЕ(Х), В результате на выход блокапоступает последовательность Вектор ошибок представляет из себя полином, 1-я позиция которого еЧть 1-й локатор ошибок, обозначаемый Х , При этом значение ошибки У, является символом из поля СГ(2 ). Сле-довательно полином ошибок имеет вид где суммирование производится по всемпозициям ошибок.Кодовая комбинация всегда делитсябез остатка на д(Х), т,е. Б-"0для 0663, Из (2) можно получить й(Ы)=6(с)+Е(М)=Е(К ) для 01143 лючение об отсутствии ошибок. Остаток от деления является синдромом ошибок Б;. По синдромам производитсяотыскание и исправление ошибок. Приделении В(Х) на составные множителиц(х) получают БоБ 1 Бь Бз. При,этом Б: =. Е(оЕ ) = В(оС) при Х =о(.Отсюда иа имеем5; =(с ) =, У (о" )=У( 5) По синдромам находится многочленлокаторов ошибок С(Х)=Д(Х-Х;,)=Х +СХ С, (6где 1 - число ошибок;Х - -й локатор ошибок;С; - элементарные симметрическиефункции д-й степени от локаторовошибок,Величины С; определяются из следующего рекуррентного соотношения1+е С 1+е-+ +Е-+е =(8) Устройство для исправления ошибок работает следующим образом,Закодированные избыточным (п,К)- кодом данные считываются из запоминающего блока 1 в буферный накопитель2 и генератор 4 синдромов, где и - длина кодового блока в элементах поля СР(2 ), К - длина информационной части блока. В генераторе. 4 путем деления на составные части образующего полинома д(Х)=(Х+1)(Х+О ) х(Х+о), получают синдромы ошибок Бо. ЯЯт Б которые записываются в накопитель 5 синдромов. На выходе накопителя 5 подключен дешифратор 8 ошибок, который функционирует как элемент ИЛИ. Если при делении получается остаток, то он содержит хотя бы одну 1. Тогда на первом выходе дешифратора 8 появляется сигнал Ошибка". Если Яо = Б, = Я = Бз = О, то на втором выходе дешифратора 8 появляется сигнал "Нет ошибки" и кодовый блок выдается потребителю путем подачи сигнала "Считывание" на управляющий вход буферного накопителя 2.Сигнал "Ошибка" дает разрешение для работы вычислителя 6. При этом вначале определяется кратность Яде степени примивного элемента Ф Если примитивный элемент о таков,что элементы Ф,о,с, Ф с являются линеино нЕзависимыми над СГ(2 ), то они образуют нормальный базис. В таблицах неприводимых мно-. гочленов можно выбрать примитивный многочлен соответствующий степени, корни которогослинейно незави 40 симы, где 1=0,1,2 щ. Тогда произвольный элемент(= С Г (2 ) может быть представлен как некоторая степень с( и в виде разложения по нормальному базису 50 Представление элементовв виде разложения по нормальному базису удобно при возведении в степень вида 2". Например. если элемент исправляемых ошибок. При 1=1 определяется С, по выражениям (8), гдеС, - элементарная симметрическаяфункция. При Г=2 определяются Си Спо функциям (9). Последовательность работы вычислителя 6 приэтом следующая. Если Б Ф О, то Х)1и определяется С .=Я /Б; Б + СБ,и Б+ Б. При + СЯ в Б + С Б -= О 1=1 и Х= С, У,= Б. Определение единственного локатора и значения ошибки на этом заканчивается.Если Я+ГБ, О или Б=О и Б О, то ) 2и определяется б = Б+ ЯЯ, С 15 =(Б 1 Б+ БОБЗ)ИС ( 1 3 1)и Р = Бэ+ СБ+ СЯ. Если Р =О,то , = 2. Если Э Ф О или если Б,- Б = О и Б О, то Х)2, при этомпринятый блок информации стирается.Если в вычислителе 6 определено,что 2=2, то с первого управляющеговыхода в блок 7 выдается сигнал наэлемент И 9. Через него на счетчик1 О начинают поступать тактовые импульсы Т. К выходам счетчика 10 под-,ключены входы блока 12,первые и вторые выходы которого задают адреса со"ответственно для коммутаторов 18 ,и 19.Вначале опишем процесс расчета ипреобразований принятых символов,каждый из которых содержит ш битв поле СР(2 ) Галуа. Все символыполя СГ(2 ) можно представить в ви 1216832+ о 1+ +Опосколькуо(гф о, Таким образом,возведение в квадрат означает цикли Оческий сдвиг элемента на один разряд,вправо,Для нахождения локаторов ошибокХгх нужно решить квадратное уравнение 5О(Х)=(Х+Х,) (Х+Х,)=Х + ОХ +О(2,где О= Х+ Хг, Ощ Х,ХКорни уравненияХ+ ОХ+ О= 0 (13) и являются локаторами ошибок Х 1 и Х гПриведем уравнение (13) к каноническому виду заменой Х=ЕО,. В ре эультате получим2 2+О,/О,=О.Если обозначить г= Ог/О, то получим ЗО(16)Блок 7 при 1=2 работает следующий образом.При обнаружении ошибок из блока 6 в блок 7 выдается сигнал, который открывает элемент И 9. Через него начинают поступать тактовые импульсы Т на счетчик 10. На выходы счетчика 10 подключен дешифратор 21.На первом такте срабатывает дешифратор 21, сигнал с первого выхода которого сдвигает на 1 разряд вправо содержимое регистра 17. При сдвиге вправо величина О, записанная в регистр 17, возводится в квадрат (О,) , На втором такте блок 12 подключает с помощью первого коммутато ра 18 иа первые входы перемножителя 22 выходы регистра 16, а выходы регистра 17 через коммутатор 20 и блок 13 - на вторую входную шину перемножителя 22. Значение О, записанное в регистре 17, является адресом для блока 19. В результате на выходе блока 13 появляется записанная в нем по этому адресу величина /О. Следовательно, на первых входах перемножителя 22 появляется величина О, а на вторых - величина 1/О, На этом же такте происходит умножение О на 1/Ои на выходе перемножителя 22 получают величину ф , которая записывается в триггеры 23 группы. На третьем такте с первых выходов блока 11 на блок 24 подается сигнал записи и выдается первый адрес, по которому величина ф записывается в блок 24 1На четвертом такте блок 11 выбирает из блока 24 величину ф, в резупьтате преобразования которой в соответствии с (5) на входах. элементов 27 и 28 и прямых выходах сумматоров 29 группы получается величина Е, которая подключается блоком 2 с помощью коммутатора 18 на первые входы перемножителя 22. Одновременно блок 12 с помощью коммутатора 19 подключает выходы регистра 17 на вторые входы,перемножителя 22. Таким образом, на выходе последнего получен локатор ошибок Х= Е,О 1, который записывается в триггеры 23 группы. На пятом такте локатор Х 1 с помощью блока 11 переписывается в блоки 24 и 25.На шестом такте блок 11 снова выбирает из блока 24 величину ф , в результате преобразования котоой в соответствии с (16) на ннверсных выходах элементов 27 и 28 и сумматоров 28 группы получается величнна 2 , которая подключается блоком 12 с помощью коммутатора 18 на первые входы . перемножителя 22.Одновременно блок 12 с помощью коммутатора 19 подключает выходы регистра 17 на вторые входы перемножителя 22, Таким образом, на выходе последнего получен локатор ошибок Х= ЕО,1, который записывается в триггеры 23 группы, На седьмом такте величина Хс помощью блока 11 переписывается в блоки 24 и 25. На этом заканчивается определение локаторов ошибок. Значения ошибок легко найти по Х, Х , Я, и Б ., Для этого необходимо осуществить преобразова 1216832(17)Определение У, начинается с восьмого такта. Блок 12 подключает спомощью коммутатора 18 на первыевходы перемножителя 22 выходы регистра 14, блок 1 выбирает из блока,25 величину Х, а блок 12 подключает ее с помощью коммутатора 19на,вторые входы перемножителя 22.Врезультате на выходе последнегополучается величина БоХ, котораязаписывается в триггеры 23 группы.На девятом такте блок 12 подключает выходы регистра 15 с помощьюкоммутатора 18 на первые входыперемножителя 22,а выход элемента 26 с помощью коммутатора 19 - навторые входы перемножителя 22. Врезультате на выходе перемножителя22 получают величину с Б = Б 1,которая складывается по модулю. 2с величиной БХ, записанной втриггерах 23 группы, Полученнаявеличина Бо Х+ Б 1 на десятом такте переписывается в блок 24,На 11-м такте блок 11 выбираетиз блоков 24 и 25 локатор ошибокХ. Блок 12 с помощью коммутатора18 подключает этот локатор напервые, а с помощью коммутатора19 - на вторые входы перемножителя 22. Полученная на его выходевеличина ХХ= Х записывается2в триггеры 23 группы. На 12-мтакте; Ьлок 11 выбирает из блока .24 величину Х , а из блока 25 -величину Х . Эти локаторы ошибок(Х 1, Х) подаются с помощью блока12 и коммутаторов 8 и 9 соответственно на первые и вторцевходы перемножителя 22, На выходе его будет получена величина ХХ,которая складывается по модулю 2 свеличиной Х, записанной в тригогеры 23 группы.На 13-и такте блок 11 выбирает из блока 25: величину БХ,+ Яи блок 12 подает ее с помощью коммутатора 18 на первые входы пере множителя 22. Сигналом с второговыхода дешифратора 21 с помощьюкоммутатора 20 величина Х 1 + ХХт.хранящаяся в группе триггеров 23,подается на вход блока 13, навыходе которого получают величину1/Х+ХХ. На этом же 13-м такте этавеличина с помощью блока 12 и коммутатора 19 подается на вторые входыперсмножителя 22, на выходе которогополучают значение ошибки 5 ОПри возникновении однократных ошибок счетчик 10 устанавливается сигналом "Установка" с второго управляющего выхода вычислителя 6 в 24-е состояние. В этом состоянии блок 12 подключает с, помощью комомутатора 18 величину о( на первые,а с помощью коммутатора 19 величину О - на вторые входы переомножителя 22. Величинао 61 записывается в триггеры 23 группы и на 25-м состоянии счетчика 1 О переписывается:в блок 24. В данном случае Х , = С . На 26-мсостоянии счетчика 1 О блок 12 подключает на первые входы перемножителя 22 синдром Я, а на вторые входы перемножителя 22 - значение о . Значение 45 50 55 Яб 1 Я 11 Х 7+ УХ5 На 14-м такте значение У, переписывается в блок 25.Совершенно аналогично, начиная с15-го такта, вычисляется значениеошибки У по формуле (7). На вычис ление У тратится также 7 тактови на 21-м такте этот локатор записывается в блок 25.Таким образом, полученные локаторы ошибок Х 1 и Х записаны в блок 24, 25а значения ошибок У 1 и У - в блок 25.На 22-м такте величина Х являющаяся адресом искаженного элемента,подается на буферный накопитель 2,в результате разряды искаженного Зф символа с адресом Х подаются наблок 3 сумматоров по модулю 2, навторые входы которых подается ошибка с помощью блока 11. При сложенииразрядов искаженного символа с У 35 происходит исправление и исправленный элемент вновь записывается в бубуфернцй накопитель 2 по тому жеадресу. Исправление элемента Хъпроисходит на 23-м такте аналогич но.Ы Б, записывается в триггеры 23 группы и на 27-м состоянии счетчика 10переписывается в блок 25. ЗдесьУп = ЯБ. Исправление однократнойошибки осуществляется так же, как идвухкратных,Формула изобретения Устройство для исправления ошибок, содержащее запоминающий блок, генератор синдромов, накопитель синдромов, вычислитель элементарных симметрических Функций, дешифратор ошибки, блок вычисления ошибок, буферный накопитель и блок из ш сумматоров по модулю два, выходы которых соединены с выходной шиной, а первые входы подключены к соответствуницим выходам буферного накопителя, первые входы которого объединены с соответствующими входами генератора синдромов и подключены к соответствующим выходам запоминающего блока, выходы генератора синдромов соединены с соответствующими входами накопителя синдромов, первые, вто рые, третьи и четвертые выходы которого соединены с соотяетствующими входами вычислителя элементарных симметрических функций и с входами дешифратора ошибки, первый выход которого подключен к управляющему входу вычислителя элементарных симметрических функций, второй выход дешифратора ошибки является контрольным выходом устройства, о т л и - ч а ю щ е е с я тем, что, с целью повышения быстродействия, блок вы- . числения ошибок состоит из четырех регистров, счетчика, дешифратора, трех коммутаторов, трех блоков постоянной памяти, двух блоков оперативной памяти, группы, из ш триггеров, перемножителя, группы из шсумматоров по модулю два, трех элементов НЕ и элемента И,первый вход которого соединен с тактовой шиной, выход подключен к счетному входу счетчика, второй вход элемента И и установочный вход счетчика подключены соответственно к первому и второму управляющим выходам вычислителя элементарных симметрических функций, выходы разрядов счетчика соединены с соответствующими входами дешифратора, первого и второго блоков постоянной памяти, первые и 5 10 15 20 25 30 35 40 45 50 55 вторые выходы первого блока постоянной памяти подключены к управляющим входам соответственно первого и второго блоков оперативной памяти, входы первого и второгорегистров соединены с соответствующими выходами накопителя синдромов, входы третьего и четвертого регистров подключены соответственно к вторым и первым выходам вычислителя элементарнйх симметрическихФункций, выходы первого, второго итретьего регистров подключены к соответствующим входам первого коммутатора, выходы которого соединены ссоответствующими первыми входамиперемножителя, вторые входы которого подключены к соответствуюшим выходам второго коммутатора, первыевходы которого соединены с выходамитретьего блока постоянной памяти,входы которого подключены к выходамтретьего коммутатора, первые входыкоторого объединены с соответствующими вторыми входами второго коммутатора и подключены к соответствующим выходам четвертого регистра,выход последнего разряда которогосоединен с входом его первого разряда, а управляющий вход подключенк первому выходу дешифратора, второй выход которого соединен с управляющим входом третьего коммутатора,вторые входы которого объединеныс соответствующими информационнымивходами первого и второго блоковоперативной памяти и подключены квыходам соответствующих триггеровгруппы, инверсный выход каждого изкоторых соединен с его входом, синхронизирующие входы триггеров группыподключены к соответствующим выходамперемножителя, выходы второго блока оперативной памяти подключенык соответствующим вторым входамблока из ш сумматоров по модулю дваи третьим входам второго коммутатора, четвертые входы которого объединены с четвертыми входами. первогокоммутатора и через первый элементНЕ соединены с шиной нулевого потенциала, выходы первого блока оператив.ной памяти подключены к соответствующим вторым входам буферного накопителя и пятым входам первого коммутатора, адресные входы которого соединены с соответствующими первымивыходами второго блока постояннойпамяти, вторые выходы которого подключены,к соответствующим адреснымвходам второго коммутатора, шестыевходы первого коммутатора подключены соответственно к шине нулевого потенциала, второму выходу первого блока оперативной памяти ипрямым выходам шсумматоров по модулю два, седьмые входы первогокоммутатора подключены соответственно к выходам второго и третьего.элементов НЕ и инверсным выходамшсумматоров по модулю два, входвторого элемента НЕ соединен с шинойнулевого потенциала, вход третьегоэлемента НЕ объединен с первым входом первого из ш 2 сумматоров помодулю два и подключен к второмувыходу первого блока оперативной 5памяти первый вход каждого из осУтальных сумматоров по модулю два сое.динен с прямым выходом предыдущего,вторые входы шсумматоров помодулю два подключены к выходам 1 О первого блока оперативной памяти стретьего по ш-Й соответственно, вы-,ходы блока из ш сумматоров по модулю два подключены к соответствующимтретьим входам буферного накопите ля, управляющий вход которого соединен с вторым выходом дешифратора ошибокмгде- размерность поля с С( 2 )Галуа,