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

ОП ИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскииСоциапистическикРеспублик(5)М. Кл.6 06 Г 11/12 Н 03 К 19/23 Н 03 К 13/32 Госудирстееиый конитет СССР ио делан изебретеиий и открытий(23) Приоритет Опубликовано 07.02;82. Бюллетень РЙ 5 Дата опубликования описания 07. 02. 82 .(54) МАЖОРИТАРНЫЙ ДЕКОДЕР одирующее устройство оизвольные ошибки или Изобретение относится к областифровой вычислительной техники и передачи информации и может бытьиспользовано в циФровых вычислительных машинах (ЦВМ), в которых информация передается, хранится или обрабатывается в корректирующем коде,а также в многоканальных системахпередачи информации,В таких системах возникает необходимость исправления кратных ошибок в определенных группах смежныхразрядов. Например, для запоминающих устройств ЦВМ разработано много типов полупроводниковых интегральных схем, содержащих в одном корпусе оборудование для хранениянескольких ( 2-8) разрядов большого количества слов. Существуют и другие многоразрядные интегральные схемы ЦВМ,например четырехразрядный арифметико-логический блок. Отказ одной изтаких схем может привести к искажению группы из М2 смежных разрядов,расположенных на определенных пози. циях, которые могут рассматриватьсякак р -ичный разряд слова, гдето =2Аналогичная ситуация может возникнуть в многоканальных системах пере- И дачи информации, где в каждый момент времени по нескольким каналампередаются несколько смежных разрядов слова. Эти разряды могут бытьискажены импульсной помехой, одновре- тОменно воздействующей на все каналы,на приемное или передающее устройство. Для восстановления информациив таких ситуатиях должны быть ист 5пользованы корректирующие коды и соответствующие декодирующие устройства, обеспечивающие исправлениепакетов из и ошибок в определенныхсмежных позициях информационного слова, соответствующнх его представлению в системе счисления с основани.ем РИзвестно декисправляющее пр3 90388пакеты ошибок кратности М в циклических кодах, содержащие сдвигаощиерегистры с обратными связями, соединенные с логическими блоками 1.1,1.,Недостаток устройства заключает 5ся в большом времени декодированияиз-за последовательного характерапроцесса.Известно также декодирующее устройство, исправляющее ошибки в Р -ич Оном разряде слова, представленномгруппой из М смежных двоичных разрядов, содержащее сдвигающие регистры, соединенные с логическими блока-ми 121.Недостаток устройства также заключается в большом времени декодирования.Наиболее близким по техническойсущности и достигаемым результатам к2 Опредлагаемому является мажоритарный декодер, содержащий мажоритарные элементы, выход каждого из которых подключен к выходной шинесоответствующего:разряда, а такжегф 1 с сумматоров по модулю 2, гдег ) (2 И+1), 1 - число информационных разрядов слова, причем каждыймажоритарный элемент имеет г входов, каждый из которых подключен кЗОвыходам соответствующих сумматоровпо модулю 231Недостатком устройства являетсяего сложность из-за большого числамноговходовых сумматоров по модулю2 и сложность мажоритарных элементов с большим числом входов (не менее 2 М+1).Цель изобретения - упрощение устройства, в частности для случая использования (8 М, 4 М) корректирующего40кода, построенного на основе (8, 4)Корректирующего кода Рида-Маллерас кодовым расстоянием, 4, где 8 М -общее число разрядов кода, 4 М - число информационных разрядов, за счетуменьшения числа сумматоров (в пересчете на один разряд) и уменьшениячисла входов мажоритарных элементовпри сохранении их количества,Указанная цель достигается тем,что мажоритарный декодер, содержащий четыре группы по М мажоритарныхэлементов, выход каждого из которыхподключен к выходу соответствующегодвоичного информационного разряда .уст-Фройства, где М " число смежных двоич"ных разрядов, рассматриваемых какР-ичный разряд слова, Р=2", дополнительно содержит первую, вторую и третью группы из четырех М-разрядных арифметических сумматоров в каждой и четвертую группу из трех М-разрядных арифметических сумматоров, первые входы первого, второго, третьего и четвертого сумматоров в первой группе подключены соответственно к первой, второй, третьей и четвертой М-разрядной группе входов декодера, во второй группе - к первой, второй, пятой и шестой группе входов, а в третьей группе - к первой, третьей, пятой и седьмой группе входов декодера, вторые входы М-разрядных арифметических сумматоров в первой группе подключены соответственно к пятой, шестой, седьмой и восьмой группам входов, во второй группе - к третьей, четвертой, седьмой и восьмой группам входов, а в третьей группе - к второй, четвертой, шестой и восьмой разрядов устройства. Первые входы сумматоров 81, 8, 8, 8, третьей группы подключены соответственно к первой 51, третьей 5, пятой 5 и седьмой 5 группе входов, а вторые входы этих сумматоров - к второй 5, четвертой 5, шестой 5 и восьмой 58 группам входов. Первые входы сумматоров 10, 1 О 10 четвертой группы подключены к выходам мажоритарных элементов первой, второй, третьей групп соответственно, а вторые входы этих сумматоров к пятой 5, третьей 5 и второй 5 группам входов. В каждой группе каждый 1-й выход сумматора с номером 81 (101), где 1=1 М, 1=1,2,3, 4, 8=1,2,3, подключен к "му (1-му) входу мажоритарного элемента такой же группы с номером 9 (111). Четвертые входы мажоритарных элементов 11 ,. 11 м четвеотой группы подключены к первой. 51 группе входов устоойства. Выходы мажооитаоных элементов 9 и 9, и 11 11, подключены к выходам соответствующих двоичных информационных разрядов устройства.Устройство работает следующим образом.При поступлении на входы устройства входного корректирующего кода в арифметических сумматорах 1, 3, 8, 10, осуществляются операции вычитания соответствующих Р-ичных разрядов в порядке, определяемом законом коди" рования. При этом на выходах всех арифметических сумматоров одной груп90388 5пы 1, ), 1, 1 131, 3, 3, 3мируются значения одного и того жеР-ичного разряда выходного слова,т.е. одной и той же группы из М дво 5ичных разрядов. Одноименные разрядысо всех этих сумматоров поступают навходы соответствующего мажоритарного элемента 2, 4, 9, 11 и проходят на его выход. При наличии во Овходной информации одного искаженного Р-ичного разряда, т.е. одной искаженной группы из М двоичных разрядов, в каждой группе арифметическихсумматоров 1, 3, 8, 10 в соответствии с законом формирования корректирующего кода неправильный результат появляется на выходах только одного сумматора, и мажоритарные элементы 2, 4, 9, 11 соответствующих 20разрядов Формируют на выходе правильный результат по большинству правильных сигналов, поступивших на ихвходы. Так, для рассмотренного вышепримера, первый Р-ичный разряд (а) 25Формируется в арифметических сумматорах 1, 1, 1, 1 по следующимгруппам входов декодера, в четвертойгруппе М-разрядных арифметическихсумматоров первые входы первого, вто- З 0рого и третьего сумматоров подключены к выходам первой, второй и третьейгруппы мажоритарных элементов, вторые входы данных сумматоров - к нятой, третьей и второй группам входов декодера, а первые, вторые,М-ные выходы всех М-разрядных арифметических сумматоров каждой группыподключены к входам соответственнопервого, второго.М-ого мажоритарного элемента соответствуюцейгруппы, а четвертые входы мажоритарных элементов четвертой группыподключены к первой группе входовФдекодера, 45На чертеже представлена блок-схема устройства, содержащая первую группу из четырех М-разрядных арифметических сумматоров .1, 1 , 1 , 1,первую группу из М четырехвходовыхмажоритарньпс элементов 22,вторую группу из четырех М-разрядных арифметических сумматоров 3,3 , 3 , 3, вторую группу из М четырехвходовых мажоритарных элемен 55тов 4 4 м, группы 55 мвходов и 61 ээбм и 74 э.,9 7 и выходов устройства, третью группу изчетырех М-разрядных арифметических 7 6сумматоров 8 , 8 , 8 , 8, третью группу из М четырехнходовых мажоритарных элементов 9 9 м, четвертую группу из трех М-разрядных арифметических сумматоров 10, 101, 10 , 1 О и четвертую группу из М четырехвходовых мажоритарных элементов 1111 м и группы 121 12 и 13 1 Зм, выходов устройства.Первые входы сумматоров 1, 1,, 1, первой группы подключены соответственно к первой 51, второй 5 д, третьей 5 и четвертой .5, И-разрядной группе входов устройства, а вторые входы этих сумматоров - соответственно к пятой 5, шестой 56 седьмой 5 и восьмой 5 з группе входов устройства. Первые входы сум-. маторов 3, 3 , 3 , 3 второй группы подключены к первой 5, второй 5 , пятой 5, шестой 56 группе входов, а вторые входы к третьей 5 четвертой 5 с седьмой 5 , восьмой 5 группе входов устройства. В каждой группе каждый 1-й выход сумматора с номером 1 (3), где 1=1,., М, 1=1,2,3,4, подключен к -му входу мажоритарного-элемента такой же группы е номером 2 (4) . Выходы мажоритарных элементов 2, 2 ь 1 и 4 4, подключены к выходам соответствуюцих двоичных информационных соотношениям: а=В-А, а=Г-В, а= О-С, с.=Н-О соответственноПри отказе одного Р-ичного разряда, например Г (группа входов 5), будет получен неправильный результат в одном арифметическом сумматоре 1 , тогда по правильным результатам арифметических сумматоров 1, 1 , 1, мажори-, тарные элементы 2, 2 сФормируюг правильные значенйя двоичных разрядов 1 и 2 выходного кода.Технико-экономические преимущества устройства заключаются в простоте и возможности реализации на .стандартных интегральньпс схемах. При этом в нем используются более простые мажоритарные элементы (с меньшим числом входов). Действительно, в известном устройстве для исправления М-кратной ошибки каждый информационный разряд необходимо сформировать г 2 И+ раз; при этом мажоритарные элементы должны иметь г входов (например, при М=4, г=9). В предлагаемом устройстве каждый двоичный разряд достаточно сформи 7 903 ровать 4 раза, независимо от величи ны М. Объем оборудования арифметических сумматоров также будет меньше, чем сумматоров по модулю 2 в известном устройстве, в котором необходимо иметь (г).ф 4 МУР 8 М сума маторов по модулю 2, в то время как в предлагаемом устройстве общее число разрядов арифметических сумматоров равно 15 М.Кроме того, устройство является более быстродействующим по сравнению с декодирукнцими устройствами, использующими последовательные сдвигающие регистры с обратными связя- ми аФормула изобретенияМажоритарный декодер, содержащий четыре группы по М мажоритарных элементов, выход каждого из которых подключен к выходу соответствующего двоичного информационного разряда устройства, где М - число смежных двоичных разрядов, рассматриваемых как Р-ичный разряд слова, Р=2, о т л и ч,а ю щ и й. с я тем, что, с целью упрощения декодера, он содержит первую, вторую и третью группы из четырех М-разрядных арифметических сумматоров в каждой и четвертую группу из трех М-разрядных арифметических сумматоров, первые входы первого, второго, третьего и четвертого сумматоров в первой группе подключены соответственно к первой, второй, третьей и четвертой М-разрядной группе входов декодера, во 887 8второй группе - к первой, второй, .пятой и шестой группе входов, а в третьей группе - к первой, третьей, пятой и седьмой группе входов декодера, вторые входы М-разрядных арифметических сумматоров в первой группе подключены соответственно к пятой, шестой, седьмой и восьмой группам входов, вовторой группе - к трец 1 тьей, четвертой, седьмой и восьмойгруппам входов, а в третьей группе - к второй, четвертой, шестой и вось" мой группам входов декодера, в четвертой группе М-разрядных арифметических сумматоров .первые входы первого, второго и третьего сумматоров подключены к выходам первой, второй и третьей группы мажоритарных элементов, вторые входы данных сум-маторов - к пятой, третьей и второйгруппам входов декодера, а первые, вторые М-ные выходы всех М-разрядных арифметических сумматоров каждой группы подключены к входам соответственно первого, второго М-ого мажоритарного элемента соответствующей группы, а четвертые входы мажоритарных элементов четвертой группы подключены к первой групЗ пе входов декодера. Источники информации,принятые во внимание при экспертизе 1. Авторское свидетельство СССР з Р 362302, кл. 6 06 Г 11/12, 1971,2. Патент США Р 3745528,кл. 340-146.1, опублик. 1975. 3. Патент США У 3582878,кл. 340-146.1, опублнк. 1971 (проди тотип).Заказ 123/31 Тир лиал ППП "Патент ВЕ 903887 Ужгород, У сн оектная, 4