Мажоритарный декодер

 

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

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

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (22) Занвлено 26. 02. 80 (21) 2888568/18-24 с присоединением заявки М (23) Приоритет (5() . л.

Я 06 11/)2

Н 0З К 19/гЗ н оз к 1з/зг

Мударстванвй квмвтвт

СССР аю двлам кзабувтвик11 к вткфйгткй

Олублмковано 15 ° 12.81 ° бюллетень М 46

Дата опубликования описания 17. 12.81 (5Зу УДК 681.325 (088.8) K. К. Ещин, А. К. Заволокин, В. И. Заровскнй,.А. А. Мошков, И. Ф. Мусатов, В. И. Рейнер н Е. К. Юферова (72) Авторы изобретения

Г (71) Заявитель (54 ) МАИОРИТАРНЫЙ ДЕКОДЕР

Изобретение относится к цифровой вычислительной технике и передаче информации и может быть использовано в ЦВМ, в которых информация передается, хранится или обрабатывается в коррек"ирующем коде, а также в многоканальных системах передачи информации.

В таких системах возникает необходимость исправления кратных ошибок в определенных группах смежных разрядов.

Например, для запоминающих устройств

ЦВМ разработано много типов полупроводниковых интегральных схем, содержащих в одном корпусе оборудование для хранения нескольких 2-8 разрядов большого количества слов. Существуют

13 и другие многоразрядные интегральные схемы ЦВМ, например четырехраэрядный арнфметико-логический блок. Отказ одной из таких схем приведет к искаже20 нню группы из М > 2 смежных разрядов, расположенных на определенных позициях, которые могут рассматриваться как

P-ичный разряд слова, где P = 2 и

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

P.

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

890397

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

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

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

bio модулю 2, где г >(2М+1), где К— число информационных разрядов слова, причем каждый мажоритарный элемент имеет г входов, каждый из которых подключен к выходам соответствующих су пчаторов по модулю 2 (31.

Недостаток известного устройства заключается в его сложности из-за большого числа сумматоров по модулю 2 н сложности мажоритарных элементов с большим числом входов (не мене 2М+

+1) .

Цель изобретения — упрощение декодера, в частности, для случая использования (8М, 4М) корректирующего

35 кода, построенного на основе 8,4 мажоритарно декодируемого корректирующего кода с кодовым расстоянием 3, где 8М вЂ” общее число разрядов кода:

4M — число информационных разрядов

40 за счет уменьшения числа сумматоров (в пересчете на один разряд) и уменьшеня числа входов мажоритарных элементов при сохранении их количества.

Для достижения укаэанной цели

45 мажоритарный декодер, содержащии четыре группы по М мажоритарных элементов, выход каждого из которых подключен к выходу соответствующего двоичного информационного разряда декодера, где М вЂ” число смежных двоичных разрядов, рассматриваемых как P-ичный разряд слова, P =- 2, содержит

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

4 группе — к первой и четвертой группе входов декодера, в третьей группе к первой и четвертой группе входов декодера, а в четвертой группе — к третьей и второй группе входов декодера, вторые входы М-разрядных арифметических сумматоров в первой группе подключены соответственно к пятой и седьмой группе входов, во второй группе — к пятой и восьмой группе входов, в третьей группе — к седьмой и шестой группе входов, а в четвертой группе — к шестой и восьмой группе входов декодера, причем первые входы каждого из М мажоритарных элементов каждой группы подключены к одноименной группе входов декодера, а вторые и третьи входы — к соответствующим выходам первого и второго М-разрядных арифметических сумматоров одноименной группы.

Входной (8М, 4М) корректирующий код для устройство формируется по следующим правилам.

Исходное двоичное 4 М-разрядное слово разбивается на четыре группы по М смежных разрядов в каждой, и каждая такая группа рассматривает я как один P-ичный разряд, где P = 2 . Затем формируется корректирующий код, аналогичный известному двоичному разделимому мажоритарно декодируемому коду (8,4) описанному в t3), только вместо двоичных разрядов используются P-ичные разряды, а вместо операции сложения по модулю 2 — операция арифметического сложения на М-разрядном арифметическом сумматоре с потерей переноса иэ старшего разряда, т.е. по модулю P = 2 . Если P-ичные

М информационные символы обозначить а, b, с, d, то символы корректирующего кода А, В, С, О, Е, F, G, Н формируют по следующим соотношениям:

А = а; В b; С i с; 0 = d; Е à i Ь;

F=C+d; G=a+c; НЬ+4, причем "+" означает операцию сложения по модулю P. Например, двоичный код 10011101 при необходимости исправления ошибки, заключающейся в искаже- . нии пары смежных разрядов (первого и второго, третьего и четвертого и т.д.) рассматривается как код 2131 в системе счисления с основанием P = 2

= 4(а = 2, b.= 1, с 3, d 1). Иэ этого кода по указанным соотношениям формируется код 21313012, который представляется двоичным кодом

100lll0lll000110.

890397 разряда по соотношениям à = E — В и а = Я вЂ” С соответственно, в сумматорах 2, 2 вычисляются значения в = Е-А и в = Н-3 и т.д. При наличии. во входной информации одного искаженного P-ичного разряда, т.е. одной искаженной группы из М двоичных разрядов, в каждом мажоритарном элементе 5-8 искажена информация не более, р чем на одном входе — либо непосредственно с искаженной группы входов, либо с выхода соответствующего сумматора 1-4. Так, для рассмотренного примера при искажении информации например в четвертом P-ичном разряде 94(U), получены неправильные ре- зультаты на выходах сумматоров 2 и 3 и на третьи входы мажоритарных эле2„ ментов 6„,...,6,„, 7,,,...,7 „, а также щ на первые входы мажоритар;:ых элементов 8,...,8> поступит неправильная информация. Поскольку на двух других входах каждого мажоритарного элемента 5-8 информация правильная, на всех

2$ выходах сформирован правильный результат.

Технико-экономический эффект предлагаемого декодера заключается в его простоте по сравнению с известным — у декодером. При этом в нем используются более простые мажоритарные элемен" ты (с меньшим числом входов) . Действительно, в известном декодере для

4 уп- исправления М-кратной ошибки информационный разряд необходимо сформироBGTb Р 7> 2М + раз, IIpH 9T0M мажори» тарные элементы должны иметь г входов (например, при М 4, 9). В предлагаемом декодере каждый мажоритарный элемент имеет 3 входа независимо отвеличины М. Объем оборудования арифметических сумматоров также меньше, чем в известном (необходимо иметь

h -!) ° 4 И ъ 8 И сумматоров по модулю 2, в то время как в данном декодере общее число разрядов арифметических сумматоров равно 8 М). В то же время данный декодер является более быстродействующим по сравнению с декодирующими устройствами, использующими последовательные сдвигающие регистры с обратными связями.

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

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

