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

Ё

Изобретение относится к вычислительной технике и технической кибернетике и может быть использовано в цифровых вычислительных системах, предназначенных для обработки сигналов, в частности для обработки изображений. Цель изобретения - расширение функциональных возможностей путем вычисления свертки. Устройство содержит пять элементов ИЛИ, два сдвиговых регистра, элемент задержки, RS-триггер, два коммутатора, две группы регистров, три элемента И, два триггера, группу коммутаторов, группу умножителей на коэффициент, сумматор по модулю M, умножитель, счетчик, группу элементов И, блок постоянной памяти коэффициентов, умножитель на коэффициент. 4 ил.

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

Целью изобретения является расширение функциональных возможностей за счет вычисления свертки.

На фиг.1 представлена структурная схема устройства; на фиг,2 - временные диаграммы работы устройства в режиме вычисления ППФГ; на фиг.З - временные диаграммы работы устройства в режиме вычисления свертки; на фиг.4 - структура размещения данных в регистрах устройства.

На фиг.2 обозначены: а - тактовая последовательность; б - сигнал на выходе элемента задержки; в - импульс начальной установки; г - сигнал на управляющих входах первого и второго коммутаторов; д сигнал на управляющих входах группы из Р коммутаторов; е - сигнал на инверсном выходе второго Т-триггера; ж - структура данных на входе устройства; з - структура сигналов на выходе сдвигового регистра; и - структура данных в первой группе из Р регистров; к - структура данных во второй группе из Р регистров; л - структура выходного сигнала. На фиг.З обозначены: а - тактовая последовательность; б - сигнал на выходе элемента задержки; в - импульс начальной установки; г-сигнал на управляющем входе второго коммутатора; д - сигнал на управляющем входе первого коммутатора; е - сигналы на управляющих входах группы из Р коммутаторов; ж - структура данных на входе устройства; з - структура сигналов на выходе сдвигового регистра; и - структура данных в первой группе из Р регистров: к - структура данных во второй группе из Р регистров; л - структура данных на выходах

О

о ел

00 00

ел

Р-разрядного сдвигового регистра; м - структура выходного сигнала.

На фиг.4 обозначены: а - структура данных в регистрах первой группы на первом этапе вычислений (после прохождения Р тактовых импульсов); б - структура данных во второй группе из Р регистров после первого этапа вычислений (после прохождения Р тактовых импульсов); в - структура данных в первой группе из Р регистров после второго этапа вычисления (после прохождения 2Р тактовых импульсов); г - структура данных в регистрах второй группы из Р регистров после второго этапа вычислений (после прохождения 2Р тактовых импульсов); д - структура данных в Р-разрядном сдвиговом регистре.

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

коммутаторов 17.117.Р, первый триггер

18, группу из Р умножителей на коэффициенты 19.1,...,19,Р, сумматор 20 по модулю М (), матричный умножитель 21 по модулю М( -1), коммутатор 22, Р-разряд- ный сдвиговый регистр 23, элемент И 24, счетчик 25, группу из Р трехвходовых элементов И 26, блок 27 постоянной памяти коэффициентов, Р-входовый элемент ИЛИ 28, умножитель 29 на коэффициент Р, элемент ИЛИ 30,информационный выход31 устройства.

Управление элементами устройства происходит следующим образом,

Импульсом по входу 2 обнуляются сдвиговый регистр 6, первая группа из Р- регистров 11.1,...,11.Р, вторая группа из Р регистров 15.115.Р, Р-разрядный сдвиговый регистр 23, счетчик 25, триггеры 16 и 18 (лог. О - на прямом выходе, лог. 1 - на инверсном), и включается RS-триггер 9 (лог. 1 - на выходе). .Лог. 1 на управляющих входах коммутаторов 10 и 22 подключает входы коммутатора к выходам (в случае коммутатора 22 - информационные входы к первым выходам), а лог. О на управляющих входах группы из Р коммутаторов 17,1,...,17.Р подключает вторые входы коммутаторов к их выходам. Изменение управляющего сигнала приводит к перекоммутации входов. Лог. О с прямого выхода триггера 16 блокирует группу из Р трехвходовых элементов И 26. Триггер 16 управляется срезом импульсов с выхода элемента ИЛИ 14, на вход которого поступают с выхода элемента И 12 совпадающие лог. 1 с Р-го выхода сдвигового регистра 6 и импульс с выхода элемента 9 задержки, а на другой вход с выхода элемента И 13 - совпадающие лог. 1 с Р-го выхода сдвигового

регистра 6 и тактовый импульс с тактового входа 3. Р-разрядный сдвиговый регистр 23 тактируется тактовыми импульсами с тактового входа 3 устройства.

Работа устройства, в зависимости от режима, заключается в следующем.

В режиме вычисления ППФГ устройство производит вычисление в соответствии с выражением, соответствующим ППФГ.

