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

 

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

союз советских

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

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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

6

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ. (21) 4731785/24 (22) 29.06.89 (46) 23.07.91. Бюл. В 27 (71) Научно-исследовательский институт бытовой радиоэлектронной аппаратуры (72) Л.В.Вариченко, В.И.Кодров и А.И,Устрехов (53) 681.32 (088.8) (56) Заявка Франции М 2384303, кл. G 06 F 15/332, 1980.

Авторское свидетельство СССР

М 1218396, кл. 6 06 F 15/332, 1986. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

ПРЕОБРАЗОВАНИЯ ФУРЬЕ-ГАЛУА (57) Изобретение относится к вычислительной технике и технической кибернетике и

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

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

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

На фиг.2 обозначены: а — тактовая последовательность; б — сигнал на выходе элемента задержки; в — импульс начальной установки; r — сигнал на управляющих входах первого и второго коммутаторов; д—, Ы,, 1665385 А1 может быть использовано в цифровых вычислительных системах, предназначенных для обработки сигналов, в частности для обработки иэображений. Цель изобретения — расширение функциональных возможностей путем вычисления свертки.

Устройство содержит пять элементов ИЛИ, два сдвиговых регистра, элемент задержки, RS-триггер, два коммутатора,две группы регистров, три элемента И, два триггера, группу коммутаторов, группу умножителей на коэффициент, сумматор по модулю М, умножитель, счетчик, группу элементов И, блок . постоянной памяти коэффициентов. умножитель на коэффициент. 4 ил. сигнал на управляющих входах группы из P коммутаторов; е — сигнал на инверсном выходе второго Т-триггера; ж — структура данных д, на входе устройства; з — структура сигналов на выходе сдвигового регистра; и — структура данных в первой группе иэ Р регистров; к — структура данных во второй группе из P регистров; л — структура выходного сигнала. О

