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

 

Изобретение относится к цифровой обработке сигналов и может быть использовано для спектрального анализа и фильтрации изображений. Цель изобретения - расширение области примыкания за счет вычисления преобразований с произвольным соотношением первой и второй размерностей преобразования . Поставленная цель достигается за счет того, что в состав устройства входят блок памяти 1, арифметической блок 2, блок постоянной памяти 3, коммутаторы 4, 5, регистр сдвига строк 6, регистр сдвига столбцов 7, счетчик строк 8 и счетчик столбцов 9, реверсивные счетчики 10, 11, триггеры 12-15, генератор тактовых импульсов 17, коммутаторы 18, 19, элемент И 20, триггер 21, элемент И 22, счетчик 23, элементы И 24, 25, регистры сдвига 26, 27, сумматор 28. 1 з.п. ф-лы, 3 ил. о б (Л

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИК (19) (Н) А1

UD 4 06 F 5 332

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

К А BTOPCKOIVIY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4160988/24-24 (22) 15. 12. 86 (46) 07.07. 88. Бюл. И 25

{71) Одесский политехнический институт

{72) В.А.Власенко и Ю.N.Ëàïïà (53) 68!.32(088.8) (56) Авторское свидетельство СССР

У 1164730, кл. G 06 F 15/332, 1985.

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

9 114284), кл. G 06 F 15/332, 1985. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ДВУ. МЕРНОГО БЫСТРОГО ПРЕОБРАЗОВАНИЯ

ФУРЬЕ (57) Изобретение относится к цифровой обработке сигналов и может быть использовано для спектрального анализа и фильтрации изображений. Цель изобретения — расширение области примыкания за счет вычисления преобразова" ний с произвольным соотношением первой н второй размерностей преобразования. Поставленная цель достигается за счет того, что в состав устройства входят блок памяти 1, арифиетической блок 2, блок постоянной памяти 3, коммутаторы 4, 5, регистр сдвига строк 6, регистр сдвига столбцов 7, счетчик строк 8 и счетчик столбцов

9, реверсивные счетчики 10, 11, триггеры 12-15, генератор тактовых импульсов 17, коммутаторы 18, 19, элемент И 20, триггер 21, элемент И 22, счетчик 23, элементы И 24, 25, регистры сдвига 26, 27, сумматор 28.

1 з.п. ф-лы, 3 ил.

408442 г =О И -1,j=D,N T,kО, N,N, — 1.

Второй этап:

=dn-1.

5 ,л

)P D> м Х

Н11N2 Й1.И2 Nt tN2 д2 — k-Й диагональный элемент

K матрицы весовых коэффициентов

4 0 111й21Л )

Аналогично на всех первых 6п этапах происходят вычисления только по столбцам матрицы промежуточных данных 1 „, при этом каждая базовая

2 операция соответствует обычной бабочке вида

Х. Х +Wxeit

Х - "Х вЂ” W2X

Далее a n-й этап: — 1

ДП Д1

X«В„„

112 с 2

2 1

ДП Х„„,. I„<<

Дд1 - k-й диагональный элемент к матрицы весовых коэффициентов

@2Ь11 3 IN>N2 2Д11 )

Начиная с (оп+1)-го этапа, вычисления выполняются одновременно и по столбцам; и по строкам. В этом случае базовая операция производится уже над четырьмя членами промежуточных данных где Х„,„и Y „- векторы размерt 41 ° 2 ностью И М Х1, составленные из столб1 цов соответственно матриц Х и

7, т.е.

1> и

