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

 

:::.;.: .. :-„, I O и И С А H И Е

1 ИЗОБРЕТЕН ИЯ (11) 562931 г

\ б (61) Дополнительное к авт, саид-ву (22) Заявлено26.08.75 (21) 2166333/24 с присоединением заявки № (23) Приоритет (51) М. Кл.е

H 041 1/10

06 Г 11/08

Гасударственный камитет

Саветв Миниатрав СССР па делам иеабретений н аткрытий

Я) УДК 681,3.04..5 (088.8) (43) Опубликовано 25.06.77Бюллетеиь № 23 (45) Дата опубликования описания 25.08.7-7 (72) Автори изобретения

Г. Л, Тауглих и Г. N. Тененгольц

Ордена Ленина институт проблем управления (71) Заявитель

{54) УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯ ПАКЕТОВ ОШИБОК

Изобретение относится к электронным дискретным устройствам систем автоматики, телемеханики, связи и вычислительной техники и предназначено для исправления однократных и двукратных пакетов ошибок, возникающих при передаче информации по каналам связи.

Известно устройство для исправления пакетов ошибок, содержащее буферный регистр, кодирующий регистр, сумматоры )lj, Это устройство позволяет исправить только одиночный пакет ошибок и конструкция его очень сложна.

Наиболее близким техническим решением к данному изобретению является устройство для исправления пакетов ошибок, содержащее входной регистр, первый кодирующий регистр и блок управления f2).

Процедура исправления ошибок заключается в отыскании безошибочного интервала длины Ъ (Ъ- число информационных ра:-урядов) в принятой тт — разрядной последовательности. При этом последовательность, находящаяся во входном регистре, сдвигается циклически на один разряд (такой сдвиг будем в дальнейшем называть тактом), а затем поступает в кодирующий регистр, ко торый определяет значения tl - % провероч ных символов по первым к разрядам содержимого входного регистра. Пороговый блок проверяет, возможно ли представить последовательность иэ этих тт - 1 проверочных символов в виде г или менее пакетов длины

Ъ (l -максимальное число исправляемых коl0 дом пакетов ошибок длины, не превосходящей Ь ). Если эту последовательность возможно представить в виде Р или менее пакетов ошибок длины Ь, то обнаружение ошибок заканчивается. В противном случае со15 держимое входного регистра сдвигается еще на один разряд и описанная процедура повторяется вновь. При этом на параметры кола накладывается следующее ограничение:

» т (Ь). (1)

20 Недостатком известного устройства являются большие временные затраты, так как число проверок, осуществляемых пороговым блоком может достигать значения тт» а при

1 каждой такой проверке производится ?т +1

25 тактов, так что общее количество тактов

562931 составляет величину, кратную ll и в самом худшем случае ности ает величины порядка

