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

 

ОПИСАН ИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (11) 537450

Союз Советских

Социалистических

Республик (61) Дополнительное к авт. свид-ву (22) Заявлено 23.10 74 (21) 2070461/24 (51) М. Кл. Н04 (3/02 с присоединением заявки №

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

Совета Министров СССР по делам изобретений и открытии (23) Приоритет (43) ОпУбликовано 30.11.76, Бюллетень ¹ 44 (53) ДК 681.325 (088,8) (46) Дата опубликования описания 05,08.77 (72) Авторы изобретения

А. А. Давыдов и Г. М. Тененгольц (71) Заявитель

Ордена Ленина институт проблем улравления,автоматики и телемеханики (54) УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ КОДА

Изобретение относится к области вычислительной техники.

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

Однако оии ие обеспечивают высокого быстродействия при приеме информации из канала связи.

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

Такое уст1тойсттко : также имеет невысокое быстродействие лри приеме,.информации из канала связи, что объясняется больтпим количеством избыточных символов, неабходиваах известному устройству для исправления пакета.,несимметричных ошибок.

Цель изобретения — повышение быстродействия устройства.

Это достигается тем, что в устройство дополнительно введены блок обнаружения искажений вычета вевешенной суммы, блок определения вида искажений, блок подсчета количества единиц, коммутатор, блок вычисления наименьшего по абсолютной величине вычета, итеративный сумматор, накапливающий сумматор, блок деления и блок груплирования символов. Вход блока группировапия символов соединен с выходом входного регистра, а выход — с входом блока обнаружения искажений вычета взвешенной суммы, с входом блока сумми1р рования по модулю два, с первым входом блока подсчета количества единиц, с первым входом блока вычисления наименьшего по абсолютной величине вычета и с первым входом блока коррекции. Выход блока обнаружения искажений вычета взвец1спшой суммы подключен к первому входу блока определения вида искажений, второй вход которого подсоединен к выходу блока сравнения с нулем, первый выход блока определения вида искажений связан с вторым входом блока коррекции, третий и четвертый входы которого подключены соответственно к первому выходу итеративного сумматора и к выходу "частное" блока деления. Второй выход блока определения вида искажений соединен с управляющим входом блока деления, входы "делитель" и "делимое" которого связаны соответствел537450

101, °,r ; т=1-4для)=в +(Фэ,,а-g. r = О, В блоке 3 осуществляется коррекция в соответПри этом равенство i = 0 означает, что ошибки ствии с соотношениями:

1х)сположены в первом множестве контрольных

f (к-)-чв) (к-g-1в) (j)

СИМВОЛОВ.

