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

 

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

СОЦИАЛИСТИ IECKVIX

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

ГОСУЛАРСТВЕННЬ И КОМИТЕТ

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4840015/24 (22) 18.06.90 (46) 30,07,92. Бюл. М 28 (72) В,П,Якуш, Н.А.Лиходед, В,В.Косьянчук, П,И.Соболевский и П.П.Чернега (56) Кухарев Г.А, и др, Систолические npoqeccopu для обработки сигналов, Мн„1988, с.75, рис. 4,3.1. . Там же. с,79, рис. 4.3.3. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

ДВУМЕРНОГО ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к области вычислительной техники и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов и изображений для вычисления двумерного ДПФ. Цель изоИзобретение относится к области вычислительной техники и может быть использовано в высокопроизводительных специализированнйх машинах и устройствах обработки сигналов для вычисления двумерного

ДПФ.

Цель изобретения — сокращение объема оборудования.

На фиг.1 приведена структурная схема устройства для вычисления двумерного.

ДПФ; на фиг.2 — организация входного и выходного потоков устройства; на фиг,3— организация входного и выходного потоков устройства для =т = P = С! = 3; на фиг,4— функциональная схема операционного блока первого типа; на фиг.5 — функциональная схема операционного блока второго типа; на фиг.6 — схема первого блока ввода (К = I) .„.. Ж,, 1751778 А1 бретения — сокращение объема оборудования. Поставленная цель достигается тем, что устройство содержит P операционных блоков первого типа, P операционных блоков второго типа, rpe Р— размерность входной матрицы Х fP,Q),-и три блока ввода, причем операционный блок первого типа содержит умножитель, сумматор; два регистра, два триггера, узел задержки на I тактов, где — размерность выходной выходной матрицы Y (!, s), две группы элементов И, группу элементов ИЛИ, элемент И и элемент НЕ, а операционный блок второго типа содержит умножитель, сумматор, два регистра, узел задержки на Q тактов, два триггера, четыре группы элементов И, две группы элементов ИЛИ, элемент И и элемент HE. 7 ил. и второго блока ввода (К = т); на фиг.7 — схема третьего блока ввода.

Устройство для вычисления двумерного

ДПФ (фиг.1) содержит группу информационных входов 1;(I = 1.P), информационный вход 2, первый-четвертый 3>-34 тактовые входы, синхровход 6, первый-третий 7 9 блоки ввода, операционные блоки первого типа 10 (i = 1,Р), операционные блоки второго типа 11I(i = 1,Р) и выход 12.

Операционный блок 10 первого типа (фиг.4) содержит пеГвый 13, второй 14 и третий 15 информационные входы, первый

16 и второй 17 тактовые входы, синхровход

18, первый 19 и второй 20 регистры, узел задержки на тактов 21, регистры узла задержки 22 (i = 1,I), умножитель 23, сумматор

24, первую 25 и вторую 26 группы элементов

И, группу элементов ИЛИ 27, первый 28 и

1751778

a— - 1

bjp =, "„Xpq cog

q=O

Р— 1

УЦ = bjp cdP>

p=o второй 29 триггеры, элемент И 30, элемент

НЕ Э1, первый 32, второй ЭЭ информационные выходы, первый 34 и второй 35 тактовые выходы;

Операционный блок 11 второго типа (фиг.5) содержит первый 36-и второй 37 информационные входы, первый 38 и второй

39 тактовые входы, синхровход 40, первый

41 и второй 42 регистры, узел задержки на

0 тактов 43, регистры узла задержки 44q(q =

-1,Q), умножитель 45, сумматор 46, первуючетвертую 47 — 50 группы элементов И, первую 51 и вторую 52 группы элементов ИЛИ, первый 53 и второй 54 триггеры, элемент И

55, элемент НЕ 56, первый 57 и второй 58 информационные выходы, первый 59 и второй 60 тактовые выходы.

Первый блок ввода 7 (К = I) и второй блок ввода 8 (К = т) (фиг.6) содержит информационйые входы 61к(К = 1,К), вход разрешения записи 62, тактовый вход 63, синхровход 64, регистры 65к(К = 1,К), группу элемейтов ИЛИ

