Устройство для исправления пакетов ошибок Советский патент 1977 года по МПК H03M13/51 G06F11/08 

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

1

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

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

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

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

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

t1 f ()).(1)

Недостатком известного устройства являются большие временные затраты, так как число проверок, ос}тцествляемых пороговым блоком может достигать значения 71 а при каждой такой проверке производится И +1 тактов, так что общее количество тактов составлиет величину, к})атную T-J и в самом худи/ем случае М(х;т1иает. величины 1юрядка ТТ . Кроме того, при скорость исходного кода, раьн.-ш меньше 0,5 (с учетом приведенного выше не1эавенства (.1), чтЬ дел&ет использование известного устройства практически нецелесообразным. Целью изобретения является расширение функциональных возможностей за счет осу шествления исправления двойных пакетов -ошибок и повышение быстродействия устрой ства. Достигается это благодари тому, что в устройство введены регистр пакета, второй и третий кодирующие регистры, сумметоры, блок анализа совпадений пакетов, три блока определения начал и длин пакет ных конфигураций, блок коммутации и арифметический блок, причем,вход устройства соединен с первым входом блока коммутации, выходы которого соединены с входами входного регистра, регистра пакета и с первыми входами четырех сумматоров. Выходы трех сумматоров соединены соответ ственно с вторым, третьим и четвертым : входами блока коммутации и с входами соответствующих кодирующих регистров, выходы сдвига которых соединены соответ ственно с вторыми входами сумматоров, а разрядные выходы - соединены с входами блока анализа совпадения пакетов. Выход регистра пакета соединен с пятым входом блока коммутации. Три выхода блока анали за совпадения пакетов соединены соотве1 ственно с входами трех блоков определе- ния начал и -длин пакетов, выходы которы соединены с входами арифметического блока. Четвертый выход блока анализа совпадения пакетов и выход арифметического блока соединены с соответствующими входа ми блока управления, выходы которых соединены соответственно с управляющими вхо дами арифметического блока и блока комму тации. Выход входного регистра,соединен с вторым входом четвертого сумматора, выход которого является выходом устройсту ва. Исправляющая способность предлагаемого устройств а основана на использовании ДВОИЧНЫХ циклических кодов длины. с числом информационныхсимволов . ),-iJff)i-lKn -l) с порождающим многочленом .O/.(,),x4-jj, исправпя- ющих одиночные и двойные пакеты ошибок длины, не превосходящей fe(, .nj взаимно простые числа). На чертеже представлена блок-схема предлагаемого устройства. Устройство для исправления пакетов оши бок содержит регистр 1 пакета, блок коммутации-2 , сумматоры 3-6, кодируюи:.ие регистры 7-9, входной регистр 10, блок 11 анализа совпадений пакетов, блоки 1214 определения начал и длин пакетных конфигураций, арифметический блок 15, блок управления 16. Блоки 2, 11 могут быть выполнены на логических элементах, блоки 12, 13, двух счетчиках, дешифраторе и логических элементах, блок 15 может предста лять собой арифметическое устройство с небольшой памятью, работающее по задан йой программе, блок 16 может быть обычным программным устройством, основанным на распределении импульсов и содержащим логические схемы. Рассмотрим процесс исправления одино ных и двойных пакетов ошибок длины t) ви (Х) к (Х.) + хВ (х), (2) где 0$ 3,, степени многочленов В(х) ) меньше t ; t:tnirt|b C ij 3) - целая часть d , t) - наибольшее натуральное число, оп ределяемое из условия: не существует натурального числа, являющегося решением системы уравнений О тпо d тПу, S ««. w ой п ,tU V ф NW j U, 1, 2,3 ), где Л. и Ь пpинимaюV следующие значения: cX.---f,2..,.,V-/, li -(t--),-ro-.V..,--i,. Допустим передано сообщение ciQ.ct,. &. - , где 0,(1 :o,tl-T).B дальнейшем используется многочленная запись и передаваемое сообщение имеет вид iiiC)-di( .,- с(. Х Предположим, is начале произошёл оди1 очный или двойной пакет ошибок вида (2), тогда на вход устройства поступитискаженное сообщение ().): o(.,-v oi, x-v....,- . V. Для удобства изложения введены следукмцие определения: Проекцией S назван остаток от деления Кх) на X -1, J 1,2,3. Пакетной конфигурацией проекции S назван ненулевой участок этой проекции, расположенный вне серии нулей длины, не меньшей 1)-1 и ,2,3. В -разрядном кодирующем регистре 1 - ый разряд нахо- дится левее (правее) j -го разряда и обозначает ) ее ли выполняется условие jrivp шоЗ-т (i SJ+ ), О f t); равенство -t Y означает, что выполняется сравнение i j тпос7 и /, 2 i tJ течение первых П тактов (один такт соответствует сдвигу содержимого регистра нао дин разряд) блок 16 подает на блок 2 сигнал, по которому входная последовательность ( it), начиная с а, поступает в регистр 10, а через сумматоры 3,4,5- соотвотственло в jjepHCTpbi 7,8,9, где происходит получение проекций (u 1,2,3/. Начиная с (n + такта, в каждой проекции определяются начало и длина пакетной конфигурации ,3). Содержимое регистров 7,8,9 циклически, сдвигается влево (по сигналу с блока 16 в блоке 2 разок кнуты все связи между регистрами) до тех пор, пока крайний левый разряд каждого из них не будет содер жать I, которому будет предшествовать серия нулей длины, не менее f -Ij по сип налу с блока 11 в блоках 12, 13, 14 определяются Л (,2,з) - начала пакетны .конфигураций, а также длины расположенных вне пакетных конфигураций серий нуле соответственно. Эта информация поступает из блоков 12, 13 , 14 в блок 15, где вычисляются длины пакетных конфигураций сС ,где JJ-длина указанной выше серии нулей (и 1, 2,3), При этом в блоке 11 производится попарное сравнение первых Ь разрядов регистров 7,8,9, длины пакетных конфигураций сравниваются в блоке 15. Если все длины равны между собой, первые Ъ разрядов регистров 7,8,9 совпадают, а в остальных разрядах стоят нули, то блок 11 фиксирует, что произошел одиночный пакет ошибок, посылая соответствующий сигнал на вход блока 16. Последний посылает сиг нал в блок 15, в котором ..определяется начало 3 одиночного пакета ошибок в виде . (3) где С.,2 -moc}my, С., f OtriOcf n C sltnod-n С О -mod TrtOj Jv 3v-mocl u Гв данном случае (,). Затем входная последовательность, находящаяся в регистре 10, начинает сдвигаться вправо и, начиная с ( ТТ - J )-го такта, содержимое одного из кодирующих регистров в течение О тактовпоступает через блок 2 на сумматор 6. На этом исправление одиночного пакета ошибок заканчивается. Если же длина одной из проекций больше Ь то в блоке 15 производится попарное сра& нение начал пакетных конфигураций, а име по, проверяется выполнение сравнений d гЗ тпойт (здесь и в дальнейшем (J i W/u.v,W 1,2,3.). Допустим выполняется сравнение (лз (положим для определенности что проекции 5/Кд З находятся соответ-. ственно в регистрах 7,8,9). Далее в блок 15 вычисляется значение -C.jJ., тп С.С З - определяются также,как и в определяется га .1 раже НИИ I-Jwodflij которая сравнивается с 3 по модулю tHj . При этом может иметь место один из . дующих трех случаев. а)3 Wj . В блоке 15 определяется проекция, у которой пакетная конфигурация имеет максимальную длину (допустим эта проекция есть 5 ); соответствующий сигнал поступает на вход блока 16.Сигнал с последнего подается на вход блока 2, после чего осуществля-отся сдвиг содержимого регистра 7 на Ъ } азрядов влево. При этом содержимое регистра 7 подается в ре гистр 1 (таким образом, в регистре 1 содержится первый пшсет ошибок BW) .и кроме того складывается с содержимым первых Ъ разрядов регистров 8, 9 соответственно в сумматорах 4, 5. Затем регистры 1 и 7 блокируются и содержимое регистров 8, 9 сдвигается влево до тех пор, пока в первом разряде у них не будут стоять символы последние tn j - Ъ ( ,3) разрядов не будут заполнены нулями (при этом в блоках 12, 13, 14 подсчитывается общее количество тактов). Если содержимое первых b разрядов регистров 8, 9 совпадает между собой, а в остальных разрядах стоят нули, то как и в случае одино ного пакета ошибок блок 11 подает на вход блока 16 сигнал, согласно которому в блоке 15 вычисляется начало второго пакета ошибок .(зс). При исправлении двойного пакета ошибок содержимое регистра 10 начинает сдвигаться вправо и в моменты, соответствующие началам В W и , содержимое регистра 1 и одного из регистров 8, 9 соответственно в течение Ъ такгов поступает на сумматор 6. б)3 Л,. .В блоке 15 производится сравнение длин пакетных конфигурацийЬ и S ей: если эти обе величины меньше Ъ; то выбирается любой из регистров 7, 8, в противном случае, выбирается тот регистр(7 или 8),у которого длина пакетной конфигурации больше.допустим это регистр 7, определяются следующие величины: Снаименьщий по абсолютной величине вычет числа 3 Jjtnodn tj-C . Затем соответствующий сигнал с блока 16 посылается на вход бло.ка 2 и первые t)-C разрядов регистра 7 цикличес.ки сдвигаются влево и заносятся в регистр 1, далее содержимое 9 1иклически сдвигается влево и начиная с (t))такта символов г заносится в регистр 1- Таким образом, в регистре 1 содержит ся ). Далее все операции п роизводятся аналогично п.а, при этом,если в п. а содержимое первых Ь разрядов регистоа 7 скла дывается с содержимым первых i) разрядов

