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

.И. Белоусиневич,Седухин Рработки 1985,ССР1987. ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР К А 8 ТОРСКОМУ СВИ(54) ПРОЦЕССОР ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ(57) Изобретение относится к вычислительной технике и может быть использовано в специализированных системах обработки сигналов и изображенийвысокой производительности, выполняющих двумерное дискретное преобразование Фурье, Цель изобретения - повышение быстродействия, Это достигается эа счет того, что в состав процессора входят группа регистров 3, процессорные элементы 5 первого типа,группа 8 регистров , процессорныеэлементы 9 второго типа3 ил.Изобретение относится к вычислительной технике и может быть использовано в специализированных системахобработки сигналов и изображений высокой производительности, выполняю щих двумерное дискретное преобразование Фурье (ДПФ).Цель изобретения - повышение быстродействия процессора дискретногопреобразования Фурье,На фиг, 1 представлена структурная схема процессора дискретного пре"образования Фурье, на фиг, 2 - функциональная схема процессорного элемента первого типа, на фиг. 3 - тоже, второго типа,Процессор (фиг,1) содержит первыйинформационный вход 1, группу входов2- 2, первую группу п регистров13, первую группу 4 процессорных элементов 5 первого типа, группу выходов 6 - б,первой группы, вторуюгруппу регистров 7, вторую группу 8процессорных элементов 9 второго типа, группу входов 10 1 - 10 группуинформационных выходов 11 - 11 итактовый вход 12.Процессорный элемент 5 (фиг. 2)содержит входы 13-14, регистры 15-17,умножитель 18, сумматор 19, мультиплексор 20, элемент НЕ 21 и выходы22 и 23,Процессорный элемент 9 (Фиг. 3)содержит входы 24-26, регистры 27-29,умножитель 30, сумматор 31 и выходы32-34.Процессор работает следующим образом.Двумерное ДПФ матрицы входных отсчетов Х(п 1, п) = (ХК К ) сводится к произведению трех матрйц, т.е.У(п, п)=Я,(п и,) Х(п и ) хгдев,М,Я, (п,п 1) =1 Ю 3, 06 ш,1 с 1( п,являются (и хп ) и (пи ) матрицами коэффициентов ДПФ соответственно,Произведение трех матриц можно свести к двум матричным умножениямУ(п пг) = Д (ии)Х(п 1 п) хх Яг (пг,пг ) Д, (2)Вычисление двумерного (их и ) - точечного ДПФ по Формуле (2) сводитсяк пп-точечным ДПФ строк, а затем к пп-точечным ЛПФ столбцов, Вычисление выражения (2) положено в основуработы процессора дискретного преобразования Фурье.Процессор реализует преобразование (2) следующим образом.Процесс преобразования входныхцанных состоит из двух этапов: этапазагрузки и этапа вычислений,На этапе загрузки тактовые сигналы, поступающие на тактовые входыэлементов 5, запрещают прием информации в регистры 15 и 17 и одновременно разрешают прием и выдачу информации, поступающей с информационноговхода 14 на регистр 16 и далее с выхода регистра 16 через мультиплексор 20на выход 23 процессорного элемента,Кроме того, на этапе загрузки разрешается прохождение информации, поступающей на группу входов 2- 2 я,процессора, через группу регистров 3 нагруппу входов первой группы 4 элемен 25 тов 5.Матрица входных отсчетов Х(п 1,п )подается на группу входов 2 - 2 и(процессора, причем на вход 2 подаются элементы нулевой строки Хо наОкгвход 2 а - элементы первой строкиХк, на 2;й вход - элементы (п 1 - 1)-йстроки Х, к , где 0 ( 1 с ( и - 1. Погфтактовым сигналам элементы матрицывходных отсчетов Хкпродвигаются1 г35через регистры 3 процессора, регистры16 и мультиплексоры 20 элементов 5первой группы 4,В конце этапа загрузки через (и -1)тактов элементы матрицы входных от 40 счетов размещаются соответственно врегистрах 16 элементов 5 и в регистрах 3, причем в регистрах 3 размещаются элементы последнего (п)-гостолбца, а в регистрах 16 (1,п - 1)-хэлементов 5 - элементы первого (нулевого) столбца, На этом этап загрузки заканчивается и начинается этапвычислений,На этапе вычислений тактовыми сигналами, поступающими на тактовые входы элементов 50 разрешается записьинформации с входов 13 и 14 на регистры 15 и 17 и одновременно прохождение информации с выхода сумматора 1955через вход мультиплексора 20 на выход 23 элемента 5, Кроме того, наэтом этапе регистры 3 работают в режиме хранения и выдачи информации, арегистры 7 и регистры 27-29 элемен 1635195 6тов 9 - в режиме приема и выдачи информации, поступающей на информационные входы,Вычисление пп -точечных ДПФ в первой группе 4 элементов 5 можно представить как нахождение вспомогательной матрицы 2(п п):2(п п) = Х(п 1 рп) 2 (п,пд) (3)В связи с тем, что матрица входныхотсчетов загружена в первую группу 4элементов 5 и в регистры 3, выражение (3) можно вычислить, используятолько п значений вектора Сд (п)(1 рИг, Ю,.,Я) . Элементывектора Я(п ) поступают ца информационный вход 1 процессора и далеена вход группы 4С входа группы 4 элементы вектора(д (и ) поступают на вход первогоэлемента 5 последней строки группы.В свою очередь, на вход ).-го (1 = 1,п - 1) элемента 5 первого столбцагруппы 4 потактно поступают элементывектора Я (п) с первого выхода(1+1)-го элемента 5,тКаждый элемент 5 первой группы 4на этапе вычислений реализует следующие функции (Фиг, 2):(цвых = (вх у2 вьх = 2 ьх Сд вх + Хвмгде Хв - содержание регистра 1 бэлемента 5Элементы Я в поступают на вход 13 и на регистр 15 элемента 5, элемент 2 , - на вход 14 и ца регистр 17.С выходов 22 и 23 выдаются соответственно элементы Гй)в,ц 2 выхвхНа входы первой группы 4 элементов 5 постоянно подаются и элементов последнего столбца матрицы входных отсчетов, хранящихся в регистрах 3, Каждая строка элементов 5 группы 4 осуществляет и -точечное ДПФ строки2матрицы входных отсчетов, Первый элемент 2 у) , вспомогательной матрицы 2(п,п) появляется на выходе элемента 5 и -й строки группы 4 ца (п)-м такте и подается для обработки на первый регистр 7 и далее на группу 8, в которой осуществляются пдхп-точечных ДПФ столбцов вспомогательной матрицы 2(пв,п).На группу входов 1 О- 10 р)процессора и, следоватепьно, ца группу входов группы 8 элементов 9 постоянно подаются весь этап вычислений элемен ты вектора С 0, (и,) = (1, Я Я Ьр ) р вр ее ф Я, ), причем ца вход 10 подаетсяо первый элемент Ы, = 1, на вход 10 5 второй элемент Я, и т.д. Каждый элемент 9 группы 8 (фиг.3)10 15 20 25 30 35 10 45 50 55 реализует следующие Функции:0)вых = (й) вх р2 рых (= 2 вхвьх= ьхвх + 2 вк причем элементы Увх поступают на вход 24 и ца регистр 28 элемента, элемент (0 в - ца вход 25 и на регистр 27, элемент 2 вх - ца вход 2 б и на регистр 29.С выходов 32, 33 и 34 выдаются соответственно элементы Увыхр СЗ р 2 врхвьор т;игвйцй ) стопбец тй = О, и -7) промежуточной матрицы 2(п,п ) потактнопоступает ца информационный вход первого регистра 7 и ца входы группы 8,цачи):ая с 2, -го элемента. Проходя через строки элементов 9 группы 8, столбцы проме)куточцой матрицы 2(п,п ) подвергаются ДПФ по второй координате. На .-м выходе группы 8 и, следовательно, ца ).-м выходе 11 (1 = 1,п) процессора Формируются 1-я строка матрицы выходных отсчетов У,Формула изобретения Процессор дискретного преобразования Фурье, содержащий первую группу из (п)-го процессорного элемента первого типа, первую группу.из (и) - го процессорного элемента второго типа, первый регистр, причем выход первого регистра пог;ключец к первому входу первого процессорного элемента первого типа первой группы, первый и второй выходы 1-го (1 = 1, и - 2)й процессорного элемецта первого типа первой группы подключены соответстренцо к первому и второму входам . + -го процессорного элемента первого типе первой группы первыйвторой выводы 1-го тт) = ) пв 2) процессорного элемента второго типа первой группы подключены соответственно к первому и второму входам (1+1)-го процессорного элемента второго типа первой группы, выход (п - 1)-го процессорного элемента второго типа первой группь) является первым информационным выходом процессора, первым информационным входом которого является информационный вход первого регистра, тактовый вход кото635,1 95рого подключен к тактовому входу процессора, при этом процессорный элемент первого типа содержит первый ивторой регистры, умножитель и сумматор, первый вход которого подключенк выходу умножителя, первый вход которого подключен к первому выходупервого регистра, информационный входкоторого является первым входом процессорного элемента первого типа,вторым входом которого является информационный вход второго регистра,выход которого подключен к второмувходу сумматора, второй выход первого регистра является первым выходомпроцессорного элемента первого типа,причем процессорный элемент второготипа содержит первый регистр, умножитель и сумматор, первый вход которого подключен к выходу умцожителя,первый вход которого подключен к первому выходу первого регистра, информационный вход которого являетсяпервым входом процессорного элемента 25второго типа, первым и вторым выходами которого являются соответственновторой выход первого регистра и выход сумматора, а тактовые входы первых регистров всех процессорных элементов первого и второго типов подключены к тактовому входу процессора,о т л и ч а ю щ и й с я тем, что, сцелью повышения быстродействия, в него введены п - 1 группа из п - 1процессорных элементов первого типав каждой группе, и- 1 группа изп - 1 процессорных элементов второго типа в каждой группе, первая группа иэ и- 1 регистров и вторая груп Опа иэ п-го регистра, причем первыйи второй выходы Е-го Ь = 2, п -2)процессорного элемента первого типа 1-й(1=2,п) группы подключены соответствецно к первому и второму входам (к+1)-го 45процессорного элемента первого типа1-й группы, выход 1-го (1 = 1, п - 1)регистра первой группы подключен кпервому входу первого процессорногоэлемента первого типа (д+1)-й гРУппы, 5 Опервый выход которого подключен квторому входу первого процессорногоэлемента первого типа -й группы, авторой вход первого процессорногоэлемента первого типа и -й группыявляется входом задания коэффициентовпроцессора, (+1)-и информационнымвходом которого является информационный вход -го регистра первой группы, тактовый вход которого подключен к тактовому входу процессора, входом задания )-го (1 = 1, и ) коэффициента группы которого является первый вход первого процессорного элемента второго типа 1-й группы, второй вход которого подключен к выходу 1-го регистра второй группы, тактовый вход которого подключен к тактовому входу процессора, (+1)-м информационным выходом которого является первый, выход (и - 1)-го процессорного элемента второго типа (д+1)-й группы, первый и второй выходы 1-го процессорного элемента второго типа (1+1)-й группы подключены соответственно к первому и второму входам (1+1)-го процессорного элемента второго типа (1+1)-йгруппы, третий выход )"го процессорного элемента второго типа 1-й группыподключен к третьему входу 1-го процессорного элемента второго типа (д+1)-й группы, выход 1-го регистравторой группы подключен к информационному входу (1+1) - го регистра второй группы, первый выход (п - 1)-го процессорного элемента первого типа -й группы подключен к третьему входу Ги - (1-2)-го процессорного элемента второго типа первой группы, а первый выход (п -1)-го процессорного2элемента первого типа, п-й группы подключен к информационному входу первого регистра второй группыпричем в процессорный элемент первого типа введены элемент НЕ, мультиплексор и третий регистр, выход которого подключен к второму входу умножителя, выход элемента НЕ подключен к тактовому входу второго регистра и управляющему входу мультиплексора, первыйи второй информационные входы которогоподключены соответственно к второму выходу второго регистра и выходу сумматора, выход мультиплексора является вторым выходом процессорного элемента первого типа, второй вход которого подключен к информационному входу третьего регистра, тактовые входы третьих регистров и входы элементовНЕ всех процессорных. элемецтов первоготипа подключены к тактовому входу процессора, при этом в процессорный элемент второго типа введены второй и третий регистры, выход второго регистра подключен к второму входу умножителя, а первый выход третьего регистра подключец к второму входусумматора, информационные входы второго и третьего регистров являютсясоответственно вторым и третьим входами процессорного элемента второготийа, третьим выходом которого является второй выход третьего регистра,:;тактовые входы второго и третьегорегистров всех процессорных элементов5второго типа подключены к тактовомувходу процессора,1635195 Составитель А. Барановедактор А.Лежнина Техред А.Кравчук Корре оши сное м при ГКНТ ССС Производственно-издательский комбинат "Патент", г. Ужгород, ул, Гагарина, 101 аказ 757НИИПИ Госу Тираж 412 По рственного комитета по изобретениям и 113035, Иосква, Ж, Раушская наб