П . К роме того, при . 2 о корость исходного кода, рлмыя Р меньше 0,5 (с учетом приведенного выше неравенства (1), что депе ет использование известного устройства практически нецелесообразным, Цепью изобретения является расширение функционапьных возможностей за счет осушествпения исправпения двойных пакетов .ошибок и повышение быстродействия устройства.

Достигается это благодаря тому, что в устройство введены регистр пакета, второй и третий кодируюшие регистры, сумма- !Б торы, блок анализа совпадений пакетов, три блока определения нечап и длин пакетных конфигураций, блок коммутации и арифметический блок, причем, вход устройства соединен с первым входом блока коммута- 26 ции, выходы которого соединены с входами входного регистра, регистра пакета и с первыми входами четырех сумматоров. Выходы трех сумматоров соединены соответ ственно с вторым, третьим и четвертым входами блока коммутации и с входами соответствующих кодируюших регистров, выходы сдвига которых соединены соответственно с вторыми входами сумматоров, а разрядные выходы - соединены с входами блока анализа совпадения пакетов. Выход регистра пакета соединен с пятым входом блока коммутации, Три выхода блоке анапиза совпадения пакетов соединены соответ ственно с входами трех блоков опредепения начал и -длин пакетов, выходы которых соединены с входами арифметического бпока. Четвертый выход блока анапиза совпадения пакетов и выход арифметического блока соединены с соответствуюшими входа- 40 ми блока управления, выходы которых соединены соответственно с упревпяюшими входами арифметического бпока и блока комму« тации. Выход входного регистра, соединен . с вторым входом четвертого сумматора, 45 выход которого является выходом устройся ва.

Исправпяюшая способность предпагаемого устройства основана на испопьзовании двоичных циклических кодов дпины,П=Л„п пз, 50 с числом йн<рормационных символов, g=(g,-Ц(-Ц(и, ) с порождаюшиммногочленом у (х) = H,OK.(ê - f, х - r,x" g), исправляющих одиночные и двойные пакеты ошибок дпил 55 ны, не превосходящей 6(rn„"-„1 ц = i,lp; e, с п, с rl,взаимно простые числа) .

На чертеже представлена блок-схема предлагаемого устройства.

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

60 бок содержит регистр 1 пакета, блок коммутации 2, сумматоры 3-6, кодируют не регистры 7-9, входной регистр 10, бпок

11 анализа совпадений пакетов, блоки 12=

14 определения начал и длин пакетных конфигураций, арифметический блок 15, бпок управления 16.

Бпоки 2, 11 могут быть выпопнены на логических элементах, блоки 12, 13, 1 (на двух счетчиках, дешифраторе и погических элементах, бпок 15 может представпять собой арифметическое устройство с небольшой памятью, работающее по заданной программе, блок 16 может быть обычным программным устройством, основанным на распределении импульсов и содержащим логические схемы.

Рассмотрим процесс исправпения одино"-." ных и двойных пакетов ошибок дпины Q вих. В(х) и х В„(к)+ x B,(x). (2) где О< 3,3<7), степени многочпенов 3(к), 3Ä(x) Ъ (х) меньше Ф () = и 1п ) ((tnz >) 16jjfot3 - цепая часть CI

"() — наибопьшее натуральное чиспо, опредепяемое из условия не существует на- турапьного чиспа, явпяюшегося решением системы уравнений 4 О п1о" тпрр, ч -. - од "",, 1 =" 5Ъ Об т „ (U 4 Ч ф 9 ) U,V, Ч = (, 2, ), rtte а(. и Р принимают спедуюшие значения:

oh=<,2, -,Ъ < =-(5-<)),-(о-2),.-. — (.

Допустим передено сообщение А,,d.„,, где с(- "0,4 (1 "-о, л-f) В дапьнейшем испап— зуется многочпенная запись и передаваемое сообщение имеет вид 1(к)=с(+О,А+ ", d „Х

Предположим, в начале произошеп одиночный ипи двойной пакет ошибок вида (2), тогда на вход устройства поступит -искаженное сообщение 1(х) = 5 + сМ x w + м-4

Q ) о„„х

;. Дпя удобства изложения введены следующие определения:

Проекцией $ назван остаток от деле(ц) . ния (Х) на Х " -1, U =1,2,3.

Пакетной конфигурацией проекции 6 назван ненулевой участок этой проекции, расположенный вне серии нупей длины, не меньшей Ъ-1 и 0=1,2,3. В -разрядном кодируюшем регистре — ый разряд находится левее (правее) 1 -го разряда и обозначает <)(> ), если выпопняется условие

j1+P7n08 tn„(q q+p modmq), О <ф < Ь; равейство С = $ означает, что выполняется сравнение a = тг1ос1 ти„, ц = <, 2, g ° г течение первых П тактов (один такт соответствует сдвигу содержимого регистра на один разряд) блок 16 подает на бпок

2 сигнал, по которому входная поспедоватепьность (х), начиная с Оо, поступает в регистр10, а через сумматоры 3,4,5 — соот562931

О

15 ственно в сумматорах 4, 5. Затем регистры 1 и 7 блокируются и содержимое регист20 ров 8, 9 сдвигается влево до тех пор, пока в первом разряде у них не будут стоять символы "1 а последние „- b (О =2,3) разрядов не будут заполнены нулями (при этом в блоках 12, 13, 14 подсчитывается

25 обшее количество тактов). Если содержимое первых Ь разрядов регистров 8, 9 совпадает между собой, а в остальных разрядах стоят нули, то как и в случае одиночного пакета ошибок блок 11 подает на вход блока 16 сигнал, согласно которому в блоке 15 вычисляется начало второго пакета ошибок.В (х). При исправлении двойного

2 пакета ошиббк содержимое регистра 1 0 . начинает сдвигаться вправо и в моменты, соответствующие началам В< (х) и В (х3 содержимое регистра 1 и одного из регистров 8, 9 соответственно в течение Ь так!Гов поступает на сумматор 6.

> б) -! З . В блоке 15 производится

О) сравнение длин пакетных конфигураций5 и (2) с О: если эти обе величины меньше b, то выбирается любой из регистров 7, 8, в противном случае, выбирается тот регистр(7 или 8),у которого длина пакетной конфигурации больше, допустим это регистр

