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

 

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

Социапистическик

Республик

«»903887 (6! ) Дополнительное к авт. свид-ву (22) Зая ален о 26. 02. 80 (2 ) 2888569/! 8-24 с присоединением заявки М (53)N. Кл.

G 06 F 11/12

Н 03 К 19/23

Н 0З К 1З/Зг

)осудирстиеиый конитет

СССР ио делан изебретеиий и открытий (23) Приоритет

Опубликовано07.02;82. Бюллетень hh 5

Дата опубликования описания 07.02.82. (53) УДК 681,325 (088.8) К.К.Ещин, А.К.Заволокин, В.И.Заровский, А.А.Мошков, И.Ф.Мусатов, В.И.Рейнер и Е.К.Юферо (72) Авторы изобретения (71) Заявитель (54) МАЖОРИТАРНЫЙ ДЕКОДЕР

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

В таких системах возникает необходимость исправления кратных ошибок в определенных группах смежных разрядов. Например, для запоминающих устройств ЦВМ разработано много типов полупроводниковых интеграль1S ных схем, содержащих в одном корпусе оборудование для хранения нескольких (2-8) разрядов большого количества слов. Существуют и другие многоразрядные интегральные схемы ЦВМ, например четырехразрядный арифметико-логический блок. Отказ одной из таких схем может привести к искажению группы из м ) 2 смежных разрядов, расположенных на определенных пози. циях, которые могут рассматриваться как р -ичный разряд слова, где Р =2

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

Известно декодирующее устройство, исправляющее произвольные ошибки или

3 90388 пакеты ошибок кратности М в циклических кодах, содержащие сдвигакнцие регистры с обратными связями, соединенные с логическими блоками 1.1.1., Недостаток устройства заключает5 ся в большом времени декодирования из-за последовательного характера процесса.

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

Недостаток устройства также заключается в большом времени декодироI вания.

Наиболее близким по технической сущности и достигаемым результатам к

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

r k сумматоров по модулю 2, где г) (2 И+1), k - число информационных разрядов слова, причем каждый мажоритарный элемент имеет Г входов, каждый из которых подключен к

ЗО выходам соответствующих сумматоров по модулю 2 f33 °

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

2 и сложность мажоритарных элементов с большим числом входов (не менее 2М+1) .

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

40 кода, построенного на основе (8, 4)

Корректирующего кода Рида-Иаллера с кодовым расстоянием, 4, где 8M— общее число разрядов кода, 4M — число информационных разрядов, за счет уменьшения числа сумматоров (в пересчете на один разряд) и уменьшения числа входов мажоритарных элементов при сохранении их количества.

Указанная цель достигается тем, что мажоритарный декодер, содержащий четыре группы по M мажоритарных элементов, выход каждого из которых подключен к выходу соответствующего двоичного информационного разряда .уст-55

Ф ройства, где M " число смежных двоич" ных разрядов, рассматриваемых как

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

И-разрядной группе входов декодера, во второй группе — к первой, второй, пятой и шестой группе входов, а в третьей группе — к первой, третьей, пятой и седьмой группе входов декодера, вторые входы И-разрядных арифметических сумматоров в первой группе подключены соответственно к пятой, шестой, седьмой и восьмой группам входов, во второй группе — к третьей, четвертой, седьмой и восьмой группам входов, а в третьей группе — к второй, четвертой, шестой и восьмой разрядов устройства. Первые входы сумматоров 8, 8, 85, 8, третьей группы подключены соответственно к первой

5< третьей 5, пятой 5„ и седьмой 5„ группе входов, а вторые входы этих сумматоров — к второй 5< четвертой 5>, шестой 5 и восьмой 58 группам входов.

Первые входы сумматоров 10„, 10

10 четвертой группы подключены к вьгходам мажоритарных элементов первой, второй. третьей групп соответственно, а вторые входы этих сумматоров к пятой 5< третьей 5 и второй 5 группам входов. В каждой группе каждый i-й выход сумматора с номером

8j (101), где i=1,..., М, j=l,2,3, 4, 8=1,2,3, подключен к "му (F-му) входу мажоритарного элемента такой же группы с номером 9! (111). Четвертые входы мажоритарных элементов

11 ...,. 11> четвеотой группы подключены к первой. 5 группе входов чстDoHcTBa. Выходы мажооитаоных элементов 9 и 9,„ и 11„,...,11„, подключены к выходам соответствующих двоичных информационных разрядов устройства.

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

При поступлении на входы устройства входного корректирующего кода в арифметических сумматорах 1, 3, 8, 10, осуществляются операции вычитания соответствующих Р-ичных разрядов в порядке, определяемом законом кодирования. При этом на выходах всех арифметических сумматоров одной груп90388

