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

 

ОПИСАНИЕ

ИЗОБРЕТЕН ИЯ

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

Союз Советских

Социалистических

Республик (61) Дополнительное к авт. свид-ву (22) Зая;влево 13.02.74 (21) 1996828/18-24 с присоединением заявки № (23) Приоритет

Оп,бликовано 30,12.75. Бюллетень № 48 (5l),Ч. 1хл. С 06f 15, 34

Государственный комитет

Совета Министров СССР по делам изобретений и открытий (53) УДЫ 681.14(088.8) Дата опубликования описания 16.06.76 (72) Авторы изобрете ния

Г. Д. Бахтиаров и А. 1О. Тищенко (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО

ПРЕОБРАЗОВАНИЯ ФУРЬЕ

Изобретение относится к области радиотехни ки и может быть использовано для построения устройств спектрального анализа и фильтрации, основанных на алгоритме быстрого преобразования Фурье (БПФ), когда объем входной выборки N = r i. r . r> ... r», где r i, rz, гз, ... r» различные простые числа.

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

С целью существенного сокращения оборудования в предложенном устройстве применена последовательно-параллельная структура вычислений, для чего выходы одного счетчика каждого каскада подключены ко входам первой коммутационной панели, выходы которой соединены с управляющими входами переключателей первой группы, другие входы которых соединены со входной шиной, а выходы — со входами аналоговых сдвигаюи щх регистров первой группы и со входами переключателей второй грулпы, управляющие входы которых подключены к выходу другого счетчика и входу переключателя выходов усилителей, другие входы переключателей второй группы соединены с выходами, второй коммутационной панели, выходы переключателей второй группы соединены со входами аналоговых сдвигающих регистров второй группы, входы второй коммутационной панели соединены с выходами а налоговых сдвигающих регистров второй

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

10 соответствующего переключателя данной группы.

Блок-схемы устройства для выполнения прямого быстрого преобразования Фурье соответственно для отдельного каскада и для двух

15 каскадо|в представлены на фиг. 1 и 2, где 1— входная шина каскада; 2 — переключатели первой группы; 3 — аналоговые сдвигающие регистры первой группы; 4 — переключатели второй группы; 5 — аналоговые сдвигающие

20 регистры второй группы; 6 — первая коммутационная панель; 7, 8 — блоки операционных усилителей (БОУ); 9 — переключатель выходов усилителей; 10 — выходная шина каскада; 11 — счетчик управления перестановкой;

25 12 —; 13— вторая коммутационная панель; 14 — счетчик управления обменом; 15 — шина тактовых импульсов с частотой, равной f,,/R; ь 16 — шина тактовых импульсов с частотой, равной

30 j„ /R;.,3

497589

ri — 1

" " й.Т

1- О где

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

Л записывается в виде таблицы, имен>щ(й

Л>ч1 столбцов размера ri. Над то-(кими, образующими столбсц, выполняется БПФ, а затем для вычисления конечных результатов выпо:1няется БПФ над строками, Прп этом для исключения операций умножения промежуточных результатов на комплексные коэффициенты точки в каждом столбце перед выполнением БПФ от столбца смещаются по кругу на а1 позиций, где I — номер столбца. Выходные данные в каждой строке получа(отея смс(ценными по кругу на bm позиций, где m— номер строки (нумерация идет с нуля) . Так как строка имеет значительную длину, то се, в свою очередь, можно представить в впдс таблицы и вычислить БПФ от строки указанным выше способом. Таким образом, вычисление БПФ состоит пз И шагов, причем на вссх, кроме последнего, необходимо обработать таблицу с размером столоца г; и строки

М

Ri= I1 rj, где L — номер шага, т. с. а

1=i 1 каждом шаге нужно вычислять БПФ от R; столбцов размером ri, причем перед вычислением точки столбца смещаются по кругу на

a;l позиций, где 1 — номер столбца; а; — — целочисленное решение уравнения b;r; — аЯ;= — 1;

b; — также целое число. На последнем шаге обрабатывается строка размером r>1 и не требуются персстаноькп перед вычп лсниями.

К-ая точки БПФ вычисляется согласно формуле

Так как 0(k(r;, 0(j(r;, то сели йФО и

r; — простое число, среди 1РI есть все r; возможных значений и каждое пз нпх встр -1ается ровно один раз. Т. е. для вычисления всех точек БПФ, кроме Hp, можно использовать блок операционных усилителей, состоящий из двух о перационных усилителей (один для получения действительной, другой — мнимой части результата) и набора весовых сопротивлений, что достигается многократной (r; — 1) подачей на его входы одних и тех же сигналов

h в разном порядке.

Для вычисления Hi> используется отдельный блок операционных усилителей 8.

В устройстве использова каскадная структура, в которой вычисления выполняются параллельно в М каскадах, причем в каждом каскаде промежуточные результаты и точки искомого БПФ вынисляются последовательно.

Данные проходят последовательно через все

2,>

:35

45 каскады, кроме того, от каскада к каскаду передаются необходимые тактовые сигналы.

Обработку в i-том каскаде можно начать, когда будет накоплено 1Д, данных, поступающих на каскад последовательно. Для этого даиныс, поступающие по входной шине 1, вводятся в аналоговые с.;(вигаю)цие рсгистры 3.

Длина каждого из этих рсг((стров R;, а вместе онп образу(от кольцевой регистр сдвига. Одновременно с накоплением производится Tp(бусмое смещение данных в столбцах по Kp) гу, для чего на входе каждого из регистров

3 имеются переключатсли 2, которые могут подключать эти входы либо к выходу предыду щего аналогового сдвигающего регистра первой группы, либо к входной шине 1. Выборочное значение, поступающее через l тактов после начала строки, относится к столбцу с номером l и должно быть введено с круговым смещением на ((а,l) ) позиций (знаки ((х) ) обозначают остаток от деления х на

r;), что выполняется введением этого сигнала через переключатель первой группы с номером ((а(1)) (нумерация начинается с нуля).

Для этого соответствующий перск;цочатель

2 по сигналу с устройства управления перестановкой подключает выход с ко входу а, в то время, как к выходам остальных переключателей первой группы 2 подключены их входы b.

Устройство управления перестановкой состоит из счетчика управления перестановкой

11, пмеющсго 1.(положений, причем управляющий сигнал выдается по выходу с номером, равным 1, для чего c Iåò÷èê считает сигналы, поступи(ощне по шине импульсов дискретизации 12 II имеющие частоту, равную частоте квантования входного сигнала j„„ II устанавливается в ноль сигналами, поступающим и по шине 1б в начале обработки строки.

Выходы счетчика управления перестановкой

11 соединяются в управляющими входами у переключателей первой группы 2 через первую коммутационную панель б, в которой входы с номерами l соединены с выходами с номерами ((a;l)). После выполнения накопления в каждом из ана",îãîâûõ сдвигающих регистров первой группы 3 оказывается за ппсаннои строка матрицы, подготовленнои к обработке. )ти данные заносятся в аналоговые сдвигающие регистры второй группы 5 (группа содержит r; регистров длиной каждый), для чего переключатели второй группы 4 по сип(алу счетчика у пра вления обменом 14, подкл(очают входы i этих регистров на вовремя R, тактов ко входам d переключателей второй группы, которые соединены со входами аналоговых сдвига)ощих регистров первой группы 3. Из регистров второй группы

5 сигналы поступают на БОУ 7 и 8, где за R; тактов вычисляется одна строка матрицы результатов, Если н. производится обмен, то эти же данные со входов f переключателей второй группы 4 снова поступают в аналоговые сдви497589

2>5 где гающиг регистры второй группы 5 и использу)отся в ходе вычисления следующей строки, для чего их порядок опргдсленным образом меняется. Измснгнис порядка осуществляется путем соединения выходов аналог013»lx сдвнгающих рггистров Ilторэй группы 5, кото рые В начале обработки содержат строку с номером /г, черсз вторую коммутационную па))гль 13 с входами J тгх псреклю-!3Т0. tcé втэрэй гругпы 4, которые стоят на входах регистров, хранивших в начале обраоотки матрицы строку с номером ((kg)). Осычно к выходной шине каскада 10 псдключагтся БОУ 7, который вычисляет строки Hib räå 1=1, 2, ..., r; — 1. Для вычисления H(> на время обмена к выходной шине каскада 10 чгргз переключаталь выходов усилителей 9 подклю ается

БОУ 8.

На выходе каскада строка, идущая j-той по порядку (начиная с и) ля) имеет помер ((ч!) ), а нулевая строка посту пает на выход ка "када последней. здесь g — первообразный корень r;.

НЯ фиг. 3 и -1 приведены соответственно общая блок-схема н блок-схема отдгльнэгэ кlcкада устройства для выпэлнсния обраflIL)10 бь!строго преобразования Фурь..

На блок-схемах применены тг же обозlгячения отдельных каскадов, что и на фиг. 1 и

2, а также введены слгдующие дополнительные каскады: 17 — пергключатсли третьей группы; 18 — аналоговые сдвнгающи" реги: тры третьей группы; )9 — блок нача.п.ной установки.

Устройство для выполнения обратного БПФ имеет следующие особенности.

Входные данныс от устройства. выполняющего прямос БПФ, поступа!От в требуемом порядке, в то время как выходные ргзультаты, как правило, требуется получать в естг гвенном порядке. Поэтому ана !0ro3»t= слвигающие регистры псрвой груп вы 3 и переключатели псрвой груп пи! 2, выполняющие круговуlo псрестановку, вклк>чснь> после переключателя выходов усилителей 9. По окончании пгрестяно вкн требуется 13ыво;1нть данны ср3зу из всех r; аналоговы:(сдвпгающпх р гпстpoI3 пс)3ВОЙ rpi ппы 3, !10 i CTpoLIcT!30»it ст последовательный выход, поэтому данные предварительно переписыва)отся в аналоговые регистры третьей группы 18 через персключатели трстьей группы )7. Эти жс регистры и переключатели служат для накоплеll!15i входнь!х

:(анны:(перед вычислснисм.

Для выполнен!)я псргстано!3кн выходных сигналов ут!равляющпе входы переключателей первой группы 2 соединсны через первую коммутационную панель 6 с выходами счетчика

i>!rIp3I3лгния перестановкой 11, так что его выход с номером S соединяется с управляющим входом переключателя первой группы с номером ((— a;S)). Для устанения дополнительной перестановки, возникшей при вычислении

r,— 1 строк в одном БСУ, необходимо в начале получения каждой строки результатов

3 )

4 )

3 устанавливать счетчик управления перестановкой )1 в положение х;1, где l — номер получаемой строки по порядку вычисления (состояние счетчика управления обменом )4).

Зняч !lite х;1 находится пз уравнений: ((— а,.х,)) ((1 — О 1)), если 7 - г, — 1 ! ((— а,Х-г, — -1)) -- r1--1, ЕСЛИ I г, — ).

Эта начальная установка осуществ,чяется блоком начальной устагэвки 19, которос соединено с выходами счетчика управ.чгния обменом 14, считающего импульсы с шины 16 с частотой, равной f„.,Я;. Кроме того, к последнему выходу этого счетчика подк,чючены управляющие входы перек.чючателгй 4. Счетчик

14 вырабатывает также импульсные сигналы для шины )5 с частотой, равной f,,!ßt !.

Вычислительную часть устройства для выполнения обратного БПФ можно было бы выполнить такой же, кяк в устройстве для выпо.; пения прямого БПФ, однако для упрощения применен блок, работающий по формуле

1- k= г; — 1 и F. ехр(2-,, r,).

Дчя этого первый из ана чоговых czI3»r310LLLI!i рсг!1с-р03 гвтэрой груtt))b! 5 ч "ргз первый пз пгрскч10- Ятгчей втэрэй г); till! 4 замкнут сам

1!3 ":.()51, 3 ". T3льныс сэрpçi toò кольцевой рсгистл.

Д:я испо !! зэВянll I кас)(Iäа В устрОЙOTÂñ . с др;.гим рязмсром выо:;рки п.tlt распо.)ожснигм каска ов достато- о замен! ITb пгрвук>

I(03!»i тя1 ПОннуlо панель 6, пост lI»ITI яня toroвыг сдвига!сшпг реги. Т» .>I ссэтвгтст!33 к)!Il(é длины. а тя.. же сменить вчэрую коммутяциo111ti I0 п3 11г, ?b 13 В 3 cTpo! cтвс д I Вьlпо:1нг11п51

itp5 vl0r;) БПФ и программу расэты б.чока на !3,Ib1!011 тановк!! 19 !3 3 стрэйствс по пг!II!» Обратногэ БПФ.

П р д ii г r !1 3:>,) .) т с и и 51