Il p a M e p. Пусть w = 3 )(= 6. e= 3. Ýò 5 х(н-)-(-()в) = х() ()a) (r) а ("длв 1=(z. означает, что m = 6, P = 2 = 64 (так как 2wk + 1

37), z = Jloga m l = 3 и что предлагаемое,

)(=Х ®е пакет а(а(мметричных ошибок длины (3 - 1) 3 + 1 =

47, а также некоторые пакеты длины 8 И9, Пусть в 9о ((-2-О) (4 2 о) а <2) х =х ® канал связи передана последовательность

Поэтому х = х 9 1 = (110) + (110) =

П (3) (3) 1 «в) - 1()- -1 10(1) (() (1) (2) (2) (а) (3) (3) (4) (4)

Х Х Х X X Х Х (000) .

"1 "2 "3 " 2 а 2 1 2

<9) (3) (4) (4) (У) (5) (Г) (C) (С) (С) (1) (Т) (1) x = x ф (. = (111) + (110) = (001)

)(х„)(х х х х )(х(4) = х(4)@ Е(" = (111) + (001) =(110), х х „(8)„(9)x (9) х(9) ъ ь

Таким образом, пакет ошибок длины 9 действитель3 1 2 3 в Гв 4в33 в"2 1 (р т) 9(т) о1о и1 000 (90 004 б01 900 Если вид искажений (О-в1 или 1-0) иэ2 Р ° . в в."вв ((4) Х(2Ъ )((Р X(4) X(A Х(Ь) X(l) вестен заранее и третье множество контрольных символов содержит только инверсию символа ф„,.(, то проверяется равенство 3 = )) . Если оно нарушено, то считается, что информационн)я в<вв . <в> . в воЮ: часть принята беэ ошибок. Если же это равенство с-. . вьшолняетая,:ТО считается,:что Ошибки в инфоринформация контрольйые символы

МаЦИОННОй Части ИМЕЮТ МЕСТвО ТОГДа И ТОЛЬКО ада, Предположим, что в данном сеансе связи имели когда хотя:бь(одна Иэ сумм (,,.:: Ие равна нулю и

И.)."

МЕСТО ОШИбКИ ВИДа О 1 И ИЭ.Каиапа ПРИНЯта ОДНОВРЕМЕННО ЧИСЛО: Le ИМЕЕтв За1)аМЕЕ ОПРЕДЕЛЕНпоследовательность, иый знак, а имейно -1,в >:О,(если ийсавжеийя вида ,очо (и ((о и(<4< 00» 100+(0 оо ооиоо9ОО . 0 1) rr Le<0 (при" иска)((енияхвядя1 —.0).В

Хв1в Х 2) X(3) X 4 «(fl X(4) X t% ХС®> Х(9) В Мр(Ъ) ОСтаЛЬНОМ НРОцЕСС дЕКОдиреиаНИя:ПРОвХОд)ГГ аиаЛО(т.е. искажены 3,4 и 5-я группы информа1)ионных символов). В блоке 5 первые 27 принятых иэ канала символов разбиваются на 9 *— — х() ... Ством иэобретениЯ пеРед известными УстРойствами

„<9> Э, „по ) в "бл, 2 и 7 В Явллетси новы пенне быстРодействиЯ пРИ пРиеме блоке 2 вычисйяются ммы (®: M информашп иэ канала свЯзи, что О()ъЯСНЯетсЯ меньшим количеством избыточных символов, необходимых предлагаемому устройству для исправления () (9О) (3) ) (9) пакета несимметричйых ошибок. Введем Обозначе9х =но; Е *х @)((1) x = ((о. НИЯ: ) яр в ГК 3а КОЛИ!фС Вов ИзбЫТОЧНЫХ ДВОИЧ)нв Х

В блоке 7 подсчитывается количество единиц s символов, необходимых дпя .Исправления пакета

: каждой группе информапйонных символов. Ре- несимметричных оцв(бок соответственно предлагаезультаты подсчета: мым устройством и иэвест))йм устройством, вы(9) (2) (Я (4) (У), (Ь) бранным за прототип, в — длина исправляемого

В =4„R =3, =2,% в(=5) Я двоичного пакета несимметричных ощибовк;

В блоке 12 вычисляется вычет 45 Ч кояиЧествО ИнфбрмапионНЫХ симВОЛОВ (6) (3 (4) (3) (2) (1)1 Тогда r»a = ч + 4E — 2. Для предлагаемого

Э устройства в = ( — 1) w + 1 где в, w — целые

-p (od Р) = r es т+,4 6-12 < эпос(64) = числа.

„е» т(т(аа ь4) =7. Оскольку двоичная за:ПО <оль О, щ,„r» =ew+))Оя, (2v+1) (+) log, Jlog, (2ч+1) (f,где )А(суть ближайшее целое число, не, письВ содержитчетыренуля,то Н (Ъ ) = Я.2." Т).. Меньше А. Поскольку в w(1и J воо (2v+ 1)

1- 9- - 1?О. 1 з

1су)цественно меньше Ч, то r„. существенно

Крометого, 1 МОИ (-ФО; ь--чьО, е.-- ФО. Пол И(м" r = 178 р = (в — 1) ° 10 + 1

ПоэтомУ блок 11 ОИРСДелнет что )rMee Mecro . Следовательйо, в = 3. искажение в информационной части, причем иска 3а счет сокращения иэбьпочности повышается жение вида 0 1, так как I > О. В блоке 7 скорость приема информации из канала связи. вычисляютсявеличины 1.):.(. ° =2, L,=2, L,= 1, в блоке 10 — сумма L + L + L =2+ 2+ 1 = 5

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

Пастноеотделения 7 на 5 sблоке13равно1 (т.е. Устройство для декодированиЯ кола нспРав

I= 1), .а остаток 2. Поскольку L, равно остатку, то о ляющего пакеты ошибок, содержащее входной ре537450

" осуществляется в соответствии с выражениями

1ЛГ 1 ц) т (к+ь 5-1ь)

g х,) (),() 5 о,"

1=0 ((1»- j-1Ь)» 1

Суммы В® (где j =0,1,...Ь- 1) с(выходаблока2 поступают на входы блоков 7 и 14. В блоке 14 все суммы С() поочередно сравниваются с нулем.

Информация о результате сравнения из,блока 14 поступает на второй вход блока 11.

В блоке 7 подсчитывается количество единиц й(1) в каждой группе информационных символов х ()) . (Эти гру)п)ы попадают из блока 5). Через коммутатор 9 коды чисел В ) доступают в .блок 12, гда вычисляется наимсныпнй по абсолютной величине вычет:Lz в соответствии с выражением:

)ф(СК- j- (1-1) В)

L =раз Ki EЯ -B (111од P), в где ге» А (mod Р) — наименьппй по абсолютной вели пня) вычет числа А по модулю Р;

1тб1 .; .3=-. Å х p..

120 1

Вычет L с выхода блока 12 поступает на вход

"делимое" блока 13 и на вход блока 14. В блоке 14 вычет 1.в сравнивается с нулем. . Информация о результате сравнения подается из блока 14 на второй вход блока 11.

В блоке 11 на основе информации, поступаювцей из блоков 6 и 14, определяется наличие искажения в информационной части и вид искажения.

При этом логические схемы, входящие в состав блока 11, работают по следующему алгоритму, г .Й4 1 f )

Если Л (В ).Ф 7» 3 t)<, то имеют место

1ооо искажения во втором или третьем множестве контрольных символов, а информщионная часть принята без ошибок.

Я-" 1 (Если Й (В ) = Е 2. 11., то считвется, что

1 о 1 второе и трепе множество контрольных символов приняты без ошибок и анализируются результаты сравнения с нулем сумм U и вычета 1.(з,. Если () ("о ) » (() (в - )

8 =P =.. = С =оо...о, тоощибок в ь

w рббврядоь информационной части нет. Если же, хотя бы одна ив сумм E p оЕа 0 и ЕФ О, то считается. что

wpo(3pg 4ов имеют место опп(бки в информационной части, При этом в данном сеансе связи были искажения вида

0- 1, если 1. )0 и искажения вида 1-«0, если

Ls (О.

Информация о наличии ошибок в информационной части и о виде искажения поступает с выходов блока 11 на вход 15 блока 3 и на управляющий вход 20 блока 13. Если ошибки в инфоумационной части отсутствуют, то инфорл(ационные символы, не претерпев изменений в блоке 3, поступают на выход устройства. При наличии ошибок в информационной части предполагается1 чт() пакет

Ошибок исказил группы символов: . (К В-1В - () 11)) (К+В-1В-() 12))

) 1

Х,х (K1 В-1» (b 1)) (Кдв-((+1)Ь) (К+Ь-(1+1)Ь-)) х,х,,х (К+Ь-(111)В-) )

",Х Опредвta ление величин i, r осуществляется устроиством и следующим образом.

В блоке 7 подсчитываются величины 1ь, 1.„.,р

L(((, где L представляет собой количество един)(ц (5 в чч-разрядном векторе С(); ч((j)

1, -Ze (1 о,,..., в-1)

Величины 1 поступают иэ блока 7 в сумматоI В1

p»r8 и 10. В блоке 10 вычисляется сумма D ( 1по которая поступает на вход 21 "делитель" блока 13 деления. В блоке 13 на основе соотношения!

-г

f LÂi 1 д4 (1 "бВ- ) ((о (правильного, в частности, нз-эа выбора величины

P) вычисляется величина 1 и подготавливаются) исходные данные для вычисления величины r. Для этого в блоке 13 осуществляется делениеабсолют1 ной величины числа Lz на сумму ь Частное or ! Е (ьв депеиия (zе, пеппе часть дроби в-< ) преи.

, (,ставляет собой, (и не передае1ся в блок 3, а

35 В-1 остаток (т.е. величина ((, )- Я g ..)является

j-o исходным данным для вычисления r и под: ется на первый вход схемы 4 сравнения. В итеративном сумматоре 8 последовательно, шаг за шагом, выи числяются суммы вида g („, (где u = 0, 1, 2 ...).

5о

При этом на каждом u — м шаге к полученной в сумматоре 8 сумме прибавляется очередное слагае45 мое Lu (увелнчивая и на единицу), н новая сумма поступает на второй вход схемы 4 сравнения, Как только величины, попадающие на первый и второй, u В-1 входы схемы 4, станут равны (т,е., Я 1.= ) Ь, i-o в

)иО на выходе схемы 4 появляется сигнал, останавливающий работу сумматора 8. Величина u" (т.е. коли- чество сложений, осуществленных сумматором 8) равна величине r. Эта величина с выхода сумматора 8 поступает на вход 17 блока 3.

В блоке 3 на основе информации, полученной от блоков 11, 13 и 8, осуществляется коррекция искаженных символов в соответствии с соотноше(к-т-t))) (K-т- в) (й) лоразрядное сложение по модулю два: t = i для537450

ЦНИИПИ Заказ 954/502 Тираж; 842

Подписное

Филиал ППП "Цвтент™, г, Ужгород. Ул, Проектная, 4 гистр, блок коррекции, схему сравнения, блок суммирования по модулю два, выход которого соединен с первым входом блока сравнения с нулем, выход блока коррекции соединен с выходом устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства, оно содержит блок обнаружения искажений вычета взвешенной суммы, блок определения вида искажений, блок подсчета количества единиц, коммутатор, блок вычисления наиьаньшего по абсолютной величине вычета, итеративный сумматор, накапливатощий сумматор, блок. деления и блок групнировання символов, в7цщ .которого соединен с выходом входного разрисуя; а: аьтход связан с входом блока обнаружения искажиитй;;вычета взвешенной суммы, с входом блок» суьамиуования по модулю два, с первым .. входом . блока подсчета количества ! единиц, с — первым входам блока вычислен ияя наименьшего по абсолютной величине вычета и с первым входом блока к оррекции, выход блока обнаружения искажений вычета взвешенной суммы подключен к первому входу блока определештл вида искажений, второй вход которого подсоединен к выходу блока сравнения с нулем, первый выход блока определения вида искажений связан с вторым входом блока коррекции, третий и четвертый входы которого подключены

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

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

29 накапливающего "сумматора и к информационному входу итеративного сумматора.

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

1. Питерсон У, Коды, исправляющие ошибки.

25 М., "Мир", 1964, рис. 10. 1,с, 215, рис. 10.5. C. 222.

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