7, определяются следуюшие величины: С— наименьший по абсолютной величине вычет ! числа 1, н о4ии й-c. Затем соответствуюший сигнал с блока 16 посылается на вход блока 2 и первые й-с разрядов регистра

7 циклически сдвигаются влево и заносят ся в регистр 1, далее содержимое 9 циклически сдвигается влево и, начиная с { 3+ ч )—

55 го такта симВОлОВ, . занОсится В реГистр

1. Таким образом, в регистре 1 содержит ся B,ff). Далее все опепаиии производятся дН; аНаЛОГИЧНО П.а, ПРИ ЭТОМ, ЕСЛИ В П а СОДЕРжимое первых О разрядов Регисты "7 скла

60 дывается с содержимым первых 4 разрядов

Ветственно В регистры 7,8,9, где происходит получение проекций 5 (» =1,2,3), (v) > !!ачиная с (Т!+1)-го такта, в каждой проекции определяются начало и длина пакетной конфигурации 5 < " (u =1, 2,3), Содержимое регистров 7,8,9 циклически сдвигается влево (по сигналу с блока 16 в блоке 2 разол кнуты все связи между регистрами) до тех пор, пока крайний левый разряд каждого из них не будет содержать "1", которому будет предшествовать серия нулей длины, не менее Q -1; по сигналу с блока 11 в блоках 12, 13, 14 определяются 3„(0=1,2,3) — начала пакетных конфигураций, а также длины расположенных вне пакетных конфигураций серий нулей соответственно. Эта информация поступает из блоков 12, 13, 14 в блок 15, где вычисляются длины пакетных конфигураций

GL = rn - „гдеХ -длина указанной выше и и> серии нулей (ц =1, 2,3).

При этом в блоке 11 производится попарное сравнение первых b разрядов регистров 7,8,9, длины пакетных конфигураций сравниваются в блоке 15. Если все длины равны между собой, первые Ь разрядов регистров 7,8,9 совпадают, а в остальных разрядах стоят нули, то блок 11 фиксирует, что произошел одиночный пакет ошибок, посылая соответствующий сигнал на вход блока 16. Последний посылает сигнал в блок 15, в котором . определяется начало > одиночного пакета ошибок в виде

3. „З„+С,З„ гм о3 г!,, (3) (ч,u) где C„" 3 гг и г> и, с„о т оД т и,С21гподттц, (v,и !»

=- Q дО,5 тг и, Qv = » понг>и (в данном случае (V =l, V =2 I .

Затем входная последовательность, находяшаяся в регистре 10, начинает сдвигаться вправо и, начиная с (tf-3 )-го такта, содержимое одного из кодируюших регистров в течение tl тактов поступает через блок 2 на сумматор 6.

На этом исправление одиночного пакета ошибок заканчивается.

Если же длина одной из проекций больше 0, то в блоке 15 производится попарное сра нение начал пакетных конфигураций, а имен

»О, проверяется выполнение сравнений

3„ Д„.гной и (здесь и в дальнейшем и Ч Ь W,u,è, à =1,2,3,).

Допустим выполняется сравнение

)р) tl1Q/n (положим для определенности, что проекции .>, „ -т находятся соответственно в регистрах 7,8,9). Далее в блоке (г,<)

15 вычисляется значение !=С„ +С тлО где С,С,З определяются также,как и в (Л,1)

В> ражении {3); определяется величина которая сравнивается с 5 по и1-.> "Л >

МОДУЛЮ >П .

При этом может иметь место один из сле . дуюших трех случаев.