Х 1 (Х 1 Х1 ОХ20 ° ° XN 1ОХ Х Х (аналогично определяется вектор к„„). н, н н к

АХд

N1.К2

На основе свойства кронекеровского произведения матрица F N "2 может быть записана в виде быстрого алгоритма вида

j12

* Г1 ((IN12 9 Г g I2 -1)®

t N,В2)

М1 2 2 х (?,„ О Р ®1 -1)) K.((DN12i-t,Э1-. х м2 2 2, й1

® I N 2tttT-t+1) (D2 1 111®Т,„2Д11- 1+1 ®

О 1„3 (С1 „00„). (2) f.

ХХ3

3 з

W Х2 W X3

2 7 3 — W" Х вЂ” ЫЪХ

"з

+ы х — W X

g e.

У, э.Х„..

+ W X

Х, Х х -х, Х - Х

Х4-Х1

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

Цель изобретения — расширение области применения за счет вычисления преобразования с произвольным соотношением первой и второй размерностей преобразования.

В устройстве используется совмещенный быстрый алгоритм вычисления двумерного ДПФ И ХИ, основанный на

1 следующей формуле вычислений:

1 2

2 2

На основе (2) получаем поэтапно следующую процедуру вычислений.

Для этапов Ь дп, п1 ИМЕЕМ ИЗ (2) порядок вычислений an + 1.

Первый этап:

an где * — знак поточечного произведения матриц; н (б .) 1 д„ где д

k-й дйагональййй элемент матрицы весовых коэфф"ц"ентов @2®IN „12 );

1 2

М2

Х

Зй к,м, Н,N2 N. N2 н12 НН н2 ° и этап:

Д11 1" t ah++1 Д ah

Х D * Х

50 н,в,, N,N2 * N1N2

1 х Х (Р2® Т И2у2), дд + - k-й диагональный элемент матрицы весовых коэффициентов

1408442 с 32 N< N N

W m mи --1 — — + hn -л-Л ч Ф 4 2 и 2+ 2п — — — — N N

4 (3) с

W 2 + 2 и составляет

Ч 22Е

11 с . — -. 0 75 - 1

Э °

/У

i2ã, +г, г, 0 N/2"-!у г20, 2" — 1 (4) х ° -х +w х;,-- .;, . ° ь) Ill 2гй гЯ

Хе у" X - W

i+2.,4

