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

 

Изобретение относится к вычислительной технике и предназначено для использования в высокоскоростных параллельно-конвейерных процессорах быстрого преобразования Фурье Виноградовского типа. Цель изобретения - повышение быстродействия устройства для вычисления дискретного преобразования Фурье (ДПФ). Поставленная цель достигается тем, что в устройстве обеспечивается реализация ДПФ любого объема, не превосходящего заданного значения, путем использования однократных модульных умножителей табличного типа. Устройство для вычисления ДПФ содержит блок преобразования двоичного кода в код модулярной системы счисления, два регистра константы сдвига, блок постоянной памяти константы сдвига, блок преобразования кода модулярной системы счисления в двоичный код, счетчик тактов, регистр номера шага, входные регистры, блок постоянной памяти коэффициентов, группы блоков постоянной памяти, блоки суммирования по модулям и блок задержки. 1 ил. (Л с

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

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

РЕСПУБЛИК (я)5 G 06 F 15/332

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

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

ПРИ ГКНТ СССР

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

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

Ы

M ((лЗ

IQl СлЗ )> (21) 4813561/24 (22) 11.04.90 (46) 07,05.92. Бюл, ¹ 17 (71) Научно-исследовательский институт прикладных физических проблем им, А.Н,Севченко (72) Л,Н.Василевич, И.И.Гунько и А,А.Коляда (53) 681.32 (088,8) (56) Авторское свидетельство СССР

N. 1290350, кл. G 06 F 15/332, 1987.

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

N 1042028, кл, G 06 F 15/332. 1983, (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57)Изобретение относится к вычислительной технике и предназначено для использования в высокоскоростных параллельно-конвейерных процессорах быстрого преобразования Фурье

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

Цель изобретения — повышение быстродействия устройства для вычисления дискретного преобразования Фурье.

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

ДПФ вида

SU 1732353 А1

Виноградовского типа. Цель изобретения— повышение быстродействия устройства для вычисления дискретного преобразования

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

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

Nr — s 1

Х.(u) = x,(u) вК"„, (1) и =о где Nr s — объем ДПФ, реализуемых íà s-м шаге алгоритма Винограда, представляющем собой множитель исходного N-точечного ДПФ (N = N> М2 ... К,, r > 1); xs(u) = х,(u)+

jxs (u);

xs (u), xs (u) — изменяются в симметричных отрезках (-P, Р), P — натуральное число;

s - =0, 1, ..., г-1; ) = К вЂ” 1, war —, = ехр(— )2Ф(ч„—.,)

Х-s(v) = xs (v)+ jxs (v) — отсчеты выходного сигнала ДПФ, 1732353

Отделив действительную и мнимую части, запишем (1) в следующей эквивалентной форме;

М 1у 2 r .2„ хв(u) — g (х.(u).ms + x,(u) sin и — о M" 1Ф 2цч .2цч

xs(U) = g (xs(U3.cos — х,(о) sin, (г)

»=о

=O,1...„N 1

Аппроксимируем константы соз(2Кс/Nr-s) и

sin(2X t/Nr-s) соответственно дробями

Wt /Q и Wst /Q, числители которых вычисляются по правилам

6/з1 = (Qcos(2 ж t/Nr-s) ), Wst = (Qsin(2 л t/Nr-s)), где t = О, 1, ..., ¹s -1; 0 — натуральное число; через (х) обозначается ближайшее к х целое число.

Выделив из множества г d I л

w=(woо, Woо," WO,Nr — 1 — 1, Wo,Nr — 1 1 (/

w1.о w1,О1 "! w1,Nr — 2 1 W1, w1,Nr — g 1 ю! I iJ ..., Wr-1,о, Wr-1,о, -, Wr — 1N1 — 1, Wr — 1,N1 — 1 } набор различных его элементов (ччо, ч»1, ..., w Л-1} (w I & w; i = О, 1...„Л -1; щ чч1, t = 0, 1 .„, Л -1; t+ 1, Л— объем набора), обозначив через

Wyo (S, u,V); Wy1 (S,u,V),à 2 (S,u,V), (yo (ЗД,V), ó1 (з,о,v), уг (з,u,v) 6 (О, 1...„ Л вЂ” 1}) числители дробей, аппроксимирующих соответственно константы

-sin(2 zt нч/1чг- ) = sin(2 a! -uv I

Nr-s/Nr-s), COS(2_#_uV/Nr-S) = СОЗ(2Л uVi

Nr-s/Nr-s), Sin(2m uV/Nr-S)= Si n(2 иЧ1

ivi=s/Nr-s).

Тогда согласно вышеизложенному искомый машинный аналог (2) можно записать в виде:

Х» = Q X j " +)(S U ÷)+ —, м г(з,о,ч)

V = O,1...,N, -1 (3) где х„, x„", Хч, М вЂ” мантиссы отсчетов xs (u)Ä

xs (u), Xs (ч), X4 (v) соответственно; 2" — масштаб (4 — неотрицательное целое число), -Is выбираемый так, чтобы величина хо = (xu 2 ) и х о = fxо" 2 ) не выходили за пределы отрезка (-Р,Р); через (х/Q) обозначается некоторое целочисленное приближение к дроби х/Q; х — целое число. Без нарушения общности действительные и мнимые составляющие отсчетов исходного N-точечно, го сигнала, а значит и величины хо(и) и хо(о) (3) полагаются целочисленными. Целочисленными являются также мантиссы хо, хи, Хч, Х для всех s = О, 1, ..., r-1, Следовательно, они являются элементами диапазона (— P, — P+1, ..., P} и имеют порядок io = О.

5 Для реализации базовых соотношений (3) используется МСС с основаниями m1, гпг, ..., пц удовлетворяющими условиям М = m1 п1г ... п1к PQq v 2 и пи > 2mo+ К-2; m,> К-2 (ГдЕ q = maX (N1, йг, ..., Nr}), 10 На чертеже приведена структурная схема предлагаемого устройства для вычисления дискретного преобразования Фурье (ДП Ф), Устройство для вычисления ДПФ содер15 жит тактовый вход 1, вход 2 задания номера шага алгоритма, первый установочный вход

3, информационный вход 4, четвертый 5, второй 6 и третий 7 установочные входы, регистр 8 номера шага разрядностью )logger(, 20 входные регистры 9.1 — 9.2q разрядностью

L = ), bI бит (b; = )logjam<(; через =1

)х(обозначается ближайшее к х справа целое число), блок 10 преобразования двоичного кода в код модулярной системы счисления, первый регистр 11 константы сдвига, счетчик 12 тактов, группы блоков постоянной 13.1-13.К памяти, блок 14 задержки, блок 15 постоянной памяти константы сдвига, блок 16 постоянной памяти коэффициентов, блоки 17.1 — 17,К суммирования соответственно по модулям m1, тг...Ä mk, блок

18 преобразования кода модулярной системы счисления в двоичный код, второй регистр 19 константы сдвига, выходы мантиссы 20 и порядка 21 устройства, Блок 10 осуществляет преобразование р ll

А-битовых двоичных кодов мантисс хо и хо ..1 л

40 в модулярный код величин хо и хо . Данный блок представляет собой известное устройство, выполняющее одно преобразование за Ти + 1 такт, где Ти = ) оцгй(;,и — число групп двоичных разрядов в преобразуемых

45 А-битовых кодах (Л вЂ” разрядность и ромасштабированнi.Ix значений соответствующих мантисс), Обращение к блоку 10 можно производить ежетактно, Первый вход преобразователя 10 является информационным

50 входом 4 устройства. Второй вход подключен к выходу регистра 11, а выход заведен на вход блока 14 задержки.

Тактовый вход блока 10 объединен с тактовыми входами регистров 8, 9.1-9.2q, 11 и 19 блока 14 задержки, блоков 17.1 — 17.К суммирования, блока 18 преобразования кода модулярной системы счисления в двоичный код со счетным входом счетчика 12 тактов и подключен к тактовому входу 1 устройства.

1732353

15 установки в нуль счетчика 12 объединен с -20

Блок 18 преобразования кода модулярной системы счисления в двоичный код является известным устройством конвейерного типа, осуществляющим одно преобразование за (T + 3) такта (T = )!о9гф, причем, обращение к преобразователю можно производить ежетактно. Блок 18 по информационным входам соединен с выходами блоков

17.1 — 17.К суммирования. Его выход является выходом 20 мантиссы устройства, при этом старшие d разрядов выхода заведены на первый адресный вход блока 15 постоянной памяти, Счетчик 12 тактов является (Tq + 1)-разряднымм (Tq = )Iogzq f) и имеет два входа установки в нуль. Наличие единичного сигнала на любом из них обнуляет содержимое счетчика в момент окончания тактового импульса на счетном входе счетчика. Первый вход входом разрешения записи регистра 8 номера шага и подключен к первому установочному входу 3 устройства, Второй вход установки в нуль объединен с входами разрешения записи регисров 9.1 — 9.2q и подключен к (2о + 1)-му выходу блока 16 постоянной памяти. Запись информации в регистры 9.1 — 9.2q осуществляется при наличии единичного сигнала на их входах разрешения записи. Выход счетчика 12 заведен на первый вход блока 16 постоянной памяти, Группа блоков 13.! (! = 1, 2, ..., К) постоянной памяти состоит из 2q одинаковых блоков постоянной памяти емкостью (2 ) Л()Ь| бит, В каждом из этих блоков постоянной памяти по адресу

f + т 2 записывается вычет tow пц для всех y = О, 1, ..., mi-1, t = О, 1, ..., Л-1, где через lAtm обозначается наименьший неотрицательный вычет, сравнимый с величиной А по модулю m. Первый адресный вход

j-го блока постоянной памяти группы 13.i подключен к l-му выходу регистра 9.j (j = 1, 2, ..., 2q), вторые адресные входы j x блоков постоянной памяти всех групп объединены и подключены к j-му выходу блока 16, а выход j-го блока постоянной памяти подключен к одноименному входу блока 17,i, Блок 14 задержки представляет собой цепочку из 2q-1 регистров разрядностью L бит, Вход первого регистра подключен к первому выходу блока 14 задержки, а выход

I-го регистра является (I + 1)-м выходом блока задержки (I = 1, 2...„2q-1), Выходы блока

14 задержки с первого по(2ц)-й подключены к информационным входам соответственно регистров 9.1 — 9.2q. Обращение к блоку задержки может осуществляться ежетактно.

Блок 15 постоянной памяти кг ста>:: ы сдвига облащет емкостью 2 ) )Iogdf бит (d =у — it+ 1). В его память по адресу х + 2 записывается величина max(l(x), e) для всех х = О, 1...„2 - 1 и I = О, 1, ..., d-1, d где l(x)-номер самой младшей цифры двоичного кода (xd-1xd-г, ..., xo)2 числа х, удовлетворяющей условию xi = х!(х) при каждом