a) !,:-З, н адт . B блоке 15 определяется проекция, у которой пакетная конфигурация имеет максимальную длину (допустим эта проекция есть с> ",>; соответствующий ° сигнал поступает на вход блока 16.Сигнал с последнего подается на вход блока 2, после чего осушествля :.-.тоя сдвиг содержимого регистра 7 на "С разрядов влево. При этом содержимое регистра 7 подается в ре» гистр 1 (таким образом, в регистре 1 содержится первый пакет ошибок В(4 ),и кроме того складывается с содержимым первых Ь разрядов регистров 8, 9 соответ 562931 рег11стров В, ", то в данном случае регистр

7 заменяется на рег стр 1, а регистр 9 на регистр 7, I в) з < 2 . Здесь все операции производятся аналогично п.а.

Если на предыдуших этапах исправление ошибок не закончено, то в блоке 15 определяется другая пара проекций, для которых

3>> = 3 Ч тт1 Оа 1т >Х, Если же и на этом этапе исправление

° ошибок не закончено, то по соответствуюшему сигналу с блока 16 в регистре 8 производятся циклические сдвиги влево (их число не меньше Ъ ) до тех пор, пока в первом разряде не будет стоять 1", а

I обшее количество сдвигов 2 (начиная с первого сдвига проекции Б г) ), подсчитываемое в блоке 13,, »е будет удовлетворять сравнению „= — гтт>ос>тт (эта проверка осу шествляется D блоке 15). B случае выполнения этого сравнения в блоке 15 выбирается регистр (7 или 8), соответствуюшая проекция которого имеет большую длину, если эти длины равны, то выбирается лю бой из этих регистров, и содержимое первых ц разрядов выбранного регистра считается символами В (х), Далее все операции производятся аналогично описанным этапам. Если последнее сравнение >е имеет места„то 13 блоке 15 произво>н гся предыдушая процедура.

Следует особо отметить частный слу«ай (он может им ть место при исправлении двойного пакета ошибок), когда одна из си) проекции, например, S = p. Это ознсч >ает„что

В„(х) =B (X) и 3 =:- 3 тт)од тт„.

Рассмотрим кратко процесс 11сит>с>11 I(ния двойного пакета ошибок в этом случае, l) блоке 15 производится сравнение tlr»r;Ä>I (uI (A ) пакетных конфигураций о и S >,пусть эти проекции находятся соотт>с>то"с)зо.t ttо» регистрах 8 и 9) . Если,„=-,х> тттод >1, т> определяется ) -начало B (х ) — )н> фс>р л> — ле вида (3); затем содержи,>ое регttcтров

8, 9 сдвигают вле)зо (число такта>з должно быть не меньше Ъ ) до тех иор, иона в первом разряде не будет стоять ".! ", и как и выше определяется начач» H2(x).

Если же J p3 NOdrttr товблоко 1 ) с)нр»1 деляк>тся начала обоих и;1„;- т>н в 1>идс;

-) =-c 3 + c J тттодт),3=(3 t r J тт>ос()), ч г и ч г где С„=- 1ттто «ттт

= Отт)о Д )) C lmo cj n, O т)т ос) ттт, С

q ттт о с) тт> „, С:- 0 1тт o d тт,,, С 2 1 тт1 о о 1 ьОтттой m (>,v) >,ч,,х> )

= Этоа„, З, =- „-оа„, и производят иснравление двойного >1,>кс>та, Процесс исправления ошибок для цикличегкого кода с параметрами )),=2,т) — 3, 1, =5, т) =30, ттт.1=15, )312 =10, ó =6. П>орождаюший многочлен имеет вид >" (X ) = q + >I,;;2> Х + )I ь .13 Ь 1т Zo г1 гг

+Х .3Х -> Х +Х +Х .>.Х, а длина исправляемых одиночных и двойных пакетов ошибок 3=2, Пусть было передано сообшение

f =100101001000000100101001000000, а в канале произошел двойной пакет ошибок

I. =-000011000000000001000000000000 (в многочленной форме имеем: f =х (1+х)+х")

У тогда на вход предлагаемого устройства поступит искаженное сообшение

$=100110pp10000p01011p1i3010p0ppp

После первых 30 тактов в регистрах 7, 8, 9 содержатся соответственно проекции;

00101 1000000000; 00001 10100; 000010.

Затем в блоках 12, 13, 14 и 15 определяются начала и длины пакетных конфигураций проекций З„=2, 2=4, з 1.-.,=4, < г =4, d.з 1, при этом содержимое регистров

7, 8, 9 циклически сдвигают влево до тех пор, пока не будет обнаружена серия нулей длины, не менее Ъ-1, и в первом раз"ряде у этих регистров не будет стоять 1.

t содержимое регистров 7, 8, 9 в резуль.-:::те этой операции имеет соответствен ro вид;

1 0 1 100000000000; 1 101000000;

3 О()000, 1 ак как пакетные конфигурации не c>)I=.« падают между собой, то имеет место дв AII0й пакет ошибок. > шее в блокс: .1 "> осушествляется следую" IQH последс>вательность операций. Произr3:>дитс я сравнени» :. с>ча>1 пакет>и >х конфигуI, > II)I Й, 11н>1! о >>няотс Я сос1внение > -" .> )т1 оо )1 г ъ 1т т., = " Р>ос1..!; вычисляется величина j С 3+