66к (К = 1, K}, группу элементов И 67к(К = 1,К), элемент И 68 и выход 69.

Третий блок ввода (фиг.7) содержит информационные входы 70j(i = 1,Р), синхровход 71, элемент задержки 72 (! = 1,Р-1) и выходы 73 (i = 1, Р).

В основу работы устройства для вычис ления двумерйого ДПФ по формулам:

i = 0; 1-1, J = О, ю -1, р = О,Р-1, q = 0,0-1, P — 10 — 1

YIj,, Хря И )л, P =Oq =0 положены следующие рекуррентные соотйошения, J = О, 1 — 1, р = Р- 1,0, q = -1,Q-1, b{J,p,0) = Х,,Q-1, . Ь() р q) = b(J р q— - 1) co+ Xp,î — 1 — q, bj, = b(J,р а 1;

i = б;Т:1, J = О. 1 —.1, р = О, P-1, У(Ц,— 1) = О, Y(l,J,p) = У(Ц, P — 1) o)i + bj, P — 1-р, Yji = У(Ц, -1).

Рассмотрим работу операционных блоков.

Операционный блок первого типаа 10 (фиг.3) работает в четырех режимах. В первом режиме на тактовые входы 16 и 17 подаются соответственно. элементы N Y и Ь.

При этом открываются группа элементов И

25 и элемент И 30, по заднему фронту тактового импульса элемент в через группу эле- .. ментов И 25 и группу элементов ИЛИ 27

5 записывается в регистр 221. элементы Y u

Ь записываются cooTBBTcTBBHHD в регистры 19 и 20, триггеры 28 и 29 устанавлива- . ются в единичное состояние, на выходе умножителя 23 формируется значение Y в;

10 а на выходе сумматора 24 значение Y в+ Ь. Во втором режиме на входы 16 и 17 подаются соответственно единичйый и нулевой сигналы, Триггеры 28 и 29 устанавливаются соответственно в единичное и нулевое

15 состояние. На входы 13 и 14 подаются соответственно элементы в1 и У1, которые записываются соответственно в регистры 221 и 19, в регистр 222 записывается элемент в, регистр 20 хранит элемент Ь, При этом на

20 выходе сумматора 24 формируется значение У1 в1 + Ь. B третьем режиме на входы

16 и 17 подактся соответственно нулевой и единичный сигналы, На входы 14 и 15 подаются соответственно элементы У2 и. Ь1. В регистры 19 и 20 записываются соответственно Yz и Ь1, Триггеры 28 и 29 устанавливаются соответственно в нулевое и единичное состояние, На выходе элемента НЕ 31 формируется единичный сигнал, который

30 открывает группу элементов И 26 и при этом обеспечивается циклическая запись элементов ojj из 22;-го регистра в 22i+1-й регистр. На выходе сумматора 24 формируется значение Yz о.; + Ь1(элемент wj записывается в,регистр 221). В четвертом режиме на входы 1Ь и 17 подаются нулевые сигналы, на вход 14 подается элемент Уз. При этом триггеры 28 и 29 устанавливаются в нулевое состояние, в регистр 19 записывается эле40 мент Уз, регистр 20 хранит элемент b1, на выходе элемента НЕ 31 формируется единичйый сигнал, который разрешает через группу элементов И 26 циклическую запись элементов и; в регистрах 22 узла задержки

21. На выходе сумматора 24 формируется значение Уз Ml<+ Ь1(в регистр 22 записывается элемент в ), Операционный блок второго типа 11 (фиг,4) работает в четырех режимах., В первом режиме на тактовые входы 38 и 39 подаются единичные сигналы, на информационные входы 36 и 37 подаются соотвественно элементы аи X. Открываются группы элементов И 47 и элемент И 55. По заднему фронту тактового импульса через открытый элемент И 55 разрешается запись в регистр

41 элемента йА а через открытую группу элементов И 47 и группу элементов ИЛИ 51 в регистр 441 записывается элемент Х; триг1751778 геры 53 и 54 устанавливаются в единичйое состояние, Во втором режиме на входы 38 и

