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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и может быть использовано в модулярных арифметических устройствах конвейерного типа. Цель изобретения - упрощение устройства. Устройство для обнаружения и исправления ошибок в интервально-модулярном коде содержит узлы 3, 4, 9 задержки, дешифратор 5 интервального индекса, блоки 6 и 7 вычисления интервального индекса, блок 8 демультиплексоров, блок 10 мультиплексоров, вычитатели 11 и 12 по модулю, блок 13 сумматоров коррекции, дешифратор 14 ошибки, блок 15 памяти и вспомогательные регистры 16 и 17. В устройстве с помощью блоков 6 и 7 вычисления интервального индекса и дешифратора 5 на первом этапе вырабатывается признак наличия ошибки в поступающем интервально-модулярном коде. На последующих этапах на основании полученного признака из блока 15 памяти извлекается информация, позволяющая локализовать и устранить ошибку. Использование при этом более простого, чем в прототипе, алгоритма существенно уменьшает объем оборудования. 1 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (191 (11) 1 4 А1 (51) 5 Н 03 M 13/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

H A ВТОРСКОМЪ/ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР (21) 4428002/24-24 (22) 27.05.88 (46) 07.02.90. Бюл. Ф 5 (71) Научно-исследовательский институт прикладных физических проблем им. А.Н.Севченко (72) Л.Н.Василевич и А.А.Коляда (53) 681.3(088.8) (56) Авторское свидетельство СССР

Ф 1136165, кл. G 06 F 11/08, 1983.

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

Ф 1134941, кл. G 06 F 11/08, 1983.

2 (54) УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ И ИСПРАВЛЕНИЯ ОШИБОК В ИНТЕРВАЛЬНО-ИОДУЛЯРНОМ КОДЕ (57) Изобретение относится к вычислительной технике и может быть использовано в модулярных арифметических устройствах конвейерного типа.

Цель изобретения — упрощение устройства. Устройство для обнаружения и исправления ошибок в интервально-модулярном коде содержит узлы 3, 4.-; 9 задержки, дешифратор 5 интервального

1541784 ф 0 индекса, блоки 6 и 7 вычисления интервального индекса, блок 8 демультиплексоров,. блок 10 мультиплексоров, вычитатели 11 и 12 по модулю, блок

13 сумматоров коррекции, дешифратор

14 ошибки, блок 15 памяти и вспомо,гательные регистры 16 и 17. В устрой стве с помощью блоков 6 и 7 вычисле ния интервального индекса и дешифратора 5 на первом этапе вырабатываетИзобретение оиносится к вычислительной технике и можеТ быть исполь" овано в модулярных арифметических устройствах конвейерного типа для

2Î обнаружения и исправления любых однократных ошибок. !

Целью изобретения является упроще ие устройства.

На чертеже представлена схема уст- 25 ойства для обнаружения и исправления ошибок в интервально-модулярном коде.

Устройство содержит первый 1 и второй 2 информационные входы устройства, первый 3 и второй 4. узлы за,цержки, дешифратор 5 интервального

e M екса, первый 6 и второй 7 блоки

ычисления интервального индекса, лок 8,цемультиплексоров, третий, узел 9 задержки, блок 10 мультиплек15 соров, первый 11 и ".-торой 12 вычитатели по модулю„блок 13 сумматоров коррекции, дешифратор 14 ошибки, блок

15 памяти, первыи 16 и второи 17 вспомогательные регистры, первый 18 и 10 второй 19 информационные выходы и первый 20 и второй 21 сигнальные выходы устройства.

Узел 3 задержки предс.тавляет собой цепочку из (Т + 2)-х последовательно соединенных регистров, разряд-Я0! ностью „ Я В бит, где Т ) 1о1; k(.

i =!

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

13 сумматоров коррекции.

Блок 8 состоит из В =max В,,В„,„ дьмультиплексоров (В„ = ) 1оя m 1, ф

m, — i-й модуль системы счисления (i = 1, 2, ..., k+1) через jxt обозначается наименьшее целое число не меньшее х. ся признак наличия ошибки в поступающем интервально-модулярном коде, На последующих этапах на основании полученного признака.из блока 15 памяти извлекается информация, позволяющая локализовать и устранить ошибку. Использование при этом более простого

Р чем в прототипе, алгоритма существенно уменьшает объем оборудования. 1 ил, Третий узел 9 задержки выполняет задержку на два такта. Блок 10 состоит из Bi! мультиплексоров. Вычитатели 11 и 12 работают соответственно по модулям m è m

Узел задержки 4 представляе- собой цепочку из Т регистров разрядностью В бит. Вход первого регистра цепочки является вторым входом устройства, а выход последнего регистра заведен на первый информационный вход блока 10 мультиплексора;в и входы вычитаемого вычитателей 11 и 12 по модулю.

Узел 9 задержки из двух последовательно соединенных (Вк+ 1)=х разрядных регистров. Вход группы из В!! младших разрядов первого регистра соединен с выходом блока 10 мультиплексоров, вход старшего разряда этого регистра объецинен с управляющим входом блока 10 мультиплексоров и подключен к выхоцу дешифратора 5. Выход группы из В„ младших разрядов второго регистра является вторым информационным выходом устройства, а выход старше разряда данного регистра заведен на вход блокировки блока 9 демультиплексоров и на первый вход дешифратора 14.

Блоки 6 и 7 предназначены для вычисления за Т тактов двухкомпонент" ного кода (! „, !1,< < ) интервально-индексной характеристики Т, (х ) числа х 6 — (0,5 И,,..., j 0,5 Mg q j -11 соот етствующего подаваемому на первый вхоц устройства модулярно> му коду (Х.„,"., „ Х„„!) по правилу к!

