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

(5 ИЕ ИЗОБРЕТЕНИЯ П 2 обработки изображений. Цель изобретения - расширение функциональных возможностей за счет обработки последовательностей разной длины (Р Рмзкс). Устройство содержит первую группу из р регистров 1, вторую группу из р регистров 2, группу иэ р коммутаторов 3, группу из р умножителей 4 на коэффициент, сумматор 5 по модулю М (М=2 Р, где р - длина преобразования), ЙЗ- триггер 6, двухвходовый элемент ИЛИ 7, сдвиговый регистр 8, вход 9 начальной установки, тактовый вход 10, информационный вход 11, информационный выход 12, шину 13 задания длины преобразования, первый мультиплексор 14 и второй мультиплексор 15. 1 ил. ГОСУДАРСТВЕННОЕ ПАТЕНТНВЕДОМСТВО СССР(71) Научно-исследовательский институт бы товой радиоэлектронной аппаратуры (72) Л,В, Вариченко и В.И, Кодров(56) Авторское свидетельство СССР )ч. 1645966, кл. 6 06 Г 15/332, 1989, (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПРЕОБРАЗОВАНИЯ ФУРЬЕ-ГАЛУА . (57) Изобретение относится к вычислитель ной технике и технической кибернетике и может быть использовано в цифровых вычислительных системах, предназначенных для обработки сигналов, в частности для 1789992 А 1Изобретение относится к вычислительной технике и технической кибернетике иможет бытьиспользовано в цифровых числительных системах; предназначенных дляобработки сигналов, в частности для обработки изображений,Цель изобретения - расширение функциональных воэможностей за счет обработки последовательностей разной длины"Устройство, представленное на чертеже, содержит первую группу иэ р регистров1, вторуюгруппу из р регистров 2, группу изр коммутаторов 3, группу из р умножителей4 на коэффициент, сумматор 5 по модулю М 15(М=2 Р, где р - длина преобразования), ВЯтриггер 6, двухвходовый элемент ИЛИ 7,сдвиговый регистр 8, вход 9 начальной установки, тактовый вход 10, информационныйвход"11, информационный выход 12,шину 2013 задания длины преобразования, первыймультиплексор 14 и второй мультиплексор15,Устройство работает следующим образом, Перед началом вычисления производится установка длины преобразования.На шине 13 задания длины преобразо- "вания" выставляется код, соответствующийдлине преобразования р, что йриводйт к"тому; что через первый мультиплексор 14 30р-выход сдвигового регистра 8 соединяетсяс первым входом двухвходового элементаИЛИ 7, т;е. производится установка длинысдвигового регистра, соответствующей длине преобразования, 35На шине 13 задания длины преобразования выставляется код, соответствующийдлина преобразования рь что приведет ктому, что через первый мультиплексор 14р-выход сдвигового регистра 8 производится установка длины сдвигового регистра 8,соответствующейдлине преобра 5 овэния,Сумматор 5 по модулю М работает следующим образом, При достижении сумматором 5 значения 2 Р происходит перенос в 45младший разряд. Поэтому при различных рьнеобходимы переносы из 1-разрядов в млад ший, что и осуществляется вторым мультиплексором 15,Импульсом на входе 9 обновляются все 50регистры (1, 2, 8) устройства и включаетсяВЯ-триггер 6 (0=1), устанавливая уровеньлог. "1" на информационном входе сдвигового регистра 8 и соединяя первые информационные входы р коммутаторов 3 с их 55выходами,Первый тактовый импульс, поступающий на тактовый вход 10 устройства, приводит к появлению уровня лог. "1" на первомвыходе сдвигового регистра 8, который выключает ВЯ-триггер 6 (0=0), устанавливает уровень лог. "0" на информационном входе р коммутаторов 3 с их выходами и записывает первый отсчет входной последовательности в первый регистр первой группы регистров 1, Второй тактовый импульс приводит к сдвигу лог, "1" на второй выход сдвигового регистра 8 и записи второго отсчета входной последовательности во второй регистр первой группы регистров 1, и т.п, р-й тактовый импульс сдвигает лог. "1" на р-й выход сдвигового регистра 8, что приводит к записи р-го отсчета входной последовательности в р-регистр первой группы регистров 1, включению. через первый мультиплексор 14 ВЯ триггера 6, появлениюуровня лог. "1" на информационном входе сдвигового регистра 8 и соединению первых информационных входов р коммутаторов 3 с их выходами. С выходов первой группы регистров 1 отсчеты входной последовательности поступают через р коммутаторов 3 на р умножителей 4, Первый умножитель 4 производит умножение на 2 О, второй на 2", третий на 2 и т.п, Поскольку при преобразовании Фурье-Галуа вычисления производятся по модулю целого числа, в данном случае по модулю числа М=2 Р, где р - простое число, то умножения на коэффициент представляют собой циклические сдвиги кодового слова. Реализовать умножения на коэффициент можно простой коммутацией входов и выходов умножителей,4. С выходов р умножителей 4 значения отсчетов хО): Щх(р - 1), умноженные соответственно на 2,2 ,2 Р поступают на информационные входы второй группы регистров 2 соответственно и на входы сумматора 5 р-разрядных чисел по модулю М=2 Р, Сумматор 5 р-разрядных чисел по модулю М=2 Рсостои из обычного сумматора р-разрядных чисел и р-разрядного сумматора, служащего для коррекции результатов суммирования по модулю М, В результате суммирования получаем спектральный коэффициент Я(1), Следующий (р+1)-й (или снова первый) тактовый импульс приводит к появлению уровня лог. "1" на первом выходе сдвигового регистра 8, включению ВЯ триггера 6, соединению вторых информационных входов коммутаторов 3 с их входами, записи первого отсчета новой входной последовательности в первый регистр первой группы регистров 1 и к записи результатов умножения предыдущего такта во вторую группу регистров 2. С выходов второй группы регистров 2 через коммутатор 3 результаты первого умножения снова поступают на р умножителей 4 на коэффициент, с выходов которых результаты второго умножения по1789992 25 ступают на информационные входы второй группы регистров 2 и на информационные входы сумматора 5 по модулю М=2 Р. В результате суммирования получается спектральный коэффициент Я(2),Следующий (р+2 или второй) тактовый импульс приводит к записи второго отсчета новой входной последовательности во второй регистр первой группы регистров 1 и вычислению следующего спектрального коэффициента Я(3).Во время следующих тактов происходит запись остальных отсчетов новой последовательности в остальные регистры первой группы регистров 1 и вычисление следующих спектральных коэффициентов Я(4), Я(5) и т,п. аналогично описанному.(р+1)-й (или 2 р+1)-й тактовый импульс приведет к записи предпоследнего отсчета новой последовательности в (р)-й регистр первой группы регистров 1 и вычислению Формула изобретения Устройство для вычисления преобразования Фурье-Галуа, содержащее первую и вторую группы из р (р-размер преобразования) регистров, сумматор по модулю М (М=2 Р), р умножителей на коэффициент, ВЯ-триггер и сдвиговый регистр, причем выход 1-го (1=1, р) умножителя на коэффициент подключен к 1-му входу сумматора по модулю М, выход которого является информационным выходом устройства, установочным входом которого являются соединенные между собой установочные входы регистров первой и второй групп и установочный вход сдвигового регистра, тактовый вход которого является тактовым входом устройства, р коммутаторов, элемент ИЛИ, выход которого подключен к Я-входу ВЯ-триггера, выход которого подключен к управляющим входам всех коммутаторов и информационному входу сдвигового регистра, выход первого разряда которого подключен к В-входу ЯЯ- триггера, первый вход элемента ИЛИ подключен к установочному входу устройства, информационным входом которого являются соединенные между собой информационные входы регистров первой группы, выход 5 10 15 20 последнего спектрального коэффициента ЯО).р-й (или 2 р-й) тактовый импульс приведет к включению ВЯ-триггера 6, уровню лог. "1" на информационном входе сдвигового регистра 8, соединению первых информационных входов коммутаторов 3 с их выходами, записи результатов последнего умножения во вторую группу регистров 2 и последнего отсчета новой последовательности в р-й регистр первой группы регистров 1, С выхода первой группы регистров 1 данные через коммутаторы 3 поступают наумножители на коэффициент 4, затем на информационные входы второй группы регистров 2 и на сумматор 5 по модулю М=2 Р, где происходит вычисление первого спектрального коэффициента Я(1)новой последовательности,В дальнейшем работа устройства происходит аналогично. 1-го регистра которой подключен к первому информационному входу 1-го сумматора, выход которого подключен к входу 1-го умножителя на коэффициент, выход которого подключен к информационному входу 1-го регистра второй группы, выход которого подключен к второму информационному входу 1-го коммутатора, выход 1-го разряда сдвигового регистра подключен к тактовому входу 1-го регистра первой группы, тактовые входы всех регистров второй группы подключеныы к тактовому входу устройства, о тл и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет обработки последовательностей разной длины (ррмэкс), в него введены два мультиплексора, причем вход задания длины преобразования устройства соединен с адресными входами обоих мультиплексоров, информационные входы первого мультиплексора соединены с соответствующими р-выходами сдвигового регистра, а выход - с вторым входом элемента ИЛИ, информа- ционные входы второго мультиплексора соединены с соответствующими р-мивыходами переноса р-х разрядов суммато.ра по модулю М, а выход - с входом переноса первого разряда сумматора по модулю М.