Процессор дискретного преобразования фурье

 

Изобретение относится к вычисли1- тельной технике и может быть использовано в специализированных системах обработки сигналов и изображений высокой производительности, выполняющих двумерное дискретное преобразование Фурье. Цель изобретения - повышение быстродействия. Это достигается за счет того, что в состав процессора входят группа регистров 3, процессорные элементы 5 первого типа, группа 8 регистров , процессорные элементы 9 второго типа. 3 ил.

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

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

РЕСПУБЛИН (g))5 С 06 Г 15/332

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

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

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

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

ПРИ ГКНТ СССР (21) 463601 7/24 (22) 12.01.89 (46) 15.03.91. Бюл, N - 10 (72) А.В.Демидов, А.И,Белоус, А.Н.Бондарь, В.Г.Гриневич, О.В,Подрубный, С.Г.Седухин и А.Н.Семашко (53) 681.32(088.8) (56) Системы параллельной обработки

/Под ред. lI.Èâåíñà. M. Мир, 1985, с. 350, рис ° 16.13.

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

;М 1363243, кл. G 06 F 15/332, 1987.

2 (54) ПРОЦЕССОР ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к вычислительной технике и может быть испольэовано в специализированных системах обработки сигналов и изображений высокой производительности, выполняющих двумерное дискретное преобразование Фурье. Цель изобретения — повышение быстродействия, Это достигается эа счет того, что в состав процессора входят группа регистров 3, процессорные элементы 5 первого типа, группа 8 регистров, ппоцессорные элементы 9 второго типа ° 3 ил.

1635195

Изобретение относится к вычислительной технике и может быть использовано в специализированных системах обработки сигналов и изображений высокой производительности, выполняю° щих двумерное дискретное преобразование Фурье (ДПФ).

Цель изобретения — повышение быстродействия процессора дискретного преобразования Фурье, На фиг. 1 представлена структурная схема процессора дискретного преобразования Фурье, на фиг. 2 — функциональная схема процессорного элемента первого типа; на фиг. 3 — то же, второго типа, Процессор (фиг,1) содержит первый информационный вход 1, группу входов

2 < — 2» первую группу п регистров

3, первую группу 4 процессорных элементов 5 первого типа, группу выходов 6 — 6„, первой группы, вторую группу регистров 7, вторую группу 8 процессорных элементов 9 второго типа, группу входов 10 < — 10„, ãðóïïó информационных выходов 11 „— I 1, и

П тактовый вход 12.

Процессорный элемент 5 (фиг. 2) содержит входы 13-14, регистры 15-17, умножитель 18, сумматор 19, мультиплексор 20, элемент НЕ 21 и выходы

22 и 23, Процессорный элемент 9 (фиг. 3) содержит входы 24-26, регистры 27-29, умножитель 30, сумматор 31 и выходы

32-34.

Процессор работает следующим образом.

Двумерное ДПФ матрицы входных отсчетов Х(п1, n<) = (ХК К ) сводится к произведению трех матрйц, т.е.

Y(n<, n )=g,(п,, n,) Х(п,, и ) х где в,k

