Устройство для приведения полиномов по модулям циклотомических полиномов Советский патент 1987 года по МПК G06F7/544 

Изобретение относится к вычислительной технике и предназначено для использования в системах цифровой обработки сигналов.

Цель изобретения - сокращение ап- 5 паратурных затрат.

. На фиг. 1 представлена функциональная схема устройства; на.фиг. 2 - циклограмма его работы.

Устройство содержит счетчики 1-3, регистр 4-7, группы 8-11 элементов И, демультиплексор 12, мультиплексоры 13 и 14, блоки 15 и 16 памяти, сумматор 17, группу 18 элементов за1357948 2

ченные на первом этапе ( их число N/2), используются для аналогичной процедуры на втором этапе: а, а

W о

m-{N/)

INlt)

N + i 1 (H/4Ul

0 «/-b N(N;I)+I Полученные разности являются коэф(Ьи(HM1-I iNM)-i циентами при переменных z ,z ,

.,., z , z° полинома X(z) mod (z +1)

5

m.

Устройство работ.ает следующим обдится сброс в начальное состояние счетчиков 1-3 и регистров 5-7. Затем на вход 31 поступает код, соответствующий численно половине входного массива, т.е. N/2, и записывается в регистр z сдвига. После этого происходит обработка входного массива fx; (. Входные слова поступают пава х- являются коэффициентами поли т / N-1 нома X(.z; х z +,

+ X,

а суммы (их число равно N/4) используются на следующем этапе и т.д. Таким образом, на каждом этапе образуются суммы и разности чисел, взятых попарно в определенном порядке, причем на первом этапе число суммиродержки, группу 19 элементов ИЛИ,эле- 5 ваний и вычитаний равно N/2, г. затем менты ИЛИ 2П-23, элемент НЕ 24, эле- уменьшается в два раза от этапа к мент 25 задержки, элементы 26 и 27 этапу. Общее число этапов log,,N сравнения, триггер 28, -вычитатель 29, входы 30-33 сброса, начальных данных, синхронизации и информацион- 20 разом. . ный и выход 34 устройства.Перед началом вычислений произвоПриведение по модулям, неприводимых полиномов является первым этапом при реализации алгоритма свертки (или корреляции) на основе полино- (миальных преобразований. С этой целью входная последовательность fx;, где i О, 1,...,N-1, должна быть представлена в виде полинома степени

N-1 переменной z, причем входные ело- 30 раллельными кодами на вход 33. Так

как счетчик 2 находится в нулевом состоянии, на управляющий вход де- мультиплексора 12 через элемент ИЛИ 21 поступает нулевой сигнал, ко- 35 торый коммутирует информационный вход на первый вход первого мультиплексора 13, на управляющем входе которого нулевой потенциал, коммутирующий на выход первый вход этого муль- 40 типлексора. Таким образом входные слова х поступают на информационный вход первого блока 15 памя:ти. На адресные входы блоков 15 и 16 памяти информация поступает с выхода 45 регистра 4, а на не:го - с выхода

счетчика 1, имеющего длину разрядной сетки, log,2(N/2) . С целью устранения гонок запись в блоки 15 и 16 памяти синхронизируется по входу 32. Инфор- 50 мация, которая записывается вс второй блок 16,памяти, безразлична на первых N/2 тактах. 3 этот перкод происходит накопление первой половины отсчетов в первом блоке 15 памяти.

По заднему фронту (N/2) - синхроимпульса счетчик 1 сбрасывается в нулевое состояние, а счетчик 2 переходит в состояние, равное едиАналогично представляется передаточная функция H(z) + ...+ + h,z + hp. Выходной полином Y(z) вычисляется как произведение X(z) и H(Z) по модулю некоторого полинома P(z): Y(z) X(z) H(z) mod P(z) ...+ y, z + Уд. Восстановление полинома Y(Z) по китайской теореме об остатках для полиномов приводит к получе.нию выходной последовательности у-Я где О, 1, ..., N-1.

Устройство реализует следующий метод вычисления остатков полинома по модулям неприводимых полиномов z-1,z+1,z2+1,,.., 1 . На первом этапе вычисляются суммы и разности входных данных массива

W:

Я-

0 + Хц,2 ,

а,, X,

+ х

lN|i) (N(2)- N(2)- bJ-i

N(Z

(z

(N(2)41 X, - X

a

Л) /2 +1 } f

Разности на . (/г)- N-1

дующих этапах не используются и являются коэффициентами при перемен- ных,г(, ...,z , z° полино- ма X(z) mod ( 1). Суммы, полу55

ченные на первом этапе ( их число N/2), используются для аналогичной процедуры на втором этапе: а, а

W о

m-{N/)

INlt)

N + i 1 (H/4Ul

0 «/-b N(N;I)+I Полученные разности являются коэф(Ьи(HM1-I iNM)-i циентами при переменных z ,z ,

.,., z , z° полинома X(z) mod (z +1)

m.

Устройство работ.ает следующим обваний и вычитаний равно N/2, г. затем уменьшается в два раза от этапа к этапу. Общее число этапов log,,N разом. . Перед началом вычислений произво 5

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

нице. Единичный сигнал с младшего разряда счетчика 2, пройдя через элемент ИЛИ 21, переключает демультиплек- сор 12, первый мультиплексор 13, а также разрешает принимать данные в регистры 5 и 6 и считать счетчику 3. Сигнал с выхода младшего разряда счетчика 2 подключает выход второго мультиплексора 14 к его первому входу. Входные отсчеты Х; , начиная с (N/2)-ro, через демультиплексор 12 и второй мультиплексор 14 поступают на регистр 6, Одновременно на регистр 5 поступает слово из блока 15 памяти, записанное по нулевому адресу. С выходов регистров 15 и 16 информация поступает на сумматор 17 и вычитатель 29. Таким образом на (N/2)-M также происходит одновременное вычисление

X,

о ность

Хн1г и

к/г

х„ - X

N(2Раз н/г х и поступает на выхо

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

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

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

- , ь

Ш

15

20

30

35

40

25

т

45

50

55

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

Таким образом, на первом этапе получается остаток X(z) по модулю

N(2N/4

Z + 1, на втором - по модулю z + 1, ..., на последнем т-м этапе получают два остатка XOz) mod (z+1) и X(z) raod (z-1),

Формула изобретения

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

тем.

5

что,

1357948

с целью сокрароне ме с

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

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

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

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

10 .соединен с информационным входом

второго регистра, выход которого с динен с входами уменьшаемого и пер вого слагаемого вычитателя и сумма тора соответственно, выход суммато

f5 pa соединен с первыми входами элементов И четвертой группы и вторым входами элементов И первой и треть групп, выходы элементов И первой группы соединены с информационными

20 входами второго блока памяти, выхо которого соединен с первьм информа ционным входом второго мультиплекс ра, выход которого соединен с инфо мационным входом третьего регистра

выми входами элементов И второй груп- выход которого соединен с входами

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

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

.соединен с информационным входом

второго регистра, выход которого соединен с входами уменьшаемого и первого слагаемого вычитателя и сумматора соответственно, выход сумматоpa соединен с первыми входами элементов И четвертой группы и вторыми входами элементов И первой и третьей групп, выходы элементов И первой группы соединены с информационными

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

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

Изобретение относится к вычислительной технике и предназначено 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