i > l(x). Второй адресный вход блока 15 подключен к выходу регистра 19, являющемуся выходом 21 порядка устройства, Информационные входы регистров 11 и 19 объединены и подключены к выходу блока

15. Вход разрешения записи регистра 11 и входы установки в нуль регистров 11 и 19 подключены соответственно к четвертому 5, второму 6 и третьему 7 установочным входам устройства. Запись в регистр 11 осуществляется при поступлении единичного сигнала на установочный вход 5 устройства, Запись в регистр 19 осуществляется ежетактно. Единичные сигналы на установочных входах 6 и 7 обнуляют содержимое соответственно регистров 11 и 19;

Блок 11 поотояннои памяти обладает емкостью 2 logpr(+ Tq+ 1) х 2q )log Л(+ 1) .

B его память по адресу (v + 2 Tq + 1)з) записывается двухкомпонентный набор величин

УУ "7>

J-я из которых поступает на J-й выход (j = 1, 2q) блока 16. Здесь у — номер нуля множества (wp, w>, ..., wJ — 1), т,е. константы Wy =О, На (2q+1)-й выход блока 16 поступает из ячейки с вышеуказанным адресом величина (1 - )2№Б - ч-1(), которая обеспечивает для счетчика 12 подсчет числа тактов по подул ю