39 подаются соответственно единичный и нулевой сигналы, на вход 37 подается элемент Õt. При этом запись в регистр 41 за- 5 прещается (в регистре хранится элемент в}, через группу элементов И 47 и группу элементов ИЛИ 51 в регистр 44! записывается элемент х>, в регистры 42 и 442 записывается элемент Х " Ь (триггер 53 находится в 10

" единичном состояни „группа элементов И

49 открыта, через нее и группу элементов

ИЛИ 52 обеспечивается подача элемента хна информационный вход регистра 42),,На выходе умножителя 45 формируется значе- 15 ние х е, а на выходе сумматора 46 — значение Ь1 - b а+ х1, В третьем режиме работы на входы 38 и 39 подаются соответственно нулевой. и единичный сигналы, на вход 36 подается элемент â!. При этом в 20 регистр 41. записывается элемент в1 (элемент И 55 открыт и разрешается запись в регистр 41), через группу элементов И 50 и группу элементов ИЛИ 52 в регистр 42 записыьается значение Ь!, на выходе элемен- 25 та НЕ 56 формируется единичный сигнал, который открывает группу элементов И48 и через группу элементов ИЛИ 51 обеспечивается циклическая запись элементов xI; из

44я-ro регистра в 44ч+ -й регистр. В четвер- 30 том режиме работы на входы 38 и 39 подаются нулевые сигналы, в регистре 41 хранится элемент се1, группа элементов И

48 открывается и обеспечивается циклическая запись элементов х! из 44 -го регистра 35 в 44ч+!-й регистр. Если на предыдущем такте триггер 54 находится в единичном состоянии, то открыта группа элементов И 49, через которую в регистр 42 записывается элемент хк = b. Если триггер 54 находится 40 в нулевом состоянии, то открыта группа элементов И 50, через которую в регистр

42 записывается значение Ьк = Ь, которое сформировано на выходе сумматора 46 на предыдущем такте. При этом на выходе 45 сумматора 46 формируется значение Ь в1 +

+xI, Рассмотрим работу первого 7 блока ввода (фиг.б). При подаче на вход 62 нулевого сигнала /3 группы элементов И 67к(К= 1,l) -0 закрываются и на вторые входы групп элементов ИЛИ ббк(К = 1,I) подаются нулевые значения, на первые входы которых подаются соответствующие коэффициенты а!, которые записываются в соответствующие 55 регистры 65к(К = 1,I) при наличии на входе

63 единичного сигнала (элемент И 68 открывается и тактовый импульс подается на синхровходы всех регистров 65y). При йодаче на вход 62 единичного сигнала /Згруппы эле ентов И 67к(К - 1Я открываются, на входы 61 подаются нулевые значения, на вход 63 подается последовательность единичных управляющих сигналов ac Q-го такта по (Q+I — 1)-й такты, на выход 69 подаются соответствующие коэффициенты в! с Q-го

1 такта по (Q+I — 1)-й такты (фиг.2) и блок ввода

7 за счет обратной связи, соединяющей регистр 65t и группу элементов И 67К, работает в режиме кольцевого счетчика.

Второй блок ввода 8 (К = т) работает аналогично. В регистры 65К(К = 1, t ) при

P = 0 предварительно записываются соответствующие коэффицие ты и)!„, На вход 63 подаются единичные управляющие сигналы а в моменты О, Q, 2Q; „„ (т — 1)Q, которые открывают элемент И 68 и в эти же моменты времени на выход 69 подаются соответствующие коэффициенты и) (фиг,б), Третий блок ввода 9 работает следующим образом (фиг,7), На входы 70!(! = 1,Р) подаются соответствующие элементы хая входной матрицы Х в моменты времени t ( одновременно подаются элементы q-ro столбца матрицы X), которые задерживаются элементами задержки 71|на (Р-!) тактов и подаются на соответствующие выходы 73ь

Организация элементов входной матрицы

Х на выходе блока ввода 9 приведена на фиг.2, Рассмотрим работу устройства для I=