1 2 т)1>)Дт> r де С, — 1 тт1ос> )т3 С: 0 ?13 О с1 т1 с3,2)

С.. = » >ос) т>. С .—: >-) т>тос> 1тт ) > - 33tTTQCI 112

C -.1,I.=)Î, 32 =4,Л=Ф, 13,Z)

> >

4 )I ределяется величина 3,: — 3 тттод)т1, 31=4.

Производится сравнение 3 с 2 по модулю

1 тп,, Itìååò место случай, описанный в п.с>: )пределяется величина С - наименьи»;о «бС-О:. К"I..IOrr ВЕЛИЧИНЕ ВЫЧЕТ ЧИСЛа

> 0 3 -,1;,(! .I>>> »,>к> )т) С вЂ” 2

1 >к «ак д — с =-(),ro содержимое регист )>ь>, :. двигается циклически влево на Ъ =2 р;..-ряда, и на следующем такте С=2 симво 1а;>анс>сятся в регистр 1 .

Далее содержимое регистра 1 (оно име>зт»ид 2) складывается с содержанием перви х Ъ-- 2 разрядов регистров В, 9; затем нос>1» цп е регистры сдвигаются до тех пор, пока в первом разряде у них не будет

60 стоять 1.

562931

10

Подписное каз 1870/1 70

Тираж 815

Филиал АППП "Патент", r. Ужгород, ул. Проектная, 4

В конце этого этапа содержимое регистров 8, 9 имест соответственновид:

1000000000, 100000. Так как содержимое этих регистров совпадает между собОй, то оно Определяе3 второй пакет,ощйбок, а начало его определяется в блоке 15. (3,2)

)33одЛ, где Э = (J =УЗ =g.Тогда 3 = 9+(0 333ОЮО, 3- 17

Использование предложенного устройст ва позволяет производить анализ конфигураций одиночных и двойных пакетов параллель-но в трех кодируюших регистрах, количест во разрядов в которых намного меньше

11 (длины сообщений) и вычислять синдром только Один раз).

Таким образом, общее количество тактов при декодировании оценивается величиной порядка 11, что существенно меньше, чем у прототипа. Кроме того, нет необходимости накладывать на параметры исполь зуемого кода очень жесткое ограничение вида (1), что позволяет использовать предлагаемое устройство в широком диапазоне скоростей.

Ф ормула изобретения

Устройство для исправления пакетов ошибок, содержащее входной регистр, первый кодирующий регистр и блох управле ния, о т л и ч а ю ш е е с я тем, что, с целью расширения фунхциональных воз»можностей и повышения быстродействия, в устройство введены регистр пакета, второй и третий кодируюшие регистры, сумма7 торы, блок анализа совпадений пакетов, три блока определения начал и длин пакет» ных конфигураций, блок коммутации и арифметический блок, причем вход устройства соединен с первым входом блока коммутации, выходы которого соединены с входами входного регистра, регистра пакета и с первыми входами четырех сумматоров, выходы трех сумматоров соединены соответственно с вторым, третьим

ы четвертым входами блока коммутации и с входамм соотъетству)ошнх кодирующих ðåгистров, выходы сдвиг«которых соедгнены соответственно с вторыми входами сум15 маторов, а разрядные выходы - соединены с входами блока анализа совпадения пакетов, выход регистра пакета соединен с пятым входом блока коммутации, три выхода блока анализа совпадения пакетов соедине2» ны соответственно с входами трех блоковопределения начал и длин пакетов, выходы которых соединены с входами арифметичес кого блока, четвертый выход блока анализа совпадения пакетов и выход арифметического

25 блока соединены ссоответствующими вхо- дами блока управления, выходы которого соединены соответственно с управляющими входами арифметического блока и блока коммутации, выход входного регистра сое30 динен со вторым входом четвертого сумматора, выход которого является выходом устройства.

Источники информации, принятые во внимание при экспертизе:

Э5 1. Питерсон У. Коды, исправляющие ошибки, М., Мир, 1964, стр. 263-265.

2. Авторское свидетельство СССР

No 200894, М. кл . (3 06 F 1 1/08, 1966.