Устройство деления полиномов Советский патент 1988 года по МПК G06F17/10 

Jik

ЭО

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

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

Блок-схема устройства представлена на чертеже.

Устройство содержит вход 1 делимого, регистр 2 остатка, группы умножителей 3 на коэффициент и группы сумматоров 4 по модулю два.

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

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

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

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

0

5

0

Поскольку триггеры всех разрядов регистра 2, в том числе триггер старшего разряда, находятся в состоянии О, на первые входы всех сумматоров 4 первой группы поступает код О, на вторые входы всех сумматоров, кроме сумматора 1-шад1пего разряда, также поступает код О, на второй вход сумматора младшего (0-го) разряда этой группы поступает код старшего разряда (бита) информационного полинома с входа ВХр. В результате на выходе всех сумматоров группы, кроме сумматора младшего разряда, появляется код О, на выходе последнего появляется код старшего разрдда (бита) информационного полинома.,

На первые- входы всех сумматоров 4 второй группы с выхода г-го сумматора первой группы поступает код О, иа вторые входы этих сумматоров, кроме сумматоров двух младших разрядов, также поступает код О, на второй 5 вход сумматора 2-го разряда поступает код старшего разряда информационного полинома с выхода с т матора младшего разряда первой группы, а на второй вход сумматора 1-го разряда поступает код второго разряда информационного полинома с входа Вх, устройства деления полиномов.

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

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

0

5

0

5

0

5

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

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

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

С выходов сумматоров 4 Птй группы код первого сегмента поступает без сдвига в регистр 2 остатка.

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

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

триггеров регистра 2 и с входов 1

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

5 О

5

0 g Q g

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

Процесс приема и сдвига кодов сегментов длится до тех пор, пока в результате очередного, k-ro такта- деления () старший разряд информационного полинома не окажется записанным в старший г-й разряд регистра 2 остатка,

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

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

5U

битом информационного полинома) с кодом порождающего полинома.

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

Фор М:У ла изобретения

Устройство деления полиномов, содержащее регистр остатка, первую группу умножителей на коэффициент и первую группу сумматоров по модулю два, причем выход i-ro разряда регистра остатка, где ,2,...,, (г - степень полинома делителя) соединен с первым входом {1+О-го сумматора по модулю два первой группы, вход старшего разряда полинома дели- :МОго соединен с первым входом первого сумматора по модулю два первой группы, вторые входы сумматоров по модулю два первой группы соединены с выходами соответствующих умножителей на коэффициент первой группы, вход синхронизации регистра остатка соединен с тактовьм входом устройтем.

ства, отличаю в; ееся что, с целью увеличения быстродействия, в него введены с второй по т-ю группы умножителей на коэффициент и сумматоров по модулю два, где m - количество разрядов в одном сегменте операнда делимого, г кратно т, входы разрядов с второго по т-й полином делимого соединены с первыми входами первых сумматоров по модулю два с второй по т-ю групп, выходы i-x сумматоров по модулю два j-й группы, где j ,2,... ,т-1, соединены

с первыми входами (i+l)-x сумматоров по модулю два (-И)-й группы, вторые входы всех сумматоров по модулю два k-й группы, где ,i4,... ,т, соединены с выходами соответствующих умножителей на коэффициент k-й группы, выход г-го разряда регистра остатка соединен с входами всех умножителей на коэффициент первой группы, вьосод г-го сумматора по модулю два (k-l)-й

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

регистра остатка.

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

ВНИИПИ Заказ 6508/50 Тираж 704

Произв.-прлигр. пр-тие, г. Ужгород, ул. Проектная, 4

Подписное