На фиг.3 обозначены: а — тактовая по- . 00 следовательность; б — сигнал на выходе (Л элемента задержки; в — импульс начальной установки; г-сигнал на управляющем входе второго коммутатора; д — сигнал на управлявВ ющем входе первого коммутатора; е — сигналы на управляющих входах группы иэ P коммутаторов; ж — структура данных на входе устройства; з — структура сигналов на выходе сдвигового регистра; и — структура данных в первой группе из P регистров; к— структура данных во второй группе из P регистров; л — структура данных на выходах

1665385

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

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

P тактовых импульсов); в - структура данных в первой группе из Р регистров после второго этапа чычисления (после прохождения

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

Устройство для вычисления преобразования Фурье-Галуа содержит информационный вход 1, установочный вход 2, тактовый вход 3, выход 4 выбора режима (трехвходовый), элемент ИЛИ 5, сдвиговый регистр 6, элемент 7 задержки, элемент

ИЛИ 8, RS-триггер 9, коммутатор 10, регистры 11.1,...,11.P первой группы иэ P регистров, элемент И 12, элемент И 13, элемент

ИЛИ 14, регистры 15.1,...,15.P второй группы из Р регистров, триггер 16, группу из Р коммутаторов 17,1,...,17.Р, первый триггер

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

28, умножитель 29 на коэффициент Р, элемент ИЛИ 30,информационный выход 31 устройства.

Управление элементами устройства происходит следующим образом, Импульсом по входу 2 обнуляются сдвиговый регистр 6, первая группа из Ррегистров 11.1,...,11.Р, вторая группа из Р регистров 15.1,...,15,Р, Р-разрядный сдвиговый регистр 23, счетчик 25, триггеры 16 и 18 (лог. "0" — на прямом выходе, лог. "1" — на инверсном), и включается RS-триггер 9 {лог.

"1" — на выходе)..Лог. "1" на управляющих входах коммутаторов 10 и 22 подключает входы коммутатора к выходам (в случае коммутатора 22 — информационные входы к первым выходам), а лог. "0" на управляющих входах группы из P коммутаторов

17,1,...,17.P подключает вторые входы коммутаторов к их выходам. Изменение управляющего сигнала приводит к перекоммутации входов. Лог. "0" с прямого выхода триггера 16 блокирует группу из Р трехвходовых элементов И 26. Триггер 16 управляется срезом импульсов с выхода элемента

ИЛИ 14, на вход которого поступают с выхода элемента И 12 совпадающие лог. "1" с

Р-го выхода сдвигового регистра 6 и импульс с выхода элемента 9 задержки, а на другой вход с выхода элемента И 13 — совпадающие лог. "1" с Р-ro выхода сдвигового регистра 6 и тактовый импульс с тактового входа 3. Р-разрядный сдвиговый регистр 23 тактируется тактовыми импульсами с тактового входа 3 устройства.

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

8 режиме вычисления ППФГ устройство производит вычисление в соответствии с выражением, соответствующим ППФГ.,2 ,2 х (о) х () к х (р-а}

Х (p-t) Х (p-t$

x (p-д.)

Х (() х (о3 ) P-1

2о

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

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

В режиме вычисления свертки устройство производит вычисления по формуле у(р) = х(р) " h(p), (2) где у(р) — выходная последовательность; х(р) — входная последовательность;

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

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

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

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

Устройство в режиме вычисления ППФГ работает следующим образом, Импульс по входу 2 приводит устройство .в исходное положение: регистры

6,11.1,...,11.Р, 15.1,...,15.Р,23„счетчик 25 и

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

Импульс с первого выхода сдвигового регистра 6 записывает первый отсчет х(0) входной последовательности х(р) в первый регистр 11.1 первой группы из P регистров, импульс с второго выхода сдвигового регистра 6 — второй отсчет х(1) во второй регистр

11.2 и т.д., импульс с P-ro выхода сдвигового регистра 6 — (P-1)-й отсчет х(Р-1) в P-й регистр 11.P. Р-м тактовым импульсом переключаются группа из P коммутаторов

17.1...„17.P (первые входы подключаются к выходам) и коммутатор 11 (информационные входы подключаются к вторым выходам и входу элемента И 24), и данные.с выходов первой группы из Р регистров 11.1 через коммутаторы 17.1,...,17.P u умножители 19.1,...,19.Р поступают на

0-входы второй группы из P регистров

15 1,...,15.P и на входы сумматора 20 по модулю, где суммируются по модулю M =

:=2 -1, вычисляя коэффициент Х(р-1), который с выхода сумматора 20 rio модулю

М через коммутатор 22, элемент И 24 и элемент ИЛИ 30 поступает на информационный выход 31 устройства. (P+1)-й тактовый импульс приводит к появлению лог. "1" на первом выходе сдвигового регистра 6 и записи первого отсчета х(0) следующей входной последовательности в первый регистр 11.1 первой группы иэ

Ррегистров 11.1,,.„11.Р, (Р-1 -й импульс выхода элемента 7 задержки приводит к записи в регистры второй группы из P регистров

15.1,...,15.P и появлению на информационных выходах 31 устройства третьего коэффициента X(P-3).

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

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

Вычисление ППФГ может продолжаться в реальном времени, так как коммутатор

10 не переключается, заблокированный чеся первым триггером 18 (лог. "1" на прямом выходе). Данные с выходов первой группы из P-регистров 11.1,...,11.Р через коммутаторы 17.1,...,17.P и умножители 19.1,...,19.Р

15 на коэффициент поступают на 0-входы группы из P регистров 15 1,...,15.P, P-й импульс выхода элемента 7 задержки записывает во вторую группу из Р регистров

15.1, „15.P данные с их D-входов и приво20 дит к переключению коммутаторов выходов умножителя 21 по модулю Н произведение Х(Р-2) Н(Р-2) через коммутатор 10

35 поступает на 0-входы первой группы иэ Р

45

55 27 поступает значение коэффициента Н(Р-3)., С выхода умножителя 21 по модулю М про5

30 рез трехвходовый элемент ИЛИ 5 лог. "1" с входа 4.

В режиме вычисления свертки лог. "0" на входе 4 запись отсчетов входной последовательности x(P) в первую группу из Р регистров 11.1,.„,11;P происходит аналогично начальной записи данных в режиме

ППФГ. P-й импульс выхода элемента И 13 не приводит к переключению коммутатора t 0, так как он блокируется переключающим17.1,..., f 7,Ð и 10 (вторые входы подключаются к выходам). С выходов второй группы из

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

17,1,.„,17.P и умножители 19.1,...,19.P на коэффициент данные поступают на 0-входы второй группы из Р регистров 15.1,.„,15 P u на входы сумматора 20 по модулю М, где вычисляется коэффициент X(P-2), который через коммутатор 22 поступает на входы умножителя 21 по модулю М, на другие входы которого с нулевой ячейки блока 27 поступает значение коэффициента Н(Р-2). С регистров 11.1,...,11.Р, в первый (11.1) из которых оно записывается импульсом с первого выхода сдвигового регистра 6, который появляется после появления (Р+1)-ro тактового импульса. (Р+1)-й импульс с выхода элемента 7 задержки записывает во вторую группу из P регистров 15.1,. „15.P данные с их 0-входов и изменяет адрес ячеек блока 27.

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

15.1,...,15.P данные через коммутаторы

17.1,...,17.P и умножители l9.1,...,19.P на коэффициент поступают на 0-входы второй группы из P регистров 15.1,....15.P и на входы сумматора 20 по модулю И, где вычисляется значение коэффициента X(P-3), который через коммутатор 22 поступает на входы умножителя 21 по модулю М, на другие входы которого с первой ячейки блока изведение X(P — 3) H(P — 3) через коммутатор

10 поступает на D-входы первой группы из

P регистров 11.1,...,11.Р, во второй (11.2) из

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

2Р-й тактовый импульс приводит к пере- 5 ключению коммутаторов 10,17.1„...17.P, (первые входы подключаются к выходам) и второго коммутатора 22 (информационные входы подключаются к первым выходам).

Данные с выходов первой группы из Р реги- 10 стров 11,",...,11.Р через коммутаторы

17,1,...,17.Р и умножители 19.1,...,19.P поступают на D-входы второй группы из Р регистров 15.1,...,15.P. 2Р-й импульс выхода элемента 7 задержки записывает во вторую 15 группу из Р регистров 15.1,...,15.P данные с их 0-входов и переключает коммутаторы

17,1,...,17.Р (вторые входы подключаются к выходам). (2Р+ 1)-й тактовый импульс приводит 20 к записи отсчета х(0) следующей входной последовательности в первый (11 1) из первой группы Р регистров 11.1,.;.,11.P и к записи.в первый регистр Р-разрядного сдвигового регистра первого модифициро- 25 ванного отсчета y{0) выходной последовательности, который с выхода сумматора 20 по модулю M через коммутатор 22 поступает на входы P-разрядного сдвигового регистра 23. 30 (2Р+1)-й импульс с выхода элемента 7 задержки записывает во вторую группу их Р регистров данные с их 0-входов. (2Р+2)-й тактовый импульс приводит к 35 записи во второй (11.2) регистр из первой группы из Р регистров второго отсчета х(1) следующей последовательности и к записи во второй регистр Р-разрядного сдвигового регистра 23 второго модифи- 40 цированного у(Р-1). Далее (Р-2) такта работа устройства происходит аналогично, (ЗР+ 1)-й тактовый импульс начинает цикл обработки следующей последова- 45 тел ьности, записывая в регистр 11.1 первой группы из Р регистров 11.1,..., 11.P новое произведение Х(Р-2} H{P-2), а также с P-го разряда Р-разрядного сдвигового регистра 23 через группу из Р трехвходовых 50 элементов И 26,.Р-входовый элемент ИЛИ

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

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

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

1665385

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

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

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

1665385

7 !! 3 !

1 2

1 2 P 1 2 2Р 2 3 г Р 1 Z

2- р 1 R1 2 P У 2 2р. Р 1 2 ФР 7 2 Хр 1

2 .ГТХТТя r u i а

1 2 Р 1 2 2Р 1 2 ЗР 7 2 Ю 7. 2 5Р 7 2U

1 Л у 2

21

1

Е 1

1 2 Р 1 2 ZP 1 Л Я 1 2 КР 1 2 5Р 7 Г

1665385

Составитель А.Баранов

Техред М.Моргентал Корректор М.Максимишинец

Редактор С.Пекарь

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

Заказ 2393 Тираж 412 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5