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

1

Изобретение относится к технике связи а именно к технике помехоустойчивого кодирования, и может использоваться при построении :КОДИРУЮ1ЦИХ

и декодирующих устройств ,для переда- 5 чи данных, в телеграфии и телемеха нике.

Известны устройства для деления многочлена на многочлен, используемые для вычисления синдромов циклическо- О го кода 1.

Все эти устройства, однако, пригодны для обработки только двоичной информации .

Наиболее близким по техническому 15 решению к предлагаемому является уст ройство, содержащее элементы задержки, сумматоры, устройство умножения на постоянную величину, причем элементы задержки соединены друг с дру- 2О гом через сумматоры, вход первого сумматора является входом устройства, устройства умножения на постоянную величину включены между вторыми входами каждого сумматора и общим выходом 25 устройства, и дополнительное устройство умножения на постоянную величину, включенное между выходом последнего элемента йадержки и выходом устройства 2 .;30

Вид многочлена-делителя при данном построении устройства однозначно определяется схемой устройства. Однако, во многих случаях возникает необходимость в изменении этого мйагочлена. Подобная задача встречается, ;наП1римёр, в адаптивных системах связи, где используемый для помехоустойчивого кодирования код и соответствующий многочлен-делитель приходится изменять при изменении характеристик канала связи. Это приводит к тому, что возникает необходимость вносить значительные изменения в устройство: умножители с одним коэффициентом заменять на другие, исключать и вводить сумматоры, т.е. по существу одно устройство заменять другим.

Таким образом, жесткая связь между схемой и видом многочлена-делителя сужает область применения известного устройства.

Цель изобретения - расширение функциональных возможностей устройства путем обеспечения деления на произвольный многочлен без замены элементов устройства.