где х(р) - отсчеты входной последовательности;

Х(р) - коэффициент ППФГ.

В режиме вычисления свертки устройство производит вычисления по формуле у(р) х(р)п(р),(2)

где у(р) - выходная последовательность; х(р) - входная последовательность;

h(p) -последовательность, сворачиваемая с входной,

следующим образом. Сначала вычисляется ППФГ входной последовательности х(р), затем производится перемножение ППФГ

входной Х(р) и сворачиваемой с входной Н(р) последовательностей, затем производится обратное преобразование Фурье-Галуа (ОПФГ) перемноженных коэффициентов Х(р) Н(р) и окончательно производится VMножение на нормирующий множитель , представляющий собой обратный элемент от Р, т.е. устройство работает в соответствии с формулой

у(р) (х) -ППФГ(п)- р 1.(3)

Так как сворачиваемая с входной последовательность п(р) обычно неизменна в процессе вычислений, то ее коэффициенты Н(р) могут быть вычислены до начала вычисления свертки Н(р) в режиме вычисления ППФГ и записаны в блок 27.

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

Импульс по входу 2 приводит устройство в исходное положение; регистры 6,11.111.Р, 15.115.Р,23, счетчик 25 и

триггеры 16 и 18 обнулены, RS-триггер 9 включен, первые входы коммутатора 10 подключены к выходам, вторые входы группы из Р коммутаторов 17.117.Р подключены к выходам, информационные входы коммутатора 22 подключены к первым выходам. Отсчеты входной последовательности х(р) поступают с частотой, равной тактовой частоте на тактовом входе 3 устройства.

Импульс с первого выхода сдвигового регистра 6 записывает первый отсчет х(0) входной последовательности х(р) в первый регистр 11.1 первой группы из Р регистров, импульс с второго выхода сдвигового регистра 6 - второй отсчет х(1) во второй регистр 11.2 и т.д., импульсе Р-го выхода сдвигового регистра б - (Р-1)-й отсчет х(Р-1) в Р-й регистр 11.Р. Р-м тактовым импульсом переключаются группа из Р коммутаторов 17.1,...,17.Р (первые входы подключают- ся к выходам} и коммутатор 11 (информационные входы подключаются к вторым выходам и входу элемента И 24), и данные с выходов первой группы из Р регистров 11.1 через коммутаторы 17.117.Р и

умножители 19.1.....19.Р поступают на D-входы второй группы из Р регистров 15.115.Р и на входы сумматора 20 по модулю, где суммируются по модулю М 2р-1, вычисляя коэффициент Х(р-1), ко- торый с выхода сумматора 20 по модулю М через коммутатор 22, элемент И 24 и- элемент ИЛИ 30 поступает на информационный выход 31 устройства.

(Р+1)-й тактовый импульс приводит к по- явлению лог. 1 на первом выходе сдвигового регистра 6 и записи первого отсчета х(0) следующей входной последовательности в первый регистр 11.1 первой группы из Р регистров 11.1,...,11.Р,(Р-1)-й импульс вы- хода элемента 7 задержки приводит к записи в регистры второй группы из Р регистров 15.1,...,15.Р и появлению на информационных выходах 31 устройства третьего коэффициента Х(Р-З).

В последующие (Р-1) такта работа устройства происходит аналогично.

(2Р-1}-й импульс с выхода элемента 7 задержки приводит к появлению на информационном выходе 31 устройства последне- го коэффициента Х(0) ППФГ первой входной последовательности.

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

Вычисление ППФГ может продолжаться в реальном времени, так как коммутатор 10 не переключается, заблокированный через трехвходовый элемент ИЛИ 5 лог. 1 с входа 4.

В режиме вычисления свертки лог. О на входе 4 запись отсчетов входной последовательности х(Р) в первую группу из Р регистров 11.111,-Р происходит аналогично начальной записи данных в режиме ППФГ. Р-й импульс выхода элемента И 13 не приводит к переключению коммутатора 10, так как он блокируется переключающимся первым триггером 18 (лог. 1 на прямом выходе). Данные с выходов первой группы из Р-регистров 11.111.Р через коммутаторы 17.1,...,17.Р и умножители 19.1,,..,19.Р на коэффициент поступают на D-входы группы из Р регистров 15.115.Р, Р-й импульс выхода элемента 7 задержки записывает во вторую группу из Р регистров 15.115.Р данные с их D-входов и приводит к переключению коммутаторов 17.117.Ри 10 (вторы ев ходы подключаются к выходам). С выходов второй группы из

Р регистров 15.115.Р через коммутаторы

второй группы из Р регистров 15.115.Р и

