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

 

Изобретение относится к вычислительной технике и технической кибернетике и может быть использовано в цифровых вычислительных системах, предназначенных для обработки сигналов , в частности для обработки изображений. Цель изобретения - повышение быстродействия. Поставленная цель достигается за счет того, что -в состав устройства входят две группы из Р (Р - размер преобразования) регистров 1, 2, Р коммутаторов 3, Р умножителей 4 на коэффициент, сумматор 5, RS-триггер 6, элемент ИЛИ 7 и сдвиговый регистр 8. 1 ил.

союз соВетских соцщлистичесних

РЕСПУБЛИК

„„SU„„1645966 (51i5 G 06 F 15/332

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

Il0 ИЗОБРЕТЕНИЯМ И OTHPHTHAM

ПРИ ГКНТ СССР

ОПИСйНИЕ ИЗОБРЕТЕНИЯ "..

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

1 (21) 4678678/24 (22) 14.04,89 (46) 30.04.91. Бюл. F 16 (71) Научно-исследовательский институт бытовой радиоэлектронной аппаратуры (72) Л„В. Вариченко, Г,А. Дробенко и B.È. Кодров (53) 681.32(088.8) (5e) Патент Франции Р- 2384303, кл. Г 06 F 15/332, 1980.

Авторское свидетельство СССР

1218396, кл. С 06 F 15/332, 1984. (54) УСТРОЙСТВО ДЛЯ ВЬР ИСЛЕНИЯ ПРЕОБРАЗОВАНИЯ ФУРЬЕ-ГАЛУА

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

Пель изобретения - увеличение быстродействия за счет совмещения циклов записи и обработки входных данных.

На чертеже представлена Функциональная схема устройства для вычисления преобразования Фурье-Галуа. устройство содержит первую группу иэ P регистров 1, вторую группу из Р регистров 2, Р коммутаторов 3, P умножителей 4 на коэЫ ициент сумР матор 5 по модулю 1! (М = 2 -1, где

P — разрядность чисел), RS-триггер б, элемент ИЛИ 7, сдвиговый регистр

2 (57) Изобретение относится к вычислительной технике и технической кибернетике и может быть использовано в цифровых вычислительных системах, предназначенных для обработки сигналов, в частности для обработки изображений. Цель изобретения — повьг шение быстродействия. Поставленная цель достигается за счет того, что

-в состав устройства входят две группы из P (P - размер преобразования) регистров 1, 2, P коммутаторов 3, P умножителей 4 на коэффициент, сумматор 5, RS-триггер 6, элемент ИЛИ 7 н сдвнговый регистр 8. 1 ил.

8, установочный вход 9, тактовый вход 10, индюрмационный вход 11 и информационный выход

Устройство работает следующим об разом.

Импульсом на входе 9 обнуляются все регистры 1, 2 и 8 устройства и включается RS-триггер 6 (Я1), устанавливая уровень "1" на информационном входе сдвигового регистра 8 и сое диняя первые информационные входы P коммутаторов. 3 с их вькодами.

Первый тактовый импульс, поступающий на тактовый вход 10 устройства, приводит к появлению уровня "1" на первом выходе сдвигового регистра 8, который выключает RS-триггер 6 (Q=Q), устанавливает уровень "0" на информационном входе сдвигового регистра 8, соединяет вторые информацис нные входы Р коммутаторов 3 с их выходами и

1645966 записывает первый отсчет входной последовательности в первый регистр первой группы регистров 1. Второй тактовый импульс приводит к сдвигу

" 1" на второй выход сдвигового регистра 8 и записи второго отсчета входной последоватсльности во второй регистр первой группы регистров 1 и т.д. P-й тактовый импульс сдвигает

"1" на P-й выход сдвигового регистра

8, что приводит к записи P-ro отсчета входной последовательности в P-й регистр первой группы регистров 1, включению RS-триггера 6, появлению уровня "1" на информационном входе сдвигового регистра 8 и соединению первых информационных входов P коммутаторов 3 с их выходами. С выходов первой группы регистров 1 отсчеты входной последовательности поступают через P коммутаторов 3 íà P умножителей 4. Первьпi умножитель 4 производит умножение на 2, второй — на 2 -( третий — на 2 и т.д,, P-f. Умножи- 25

1 тель производит умножение на 2

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

4 значения отсчетов Х(О),...,Х(Р-1), о умноженные соответственно на 2

2,...,2, поступают на информационр-< ные входы второй группы регистров 2 соответственно и на входы сумматора

5 P-разрядных чисел по модулю Y=

Р

2 -1. Сумматор 5 P-разрядных чисел по модулю M=2 -1 состоит из обычного сумматора Р-разрядных чисел и Pразрядного сумматора, служащего для коррекции результата суммирования по модулю У<, В результате суммирования получаем спектральный коэффициент

S(P-1). Следующий (Р-1)-й или снова первый тактовый импульс приводит к появлению уровня " 1" на первом выходе сдвигового регистра 8, включению RSтриггера 6, соединению вторых инфор" мационных входов коммутаторов 3 с их выходами, записи первого отсчета но55 вой входной последовательности в первьо1 регистр первой группы регистров 1 и записи результатов умножения предыдущего такта во вторую группу регистров 2. С выходов второй группы регистров 2 через коммутаторы 3 результаты первого умножения снова поступают на Р умножителей 4 на коэффициент, с выходов которых результаты второго умножения поступают на информационные входы второй группы регистров 2 и на информационные входы сумматора 5 по модулю И=2 -1. В резульР тате суммирования получается спектральный коэффициент S(P-2).

Следующий (Р+2)-й или второй, тактовый импульс приводит к записи второго отсчета новой входной последовательности во второй регистр первой группы регистров 1 и вычислению слеэующего спектрального коэффициента

Б(Р-З).

Во время следующих тактов происходит запись остальных отсчетов новой последовательности в остальные регистры первой группы регистров 1 и вычисления следующих спектральных коэффициентов S(P-4), S(P-5) и т.д. аналогично описанному. (P-1)-й или (2P. — 1)-й тактовый импульс приводит к записи предпоследнего отсчета новой последовательности в (P-t)-й регистр первой группы регистров 1 и вычислению последнего спектрального коэффициента S(O).

P-й или 2Р-й тактовый импульс приведет к включению RS-триггера 6, уровню лог„ " 1" на информационном входе сдвигового регистра 6, соединению первых информационных входов коммутаторов 3 с их выходами, записи результатов последнего умножения во вторую группу регистров 2 и последнего отсчета новой последовательности в

Р-й регистр первой группы регистров 1.

С выходов первой группы регистров 1 данные через коммутаторы 3 поступают на умножители 4 на коэффициент, затем на информационные входы второй группы регистров 2 и на сумматор 5 по модулю N=-2 -1, где происходит вычисР ление первого спектрального коэффициента $(Р-1) новой последовательности.

В дальнейшем работа устройства происходит аналогично.

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

Устройство для вычисления преобразования Фурье-Галуа, содержащее

Составитель А. Гаранов

Техред Л°, Qлийнык Корректор Н.Король Редактор Л. Рчолинская

Заказ 1351 Тираж 415 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 101

164596 первую и вторую группы иэ P (P — размер преобразования} регистров, сумматор, P умножителей на коэффициент, RS-триггер и сдвиговый регистр при5 чем вьмод i-го (i=1, P) умножителя на коэффициент подключен к i-му входу сумматора, выход которого является информационным выходом устройства, установочным входом которого являются соединенные между собой установочные входы регистров первой и второй групп и установочный вход сдвигового регистра, тактовый вход которого является тактовым входом устройства, о т л и ч а ю щ е е с я тем, что, с целью повыпения быстродействия, в него введены P коммутаторов и элемент

ИН4, выход которого подключен к Sвходу RS-триггера, выход которого под- 20 ключен к управляющим входам всех коммутаторов и информационному входу сдвигового регистра, выход первого

6

H P-го разрядов которого подключены соответственно к Р;оду ГЯ-триггера и первому входу элемента ИЛ4, второй вход которого подключен к установочному входу устройства, информациокным входом которого являются соелиненные между собой информационные входы регистров первой группы, выход

i-го регистра которой подключен к первому информационному входу i«ro коммутатора, выход которого подключен к входу i-го умножителя на коэффициент, выход которого подключен к информационному входу i-ro регистра второй группы, вьмод которого подключен к второму информационному входу

1-го коммутатора, вьмод ъ-го разряда сдвигового регистра подключен к тактовому входу i-го регистра первой группы, а тактовые входы всех регистров второй группы подключены к тактовому входу устройства.