Мажоритарный декодер Советский патент 1981 года по МПК H03M13/43 

(54) МАЖОРИТАРНЫ ДЕКОДЕР

Изобретение относится к цифровой вычислительной технике и передаче информации и ножет быть использовано в ЦВМ, в которялх информация передается, хранится или обрабатывается в кор рекгирующем коде, а также в многоканальных системах передачи информации. В таких системах возникает необходимость исправления кратных ошибок в определенных группах смежных разрядов Например, для запоминающих устройств ЦВМ разработано много типов полупроводниковых интегральных схем, содержа щих в одном корпусе оборудование для хранения нескольких 2-8 разрядов большого количества слов. Существуют и другие многоразрядные интегральные схемы ЦВМ, например четырехразрядный арифметико-логический блок. Отказ одной из таких схем приведет к искажению группы из М :, 2 смежных разрядов, расположенных на определенных позициях, которые могут рассматриваться как Р-ичный разряд слова, где Р 2 . Аналогичная ситуация может возникнуть в многоканальных системах передачи rfkформации, где в каждый момент времени по нескольким каналам передаются несколько смежных разрядов слова. Эти разряды могут быть искажены импульсной помехой, одновременно воздействую- щей на все каналы, на приемное или пе редакщее устройство. Для восстановления информации в таких ситуациях должны быть использованы корректирукп9{е коды и соответствую1ф1е декодирующие устройства, обеспечива1ав01е исправление пакетов из М ошибок в определенных смежных позициях информационного слова, соответствующих его представлению в системе счисления с основанием Р. Известно декодирующее устройство, исправляющее произвольные.ошибки или пакеты ошибок кратности М в циклических кодах, содержа1цие сдвигающие регистры с обратными связями, соединенные с логическими блоками 11 . 3 Недостаток данного устройства заключается в большом времени декодирования из-за последовательного хара тера процесса. Известно также декодирующее устройство, исправляющее ошибки в Р-ичном разряде слова, представленном группой из М смежных двоичных разрядов, содержащее сдвигаюпще регистры, соединенные с логическими блоками 2 Недостаток известного устройства заключается также в большом времени декодирования. Наиболее близким по технической сущности и достигаемым результатам к предлагаемому является мажоритарный декодер, содержащий мажоритарные эле менты, выход каждого из которых подключен к выходной шине соответствующего разряда, а также сумматоров по модулю 2, где г(2М+1) , где К число информационных разрядов слова, причем каждый мажоритарный элемент имеет г входов, каждый из которых подключен к выходам соответствукяцих сумматоров по модулю 2 32. Недостаток известного устройства заключается в его сложности из-за большого числа сумматоров по модулю и сложности мажоритарных элементов с большим числом входов (не мене 2М+ 1). Цель изобретения - упрощение декодера, в частности, для случая использования (8М, 4м) корректирующего кода, построенного на основе 8,4 мажоритарно декодируемого корректирующего кода с кодовым расстоянием 3 где 8М - общее число разрядов кода: 4М - число информационных разрядов за счет уменьшения числа сумматоров (в пересчете на один разряд) и умень шения числа входов мажоритарных элементов при сохранении их количества. Для достижения указанной цели мажоритарный декодер, содержащий четыре группы по М мажоритарных элементов, выход каждого из которых под ключен к выходу соответствующего дво ичного информационного разряда декодера, где М - число смежных двоичных разрядов, рассматриваемых как Р-ич- ный разряд слова, Р 2 , содержит четыре группы по два М-разрядных ари метических сумматора в каждой, первы входы первого и второго сумматора в первой группе подключены соответстве но к второй и третьей М-разрядной , групппе входов декодера, во второй 7 группе - к первой и четвертой группе входов декодера, в третьей группе к первой и четвертой группе входов декодера, а в четвертой группе - к третьей и второй группе входов декодера, вторые входы М-разрядных арифметических сумматоров в первой группе подключены соответственно к пятой и седьмой группе входов, во второй группе - к пятой и восьмой группе входов, в третьей группе - к седьмой и шестой группе входов, а в четвертой группе - к шестой и BocbMoii группе входов декодера,причем первые входы каждого из М мажоритарных элементов каждой группы подключены к одноименной группе входов декодера, а вторые и третьи входы - к соответствующим выходам первого и второго М-разрядных арифметических сумматоров одноименной группы. Входной (8М, 4И) корректирующий код для устройство формируется по следующим правилам. Исходное двоичное 4 М-разрядное слово разбивается на четыре группы по М смежных разрядов в каждой, и каждая такая группа рассматривается как один Р-ичный разряд, где Р 2 . Затем формируется корректирующий код, аналогичный известному двоичному разделимому мажоритарно декодируемому коду (8,4) описанному в ГЗ, только вместо двоичных разрядов используются Р-ичные разряды, а вместо операции сложения по модулю 2 - операция арифметического сложения на М-разрядном арифметическом сумматоре с потерей переноса из старшего разряда, т.е. по модулю Р 2 . Если Р-ичные информационные символы обозначить а, Ь, с, d, то символы корректирующего кода А, В, С, D, Е, F, G, Н формируют по следующим соотношениям: А а; В Ь; С с; D d; E F C-f-d; G a + c; H b + d, причем + означает операцию сложения по модулю р. Например, двоичный код lOOlllOl при необходимости исправления ошибки, заключающейся в искаже- , НИИ пары смежных разрядов (первого и второго, треть.его и четвертого и т.д.) рассматривается как код 2131 в системе счисления с основанием Р 2 4(а 2, b 1 , с 3, d 1) . Из этого кода по указанным соотношениям формируется код 21313012, который представляется двоичным кодом 1001110111000110. На чертеже представлена блок-схема предлагаемого декодера. Мажоритарный декодер содержит первую, вторую, третью и четвертую группы по два М-разрядных арифметических сумматора 1, 1,, 3, 3,, 4, 4л соответственно и четыре группы по М трехвходовых мажоритарных элементов 5 .. ., 5||Д; 6 ,. .. , 6 М, 7 ,.. ., 7ц,, 8-1,...,8, выходы которых подключены к выходам соответствующих двоичных ин формационных разрядов устройства. В первой группе сумматоров Ц и первые и вторые входы первого сумматора 1. подключены соответственно к вто рой 9л и пятой 9j М-разрядной группе входов декодера, а второго сумматора А - к третьей и седьмой группе входов. Во второй группе сумматоров и 2п входы первого сумматора 2 подключены к первой 9 и пятой 9 группе входов декодера, а второго сумматора - к четвертой 9, и восьмой 9д группе входов декодера. В третьей группе сумматоров 3 , и Зп входы первого сумматора 3- подключены к первой 9 и седьмой 9-у группе входов де кодера, а второго сумматора - к четвертой 9 и шестой 9/ группе входов декодера. В четвертой группе суммато ров 4 и 4 л входы первого суьматора подключены к третьей 9 и шестой 9j, группе входов декодера, а второго су матора - к второй и восьмой 9в гр пе входов декодера. Первые входы каж дого из М мажоритарных элементов пер вой ,...,5ц; второй 6,...,6, тре тьей 7 , .. ., 7у и четвертой 8,...,8| группы подключены соответственно к первой 9д, второй 9л третьей 9л и четвертой 9 группе входов декодера, вторые входы этих элементов - соответственно к первому, ..., М-ому выходу первых сумматоров Ц , 2 , 3 , 4 соответствующей группы, третьи входы этих элементов - соответственно к первому, ..., М-ому выходу вторых сумматоров l|j, 2« , З, 4 этой же группы. Декодер работает следующим образом. При поступлении на входы декодера входного корректирующего кода в ариф метических сумматорах 1, К, 2., 2 3, 3,, 4, 4 производятся операции вычитания соответствующих Р-ичных разрядов в порядке, определяемом законом кодирования. Так, в сумматорах 1д и 1 (j формируются значения Р-ичиого разряда (J по соотношениям а Е - В и а в - С соответственно, в сумматорах 2, 2 2 вычисляются значения в Е-А и в H-I и т.д. При наличии, во входной информации одного искаженного Р-ичного разряда, т.е. одной искаженной группы из М двоичных разрядов, в каждом мажоритарном элементе 5-8 искажена информация не более, чем на одном входе - либо непосредственно с искаженной группы входов, либо с выхода соответствующего сумматора 1-4. Так, для рассмотренного примера при искажении информации например в четвертом Р-ичном разряде ), получены неправильные результаты на выходах сумматоров 2п и 3л и на третьи входы мажоритарных элементов 6,,...,6, 7,...,7,, а также на первые входы мажоритар;:ых элементов 8,...,8ц поступит неправильная информация. Поскольку на двух других входах каждого мажоритарного элемента 5-8 информация правильная, на всех выходах сформирован правильный результат . , Технико-экономический эффект предлагаемого декодера заключается в его простоте по сравнению с известным декодером. При этом в нем используются более простые мажоритарные элементы (с меньшим числом входовj. Действительно, в известном декодере для исправления М-кратной ошибки информационный разряд необходимо сформировать Г 7, 211 + I раз, при этом мажоритарные элементы должны иметь г входов (например, прк М 4, « 9). В предлагаемом декодере каждый мажоритарный элемент имеет 3 входа независимо отвеличины Н. Объем оборудования арифметических сумматоров также меньше, чем в известиом необходимо иметь (г -1). 4 М : 8 сумматоров по модулю 2, в то время как в данном декодере общее число разрядов арифметических сумматоров равио В М). В то же время декодер является более быстродействующим по сравнению с декодирующими устройствами, использующии последовательные сдвигающие регисты с обратными связями. 4 ормула изобретения Мажоритарный декодер, содержащий етыре группы по М мажоритарных элементов, выход ка;ждого из которых под)

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

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

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

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

. 2. Патент США № 3745528, кл. 340-146.1, опублик. 1975.

кл. 340-146.7, опублик. 1971 (про-; тотип .