$ = X(x )/m;=/Я R;; (Х)+1 /(X, )/1г,-, 1 1 где (1)

Б; („)=-/; jX;,ê /ц!/ш;;1 (2) 6

5 1541784

° /х / /M х,!, jk, k+1; (3) вычет

I(x ) определяется соотношением

К 4 х —.я м,х; +a{< )м

iа(М. с/М ти . /ш,,е е е мс = П Ф (1=k 1 k+1); «() . „к», = /м;,.-,М/;.

Через txj обозначается целая часть числа х, а через /х/ — наименьший неотрицательный вычет, сравнимый с величиной х по модулю ш.

Блоки 6 и 7 имеют Т-каскадную параллельно-конвейерную структуру.

Блок 13 сумматоров коррекции работает по модулям ш „ ш,...,m„„ .Дешифратор 5 является неполным дешифратором второго рода. Блок 15 памяти реализован посредством ПЗУ.

Устройство работает следующим образом.

Операция декодирования интервально -модулярного кода (I ( (е,,...,к„,, z„) ()с;с о,) ««I.

Е„ g (0,1,...,«„, ), i=I,2,...,k+1), поступающего на входы l и 2 устройства, выполняется на Т+3 такта и протекает следующим образом.

На первом такте операции модулярный код {х,.„.,)с„, ) и (k+2)-я циф-.ра — I входного кода поступают соот- ветственно в узлы 3 и 4 задержки, а блоки 6 и 7 начинают вычисление величин и к,„по формулам (1) — (3) которое завершается на Т-м такте. В ходе (Т + 1)-го такта дешифратор 5 по коду (g g к„< ) интервального индекса X(x ) числа вырабатывает признак

l,åñëè l(z ) р t -m -k+2, «Д; (4)

О, где ш . — натуральное число, выбирае(р . мое из условий: ш ) 2ш +k-2 и m() P k-2.

Признак d позволяет установить отсутствие или наличие ошибки в модулярном коде. Признак 1 поступает в узел 9 задержки на два такта и на управляющий вход блока 10 мультиплексоров, благодаря чему на выходе блока 10 мультиплексоров формируется к к (5.) который поступает в узел 9 задержки °

Параллельно с изложенным вычитатели

6 и 7 получают величину Ь ={3,,3„„ ), где

/(.-Т„/m,åñëè I g m òï -k+2;

10 /1 .-Т +m /ш, в остальных случаях; к к

На (Т+2)-м такте из блока 15 памяти по адресу t + ) ? считываЬ»

