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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Республик

< >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 (прототип) .