Устройство деления полиномов

 

Изобретение относится к области вычислительной техники и предназначено для использования в системах передачи информации, в цифровых вычислительных машинах, в которых время деления полиномов двоичной информации должно быть существенно : меньше времени передачи двоичной информации по каналам связи. Целыб изобретения является увеличение быстродействия . Устройство деления полиномов содержит вход делимого I, триггерный регистр остатка 2 группы умножителей 3 на постоянную величину и группы сумматоров 4 по модулю два. В предлагаемом устройстве обеспечивается ускоренное деление полиномов двоичной информации при кодировании ее систематическим циклическим кодом или при декодировании этого кода. ил. (Л

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

А1 (19) (111

m 4 G 06 F 15 31

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

И АBTOPCHOMY СВИДЕТЕЛЬСТВУ

1h,„ г.

:Ь

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4247117/24-24 (22) 18.05.87 (46) 15,12,88. Бюл. У 46 (72) Г.И.Шевченко, P.Á.Íàçüìîâ и В.И.Савоничев (53) 681.325(088.8) (56) Хетагуров Я.А., Вуднев 10.Н. Повышение надежности цифровых устройств методами избыточного кодирования.

M.: Энергия, 1974, с. 75, рис. 3-4.

Питерсон У,,Уэлдон Э. Коды, исправляющие ошибки. N.: Мир, 1976, с. 200, рис, 7 6. (54) УСТРОЙСТВО ДЕЛЕНИЯ ПОЛИНОМОВ (57) Изобретение относится к области вычислительной техники и предназначено для использования в системах передачи информации, в цифровых вычислительных машинах, в которых время деления полиномов двоичной информации должно быть существенно меньше времени передачи двоичной информации по каналам связи. Целью изобретения является увеличение быстродействия. Устройство деления полиномов содержит вход делимого 1, триггерный регистр остатка 2, группы умножителей 3 на постоянную величину и группы сумматоров 4 по модулю два. В предлагаемом устройстве обеспечивается ускоренное деление полиномов двоичной информации при кодировании ее систематическим цикличесЖ ким кодом или при декодировании этого кода. I ил.

1444811

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

Целью изобретения является увеличение быстродействия.

Блок-схема устройства представлена на чертеже, Устройство содержит вход 1 делимого, регистр 2 остатка, группы умножителей 3 на коэффициент и групп r сумматоров 4 по модулю два, Количество разрядов r в регистре

2 и группах 3 и 4 равно степени полинома делителя ° Количество входов полинома делимого m не должно превышать r, кроме того, r должно делиться на m без остатка. Если исходный полином делимого содержит более чем m символов (битов), то он должен поступать на входы Вхо+Вх, сегментами по т разрядов в сегменте, причем на вход Вх должен поступать старший разряд каждого сегмента, и первым на Вх +Вх, должен поступать сегмент, содержащий старший разряд информационного полинома.

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

"1"„ Старший разряд (бит) любого полинома делителя-степени r, содержимое которого х, как и содержимое г о младшего разряда (бита) полинома х всегда равно 1 (х"=х.=1) в предлагаемом устройстве, как и в прототипе, не представляется.

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

Перед началом работы регистр 2 обнуляется. В первом такте деления на входы 1 (Вх +Вх ) параллельно поступают m разрядов кода сегмента информационного полинома, включающего старший разряд полинома.

Поскольку триггеры всех разрядов регистра 2, в том числе триггер старшего разряда, находятся в состоянии

"0" на первые входы всех сумматоров э

It I1

4 первой группы поступает код О на вторые входы всех сумматоров, кроме сумматора младшего разряда, также поступает код "О", на второй вход

10 сумматора младшего (О-ro) разряда этой группы поступает код старшего разряда (бита) информационного полинома с вхоца Вх . В результате на выходе всех сумматоров группы, кроме

15 сумматора младшего разряда, появляется код "О", на выходе последнего появляется код старшего разрядa (бита) информационного полинома., На первые входы всех сумматоров 4

20 второй группы с выхода r-ro суммато11 11 ра первой группы поступает код О на вторые входы этих сумматоров, кроме сумматоров двух младших разрядов, ве и также поступает код О, на второи вход сумматора 2-ro разряда поступает код старшего разряда информационного полинома с выхода сумматора младшего разряда первой группы, а на второй вход сумматора 1-ro разряда

30 поступает код второго разряда информационного полинома с входа Вх< устройства деления полиномов.

На выходах всех сумматоров 4 второй группы, кроме сумматоров 1-го и

11 11

2-го разрядов, установлен код 0, на выходе сумматора 2-ro разряда— ко д старшего, 1 - го разряда (бит а ) информационного полинома, на выходе сумматора 1 - ro разряда — код - ro ,10 разряда (бита ) информационного полинома .

Таким о бра э ом, ко д старшего ра зряда (бита ) информационного полинома сдвинут на один разряд вправо относительно положения на выходах сумма то ров пр едыдущей группы, а ко д второго разряда информационного полинома принят в младший, 1 -й разряд сумматора 4 второй группы .

Аналогичные процессы сдвига и приема последующих разрядов (битов) информационного полинома происходят в последующих группах, в результате которых ш разрядов первого, старшего сегмента информационноro полинома оказываются размещенными в младших разрядах сумматоров 4 последней группы, причем старший, 1-й разряд (бит) информационного полинома записан в

44811

15 з

14

m-й разряд m-й группы сумматоров 4, а m-й разряд информационного полинома — в младший, 1-й разряд сумматоров этой группы.

С выходов сумматоров 4 п-.é группы

"код первого сегмента поступает без сдвига в регистр 2 остатка.

Таким образом, в конце первого такта деления m разрядов кода старшего сегмента информационного полинома, начиная со старшего,,1-го разряда и кончая m-м, оказываются записанными в младших разрядах регистра остатка 2, причем старший разряд (бит) информационного полинома оказывается записанным в m-й разряд регистра 2, а m-й разряд полинома — в младший, 1-й, разряд регистра.

Во втором такте деления. на входы

1 устройства поступает второй m-разрядный сегмент информационного полинома, причем m+1-й разряд (бит) полинома поступает на вход Вх, à 2m-й 25 разряд (бит) полинома — на Вх„,. Одновременно с поступлением битов второго сегмента информационного полинома производится выдача битов первого сегмента этого полинома с реги- З0 стра 2 остатка в первую группу. Поскольку r-й разряд регистра 2 находится в состоянии "0" и не оказывает влияния на прохождение информации с триггеров регистра 2 и с входов 1 устройства через первую группу сумматоров по модулю два, на выходе последнего появляется информация (биты первого сегмента информационного полинома), сдвинутая на один разряд 40 вправо относительно находящейся в регистре 2, а в младшем разряде первой группы 4 (на выходе сумматора 1-го разряда) появляется старший, m+1 é разряд второго сегмента информационного полинома. Во второй группе 4, поскольку на выходе сумматора старшего, m-ro разряда первой группы 4 сохраняется код "О", эта информация сдвигается еще на один разряд вправо, 50 а на выходе младшего, 1-ro разряда этой группы поступает m+2-й разряд информационного полинома, Аналогичные процессы сдвига и приема происходят в последующих группах 4, в результате чего на выходах сумматоров 4

m-й группы устанавливается код битов двух сегментов информационного полинома, причем старший бит первого сегмента полинома окаэьпзается в 2m-м разряде блока, а младший бит второго сегмента — в младшем, 1-м разряде, Укаэанный код без сдвига переписывается в регистр 2 остатка, затем начинается третий такт деления, аналогичный предыдущим двум.

Процесс приема и сдвига кодов сегментов длится до тех пор, пока в результате очередного, k-го такта деления (k=r/m) старший разряд информационного полинома не окажется записанным в старший r-й разряд регистра 2 остатка, В (k+1)-м такте деления содержимым старшего разряда является "1", которая при опросе регистра 2 одновременно с поступлением битов очередного сегмента информационного полинома на входы 1 устройства поступает на входы всех умножителей 3, имеющихся в первой группе. На выходах тех разрядов умножителей 3, которые соответствуют коду "1", в одноименных разрядах порождающего полинома (полинома делителя) появляются сигналы

"1", которые поступают на первые входы связанных с ними сумматоров 4 по модулю 2 этой группы. На вторые входы этих сумматоров, как и в предыдущих тактах деления, поступают коды символов сегментов информационного полинома. Поэтому на r выходах сумматоров образуется сдвинутая на один разряд вправо поразрядная сумма г+1 старших разрядов информационного полинома любой степени и г+1 разрядов порождающего полинома (полинома делителя) степени г (с учетом того обстоятельства, что старшие разряды слагаемых — информационного и порождающего полиномов — всегда равны 1, их сумма по модулю два всегда равна нулю и для представления суммы по модулю два г+1 разрядов этих слагаемых нужно лишь r разрядов блоков устройства).

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

1444811

В11ИИПИ Заказ 6508/50 Тираж ное

Произв.-полигр. пр-тие, г. Ужгород, ул. Проектная, 4 битом информационного полинома) с кодом порождающего полинома.

В результате в конце (k+1)-го такта деления в регистре 2 остатка появляется остаток от деления k+1 сегментов информационного полинома любой степени на порождающий полином степени.

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

Устройство деления полиномов, содержащее регистр остатка, первую группу умножителей на коэффициент и первую группу сумматоров по модулю два, причем выход i-го разряда регистра остатка, где i=1,2,.. »r-1, (r — степень полинома делители) соединен с первым входом (i+1)-го сумматора по модулю два первой группы, вход старшего разряда полинома делимого соединен с первым входом первого сумматора по модулю два первой группы, вторые входы сумматоров по модулю два первой группы соединены с выходами соответствующих умножителей на коэффициент первой группы, вход синхронизации регистра остатка соединен с тактовым входом уствойства, о т л и ч а ю щ е е с я тем, что, с целью увеличения быстродейст" вия, в него введены с второй по m-ю группы умножителей на коэффициент и сумматоров по модулю два, где m— количество разрядов в одном сегменте операнда делимого, r кратно m входы разрядов с второго по m-й поли10 ном делимого соединены с первыми входами первых сумматоров по модулю два с второй по m-v групп, выходы

i-x сумматоров по модулю два )-й группы, rде j=l 2,...,m-1, соединены

15 с первыми входами (i+1)-x cy azopoa по модулю два (j+1) и группы, вторые входы всех сумматоров по модулю два

k-й группы, где k=2, 4,...,m, соединены с выходами соответствующих ум20 ножителей на коэффициент k-й группы, выход r-го разряда регистра остатка соединен с входами всех умножителей на коэффициент первой группы, выход

r-ro сумматора по модулю два (k-!)-й

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