на входы сумматора 20 по модулю М, где вычисляется коэффициент Х(Р-2), который через коммутатор 22 поступает на входы умножителя 21 по модулю М, на другие входы которого с нулевой ячейки блока 27 поступает значение коэффициента Н(Р-2). С выходов умножителя 21 по модулю Н произведение Х(Р-2) Н(Р-2) через коммутатор 10 поступает на D-входы первой группы из Р

регистров 11.111.Р, в первый (11.1) из

которых оно записывается импульсом с первого выхода сдвигового регистра 6, который появляется после появления (Р+1)-го тактового импульса.

(Р+1)-й импульс с выхода элемента 7 задержки записывает во вторую группу из Р

регистров 15.115.Р данныес их D-входов

и изменяет адрес ячеек блока 27.

С выходов второй группы из регистров

которых оно записывается импульсом с второго выхода сдвигового регистра 6. Далее (Р-2) такта работа устройства происходит аналогично.

2Р-й тактовый импульс приводит к переключению коммутаторов 10,17.1,,..,17.Р (первые входы подключаются к выходам) и второго коммутатора 22 (информационные входы подключаются к первым выходам). Данные с выходов первой группы из Р регистров 11, ,...,11.Р через коммутаторы 17,117.Р и умножители 19.119.Р поступают на D-входы второй группы из Р регистров 15.1,.,.,15.Р. 2Р-й импульс выхода элемента 7 задержки записывает во вторую группу из Р регистров 15.1,...,15.Р данные с их D-входов и переключает коммутаторы

выходам).

(2Р+ 1)-й тактовый импульс приводит к записи отсчета х(0) следующей входной последовательности в первый (11.1) из первой группы Р регистров 11.111.Р и к

записи в первый регистр Р-разрядного сдвигового регистра первого модифицированного отсчета у(0) выходной последовательности, который с выхода сумматора 20 по модулю М через коммутатор 22 поступает на входы Р-разрядного сдвигового регистра 23.

(2Р-И)-й импульс с выхода элемента 7 задержки записывает во вторую группу их Р регистров данные с их D-входов.

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

(ЗР+ 1)-й тактовый импульс начинает цикл обработки следующей последовательности, записывая в регистр 11.1 первой группы из Р регистров 11,1,...,11.Р новое произведение Х(Р-2) Н(Р-2), а также с Р-го разряда Р-разрядного сдвигового регистра 23 через группу из Р трехвходовых элементов И 2б,-Р-входовый элемент ИЛИ 28, умножитель 29 на коэффициент и элемент ИЛИ 30 выводит на информационный выход 31 устройства первый отсчет у(0) выходной последовательности. (ЗР+2)-й тактовый импульс выводит на информационный выход 31 устройства второй отсчет у(1) выходной последовательности и записывает второй отсчет х(2) следующей входной последовательности во второй (11.2) регистр

первой группы из Р регистров. Далее работа устройства происходит аналогично,

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

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

расширения функциональных возможностей путем вычисления свертки, в него введены группа из Р коммутаторов, первый и второй коммутаторы, второй сдвиговый регистр, группа из Р элементов И,

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

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

выход которого подключен к информационному входу р-го регистра второй группы, выход которого подключен к второму информационному входу р-го коммутатора группы, выход коммутатора по модулю М подключен к информационному входу второго коммутатора, первый выход которого подключен к информационному входу второго сдвигового регистра, р-й выход которого подключен к

0 первому входу р-го элемента И группы, выход которого подключен к р-му входу первого элемента ИЛИ, выхо Д которого подключен к входу умножителя на коэффициент, выход которого подкя.ючен

5 к первому входу второго элемента ИЛИ, выход которого является информационным, выходом устройства, информационным входом которого является второй информационный вход первого коммутатора, второй выход второго

коммутатора подключен к второму входу умножителя и первому входу первого элемента И, выход которого подключен к второму входу второго элемента ИЛИ, р-й выход сдвигового регистра подключен к второму входу р-го элемента И группы, третий вход которого подключен к прямому выходу первого триггера, инверсный выход которого подключен к управляющему входу второго коммутатора и первому входу третьего элемента ИЛИ, выход которого подключен к управляющему входу первого коммутатора, выход элемента задержки подключен к счетному входу счетчика, тактовому входу р-го регистра второй группы и первому входу второго элемента И, выход которого подключен к первому входу четвертого элемента ИЛИ, выход которого подключен к тактовому входу второго триггера, выход которого под- ключей к управляющему входу р-го коммутатора группы и второму входу третьего элемента ИЛИ, первый выход первого сдвигового регистра подключен к R-входу RS-триггера, выход которого подклю-

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

- УЛУЛЩ 1 п J-:

Ж./ТХ2ХРЛ7Т2

i t j i AZ.XP XTTL

tf К К К К К Л К

/гК К КАК

лПК X

0уе.2

4+ f44444

-444Ч4ЧИЧЧИЧ4

-у--

v

г

г

Г

г

г

1 Х2

Г. , f-t

Ы

w