Указанная цель достигается тем, что в уст 5ойство для деления многочлена на многочлен, содержащее элементы задержки, сумматор, выход кото рого соединен со входом первого элемента зё1держки, и блок умножения на постоянную величину, вход которого подключен к выходу г-го элемента задержки, введбнег элемент памяти, блок умножения на переменную величину и переключатель, причем первый вход переключателя является входом делимо го устройстпа, вйХЬд пёреключатейя подсоединен к первому входу су,мматора, второй вход которого связан с вы ходом « блока умножения на переменную величину, а выход сумматора подключен ко входу первого элемейта, задерж ки, выход 1-го элемента задержки (1 1, ...., г - 1) связан со входом (i + 1)-го элемента заЩёржТкй, а выход г-го элемента задержки подключен ко второму входу переключателя, выход блока умножения на постоянную величину связан со входом элемента памяти, выход которого является выхо дом устройства и подсбединен к перво му входу блока умножения На переменную величину, второй вход которого является входом делителя устр6Йст1йа; Благодаря такому построению) струк турной схема возможно, используя дополнительный вход, изменять вид многочлена-делителя, а деление произ одними и тетли же элементами схёлы. Соединение f элементов задерж ки непосредственно друг с другом поз воляет использовать регистры на г ра рядов без промежуточных выводов, что существенно упрощает устройство и ув личивает его надежность. На фиг. 1 изображена функциональная схема предла;гаемьгб устройствау на фиг. 2 - временные диаграммы, пояс няющие работу устройства; на фиг.. 3 примерг р(эалйзацйй. Предлагаемое устройство для деления мНогочл эна на многочлен содержит последовательно соединенные непос- , ,рёдственно друг с другом элементы 1| - 1 f, задержки (по числу, равному максимальной степени делителя), к пе вбму из которых подключен выход .сумматора i, а к последнему - блок 3 ум ножения на постоянную величину К, информационный вход переключетеля 4, второй вход которого является основным входом устройства, предназначеНнглм дпя поступления многочлена-делимого. Устройство содержит такЖе элемент 5 памяти, вход которого соединен с выходом блока 3 умножения на постоянную величину, а выход подключен к информационному входу блока б умножения на переменную величину, второй вход которого является дополнительным входом устройства. Выход умножителя б на переменную соединен со вторым входом сумматора 2, первый вход которого подключен к выходу переключателя 4 .-- Коэффициенты многочлена-делиМОго в виде символов дискретного CHrHcUia (начиная со старшего коэффициента) пос,тупают на :ВХОД устройства. На дополнительный вход устройства подается информация о коэффициентах :многочлена-делителя. На выходе устройства .йсэяЬляются, один за другим коэффициенты многочлена-частного. После окончаний процесса деления в элементах Ij - IP задержки устройства-остаются символы, соответствующие коэффициентам многочлена-остатка. Цепи подачи тактовых импульсов на фиг. 1 не показаны. Тактовые импульсы продвигают информацию по регистру сдвига, образованному элементами 1 - 1р задержки, а также управляют работой переключателя и элемента 5 памяти. Частота следования тактовых импульсов установлена в (г + 1) раз большей, чем скорость поступления символов во входном сигнале (г - число элементов задержки в устройстве и, соответственно, максимальная степень многочлена, на который оно может делить). На интервале времени, занятом одним символом входного сигнала, помещается, таким образом, (г + 1) тактовый импульс. Тактовые импульсы разбивают этот интервал на отрезки равной длины-позиции, всего (г + 1) позиция. На первой позиции каждого интервала, занятого входным символом, переключатель 4 соединяет вход сумматора 2 с основным входом устройства, а в течение остальных г позиций - с выходом последнего элемента 1р задержки. Элемент 5 памяти принимает символ, приходящий на (. его вход с выхода блока 3 умножения на постоянную величину К на первой позиции, запоминает этот символ и удерживает его на своем выходе в течение (г + 1)-ой позиции, т.е. в течение всего интервала времени, занятого входным символом. На диаграмме а (фиг. 2) показаны границы интервалов времени, занятых символами, приходящими на вход устройства; на диаграмме 6 - тактовые импульсы; на диаграмме номера позиции, на которые тактовые импуЛьСы разбивают интервалы времени, занятые входными символами. На диагпотенциал логической единицы отмечает отрезки времени, на которых перекШчатёль 4 соединяет вход устройства с вkoдoм сумматора 2. На диаграмме показан пример сигнала, который может появиться на выходе блока умножения на постоянную е - сигвеличину, а на диаграмме нал, который сформирует в этом случае на своем выходе элемент 5 памяти. Коэффициенты многочлена-делителя подгиотся на дополнительный вход устройства с частотой следования тактовых ймпульсОв. Если деление произво дится на многочлен рХ+,, J ....-6о, то на дополнительный вход в течёйие каждого интервала времени, занятого одним символом на основном входе, должны поступить г + 1 символ- О,g.i , ... go- Блок 3 умножает на дД Процесс деления в устройстве Происходит следующим образом. Вначале в элементах li - It задер ки содержатся нули. Соответственно нуль одерживается на выходе элемента 5 памяти, а также на выходе блока, 6 умножения на переменную величину . В такой ситуации сумматор 2 повторяет на своем выходе информацию, приходящую (К нему с выхода переключателя 4. Когда на основном входе устройства появляется первый (ненулевой символ d ц старший коэффициент многочлен а-делимо го d(x) dnX + d. +... + dp, он записывается на первой позиции в первый элемент In задержки. После прохождения (г-тактовых импульсов, т.е. на послед йей позиции, символ d, выходит на вы ход последнего элемента IP задержки, Так как в устройстве имеется 1г после довательно соединенных элементов задержки, а число позиций равно {г + 1 то на каждом следующем интервале вре лени, занимаемом одним входным симво лом, символ dn поступает на выход элемента 1р задержки на одну позицию раньше. Через г входных символов, т.е. когда на вход приходит символ (dn - 2) символ dn выходит на выход элемента 1р задержки на первой позиции, после умножения .на постоянную д считывается элементом,5 и в течен%е tr + 1)-ой позиций удерживается на его выходе. Таким образом получа.ется первый коэффициент частного., дальнейшем устройство работ.рет Жнало гично с той только разницей, что для каждого коэффициента частного gj бло ка б умножения на переменную величину осуществляется его умножение на коэффициенты деления g р.,..., 3о произведения складываются в сумматоре 2 с символами, хранящимися в элементах задержки. Иными словами, для каждого коэффициента частного д из делимого вычитается многочлен (x) (g(x) - многочлен-делитель). Тем самым реализуется тот же алгоритм деления, что и в известном устройстве Более подробно работу устройства можно пояснить на примере для {двоичного случая, когда коэффициенты многочленов принимают значения О и 1. На фиг. 3 дан Пример реализации устройства, содержащего б элементов задержки (триггеров), что позволяет осуществлять делейие на произвольный многочлен шестой степени и ниже. Блок 3 умножения на постоянную осуществляет в данном конкретном случае операцию умножения на единицу, т.е, является повторителем. Блок б умножения на Переменную величину может быть выполнен в виде-двухвходовой схемы И, сумматором 2 является сумматор по модулю два, а Переключатель 4 выполняется по схеме 2И-ИЛИ. Рассмотрим работу устройства при делении многочлена d(x) х + х + + х +х+х +х +х+1 /на. многочлен д{х) х + х + X + 1, На ОСНОВНОЙ бход устройства должна поступать последовательность бит 10110010011011 (коэффициенты многочлена d(x)). На дополнительный вход устройства в кг1ждый интервал времени, занятый одним битом на основном входе, надо подать комбинацию бит вила 0111001 (коэффициент 0,g.i,gp.2,...,-gj Значения напряжения (логический нуль или логическая единица) в различных точках схемы фиг, 3 в процессе деления показаны в таблице. Здесь через i обозначен номер интервала, занятого символом на основном входе, через j - номер позиции внутри интервала. В столбце Основной показаны символы на основном входе устройства, в столбце Дополнительный вход - на дополнительном. В столбце а приведены символы на выходе умножителя на переменную (элемент И). В следующих столбцах б и показаны символы, приходжцие на вход сумматора по модулю два и символы на его выходе. Дгшее идут шесть столбцов llnll ||д«| Itptl ll.,.fl 1(11 ь. А/ I Ж Э/ и (регистр), в которых записаны символы, хранящиеся соответственно 1-ом, 2-ом, б-ом триггерах, а также столбец с сигналом на выходе устройства. Правило заполнения таблицы следуjotiiee. Вначале в триггерах содержатся 1Гута,йулй равен также символ на выхо де схемы. на выходе блочка умножения а получается перемножением символов в столбцах ДополниЬс-ельный вход и Вых, в той же строке. В столбец S на первой позиции переносится символ из столбца Ос но вной вход а на остальных из последнего столбца и регистра. Символ в столбце Ь получается сложением по модулю два символов из столбцов а и б, в каждый из Столбцов регистра записывается символ, который присутствует в предыдущей строке в предшес вующем столбце, В столбец ,Выход., заносится символ, который имеется на первой позиции этого же интервала в столбце И регистра, Как видно из таблицы на выход устройства поступает последовательность бит ООООООИ100111, что соответствует многочлену к + х + х + х + + X + 1. в триггерах остаются биты 001010, что соответствует многочлену X + X. Действительно, если разделить многочлен х + х + х + + X + X + 1 на X + X -+ X V X + + 1, то частное равно х + , а остаток х + х. Следовательно устройство выполняет функции деления многочлена на многочлен. Технико-экономический эффект изобретения заключается в том, что в то время, как известное устройство може выполнять деление только на один многочлен, коэффициенты которого задаются схемой, т.е. набором умножителей определенного вида и суйматоров предлагаемое устройствоможет делить на .Произвольный многочлен, коэффициенты кот)рого задаются символами, проходящими на дополнительный вход. Наиболее эффективно применение изобретения в адаптивных системах связи, в исследовательских комплексах, где необходимо оценить эффектив ность различных кодов и, потому, осу ществлять деление на различные много члены. Кроме того, преимуществом прёдлаг. емого устройства является то, что в нем элементы задержки соединены в ре гистр сдвига без промежуточных отводов. Такой регистр можно выполнить на одной микросхеме, что значительно уменьшает объем устройства. Так, напрймер, при многочлене-делителе 20-й степени известное устройство должно содержать 20 Элементо задержек, выполняемых на триггерах. При использовании наиболее распростр ненной интегральной серии 155 (и бол шинства других интегральных схем) эт составит 10 корпусов. Кроме того, в зависимости от вида многочлена необходимо иметь до 20 сумматоров по модулю 2, что также выражается в количестве 10 корпусов интегральных схем Умножители на постоянную представляю из себя в двоичном случаеповторители, и их количество (до 20 штук) определяет потребность еще в 4 - 5 корпусах. Всего, следовательно,--известное устройство содержит до 25 Корпусов интегральных схем. в предлагаемом устройстве элемены :задержки, соединенные; непосредстенно друг с другом, представляют из себя регистр без промежуточных выводов,в качестве которого можно использовать, например, интегральную схему типа К186ИРЗ ( 20-и разрядный регистр в одном корпусе). Единственный сумматор и переключатель составят еще один корпус. Умножигель на постоянную, считыватель и умножитель на переменную (как видно из схемы на фиг.З) могут быть выполнены не более (чем на 2 корпусах. Таким образом, предлагаемое устройство содержит в 5 - б раз меньше основных интегральных схем. Число вспомогательных схем, необходимых, например, для записи и продвижения импульсов в регистре или элементах задержки, организации тактовых импульсов ( на фиг. 1 не показанных) и т.п. примерно одинаково для обоих /устройств . Приведенный пример многочленa-fдeлителя является типичным для кодирую «их и декодирующих устройств помехоустойчивоГо кодирования, в которых может использоваться предлагаемое устройство деления многочлена на любой многочлен. Формула изобретения Устройство, для деления многочлена на многочлен, содержащее элементы задержки, сумматор, выход которого соединен со входом первого элемента задержки и блок умножения на постоянную величину, вход которого подключен к выходу г-го элемента задержки, отличающееся тем, что, с целью расширения его функциональных возможностей засчет обеспечения деления на произвольный многочлен, оно содержит элемент памяти, блок умножения на переменную величину и переключатель, причем первый вход переключателя является входом делимого УСТ,- ройства, выход переключателя подсоединен к первому входу сумматора, второй вход которого связан с выходом блока умножения на переменную величину, а выход сумматора подключен ко входу первого элемента задержки выход i-ro элемента задержки i 5 1, ...... г - 1);связан со входом (i + 1)-го элемента задержки, а выход г-го элемента задержки подключен ко второму входу переключателя, выход блока умножения на постоянную величину связан со входом элемента rtaмяти, выход которого является выходом устройства и подсоединен к первому входу блока умножения на .переменную величину, второй вход которого является входом делиЧ-еля устройства.

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР 478450, кл. G 06 F 7/00, 1973.

2. Питерсон У., Уэлдон Э. Ко,ды, исправляющие ошибки,Мир,

М., 1976, с. 199 - 200(прототип) .