, W в ехр (-j 27

1 на первых аn n — и этапах вычис лений и базовую операцию вида ч 2

Окончательно п -й этап:

j м 1, 22, "22-2

Й Н !Ма л 2 tl q м, м (и21 Е ) м, м, (Тgggg)2

Д« — k-й диагональный элемент к матрицы весовых коэффициентов (D х х Р„ ), й

При описанном способе вычислений число операций умножения, требуемых для полного двумерного ДПФ, равно

Отсюда экономия в числе умножений . для данного способа вычислений по сравнению с построчно-столбцовым . равна г» в зависимости от соотношений и, и и (максимальный выигрыш по чис2.

: лу умножений получается в случае 35 квадратного ДПФ, т.е. N К ).

Другие характеристики эффективности ,вычислений (число сложений, объем оперативной памяти, объем постоянной памяти хранения весовых коэффициен- 40 тов) остаются неизменными.

Ка фиг. 1 изображена структурная

;:схема устройства (прнмер выполнения

% 45! фиг. 2 - структурная схема арифметического блока; на фиг. 3 — временные диаграммы работы устройства.

Устройство двумерного быстрого преобразования Фурье (фиг. !) содержит блок 1 оперативной памяти, арифметический блок 2, блок 3 постоянной памяти, коммутатор 4 строк и коммутатор 5 столбцов, регистр 6 сдвига строк и регистр 7 сдвига столбцов, счетчик 8 строк и счетчик 9 столбцов, реверсивные счетчики 10,и 11, триггеры 12-16, генератор 17 тактовых импульсов (ГТИ), коммутаторы 18 и 19, элемент

И 20, триггер 2 1, второй элемент И 22, счетчик 23, элементы И 24 и 25, регистры 26 и 27 сдвига, сумматор 28.

Арифтический блок (фиг. 2) состоит из умножителя 29 комплексных чисел, узла 30 буферной памяти, накапливающего сумматора-вычитателя 31, ключа

32, регистров 33 и 34 знака, элемента И 35, ключа 36.

Устройство работает следующим образом.

Исходный массив N, ° N з занесен в блок 1 оперативной памяти в двоичноинверсном порядке как по строкам, так и по столбцам.

В начальном состоянии счетчик 8 строк, счетчик 9 столбцов, а также счетчик 23 обнулены. В регистр 6 сдвига строк и регистр 7 сдвига столбцов записаны коды первого этапа 00" ...О1 аналогичные коды записаны в реверсивные счетчики 10 и 1.

На входы коммутаторов 4 и 5 поступают коды с выходов соответственно счетчика 8 строк и счетчика 9 столбцов, на другие входы - коды данных счетчиков плюс коды номеров этапов соответственно с выходов регистра 6 сдвига строк и регистра 7 сдвига столбцов, Арифметический блок устройства вычисляет базовую операцию вида

1408442

W Х;„к-г + W

1Ф 2 ° г

-чх - +

1+ Q ггпу

+ W X ° к1.-+2 2 VA1 + 1Tlg

Х,„.,- —. +W X

Pn +

1+,,г+ 2

W X "- "- W " Х <- (5)

1, l + Q (+2 г+ггК-1-ЬЬ

К-1-ЬЬ У 1 2 Х. К-1 к-1- М

foal 2 гг \ + гг

1,1+ 2 14-2 14+ 2

Х . Х + гj 1J

Ф г1-1-У X

1 jtg 1 J

На данном этапе имеет К = 1,и, следовательно, при любом (из формулы (4)), тогда W = 1, отсюда в арифмеIS тическом блоке выполняются операции вида X1j+ х4-1 3

В

1+г,.г г,,г 1+ г .г

2г, r, =0,N 21;

r 0 а

+ г °

Х

1,J+1

i+1, j+1

1, 14-1

1г3Ф1

j =2L;

+ Х.

i+1, j+!

l+1,J4- г

L-=0, И/2-1 — 25

Из приведенного выражения следует порядок адресации считывания-записи элементов Х;„ из блока 1 оперативной

1 памяти, Рассмотрим порядок адресации более подробно. Начальные состояния счетчика 8- строк и счетчика 9 столбцов нулевые. При этом на входы коммутаторов 4 и 5 поданы коды 00...00 строки и 00...00 столбца, на другие входы данных коммутаторов поданы эти же коды плюс коды с выхода регистра

6 сдвига строк (код 00...01). и ре" гистра 7 сдвига столбцов (код 00...

01). Таким образом, на вторые входы коммутаторов 4 и 5 подается в данном 40 случае одинаковый код 00...01. Записывая код строки и столбца через запятую, можно видеть, что на основании сигналов разрешения, поданных,на коммутаторы 4 и 5 соответственно с выходов триггеров на 8 и на 16 (фиг ° 3, D8 и D16), считывание из блока 1 оперативной памяти выполняется по адресам 0,0; 1,0; О, 1; 1, 1, т.е. за первые 16 тактов от ГТИ 17 происходит считывание из блока 1 оперативной памяти, умножение на весовые коэффициенты и запись в узел ЗО буферной па" мяти четырех операндов Х, Х, Х, и Х . Запись в узел 30 буфер1 1,1 ной памяти происходит по адресу с выхода счетчика 23, который на первых

16 тактах ГПИ 17 имеет последовательную agpeсацию (фиг. 3, X3(1, ап) или на остальных этапах вычислений, где

k> ап (т.е. 1с-ап+ 1, и,).

Рассмотрим процесс вычислений на первом этапе.

ХЗ(ап, п,) . Кроме того, на первых и далее всех нечетных 16 тактах ГТИ 17 происходит формирование адресов блока

3 постоянной памяти для считывания соответствующих весовых коэффициентов

W . Для формирования данных адресов используются элементы И 23 и 24, регистр 26 сдвига на ьп, сумматор 11 и регистр 27 сдвига. На первых ап этапах элемент И 24 закрыт нулевым сигналом с выхода регистра 6 сдвига строк и, следовательно, на первых п,п этапах происходит формирование адре сов весовых коэффициентов только по строкам. Регистр 27 сдвига сдвигает результат суммы с выхода. сумматора

28 на n, - К разрядов влево, где Кномер этапа, подаваемый на регистр

27 сдвига с выхода регистра 6 этапа строк. При этом все разряды, уходя-, щие при сдвиге за разрядную сетку, теряются, что соответствует вычислению адреса весового коэффициента по модулю N, . Если на выходе регистра 27 сдвига образуется нулевой код, то сигнал "0" по шине Х5 переключает ключ 36 в арифметическом блоке 2 на другой выход и операнд Х .переда1,г ется в узел 30 буферной памяти, ми- нуя умножитель 29, что ускоряет время вычислений.

Таким образом, после первых (н каждых нечетных) 16 тактов ГТИ 17 в узле 30 буферной памяти последова1408442

7 тельно записаны операнды X . .(1

11J

= О, 1; j = О, 1), умноженные на соответствующие весовые коэффициенты.

На вторых (.и каждых четных) 16 тактах ГТИ 17 происходит выполнение базоной операции. На первой итерации первого этапа выполняются операции с вида

О,0 -1.O q1 O,t

I с !

Умножения на И не происходит, так как в данном случае адрес весового коэффициента для операндов Х и Х . Ь,о

1 постоянно нулевой, так как кроме элемента И 24 закрыт элемент И 25 нулевым сигналом по входу подаваемого с выхода делителя !4-16 на 8 (фиг.3, D8). Для операндов Х „ и Х1, адрес имеется (так как элемент И 25 открыт), но он нулевой (код счетчика 8 строк равен О).

Иэ выражения (4) видно, что на первых бп этапах в накапливающий сум- 25 матор 31 необходимо сначала два раза считать операнды Х .. и Х;, (на

1,Д 3+1 4 первой итерации Х и Х, ), затем два раза считать операнды Х и

1 +1

Х<+» (на первой итерации Х, и

Х ). Отсюда следует, что на пер1,1 вых дп этапах адресация счетчика 23 на вторых (и каждых четных) 16 тактах ГТИ 17 должна быть равна О, 1, О, 1, 2, 3, 2, 3 (фиг. 3, ХЗ(1, дп).

При этом соблюдается правильный поря-35 док считывания операндов иэ узла 30 буферной памяти в накапливающий сумматор-вычитатель 31. Одновременно со слагаемыми в накапливающий сумма40 тор-вычитатель 31 с выхода регистров

33 и 34 знака поступает знак операции + или - (сложение или вычитание).

На первых этапах регистр 34 знака закрыт элементом И 35 и ключ 32 передает сигнал по выходу 2. В этом случае выполняется базовая операция.

,Сигнал Х7, подаваемый в накапливающий . сумматор-вычитатель 31 с выхода дели теля импульсов 15, 16 на 4 (фиг.3,,04), осуществляет очистку сумматора после конца выполнения полной операции сложения. Одновременно после конца операции сложения результат с выхода накапливающего сумматора-вычитателя 3f по шине 71 передается на 55 вход записи блока 1 операт юной памяти и записывается в него по тем же адресам, по которым происходило счи8 тывание в первых l6 тактах. Это oGecпечивается повторением управляющих сигналов на входах коммутаторов 4 и

5 (фиг. 3, D8 и D16) при неизменном состоянии счетчика 8 строк и счетчика 9 столбцов.

Таким образом, после вторых (и каждых четных) 16 тактов ГТИ 17 заканчиваются выполнение базовой операции и запись результата вычислений в блок 1 оперативной памяти. Полное выполнение первой (и каждой последующей) итерации осуществляется за

32 такта. !

На третьих 16 тактах ГТИ 17 начинается выполнение второй итерации первого этапа вычислений. При этом задним фронтом импульса с выхода триггеров 1 2-16 на 32 происходит переключение счетчика 8 строк в следующее состояние и реверсивного счетчика 10 на один такт, уменьшая его содержимое на единицу. Следующим состоянием счетчика 8 строк является код счетчика + 1, если после переключения код реверсивного счетчика

10 не равен О, или код счетчика + 1 +

+ код этапа, если после переключения код реверсивного счетчика 10 равен .О. В данном случае до переключения код реверсивного счетчика 1О равен коду первого этапа, т.е. 00...0f, после переключения код равен 00...00, следующим состоянием счетчика 8 строк является код + 1 + код этапа 00... .,00 + 00...01 + 00.. 01 = 00...010 =

2. При этом состояние счетчика столбцов на данной итерации не изменяется. В реверсивный счетчик 10 после индикации кода 00...00 опять записывается код этапа (в данном случае 00...01).

Таким образом, на третьих 16 тактах ГТИ 17 происходит считывание четырех операндов из блока 1 оперативной памяти уже по адресам 2,0; 3,0;

2,1; 3,1, т.е. операндов Х ; Х

Х,„; Х „, которые, последовательно ! проходя через умножитель 29 комплексных чисел или минуя его в случае нулевого кода на выходе регистра 27 сдвига, записываются в узел 30 буферной памяти.

На четвертых 16 тактах выполняет ся базовая операция вида (4) для указанных операндов, т.е.

9 1408442 1О

Хяо Xno+ Хаев Х 1= Xz, + Хз, ю

3,o k,o Ъ,о

После второй итерации (4 ° 1 6 т актов ГТИ 1 7 ) первого этапа происходит переброс счетчика 8 строк по принципу, аналогичному н а первой итерации : код строки к од строки + 1 + код этапа 00 . . . 00 1 0 + 00 . ° . 0 1 + 00 . . .

0 1 00 . . . 0 1 00 = 4, и далее н а каждый

i-й итерации первого этапа счетчик 8 строк увеличивает код н а 2 (00 . . . 0 1 0 ).

Код счетчика столбцов не изменяется до тех пор, пока счетчик 8 строк не набе рет код N (кон ец по следней

1 строки), тогда в начале следующей итерации отрицательный перепад n-ro ! старшего разряда счетчика 8 строк перебрасывает (по тактовому входу) счетчик 9 столбцов в следующее состояние, Следующее состояние счетчика

9 столбцов определяется аналогично ! счетчику 8 строк, т.е. код счетчика

9 столбцов при следующем тактовом импульсе равен: код счетчика 9 = код предыдущего такта + 1, если код реверсивного счетчика 11 Ф 0(первый вариант); код счетчика 9 = код предыдущего этапа + 1 + код номера этапа по столб-! ! . цам, если код реверсивного счетчика

11 0 (второй вариант) .

Код номера этапа по столбцам поступает с выхода регистра 7 сдвига столбцов и на первых ьп этапах равен

00. ° .01.

Исходя из определенного условия, после выполнения вычислений по всем строкам нулевого -и первого столбцов происходит переключение счетчика 9 столбцов по второму варианту, так как код реверсивного счетчика 11 после переключения равен О.

Отсюда, код счетчика 9 = 00... ,"00 + 00...01 + 00...01 = 2.

В этом случае на входы коммутатора 5 подаются соответственно коды

00...010 и 00.011, следовательно, на следующих итерациях первого этапа выполняются базовые операции вида с

Х "Х. +Х

1,%,2 >+,2 1э i ç 1э

Х. Х. - Х.; Х. Х - X. с+11 j2 a+ s2 i+i З q> i i3 °

Аналогичный процесс нычислений продолжается до конца первого этапа.

На последних итерациях первого этапа ныполняется базовая операция по пос-, ледним двум столбцам матрицы данных, хранящейся н блоке 1 оперативной памяти, т.е.!,м -2 1,й -g 1+1,Ng-1

Х=Х-Х.

10 1+,È -2 1,N -2 +1,\Ч -2; е Х + Х. хtH -1 t и i yll

1.% 1,149-1

Конец первого (и каждого следующего этапа) определяется по состоянию старшего и -го разряда счетчика

2.

9 столбцов.

Началом второго (и каждого следующего) этапа вычислений является переход счетчиков 8 и 9 из состояний

11.. ° 11 н состояние 00...0, при этом задним фронтом импульса старшего

n -ro разряда счетчика 9 столбцов

2 происходит сдвиг (по тактовому входу) регистров 6 и 7 сднигон. на один разряд влево каждый. Причем на первых ьп этапах срабатывает тОлько регистр

6 сдвига строк, так как регистр 7 сдвига столбцов закрыт до появления сигнала разрешения.

Таким образом, на втором этапе вычислений код регистра 7 сдвига столбцов остается прежним (00...01), а код регистра 6 сдвига строк станонится равным 00...010. В этом случае режим переключения счетчика 9 столбцов остается прежним, как и на первом этапе, а режим работы счетчика

8 строк несколько изменяется. .!

В начале второго этапа исходный код счетчика 8 строк равен 00...00, реверсивного счетчика 10 — 0...010.

После выполнения первой итерации реверсинный счетчик 10 переключается в код 00.01, который не равен О, отсюда счетчик 8 строк переключается на 1 и его код равен 00 ° . ° 01. После выполнения второй итерации реверсивный счетчик 10 переключается в код

00...00, отсюда счетчик 8 строк переключается на 1 + код этапа 00...

01 + 0...010 0...011 и его.код равен 0...0100 4.

Таким образом, на втором этапе вычислений выполняется базовая операция вида (4) при К 2, т.е.

1408442

М22 м,ЛХ !

+ ) q н,а

w х„,„;

W" Х

i4i2 )Ф! Э х.

),4

Х .+ х. +

1 j4.1

1 х. !

+2,j

i=4r) +r2, r, =О, N/41;

