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

1

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

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

расположенных на определенных пози.1ЩЯХ, которые могут рассматриваться как р -ичный разряд слова, гдер 2.

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

Известно декодирующее устройство, исправляющее произвольные ошибки или пакеты ошибок кратности н в циклических кодлх, содержащие сдвигающие регистры с обратными связями, соединенные с логическими блоками L П. Недостаток устройства заключается в большом времени декодирования из-за последовательного характера процесса Известно также декодируюо(ее устройство, исправляющее огаибки в Р -к ном разряде слова, представленном группой из М смежных двоичных разря дов, содержащее сдвигающие регистры, соединённые с логическими блока ми 123 . Недостаток устройства также закл ается в большом времени декодирования . Наиболее близким по технической сущности и достигаемым результатам предлагаемому является мажоритарный декодер, содержащий мажоритарные элементы, выход каждого из которых подключен к выходной шине соответствующегоразряда, а также Гk CinviMHTOpoB по модулю 2, где г(2 М+1), k - чисцо информационных разрядов слова, причем каадчый мажоритарный элемент имеет г входов, каждый из которьш подключен к выходам соответствующих сумматоров по модулю 2 С 3J. Недостатком устройства является его сложность из-за большого числа многовходовых сумматоров по модулю 2 и сложность мажоритарных элементов с большим ЧИСЛОМ входов (не менее 2М+1). Цель изобретения - упрощение уст ройства, в частности для случая использования (8М, 4м) корректирующег кода, построенного на основе (8, 4) koppeктиpyIOщeгo кода Рида-Маллера кодовьм расстоянием, 4, где 8М общее число разрядов кода, 4М - чис ло информационных разрядов, за счет уменьшения числа сумматоров (в пере счете на один разряд) и уменьшения числа входов мажоритарных элементов при сохранении их количества. Указанная цель достигается тем, что мажоритарный декодер, содержащий четыре группы по М мажоритарных элементов, выход каяодого из которых подключен к выходу соответствующего двоичного информационного разряда .у ройства, где М - число смежных двои ных разрядов, рассматриваемых как Р-ичный разряд слова, , дополни тельно содержит первую, вторую и третью группы из четырех М-разрядных арифметических сумматоров в каждой и четвертую группу из трех М-разрядных арифметических сумматоров, первые входы первого, второго, третьего и четвертого сумматоров в первой группе подключены соответственно к первой, второй, третьей и четвертой М-разрядной группе входов декодера, во второй группе - к первой, второй,. пятой и шестой группе входов, а в третьей группе - к первой, третьей, пятой и седьмой группе входов декодера, вторые входы М-разрядных арифметических cy Iмaтopoв в первой группе подключены соответственно к пятой, шестой, седьмой и восьмой группам входов, во второй группе - к треуьей, четвертой, седьмой и восьмой группам входов, а в третьей группе - к второй, четвертой, шестой и восьмой разрядов устройства. Первые входы сумматоров 8, 8j, 8,,.8ц, третьей группы подключены соответственно к первой 5;, третьей 5j, пятой 5 и седьмой пе входов, а вторые входы этих сумматоров - к второй 5 четвертой 5ц, иестой 5 и восьмой 5g группам входов. Первые входы сумматоров 10, 10, 10, четвертой группы подключены к выходам мажоритарных элементов первой, второй, третьей групп соответственно, а вторые входы этих сумматоров к пятой 5г, третьей 52 и второй 5 группам входов. В каждой группе каждый i-и выход сумматора с номером 8J (101), где ,..., М, ,2,3, 4, 1,2,3, подключен к j-му (-му) входу мажоритарного элемента такой же группы с номером 91 (11 i). Четвертые входы мажоритарных элементов 11,,.... 11ц, четвертой гоуппы подключены к первой. 5 группе входов устройства. Выходы мажооитаоных элементов 9 , и 9„ и 1 Ц ,..,, 1 11 подключены к выходам соответствую1шх двоичных информационных разрядов устройства . Устройство работает следующим образом. При поступлении на входы устройства входного корректирующего кода в арифметических сумматорах 1, 3, 8, 10, осуществляются операции вычитания соответствукяцих Р-ичнь1х разрядов в порядке, определяемом законом кодирования. При этом на выходах всех арифметических сз мматоров одной груп4 г з Ц 3 ц 84 . i -и,, 8ц i 10 , 10, lOj) формируются з}шчения одного и того же Р-ичного разряда выходного слова, т.е. одной и той же группы из М дво ичных разрядов. Одноименные разряды со всех этих сумматоров поступают н входы соответствующего мажоритарного элемента 2, 4, 9, II и проходят на его выход. При наличии во входной информации одного искаженно го Р-ичного разряда, . одной искаженной группы изМдвоичных разрядов, в каждой группе арифметических сумматоров 1, 3, 8, 10 в соответствии с законом формирования коррек тирующего кода неправильный результат появляется на выходах только од ного сумматора, и мажоритарные элементы 2, 4, 9, 11 соответствуюищх разрядов формируют на выходе правил ный результат по большинству правильных сигналов, поступивших на их входы. Так, для рассмотренного вьше примера, первый Р-ичный разряд (.а) формируется в арифметических сумматорах Ц , I,,, 1,, Ц по следующим группам входов декодера, в четверто группе М-разрядных арифметических сумматоров первые BXOJD I первого, вт рого и третьего сумматоров подключе ны к выходам первой, второй и треть 1руппы мажоритарных элементов, вторые входы данных сумматоров - к пятой, третьей и второй группам входов декодера, а первые, вторые,... М-ные выходы всех М-разрядных арифметических сумматоров каяодой группы подключены к входам соответственно первого, второго, ..., М-ого мажори тарного элемента соответствующей группы, а четвертые входы мажоритарных элементов четвертой группы подключены к первой группе входов декодера. На чертеже представлена блок- схе- ма устройства, содержащая первую гру пу из четырех М-разряДных арифметических сумматоров Ц , 1 , Ij , L , первую группу из М четырехвходовых мажоритарных элементов 2 ,..«,2, вт.орую группу из четырех М-разрядных арифметических сумматоров 3, 3, 3j , 3ц , вторую группу из М четырехвходовых мажоритарньпс элементов 4 ,.. ,, 4,, группы 5 ,..., 5„ входов и 6д ,. .., 6м и 7, J J 7| выходов устройства, третью группу из четырех М-разрядных арифметических 7 сумматоров 8 , 8j, 8j , 8ц , третью группу из М четырех«ходовых мажоритарных элементов 9 ... 9, четвертую группу из трех М-разрядных ари(етических сумматоров 10 , lOj, О, , 10ц и четвертую группу из М четырехвходовых мажоритарных элементов 1 Ц ,..., 11 |4f и группы i 2 ,..., 12м и 13j,...,13„; выходов устройства. Первые входы сумматоров Ц , l.j, 1-, 1ц, первой группы подключены соответственно к первой 5, второй 5д, третьей 5, и четвертой 5|j М-разрядной группе входов устройства, а вторые входы этих сумматоров - соответственно к пятой 5f, шестой 5 седьмой 5 и восьмой 5g группе входов устройства. Первые входы сумматоров 3,,, 3j, 3j, 3ц второй группы подключены к первой 5 , второй Зо, пятой 5 , Шестой 5 группе входов, а вторые входы к третьей 5,, четвертой 5ц, седьмой 5, восьмой 5g группе входов устройствао В каждой группе каждый i-и выход сумматора с номером 1J (3j), где ..., М, ,2,3,4, подключен к j-му входу мажоритарного-элемента такой же группы е номером 2 (4f). Выходы мажоритарных элементов 2.,..., 2, и 4i| , о о., 4 подключены к выходам соответствующих двоичных информационных соотношениям: , , ,. соответственно..При отказе одного Р-ичного разряда, например F (группа входов 5), будет получен неправильный результат в одном арифметическом сумматоре Ij, тогда по правильным результатам арифметических сумматоров 1 , Ij , 1ц мажоритарные элементы 2 , 2 сформируют правильные значения двоичных разрядов 1 и 2 выходного кода. Технико-экономические преимущества устройства заключаются в простоте и возможности реализации на стандартных интегральных схемах. При этом в нем используются более простые мажоритарные элементы (с меньшим числом входов). Действительно, в известном устройстве для исправления М-кратной ошибки каждый информационный разряд необходимо сформировать г; 2М-ь1 раз; при этом мажоритарные элементы должны иметь г входов (например,.при , ). В предлагаемом устройстве каждый двоичный разряд достаточно сформиррвать 4 раза, независимо от величины М. Объем оборудования арифметических сумматоров также будет меньше , чем сумматоров по модулю 2 в известном устройстве, в котором необходимо иметь (г-1) М сум маторов по модулю 2, в то время как в предлагаемом устройстве общее чис ло разрядов арифметических сумматоров равно 15 М, Кроме того, устройство является более быстродействующим по сравнению с декодирзтощимй устройствами, использующими последовательные сдви гающие регистры с обратными связя, ми. Формула изобретения Мажоритарный декодер, содержащий четыре группы по М мажоритарных эле ментов, выход каждого из которых подключен к выходу соответствующего двоичного информационного разряда устройства, где М - число смежных двоичных разрядов, рассматриваемых как Р-ичный разряд слова, , отлич.ающий. ся тем, что, с целью упрощения декодера, он содержит первую, вторую и третью груп пы из четырех М-разрядных арифметических сумматоров в каждой и четвер тую группу из трех М-разрядных ариф метических сумматоров, первые входы первого, второго, третьего и чет вертого сумматоров в первой группе подключены соответственно к первой, второй, третьей и четвертой М-разрядной грзшпе входов декодера, во 9 8 второй группе - к первой, второй, пятой и шестой группе входов, а в третьей группе - к первой, третьей, пятой и седьмой группе входов декодера, вторые входы М-разрядных арифметических сумматоров в первой группе подключены соответственно к пятой, шестой, седьмой и восьмой группам входов, во второй группе - к третьёй, четвертой, седьмой и восьмой группам входов, а в третьей группе к второй, четвертой, шестой и восьмой группам входов декодера, в четвертой группе М-разрядных арифметических сумматоров первые входы первого, второго и третьего сумматоров подключены к выходам первой, второй и третьей группы мажоритарных элементов, вторые входы данных сумматоров - к пятой, третьей и второй группам входов декодера, а первые, вторые,..., М-ные выходы всех М-разрядных арифметических сумматоров каждой группы подключены к входам соответственно первого, второго,.,., М-ого мажоритарного элемента соответствующей группы, а четвертые входы мажоритарных элементов четвертой группы подключены к первой группе входов декодера. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР № 362302, кл. G 06 F П/12, 1971. 2,Патент США № 3745528, 340-146.1, опублик. 1975. 3. Патент США № 3582878, кл. 340-146.1, опублик. 1971 (прототип) . 1 5и