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

(51) М. Кл,е Н 0414 1/10 6 06 Р 11/08 Гасударстеениый комитет Соната Министров СССР аа делам изобретений н открытий(43) Опубликовано 25,06.77 Бюллетевь23 (45) Дата опубликования описания 25.08.77(72) Авторы иаобретения Г, Л, Тауглих и Г. М. Тененгольц Ордена Ленина институт проблем управления(54) УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯ ПАКЕТОВ ОШИБОК 1Изобретение относится к электроннымдискретным устройствам систем автоматики, телемеханики, связи и вычислительнойтехники и предназначено для исправленияоднократных и двукратных пакетов ошибок,возникаюших при передаче информации поканалам связи,Известно устройство для исправленияпакетов ошибок, содеожашее буферный регистр, кодируюший регистр, сумматоры 1,11,Это устройство позволяет исправить толькоодиночный пакет ошибок и конструкция егоочень сложна.Наиболее близким техническим решениемк данному изобретению является устройстводля исправления пакетов ошибок, содержащеевходной регистр, первый кодирующий регистри блок управления 21,Процедура исправления ошибок заключается в отыскании безошибочного интерваладлины Ъ (Ъ- число информационных разрядов) в принятой тт - разрядной последовательности, При этом последовательность,находяшаяся во входном регистре, сдвигается циклически на один разряд (такой сдвиг будем в дальнейшем называть тактом), а затем поступает в кодируюший регистр, ко торый определяет значения тт - % провероч ных символов по первым к разрядам содер жимого входного регистра, Пороговый блокпроверяет, возможно ли представить последовательность иэ этих тт - Ь проверочных символов в виде г или менее пакетов длины "й ( 1 -максимальное число исправляемых ко О дом пакетов ошибок длины, не превосходяшей Ь ). Если эту последовательность возможно представить в виде Р или менее пакетов ошибок длины Ь , то обнаружение ошибок заканчивается. В противном случае со держимое входного регистра сдвигаетсяеше на один разряд и описанная процедура повторчется вновь. При этом на параметры кода накладывается следуюшее ограничение:ттЗт(фЬ) (120 Недостатком известного устройства являются большие временные затраты, так как число проверок, осуществляемых пороговым блоком может достигать значения Я, а при каждой такой проверке производится тт +1 25 тактов, так что обшее количество тактовственно в сумматорах 4, 5. Затем регистры 1 и 7 блокируются и содержилчое регист 20ров 8, 9 сдвигается влево до тех пор, пока в первом разряде у них не будут стоятьсимволы "1" а последние йи- Ь (О =2,3)разрядов не будут заполнены нулями (приэтом в блоках 12, 13, 14 подсчитывается25общее количество тактов). Если содержимоепервых б разрядов регистров 8, 9 совпадает между собой, а в остальных разрядах стоят нули, то как и в случае одиночного пакета ошибок блок 11 подает на входблока 16 сигнал, согласно которому в блоке 15 вычисляется начало второго пакетаошибок.В х). При исправлении двойного2пакета ошибок содержимое регистра 10. начинает сдвигаться вправо и в моментысоответствующие началам В 1 Х И В 260содержимое регистра 1 и одного из регистров 8, 9 соответственно в течение Ь тактовпостпает нв сумматор 6,б/ -5, В блоке 15 производитсяИсравнение длин пакетных конфигураций 5 иР)с о; если эти обе величины меньшеЪ, то выбирается Л 1 обой из регистров 7,8, в противном случае, выбирается тот ре 45 гистр(7 или 8),у которого длина пакетнойконфигурации больше, допустим это регистр7, определяются следующие величины: С -наименьший по абсолютной величине вычетчисла 3-3,ъодвзи Ь-с .Затем соответствуюший сигнал с блока 16 посылается на входблока 2 и первые й-с разрядов регистра7 циклически сдвигаются влево и заносятся в регистр 1, далее содержимое 9 циклически сдвигается влево и,нвчиная с (+1) -55 ГО такта симВОлОВ заносится В регистр1. Таким образом, в регистре 1 содержится В,х). Далее все опеваиии производятсядИ; аНаЛОГИЧНО П,В, ПРИ ЭТОМ, ЕСЛИ В П.а СОДЕРжимое первых Ь разрядов регистоа "7 скла60 дывается с содержимым первых 4 разрядов Ветственно в регистры 7,8,9, где происходит получение проекций 5 ( О =1,2,3),(м)вчиная с (т+1)-го такта, в каждойпроекции определяются начало и длинапакетной конфигурации 5" (О =1, 2,3),Содержимое регистров 7,8,9 циклическисдвигается влево (по сигналу с блока 16в блоке 2 разол кнуты все связи междурегистрами) до тех пор, пока крайний левый разряд каждого из них не будет содер.жать "1", которому будет предшествоватьсерия нулей длины, не менее-1; по сигналу с блока 11 в блоках 12, 13, 14 определяются Э (0=1,2,3) - начала пакетныхконфигураций, а также длины расположенных вне пакетных конфигураций серий нулейсоответственно. Эта информация поступаетиз блоков 12, 13, 14 в блок 15, гдевычисляются длины пакетных конфигурацийд = уп - Е где Хи -длина указанной вышеи исерии нулей (й =1, 23)При этом в блоке 11 производитсяпопврное сравнение первых 5 разрядоврегистров 78,9 длины пакетных конфигураций сравниваются в блоке 15, Если вседлины равны между собой, первые и разрядов регистров 7,8,9 совпадают, а в остальных разрядах стоят нули, то блок 11фиксирует, что произошел одиночный пакетошибок, посылая соответствующий сигнална вход блока 16. Последний посылает сигнал в блок 1 5, в котором определяетсяначалоодиночного пакета ошибок в виде3 3 С 3 мойтч (3)Гч,иЪгде С" 1 той пи, С-Огтод ти,С 2-"подти,(Ч,ЛС,ь О твоа пи, Э= 3 пойи (в данномслучае (0=1, Ч =2).Затем входная последовательность, находящаяся в регистре 10, начинает сдвигаться вправо и, начиная с (Ъ - Э )-готакта, содержимое одного из кодируюшихрегистров в течение Ь тактовпоступаетчерез блок 2 на сумматор 6,На этом исправление одиночного пакетаошибок заканчивается.Если же длина одной из проекций больше Ъто в блоке 15 производится попарное сравнение начал пакетных конфигураций а именно, проверяется выполнение сравненийЗЬДгно 3 и (здесь и в дальнейшеми Фч 4 Фи,ч,и =1,2,3,),Допустим выполняется сравнениеЗр 3 Р 10 сп(положим для определенности,что проекции ., О . находятся соответственно в регистрах 7,8,9), Далее в блоке(г,4)1 5 вы числяется значение 3 = СЗ С Этогде СС 2,3определяются также,как и вг,1)В 1 рвжении (3); определяется величина 1= по 1 которая сравнивается с з по-.людулю п 1При этом может иметь место один из сле,.дуюших трех случаев,а) :-3 щадим, В блоке 15 определяется проекция, у которой пакетная конфигурация имеет максимальную длину (допустим эта проекция есть 5" ); соответствующий сигнал поступает на вход блока 16,Сигнал с последнего подается на вход блока 2, после чего осушествлятся сдвиг содержимого регистра 7 нв С разрядов влево. При этом содержимое регистра 7 подается в ре гистр 1 (таким образом, в регистре 1 содержится первый пакет ошибок ВЬ,и кроме того складывается с содержимымпервых Ъ разрядов регистров 8, 9 соответ регистров Й ", то в данном случае регистр7 заменяется па рег стр 1 а регистр 9,ца регистр 7.1в)2 Здесь все операции производятся аналогично п,а,Если на предыдуших этапах исправлениеошибок не закончено, то в блоке 15 определяется другая пара проекций, для которыхЗо: - 3,тОО тЕсли же и ца этом этапе исправлениеошибок не закончено, то по соответствуюц)ему сигналу с блока 16 в регистре 8производятся цклические сдвиги влево(их число не меньше Е ) до тех пор, покав первом разряде не будет стоять 1 ф, аобшее количество сдвигов2 (начиная спервого сдвига проекции 52) ) подсчитываемое в блоке 13 п це будет удовлетворятьсравнению = -3 2 тпод(эта проверка осушествляется в блоке 15). В случае выполнения этого сравнения в блоке 15 выбирается регистр (7 или 8), соответствуюшаяпроекция котооого имеет большую длину,если эти длины равны, то выбирается любой из этих регистров, и содержимое первых ц разрядов выбранного регистра считается символами В (х), Далее все операции производятся аналогично описанным этапам. Если последнее сравнение еимеет местато в блоке 15 произвоц гсяпредыдущая процедура.Следует особо отметить частный случай(он может иметь место при исправлениидвойного пакета ошибок), когда одна из(и)проекции, например, 5 = О. Это озна ает что/=В (х=.-.оИРассмотрим кратко процесс н рп Пядвойного пакета опибок в этом случае, 15блоке 15 производится сраяение гг(о) (а)пакетных конфигураций 5 ц 5 ,пусть этипроекции находятся соотстет 5 о рогистРах 8 и 9), Если ,=З,х) тиос тп, топределяется ) -начало В(х) - п фо 1 ллле вида (3); затем содержи,ое ртг.стро 18, 9 сдвигают влево число тктов ч)жно быть не меньше Ъ ) до тех пор, окав первом разряде не будет стоять ".1", икак и выше опредецяРтся начаВ (х).Если же 3 г 104)товбпоко 15 пров:4 тподтт, С вОтподт, С = 1 т 1 ос) , С, ььотпос 7 тп,Еч) 1 ч,и)З=Э тпоа ,з, ьз. оаи производят исцравление двойного ,кота,Процесс исправления ошибок для циюпчегкого кода с параметрами)11=2,т - 3, п =5,т =30, Ъ=15, т 2 =10,тт =6. 1 оро)кдаюшиймногочлец имеет вид гСХ) =4 +Х х т Х + х +) 5 ь 4 т га м 22Х +Х 5 Х Х +Х +Х Х,а длина исправляемых одиночных и двойныхпакетов ошибок 3=2,Пусть было передано сообшение=100101001000000100101001000000,а в канале произошел двойной пакет ошибок1 =000011000000000001000000000000(в многочленной форме имеем; 1". =х(1+х)+х")тогда на вход предлагаемого устройствапоступит искаженное сообшение1001100.01000000101101001000000После первых 30 тактов в регистрах 7, 8, 9содержатся соответственно проекции;00101 1000000000; 00001 10100; 000010. 20Затем в блоках 12, 13, 14 и 15 определяются начала и длины пакетных конфигураций проекций ,=2,=4,=4аЕ. 4, 4 2 =4,сЕ. 1, при этом содержимое регистров257, 8, 9 циклически сдвигают влево до техпор, пока не будет обнаружена серия нулейдлины, не менее Ъ, и в первом ра"ряде у этих регистров не будет стоять 1содержимое регистров 7, 8, 9 в резу.п,теэтой операции имеет соответственно вид;101100000000000; 11010000 СО;1 ООООО,1 ак как пакетные конфигурации це сг:падают между собой, то имеет место ду;Апй пакет опибок,Дще в блоке .1 5 осуществляется следуюпая поспедоватен,ность операций. Произвдится сравнеци начал пакетцх конфигу 1"Й 1115 ется с)селнРние Д -" 1 п 0 т2 Ь 1т.,= 1 пос 1; вычисляется величинаЭ-С 3+С1 2)пределяется величина С - наимецьабоо:.к.той величине вычет числа50,) -. и п.пу.ктп С - 21 "к лак д - с =.,то содержимое регистра " сд 5 игается циклически влево ца Ь =2разр 5:а, и ца следующем такте С=2 символа;ансятся в регистр 1.Далее содержимое регистра 1 (оно имеет ьчд 2) складывается с содержанием перва х 2 разрядов регистров 8, 9; затемцосец)е регистры сдвигаются до тех пор,пока в первом разряде у них не будетстоять 1.562931 10 10 Заказ 1870/170 Тираж 8 одп лиал АППП "Патент", г. Ужгород, ул. тная, 4 В конце этого этапа содержимое регистров 8, 9 имест соответственновид:1000000000, 100000. Так как содержимое этих регистров совпадает между собой,то оно определяет второй пакет ,ощйбок,а начало его определяется в блоке 15,)подл,где Э= , 3 =,3=8 Тогда 3 =2+9+0 2)поЮО,Э:1 ГИспользование предложенного устройства позволяет производить анализ конфигураций одиночных и двойных пакетов параллель-.но в трех кодируюших регистрах, количество разрядов в которых намного меньшеЪ (длины сообщений) и вычислять синдромтолько один раз).Таким образом, общее количество тактов при декодировании оценивается велижной порядка 1, что существенно меньше,чем у прототипа, Кроме того, нет необходимости накладывать на параметры используемого кода очень жесткое ограничениевида (1), что позволяет использовать предлагаемое устройство в широком диапазонескоростей. ф ормула изобретения Устройство для исправления пакетов ошибок, содержащее входной регистр, первый кодирующий регистр и блох управле ния, о т л и ч а ю ш е е с я тем, что, с целью расширения фунхциональных воэможностей и повышения быстродействия, в устройство введены регистр пакета, второй и третий кодируюшие регистры, сумма 7 торы, блок анализа совпадений пакетов,три блока определения начал и длин пакетных конфигураций, блок коммутации и арифметический блок, причем вход устройствасоединен с первым входом блока коммутации, выходы которого соединеныс входами входного регистра, регистрапакета и с первыми входами четырехсумматоров, выходы трех сумматоровсоединены соответственно с вторым, третьимы четвертым входами блока коммутации ис входамм соответствующих кодирующих регистрсе, выходы сдвигкоторых соедгнены соответственно с вторыми входами сум 15 маторов, а разрядные выходы - соединеныс входами блока анализа совпадения пакетов, выход регистра пакета соединен с пятым входом блока коммутации, три выходаблока анализа совпадения пакетов соедине 26 ны соответственнос входами трех блоковопределения начал и длин пакетов, выходыкоторых соединены с входами арифметического блока, четвертый выход блока анализасовпадения пакетов и выход арифметического25 блока сОединены ссоответствующими вхо-дами блока управления, выходы которогосоединены соответственно с управляющимивходами арифметического блока и блокакоммутации, выход входного регистра соеЭО динен со вторым входом четвертого сумматора, выход которого является выходомустройства,Источники информации, принятые во внимание при экспертизе:З 5 1. Питерсон У. Коды, исправляющиеошибки, М., Мир, 1964, стр. 263-265.2. Авторское свидетельство СССРМо 200894, М. кл . ф 06 Р 11/08, 1966.