= r = Р = О = 3 (фиг,2). Входной и выходной поток данных приведен на фиг.2 и 3, где в обозначении а индекс t указывает номер такта работы устройства, На вход 2 . постоянно подается нулевое значение. Рассмотрим работу устройства при формировании элемента Уц. На нулевом такте на вход

1з устройства и вход 36 операционного блока 11з подаются соответст,венно элемейты хгг и из, на входы Зз и 34 — единичные сигналы, В операционный блок 11з в регистры 41 и 44 записываеются соответственно элементы вз и x22=Ь(0,2,0). На первомтакте на вход 1з подается х21, на входы Зз и 34— соответственно единичный и нулевой сигналы. В операционном блоке 11з формируется значение Ь(0,2,1) - Ь(0,2,0) щз +

+х21. На втором тагте га вход 1з подается элемент хго, на входы Зз и 34 — соответственно единичный и нулевой сигналы. В операционном блоке 11з формируется значение Ьог = Ь(0,2,2) = Ь(0,2,1) иа + хга, которое подается на третий информационный вход 15 оперативного блока 10з, На третьем такте на вход 13 операционного блока 10з подается элемент вз . В операционном

1751778

20

30

40

55 блоке 10з формируется значение Y(2,0,0)Y(2,0,-1) мз + Ьог, которое подается на вход

14 операционного блока 10г. На четвертом такте в операционном блоке 10г формируется значение Y(2,0,1) = Y(2,0,0) мз ++Ьо, которое подается на вход 14 операционного блока 101. На пятом такте в операционном блоке 10 формируется значение VgpY(2,0,2) Y(2,0,1) вз + bpp, Аналогичным образом формируются остальные элементы Yii, Время вычисления двумерного ДПФ предлагаемым устройством составляет 1 r+ Р + 0 — 2 тактов, а при! = т= P - О - N равно и + 2N — 2 г тактов. Например, для N = 3 устройство реализует вычисление двумерного ДПФ за 13 тактов.

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

Устройство для вычисления двумерного дискретного преобразования Фурье, содержащее Р операционных блоков первого типа, где Р— размерность входной матрицы Х (Р,О), и Р операционных блоков второго типа, причем операционный блок первого типа содержит два регистра, умножитель и сумматор, а операционный блок второго типа — регистр, умножитель и сумматор, о т л и ч а ю щ е е с я тем, что. с целью сокращения объема оборудования, оно содержит три блока ввода, каждый операционный блок первого типа содержит узел задержки, две группы элементов И, группу элементов

ИЛИ, двэ триггера, элемент И и элемент НЕ, каждый операционный блок второго типа— узел задержки, регистр, два триггера, четыре группы элементов И, две группы элемен.тов ИЛИ, элемент И и элемент НЕ, причем первый и второй тактовые входы устройства подключен.ы соответственно к первому и второму тактовым входам первого и второго. блоков ввода, выходы которых подключены соответственно к первым информационным входам Р - x операционных блоков первого и второго типа, информационный вход устройства подключен к второму информаци. Онному входу Р-ro операционного блока первого типа, первый и второй тактовые входы группы устройства — соответственно . к пераоМу и второму тактовым входам P-го операционного блока первого типа, третий и четвертый тактовые входы группы устройства — соответственно к первому и второму тактовым входам Р-ro операционного блока второго типа, i-й вход группы информационных входов устройства подключен к i-му информационному входу третьего блока ввода, I-й выход которого подключен к второму информационному входу 1-го операционного блока второго типа, синхровход устройства подключен к синхровходам всех операционных блоков первого и второго типа устройства, первый и второй информационные входы j-го операционного блока первого типа (j - 1,Р-1) подключены соответственно к первому и второму информационным выходам (j+1)-го"операционного блока первого типа, первый информационный вход j-ro операционного блока второго типа подключен к первому информационному входу (j+1)-го операционного блока второго типа,. первый и второй тактОвые входы i-ro операционного блока первого типа (1 - 1,P-1) подключены соответственно к первому и второму тактовым входам (1+1)-ro операционного блока первого типа, первый и второй тактовые входы l-го операционного блока второго типа (i = 1,Р-1) подключены соответственно к первому и второму тактовым выходам (1+1)-ro операционного блока второго типа, второй информационный выход 1-го операционного блока второго типа подключен к третьему информационному входу 1-го операционного блока первого типа, второй информационный выход первоro операционного блока первого типа подключен к выходу устройства, причем в операционном блоке первого типа первый информационный вход подключен к первым входам элементов И первой группы, вторые входы которых соединены с информационным входом первого триггера и подключены к первому управляющему входу операционного блока первого типа, а выходы элементов И первой группы соответственно подключены к первым входам элементов ИЛИ группы, вторые входы которых подключены к выходам соответствующих элементов И второй группы, а выходы— к соответствующим информационным входам узла задержки, первый информационный выход которого подключен к первому входу умножителя и к первому информаци45 онному выходу операционного блока первого типа, а второй информационный выход — к первым входам элементов И второй группы, втбрые входы которых подключены к выходу элемента НЕ, вход которого пОдключен к первому тактовому входу оперэционного блока первого типа, второй информационный вход которого подключен к. информационному входу первого регистра, вйход которого подключен к второму входу умножителя, выход которого подключен к первому входу сумматора, выход которого подключен к второму информационному выходу операционного блока первого типа, третий информационный вход которого подключен к информационному входу второго

