Устройство для декодирования кода Советский патент 1976 года по МПК H04L3/02 

(54) УСТРОЙСТВО ДЛЯ ДЕКОДИЮВАНИЯ КОДА j0,1,-- ,р i t jsh-vi, .-.-.B-tnpH этом равенство t s 0 означает, что оцшбки расположешл в первом множестве контрольных CJiNfflOnOB. Пример. Пусть W 3, k 6, в 3. Это означает, что m 6, Р 2 64 (так как 2wk + 1в 37), Z Jlogj m ( 3 и что предлагаемое устройство позволяет исправить любой одиночный пакет асимметричных ошибок длины (3-1)3 + 1 7, а также некоторые пакеты длины 8 и 9. Пусть в канал связи передана последова1ельнос1ъ Ч) (1) (1) (2) (i) (Z) (3 { (4) 4) Х AJ Xj Х X,j j X X . Х Xj .. (4) () (П (f 0„ «) (О (Т) (Т), (7) А л, Л X, Д, Х Xj )( Xj Xj , t&) (в.,(8), (9) (9)(9) ) Pt л л, л,л. А, X I ООС ОО1 -lob -MpSQio ( ооо -«о оо-с ooi 100 -, - - w чиу . «ХЧ «У 7п А т ) ){fl ХО) ИНФОРМАЦИЯ ооноо юр 110 оси )ш ) в NoW информацияконтрОль1а 1е символы Предположим, что в данном сеансе связи имели место ошибки вида и из.канала принята последовательность ,о-(о )-(( H-fo лд ooi 100 oo-fqawgoio х x 7«i х x xf« 9 M (т.е. искажены 3,4 и 5-я группы информа11иош{ых а{мволов). В блоке 5 первые 27 принятых из канала символов разеваются т 9 груш - - Эти группы поступают в блоки 2 и 7. В блоке 2 вычисляются суммы t : .®Х.0;г Х ®Х ©Х--Мт в блоке 7 подсчиашается количество единиц в . каждой группе информациоюсш: символов. Ре зультаты подсчета: M,i,4,n2,R« U U;R K.. В блоке 12 вычисляется вычет Ь з« FT ( т) ги V -p4-modP)pis7f 2 6--f2ftnod 54) Fes Т(тоаб4)7. Поскольку двоичная заiпись 5 содержит четыре нуля, таМ.,(В ) Szn : iioКроме того, L О и ( 6; О. « t Поэтому блок 11 определяет, чю имеет мест искажение в информационной части, 1фичем иска жение вида , так как L, 0. В блоке 7 вычисляются величины Lj:L,-2, L,2, L, 1, в блоке 10 - сумма L, + L, + L, 2 + 2 + 1 5. Частное от деления 7 на 5 в блоке 13 равно 1 (т.е 1 1), а остаток 2. Поскольку Ц равно остатку, 0. В блоке 3 осуществляется коррекция в соответвии с соотношениями: (K-J-iB(K-,--isl jUJ . . CK-j-(i-OB). ..CK-j-() ® j-f,2. А Следовательно, (6-О-1-) „(6-0-1-J-) j((-o) ,(6-1-0) gg j(6-i-«).(«-2-0 ф g (2) Поэтому Г ° (110) + (ПО) ООО). х) Е (111)+(110) (001). х (111)+ (001) (110). аким образом, пакет ошибок длины 9 действительо исправлен. Если вид искажений ( или ) изестен заранее и третье множество контрольных имволов содержит только инверсию символа „, , то проверяется равенство L. . Если но нарушено, то считается, что информационная асть принята беэ оишбок. Если же зто равежтво ьшолкяется, то считается, что оцшбки в инфорационной части имеют место тогда и только тргда, огда хотя бы, одаа из сумм . не рдвна нулю и одновременно число Ц имее определенный знак, а именно L О (есяя искажения вида ) и (при искажениях вида ).В остальном процесс декодирования щюходит аналогично изложенному. Основным технико-экономическим пpeи fyщeством изобретения перед известными устройствами является првыцюние быстродействия при приеме информации из канала связи, что объясняется меньшим кодичес-гвомизбьпгочных символов, необходимых предлагаемому устройству для исправления пакета несиМметр Ывд) . Введем обозначения: Гдр, г„зд г- кбяйдаство избыточных двоичных символов, необхощмцх д|ш и пакета несимметричных О1ииб(яё с()1ответствещ(о предлагаемым устройством и известйИЕМ устройством, выбрашсым за прототип, в - длина исправляемого даоичного пакета несимметричных ошибок; V - количество информационных символов. Тогда изв V + 4t - 2. Для предлагаемого устройства t (в - 1) W + 1, где в, w- целые числа. + Jtog, (2v + l)(+ log,Jlog,(2v + l) I Ьгде )A{ суть ближайшее целое число, не. меньше А. Поскольку в w 1и J log, (2v+ 1) существенно меньше V, то г„р. сушествешго меньше Так, при v 100, w 10, В 21. Получим: г„дв 178, С (в - 1)-10 + 1, следовательно, в 3. За счет со1фа1цения избыточности повышается ocqpocTb Щ)иема инфсфМации из канала связи. Формула изо-бретения Устройство для декодирования кода, исправляницего пакеты ошибок, содержашее входной реосуществляется в соответствия с выражениями C Aeef«K b «bcexi.jj J)Jif, ( J«o,,...,ь-, « E Л, 9r,2,....VV К1-8-j-1 i ) Суммы t (где j 0,1, ...Ь 1) с|выхода блока 2 поступают,иа входы блоков 7 и 14. В блоке 14 все суммы поочередно сравниваются с нулем. Информация о результате сравнения из блока 14 поступает на второй вход блока И. В блоке 7 подсчитьшается количество единиц R в каждой группе информационных символов . (Эти гругаш попадают из блока 5). Через коммутатор 9 коды чисел в поступают в .блок 12, где вычисляется наимсташий по абсолютной величине вычет L в соответствии с вырйжеш ем: . L, re5pl:iCH - - - B-/(it,od), i- -.о где ге| А (mod Р) - наименьишй по абсЬлют1Й)й величине вычет числа А по модулю Р; i t nvi .- , -.B.i: г.. I 110 Вычет Lg с выхода блока 12 поступает на вход делимое блока 13 и на вход блока 14. В блстсе 14 вычет Lg сравнивается с нулем. Информация о результате сравнения подается из блока 14 на второй вход блока 11. В блоке 11 на основе информации, поступающей из блоков б и 14, определяется наличие искажения в информационюй част и вид искажения. При этом логические |Схемы, входящие в состав б1лока 11, работают по следующему алгоритму. ,. 4 t , Если (NO(В /Е Я TI; ; ,то имеют место искажения во второмшш третьем множестве контрольных шмнолов, а информациошшя часть принята без ошибок. k-( Если N Св ) . S . ад с штается, что -iro второе и третье М1южество контрольных символов п жняты без ошибок и анализируются ре льтаты равнения с нулем сумм tJ и вычета iLe,. Если ,(-о)(«).(B-i) „ „ В -е --..-е 00... о , то ошибок в W реязряДоЬ информационной части нет. Если же, хотя бы одна из сумм г V OQ..O и Lg О, то считается, что Wp«ipgftOB имеют место ошибки в информационной части. При этом в данном сеансе связи были искажения вида , если Lg 0 и искажения вида , если . Информация о наличии ошибок в информационной части и о виде искажения поступает с выходов блока 11 на вход 15 блока 3 и на управляю щий вход 20 блока 13. Если ошибки в информационной части отсутствуют, то информационные символы, не протерпев изменений в блоке 3, поступают на выход устройства. При наличии ошибок в инфоймацирнной части предполагается что пакет ошибок исказил группы символов; (к в-i«-()cк B-1B-( + 2)) А, Л,. . .J „(KtB-iB-tb-l ((- + 1)В) ((i+-l)b-o ..... ГОпреде/ ление величин i, г осуществляется устройством следующим образом. В блоке 7 подсчитываются величины ,./ Lf,f , где LJ представляет собой количество у разрядаом векторе (,i,. , Величины Lj поступают из блока 7 в суммато. I вн ры8 к 10. В блоке 10 вычисляется сумма; , которая поступает на вход 21 делитель блока 1-3 деления. В блоке 13 на осноие соотношения ; (...UB.H(U.. ,), (правильного, в частности, из-за выбора величины Р) вычисляется величина i и подготавливаются исходные данные для вычисления величины г. Для этого в блоке 13 осуществляется деление абсолютной величины числа Le на сумму j Частное ct I Ць. 1 деления (т.е. целая часть дроби в-ч) представляет собой , и не передае1ся в блок 3, а Iви остаток (т.е. величина | L. |-i S Ь является исходным данным для вычисления г и подается на первый вход схемы 4 сравнения. В итеративном сумматоре 8 последовательно, шаг за шагом, вычисляются суммы вида.2 Ь - (где и О, 1,2 ...). При этом на каждом и-м шаге к полученной в сумматоре 8 сумме прибавляется очередное слагаемоё LU (увеличивая и на единицу), и новая сумма поступает на второй вход схемы 4 сравнения. Как только величины, попадающие на первый и второй i Uв- ходы схемы 4, станут равны (т.е.; 2 Ь-«1Ь l-i2il,-l ij,o V J.o а выходе схемы 4 появляется сигнал, остапавливащий работу сумматора 8. Величина и (т.е. колиестно сложений, осуществленных сумматором 8) авна величине г. Эта величина с выхода сумматора 8 оступает на вход 17 блока 3. В блоке 3 на основе информации, полученной от блоков И, 13 и 8, осуи1ествляется коррекция искаженных шмволов в соответствии с соотноше,(K-,--tBlg g( CK-t-iB лоразрядное сложение по модулю два: t i длягестр, блок коррекции, схему q aBHeHHfl, блок суммофования по модулю два, выход которого соединен с первым входе блока сравнения с нулем, выход блока ксфрекции соединен с выходом уст ройства, отличающееся тем, что, с целью повышения быстродействия устройства, ош) содержит блок обнаружения искажений взвешеннш суммь, блок определения вида искажений, блок подсчета количества единиц, коммутатор, блок вычисления наименьшего по абсолютист величине вычета, итератавньШ сумматор, накапливающий сумматр|, блок; д елешя и блок групп1фования символов, втсод; соединен с выходом входного решс1||я 11.вЦ9(од связан с входом блока обнаружения иск ясеяй шчета взвешенной суммы, с ю(опом блрка с} 1«1ч фоваш1я по модулю даа, с {Первым входом %рка подсчета количества |единиц, с первым 9 С0дом блока вычислекия наименьшего по абсолютной величине вычета и с первым входом блока коррекции, выход блока обнаруже1фя искажений вычета вэвешеннс суммы подключен к первому входу блока (шределеш вида искажений, второй вход котсфого подсоедиюн к выходу блока сравнения с иупем, первый выход блока отфеделения вида искажений связан с вт(фым входом блока коррекции, третий и четвертый входы подключены

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

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

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

накапливакицегр умматора и к информационному входу итеративното «умматора.

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

1.ПИтерсон У. Коды, исправляющие ошибки. М., М1ф, 1964, рис. 10. 1,с. 215, рис. 10.5. с. 222.

2.Патент США №3.648.238, кл 340-146,1,1972 (прототип).