8, О,

то в датпюм случае регистр

регистров

7 аак5ецяется на регистр 1, а регистр 9 .на регистр 7,

в) Здесь все операции производятся аналогично п.а.

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

Если же и на этом этапе исправление -ошибок не закончено, то по соответствующему сигналу с блока 16 в регистре 8 производятся циклически:е сдвиги влево (их число не меньше Ь ) До тех пор, пока в первом разряде не будет стоять 1, а общее количество сдвигов 3 (начиная с первого сдвига проекции ), подсчитываемое в блоке 13, не будет удовлетворять сравнениюЗ (эта проверка осу шествляегся в блохе 15;, В случае выпо лнения этого сравнения в блоке 15 выбирается регистр (7 или В), соответствующая проекция которого имеет большую длину, если эти длины равны, то выбирается лю бой из этих регистров, и содержимое первых t) разрядов выбранного регистра считается символами В(х), Далее все операции производятся аналогично описан- . ным этапам. Если последнее сравнение не имеет места, то в блоке 15 произвоштся предыдущая процедура.

Следует особо отметить частный случай (он может иметь место при исправлении двойного пакета ошибок), когда одна из проекций, например, S 0. Это означает, что и J - Jmoc) т,

Рассмотрим кратко цропссс и ;-И1:)а)л(иия двойного пакета ошибок в этом случае, 1 блоке 15 производится сраннение пач.чл пакетных конфигураций S н s ,пус;тг, эги проекции находятся cooTiiOTcTBOHiio li pernui pax 8 и 9) . Если 3 3 tnod ri,j го определяется 3-чшчало В(7) - по форчгуле вида (з); затем содержи юе регч-стров 8, 9 сдвигают влево (число тактов лолжно быть не меньше {з ) яо тех пор, иока в первом разряде не будет стоять и

как и выше определяется начато Ь2(

Если же Jyf J mocJuu, тэвблоке 1 о :)прО деляются начала обоик иакетои п nn/it : 3s.C 3 C2a -modti,D5C, j tC J mocfTj где с 1 TnoJ-n,

С Отпобп..О гОтойт -fTrrodTn, С; Qmodn, С ; 1 wod л,, с:, н

50тпо 3 тп

л/

,v)