5 пы 1, ), 1, 14 (3,, 3, 34 мируются значения одного и того же

P-ичного разряда выходного слова, т.е. одной и той же группы из М дво5 ичных разрядов. Одноименные разряды со всех этих сумматоров поступают на входы соответствующего мажоритарного элемента 2, 4, 9, il и проходят на его выход. При наличии во !9 входной информации одного искаженного Р-ичного разряда, т.е. одной искаженной группы из N двоичных разрядов, в каждой группе арифметических сумматоров l. 3, 8, 10 в соответствии с законом формирования корректирующего кода неправильный результат появляется на выходах только одного сумматора, и мажоритарные элементы 2, 4, 9, 11 соответствующих щ разрядов формируют на выходе правильный результат по большинству правильных сигналов, поступивших на их входы. Так, для рассмотренного выше примера, первый Р-ичный разряд (а) 25 формируется в арифметических сумматорах 1, 1, 1, 14 по следующим группам входов декодера, в четвертой группе М-разрядных арифметических сумматоров первые входы первого, вто- Зо рого и третьего сумматоров подключены к выходам первой, второй и третьей группы мажоритарных элементов, вторые входы данных сумматоров — к нятой, третьей и второй группам входов декодера, а первые, вторые,...

M-ные выходы всех M-разрядных арифметических сумматоров каждой группы подключены к входам соответственно первого, второго, ..., M-ого мажори- 4> тарного элемента соответствуюцей группы, а четвертые входы мажоритарных элементов четвертой группы подключены к первой группе входов декодера. 45

На чертеже представлена блок-схема устройства, содержащая первую группу из четырех M-разрядных арифметических сумматоров 1„, 1, 1, l, первую группу из М четырехвходовых мажоритарных элементов 2„,...,2„ вторую группу из четырех М-разрядных арифметических сумматоров 3, 3, 3, 3>, вторую группу из М четырехвходовых мажоритарных элемен55 тов 4„,..., 4м, группы 5„,...,5м входов и 61 ý " эбм и 74 э ° .э 7и выходов устройства, третью группу из четырех И-разрядных арифметических

7 6 сумматоров 8, 8, 8, 8„, третью группу из М четырехнходовых мажоритарных элементов 9,..., 9, четвертую группу из трех М-разрядных арифметических сумматоров 10, 10а, 10, 10 и четвертую группу из М четырехвходовых мажоритарных элементов 11,,,...,11м и группы 121,. ° °, 12м и 13,„,...,13м, выходов устройства.

Первые входы сумматоров 1, !

, 1„, первой группы подключены соответственно к первой 5, второй

5z, третьей 5 и четвертой .5 И-разрядной группе входов устройства, а вторые входы этих сумматоров — соответственно к пятой 5, шестой 56 седьмой 57 и восьмой 58 группе входов устройства. Первые входы сумматоров 3, 3, 3, 3> второй группы подключены к первой 5„, второй

5, пятой 5, шестой 56 группе входов, а вторые входы к третьей 5 четвертой 5ь, седьмой 5, восьмой

5 группе входов устройства. В каждой группе каждый i--й "выход сумматора с номером Ij (3j), где i=l. ° ., М, j=l 2,3,4, подключен к j-му входу мажоритарного-элемента такой же группы е номером 2i (41). Выходы мажоритарных элементов 2,,..., 2> и

4„-,..., 4„, подключены к выходам соответствуюцих двоичных информационных соотношениям: a=E-А, а=Г-В, а6-С, а=Н-0 соответственно..При отказе одного Р-ичного разряда, например

F (группа входов 5 ), будет получен неправильный результат в одном арифметическом сумматоре 1, тогда по правильным результатам арифметических сумматоров 1„, 1, 1,„ мажори-, тарные элементы 2„, 2 сформируют правильные значенйя двоичных разрядов 1 и 2 выходного кода.

Технико-экономические преимущества устройства заключаются в простоте и возможности реализации на .стандартных интегральных схемах.

При этом в нем используются более простые мажоритарные элементы (с меньшим числом входов). Действительно, в известном устройстве для исправления M-кратной ошибки каждый информационный разряд необходимо сформировать rp 2M+i раз; при этом мажоритарные элементы должны иметь

r входов (например,.при M--4, г=9).

В предлагаемом устройстве каждый двоичный разряд достаточно сформи7 903 ровать 4 раза, независимо от величи. ны М. Объем оборудования арифметических сумматоров также будет меньше, чем сумматоров по модулю 2 в известном устройстве, в котором необходимо иметь (г-1) . 4M 8 М сума маторов по модулю 2, в то время как в предлагаемом устройстве общее число разрядов арифметических сумматоров равно 15 М.

Кроме того, устройство является более быстродействующим по сравнению с декодирукнцими устройствами, использующими последовательные сдвигающие регистры с обратными связя-, ми .

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

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

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

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

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

Р 362302, кл. G 06 F ll/12, 1971.

2. Патент Cl!IA Р 3745528, кл. 340-146.1, опублик. 1975.

3. Патент США и 3582878, кл. 340-146.1, опублнк. 1971 (про40 ТОТИП) °