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

союз советскихСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 8 06 Е 15/3 1)5 НИЕ ИЗОБРЕТЕНИОМУ СВИДЕТЕЛЬСТВУ Ой институт баратурыи А,И,Устрех 3,СССР 1986.ЫЧИСЛЕНИЯГАЛУА вычислительибернетике и ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИПРИ ГКНТ СССР(54) УСТРОЙСТВО ДЛЯ ВПРЕОБРАЗОВАНИЯ ФУРЬЕ(57) Изобретение относится кной технике и технической Изобретение относится к вычислительной технике и технической кибернетике и может быть использовано в цифровых вычислительных системах, предназначенныхдля обработки сигналов, в частности для обработки иэображений.Целью изобретения является расширение Функциональных воэможностей эа счет вычисления свертки.На фиг. представлена структурная схема устройства; на фиг.2 - временные диаграммы работы устройства в режиме вычисления ППФГ; на фиг.3 - временные диаграммы работы устройства в режиме вычисления свертки; на Фиг.4- структура размещения данных в регистрах устройства.На фиг,2 обозначены: а - тактовая последовательность; б - сигнал на выходе элемента задержки; в - импульс начальной установки; г - сигнал на управляющих входах первого и второго коммутаторов; д -может быть использовано в цифровых вычислительных системах, предназначенных для обработки сигналов, в частности для обработки иэображений. Цель изобретения - расширение Функциональных возможностей путем вычисления свертки. Устройство содержит пять элементов ИЛИ, два сдвиговых регистра, элемент задержки, ВЗ-триггер, два коммутатора,две группы регистров, три элемента И, два триггера, группу коммутаторов, группу умножителей на коэффициент, сумматор по модулю М, умно- житель, счетчик, группу элементов И, блок . постоянной памяти коэффициентов. умно- житель на коэффициент. 4 ил. сигнал на управляющих входах группы из Р коммутаторов; е - сигнал на инверсном выходе второго Т-триггера; ж - структура данных на входе устройства; 3 - структура сигналов на выходе сдвигового регистра; и - структура данных в первой группе из Р регистров; к - структура данных во второй группе из Р регистров; л - структура выходного сигнала.На фиг.3 обозначены: а - тактовая последовательность; б - сигнал на выходе элемента задержки; в - импульс начальной установки; г-сигнал на управляющем входе второго коммутатора; д- сигнал на управляющем входе первого коммутатора; е - сигналы на управляющих входах группы иэ Р коммутаторов; ж - структура данных на входе устройства; з - структура сигналов на выходе сдвигового регистра; и - структура данных в первой группе из Р регистров; к - структура данных во второй группе из Р регистров; л - структура данных на выходахР-разрядного сдвигового регистра; м - структура выходного сигнала.На фиг.4 обозначены; а - структура данных в регистрах первой группы на первом этапе вычислений (после прохождения Р тактовых импульсов); б - структура данных во второй группе из Р регистров после первого этапа вычислений (после прохождения Р тактовых импульсов); в - структура данных в первой группе из Р регистров после второго этапа чычисления (после прохождения 2 Р тактовых импульсов); г - структура данных в регистрах второй группы из Р регистров после второго этапа вычислений (после прохождения 2 Р тактовых импульсов); д - структура данных в Р-разрядном сдвиговом регистре.Устройство для вычисления преобразования Фурье-Галуа содержит информационный вход 1, установочный вход 2, тактовый вход 3, выход 4 выбора режима (трехвходовый), элемент ИЛИ 5, сдвиговыйрегистр 6, элемент 7 задержки, элемент ИЛИ 8, ВЯ-триггер 9, коммутатор 10, регистры 11.1,.,11,Р первой группы иэ Р регистров, элемент И 12, элемент И 13, элемент ИЛИ 14, регистры 15,115.Р второй группы из Р регистров, триггер 16, группу из Р коммутаторов 17,117.Р, первый триггер 18, группу из Р умножителей на коэффициенты 19 119,Р, сумма гор 20 по модулю М (М=2 -1), матричный умножитель 21 по моРдулю М(М=2 -1), коммутатор 22, Р-разрядный сдвиговый регистр 23, элемент И 24, счетчик 25, группу из Р трехвходовых элементов И 26, блок 27 постоянной памяти коэффициентов, Р-входовый элемент ИЛИ 28, умножитель 29 на коэффициент Р, элемент ИЛИ 30,информационный выход 31 устройства. 5 10 152025 30 35 40 45 50 55 Управление элементами устройства происходит следующим образом,Импульсом по входу 2 обнуляются сдвиговый регистр 6, первая группа из Р- регистров 11.111.Р, вторая группа из Р регистров 15.115,Р, Р-разрядный сдвиговый регистр 23, счетчик 25, триггеры 16 и 18 (лог. "О" - на прямом выходе, лог. "1" - на инверсном), и включается ВЯ-триггер 9 (лог. "1" - на выходе)Лог. "1" на управляющих входах коммутаторов 10 и 22 подключает входы коммутатора к выходам (в случае коммутатора 22 - информационные входы к первым выходам), а лог. "0" на управляющих входах группы из Р коммутаторов 17,117,Р подключает вторые входы коммутаторов к их выходам. Изменение управляющего сигнала приводит к перекоммутации входов. Лог, "0" с прямого вы 2.2 Е)2 о где х(р) - отсчеты входной последовательности;Х(р) - коэффициент ППФ ГВ режиме вычисления свертки устройство производит вычисления по формулеу(р) = х(р)Ь(р), (2)где у(р) - выходная последовательность;х(р) - входная последовательность;Ь(р) -последовательность, сворачиваемая с входной,следующим образом. Сначала вычисляетсяППФГ входной последовательности х(р), затем производится перемножение ППФГвходной Х(р) и сворачиваемой с входной Н(р)последовательностей, затем производитсяобратное преобразование Фурье-Галуа(ОПФГ) перемноженных коэффициентовХ(р) Н(р) и окончательно производится чмножение на нормирующий множитель Р ,представляющий собой обратный элементот Р, т.е. устройство работает в соответствии с формулойу(р) ОПФГ ППФГ(х) ППФГ(Ь)1 р . (3)Так как сворачиваемая с входной последовательность Ь(р) обычно неизменна впроцессе вычислений, то ее коэффициенты Н(р) могут быть вычислены до началавычисления свертки Н(р) в режиме вычисления ППФГ и записаны в блок 27.Устройство в режиме вычисления ППФГработает следующим образом,Импульс по входу 2 приводит устройство в исходное положение: регистры6,11.1,.,11.Р, 15.1.15.Р,23 счетчик 25 и хода триггера 16 блокирует группу из Р трехвходовых элементов И 26, Триггер 16 управляется срезом импульсов с выхода элемента ИЛИ 14, на вход которого поступают с выхода элемента И 12 совпадающие лог. "1" с Р-го выхода сдвигового регистра 6 и импульс с выхода элемента 9 задержки, а на другой вход с выхода элемента И 13 - совпадающие лог. "1" с Р-го выхода сдвигового регистра 6 и тактовый импульс с тактового входа 3. Р-разрядный сдвиговый регистр 23 тактируется тактовыми импульсами с тактового входа 3 устройства.Работа устройства, в зависимости от режима, заключается в следующем.В режиме вычисления ППФГ устройство производит вычисление в соответствии с выражением, соответствующим ППФГ.триггеры 16 и 18 обнуленц, ВЯ-триггер 9 включен, первые входы коммутатора 10 подключены к выходам, вторые входы группы из Р коммутаторов 17.117.Р подключены к выходам, информационные входы коммутатора 22 подключены к первым выходам. Отсчеты входной последовательности х(р) поступают с частотой, равной тактовой частоте на тактовом входе 3 устройства.Импульс с первого выхода сдвиговогорегистра 6 записывает первый отсчет х(0) входной последовательности х(р) в первый регистр 11,1 первой группы из Р регистров, импульс с второго выхода сдвигового регистра 6 - второй отсчет х(1) во второй регистр 11.2 и т.д., импульс с Р-го выхода сдвигового регистра 6 - (Р)-й отсчет х(Р) в Р-й регистр 11.Р. Р-м тактовым импульсом переключаются группа из Р коммутаторов 17.117.Р (первые входы подключаются к выходам) и коммутатор 11 (информационные входы подключаются к вторым выходам и входу элемента И 24), и данные с выходов первой группы из Р регистров 11.1 через коммутаторы 17.117.Р и умножители 19.119.Р поступают на О-входы второй группы из Р регистров 15 115,Р и на входы сумматора 20 по модулю, где суммируются по модулю М = =2 -1, вычисляя коэффициент Х(р), который с выхода сумматора 20 по модулю М через коммутатор 22, элемент И 24 и элемент ИЛИ 30 поступает на информационный выход 31 устройства.(Р+1)-й тактовый импульс приводит к появлению лог. "1" на первом выходе сдвигового регистра 6 и записи первого отсчета х(0) следующей входной последовательности в первый регистр 11,1 первой группы иэ Р регистров 11.1, . 11. Р, (Р)-й импульс выхода элемента 7 задержки приводит к записи в регистры второй группы из Р регистров 15,115,Р и появлению на информационных выходах 31 устройства третьего коэффициента Х(Р-З).В последующие (Р - 1) такта работа устройства происходит аналотично.(2 Р)-й импульс с выхода. элемента 7 задержки приводит к появлению на инфор-.мационном выходе 31 устройства последнего коэффициента Х(0) ППФ Г первой входной последовательности.2 Р-й тактовый импульс приводит к записи Р-го отсчета х(Р - 1) следующей входной последовательности и началу вычисления коэффициентов ППФГ, которое производится аналогично.Вычисление ППФГ может продолжаться в реальном времени, так как коммутатор 10 не переключается, заблокированный че ся первым триггером 18 (лог, "1" на прямом выходе). Данные с выходов первой группы из Р-регистров 11.111.Р через коммутаторы 17.117.Р и умножители 19,119,Р 15 на коэффициент поступают на О-входыгруппы из Р регистров 15 115.Р, Р-й импульс выхода элемента 7 задержки записывает во вторую группу из Р регистров 15.1, 15.Р данные с их О-входов и приво дит к переключению коммутаторов выходов умножителя 21 по модулю Н произведение Х(Р) Н(Р) через коммутатор 10 35 поступает на О-входы первой группы иэ Р 40 45 50 55 27 поступает значение коэффициента Н(Р-З), , С выхода умножителя 21 по модулю М про 510 25 30 рез трехвходовый элемент ИЛИ 5 лог. "1" с входа 4.В режиме вычисления свертки лог, "0" на входе 4 запись отсчетов входной последовательности х(Р) в первую группу из Р регистров 11.1,.,11;Р происходит аналогично начальной записи данных в режиме ППФГ, Р-й импульс выхода элемента И 13 не приводит к переключению коммутатора 10, так как он блокируется переключающим 17,117,Р и 10(вторые входы подключаются к выходам). С выходов второй группы из Р регистров 15,115.Р через коммутаторы 17,1,.,17.Р и умножители 19.119,Р на коэффициент данные поступают на О-входц второй группы из Р регистров 15.1,15.Р и на входы сумматора 20 по модулю М, где вычисляется коэффициент Х(Р), который через коммутатор 22 поступает на входы умножителя 21 по модулю М, на другие входы которого с нулевой ячейки блока 27 поступает значение коэффициента Н(Р). С регистров 11.111.Р, в первый (11.1) из которых оно записывается импульсом с первого выхода сдвигового регистра 6, который появляется после появления (Р+1)-го тактового импульса.(Р+1)-й импульс с выхода элемента 7 задержки записывает во вторую группу из Р регистров 15.1,. 15,Р данные с их О-входов и изменяет адрес ячеек блока 27.С выходов второй группы из регистров 15.115.Р данные через коммутаторы 17.117,Р и умножители 19.1,. 19.Р на коэффициент поступают на О-входы второй группы из Р регистров 15.115.Р и на входы сумматора 20 по модулю И, где вычисляется значение коэффициента Х(Р-З), который через коммутатор 22 поступает на входы умножителя 21 по модулю М, на другие входы которого с первой ячейки блока изведение Х(Р - 3) Н(Р - 3) через коммутатор 10 поступает на О-входы первой группы из Р регистров 11.111.Р, во второй (11.2) изкоторых оно записывается импульсом с второго выхода сдвигового регистра 6. Далее (Р) такта работа устройства происходит аналогично.2 Р-й тактовый импульс приводит к пере ключению коммутаторов 10,17.117.Р , (первые входы подключаются к выходам) ивторого коммутатора 22 (информационные входы подключаются к первым выходам).Данные с выходов первой группы из Р реги строе 11,"11. Р через коммутаторы 17,117.Р и умножители 19.119.Р поступают на О-входы второй группы из Р регистров 15.115.Р. 2 Р-й импульс выхода элемента 7 задержки записывает во вторую 15 группу из Р регистров 15.115,Р данные с их О-входов и переключает коммутаторы 17,117.Р (вторые входы подключаются к выходам).(2 Р+ 1)-й тактовый импульс приводит 20к записи отсчета х(0) следующей входной последовательности в первый (11 1) из первой группы Р регистров 11.1,.;.,11.Р и к записи в первый регистр Р-разрядного сдвигового регистра первого модифициро ванного отсчета у(0) выходной последовательности, которцй с выхода сумматора 20 по модулю М через коммутатор 22 поступает на входы Р-разрядного сдвигового регистра 23. 30(2 Р+1)-й импульс с выхода элемента 7задержки записывает во вторую группу их Р регистров данные с их О-входов.(2 Р+2)-й тактовый импульс приводит к 35записи во второй (11.2) регистр из первой группы из Р регистров второго отсчета х(1) следующей последовательности и к записи во второй регистр Р-разрядного сдвигового регистра 23 второго модифи цированного у(Р). Далее (Р) такта работа устройства происходит аналогично,(ЗР+ 1)-й тактовый импульс начинает цикл обработки следующей последова тел ьности, записывая в регистр 11.1 первой группы из Р регистров 11.1.11.Р новое произведение Х(Р) Н(Р), а также с Р-го разряда Р-разрядного сдвигового регистра 23 через группу из Р трехвходовых 50 элементов И 26,.Р-входовый элемент ИЛИ 28, умножитель 29 на коэффициент и элемент ИЛИ 30 выводит на информационный выход 31 устройства первый отсчет у(0) выходной последовательности. (ЗР+2)-й такто вый импульс выводит на информационный выход 31 устройства второй отсчет у(1) выходной последовательности и записцвает второй отсчет х(2) следующей входной последовательности во второй (11.2) регистр первой группы из Р регистров. Далее работаустройства происходит аналогично,Формула изобретения Устройство для вычисления преобразования фурье-Галуа, содержащее первый сдвиговцй регистр, первую и вторую группы из Р (Р - размер преобразования) регистров, первый элемент И, три элемента ИЛИ, ЯЯ- триггер, группу из Р умножителей на коэффициент и сумматор по модулю М, (М=2 Р), р-й (р=1,Р) вход которого подключен к выходу р-го умножителя на коэффициент, причем установочные входы первого сдвигового регистра, регистров первой и второй групп подключены к установочному входу устройства, к тактовому входу которого подключен тактовый вход первого сдвигового регистра, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей путем вычисления свертки, в него введены группа из Р коммутаторов, первый и второй коммутаторы, второй сдвиговцй регистр, группа иэ Р элементов И, четвертый и пятый элементы ИЛИ, умно- житель на коэффициент, умножитель, счетчик, элемент задержки, второй и третий элементы И, первый и второй триггеры и блок постоянной памяти коэффициентов, выход которого подключен к перво-. му.входу умножителя, выход которого подключен к первому информационному входу первого коммутатора,выходкоторого подключен к информационному входу р-го регистра первой группы, выход которого подключен к первому информационному входу р-го коммутатора группы, выход которого подключен к входу р-го умножителя на коэффициент группы, выход которого подключен к информационному входу р-го регистра второй группы, выход которого подключен к второму информационному входу р-го коммутатора группц, выход коммутатора по модулю М подключен к информационному входу второго коммутатора, первый выход которого подключен к информационному входу второго сдвигового регистра, р-й выход которого подключен к первому входу р-го элемента И группы, ,выход которого подключен к р-му входу первого элемента ИЛИ, выход которого подключен к входу умножителя на коэффициент, выход которого подключен к первому входу второго элемента ИЛИ, выход которого является информационным, выходом устройства, информационным входом которого является второй информационнцй вход первого коммутатора, второй выход второгокоммутатора подключен к второму входу умножителя и первому входу первого элемента И, выход которого подключен к второму входу второго элемента ИЛИ, р-й выход сдвиговаго регистра подключен к 5 второму входу р-го элемента И группы, третий вход которого подключен к прямому выходу первого триггера, инверсный выход которого подключен к управляющему входу второго коммутатора и первому 10 входу третьего элемента ИЛИ, выход которого подключен к управляющему входу первого коммутатора, выход элемента задержки подключен к счетному входу счетчика, тактовому входу р-го регистра второй 15 группы и первому входу второго элемента И, выход которого подключен к первому входу четвертого элемента ИЛИ, выход которого подключен к тактовому входу второго триггера, выход которого под ключен к управляющему входу р-го коммутатора группы и второму входу третьего элемента ИЛИ, первый выход первого сдвигового регистра подключен к В-входу ВЯ-триггера, выход которого подклю чен к информационному входу первого сдвигового регистра, р-й выход которого подключен к первому входу пятого элемента ИЛИ, второму входу второго элемента И и первому входу третьего элемента И, выход которого подключен к второму входу четвертого элемента ИЛИ и тактовому входу первого триггера, установочные входы счетчика, первого и второго триггеров, второго сдвигового регистра и второй вход пятого элемента ИЛИ подключены к установочному входу устройства, к тактовому входу которого подключены вход элемента задержки, второй вход третьего элемента И и тактовый вход второго сдвигового регистра, информационный выход счетчика подключен к адресному входу блока постоянной памяти коэффициентов, р-й выход первого сдвигового регистра подключен к тактовому входу (Р-р+1)-го регистра первой группы, второй вход первого элемента И и третий вход третьего элемента ИЛИ подключены к входу выбора режима устройства.Составитель А.Барановтор С.Пекарь Техред М.Моргентал Корректор М.Максимишинец ственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина, 101 Прои Заказ 2393 Тираж 412 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 4/5