Устройство для вычисления преобразования Фурье-Галуа Советский патент 1993 года по МПК G06F15/332 

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

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

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

На-шине 13 задания длины преобразр- вания вйётавляется код, соответствующий длине преобразования pi. что приводит к тому; что через первый мультиплексор 14 pi-выход сдвигового регистра 8 соединяется с первым входом двухвходовогр элемента ИЛИ 7, т.е. производится установка длины сдвигового регистра, соответствующей длине преобразования.

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

Сумматор 5 по модулю М работает следующим образом. При достижении сумматором 5 значения 2Р происходит перенос в младший разряд. Пбэтбму при различных pi необходимы переносы из 1-разрядов в младший, что и осуществляется вторым мультиплексором 15.

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

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

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

4 производит умножение на 2°, второй на 21, третий на 22 и т.п. Поскольку при преобразовании Фурье-Галуа вычисления производятся по модулю целого числа, в данном случае по модулю числа , где р - простое число, то умножения на коэффициент представляют собой циклические сдвиги кодового слова. Реализовать умножения на коэффициент можно простой коммутацией входов и выходов умножителей4. С выходов р умножителей 4 значения отсчетов х(0): (1j...x(pi-1), умноженные соответственно на 2 ,2 ...2Р поступают на информационные входы второй группы регистров 2 соответственно и на входы сумматора 5р-разрядиых чисел по модулю . Сумматор 5р-раз- рядных чисел по модулю состоит из обычного сумматора р-разрядных чисел и р-разрядного сумматора, служащего для коррекции результатов суммирования по модулю М. В результате суммирования получаем спектральный коэффициент 5(1). Следующий (р|+1)-й (или снова первый) тактовый импульс приводит к появлению уровня лог. 1 на первом выходе сдвигового регистра 8, включению RS триггера б, соединению вторых информационных входов коммутаторов 3 с их входами, записи первого отсчета новой входной последовательности в первый регистр первой группы регистров 1 и к записи результатов умножения предыдущего такта во вторую группу регистров 2. С выходов второй группы регистров 2 через коммутатор 3 результаты первого умножения снова поступают на р умножителей 4 на коэффициент, с выходов которых результаты второго умножения поступают на информационные входы второй группы регистров 2 и на информационные входы сумматора 5 по модулю . В результате суммирования получается спектральный коэффициент 5(2).

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

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

()-й (или 2р|+1)-й тактовый импульс приведет к записи предпоследнего отсчета новой последовательности в (р|-1)-й регистр первой группы регистров 1 и вычислению

последнего спектрального коэффициента 5(0).

PI-Й (или 2ргй) тактовый импульс приведет к включению RS-триггера б, уровню лог. 1 на информационном входе сдвигового регистра 8, соединению первых информационных входов коммутаторов 3 с их выходами, записи результатов последнего умножения во вторую группу регистров 2 и последнего отсчета новой последовательности в pi-й регистр первой группы регистров 1. С выхода первой группы регистров 1 данные через коммутаторы 3 поступают на умножители на коэффициент 4, затем на информационные входы второй группы регистров 2 и на сумматор 5 по модулю , где происходит вычисление первого спектрального коэффициента 5(1)новой последовательности.

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

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

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

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

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