Мажоритарный декодер содержит первую, вторую, третью и четвертую группы по два M-разрядных арифметических сумматора 1„, 1, 2„; 2; 3, 3,, 4,, 4 соответственно и четыре группы по

М трехвходовых мажоритарных элементов 5,...,5„; 6,...,6 М; 71,...,7

8-,...,8,, выходы которых подключены к выходам соответствующих двоичных информационных разрядов устройства. В первой группе сумматоров 1 н 1я первые и вторые входы первого сумматора !1 подкачены соответственно к вто рой 9 и пятой 9 М-разрядной группе входов декодера, а второго сумматора 1 — к третьей и седьмой группе входов. Во второй группе сумматоров и 2 входы первого сумматора 2 подключены к первой 91 и пятой 9 группе входов декодера, а второго сумматора — к четвертой 9 и восьмой 9

4 группе входов декодера. В третьей группе сумматоров 3 и 3> входы первого сумматора 3.1 подключены к первой 91 и седьмой 9 группе входов де кодера, а второго сумматора — к четвертой 94 и шестой 9 группе входов декодера. В четверто группе суммато ров 41 и 4 входы первого сумматора подключены к третьей 9 н шестой 95 группе входов декодера, а второго сум матора — к второй 9 и восьмой 98 гр пе входов декодера. Первые входы каж дого из И мажоритарных элементов пер вой 51,...,5>,второй 6„,...,6 „, тре тьей 7,,...,7,„ и четвертой 81,. ° .,81 группы подключены соответственно к первой 9, второй 9, третьей 9 и четвертой 9 группе входов декодера, вторые входы этих элементов — соответственно к первому, ..., М-ому выходу первых сумматоров 11, 2, 3

4 соответствующей группы, третьи входы этих элементов — соответственно к первому, ..., М-ому выходу вторых сумматоров 1, 2, 3, 44 этой же группы.

Декодер работает следующим образом.

При поступлении на входы декодера входного корректирующего кода в арифметических сумматорах 1„, 1, 2,„, 2, 3, 3, 4, 4 производятся операции вычитания соответствующих P-ичнык разрядов в порядке, определяемом законом кодирования. Так, в сумматорах

11 и 1 у Формируются значения P-ичного

Мажорйтарный декодер, содержащий четыре группы по М мажоритарных элементов, выход каждого из которых под890397! ключен к выходу соответствующего двоичного инФормационного разряда декодера, где М вЂ” число смежных двоичных разрядов, рассматриваемых как P-ичный м разряд слова, P = 2, о т л и ч а— ю шийся тем, что, с целью упрощения декодера, он содержит четыре группы по два М-разрядных ариФметических сумматора в каждой, первые входы первого и второго сумматора в IO первой группе подключены соответственно к второй и третьей М-разрядной группе входов декодера, во второй группе — к первой и четвертой группе входов декодера, в третьей группе — к первой,и четвертой группе входов декодера, а в четвертой группе — к третьей и второй rpyrme входов декодера, вторые входы М-разрядных арифметических сумматоров в первой группе щ подключены соответственно к пятой и седьмой группе входов, во второй группе — к пятой и восьмой группе входов, в третьей группе — к седьмой и шестой группе входов, а в четвертой группе — к шестой и восьмой группе входов декодера, причем первые входы каждого из М-мажоритарных элементов каждой группы подключены к одноименной группе входов декодера, а вторые и третьи входы — к соответствующим выходам первого и второго

М-разрядных ариФметических сумматоров одноименной группы.

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

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

У 362302, кл. Ij 06 F ll/12, 1971. . 2. Патент СНА В 3745528, кл. 340-!46.1, опуолик. 1975.

3. Патент СШЛ У 3582878, кл. 340-146.7, опуолик. 1971 (про-, тотип) .

890397

Составитель В. Максимов

Редактор М. Иинко Техвед Е. Харитончик Корректор В. Бутяга

Заказ 11008/79 Тиран 748 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и отнятий

113035 Москва, >(-35 Рариская иаб. л. 4/5

А

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