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

ОЮЗ СОВЕТСКИХОЦИАЛИСТИЧЕСКРЕСПУБЛИК 119) (1 4 0 06 Р 15 3 л ОПИСАН БРЕТЕНИ Б,Назым 10.Н. Поустройстания,с. 3-4.ы, ис 1976 ь Ву фр од нЭ. Ко. Мир,ОЛИНОМОВя к областипредназнасистемах ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ВТОРСКОМУ СВИДЕТЕЛЬСТВУ(56) Хетагуров Я.А.вышение надежностиметодами избыточногоМ.: Энергия, 1974,Питерсон У.,Уэлдправляв)цие ошибки,с, 200, рис, 7,6. 54) УСТРОЙСТВО ДЕЛЕНИЯ57) Изобретение относитычислительной техники иено для использования в передачи информации, в цифровых вычислительных машинах, в которых время деления полиномов двоичной информации должно быть существенноменьше времени передачи двоичной информации по каналам связи. Цельюизобретения является увеличение бы"стродействия. Устройство деления полиномов содержит вход делимого 1,триггерный регистр остатка 2, группы умножителей 3 на постоянную величину и группы сумматоров 4 по модулюдва. В предлагаемом устройстве обеспечивается ускоренное деление полиномов двоичной информации при кодировании ее систематическим циклическим кодом или при декодировании этого кода. 1 ил, 1444811Изобретение относится к вычислительной технике, а именно к устройствам обработки информации, и можетбыть использовано в системах информации и в цифровых вычислительных машинах, в которых время деления напорождающий полином передаваемой илипринимаемой информации должно бытьсущественно меньше времени передачидвоичной информации по каналам связи.Целью изобретения является увеличение быстродействия.Блок-схема устройства представлена на чертеже,Устройство содержит вход 1 делимого, регистр 2 остатка, группы умножителей 3 на коэффициент и групп 1сумматоров 4 по модулю два.Количество разрядов г в регистре2 и группах 3 и 4 равно степени полинома делителяКоличество входовполинома делимого ш не должно превьппать г, кроме того, г должно делиться на ш без остатка, Если исходный полином делимого содержит болеечем ш символов (битов), то он должен поступать на входы Вхо+Вх ., сегментами по ш разрядов в сегменте,причем на вход Вх должен поступатьстарший разряд каждого сегмента, ипервым на Вх 1+Вх , должен поступатьсегмент, содержащий старший разрядинформационного полинома.В простейшем случае, когда в предлагаемом устройстве реализуется деление информационного полинома наодин-единственный полином делителя,умножители на постоянную величинупредставляют собой перемычки, устанавливаемые в тех разрядах блоков, вкоторых полином делителя содержит"1" Старший разряд (бит) любогополинома делителя степени г, содержимое которого х , как и содержимоегомладшего разряда (бита) полинома хвсегда равно 1 (х =х.=1), в предлаогаемом устройстве, как и в прототипе,не представляется,Устройство работает следующим образом.Перед началом работы регистр 2 обнуляется, В первом такте деления на входы 1 (Вх +Вх ) параллельно поступают ш разрядов кода сегмента информационного полинома, включающего старший разряд полинома. Поскольку триггеры всех разрядоврегистра 2, в том числе триггер старшего разряда, находятся в состоянии110", на первые входы всех сумматоров11 114 первой группы поступает код Она вторые входы всех сумматоров, кроме сумматора младшего разряда, также поступает код "О", на второй вход10 сумматора младшего (О-го) разрядаэтой группы поступает код старшегоразряда (бита) информационного полинома с вхоца Вх . В результате навыходе всех сумматоров группы, кроме15 сумматора младшего разряда, появляется код "О", на выходе последнегопоявляется код старшего разряда (бита) информационного полинома.,На первые входы всех сумматоров 420 второй группь с выхода г-го суммато 11 11ра первой группы поступает код Она вторые входы этих сумматоров , кроме суммато ров двух младших разрядов ,11 Интакже поступает код О, на второивход сумматора 2-го разряда поступает код старшего разряда информационного полинома с выхода сумматорамладшего разряда первой группы, а навторой вход сумматора 1-го разряда30 поступает код второго разряда информационного полинома с входа Вх устройства деления полиномов,На выходах всех сумматоров 4 второй группы, кроме сумматоров 1-го и11 112-го разрядов , установлен код О ,на выходе сумматора 2-го разряда -ко д старшего , 1 - го разряда ( бит а )информационного полинома, на выходесумматора 1 - го разряда - код 2- го110 разряда ( бита ) информационно го полинома ,Таким о бра э ом , ко д старшего ра зряда ( бита ) информационного полинома сдвинут на один разряд вправоотносительно положения на выходахсумма то ров пр едыдущей группы , а ко двторого разряда информационного полинома принят в младший, 1 -й разрядсумматора 4 второй группы,50Аналогичные процессы сдвига и приема последующих разрядов (битов) инФормационного полинома происходят впоследующих группах, в результате которых ш разрядов первого, старшегосегмента информационного полиномаоказываются размещенными в младшихразрядах сумматоров 4 последней группы, причем старший, 1-Й разряд (бит)информационного полинома записан в44811 51015 з14щ-и разряд щ-й группы сумматоров 4,а щ-й разряд информационного полинома - в младший, 1-й разряд сумматоров этой группы.С выходов сумматоров 4 п-.й группы"код первого сегмента поступает безсдвига в регистр 2 остатка,Таким образом, в конце первого такта деления щ разрядов кода старшего сегмента информационного поли- нома, начиная со старшего 1-го разряда и кончая щ-м, оказываются записанными в младших разрядах регистра остатка 2, причем старший разряд (бит) информационного полинома оказывается записанным в щ-й разряд регистра 2, а щ-й разряд полинома - в младший, 1-й, разряд регистра.20Во втором такте деления на входы 1 устройства поступает второй щ-разрядный сегмент информационного поли- нома, причем щ+1-й разряд (бит) поли- нома поступает на вход Вх, а 2 щ-й 25 разряд (бит) полинома - на Вх,. Одновременно с поступлением битов второго сегмента информационного поли- нома производится выдача битов первого сегмента этого полинома с реги- З 0 стра 2 остатка в первую группу. Поскольку г-й разряд регистра 2 находится в состоянии "О" и не оказывает влияния на прохождение информации с триггеров регистра 2 и с входов 1 устройства через первую группу сумматоров по модулю два, на выходе последнего появляется информация (биты первого сегмента информационного полинома), сдвинутая на один разряд 40 вправо относительно находящейся в регистре 2, а в младшем разряде первой группы 4 (на выходе сумматора 1-го разряда) появляется старший, щ+1-й разряд второго сегмента информационного полинома. Во второй группе 4, поскольку на выходе сумматора старшего, ш-го разряда первой группы 4 сохраняется код "О", эта информация сдвигается еще на один разряд вправо, 50 а на выходе младшего, 1-го разряда этой группы поступает щ+2-й разряд информационного полинома, Аналогичные процессы сдвига и приема происходят в последующих группах 4, в результате чего на выходах сумматоров 4 щ-й группы устанавливается код битов двух сегментов информационного поли- нома, причем старший бит первого сегмента полинома окаэьпзается в 2 щ-мразряде блока, а младший бит второгосегмента - в младшем, 1-м разряде,Укаэанный код без сдвига переписывается в регистр 2 остатка, затем начинается третий такт деления, аналогичный предыдущим двум.Процесс приема и сдвига кодов сегментов длится до тех пор, пока в результате очередного, 1-го такта деления (К=г/щ) старший разряд информационного полинома не окажется записанным в старший г-й разряд регистра 2остатка,В (1+1)-м такте деления содержимым старшего разряда является 1", которая при опросе регистра 2 одновременно с поступлением битов очередного сегмента информационного поли- нома на входы 1 устройства поступает на входы всех умножителей 3, имеющихся в первой группе, На выходах тех разрядов умножителей 3, которые соответствуют коду "1", в одноименных разрядах порождающего полинома (поли- нома делителя) появляются сигналы "1", которые поступают на первые входы связанных с ними сумматоров 4 по модулю 2 этой группы. На вторые входы этих сумматоров, как и в предыдущих тактах деления, поступают коды символов сегментов информационного полинома. Поэтому на г выходах сумматоров образуется сдвинутая на один разряд вправо поразрядная сумма г+1 старших разрядов информационного полинома любой степени и г+1 разрядов порождающего полинома (полинома делителя) степени г (с учетом того обстоятельства, что старшие разряды слагаемых - информационного и порождающего полиномов - всегда равны 1, их сумма по модулю два всегда равна нулю и для представления суммы по модулю два г+1 разрядов этих слагаемых нужно лишь г разрядов блоков устройства).В зависимости от кода старшего разряда полученного результата, появляющегося на выходе сумматора г-го разряда первой группы 4, во второй группе произойдет либо сдвиг иа один разряд вправо результата и прием очередного символа информационного поли- нома в сумматор младшего разряда, либо сложение сдвинутого на один разряд результата (с принятым очередным.-полигр. пр-тие, г. Ужгород оектная,битом информационного полинома) с кодом порождающего полинома.В результате в конце (1+1)-го такта деления в регистре 2 остатка появляется остаток от деления 1+1 сегментов информационного полинома любой степени на порождающий полином степени. Формула изобретения Устройство деления полиномов, содержащее регистр остатка, первую группу умножителей на коэффициент и первую группу сумматоров по модулю два, причем выход .-го разряда регистра остатка, где 1.=1,2г, (г - степень полинома делители) соединен с первым входом (+1)-го сумматора по модулю два первой группы, вход старшего разряда полинома делимого соединен с первым входом первого сумматора по модулю два первой группы, вторые входы сумматоров по модулю два первой группы соединены с выходами соответствующих умножителей на коэффициент первой группы, вход синхронизации регистра остатка соединен с тактовым входом устройства, о т л и ч а ю щ е е с я тем, что, с целью увеличения быстродейст" вия, в него введены с второй по щ-ю группы умножителей на коэффициент и сумматоров по модулю два, где ш - количество разрядов в одном сегменте операнда делимого, г кратно щ, входы разрядов с второго по щ-й поли ном делимого соединены с первыми входами первых сумматоров по модулю два с второй по п 1-ю групп, выходы х-х сумматоров по модулю два 1-й группы, где 1=1,2 ш, соединены с первыми входами (+1)-х сумматоров по модулю два Д+1)-й группы, вторые входы всех сумматоров по модулю два 1 с-й группы, где К=2,4ш, соединены с выходами соответствующих ум ножителей на коэффициент К-й группы, выход г-го разряда регистра остатка соединен с входами всех умножителей на коэффициент первой группы, выход г-го сумматора по модулю два (Х)-й 25 группы соединен с входами всех умножителей на коэффициент К-й группы, выходы сумматоров по модулю два ш-й группы соединены с информационными входами соотВетствующих разрядов чп регистра. остатка.