Устройство для вычисления преобразования фурье-галуа

 

Изобретение относится к вычислительной технике и технической кибернетике. Цель изобретения - повышение быстродействия. Цель достигается тем, что в устройство вводится р блоков злементов ИПИ, устройство управления, включающее сдвигающий регистр (распределитель ), RS-триггер, схему И и р элементов ИЛИ. На первые входы блоков элементов ИЛИ подаются входные данные . Вторые входы блоков элементов ИЛИ соединены с выходами регистров первой группы, выходы блоков элементов ИЛИ соединены с входами регистров второй группы с выходов которых данные через умножители на коэффициент, выходы которых соединены с входами регистров первой группы , поступают на сумматор по модулю М, выход которого является выходом устройства. Устройство управления обеспечивает перезапись данных в регистры второй группы с выходов умножителей на коэффициент через регистры первой группы. После начального ввода данных вычисляется последний коэффициент преобразования , а затем за счет парал-г лельных обратных связей с выходов умножителей на коэффициент на входы регистров первой группы и все последующие. 1 ил. (Л

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

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

РЕСПУБЛИК

Ggg G 06 F 15/332

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

К ABTOPCKOMY СВИДЕТЕЛЬСТВУ

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

00 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТЗФ (21 ) 3806328/24-24 (22) 20.09.84 (46) 15.03.86. Бюл. 9 10 (71) Физико-механический институт им. Г.В.Карпенко (72) Л.11.Вариченко, M.À.Раков и Г.С.Сварчевский (53) 681.32(088.8) (56) Маккеллан Дж.Х. Аппаратурная реализация преобразования Ферма.—

В кн.: Маккеллан Дж.Х., Рейдер Ч.М.

Применение теории числа в цифровой обработке сигналов. M. Радио и связь, !983, с. 186-202.

Патент Франции Р 2384303, кл. G 06 F 15/332, 1980. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПРЕОБРАЗОВАНИЯ ФУРЬЕ-ГАЛУА (57) Изобретение относится к вычислительной технике и технической кибернетике. Цель изобретения повышение быстродействия. Цель достигается тем, что в устройство вводится р блоков элементов ИЛИ, устройство управления, включающее,.SU„„1218396 А сдвигающий регистр (распределитель), RS-триггер, схему И и р элементов ИЛИ. На первые входы блоков элементов ИЛИ подаются входные данные. Вторые входы блоков элементов

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

1 12!8

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

Цель изобретения — повышение быстродействия устройства.

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

Функциональная схема устройства, для вычисления преобразования ФурьеГалуа содержит р регистров 1 (промежуточного хранения данных), р,блоков элементов ИЛИ 2, регистров 3 (хранения данных); р умножителей 4 на коэффициент,сумматор 5 по модулю М (М=2 р — разрядность чисел), синхронизатор 6, состоящий из сдвигового регистра 7, р элементов ИЛИ 8, RS-триггера 9 и элемента И 10, информационный 11 и тактовый входы 12. Да— лее с приходом 2-го отсчета регистр

7 переключается в состояние, когда уровень логической "1" появляется на втором выходе, т.е. на выходе второй ячейки регистра 7, и второй отсчет входных данных анало30 гично первому записывается во ВТо рой регистр 3. Точно так же записываются остальные отсчеты входных данных. Последний P -й отсчет записывается в Р— и регистр 3. С вы— ходов р регистров отсчеты входных даннйх поступают на P умножителей

4. Первый блок 4 производит умножение

Р-1 на 2, второй блок 4 — на 2, третий блок 4 — 2 . ..., р-й блок 4 производит умножение на 2 . Поскольку при преобразовании Фурье-Галуа вычисления производятся по модулю целого числа, в данном случае по модулю числа M = 2, где простое число, то умножения на коэффициент представляют собой циклические сдвиги кодового слова. Реализовать умножение на коэффициент е-1 по модулю M = 2 можно простой коммутацией проводов, С вь!ходов р блоков 4 значения отсчетов х(б),..., х(р-l), умноженные соответственно о р-1 1 на 2, 2,..., 2-, поступают на

P регистров 1 соответственно, где запоминаются. Кроме того, данные с 55 выходов P блоков 4 поступают на входы сумматора 5 P -разрядных чисел

Р-1 по модулю M = 2 . В результате

196 2 суммирования получаем спектральный коэффициент (P -I). Сумматор 5 P. -раз

Р-1 рядных чисел по модулю М = 2 состоит из обычного ° сумматора р-разрядных чисел и р-разрядного сумматора, служащего для коррекции результата суммирования по модулю

М. Разряды, вышедшие за пределы р-разрядной сетки, суммируются с младшими. Возможный перенос Р в (р+1) -й разряд суммируется с младшими разрядами. С выходов Р регистров 1 данные через P блоков 2 поступают и запоминаются в р регистрах 3 и снова умножаются на коэффициенты последней строки матрицы преобразования. В результате суммирования умноженных вторично отсчетов входных данных получаем значение спектрального коэффициента Б(Р-2).

Такой процесс повторяется Р раз, пока не получится спектральный коэффициент S(O).

Управление этим процессом осуществляетая следующим образом.

Регистр 7 переключается в положение Р +1 (при записи последнего отсчета входных данных регистр 7 находится в состоянии, когда напряжение логической "1" присутствует на выходе р — положение р ). Импульс с выхода (р+1)-го регистра 7 устанавливает RS- триггер в положе— ние Q=l. Сигнал Q=l открывает прохождение тактовой частоты через элемент И 10. Импульс с выхода этого элемента поступает на тактовые входы а регистров 1. Тот же импульс с выхода элемента И 10 поступает на входы элементов ИЛИ 8, с выходов которых он уже в качестве Р импульсов поступает на тактовые входы Р регистров 3. С появлением сигнала логической "!" на выходе 2 Р регистра 7 RS-триггер устанавливается в состояние Я=О, закрывая элемент И 10, но за счет задержки включения RS-триггера импульс тактовой частоты успевает пройти на тактовые входы р регистров и 3, и в результате вычисляется коэффициент

S(0). С приходом следующего импульса тактовой частоты регистр 7 устанавливается в нулевое положение и тем самым схема готова к приему следующих отсчетов входных данных.

121ЯЗ 6

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

Устройство для вычисления преобразования Фурье-Галуа, содержащее первую и вторую группы регистров по р регистров, причем выход i-го (i=(, р) регистра второй группы подключен к входу i-ro умножителя на коэффициент, выход которого подключен к i-му входу сумматора по модулю М (М = 2, выход которого является информационным выходом устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены Р блоков элементов ИЛИ, RS-триггер, элемент

И, р элементов ИЛИ и сдвиговый регистр, выход х-го разряда которого подключен к первому входу i-го элемента ИЛИ, выход которого подключен к тактовому входу i-го регистра второй группы, информационный вход х которого подключен к выходу 3-го блока элементов ИЛИ, первый вход которого подключен к выходу i-ro регистра первой группы, информационный вход которого подключен к выходу i-ro умножителя на коэффициент, выход (р+1)-го разряда сдвигового регистра подключен к S-входу RS-триг гера, выход которого подключен к

10 первому входу элемента И, выход которого подключен к второму входу

i-ro элемента ИПИ и тактовому входу

i-ro регистра первой группы, вторые входы блоков элементов ИЛИ являются

15 информационными входами устройства, тактовым входом устройства являет(ся тактовый вход сдвигового регистра, соединенный с вторым входом элемента И, а выход (2р-1) -гс

20 разряда сдвигового регистра подключен к R — входу RS — триггера.

12! 8396

BHHHIIH Заказ 1133/57 Тираж 673 Подписное филиал ППП "Патент", г.Ужгород, ул.Проектная, 4