Г2 = 011;

2L;

Ь О, И /2-1.

Аналогичным образом продолжаются вычисления на всех ьп этапах. На . (a n + 1)-м этапе (и всех последующих) меняется вид базовой операции, В начале (aп+1) -ro этапа регистр 6 сдвига строк находится в состоянии

О... }00...0 (1 на ап+1)-й позиции).

С выхода 2 регистра 6 сдвига строк поступает (до конца и --го этапа) сиг1 нал разрешения на входы регистра 7 сдвига столбцов, элемента И 24, триггер 21, ключ 32 и элемент И 35. Состояние регистра 7 сдвига столбцов остается неизменным 00...01, поэтому

25 режим переключения счетчика 9 столбцов и адреса с выхода коммутатора 5 столбцов остается таким же, как и на первых an этапах. В реверсивный счетчик 10 записываешься код (4,п+1)-го 30 этапа, отсюда режим переключения счетчика 8 строк следующий: код счетчика 8 0,1,:2,...,2 — 1 (смена режима— код счетчика 10 35 е е0), 2411 1 + 24 - 2411

ah 1

+ 1,...., 3 2

1 (смена режима— код счетчика 10 40 1)

r =О 2 -1

2 I 1 ш=гй/2

2 1 4

ah-1

0), 32 +