2¹s. Второй адресный вход блока 16 постоянной памяти подключен к выходу регистра

8 номера шага, Информационный вход последнего подключен к входу 2 задания номера шага, Запись числа в регистр 8 осуществляется по окончанию такта при наличии единичного сигнала на входе разрешения записи, Блоки суммирования по модулю 17.117.К являются известными устройствами.

Они имеют (Tq + 1)-каскадную параллельноконвейерную структуру, благодаря чему обращение к ним можно производить ежетактно, Работа предлагаемого устройства для вычисления ДПФ.

Процесс выполнения ДПФ, описываемого выражением (3), можно разбить на

Ih(S,v) = <72-h(S,Î,v),уз-ь(S,О,v), Уг — h(Si1,Ч) УЗ вЂ” h(Si t,Ч),." УЗ вЂ (S,Nr — s — 1,V), 1732353 два этапа. В ходе первого этапа мантиссы

XNr-s-1, XNr-s-1, Xh, Хо дЕйСтВИтЕЛЬНЫХ И МНИмых составляющих отсчетов входного сигнала ДП Ф последовательно от такта к такту, начиная с нулевого, в указанном порядке 5 подаются на первый вход блока 10, на второй вход которого из регистра 11 ежетактно поступает константа сдвига I=Is, отвечающая текущему (s-му) шагу алгоритма Винограда.