1751778

10. Xle Хр уq

Фиг.1 х>< регистра, выход которого подключен к второму входу сумматора, первый вход элемента И соединен с информационным входом второго триггера и подключен к второмутактовому входу операционного блока первого типа, выходы первого и второго триггеров подключены соответственно к первому и второму тактовым выходам операционного блока первого типа, синхровход которого подключен к синхровходам первого регистра, узла задержки, и рвого и второго триггеров и второму входу элемента И, при этом . в операционном блоке второго типа первый информационный вход подключен к информационному входу первого регистра, выход которого подключен к первому входу умножителя и к первому информационному выходу операционного блока второго типа; второй информационный вход которого подключен к первым входам элементов И первой группы, вторые входы которых соединены с входом элемента НЕ, информацион ным входом первого триггера и подключены к первому тактовому входу операционного блока второго типа, а выходы элементов И первой группы подключены к первым входам соответствующих элементов ИЛИ первой группы, вторые входы которых подключены к выходам соответствующих элементов И второй группы, а выходы — к информационным входам узла задержки на

0 тактов, первый информационный выход которого подключен к первым входам элементов И третьей группы и к первому входу сумматора, а второй информационный выход — к пеовым входам элементов И второй группы, вторые входы которых подключены

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

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

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

25 входам элементов И третьей группы, прямой выход первого триггера подключен к первому тактовому выходу 6перационного блока второго типа, выход элемента И вЂ” к тактовому входу первого регистра, синхров30 ход операционного блока второго типа. — к синхровходам второго регистра, узла задержки, первого и второго триггеров и к второму входу элемента И. б о

О у

«юб»

C+

С»

Ф

««а (ь о.

ЪС

Ф с» (I а

Ъ М (;», Ф.

Ъ ( (» (»«

Ъ (Э

О . (у х

О. с (3

;З с4 б а б

О ь

=л

У) («Р

Ю м

«»

gl с .о (6 с @

Г О

6 с йь и (» (о ч е н

1 н

О. к

Q ч» с.

О

4»

Ь (:»

И а

О

I б (:»

С ) с д Ъс ь 7 (о

: (3 с

1 о

О C) е Ь

3 ъ.

1751778

f (Э

Ю

«

К

Ю î

°

О (»..с- Ы. гЦ

I Ф

О Ю (.»

Ф1/ а О ,Ф. О

Ъ

1751178

О О

С)

4г

4ь

Щ. И)

"Ф»

З с0 щ г» е, G о

Cl eO

3 сг

1751 77В

1751778

l2 t.2 (g.у) ф)} !g дИ./

7И

t р-у t p- j re sf

t+I

)fp Р

e gnC

Составитель В. Якуш

Техред М. Моргентал

Редактор О. Спесивых

Корректор 8Яетраш

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

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

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

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