Устройство для приведения полиномов по модулям циклотомических полиномов

 

Изобретение относится к вычислительной технике и предназначено 32 для использования в системах цифровой обработки сигналов. Устройство реализует итерационный алгоритм вычисления остатков полинома по модулям неприводимых полиномов. С целью сокращения аппаратурных затрат в устройство , содержащее регистры 5-7, счетчики 1-3, элементы ИЛИ 21 - 23, группы элементов И 9- - 11, элемент 25 задержки, элемент 27 сравнения, сумматор 17, группу элементов ИЛИ 19, элемент НЕ 24 и триггер 28, введены регистр 4, элемент ИЛИ 20, группа элементов И 8, элемент 26 сравнения вычитатель 29, группа элементов 18 задержки, блоки 15, 16 памяти, мультиплексоры 13, 14 и демультиплёксор 12. 2 ил. i (Л СлЭ СП со 4 00 ful I

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН (1gl (11) <511 4 G 06 F 7 / 5 4 4

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А BTOPCHOMY СВИДЕТЕЛЬСТВУ.то я

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPblTVM (21) 3965533/24-24 (22) 16.10.85 (46) 07.12.87. Бюл. ¹ 45 (71) Таганрогский радиотехнический институт им. В.Д.Калмыкова (72) И.М.Криворучко, К.Г.Иваненко, В.М.Витиско и В.В.Карпенко (53) 681.325(088.8) (56) Авторское свидетельства СССР

¹- 1320804, кл. G 06 F 7/544, 1986.

Авторское свидетельство СССР № 1180883, кл. G 06 F 7/544, 1984. (54) УСТРОЙСТВО ДЛЯ ПРИВЕДЕНИЯ ПОЛИНОМОВ ПО МОДУЛЯМ ЦИКЛОТОМИЧЕСКИХ ПОЛИНОМОВ (57) Изобретение относится к вычислительной технике и предназначено для использования в системах цифровой обработки сигналов ° Устройство реализует итерационный алгоритм вычисления остатков полинома по модулям неприводимых полиномов. С целью сокращения аппаратурных затрат в устройство, содержащее регистры 5 — 7, счетчики 1 — 3, элементы ИЛИ 21 — 23, группы элементов И 9. — 11, элемент

25 задержки, элемент 27 сравнения, сумматор 17, группу элементов ИЛИ 19, элемент НЕ 24 и триггер 28, введены регистр 4, элемент ИЛИ 20, группа элементов И 8, элемент 26 сравнения вычитатель 29, группа элементов 18 задержки, блоки 15, 16 памяти, мультиплексоры 13, 14 и демультиплексор

12. 2 ил.

1357948

Устройство реализует следующий метод вычисления остатков полинома по модулям неприводимых полиномов

2 — 1, z + 1, 2 + 1 ».. z + 1»

На первом этапе вычисляются суммы и разности входных данных массива ао хо + хн)2 а.1

a> = х(«,), — х н, . Разности на .следующих этапах не используются и являются коэффициентами при переменных z z ... г z полино (H)2\-Ч (нИ)-2 о ма X(z) mod (z""+ 1) . Суммы, полуИзобретение относится к вычислительной технике и предназначено для использования в системах цифровой об" работки сигналов.

Цель изобретения — сокращение an- 5 паратурных затрат, . Ha фиг. 1 представлена функциональная схема устройства; на.фиг. 2 циклограмма его работы.

Устройство содержит счетчики 1-3, регистр 4-7, группы 8-11 элементов И, демультиплексор 12, мультиплексоры

13 и 14, блоки 15 и 16 памяти, сумматор 17, группу 18 элементов задержки, группу 19 элементов ИЛИ,элементы ИЛИ 20-23, элемент НЕ 24, элемент 25 задержки, элементы 26 и 27 сравнения, триггер 28, вычитатель

29, входы 30-33 сброса, начальных данных, синхронизации и информацион- 20 ный и выход 34 устройства.

Приведение по модулям. неприводимых полиномов является первым этапом при реализации алгоритма свертки

?5 (или корреляции) на основе полиномиальных преобразований. С этой целью входная последовательность jx;) где

i = О, 1,...,N-1, должна быть представлена в виде полинома степени

N-1 переменной z причем входные сло- 30 ва х являются коэффициентами поли1 нома X(z) = х„z +...+ х,к + х,.

Аналогично представляется передаточН-1 ная функция H(z) = h,,z + ...+

+ h, z + h, . Выходной полином Y(z) вычисляется как произведение X(z) и

H(z) по модулю некоторого полинома

P(z): Y(z) = X(z) H(z) mod P(z)

