Устройство для вычисления двумерного дискретного преобразования Фурье Советский патент 1992 года по МПК G06F15/332 

второй 29 триггеры, элемент И 30, элемент НЕ 31, первый 32, второй 33 информационные выходы, первый 34 и второй 35 тактовые выходы.

Операционный блок 11 второго типа (фиг.5) содержит первый 36 и второй 37 информационные входы, первый 38 и второй 39 тактовые входы, синхровход 40, первый 41 и второй-42 регистры, узел задержки на О.тактов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к (К Щ группу элементов И 67к(К 1 ,К), элемент И 68 и выход 69.

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

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

I 0.1-1, J 0, г-1, р О.Р-1, q 0,0-1,

р - IQ - 1 Yij 2 2ХрчшЫЈ,

Р 0q 0

bjP 2xpq4q-q 0

YiJ 2Ь,рйЛ. P 0

оложены следующие ошения: j

рекуррентные соот0, r-1, p P-1,0, q 1,0-1, b(j,p,0) XP,Q-1,

b(J,p.q) b(j,p,q-1) 4+Xp,Q-1-q. bJPzb(LP Qzlll

i o7riTj o. r-i, p o,p-i.

Y(l,j,-1) 0,

Y(IJ.p)- Y(l.j.P-1) Щ + bj, P-1-p,

Yji Y(i,j,P-1).

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

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

При этом открываются группа элементов И 25 и элемент И 30, по заднему фронту тактового импульса элемент (а через группу элементов И 25 и группу элементов ИЛИ 27

записывается в регистр 221, элементы Y и b записываются соответственно в регистры 19 и 20, триггеры 28 и 29 устанавлива- ются в единичное состояние, на выходе умножителя 23 формируется значение Y ш,

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

состояние. На входы 13 и 14 подаются соответственно элементы и YI, которые записываются соответственно в регистры 22i и 19, е регистр 22а записывается элемент ш, регистр 20 хранит элемент Ь. При этом на

выходе сумматора 24 формируется значение YI + Ь. В третьем режиме на входы 16 и 17 подаются соответственно нулевой и единичный сигналы. На входы 14 и 15 подаются соответственно элементы YZ и bi. В

регистры 19 и 20 записываются соответственно Y2 и bi. Триггеры 28 и 29 устанавливаются соответственно в нулевое и единичное состояние. На выходе элемента НЕ 31 формируется единичный сигнал, который

открывает группу элементов И 26 и при этом обеспечивается циклическая запись элементов щ из 22гго регистра в 22|+1-й регистр На выходе сумматора 24 формируется значение Y2 а + bi (элемент 0) зэписывается в регистр 221). В четвертом режиме на входы 16 и 17 подаются нулевые сигналы, на вход 14 подается элемент Уз При этом триггеры 28 и 29 устанавливаются в нулевое состояние, в регистр 19 записывается элемент YS, регистр 20 хранит элемент bi, на выходе элемента НЕ 31 формируется единичный сигнал, который разрешает через группу элементов И 26 циклическую запись элементов щ в регистрах 22 узла задержки

21 На выходе сумматора 24 формируется значение УЗ ад + bi (в регистр 221 записывается элемент ол).

Операционный блок второго типа 11 (фиг,4) работает в четырех режимах. В

первом режиме на тактовые входы 38 и 39 подаются единичные сигналы, на информационные входы 36 и 37 подаются соотвест- венноэлементы Открываются группы элементов И 47 и элемент И 55 По заднему

фронту тактового импульса через открытый элемент И 55 разрешается запись в регистр 41 элемента со, а через открытую группу элементов И 47 и группу элементов ИЛИ 51 в регистр 44i записывается элемент X. триггеры 53 и 54 устанавливаются в единичное состояние. Во втором режиме на входы 38 и 39 подаются соответственно единичный и нулевой сигналы, на вход 37 подается элемент XL При этом запись в регистр 41 за- прещается (в регистре хранится элемент ей), через группу элементов И 47 и группу элементов ИЛИ 51 в регистр 44i записывается элемент XL в регистры 42 и 442 записывается элемент X b (триггер 53 находится в единичном состояние группа элементов И 49 открыта, через нее и группу элементов ИЛИ 52 обеспечивается подача элемента х на информационный вход регистра 42). На выходе умножителя 45 формируется значе- ние х СУ, а на выходе сумматора 46 - значение bi b w + XL В третьем режиме работы на входы 38 и 39 подаются соответственно нулевой и единичный сигналы, на вход 36 подается элемент й. При этом в регистр 41 записывается элемент щ (элемент И 55 открыт и разрешается запись в регистр 41), через группу элементов И 50 и группу элементов ИЛИ 52 в регистр 42 за- писыьается значение bi, на выходе элемен- та НЕ 56 формируется единичный сигнал, который открывает группу элементов I448 и через группу элементов ИЛИ 51 обеспечивается циклическая запись элементов xj; из 44q-ro регистра в 44ч-н-й регистр. В четвер- том режиме работы на входы 38 и 39 подаются нулевые сигналы, в регистре 41 хранится элемент аи, группа элементов И 48 открывается и обеспечивается циклическая запись элементов xj из 44q-ro регистра в 44ч+1-й регистр. Если на предыдущем такте триггер 54 находится в единичном состоянии, то открыта группа элементов И 49, через которую в регистр 42 записывается элемент хк Ь. Если триггер 54 находится в нулевом состоянии, то открыта группа элементов И 50, через которую в регистр 42 записывается значение Ьк Ь, которое сформировано на выходе сумматора 46 на предыдущем такте. При этом на выходе сумматора 46 формируется значение b (Oi +

+XJ.

Рассмотрим работу первого 7 блока ввода (фиг.6). При подаче на вход 62 нулевого сигнала / группы элементов И 67к(К 1,1) закрываются и на входы групп элементов ИЛИ 66к(К 1,1) подаются нулевые значения, на первые входы которых подаются соответствующие коэффициенты ut. которые записываются в соответствующие регистры 65к(К 1,1) при наличии на входе 63 единичного сигнала (элемент И 68 откры- ваетсй и тактовый импульс подается на син- хровходы всех регистров 65к). При подаче

на вход 62 единичного сигнала / группы элементов И 67к(К Tj) открываются, на входы 61 к подаются нулевые значения, на вход 63 подается последовательность единичных управляющих сигналов ас Q-ro такта по (СЖ-1)-й такты, на выход 69 подаются соответствующие коэффициенты с Q-ro такта по (0+1-1)-й такты (фиг.2) и блок ввода 7 за счет обратной связи, соединяющей регистр 65i и группу элементов И 67К, работает в режиме кольцевого счетчика.

Второй блок ввода 8 (К г) работает аналогично. В регистры 65К(К 1, г) при / 0 предварительно записываются соответствующие коэффициечты aL.

На вход 63 подаются единичные управляющие сигналы а в моменты О, Q, 2Q

(т-1)0, которые открывают элемент И 68 и в эти же моменты времени на выход 69 подаются соответствующие коэффициенты

(фиг.6).

Третий блок ввода 9 работает следующим образом (фиг.7). На входы 70i(i 1,Р) подаются соответствующие элементы хрч входной матрицы X в моменты времени t ( одновременно подаются элементы q-ro столбца матрицы X), которые задерживаются элементами задержки 711 на (Р-1) тактов и подаются на соответствующие выходы 73i. Организация элементов входной матрицы X на выходе блока ввода 9 приведена на фиг.2.

Рассмотрим работу устройства для 1 Т Р О 3 (фиг.2). Входной и выходной поток данных приведен на фиг.2 и 3, где в обозначении а1 индекс t указывает номер такта работы устройства. На вход 2 постоянно подается нулевое значение. Рассмотрим работу устройства при формировании элемента Yn. На нулевом такте на вход 1з устройства и вход 36 операционного блока 11з подаются соответственно элементы Х22 и ад0, на входы Зз и 34 - единичные сигналы. В операционный блок 11з в регистры 41 и 44 записываеются соответственно элементы адз° и Х22 Ь(0,2,0). На первом такте на вход 1з подается Х21, на входы Зз и 34 - соответственно единичный и нулевой сигналы. В операционном блоке 11з формируется значение Ь(0,2,1) Ь(0,2,0) шз° + +Х21. На втором такте f а вход 1з подается элемент Х20, на входы Зз и 34 - соответственно единичный и нулевой сигналы. В операционном блоке 11з формируется значение boa Ь(0,2,2) Ь(0,2,1) шз° + Х20, которое подается на третий информационный вход 15 оперативного блока Юз. На третьем такте на вход 13 операционного блока Юз подается элемент ад2 . В операционном

блоке Юз Формируется значение У(2ДО) Y(2,0,-1) + Ьоз. которое подается на вход 14 операционного блока Юз. На четвертом такте в операционном блоке 1Оа формируется значение Y(2,0,1) Y(2,0.0) УЗ + +boi. кото- рое подается на вход 14 операционного блока 10i. На пятом такте в операционном блоке 10i формируется значение Yao Y(2,0,2) - Y(2.0,1) ftJ32 + boo.

Аналогичным образом формируются ос- тальные элементы YIJ. Время вычисления двумерного ДПФ предлагаемым устройством составляет -т+ Р + Q - 2 тактов, а при равно N2 + 2N - 2 тактов. Например, для N 3 устройство pea- лизует вычисление двумерного ДПФ за 13 тактов.

Формула изобретения Устройство для вычисления двумерного дискретного преобразования Фурье, содержащее Р операционных блоков первого типа, где Р - размерность входной матрицы X P,Q, и Р операционных блоков второго типа, причем операционный блок первого ти- па содержит два регистра, умножитель и сумматор, а операционный блок второго типа - регистр, умножитель и сумматор, о т - личающееся тем, что, с целью сокращения объема оборудования, оно содержит три блока ввода, каждый операционный блок первого типа содержит узел задержки, две группы элементов И, группу элементов ИЛИ, два триггера, элемент И и элемент НЕ, каждый операционный блок второго типа - узел задержки, регистр, два триггера, четыре группы элементов И, две группы элементов ИЛИ, элемент И и элемент НЕ, причем первый и второй тактовые входы устройства подключены соответственно к первому и второму тактовым входам первого и второго блоков ввода, выходы которых подключены соответственно к первым информационным входам Р - х операционных блоков первого и второго типа, информационный вход уст- ройства подключен к второму информационному входу Р-го операционного блока первого типа, первый и второй тактовые входы группы устройства - соответственно к первому и второму тактовым входам Р-го операционного блока первого типа, третий и четвертый тактовые входы группы устройства - соответственно к первому и второму тактовым входам Р-го операционного блока второго типа, 1-й вход группы информацион- ных входов устройства подключен к i-му информационному входу третьего блока ввода, 1-й выход котарого подключен к второму информационному входу 1-го операционного блока второго типа, синхровход устройства подключен к синхровходам всех операционных блоков первого и второго типа устройства, первый и второй информационные входы j-ro операционного блока первого типа (J - 1.Р-1) подключены соответственно к первому и второму информационным выходам 0+1)го операционного блока первого типа, первый информационный вход j-ro операционного блока второго типа подключен к первому информационному входу (j+1)-ro операционного блока второго типа, первый и второй тактовые входы 1-го операционного блока первого типа (I 1.P-1) подключены соответственно к первому и второму тактовым входам (i+1)-ro операционного блока первого типа, первый и второй тактовые входы 1-го операционного блока второго типа (I 1.P-1) подключены соответственно к первому и второму тактовым выходам (1+1}-го операционного блока второго типа, второй информационный выход 1-го операционного блока второго типа подключен к третьему информационному входу 1-го операционного блока первого типа, второй информационный выход первого операционного блока первого типа подключен к выходу устройства, причем в операционном блоке первого типа первый информационный вход подключен к первым входам элементов И первой группы, вторые входы которых соединены с информационным входом первого триггера и подключены к первому управляющему входу операционного блока первого типа, а выходы элементов И первой группы соответственно подключены к первым входам элементов ИЛИ группы, вторые входы которых подключены к выходам соответствующих элементов И второй группы, а выходы - к соответствующим информационным входам узла задержки, первый информационный выход которого подключен к первому входу умножителя и к первому информационному выходу операционного блока первого типа, а второй информационный выход - к первым входам элементов И второй группы, вторые входы которых подключены к выходу элемента НЕ, вход которого подключен к первому тактовому входу операционного блока первого типа, второй информационный вход которого подключен к информационному входу первого регистра, выход которого подключен к второму входу умножителя, выход которого подключен к первому входу сумматора, выход которого подключен к второму информационному выходу операционного блока первого типа, третий информационный вход которого подключен к информационному входу второго

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

i

м

i.

О

°зц

Gr Т1

--( М

3

эц°

О

LAAA

о.

X

&

Э1

,s

If

7 J

Is

A

i °

1

1J

со

Si ч :л

«Ji SJ

Я 31

J

J