+ 2a)1-1+ g4l1+

)1 -ah+1

+ 1,....,2

1. 45

Вторые 16 тактов первой итерации (an+1)-го этапа обеспечивают выполнение базовой операции. В этом случае триггер 21 заперт единичным сигналом по входу и счетчик 23 набирает последовательный код адреса, обеспечивая этим последовательное считывание операндов (фиг. 3, ХЗ(4п,n,)) с узла

30 буферной памяти в накапливающий сумматор-вычитатель 31. Одновременно в него подается код операции с выхода !

;регистра 33 знака. При этом ключ 32 находится в положении 1 и за 16 такВ этом случае код адреса номера строки на выходе коммутатора 4 строк равен

411

Код адреса номера строки 0,2

1,2 - + 11....,2 - 1,2 "1 (смена режима), 2

3 2 " 1 2 + 1,3 2 + 1, ° .

3 2 — 1,2 а"+ - 1 (смена режима), 2 +, 5 2,.,55

1-ad! 2 >w

На (an+1)-м этапе выполняется базовая операция вида 12 й)12 х. =х.-w х

i+2 )1 1,)+1 1 б2,J+!

Х;„=Х .+W Х. „,+Х.. +

1),) П)! Ф Q ) 1 f+) 1

+ и х .,6)

2 ",1, ))Ъ