Перед началом нулевого шага алгоритма 10 регистр 11 по сигналу Zz = 1 с входа 6 устройства обнуляется (lо = 0), а на последнем (Ти+ 2Nrs + Тя + Т + 5)м такте каждого шага в регистр 11 по сигналу 24 = 1, поступающему с входа 5 устройства, запи- 15 сывается константа, формируемая так, как это изложено ниже, на входе блока 15 постоянной памяти. На (Ти+ 1)-м такте каждого на установочном, входе 3 устройства появляется сигнал Z1 = 1, по которому в конце этого 20 такта в регистр 8 занесется значение s, поступавшее на вход 2 задания номера шага алгоритма, а содержимое счетчика 12 тактов обнуляется. С конца (Ти+ 1)-го такта, где Ти = )logo+ (,,и — число групп двоичных

25 разрядов в преобразуемых, il,-битовых кодах, в блок 14 задержки с выхода блока 10 ежетактно начнут поступать модулярные ко((л(л(ДЫ (MK) ВЕЛИЧИН XNr-s-1, XNr-s-1, ..., Xp, Xp u по истечении (Ти+ 2¹s)-го такта полученные МК по единичному сигналу с (2q+1)-ro выхода блока 16 передаются в регистры 9.1—

9.2Nr-s, модУлЯРный код (2¹s - 1+1)-го элемента последовательности запоминается в 35 регистре 9л (1 = 1, 2...„2¹s).

Второй этап процесса реализации выражений (3) так же, как и первый, состоит из

2¹s тактов. В ходе (2ч+ h) ãî цикла, начинающегося с (Ти+.2йг-з+ 2ч+ h)-ro такта 40 (ч-(О, 1, ..., ¹s1; h=(1,2)) на первый и второй входы группы блоков 13,1(i = 1, 2, ..., К) подаются соответственно 2q-компонентные наборы величин

-(("\ (< хо I mt I xo I m(, ° ° ° xNr-s-1I mi, 45

I xNr-s-1Imi, R2Nr-1, ..., R2q-1 иГь (s, ч), где R1 — t-я цифра МК, записанного в регистРЕ 9 1 (1 = 2¹s + 1,2 Nr-s + 2, ..., 2с1). В РеЗУл ьтате во входные регистры блоков 17.1 суммирования вычетов с выхода группы 50 блоков 13.i постоянной памяти поступит на6ор вычетов ч(.3 fl

< I Xp — h (S O,V)Imh !ХоФ/)(З вЂ” h (S,O,V)imh ..., ll

I xNr-s-1(("(у2-1((3, Nr-s-1, ч) I ml, 55 ! хм(-s-1W+ — h (s,¹s1. ч) Imh О, ..., 0> для всех i = 1, 2, ..., К и по окончании (Ти+ 2¹s+ 2 ч + h + Tq + 1)-го такта блоки

17.1 — 17.К сформируют МК числа у> при h = 1 и числа у при h = 2 по правилу, Nr — s — g

yv = g (XuWy1(S,u,V)+XuW (S,u,Ч))

u=0

Nr — s — 1, yv = g (xuWy,(s,U,v) + xuWy1(sд,ч)), u=O

Полученный МК на следующем такте поступает в блок 18 преобразования. Двоичные

А-разрядные коды результатов масштабирования величин уч и уч нв масштаб Q, т.е, искомые мантиссы Хч(и Х ч действительной и мнимой составляющих V-ro комплексного отсчета выходного сигнала выполняемого ДПФ (формула (3) будут получены блоком 18 соответственно на (Ти+ 2Nr-s + 2ч +

+Tq+T+5)=s4 Pl(Tp+2¹s+2v+Tq+T+6)

= м тактах. Мантисса, полученная по истечении (Tp+ 2¹s+ 2ч+ Tq+ Т+ h+ 4)-го такта, снимается с выхода мантисс AY в следующем такте. При этом ее d-битовая старшая часть gv вместе с содержимым регистра

RGe подаются на адресные входы блока 12 и из его памяти по адресу gv + е 2 считыd вается величина max(l(gv), е ), которая запоминается в регистре 19, В момент появления на выходе блока 18 преобразования мантиссы действительной части нулевого комплексного отсчета выходного сигнала первого из

ДПФ, выполняемых íà s-M шаге алгоритма

Винограда (s = О, 1...„r-2), т.е. по окончании (Tp+ 2¹s+ Tq+ Т+ 5)-го такта данного шага, регистр 19 обнуляется по сигналу 2з = 1 с входа 7 устройства. Поэтому согласно вышеизложенному после выполнения последнего из ДПФ s-го шага на выходе блока 15 постоянной памяти сформируется константа СдВИГа Is+1 дЛя (S+1)-rO ШаГа. ПОЛуЧЕННая константа записывается как в регистр 19, откуда она поступает на выход 21 порядка устройства, так и по сигналу Z4 = 1 в регистр

11. Действительные и мнимые составляющие всех отсчетов выходного сигнала исходного N-точечного ДПФ, вычисляемые в ходе заключительного шага алгоритма Винограда, имеют общий порядок: 11+ 12 + ... + Ir-1.

Заметим, что отдельные ДПФ объема

Nr-> в описываемом устройстве осуществляются за T(Nr-s) = 4Nr-s+ Ти+ Tq + Т+ 5 тактов.

При этом реализация нового ДПФ данного объема может быть начата по истечении (2Nr-81-го такта текущего преобразования, т.е. частота обращения к устройству на s-м шаге алгоритма Винограда состав10

1732353

55 ляет f = 1/2(2¹ )Тмт, где Тмт — длительность модульного такта.

Если, например, ¹s = 4, то f = 1/8Тмт, что существенно выше частоты обращения известного устройства, составляющей

1/13Т >. Поскольку предлагаемое устройство способно выполнять любое ДПФ объема, не превышающего q, то сфера его применения существенно шире, чем у известного.

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

Устройство для вычисления дискретного преобразования Фурье, содержащее первый и второй регистры константы сдвига, блок постоянной памяти констант сдвига, блок преобразования кода модулярной системы счисления (MCC) в двоичный код и блок преобразования двоичного кода в код модулярной системы счисления, первый и второй информационные входы которого подключены соответственно к информационному входу устройства и выходу первого регистра константы сдвига, тактовый вход которого подключен к тактовому входу устройства и соединен с тактовыми входами блока преобразования двоичного кода в код модулярной системы счисления, второго регистра константы сдвига и блока преобразования кода модулярной системы счисления в двоичный код, выход которого. является выходом мантиссы устройства и подключен к первому адресному. входу блока постоянной памяти константы сдвига, второй адресный вход которого подключен к выходу второго регистра константы сдвига, выход которого является выходом порядка устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены регистр номера шага, счетчик тактов, блок постоянной памяти коэффициентов, 2q (q — объем преобразования) входных регистров, К групп блоков постоянной памяти (К— число оснований модулярной системы счисления) по 2q блоков в каждой, К блоков суммирования по модулю соответственно m<, m2 ..., mK, блок задержки, j-é (j = 1 2;.,) вы:лд которого подключен к информационному входу J-го входного регистра, i-й (i = 1,K) выход которого подключен к первому адрес5 ному входуj-го блока постоянной памяти 1-й группы, выход которого подключен к j-му информационному входу блока суммирования по модулю п, выход которого подключен к i-му информационному входу блока

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

20 подключен к тактовому входу устройства, первый установочный вход которого подключен к установочному входу счетчика тактов и входу разрешения записи регистра номера шага, выход которого подключен к

25 второму адресному входу блока постоянной памяти коэффициентов, М-й выход(М =1,2q) которого подключен к второму адресному входу М-ro блока постоянной памяти i-й группы, информационный выход счетчика

30 тактов подключен к первому адресному входу блока постоянной памяти коэффициентов, (2q + 1)-й выход которого подключен к входу обнуления счетчика тактов и входу разрешения записи j-го входного регистра, 35 выход блока постоянной памяти констант сдвига подключен к информационным входам первого и второго регистров констант, сдвига, установочные входы которых подключены соответственно к второму и треть40 ему установочным входам устройства, четвертый установочный вход которого подключен к входу разрешения записи первого регистра константы сдвига, а вход задания номера шага устройства подключен к инфор45 мационному входу регистра номера шага.

1732353

Составитель Л.Василевич

Техред М.Моргентал Корректор T.Ïàëèé

Редактор Е.Папп

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

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

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

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