Устройство для деления многочлена на многочлен

ОПИСАНИЕ ИЗОБРЕТЕНИЯ Союз Советских Социалистических РеспубликК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ительное к авт. свид-в ено,060478 (21) 2639856/18-24 нением заявки Моитетиковвно 070780, Бюллетень Мо 25публиковвнияописания 0707,80(22 Заяв Кл.6 Г 7/39 Государственный комите СССР по делам изобретений и открытийП. Вольфбейн и В. Н, Сараев 1) Заявител ОЙСТВО ДЛЯ ДЕЛЕНИЯ МНО НА МНОГОЧЛЕНИзобретение относится к техникесвязи, а именно к технике помехоустойчивого кодирования, и может использоваться при построении кодирующихи декодирующих устройств для передачи данных, в телеграфии и телемеханике.Известны устройства для делениямногочлена на многочлен, используемыедля вычисления синдромов циклического кода (1),Все эти устройства, однако, пригодны для обработки только двоичной информации.Наиболее близким по техническому 1решению к предлагаемому является уст-.ройство, содержащее элементы задержки, сумматоры, устройство умноженияна постоянную величину, причем элементы задержки соединены друг с дру- Жгом через сумматоры, вход первогосумматора является входом устройства,устройства умножения на постоянную величину включены между вторымивходами каждого сумматора и общим выходом 2устройства, и дополнительное устройство умножения ьа постоянную величину,включенное между выходом последнегоэлемента задержки и выходом устройства (2)3 Вид многочлена-делителя при данном построении устройства однозначноопределяется схемой устройства. Однако, во многих случаях возникает необходимость в изменении этого мйагочлена. Подобная задача встречается, найример, в адаптивных системах связи,где используемый для помехбустойчивого кодирования код и соответствующиймногочлен-делитель приходится изменять при изменении характеристик канала.связи. Это приводит к тому, чтовозникает необходимость вносить значительные изменения в устройство: умножители с одним коэффициентоМ заменять на другие, исключать и вводитьсумматоры, т.е. по существу одно устройство заменять другим,Таким образом, жесткая связь междусхемой и .видом многочлена-делителясужает область применения известногоустройства.Цель изобретения - расширение функциональных воэможностей устройствапутем обеспечения деления на произвольный многочлен без замены элементов устройства.Указанная цель достигается тем,что в устройство 1 для деления миогочлена на многочлен, содержащее элеПредлагаемое устройство для деления многочлена на многочлен содержитпоследовательно соединенные непос- ., редственно друг с другом элементы11 - 1 задержки (по числу, равномумаксимальной степени делителя), к пер"вому из которых подключен выход .сумматора 2, а к последнему - блок 3 ум-.ножения на постоянную величину К,информационный вход переключетеля 4,второй вход которого является основным входом устройства, предназначенным для поступления многочлена-делимого. Устройство содержит также элемент 5 памяти, вход которого соединен с. выходом блока 3 умножения напостоянную величину, а выход подключен к информационному входу блока 6умножения на переменную величину,второй вход которого является допол-.нительным входом устройства, Выходумножителя б на переменную соединенсо вторым входом сумматора 2, первыйвход которого подкЛючен к выходу переключателя 4,менты задержки, сумматор, выход которого соединен со входом первого элемента задержки, и блок умножения на постоянную величину, вход которого подключен к выходу-го элемента задержки, введены элемент памяти, блок умножения на переменную величину иререключатель, причем первый вход переключателя является входом делимого устройст а, выход переключателя подсоединен к первому входу сумматора, второй вход которого связан с выходом . блока умножения на переменную величину, а выход сумматора подключен ко входу первого элемента задержки, выход 1-го элемента задержки (1 = 1, ;, г - 1) связан со входом (1 + 1)-го элемента зЩержкй, а выход г-го элемента задержки подключен ко второму входу переключателя, выход блока умножения на постоянную величину связан совходом элемента памяти, выход которого является выходом устройства и подсоединен к первому входу блока умножения напеременную величину, второй вход которого является входом делителя устройства.Благодаря такому .построеник(структурной схем возможно, используя дополнительный вход, изменять вид многочлена-делителя, а деление производить одними и.теми же элементами схем. Соединение Р элементов задержки непосредственно друг с другом поз" валяет использовать регистры на г раз. рядов без промежуточных выводов, что существенно упрощает устройство и увеличивает его надежность.На Фиг. 1 изображена функциональная схема предлагаемого устройСтва;" на фиг. 2 - временные диаграммы, пояс. няющие работу устройства; на фиг,. 3- пример" реализации. Коэффициенты многочлена-делимогов виде символов дискретного сигнала(начиная со старшего коэффициента)поступают на .вход устройства. На дополнительный вход устройства подается информация о коэффициентах многочлена-делителя, На выходе устройства,появляются, один эа другим коэффициенты многочлена-частного. После оконча"ния процесса деления в элементах1 1 - 1 задержки устройства. остаются10 символы, соответствующие коэффициентам многочлена-остатка.Цепи подачи тактовых импульсов на.Фиг. 1 не показаны.Тактовые имПульсы продвигают инфор.15 мацию по регистру сдвига, образованному элементами 1 - 1задержки, а так"же управляют работой переключателя3 и элемента 5 памяти.:Частота следования тактовых импульсов установлена2 О в (г + 1) раэ большей, чем скоростьпоступления символов во входном сигнале (г - число элементов задержки вустройстве и, соответственно, максимальная степень многочлена, на кото 25 рйй оно может делить) На интерв евремени, .занятом одним символом входного сигнала, помещается, таким образом, (г + 1) тактовый импульс. Тактовые импульсы разбивают этот интервална отрезки равной длины-позиции, всего (г + 1) позиция. На первой позиции каждого интервала, занятого входным символом, переключатель 4 соединяет вход сумматора 2 с основным входом устройства, а в течение остальЗ 5 ных г позиций - с выходом последнегоэлемента 1 р задержки, Элемент 5 памяти принимает символ, приходящий наего вход с выхода 5 лока 3 умноженияна постоянную величину К на первой40 позиции, запоминает этот символ иудерживает его на своем выходе в течение (г + 1)-ой позиции, т.е. в течение всего интервала времени, занятоговходным символом,На диаграмме а (фиг. 2) показаны границы интервалов времени, занятых символами, приходящими на входустройства; на диаграмме б - тактовые импульсы; на диаграмменомера позиций, на которые тактовыеимпульоы разбивают интервалы времени,занятые входными символами. На диаграмме гф потенциал логической единицы отмечает отрезки времени, на которых перечЛЮчатель 4 соединяет вход55 устройства свходом сумматора 2, Надиаграмме фдф показан пример сигнала, который может появиться на выходе блока умножения на постояннуювеличину, а на диаграмме 0 - сигщ нал, котоРый сформирует в этом случае на своем выходе элемент 5 памяти.Коэффициенты многочлена-делителяподаются на дополнительный вход устройства с частотой следования такто"вых имйульсов.Если деление произво.дится на многочленфХ"+д хг+фто на дополнительный вход в течениекаждого интервала времени, занятогоодним символом на основном входе,должны поступить г + 1 символ .О,дд.,до . Блок 3 умножает на дФПроцесс деления в устройстве происходит следующим образом.Вначале в элементах 11 - 1 задержки содержатся нули. Соответственно нуль одерживается на выходе элемента 5 памяти, .а также на выходе блока б умножения на переменную величину. В такой ситуации сумматор 2 повторяет на своем выходе информацию, приходящую к нему с выхода переклю чателя 4. Когда на основном входе устройства появляется первый )ненулевой символ с) старший коэффициент многочлена-делимого д(х) = Й х + + й х + + й, он записыва ется на первой позиции в первый элемент 1 задержки. После прохождения (г тактовых импульсов, т.е. на последней позиции, символ Й выходит на выход последнего элемента 1 г задержки., 25 Так как в устройстве имеется 1 гпоследовательно соединенных элементов за" держки, а число позиций равно (г + 1), то на каждом следующем интервале времени, занимаемом одним входным симво- ЗО лом, символ й поступает на выход элемента 1 задержки на одну позицию раньше. Через г входных символов, т,е. когда на вход приходит символ (д - 2) символ йп выходит на выход элемента 1 задержки на первой позиции, после умножения на постоянную дсчитывается элементом:5 и в теченйе г + 1)-ой позиций удерживается на его выходе. Таким образом получа.ется первый коэффициент частного.(, В 4 О дальнейшем устройство работает айало" гично с той только разницей, что для каждого коэффициента частного д блока 6 умножения на переменную величину осуществляется егоумножение на 45 коэффициенты деления д,до ипроизведения складываются в сумматоре 2 с символами, хранящимися в элементах задержки. Иными словами, для каждого коэффициента частного д( из 50 делимого вычитается многочлен д;д(х) (д(х) - многочлен-делитель) . Тем саьим реализуется тот же алгоритмделения, что и в известном устройствеБолее подробно работу устройстваможно пояснить на примере для двоичного случая, когда коэффициенты многочленов принимают значения 0 и 1.На фиг. 3 дан пример реализацииустройства, содержащего б элементовзадержки (триггеров), что позволяетосуществлять деление на произвольныймногочлен шестой степени и ниже. Блок3 умножения на постоянную осуществляет в данном конкретном случае операцию умножения на"единицу, т.е, является повторителем. Блок б умноженияна Переменную величину может бытьвыполнен в виде;двухвходовой схемы И,сумматором 2 является сумматор по модулю два, а переключатель 4 выполняется по схеме 2 И-ИЛИ.Рассмотрим работу устройства пиделении миогочлена й(х) = хф + х++ х + х + х 4 + хз+ х + 1 (на мноогочлен д(х) = хР:+ х + хф + хф + 1,На основной Вход устройства должнапоступать последовательность бит10110010011011 (коэффициенты многочлена. Й(х, На дополнительный входустройства в каждый интервал времени, занятый одним битом на основномвходе, надо подать комбинацию битвила 0111001 (коэффициент О,Дг-,Яг. -ф)Значения напряжения (логическийнуль или логическая единица) в различных точках схема фиг. 3 в процессе деления показаны в таблйце. Здесьчерез 1 обозначен номер интервала,занятого символом на основном входе,через- номер позиции внутри интервала. В столбце Основной вход показаны символы на основном входе устройства, в столбце фДополнительныйвход 1 - на дополнительном. В столбце .фаприведены символы на выходеумножителя на переменную (элемент И).В следующих столбцах 81 ф ипоказаны символы, приходящие на входсумматора по модулю два и символы наего выходе, Далее идут шесть столбцовлфи (регистр), в которых записанысимволы, хранящиеся соответственно1-ом, 2-ом, 6-ом триггерах, а такжестолбец с сигналом на выходе устройства,746512 Регистр к 9 о Регистр к Ф о к Ю СЭ ж г д з и 3 4 1 5 б о о 1 О 1 0 1 0 о о о о 1 0 о о 1 0 1 0 1 О о о о о1 О 1 0 о о Правило заполненйя таблйцы следуюцее. Вначале в триггерах содержатся ем символов в льный вход и роке. В столбе ции переноситс Основной вход ахбц хни ге ст 1- нули,нулю-равен также символ на выхо- ст де схем. Символ на выходе блока ум- зи ножения а получается перемноже Ц Я мво на1 2 3 4 5 б 7 1 2 3 4 5 б 7 1 2 3 4 5 б 7 2 3 4 5 б 7 о 1 1 1 0 0 1 0 1 1 1 о а о 0 0 о 0 о о о о 0 0 0 О о 0 о 1 о 1 1 о о 1 1 о о 1 о 1 1 о о 1 о 1 о о О о о 1 1 о о 1 о 1 О 1 о 0 0 о д 0 о 1 0 0 0 о о о 1 1 О о о е О о о 1 0 О О 1 0 1 1 о 0 1 1 1 о О 1 о 1 1 о а 1 1 о 0 1 1 0 о 1 1 о 1 2 .3 5 б 7 2 3 4 5 б 7 а 1 1 о о 1 0 о о о 0 0 0 0 1 1 о о 1 1 1 1 0 1 1 о 1 0 0 1 о О о о о 0 1 1 1 олВы1 1сиа Дополнитой жепервой поз столбцатальных "из последнего столбца И регистра. Символ в столбце Ь получается сложением по модулю два символов из столбцов О и 1 Я. В каждый из столбцов регистра записывается символ, который присутствует в предыду щей строке в предшествующем столбце, В столбец ,Выход. заносится символ, который имеется на первой позиции этого же интервала в столбце И регистра. 10Как видно из таблицы на выход устройства поступает последовательность бит 00000011100111, что соответствует многочлену х 7 + хь + х + х + + х + 1, В триггерах остаются биты 001010, что соответствует многочлену х + х. Действительно, если разделить многочлен х 1 З + хи + Х 10 + х 7 +Х 4 + + х+ х + 1 на х+ х + х 4+ х+ + 1, то частное равно х + х + хф + + х + х + 1, а остаток х + х, Следовательно устройство выполняет функции деления многочлена на многочлен.Технико-экономический эффект изобретения заключается в том, что в то время, какизвестное устройство мо жет выполнять деление только на один многочлен, коэффициенты которого задаются схемой, т.е, набором умножителей определенного вида и сумматоров, предлагаемое устройство может делить 30 на 1 произвольный многочлей, коэффициенты которого задаются символами, проходящйми на дополнительный вход.Наиболее эффективно применение изобретения в адаптивных системах . 35 связи, в исследовательских комплексах, где необходимо оценить эффективность различных кодов и, потому, осу" ществлять деление на различные много- члены.40Кроме того, преимуществом предлагаемого устройства являЕтся то,что в нем элементы задержки соединены в регистр сдвига без промежуточных отводов, Такой регистр можно выполнить на одной микросхеме, что значительно уменьшает объем устройства.Так,например при многочлене-де" лителе 20-й степени известное уст.ройство должно содержать 20 элементов задержек, выполняемых на триггерах. При использовании наиболее распростра-. ненной интегральной серии 155 (и большинства других интегральных схем) это составит 10 корпусов. Кроме того, в зависимости от вида многочлена необ ходимо иметь до 20 сумматоров по модулю 2, что также выражается в количестве 10 корпусов интегральных схем. Умножители на постоянную представляютиз себя в двоичном случае повторите ли, и их количество (до 20 штук) определяет потребность еще в 4 - 5 кор" пусах. Всего, следовательно,: известное устройство содержит до 25 корпусов интегральных схем. у 5 В предлагаемом устройстве элементы "задержки, соединенные; непосредственнс друг с другом, представляют из себя регистр безпромежуточных выводов,в качестве которого можно использовать, например, интегральную схему типа К 186 ИРЗ ( 20-и разрядный регистр в одном корпусе). Единственный сумматор и переключатель составят еще один корпус. умножи 1 тель на постоянную, считыватель и умножитель на переменную (как видно из схемы на фиг,З) могут быть выполнены не более чем на 2 корпусах.Таким образом, предлагаемое устройство содержит в 5 - б раз меньше основных интегральных схем. Число вспомогательных схем, необходимых, например, для записи и продвижения импульсов в регистре или элементах задержки, организации тактовых импульсов ( на фиг. 1 не показанных) и т.п, примерно одинаково для обоих устройств.Приведенный пример многочлена-,делителя является типичным для кодирую цих и декодирующих устройств помехоустойчивоГо кодирования, в которых может использоваться предлагаемое устройство деления многочлена на любой многочлен.Формула изобретенияУстройство для деления многочлена на многочлен, содержащее элементы задержки, сумматор, выход которого соединен со входом первого элемента задержки и блок умножения на постояннуюУвеличину, вход которого подключен к выходу к-го элемента задержки, о тл и ч а ю щ е е с я тем, что, сцелью расширения его функциональных возможностей засчет обеспечения деления на произвольный многочлен, оносодержит элемент памяти, блок умноженияна переменную величину и переключатель, причем первый вход переключателя является входом делимого уст ройства, выход переключателя подсоединен к первому входу сумматора, второй вход которого связан с выходом блока умножения на переменную величину, а выход сумматора подключен ко входу первого элемента задержки выход 1-го элемента задержки 1(,1- 1, , к - 1)связан со входом (1 + 1)-го элемента задержки, а выход к"го элемента задержки подключен ко второму входу переключателя, выход блока умножения на постоянную ве" личину связан со входом элемента йамяти, выход которогс является выходом устройства и подсоединен к первому входу блока умножения на переменную величину, второй вход которого является входом делителя устройства.746512 Источники информации,принятые во внимание при экспертизе 1. Авторское свидетельство СССР 9 478450, кл, С 06 Р 7/00, 1973, Фиа Ц)иг д Составитель В.Субботиндактор Я.Алексеенко Техред О, Андрейко Корректо тник Тираж 751го комитета СССРий и открытийаушская наб., д. 4/ дписно ал ППП фПатент, г. Ужгород, ул на аказ 4103/17 ЦНИИПИ 1 осударственн по,делам: изобрете 113035, Москва, Ж, 2. Питерсон У , Уэлдон Э. Ко,ды, исправляюцие ошибки, фМир,М., 1976, с. 199 - 200 (прототип),