Х. a) - Х.. — W Х- a)1. + Х..

i+2 1+2, j i,j+1

Х;„-Х +И Х а)1.-Х

1+% j i .)+

1! I

atl

)+2,,) 1

m, Х <" . " Х. — W Х 1,,- Х . +

1!2,j+1 1,) в," Х,;»

+ W Х1+2 j+1 ) 1

21; L=О, N 2-1;

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

31 а также регистров 33 и 34 знака.

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

30 буферной памяти. Порядок вычислений и временные диаграммы аналогичны описанным на предыдущих этапах.

13 14084 тов базовой операции происходит последовательный циклический сдвиг 16 знаков операций с завершением цикла на 16-м такте. Процесс записи результата базовой операции в блок 1 опера- тинной памяти происходит так же, как и на предьдущих этапах вычислений, по

4 тем же адресам, что и считывание.

На каждом следующем после (оп+1)го этапе вычислений происходит одновременный сдвиг на один разряд влево содержимого регистров 6 и 7 сдвигов строк и столбцов, индицирующих номер этапа.

Порядок адресации весовых коэффициентов, считываемых из блока 3 постоянной памяти, на (дп+1, n ) -ых этапах, определяется следующим образом.

На элементы И 24 и 25 подаются соответственно коды столбца и строки, по которым в данный момент считываются данные из блока 1 оперативной памяти. По сигналам разрешения с выхода этих элементов И код строки поступает непосредственно в сумматор 28, а код столбца сдвигается на дп разрядов влево с потерей старших разрядов при выходе их за пределы разрядной сетки. Это связано с тем, что в двумерном преобразовании Фурье весовые коэффициенты по столбцам W опЙ2 ределены по модулю N т. е. W

