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

3

Фиг i

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

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

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

lN,Nj3 N, N2° ,N

где Хц, lii N векторы размер ., г, „.J-. ..

ностью N W XI, составленные из столб1 4цов соответственно матриц X

т.е.

N,,Nj

i 0. N, -К j О, N -Л, k iO, N,N, - 1. Второй этап:

i дп - 1.

5.л

X D - X

Nl.N2N,.NIN,,Ni

xU (i,©F,®i,;,, )-x«%,i.,,.,

где D,, -{A,,} (a, } ;

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

DA© lN,NaU Аналогично на всех первых бп этапах происходят вычисления только по столбцам матрицы промежуточных данных Xj , при этом каждая базовая операция соответствует обычной бабочке вида

Х, Х, + Xj Х - . Далее ь п-й этап:

Изобретение относится к цифровой обработке сигналов и может быть использовано для спектрального анализа и фильтрации изображений. Цель изобретения - расширение области примыкания за счет вычисления преобразований с произвольным соотношением первой и второй размерностей преобразования. Поставленная цель достигается за счет того, что в состав устройства входят блок памяти 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 ил. о б (Л

X

Nrja

(., .X. a,v

v - Y YY Лт

N,-i.i o,vi,,Na- N,--i,r4,-i) , (аналогично определяется вектор

F

NA

На основе свойства кронекеровского зо произведения

i ПВ )

i-1

матрица Р 1 - может быть записана

iв виде быстрого алгоритма вида

iHI

: « Д (IM, ® F,® )@ I (iNiiiJ®F ®i.-,)Mi:(DN iii-iJs i i.

X (.,®,,., )1 « nj( (X)

I ® N,( 2 - -) (,,

,. 2)

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

Первый этап: i лп

X- D

N,N2N,NI

N,Nj Xl

N,N

(F,®i«,,) .

ЬЬ + 1

где - знак поточечного произведения 55 .д D { (

UerPrktJTf . Iи

матриц;

jun+1 - k-й диагональный э

NiNl

г1 т1rt М ИС1ЛО«1МГ1 J

{ .j} I к J .® К матрицы весовык коэффициентов

k-й диагональный элемент матр ицы весовых коэффициентов (Dj( . );

(D,

Ч(.

5

i 1

лп

о

N,«7

уйИ

N,,N,

t

N,,N4

где 0

D

ль

N.HO

/

NI.N.I

(,ah)JC

N

.75 ) f

N,,N4

ah - k-й диагональный элемент

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

(Djbn ® N,N11 ч )

Начиная с Сьп+О-го этапа, вычисления выполняются одновременно и по 5 столбцам , и по строкам. В этом случае базовая операдия производится уже над четырьмя членами промежуточных данных

X, - X, + + W

Хп X, - + W Xj - x.l

г. 1 в г т l тг

X, + W tKi- - wT Xv; : X, - w Xa - w VXj + .

45

Для этапов L дтг, n имеем из (2) порядок вычислений an + 1,

0

j n j этап:

X

&h + i N,Nj

&h+i

X N,NI ;

uh + 1

N,N2 («1 + 1

ЬЬ + 1

X

X . (Fj® I

N,NI 1«,

N717 V

Iи

jun+1 - k-й диагональный элемент

ИС1ЛО«1МГ1 J

ицы весовык коэффициентов

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

(D,

Ч(.

Окончательно п,-й этап: j - 1.

Y У

N,.NI N,.N, N,N2

n,-i

t,N,

. «1

if.;, «««® «) N;,N,.,if ,

jj«i - lc-й диагональный элемент матрицы весовых коэффициентов (D X D).

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

N,N 4 ьп

(3)

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

Ь W

«Ll-

2n -ь 2„ и составляет

gi- - 0,75 т 1

;У

зависимости от соотношений яр п . (максимальный выигрыш по чис

в

и

лу умножений получается в случае

квадратного ДПФ, т.е. N « Nj).

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

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

тов) остаются неизменными.

На фиг. 1 изображена структурная |схема устройства (пример выполнения jIflJM случая N , . N, N I j на :фиг 2 - структурная схема арифмети S.

JXi,i - Х,.; ,.-, |Х4..;- W-iX-.H-i;.

- X,,i,, j -

Tw exp(,),

i -

на первых 4 n - п., этапах вычис лений и базовую операцию вида

5

0

5

°

5

Q

5

ческого блока; на фиг, 3 - временные диаграммы работы устройства.

Устройство двумерного быстрого преобразования Фурье (фиг. 1) содержит блок 1 оперативной памяти, арифметический блок 2, блок 3 постоянной памяти, коммутатор 4 строк и коммутатор 5 столбцов, регистр 6 сдвига строк и регистр 7 сдвига столбцов, счетчик 8 строк и счетчик 9 столбцов, реверсивные счетчики 10,и 11, триггеры 12-16, генератор 17 тактовых импульсов (ГТИ), коммутаторы 18 и 19, элемент И 20, триггер 21, второй элемент И 22, счетчик 23, элементы И 24 и 25, регистры 26 и 27 сдвига, сумматор 28. Арифтический блок (фиг. 2) состоит из умножителя 29 комплексных чисел, узла 30 буферной памяти, накапливающего сумматора-вычитателя 31, ключа 32, регистров 33 и 34 знака, элемента И 35, ключа 36.

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

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

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

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

Арифметический блок устройства вычисляет базовую операцию вида

r, 0. N, 1 r - 0, 1 .

(4)

L - 0, N,/2-1 ;

X. . X

C5)

.. X,,, + ,,«-,.+ ,,j.-i-.n + ,г-,п

/,K-,j X,,i - W - .x..-i H- .,,, .K-,..,,,, ; х. 4j - ,.,K-,.- w .x,.;,,, w i..,-- i-vu , J4.5 - -bb - ..jKHj- W X.,.,-ah+ .,K-i j jK-i-n ;

i 2% +4,; r, 0, NJ r m,

2

K-ib

j + p 0, N. p, 0, 1; m,, p N,/2

t -tVh-i

на остальных этапах вычислений где На данном этапе имеет К 1.и, k йп(т,е.,п,). следовательно, при любом (из формулы,

(4)), тогда 1 , отсюда в apHtJweРассмотрим процесс вычислений на 15 тическом блоке выполняются операции первом этапе.вида

X ;,

,J X.i+ X,,,j;

i

у .

i-t-ijj

.l-t-1

+ X.

X.

i,j-vi

I + 1, j + 1 i+rj+i

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

и X.,, Запись в узел 30 йуфер- VV - -

o.t

ной памяти происходит по адресу с выхода счетчика 23, который на первы 16 тактах ГТШ 17 имеет последов атель HjTo адресацию (фиг, 3, Х3(1, ) или

C5)

t -tVh-i

2r, +

0, N,/2-1; 0;

j 2L; L 0, N-/2-1

5

5

0

0

55

45

50

Х3(йп, п,), Кроме того, на первых и . далее всех нечетных 16 тактах ГТИ 17 происходит формирование адресов блока 3 постоянной памяти для считывания соответствующих весовых коэффициентов W , Для.формирования данных адресов используются элементы И 23 и 24, регистр 26 сдвига на dn, сумматор 11 и регистр 27 сдвига. На первых лп этапах элемент И 24 закрыт нулевым сигналом с выхода регистра 6 сдвига строк и, следовательно, на первыхьп этапах происходит формирование адрег сов весовых коэффициентов только по строкам. Регистр 27 сдвига сдвигает результат суммы с выхода.сумматора 28 на п , - К разрядов влево, где К - номер этапа, подаваемый на регистр 27 сдвига с выхода регистра 6 этапа строк. При этом все разряды, уходя- , щие при сдвиге за разрядную сетку, теряются, что соответствует вычислению адреса весового коэффициента по модулю N, , Если на выходе регистра 27 сдвига образуется нулевой код, то сигнал О по шине Х5 переключает ключ 36 в ари(етическрм блоке 2 на другой выход и операнд X. передается в узел 30 буферной памяти, ии- нуя умножитель 29, что ускоряет время вычислений.

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

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

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

Х,о 0.0 - ,, Хо., Х,,

X X. - X. : IX X..- X

1,о 0.0 - .о 1,1 О. ч, Умножения на W не происходит, так как в данном случае адрес весового коэффициента для операндов Х о i постоянно нулевой, так как кроме элемента И 24 закрыт элемент И 25 нулевым сигналом по входу подаваемого с выхода делителя 14-16 на 8 (фиг.З, D8) . Для операндов X j и X,, адрес имеется (так как элемент И 25 открыт), но он нулевой (код счетчика 8 строк равен 0),

Из выражения (4) видно, что на

первых an этапах в накапливающий сум- 25 чика 10 на один такт, уменьшая его

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

30

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

При этом соблюдается правильный поря-35 после переключения код равен 00...00,

40

док считывания операндов из узла 30 буферной памяти в накапливающий сумматор-вычитатель 31. Одновременно со слагаемыми в накапливающий сумма- тор-вычитатеЛь 31 с выхода регистров 33 и 34 знака поступает знак операции + или - (сложение или вычитание). На первых этапах регистр 34 знака закрыт элементом И 35 и ключ 32 передает сигнал по выходу 2, В этом случае выполняется базовая операция. |Сигнал Х7, подаваемый в накапливающий iсумматор-вычитатель 31 с выхода дели- теля импульсов 15, 16 на 4 (фиг.З, о4), осуществляет очистку сумматора 50 после конца выполнения полной операции сложения. Одновременно после конца операции сложения результат с выхода накапливающего сумматора-вычи- тателя 31 по шине Y1 передается на вход записи блока 1 oneparjiSHoft памяти и записывается в него по тем же адресам, по которым происходило счи55

следующим состоянием счетчика 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, т.е. операндов Х,; Х ; 2,1 Xj., , которые, последовательно проходя через умножитель 29 комплексных чисел или минуя его в случае нулевого кода на выходе регистра 27 сдвига, записываются в узел 30 буферной памяти.

На четвертых 16 тактах выполняет-

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

ки08ДА28

тывяние в первых 16 тактах. Это обеспечивается повторением управляющих сигналов на входах коммутаторов А и 5 (фиг. 3, D8 и D16) при неизменном состоянии счетчика 8 строк и счетчика 9 столбцов.

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

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

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

после переключения код равен 00...00,

0

0

5

следующим состоянием счетчика 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, т.е. операндов Х,; Х ; 2,1 Xj., , которые, последовательно проходя через умножитель 29 комплексных чисел или минуя его в случае нулевого кода на выходе регистра 27 сдвига, записываются в узел 30 буферной памяти.

На четвертых 16 тактах выполняет-

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

jX,o X о + X,j,; J X

0 7,0 3,0 Э,1

Q., i.

г., - X,,

После второй итерации (4«16 тактов ПИ 17) первого этапа происходит переброс счётчика 8 строк по принципу, аналогичному на первой итерации: код строки код строки + 1 -( код этапа 00...0010 + 00...01 + 00... 01 00...О100 4, и далее на каждый i-й HTepaipiH первого этапа счетчик 8 строк увеличивает код на 2 (00...010)

Код счетчика столбцов не изменяется до тех пор, пока счетчик В строк не наберет код N (конец последней строки), тогда в начале следующей итерации отрицательный перепад п-го старшего разряда счетчика 8 строк перебрасьшает (по тактовому входу) счетчик 9 столбцов в следующее состояние. Следующее состояние счетчика 9 столбцов определяется аналогично счетчику 8 строк, т.е. код счетчика 9 столбцов при следующем тактовом им пульсе равен:

код счетчика 9 код предыдущего такта + 1, если код реверсивного счетчика 11 О первый вариант);

код счетчика 9 код предыдущего этапа + 1 + код номера этапа по столбцам, если код реверсивного счетчика 11 О (второй вариант).

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

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

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

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

{Х..г-.Х.,,,, fX,, .Х,Х.,,,;, Чод-Х.д ,.,МХи,ГХ.з-Хигз.

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

г 0 5

о

5

Q

0

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

Ft,N,-7 i.Ki-a X,i,N2-a .Nj- f UI.NI-Q;

. i,Ni-l ,Nг-1 , Y Y - Y . - iNi-l ,Na-i .

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

Началом второго (и каждого следующего) этапа вычислений является переход счетчиков 8 и 9 иэ состояний 11... 11 в состояние 00...О, при этом задним фронтом импульса старшего n,j-ro разряда счетчика 9 столбцов происходит сдвиг (по тактовому входу) регистров 6 и 7 сдвигов на один разряд влево каждь1й. Причем на первых лп этапах срабатывает только регистр 6 сдвига строк, так как регистр 7 и сдвига столбцов закрыт до появления сигнала разрешения.

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

,1

В начале второго этапа исходный код счетчика 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, т.е.

. ..,4x,.,, x,,,.,.,,,,

rj.N,l5

,.7.Г ЧГ W U..i .,Г Х.Г W

i Дг, -I- r,; r, 0, N,/4-1; r, 0,1;

j 2L;

L 0,

Аналогичным образом продолжаются вычисления на всех ьп этапах. На . (лп + 1)-м этапе (и всех последующих) меняется вид базовой операции, В начале ( ьп-|-1)-го этапа регистр 6 сдвига строк находится в состоянии 0...100...0 (1 найп-«-1)-й позиции). С выхода 2 регистра 6 сдвига строк поступает (до конца п -го этапа) сиг нал разрешения на входы регистра 7 сдвига столбцов, элемента И 24, триггер 21, ключ 32 и элемент И 35. Состояние регистра 7 сдвига столбцов остается неизменным 00...01, поэтому режим переключения счетчика 9 столбцов и адреса с выхода коммутатора 5 столбцов остается таким же, как и на первых &п этапах. В реверсивный счетчик 10 записываел;ся код (лп+1)-го этапа, отсюда режим переключения счетчика 8 строк следующий: .

код счетчика 8 0,1 ,;2,... ,2 -1 (смена режима - 1 од счетчика 10 0),

-f 2 2 + + 13 2 i

1,.«..| о

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

uh-t

0), 3-2 +

+ 2

- 1.

uh+1 n.-лп+Г

В этом случае код адреса номера строки на выходе коммутатора 4 строк равен

п Ьм-1 Код адреса номера строки 0,2 ,

1 оДп-1 . 1 2 1 2 - 1,2 + 1.

- 1 (смена режима), 2

п &tv-i 2

+ 1, 1,...

. 2 ль-1 . 2 йь41 4 ...,J 1

(смена режима), , 5-2 V о г, о ч 1

ч..., ,

На (лп+1)-м этапе выполняется базовая операция вида

JjN,-.

+7 j + 1

м i,,..,,..., W Х,.,-.

Х-,,.- «Х. - ,,... Х.., - - ,лп,,,

х,..ч, . . - АГ - .Ahj,

п Xuo-...- Х,; - W Х., X.i,. +

. .i ,.a ., ,

.J+1

,ЛП+

где i -ь г,; г, ° 0. N,/2° -1; J 21; L О, N /2-1;

д«

Г, о, 2 т, r,N /2

ah+1

5

О

5

0

5

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

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

Вторые 16 тактов первой итерации (ап+1)-го этапа обеспечивают выполнение базовой операции. В этом случае триггер 21 заперт единичным сигналом по входу и счетчик 23 набирает последовательный код адреса, обеспечивая этим последовательное считывание операндов (фиг. 3, Х3(&п,п)) с узла 30 буферной памяти в накапливающий сумматор-вычитатель 31. Одновременно в него подается код операции с выхода ;регистра 33 знака. При этом ключ 32 находится в положении 1 и за 16 так10

15

20

25

30

NC

no строкам W

N,

N, W

2

определены no модулю exp(-j--i). Так как N, /N

.. N

r-ff

, o W N соответствует сдвигу кода показателя степени на дп разрядов влево. Разряды, выходящие за предел разрядной сетки, не нужны, так как W „

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

35

40

45

131408 А 4 2

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

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

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

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

X: . X. ,J ,.) гли .

+ W

+ w

,9j

(,j ч-Мэ

Иг17 .

1 + N,17 j

,J i, W

- ,,K,j- w %

X,

-V N.

l.i HjIl

Л I ii.l 1л Л-.

,i +N«119. I j

+ w

.J

,l2,ji-N,,l

N,1 4,j

T. Y

,H,i

-1; j „;

m

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

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

писан

ного сигнала X

,.N:

Формула

.HI

3 о

бретени

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

на управляющий вход регистра 27 сдан- 50 вому информационному входу первого

га с выхода регистра 6 сдвига строк. На последнем п -м этапе вычислений в регистрах 6 и 7 сдвига строк и столбцов записаны коды 10...00 (соответственно 1 в регистре 6 на

на п -м

п ,-м разразряде, в регистре 7 ряде). Базовая операция на последнем

этапе имеет вид

w

,9j

(,j ч-Мэ (2

Иг17 .

,J W

- ,,K,j- w %

X,

-V N.

l.i HjIl

Л I ii.l 1л Л-.

,i +N«119. I j

+ w

.J

,l2,ji-N,,lu

N,1 4,j

T. Y

,H,,

-1; j „;

m

7

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

В блоке 1 оперативной памяти за

спектр (N к N Y от входписан

ного сигнала X

,.N:

Формула

.HI

3 о

бретения

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

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

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

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

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

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

ае. 2

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

Л

У1

Х6

Т7

jL

32

7г:

35

5 § J

«

5

5

5§ :S5 5 81

J

JS

«а

« «

& 2: 5 1 «ц Ц еч

S