Ъ CTPOIICT!30:1 151 t)L:C!:), ..!IIIIIII ОЫСТРЭГ<) IIP(Ооразования Фурье. содсржащее касI(33bt каждый пз которых содержит двг гр3 ппы аналоговых сдв))гающпх ргг:!стров и игрек t!O÷3течей, коммутационные ганглп, п ргключягель выходов уси.чптглгй, счетчики, блок!!

01,, ) "I: 11 )!1" I>1; 3 C to I! IT(., I(. t () I, (11 Я !О III (С С 5!

TC3t, !Т ), С Цг !ЬЮ:С! Р(>П(С»!)и ОО:)Pi 101331!I!5> устрой тва, в и м выхо,чы одного c÷åò÷ï"! к я )к л 0 г 0 к я с к 3 л я и О д к. ю с! 1 ы ко В х 0;1 3 3! и г рвой коммутационной панели, выходы которой соединены с управ 351!OILLII31! t входами переключателей первой группы, другие входы которых соединены с входно!1 шиной, à выхо. ды — со входами аналоговых сдвпг310tLLLèê регистров первой группы и со вхо (3 IH,nepe:. Io- агелей второй группы, 1:правляющие Входы которых подключены к выходу, другого

c, тчика и входу переключателя выходов уси

497589 атил.ад 2каскад

Р». Юм. яв.асад 1»гасл ад

Ю» Ры.г. лителей, другие, входы переключателей второй группы соединены с выходами второй коммутационной панели, выходы переключателей второй группы соединены с входами аналоговых сдвигающих регистров второй группы, входы второй коммута цио нной,па нели соединены с выходами аналоговых сдвигающих регистров второй группы и входами блоков операционных усилителей, выходы которых сосдинены со входами переключателя выходов усилителей,,пр ичем выход каждого аналогового регистра первой грунины соединен со входом соответствующего переключателя данной группы, 497589

Рг.г. Ф

Составитель А. Тищенко

Техред М. Семенов

Корректор Е Хмелева

Редактор В. Левятов

ТипогэаФия. по. Сапунова, 2

Заказ 1092/13 Изд. № 2120 Тираж 679 Подписное

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

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