Q, (n,,п,) =(Я, 3, 05 m,,k1«(п<-1, являются (n xn <) и (п у и ) матрицами коэффициентов ДПФ соответственно.

Произведение трех матриц можно свести к двум матричным умножениям

Y(n,nz) = Д,(п,,n<) t X(n<,п ) х х Qz(п,п )), (2)

Вычисление двумерного (n < х n<) — точечного ДПФ по формуле (2) сводится к п п -точечным ДПФ строк, а затем к п п -точечным ЛПФ столбцов, Вычисление выражения (2) положено в основу работы процессора дискретного преобразования Фурье.

Процессор реализует преобразование (2) следующим образом.

Процесс преобразования входных цанных состоит из двух этапов: этапа загрузки и этапа вычислений, На этапе загрузки тактовые сигналы, поступающие на тактовые входы элементов 5, запрещают прием информации в регистры 15 и 17 и одновременно разрешают прием и выдачу информации, поступающей с информационного входа 14 на регистр 16 и далее с выхода регистра 16 через мультиплексор 20 на выход 23 процессорного элемента.

Кроме того, на этапе загрузки разрешается прохождение информации, поступающей на группу входов 2 — 2п,процессора, через группу регистров 3 на группу входов первой группы 4 элементов 5.

Матрица входных отсчетов X(n,n ) подается на группу входов 2 < — 2 и ( процессора, причем на вход 2 подают( ся элементы нулевой строки Хд„ на ок вход 2 — элементы первой строки

X к, на 2„;й вход — элементы (n< — 1)-й строки Х, <, где 0 (k < n — 1. По

z тактовым сигналам элементы матрицы входных отсчетов Х продвигаются

1> 2

35 через регистры 3 процессора, регистры

16 и мультиплексоры 20 элементов 5 первой группы 4.

B конце этапа загрузки через (n -1) тактов элементы матрицы входных от40 счетов размещаются соответственно в регистрах 16 элементов 5 и в регистрах 3, причем в регистрах 3 размещаются элементы последнего (п -1)-ro столбца, а в регистрах 16 (i,n — 1)-х элементов 5 — элементы первого (нуле-. вого) столбца, На этом этап загрузки заканчивается и начинается этап вычислений, На этапе вычислений тактовыми сигналами, поступающими на тактовые входы элементов 50 разрешается запись информации с входов 13 и 14 на регистры 15 и 17 и одновременно прохождение информации с выхода сумматора 19

55 через вход мультиплексора 20 на выход 23 элемента 5. Кроме того, на этом этапе регистры 3 работают в режиме хранения и выдачи информации, а регистры 7 и регистры 27-29 элемен1635195 6

15

55 тов 9 — в режиме приема и выдачи информации, поступающей на информационные входы.

Вычисление п<п -точечных ДПФ в первой группе 4 элементов 5 можно представить как нахождение вспомогательной матрицы Z(n<, n<):

Z(n<,na) = Х(п i,ne) <,2 (пz nz), (3) В связи с тем, что матрица входных отсчетов загружена в первую группу 4 элементов 5 и в регистры 3, выражение (3) можно вычислить, используя тОлькО п значений Вектора сд (п ) (1,Я, Я, ...,...Я < ) ° Элементы вектора Я (и ) поступают на информационный вход 1 процессора и далее на вход группы 4 °

С входа группы 4 элементы вектора(д (и ) поступают на вход первого элемента 5 последней строки группы.

В свою очередь, на вход i-го (i = 1, п — 1) элемента 5 первого столбца группы 4 потактно поступают элементы вектора Я (п ) с первого выхода (i+1)-ro элемента 5. т

Каждый элемент 5 первой группы 4 на этапе вычислений реализует следующие функции (фиг. 2): (у)ьы = (у) ех

ebs ьх 0) ex + в.м где Х вЂ” содержание регистра 16 элемента 5 °

Элементы Я в поступают на вход 13 и на регистр 15 элемента 5, элемент

Z — на вход 14 и на регистр 17.

С выходов 22 и 23 выдаются соответственно элементыЯв,„и Z вы . вм

На входы первой группы 4 элементов 5 постоянно подаются и» элементов последнего столбца матрицы входных отсчетов, хранящихся в регистрах 3, Каждая строка элементов- 5 группы 4 осуществляет и -точечное ДПФ строки

2 матрицы входных отсчетов. Первый элемент Z n 4, вспомогательной матрицы

Z(n,n ) появляется на выходе элемента 5 и<-й строки группы 4 на (n -1)-м такте и подается для обработки на первый регистр 7 и далее на группу 8, в которой осуществляются

nzxn<-òo÷å÷nûõ ДПФ столбцов вспомогательной матрицы Z(nz,п ), На группу входов 10 < — 10„ процессора и, следоватепьно, на группу входов группы 8 элементов 9 постоянно т подаются весь этап вычислений элементы вектора 43, (n,) = (1, Я, Я, h<-1

1 р р т ° ° ° ° ф.

Я, ), причем на вход 10 подается

О первый элемент 43, = 1, на вход 10

5 второй элемент Я, и т.д.

Каждый элемент 9 группы 8 (фиг.3) реализует следующие функции: (0ьых = (") вх i

Zebix (= вх

1вых Ye,x +e,x + Zex> причем элементы У>< поступают íà вход

24 и на регистр 28 элемента, элемент (0 — на вход 25 и на регистр 27, элемент 7. ax — на вход 26 и на регистр 29.

С выходов 32, 33 и 34 выдаются соответственна элементы У ц„, Q Z gx.

АР

I(; ворот j стопрец (j = р, и -1т проиежуточной матрицы Z(n<,n ) потактно пое тупа ет на информационный вход первогn регистра 7 и на входы группы 8, начиная с Z „, ) -ro элемента. Проходя через строки элементов 9 группы 8, столбцы промежуточной матрицы Z(n<,п ) подвергаются ДПФ па второй координате. Ва i-м выходе группы 8 и, следовательно, на i-м выходе 11 (i = 1,n<) процессора формируются 1-я строка матрицы выходных отсчетов Y.

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

Процессор дискретного преобразования Фурье, содержащий первую группу из (п -1) -го процессорного элемента первого типа, первую группу из (n -1)—

ro процессорного элемента второго типа, первый регистр, причем выход первого регистра подключен к первому входу первого процессорного элемента первого типа первой группы, первый и второй выходы i-го (i = 1, n — 2) и процессорного элемента первого типа первой группы подключены соответстпенна к первому и второму входам (i + I)-го процессорного элемента первого типе первое группы первыт1 второй выводы 1-го (j = I, пе — 2) процессорного элемента второго типа первой группы подключены соответственна к первому и второму входам (j+1)-го процессорного элемента второго типа первой группы, выход (n —

1)-го процессорного элемента второго типа первой группы является первым информационным выходам процессора, первым информационным входом которого является информационный вход первого регистра, тактовый вход кото! 635,195 рого подключен к тактовому входу процессора, при этом процессорный элемент первого типа содержит первый и второй регистры, умножитель и сумматор, первый вход которого подключен к выходу умножителя, первый вход которого подключен к первому выходу первого регистра, информационный вход которого является первым входом процессорного элемента первого типа, вторым входом которого является информационный вход второго регистра, выход которого подключен к второму входу сумматора, второй выход первого регистра является первым выходом процессорного элемента первого типа, причем процессорный элемент второго типа содержит первый регистр, умножитель и сумматор, первый вход которого подключен к выходу умножителя, первый вход которого подключен к первому выходу первого регистра, информационный вход которого является первым входом процессорного элемента 25 второго типа, первым и вторым выходами которого являются соответственно второй выход первого регистра и выход сумматора, а тактовые входы первых регистров всех процессорных эле- ЗО ментов первого и второго типов подключены к тактовому входу процессора, отличающийся тем, что, с целью повышения быстродействия, в него введены п — 1 группа иэ n — процессорных элементов первого типа в каждой группе, n < — 1 группа из п — 1 процессорных элементов второ( го типа в каждой группе, первая группа иэ n < — 1 регистров и вторая груп- 4р па иэ п -го регистра, причем первый и второй выходы k-го (k = 2, п -2) процессорного элемента первого типа 1-й (1=2,п ) группы подключены соответственно к первому и второму входам (k+1)-ro 45 процессорного элемента первого типа

k-й группы, выход i-го (i = 1, n — 1) регистра первой группы подключен к первому входу первого процессорного элемента первого типа (i+1) é группы, первый выход которого подключен к второму входу первого процессорного элемента первого типа i-й группы, а второй вход первого процессорного элемента первого типа и -й группы является входом задания коэффициентов процессора, (i+1)-и информационным входом которого является информационный вход i-ro регистра первой группы, тактовый вход которого подключен к тактовому. входу процессора, входом задания )-ro (j = 1, и ) коэффициента группы которого является первый вход первого процессорного элемента второго типа 1-й группы, второй вход которого подключен к выходу j-го регистра второй группы, тактовый вход которого подключен к тактовому входу процессора, (1+1) м информационным выходом которого является первый, выход (и — 1)-го процессорного элеменI та второго типа (i+1)-й группы, первый и второй выходы i-ro процессорного элемента второго типа (i+1)-й группы подключены соответственно к первому и второму входам (i+1)-го процессорного элемента второго типа (i+1)-й группы, третий выход )"го процессорного элемента второго типа i-й группы подключен к третьему входу j-ro процессорного элемента второго типа (i+1)-й группы, выход i-ro регистра второй группы подключен к информационному входу (i+1) — го регистра второй группы, первый выход (п — 1)-ro процессорного элемента первого типа i-й группы подключен к третьему входу

Г

n — (i-2) -ro процессорного элемента второго типа первой группы, а первый выход (п -1)-ro процессорного

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

nephoro регистра второй группы„причем в процессорный элемент первого типа введены элемент НЕ, мультиплексор и третий регистр, выход которого подключен к второму входу умножителя, выход элемента НЕ подключен к тактовому входу второго регистра и управляющему входу мультиплексора, первый и второй информационные входы которого подключены соответственно к второму выходу второго регистра и выходу сумматора, выход мультиплексора является вторым выходом процессорного элемента первого типа, второй вход которого подключен к информационному входу третьего регистра, тактовые входы третьих регистров и входы элементов

НЕ всех процессорных. элементов первого типа подключены к тактовому входу процессора, при этом в процессорный элемент второго типа введены второй и третий регистры, выход второго регистра подключен к второму входу умножителя, а первый выход третьего регистра подключен к второму входу

1635195

I0 сумматора, информационные входы второго и третьего регистров являются соответственно вторым и третьим входами процессорного элемента второго типа, третьим выходом которого является второй выход третьего регистра, :; тактовые входы второго и третьего регистров всех процессорных элементов

5 второго типа подключены к тактовому входу процессора, 1635195

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

Техр ед А. Кравчук Корр ек тор М. Шароши

Редактор А.Лежнина

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

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

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

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