N-< у z + ...+ у, z + у, . Восстановление полинома Y(z) по китайской 40 теореме об остатках для полиномов приводит к получению выходной последовательности (у.)), где j = О, 1, !

° ° ° » N 1 ° ченные на первом этапе (их число

N/2), используются для аналогичной процедуры на втором этапе: а„ = а, + ай(ф appal а а (H(4) tl S ° ° ° З»a Nt(H(4) аgjq з aН(Н) )+ а а(Н(), ° ° °

Полученные разности являются коэффи(Н(О) - i НЙ)-2 циентами при переменных z,z о

Н(О . ° ., z, z полинома X(z) mod (z +1) а суммы (их число равно N/4) используются на следующем этапе и т.д.

Таким образом, на каждом этапе образуются суммы и разности чисел, взятых попарно в определенном порядке, причем на первом этапе число с.уммирований и вычитаний равно N/2, а. затем уменьшается в два раза от этапа к этапу. Общее число этапов log„N =

1TI z

1оя 2 = m, Устройство работает следующим образом.

Перед началом вычислений производится сброс в начальное состояние счетчиков 1-3 и регистров 5-7. Затем на вход 31 поступает код, соответствующий численно половине входного массива, т.е. N/2, и записывается в регистр z сдвига. После этого происходит обработка входного мас.сива (х ) . Входные слова х поступают параллельными кодами на вход 33. Так как счетчик 2 находится в нулевом состоянии, на управляющий вход демультиплексора 12 через элемент

ИЛИ 21 поступает нулевой сигнал, который коммутирует информационный вход на первый вход первого мультиглексора 13, на управляющем входе которого нулевой потенциал, коммутирующий на выход первый вход этогс мультиплексора. Таким образом входные слова х; поступают на информационный вход первого блока 15 памяти. На адресные входы блоков 15 и 16 памяти информация поступает с выхсда регистра 4, а на не.о — с выхсда счетчика 1, имеющего длину ра=-рядной сетки log (N/2). С целью устранения гонок запись в блоки 15 и 16 памяти синхронизируется по входу 32. Информация, которая запи ывается вс второй блок 16.памяти, безразлична на первых N/2 тактах. В этот период происходит накопление первой полсвины отсчетов в первом блоке 15 памяти, По заднему фронту ((1)/2) — 1) -го синхроимпульса счетчик 1 сбрасывается в нулевое состояние, а счетчик

2 переходит в состояние, равное еди1357948 нице. Единичный сигнал с младшего разряда счетчика 2, пройдя через элемент ИЛИ 21, переключает демультиплексор 12, первый мультиплексор 13, а также разрешает принимать данные в

5 регистры 5 и 6 и считать счетчику 3.

Сигнал с выхода младшего разряда счетчика 2 подключает выход второго мультиплексора 14 к его первому входу. Входные отсчеты х;, начиная с (N/2)-го, через демультиплексор 12 и второй мультиплексор 14 поступают на регистр 6. Одновременно на регистр

5 поступает слово из блока 15 памяти, 1 записанное по нулевому адресу. С выходов регистров 15 и 16 информация поступает на сумматор 17 и вычитатель

29. Таким образом на (N/2)-м также происходит одновременное вычисление а, = хо хн т и айаг= х, — хи(° Разность а„ = х †.х„, поступает на выход о

34 устройства через группу 19 элементов ИЛИ. Сумма а, = х, + х, поступает на первые входы групп 8 и 10 эле- 2б ментов И. На инверсном выходе триггера 28 единичный потенциал, который открывает группу 8 элементов И и закрывает группу 10 элементов И. Таким образом N/4 сумм х, + х <„, ),; (i

= О, 1,. ° .,(N/4) — 1) записывается в блок 15 памяти по адресам О, 1, (N/4) ; 1 (старые данные х,, х,,..., х,1, более не требуются).

Начиная с второй итерации работает счетчик 3. При достижении им значе35 ния N/4 на выходе элемента 27 сравнения появляется единичный сигнал, который перебрасывает триггер 28 в единичное состояние, в результате чего суммы с выхода сумматора 17 постулают, начиная с (N/4)-й, на блок 16 памяти.

По заднему фронту (N — 1)-го тактирующего импульса счетчик 1 сбрасы- 4> вается в нулевое состояние, Счетчик

3 единичным сигналом с выхода элемента 27 сравнения сбрасывается в нуль.

При достижении счетчиком 3 значения, равного N/4, триггер 28 сбрасывается в нуль. Счетчик 2 переходит в состояние, равное двум, тем самым открывая группу 11 элементов И и сохраняя состояние мультиплексора 13 прежним. При этом мультиплексор 14 переключается нулевым сигналом с выхода младшего разряда счетчика 2.

Когда счетчик 2 переходит в состояние, равное двум, единичный сигнал с его старшего разряда открывает группу 11 элементов И и содержимое регистра 7 проходит на элемент 26 сравнения. Поэтому на второй итерации при достижении содержимым первого счетчика 1 значения N/4 на выходе элемента 26 сравнения появляется единичный сигнал, сбрасывающий первый счетчик 1 в нулевое состояние и сдвигающий содержимое регистра 7 на один разряд в сторону младших разрядов, т.е. его значение становится равным N/8. Далее процесс повторяется до m-й итерации (m = 1о8 N), где вычисляются последние суммы и разность на сумматоре 17 и вычитателе

29. Единичный сигнал с младшего разряда регистра 7 открывает группу 9 элементов И и последняя сумма поступает на выход 34 устройства, Таким образом, на первом этапе получается остаток X(z) по модулю

Н(2 N IQ

z + 1, на втором — по модулю z + 1, на последнем m ì этапе получают два остатка X(z) mod (z+1) и

X(z) mod (z-1). формула и з обретения

Устройство для приведения полиномов по модулям циклотомических полиномов, содержащее три регистра, три счетчика, три элемента ИЛИ, три группы элементов И, элемент задержки, первый элемент сравнения, сумматор, группу элементов ИЛИ, элемент НЕ и триггер, прямой выход которого соединен с первым входом первой группы элементов И, вход начальных данных устройства соединен с информационным входом первого регистра, выход которого соединен с первым входом первого элемента сравнения, выход которого соединен со счетным входом триггера, вход сброса устройства соединен с входами сброса первого, второго и третьего регистров и первыми входами

1 первого и второго элементов ИЛИ вы9

1 ход второго элемента ИЛИ соединен с входом сброса первого счетчика, выход которого соединен с вторым входом первого элемента сравнения, выход младшего и старшего разрядов второго счетчика соединен с первым и вторым входами третьего элемента

ИЛИ, выход которого соединен с входами разрешения записи второго и третьего регистров, о т л и ч а ю1357948 щ е е с я тем, что, с целью сокращения аппаратурных затрат., оно содержит четвертый регистр, четвертый элемент ИЛИ, четвертую группу элементов

И, второй элемент сравнения, вычитатель, группу элементов .задержки, два блока памяти, два мультиплексора и демультиплексор, информационный вход которого является информационным входом устройства, вход синхро- 10 низации которого соединен с входами синхронизации первого и третьего счетчиков, второго, третьего и четвертого регистров и через элемент HE с входами разрешения записи первого 15 и второго блоков памяти, адресные входы которых соединены с выходом четвертого регистра, информационный вход которого соединен с первым входом второго элемента сравнения и вы- 20 ходом первого счетчика, выход переноса которого соединен со счетным входом второго счетчика, выход старшего разряда которого соединен с первыми входами элементов И второй груп- 25 пы, выход которой соединен с вторым входом второго элемента сравнения, выход которого соединен с первым входом четвертого элемента ИЛИ и через элемент задержки с входом управления ЗО сдвигом первого регистра, выход старшегб разряда которого соединен с вторым входом первого элемента ИЛИ, выход которого соединен с входом сброса второго счетчика, выход младшего разряда первого регистра соединен с первыми входами элементов И третьей группы, выходы которых соединены с входами соответственно элементов задержки группы, выходы кото- 40 рых соединены с первыми входами эле,ментов ИЛИ группы, выходы которых образуют информационный выход устройства, вход сброса которого соединен с вторым входом четвертого элемента ИЛИ, выход которого соединен с входом сброса третьего счетчика, первый выход демультиплексора соединен с первым информационным входом первого мультиплексора, выход которого соединен с информационным входом. первого блока памяти, выход которого соединен с информационным входом .второго регистра, выход которого соединен с входами уменьшаемого и первого слагаемого вычитателя и сумматора соответственно, выход сумматора соединен с первыми входами элементов И четвертой группы и вторыми входами элементов И первой и третьей групп, выходы элементов И первой группы соединены с информационными входами второго блока памяти, выход которого соединен с первым информационным входом второго мультиплексора, выход которого соединен с информационным входом третьего регистра, выход которого соединен с вхоцами вычитаемого и второго слагаемого вычитателя и сумматора соответственно, выходы вычитателя соединены с вторыми входами элементов ИЛИ группы, инверсный выход триггера соединен с вторыми входами элементов И четвертой группы, выходы которых соединены с вторыми информационными входами первого мультиплексора, управляющий вход которого соединен с выхоцом третьего элемента ИЛИ, входом разрешения счета первого счетчика и управляющим входом демультиплексора, второй выход которого соединен с информационным входом второго мультиплексора., управляющий вход которого соединен с выходом младшего разряда второго счетчика.!

357948