»(( ется набор величин < K, i-lr где (,к (Я =/-M Е/m -.-« i Я вЂ” пара, удов: етворяющая системе равенств

/ke шк» „/m l + 1/" » и (7)

/(Q m»m„„ /m J + Ы/ш»е О»+(, лри некотором Ы С (О, 1) Если С»

=О то независимо от i f =О.

X+<

В этом случае величине i присваивается значение i--l. В случае, когда система уравнений (7) не имеет решения, из блока 15 памяти считывается набор величин Я, i-1) = Ор 1) . На заключительном (Т+3)-м такте операции. обнаружения и исправления ошибки в коде (y,, ..., g, ?, ) aemmHHsi Я

i-l с первого и второго выходов блока 1 5 памяти поступают соответственно на информационный и управляющий входы блока 8 демультиплексоров, а также на второй и третий входы дешифратора 14, при этом на вход блокировки блока 8 демультиплексоров, и первый вход дешифратора 14 из узла 9 задержки подается признак d определяемый по (4). В результате на выходе блока

"О 8 демультиплексоров получают код (О, О, ..., О, d F, О, ..., 0),а дешифратор 14 формирует сигналы

О, если+8 i-1) = (0,0) и d=l

Г,= в остальных случаях

l,если Б, i-1) = 0, 1) и й=О;

Г=

О, в остальных случаях.

50 КОд {0,0р ° ° ° р О, С1 р О, . ° °, О) к(-)д (Q р ° ° ° р 1() р появляющийся В данный момент на выходе узла 3 задержки, передается в блок 13 сумматоров коррекции, где производится исправле55 ние ошибки, если она содержится в какой-либо из первых k+1-й цифр исходного интервально-модулярного кода.

Значение (k+2)-й цифры (формула (5)) ° выходного интервально-модулярного

154178

CocTRBèT8ëü А „Клюев

Редактор М.Бланар Техред И.Ходанич Корректор Т.Малец

Заказ 290 Тираж .658 Подписное

ЗНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5 производственно-издательский комбинат Патент", r.Óæãoðoä„ ул. Гагарина,101 кода устройства снимается с информационного выхода 19 устройства. При обнаружении во входном коде ошибки, в ходе (Т+3)-ro такта операции на вы5 х де 20 появляется единичный сигнал

Г = 1, причем, если, обнаруженная о ибка не является однократной, то н выходе 21 генерируется сигнал Г,,=

1 отказа от декодирования. В ="-том учае так же как и в случае отсутств я ошибки на информационном:выходе

1 устройства выдается исходный интервально-модулярный код.

Благодаря конвейерной структуре б оков 6 и 7 вычисления интервальн го индекса обращение к устройству м жно производить ежетактно.

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

Устройство для обнаружения и иси авления ошибок и интервально-модул рном коде, содержащее первый и вто=р и узлы задержки, дешифра.тор ошибк, блок мультиплексоров, блок сумма- --

2 торов коррекции, первый и второй вспомогательные регистры, причем пер-в и и второй информационные входы устройства соединены соответственно с входами первого и второго узлов за= 30 держки, выходы группы первого узла задержки соединены с входами перво-" го слагаемого группы блока сумматоров коррекции, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройст-= 3-5 ва, оно содержит дешифратор интервального индекса, первый и второй блоки вьгчисления интервального индекса,, блок демультиплексоров, третий узел задержки, первьФ: и второй @) вычитатели по модулю и блок амятд, причем входы разрядов с первого но

k-й (k — количество информационных символов кода) первого информационного входа устройства соединены с 45 соответствующими входами первого блока вычисления интервального индекса, входы разрядов с первого по (k-1)-й и (k+1)-ro разряда первого информа.ционного ВхОдя устройства. СОединены

I соответственно с входами второго блока вычисления интервального индекса, выход второго узла задержки соединен с первым информационным входом блока мультиплексоров, с входами вычитаемых первого и второго вычитателей по модулю, выход первого блока вычисления интервального индекса соединен с вторым информационным входом блока мультиплексоров, с входом уменьшаемого первого вычитателя по модулю и с первым вхоцом дешифратора интервального индекса, второй вход которого объединен с входом уменьшаемого второго вычитателя по модулю H соединен с выходом второго блока вычисления интервального инцекса, выход дешифратора интервального индекса соединен с управляющим входом блока мультиплексоров и с входом старшего разряда третьего узла задержки, вхоцы младших разрядов которого соединены с выходами разрядов блока мультиплексоров, выходы псрвого и второго вычитателей по модулю соединены соответственно через первый и второй вспомогательные регистры с первым и вторым адресными .входами блока памяти, выход старшего разрядa третьего узла задержки соединен с первым входом дешифратора ошибки и с входом блокировки блока демультиплексоров, выходы группы которого соединены соответственно с входами второго слагае" мого группы блока сумматоров коррекции, выход которого является первым информационным выходом устройства, второй информационный выход которого соединен с выходами младших разрядов третьего узла задержки, первый выход блока памяти соединен с информационным входом блока демультиплексоров и с вторым входом дешифратора ошибки, первый и второй выходы которого являются соответствующими сигнальными выходами устройства, второй выход блока памяти соецинен с управляющим входом блока деиультиплексоров и с .третьим входом дешифратора ошибки..