-, (,

v

а vjv -rnodn

и производят исЦравленяе аакота,, Процесс исправления ошибок для циклшчес.

кого кода с параметрамиТ1 2,, , П 30,, tn2 10,. Порождающий

многочлен имеет вид оСХ ) г-(-,. х t х 4 х + т -(У 16 т го 21 Z2

X +Х -tX -fX м-Л -t-X -fX,

а длина исправляемых одиночных и двойных пакетов ошибок .

ПустЬ было передано сообщение I 100101001000000100101001000000, а в канале произошел двойной пакет ошибок t 000011000000000001000000000000 (в многочленной форме имеем: f х-(1+х) тогда на вход предлагаемого устройства поступит искаженное сообщение

Г 1001100.01000000101101001000000

, А.

Поспе первых 30 тактов в регистрах 7,8,9 содержатся соответственно проекции; ОО101 ЮОООООООО; 0000110100; 000010.

Затем в блоках 12, 13, 14 и 15 определяются начала и длины пакетных конфигураций проекций , , ,4, d., , при этом содержимое регистров 7, 8, 9 циклически сдвигают влево до тех пор, пока не будет обнаружена серия нулей длины, не менее t-1, и в первом раэ.™ ряде у этих регистров не будет стоять l; содержимое регистров 7, 8, 9 Б резуль.-ате этой операции имеет соответственно видг 101100ООООООООО; 11О10ООООО; 1ООООО.

Так как пакетные конфигурации не со& падают между собой , то имеет место даи, ной пакет ошибок,

;1а«1.,е Б блоке .1. П осуществляется следуЮ111ая последовагел(,ность операций. Проиэводится сравнение пача.11 пакетных конфигу- {joiiiui. Выиоиияется сравнение 3 J , т.-, .J.S 1 tncxr.i; вычисляется величина ,:. V т 0(5и,где цН-1ггтос гп.,, С.,нО-той-ц,

С,2}

- Л j-mod Tij ,

- Гпюс п,С нОтг1осЗтп ,Л

Z

,л.4. с : fO

Оирецеляется величина J.J - 3 .j 41 хзнзводится сравнение З с модулю Tn.f , Имеет место случай, описанный в п. 6 Т,,. 1ределяется величина С- наимень- ,su ill; абсч.)лютной величине вычет числа И.,-. и(. модулю С 2.

1ак как Ъ - С () ,го содержимое регистра 7 сцгзигается циклически влево на t 2 рйо;}яла, и на следующем такте С 2 символа ..(УНОСЯТСЯ в регистр 1.

Далее содержимое регистра 1 (оно имеет вид 2/ складывается с содержанием первых U разрядов регистров 8, 9; затем последние регистры сдвигаются до тех пор, ггока Б первом разряде у них не будет стоять 1.