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

(51)5 Н 03 М 13/О ОПИСАНИЕ ИЗОБРЕТ ГОСУДАРСТ 8 ЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМПРИ ГННТ СССР 1(56) Хетагуров Я.А. и др. Повышениенадежности циФровцх устройств методами избыточного кодирования. М.:Энергия, 1974, с, 51-56.Авторское свидетельство СССРУ 720757, кл. Н 03 М 13/02, 1980.Патент США Р 3755779,кл. С 06 Р 11/12,(54) УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯ ПАКЕ. ТА ОШИБОК ДЛИНЫ ДВА,(57) Изобретение относится к вычислительной технике, а именно к передачам инФормации, и может быть использовано для контроля оперативных и постоянных запоминающих устройств. Целью изобретения является повышение достоверности исправляемой инФормации. Устройство содержит генератор 1 синдрома, генератор 2 сигналов ошибок, селекторы 3,4, дешиФраторы 5,6, первый блок 7 суммматоров по модулю два, преобразователь 8 кода, второй блок 9 суммато-. ров по модулю два, информационные входы 1 О, выходы 11, 12, 13 сигналов ошибок, информационные выходы 14.(1символ кода а( .при 1 = 1-и, совпаает с одним из значений столбцов матрицы Н, а синдром ошибки в соседних разрядах кода а - с одним из эначе(нйй столбцов матрицы С.В этом случае, например, код Хэминга (32, 26) преобразуется в код (24, 18), исправляющий пакеты ошибокй Н( О(4, 2 1; ;э,Ы , гдеа 1 а 2 аэа 4 аэаьаа 8 а аа 9 10,11 0010 0011 1111 0100 0110 0011 1111 01 0.0 0110 0011 0010 0011 0110 0011 0010 0011 1111 0100 а 1 эа 14 аа а 19 а 18 а 19 а ада а,а 0011 0010 0011 1111 0100 0110 0011 1111 01.00 01 10 0011 0010 0100 0110 0011 001 0 0011 1111 г = 6;= 4; -1; .к --О - 5 (1.=0;- 0+4=4, 1.9=2=(4+4)шод 6, х,= 2-1= =1, 1 =1+4=5, .=3=(5-4)тло 36); каждому столбцу этих подматриц и(" соответствует один из символов аи = 24-разрядного кода а = (а а аа ащ)(ге) (Ц Я при 1 = 1 . - 24. Для упроцейия схемы кодирования, также как и в случае кода Хэмминга, целесообразно в качестве контрольных символов выбрать значения а а , а а а, и а соответствующие первым столбцам этих подматриц у 1 КМатрица С =3 , (3;/5 Э образуется из следующих подматриц1.112 С(э 1111(618 . (91 ОС 11114 0110 01 00 0001 1.1 00010 01 01 1010 01 01 0111 01 01 0001 1100 0001 11 00 1010 01 01 0111 01 01 па 419 С(го 1 г 1 агэ Э 14 6 010 011 010 000 110 101 1100 1010 01 01 0111 01 01 0001 01 01 0001 1100 1010 01 01 0111 Каждый 3- столбец в подматрицах8"обозначен символом с 1; Й = Б, + Изобретение относится к вычислительной технике, а именно к областипередачи инФормации, и может быть ис дпользовано для контроля оперативныхи постоянных ЗУ,Цель изобретения - повьппение достоверности исправляемой инФормациипутем исправления максимального чис- мла ипакетов ошибок длины два.10На чертеже приведена структурная длсхема предлагаемого устройства.Устройство содержит генератор 1синдрома, генератор 2 сигналов ошибок, селекторы 3 и 4, деыиФраторы 5и 6, первьп блок 7 сумматоров по модулю два, преобразователь 8 кода,второй блок 9 сумматоров по модулю два,инФормационные входы 10, выходы 1113 сигналов ошибок и инФормационныевыходы 14.Предлагаемое. устройство предназначено для декодирования кода длины и,исправляющего и, одиночных ошибок иипакетов ошибок длины два.Код образуется путем сокращениячисла и инФормационных символов модиФицированного кода Хэмминга с обнаружением двойных ошибок на основе матрицы Н, содержащей и различимых кодовстолбцов нечетного веса, таким обра 30зом, чтобы число и было кратно числуг = и-тп контрольных символов исходного кода Хэмминга (2 , 2 -г), где=1 - г ; ., = 0;=э1+(той,г);3.сопят подматрицы о(,к были бы составлены путем (э.к-Ц )вос г цикличес-, 40ких перестановок строк подматрицы п,а значение столбцов в подматрице О(и значениебыли бы выбраны так,чтобы матрица С,столбцы которой Формируются в результате суммирования всех 45соседних столбцов матрицы Н, содержала бы различимые коды, столбцов ,четного веса с аналогичной структурой1 к , 31где кподматрица, являющаяся результатомпоследовательного суммирования значений соседних столбцов подматрицы К,к,1 к 91включая первый столбец подматрицыМ ".Код однозначно исправляет и. одиночных опбок и ипакетов ошибок длиныдва в результате различимости значений столбцов в матрицах Н и С, Приэтом учитывается, что синдром одиночной ошибки в коде а =(а,а а..+ Я 4 (тпос 12); Б - синдром одиночнойошибки, соответствующий 3-му столбцуматрицы Н, Например, если в коде а(пошибка произошла по разрядам а и а,то 1 = 5, Б= й 0000101, Б= 111000111,а д = Б + Б (тпос 12) = й 000011, гдеТ - знак транспонирования матрицы.Декодирование предлагаемого кода вустройстве производится в три этапа.Первым этапом декодирования вычисляется значение г-разрядного синдромап 1Б по известному выражению: Б = а 1 п 1 Н.Если в коде а 1111 отсутствуют ошибки, тоБ = 0 (нулевой синдром). В случаеодиночной ошибки по. разряду аполучается БО (ненулевой синдром) нечетного веса, совпадаюций с 1-ым столбцом матрицы Н. При возникновении пакета ошибок длины два по разрядам 20аи а 1+1 - Б = д четного веса, Если+1значение БО.и не совпадает ни с одним из значений столбцов матриц Н иС, значит имеет место неисправнаяошибка (произвольная четная или нечетная ошибка),Вторым этапом декодирования производится дешифрация Б, результатом которой являются коды е = (ее ее ) и е =, (ее 4 е 1+ еп) 30состнелтеннме ин симнонон е 1 = 10; 11соответственно с нечетными 1 и четными 1+1 индексами,При Б = О и Я Ф О, не совпадаюттим. ни с одним из значений столбцов матрицН и С, выполняется условие: е= е я =35= О. При Б0 нечетного веса толькоодно значение е в кодах е я и е может равняться единице. Если ошибкапроисходит по нечетному разряду акода а , то ец. = О, ен0 с е = 1;Юа в случае ошибки по четному разрядуа+, - ет = О, еп Ф 0 с е., = 1. Например, если ошибка происходит по разряду акода а 1., то е и = (000000000000),ер=(001000000000) се =1; при ошибкепо разряду аб - ея = (000000000000),е;, = (001000000000) с е 6 = 1.В случае Б0 четного веса с учетом с 1 = Б + Б+,(тпос 12) сначала производится преобразование Б = д 1 в Ыс нечетным индексом 1 и вычислениеБ 14 с четным. индексом 4 1 на.основе,Б е, = Бее + с 1(тпос 12), а затем аналогично случаю Б0 нечетного веса55генерируются зттачение ея Ф 0 и еп Ф 0по Б 4 и Б 4, соответственно. Указанноепреобразование Я = Й 1 в Я производится путем выбора Б по значению Й из 12 бтаблицы преобразования, где каждому1значению д матрицы С поставлено всоответствйе значение Б с нечетныминдексом 1.Например, для кода (24, 18) в соо 1ветствии с укаэанными примерами матриц Н и С получается таблица преобразования (см, нйже),(241Если в коде а происходит ошибкано разрядам а 5 и аб, то для 3 = 5,с 1 = 100001 согласно приведеннойтаблице должно быть выбрано значениеБ = ) 000010, вычислено Бб = й +1+ Б (тпос 12) = 1000110. После деписЪрации Ы и Бб получаются коды ео Ф 0 се = 1 и еп Ф 0 с е = 1. Третьим этапом производится коррекция кода а путем вь."числения по значениям 1 поразрядной суммы: а 1"+ еи + ем(пют 12). Например, если е(10001000000000010000), то после вычисления значения синдрома по Б241 та(21 Н и дешифрации Б получаем ецОсе =1 иеп ФОсе =1, а в коде а 1 41 проинвертированы разряды 5 и б, обозначенные знаком +, Откоррек(241тированньпт код а" имеет следующий вид: а = (100001000000000100010000), которьп 1 удовлетворяет соотношениюБ = а 121 Н = О.Устройство работает следующим образом.С входов 10.1; 10,2. 10.(п), 10 п и-разрядньпт коц г 1 ф= (а а а ап) в параллельной форме поступает на входы соответствуюттих сумматоров 7.1, 7.2,7.(п), 7.п и на входы генератора 1. В соответствии с первым этапом декодирования генератор 1 по матрице Н на своих выходах вырабатывает г-разрядный синдром Б, который поступает на входы генератора 2 и преобразователя 8, на первые входы селекторов 3 и 4 и блока 9.В случае возникновения в коде а одиночной ошибки вырабатывается БО нечетного веса, по которому генератор 2 на своем первом выходе вырабатывает сигнал одиночной ошибки, поступающий на выход 12 устройства. При этом сигналы двойной и неисправимой ошибок на соответствующих втором и третьем вьмодах генератора 2 не вырабатываются. В селекторах 3 и 4 открываются каналы, пропускающие на выход информацию с первых входов, а значение Б с выходов1)578812 селекторов 3 ц 4 постуг)ает на Входы соответствуюьгнх дешцфраторов 5 ц 6, преднязняченнь)Х для Гееряцит) кпдоьг е. и еее соответственно. Если оыцбка происходит по Одному цз нечетных раз 5 РЯДов а а, ао., коДа а, то в(1 СООтВЕтетВИИ С БТОРЬ)Ь) ЭТЯГЕОМ ДЕКОДИ-. ровапия деетвЕет)ратором 6 Бь)рябатьепяется код е = О а Деш 151 фре)тором 5 - коде.е:, 0 с сигналом е = 1 коррекции на соответствуюцеь) Выходе дещцфрато" ра 5. Сцгналт е = 1 поступает на друГОй ВХОД СООтБЕТСтВУЮЕтЕЕГО СУММатОРа 7,1 ипц 7.3, или 7.5 и тоде с нечет ным номером В результате, сумматора- ми 7,1 7 о 3; 7.5,ооо Б соогветствии С тРЕтЬИМ ЭТЯПОМ )1 ЕКОт)ЕРО)За)Е)тГЕ ГЕНЕ- рцруЕтСН рЕэуЛЬТЯт т"уЬть) ЯЕ + Е(ШОЛА); сигь)япг)м е=- ) 1.)Евер гнр 5 етс)1 ц кор ректцруется о .)Ибочпи 1) печатный )-и разяц Я. кода Я о Отко)5 ре)ет)1 рован)ть 1) )ПЯЗ)ЯД ЯВМЕСТЕ С ОСТ,:Пт.н)ЕМ) ПЯЗРЯ Едами кода я. . котооые с учетом сь = О1без изменения генерцр по ся ня Бкходях ) СУмматоРОБ о ),. 7 о:.;п -1) ., 7,п В 1) с) Р ЯЛЛЕЛЬНОй Е)ОРМЕ Г ОСТ УЕЕЯ ЮТ 11 ега СООТВЕТСТБУЕОЕ)ЕЦЕ ВЫХОДЫ 1) 4, ; 1-; о 2. о, ) 4 о (и) о4,. 1) устройс е вяЕсли ОшибКа ПРОЦСХОДНт ПО ОДНОМУ ЦЗ ЧЕтНЬ)Х. (ра.эря)ДОБ ае) 9 ,)Я се о о , КОДЯ ст:т, 1 Ое, Ф О е)е = О и процедура коррекцииОтццочной Ое)пЕбки Осугт 1 е твляется анялОГнчнО дешифпятором 6 11 С 5 гее)мяторями)5 СЛУЧЯЕ ВозноЕКНОЫЕНЫЯ Б КОДЕ(35пакета Огптбок Длинь).два Бырабать)ваетСЯ С .= ДНЕЧЕ)оно О Бсос ГЕО КоееОПОМУогенератор 2 ня своем Втором ВыходеБЫ)5 ябятывяЕеГ СИГНяп двойной ОШИОКИт) т)Пги этом сигналы одиночной и 1)еисгетэаБим ОЙ Ошг) б;) к ь)е Бы) я Оятыва)Оеся, т иГнс)л двойной Ояцбк 11 1 тоступь 1 ет ня упрявляюпеие входы селекторов 3 и 4 и наВьг"Од 1 Е Ус УРОЕства о .8 селектОРах)еЕОдуду ДГя ЭНЯЧЕНтт)1 8 Ее 8посо)еу 8паиЕтеих на первые и вторые входы блока 9 с выходов генератора 1 и преобразователя 8 соответственно. С выходов селекторов 3 и 4 эначенця 8 и 81соответственно поступают на входыдешифраторов 5 и б. Дальнейшая процедура коррекции пакета ошибок длиныдва Б соответствии с третьим этапомедекодирования аналогична случаю одиночной ошибки. Исправление ошибок вЕонечетном и четном разрядах кода апроизводится одновременно. По е Ф ОДешцфратором 5 и сум)еаторами 7.1;7.3; 7.5, с нечетньеии номерами исправляется ошцбочцьпг цечетны)1 разряда , а по ее, 1 -0 дешифратором 6 и сум)еяторями 7.2; 7,4; 7.6, с четныминомерами - ошибочный четный разряд(тг.,) кода аБ случае отсутствия ошибок вырабатывается 8 = О. При этом генератор 2на своих выходах не вырабатывает сигналы одиночной, двойной и неисправимой Ое)птбок о Значение Я = 0 через первые входы селекторов 3 и 4 поступаетна входы соответствуюцих дешифраторов5 и б и поскольку в этом случаее= ееЕ = О, корректкьей код а 1 сВеоеодов 10 е 1 о 10 о 2 оо о е е 10 о (П 1) о 10 П.устройства без изменения через входыСУММЯТОРОБ 7 о 1 р 7 о 2,ооу 7 о(П),7 оПВыдается на Выходы 14.1; 14.214(п-е), 14.п устройства,15 случае, когда Ы Ф 0 и це совпадает цц с ОДним цз значений столбцовв матрицах Е) и С, на третьем выходегенератора 2 вырабатывается сигналнеисправимой ошибки, который поступает на выход 13 устройства и на управляюшце входы дешифраторов 5 и б. Приэто)1 блокируется работа ДешиЧ)раторов5 и б (генерируются коды е= еее = 0и ошибочны)1 код а") с входов 10.1;10 о 210.(п), 10.п устройствабеэ.,изменения через Входы сумматоров7.) 029 оо, 7.(П), 7.П ВЬЕДЯЮТСяна выходы 14.1; 14,214,(п),)Яким образом предлагаемое устройстьо по сряв 11 ецию с известным обеспечцваст геовьгеынцую достоверность выдао Баемой информации. Исправление ипакетов опвбок в предлагаемом устройстве против п)е 2 пакетов ошибок в известном устройстве позволяет практически вдвое повысить надежность обработки информации кода аф 1).1578812 Формула изобретения 1 Б 3 с 1Б 000 111 010 111 001 101 000 110 110 101 0.1 0 001 1 10000 3 1011 .3 10111 5 00001 5 00001 7 11111 7 11111 9 00100 9 00100 11 11101 11 11101 13 01000 0 13 1 14 1 15 0 16 0 17 0 18 0 19 0 20 0 21 1 22 1 23 0 001100 101011 000101 110011 11000001110 010100 001111 000011 111010 010001 1 0112 0103 0014 1005 1006 0117 1018 0119 00010 11 011 10012.0 О 1 13 01 15 11 15. 11 17 00 17 00 19 01 19 01 21 00 21 00 23 11 23 11 0000 0111 0111 0001 0001 1 11111 0100 0100 110110 Составитель С. ЛевцчевТехред М Моргентал Корректор Л. Патай Редактор С. Лисица Тираж 660 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., д. 4/5Заказ 1922 Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина, 101 устройство для исправления пакета ошибок длины два, содержащее первьп 1 и второй дешифраторы, генератор синдрома, и входов, которого (где и - раз-, рядность входного кода) объединены с первыми входами первого блока суммматоров по модулю два и являются инфор- О мационными входами устройства, генератор сигналов ошибок, первьп, второй, и третий выходы которого являются со- . ответствующими выходами сигналов ошиоок устройства выходы сумматоров по модулю два являются информационными выходами устройства, о т л и ч а ю - щ е е с я тем, что, с целью повьпления достоверности исправляемой информации, в пего введены преобразователь кода, второй блок сумматоров по модулю два, первьп и второй селекторы, первые входы которых объединены с одноименными входами преобразователя кодов, первыми входами второго блокасумматоров по модулю два, входами генератора сигналов ошибок и подключены к выходам генератора синдрома,вторые входы второго блока сумматоров помодулю два и первого селектора объединены и подключены к соответствующимвыходам преобразователя кодов, третьивходы первого и второго селекторовобъединены и соединены с вторым. выходом сигнала ошибок устройства, выходы первого и второго селекторов соединены соответственно с первыми входами первого и второго дешифраторов,вторые входы которых объединены иподключены к третьему выходу сигналаошибок устройства, выходы первого ивторого дешифраторов подключены соответственно к вторым входам четных инечетных сумматоров по модулю двапервого блока, вторые входы второгосепектора соединены с выходами второгосумматора по модулю два.1