Устройство для деления многочлена на многочлен
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
Союз Советских
Социалистических
Республик
< >746512 (61) Дополнительное к авт. свид-ву (22) Заявлено, 060478 (21) 2639856/18-24 (51)М. Кл.
G 06 F 7/39 с присоединением заявки ¹
Государственный комитет
СССР по делам изобретений и открытий (23) Приоритет
Опубликовано 0707.80. Бюллетень ¹ 25 (53) УДК 621,3 (088.8
Дата опубликования описания 0707.80 (72) Авторы изобретения
С. П. Вольфбейн и B. Н. Сараев (71) Заявитель (54) YCTPOACTBO QJIH QEJIEHHH MHOFOgglZHA
HA МНОГОЧЛЕН
Изобретение относится к технике связи, а именно к технике помехоустойчивого кодирования, и может использоваться при построении .кодирующих и декодирующих устройств для переда- 5 чи данных, в телеграфии и телемеханике.
Известны устройства для деления многочлена на многочлен, используемые для вычисления синдромов циклического кода (1) °
Все эти устройства, однако, пригодны для обработки только двоичной информации.
Наиболее близким по техническому 15 решению к предлагаемому является устройство, содержащее элементы задержки, сумматоры, устройство умножения на постоянную величину, причем элементы задержки соединены друг с дру- Х/ гом через сумматоры, вход первого сумматора является входом устройства, устройства умножения на постоянную величину включены между вторыми входами каждого сумматора и общим выходом 25 устройства, и дополнительное устройство умножения ьа постоянную величину, включенное между выходом последнего элемента задержки и выходом устройства (2) . 30
Вид многочлена-делителя при данном построении устройства однозначно определяется схемой устройства. Однако, во многих случаях возникает необходимость в изменении этого мйагочлена. Подобная задача встречается, на йример, i адаптивных системах связи, где используемый для помехбустойчивого кодирования код и соответствующий многочлен-делитель приходится изменять при изменении характеристик канала.связи. Это приводит к тому, что возникает необходимость вносить значительные изменения в устройство: умножители с одним коэффициентоМ заменять на другие, исключать и вводить сумматоры, т.е. по существу одно устройство заменять другим.
Таким образом, жесткая связь между схемой .и .видом многочлена-делителя сужает область применения известного устройства
11ель изобретения - расширение функциональных воэможностей устройства путем обеспечения деления на произвольный многочлен без замены элементов устройства.
Указанная цель достигается тем, что в устройство 1для деления многочлена на многочлен, содержащее эле746512
Предлагаемое устройство для деления многочлена на многочлен содержит последовательно соединенные непос- ., редственно друг с другом элементы
11 - 1 задержки (по числу, равному максимальной степени делителя), к первому из которых подключен выход .сумматора 2, а к последнему - блок 3 ум-. ножения на постоянную величину K информационный вход переключетеля 4, второй вход которого является основным входом устройства, предназначенным для поступления многочлена-делимого. Устройство содержит также элемент 5 памяти, вход которого соединен с. выходом блока 3 умножения на постоянную величину, а выход подключен к информационному входу блока б умножения на переменную величину, второй вход которого является допол-нительным входом устройства. Выход умножителя б на переменную соединен со вторым входом сумматора 2, первый вход которого подкЛючен к выходу переключателя 4.- -1 менты задержки, сумматор, выход которого соединен со входом первого элемента задержки, и блок умножения на постоянную величину, вход которого подключен к выходу -го элемента задержки, введенй элемент памяти, блок умножения на переменную величину и переключатель, причем первый вход переключателя является входом делимого устройст- а, выход переключателя подсоединен к первому входу сумматора, второй вход которого связан с вы: ходом . блока умножения на переменную величину, а выход сумматора подклю чен ко входу первого элемента задержки, выход |-го элемента задержки (1 = 1, ;..., г — 1) связан со входом (1 + 1)-го элемента зЩержкй, а выход r-го элемента задержки подклю чен ко второму входу переключателя, выход блока умножения на постоянную величину связан со входом элемента памяти, выход которого является выходом устройства и подсоединен к irepsoму входу блока умножения на переменную величину, второй вход которого является входом делителя устройства.
Благодаря такому .построеник(структурной схем возможно, используя дополнительный вход, изменять вид многочлена-делителя, а деление производить одними и.теми же элементами схем. Соединение Р элементов задержки непосредственно друг с другом позваляет использовать регистры на г разрядов без промежуточных выводов, что существенно упрощает устройство и увеличивает его надежность.
На фиг. 1 изображена функциональная схема предлагаемого устройСтва на фиг. 2 — временные диаграмвы, поясняющие работу устройства; на фиг,. 3пример- реализации.
Коэффициенты многочлена-делимого
s виде символов дискретного сигнала (начиная со старшего коэффициента) поступают на вход устройства. На дополнительный вход устройства подается информация о коэффициентах многочлена-делителя. На выходе устройства ,йоявляются,один эа другим коэффициенты многочлена-частного. После окончания процесса деления в элементах
1 1 - 1„ задержки устройства-остаются символы, соответствующие коэффициентам многочлена-остатка.
Цепи подачи тактовых импульсов на фиг. 1 не показаны.
Тактовые импульсы продвигают инфорt5 мацию по регистру сдвига, образованному элементами 1 — 1 задержки, а также управляют работой переключателя ф и элемента 5 памяти.:Частота, следования тактовых импульсов установлена
2р в (г + 1) раэ большей, чем скорость поступления символов во входном сигнале (r — число элементов задержки в устройстве и, соответственно, максимальная степень многочлена, на кото*25 рйй оно может делить) На интерв е времени, .занятом одним символом входного .сигнала, помещается, таким образом, (г + 1) тактовый импульс. Тактовые импульсы разбивают этот интервал на отрезки равной длины-позиции, всего (r + 1) позиция. На первой пози. ции каждого интервала, занятого входным символом, переключатель 4 соединяет вход сумматора 2 с основным входом устройства, а в течение осталь ных r позиций - с выходом последнего элемента 1р задержки. Элемент 5 памяти принимает символ, приходящий на его вход с выхода блока 3 умножения на постоянную величину К на первой
4р позиции, запоминает этот символ и удерживает его на своем выходе в течение (r + 1)-ой позиции, т.е. в течение всего интервала времени, занятого входным символом.
На диаграмме а (фиг. 2) показаны границы интервалов времени, занятых символами, приходящими на вход устройства; на диаграмме б — тактовые импульсы1 на диаграМме номера позиций, на которые тактовые импульоы разбивают интервалы времени, занятые входными символами. На диаграмме г потенциал логической единицы отмечает отрезки времени, на которых переч йочатель 4 соединяет вход
55 устройств c âõîäoì сумматора 2. На диаграмме д показан пример сигнала, который может появиться на выходе блока умножения на постоянную величину, а на диаграмме 0 — сиг р нал, который сформирует в этом случае на своем выходе элемент 5 памяти.
Коэффициенты многочлена-делителя подаются на дополнительный вход устройства с частотой следования тактовых имйульсов. Если деление произво.
746512 дится на многочленф„X "i(Ä < X"- i...+ф„ то на дополнительный вход в течение каждого интервала времени, занятого одним символом на основном входе, должны поступить r + 1 символ .О,g д„., ... go Блок 3 умножает на g
l !
1 О °
Процесс деления в устройстве происходит следующим образом.
Вначале в элементах 1! - 1„ задержки содержатся нули. Соответственно нуль одерживается на выходе элемента 5 памяти, .а также на выходе блока б умножения на переменную величину. В такой ситуации сумматор 2 повторяет на своем выходе информацию, приходящую к йему с выхода переклю- 5 чателя 4. Когда на основном входе устройства появляется первый )ненулевой символ d „ старший коэффициент многочлена-делимого d(x) = d х + и-i
+ d„, х +... + о„, он записыва- 21 ется на первой позиции в первый элемент 1„ задержки. После прохождения (r тактовых импульсов, т.е. на последней позиции, символ Й„ выходит на выход последнего элемента 1!. задержки., 35
Так как в Устройстве имеется г„последовательно соединенных элемейтов задержки, а число позиций равно (r + 1), то на каждом следующем интервале времени, занимаемом одним входным симво- щ() лом, символ d!! поступает на выход элемента 1„ задержки на одну позицию раньше. Через r входных символов, т.е. когда на вход приходит символ (dя — 2) символ d!! выходит на выход 35 элемента 1„ задержки на первой позиции, после умножения на постоянную
g„ ñ÷èTûâàåòñÿ элементом:5 и в тече-!!яе (r + 1)-ой позиций удерживается на его выходе. Таким образом получа.ется первый коэффициент частного.(, В О дальнейшем устройство работает айало" гично с той только разницей, что для каждого коэффициента частного g бло3 ка 6 умножения на переменную величину осуществляется его умножение íà 45 коэффициенты деления g „,...Ä g и
1 произведения складываются в сумматоре 2 с символами, хранящимися в элементах задержки. Иными словами, для каждого коэффициента частного g(из 50 делимого вычитается многочлен д;g(х) (g(х) — многочлен-делитель) .
Тем сам!м реализуется тот же алгоритм деления, что и в известном устройстве
Более подробно работу устройства можно пояснить на примере для двоичного случая, когда коэффициенты многочленов принимают значения 0 и 1.
На фиг. 3 дан пример реализации устройства, содержащего б элементов задержки (триггеров), что позволяет осуществлять деление на произвольный многочлен шестой степени и ниже. Блок
3 умножения на постоянную осуществляет в данном конкретном случае операцию умножения на"единицу, т.е, является повторителем. Блок б умножения на Переменную величину может быть выполнен в виде:,двухвходовой схемы И, сумматором 2 является сумматор по модулю два, а переключатель 4 выполняется по схеме 2И-ИЛИ.
Рассмотрим работу устройства при делении миогочлена d(x) = х!З + х +
+ х + х + х4 + хз+ х + 1(на мно-! о гочлен g(x) = х :+ х + х + х + 1, На основной Вход устройства должна поступать последовательность бит
10110010011011 (коэффициенты многочлена. Й(х)). На дополнительный вход устройства в каждый интервал времени, занятый одним битом на основном входе, надо подать комбинацию бит вила 0111001 (коэффициент О,g„<,Д, Значения напряжения (логический нуль или логическая единица) в различных точках схем! фиг. 3 в процессе деления показаны в (таблйце. Здесь через i обозначен номер интервала, занятого символом на основном входе, через j - номер позиции внутри интервала. В столбце Основной вход показаны символы на основном входе устройства, s столбце Дополнительный вход! - на дополнительном. В столбце !a приведены символы на выходе умножителя на переменную (элемент И).
В следующих столбцах !6! и Ь! показаны символы, приходящие на вход сумматора по модулю два и символы на его выходе. Далее идут шесть столбцов !! !!! ° !Ф! ° !Э! I !!!!э!! !и! (регистр), в которых записаны символы, хранящиеся соответственно
1-ом, 2-ом, 6-ом триггерах, а также столбец с сигналом на выходе устройства.
746512
Регистр к ф) о
Регистр к
lQ
TсЭ
С> к
Ф о
«- (к
Ю
C) D и ж д е о о
1 1
1 1 з
4 4 1
5 б о о
1 О
1 О
1 О о о о о
1 О о о
1 О
1 О
1 О о о о о
14
0 1
Правило заполненйя« таблйцы следур цее. Вначале в триггерах содержатся ем символов в льный вход и роке. В столбе ции переноситс
Основной вход ах бц х
I ни те ст
I в на и ос нули, нулю равен также cHMBoJI на выхо- ст де схем. Символ на выходе блока ум- зи ножения а получается перемноже- 65
Ц
Я мво на
2 з
5 б
2 з
5 б
2 з
5
1
3
5 б
7 о
1
О
О
О
1
1 о а
1 о О
О о
О о о о о
О
О
О
О о о
1 о о
О о
О
1 о
1 о
1 о о
1 о
1 о о
О о
О
1 о
0 о д
О о
О
О
0 о
1 о о
О
1 о о
1
О
0 е
О о о
О
О
О
1 о
О
1 о
О
1 о
1 о о
1 о
1
О о
1 о
2 .3
5 б
2
4
5 б
1
1
О о
О о о о
О
О
О
1
О о
1
О
1
1
О
О
1 о
О о
О
1
О
О о о о
О
1
1 ол Вы
1 1 си а Дополнитой же первой поз столбца тальных74б 512
10 из последнего столбца И регистра.
Символ в столбце Ь получается сложением по модулю два символов из столбцов С1 и Я . В каждый из столбцов регистра записывается символ, который присутствует в предыду- 5 щей строке в предшествующем столбце.
В столбец, Выход . заносится символ, который имеется на первой позиции этого же интервала в столбце И регистра. 10
Как видно из таблицы на выход устройства поступает последовательность бит 00000011100111, что соответствует многочлену х7 + х 6 + x + х +
+ х + 1. В триггерах остаются биты
001010, что соответствует многочлену х + х. Действительно, если разделить многочлен х13 + Х11 + Х10 +.. x7 + Х4 +
+ х + х+ 1 на х + х + х4+ х +
+ 1, то частное равно х + х + х +
+ х + х + 1, а остаток x> + х. Следовательно устройство выполняет функции деления многочлена на многочлен.
Технико-экономический эффект изобретения заключается в том, что в то время, как известное устройство мо- 25 жет выполнять деление только на один многочлен, коэффициенты которого задаются схемой, т.е. набором умножителей определенного вида и сумматоров, предлагаемое устройство может делить 30 на 1произвольный многочлей, коэффициенты которого задаются символами, проходящйми на дополнительный вход.
Наиболее эффективно применение изобретения в адаптивных системах . Я5 связи, в исследовательских комплексах, где необходимо оценить эффективность различных кодов и, потому, осу" ществлять деление на различные многочлены.
Кроме того, преимуществом предлагаемого устройства являЕтся то, что в нем элементы задержки соединены в регистр сдвига без промежуточных отводов. Такой регистр можно выполнить на одной микросхеме, что значительно уменьшает объем устройства.
Так, например при многочлене-делителе 20-й степени известное уст.ройство должно содержать 20 элементов задержек, выполняемых на триггерах.
При использовании наиболее распростра-. ненной интегральной серии 155 (и большинства других интегральных схем) это составит 10 корпусов. Кроме того, в зависимости от вида многочлена необ- 55 ходимо иметь до 20 сумматоров по модулю 2, что также выражается в количестве 10 корпусов интегральных схем.
Умножители на постоянную представляют из себя в двоичном случае повторите- 60 ли, и их количество (до 20 штук) определяет потребность еще в 4 — 5,кор" пусах. Всего, следовательно,= известное устройство содержит до 25 корпусов интегральных схем.
В предлагаемом устройстве элементы ". задержки, соединенные; непосредственнс друг с другом, представляют из себя регистр без промежуточных выводов,в качестве которого можно использовать, например, интегральную схему типа K186ИРЗ (20-и разрядный регистр в одном корпусе). Единственный сумматор и переключатель составят еще один корпус. Умножи1тель на постоянную, считыватель и умножитель на переменную (как видно из схемы на фиг.3) могут быть выполнены не бо лее чем на 2 корпусах.
Таким образом, предлагаемое устройство содержит в 5 — б раз меньше основных интегральных схем. Число вспомогательных схем, необходимых, например, для записи и продвижения импульсов в регистре или элементах задержки, организации тактовых импульсов (на фиг. 1 не показанных) и т.п. примерно одинаково для обоих устройств.
Приведенный пример многочлена-, делителя является типичным для кодирую цих и декодирующих устройств помехоустойчивоГо кодирования, в которых может использоваться предлагаемое устройство деления многочлена на любой многочлен.
Формула изобретения
Устройство для деления многочлена на многочлен, содержащее элементы задержки, сумматор, выход которого соединен со входом первого элемента задержки и блок умножения на постоянную
I величину, вход которого подключен к выходу r-ro элемента задержки, о тл и ч а ю щ е е с я тем, что, с целью расширения его функциональных возможностей за счет обеспечения деления на произвольный многочлен, оно содержит элемент памяти, блок умножения на переменную величину и переключатель, причем первый вход переключателя является входом делимого уст ройства, выход переключателя подсоединен к первому входу сумматора, второй вход которого связан с выходом блока умножения на переменную величину, а выход сумматора подключен ко входу первого элемента задержки выход 1-ro элемента задержки (i — 1, ....., к — lj связан со входом (i + 1)-го элемента задержки, а выход r-ro элемента задержки подключен ко второму входу переключателя, выход блока умножения на постоянную величину связан со входом элемента йамяти, выход которогс является выходом устройства и подсоединен к первому входу блока умножения на .переменную величину, второй вход которого является входом делителя устройства.
746512
Фие 2
Ц)иг. 4
Составитель В.Субботин
Техред О. Андрейко КорректоР Г.Решетник
Редактор Л.Алексеенко
Подписное
Заказ 4103/17 Тираж 751
ЦНИИПИ Foñóäàðñòâåííoão комитета СССР по,делам: изобретений и открытий
1 к янаб.. 4 5
13035, Москва, Ж 35, Раушс а, д /
Филиал ППП Патент, г. Ужгород, ул. Проектная, 4
Источники информации, принятые во внимание при экспертизе
1. Авторское свидетельство СССР
9 478450, кл. G 06 F 7/00, 1973.
2. Питерсон У, Уэлдон Э. Коисправля @ие otIIH6KH MHp
М., 1976, с. 199 — 200 (прототип) .