Nq . 2Г!.

= exp(-j — i), а весовые коэффициенты

N2 по строкам W определены по модулю .2Т

N — W = ехр(-j — i) . Так как N, /N =

It .. N1

1

= 2 ", то W„= W„, что соответ1 ствует сдвигу кода показателя степени на дп разрядов влево. Разряды, вы40 ходящие за предел разрядной сетки, не нужны, так как W 2 W

Я1 N1

С выхода сумматора 11 результат поступает в регистр 27 сдвига, где происходит сдвиг кода на К разрядов влево с потерей старших разрядов (по указанной причине), выходящих за пределы разрядной сетки, где К вЂ” номер этапа вычислений, который поступает на управляющий вход регистра 27 сдви- 50

ra с выхода регистра 6 сдвига строк, На последнем и -м этапе вычисле1 ний в регистрах 6 и 7 сдвига строк и столбцов записаны коды 10...00 (соответственно 1 в регистре 6 на n, — ì 55 разряде, в регистре 7 - на п -м разряде). Базовая операция на последнем этапе имеет вид

42

I4

+ W " х t W Х .. +

l t 13.

t,,t +> 191 1 j+M 2

1 1 Я

+ Ы i N I2,,1 9 12

Ill ) rтЪ1

Х;... „= Х,„- W Х,,„1,„+ W х .х Х,„- W "" Х, 1, 1.114г(т 1+ N 2 t.y I21

11

ГГ1

1

t, i+ N2. (2 1+ >tl2,>t <2I2 х

1+tt,1 2.,я1-111)2 I 1 1-1. м 1а,з

Ръ 2 + И

111 4-

1, +и (2 11.11, ф «1 121 й, где i =г ; г =О, N /2-1; j =р р = 01 N2/2 1; m = r2 m2= р

После окончания п -ro этапа ре1 гистры 6 и 7 сдвига строк и столбцов переходят в начальные состояния работы с кодом 00...01.

В блоке 1 оперативной памяти записан спектр (N x N ) Y от входного сигнала Х

N N

11 Н

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

1. Устройство для вычисления двумерного быстрого преобразования Фурье, содержащее сумматор, блок памяти, блок постоянной памяти и арифметический блок, выход которого подключен к информационному входу блока памяти, выход которого подключен к входу операндов арифметического блока, вход коэффициентов которого подключен к выходу блока постоянной памяти, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения за счет вычисления преобразования с произвольным соотношением первой и второй размерностей преобразования, в него введены четыре коммутатора, регистр сдвига строк, регистр сдвига столбцов, два регистра сдвига, четыре элемента И, шесть триггеров, счетчик, счетчик строк, счетчик столбцов, два реверсивных счетчика и генератор тактовых импульсов, выход которого подключен к первому информационному входу первого коммутатора и тактовому входу первого триггера, выход которого подключен к второму информационному входу первого коммутатора и тактовому входу второго триггера, выход которого подключен к первому входу второго коммутатора, входу синхронизации выдачи арифметического блока и такl5

1408442 !

ЗО

50

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

В выходу регистра сдвига строк, выходы первого и третьего элементов И подключены соответственно к второму входу сумматора и тактовому входу второ"

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

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

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

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

1408442

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

Л.Гратилло Техред А.Кравчук Корректор Л.Патай

Редактор

Заказ 3353/52

Тиос 704 Подписное

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

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

Производственно-полиграфическое предприятие, r, У город, ул. Проектная, 4