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

 

Изобретение относится к вычислительной технике и технической кибернетике и может быть использовано в цифровых вычислительных системах, предназначенных для обработки сигналов, в частности для обработки изображений. Цель изобретения - расширение функциональных возможностей за счет обработки последовательностей разной длины (Pi Рмакс). Устройство содержит первую группу из р регистров 1, вторую группу из р регистров 2, группу из р коммутаторов 3, группу из р умножителей 4 на коэффициент, сумматор 5 по модулю М (, где р - длина преобразования), RS- триггер 6, двухвходовый элемент ИЛИ 7, сдвиговый регистр 8, вход 9 начальной установки , тактовый вход 10, информационный вход 11, информационный выход 12, шину 13 задания длины преобразования, первый мультиплексор 14 и второй мультиплексор 15. 1 ил.

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

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

РЕСПУБЛИК (si)s G 06 F 15/332

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4860927/24 (22) 19,06.90 (46) 23.01.93. Бюл. № 3 (71) Научно-исследовательский институт бытовой радиоэлектронной аппаратуры (72) Л.В. Вариченко и В.И, Кодров (56) Авторское свидетельство СССР

¹ 1645966, кл. G 06 F 15/332, 1989. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

ПРЕОБРАЗОВАНИЯ ФУРЬЕ-ГАЛУА . (57) Изобретение относится к вычислительной технике и технической кибернетике и может быть использовано в цифровых вычислительных системах, предназначенных для обработки сигналов, в частности для. Ы 1789992 А1 обработки изображений. Цель изобретения — расширение функциональных возможностей за счет обработки последовательностей разной длины (Р < Рмзкс). Устройство содержит первую группу из р регистров 1, вторую группу из р регистров 2, группу иэ р коммутаторов 3, группу из р умножителей 4 на коэффициент, сумматор 5 по модулю М (M=2Р-1, где р — длина преобразования), RSтриггер 6, двухвходовый элемент ИЛИ 7, сдвиговый регистр 8, вход 9 начальной установки, тактовый вход 10, информационный вход 11, информационный выход 12, шину

13 задания длины преобразования, первый мультиплексор 14 и второй мультиплексор

15. 1 ил.

1789992

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

". Устройство, представленное на чертеже, содержит первую группу иэ р регистров

1, вторую группу иэ р регистров 2, группу из р коммутаторов 3, группу из р умножителей

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

13 задания длины преобразования, первый мультиплексор 14 и второй мультиплексор"

15.

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

На шине 13 задания длины преобразо- " вания" выставляется код, соответствующий длине преобразования pj, что йриводйт к" тому; что через первый мультиплексор 14 30

pj-выход сдвигового регистра 8 соединяется с первым входом двухвходового элемента

ИЛИ 7, т;е. производится установка длины сдвигового регистра, соответствующей длине преобразования. 35

На шине 13 задания длины преобразования выставляется код, соответствующий длина преобразования рь что приведет к тому, что через первый мультиплексор 14

pj-выход сдвигового регистра 8 производит- 40 ся установка длины сдвигового регистра 8, соответствующей длине преобразования, Сумматор 5 по модулю М работает следующим образом, При достижении сумматором 5 значения 2Р происходит перенос в 45 младший разряд. Поэтому при различных рь необходимы переносы из I-разрядов в млад ший, что и осуществляется вторым мультиплексором 15, Импульсом на входе 9 обновляются все 50 регистры (1, 2, 8) устройства и включается

RS-триггер 6 (0=1), устанавливая уровень лог. "1" на информационном входе сдвигового регистра 8 и соединяя первые информационные входы р коммутаторов 3 с их 55 выходами.

Первый тактовый импульс, поступающий на тактовый вход 10 устройства, приводит к появлению уровня лог. "1" на первом выходе сдвигового регистра 8, который выключает RS-триггер 6 (0=0), устанавливает уровень лог. "0" на информационном входе р коммутаторов 3 с их выходами и записывает первый отсчет входной последовательности в первый регистр первой группы регистров 1, Второй тактовый импульс приводит к сдвигу лог, "1" на второй выход сдвигового регистра 8 и записи второго отсчета входной последовательности во второй регистр первой группы регистров 1, и т.п. pj-й тактовый импульс сдвигает лог. "1" на pj-й выход сдвигового регистра 8, что приводит к записи pj-ro отсчета входной последовательности в pj-регистр первой группы регистров 1, включению: через первый мультиплексор 14 RS триггера 6, появлению уровня лог. "f" на информационном входе сдвигового регистра 8 и соединению первых информационных входов р коммутаторов 3 с их выходами. С выходов первой группы регистров 1 отсчеты входной последовательности поступают через р коммутаторов

3 на р умножителей 4, Первый умножитель

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

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

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

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

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

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

20 последнего спектрального коэффициента

s(o).

pi-й (или 2pi-й) тактовый импульс приведет к включению RS-триггера 6, уровню лог.

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

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

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

I-го регистра которой подключен к первому информационному входу i-го сумматора, выход которого подключен к входу i-го умножителя на коэффициент, выход которого подключен к информационному входу l-го регистра второй группы, выход которого подключен к второму информационному входу i-го коммутатора, выход I-го разряда сдвигового регистра подключен к тактовому входу 1-го регистра первой группы, тактовые входы всех регистров второй группы подключеныы к тактовому входу устройства, о тл и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет обработки последовательностей разной длины (pl pMBKc) в него введены два мультиплексора, причем вход задания длины преобразования устройства соединен с адресными входами обоих мультиплексоров, информационные входы первого мультиплексора соединены с соответствующими р -выходами сдвигового регистра, а выход— с вторым входом элемента ИЛИ, информа- ционные входы второго мультиплексора со единены с соответствующими pi-ми выходами переноса р -х разрядов суммато.ра по модулю М, а выход — с входом переноса первого разряда сумматора по модулю М.