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

1

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

входной выборки Л Г1-Г2-Гз ... Гм, где fi, Г2,

fs, ... различные простые числа.

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

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

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

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

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

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

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

12 - шина импульсов дискретизации; 13 - вторая коммутационная папель; 14 - счетчик управления обменом; 15 - шина тактовых импульсов с частотой, равной /кв/-/ -ь 16 - щина тактовых импульсов с частотой, равной

fuB/RiУстройство рассчитано на естественный порядок входных данных, результаты же вычислений получаются в порядке, удобном для последующего выполнения обратного преобразования. В соответствии с используемым алгоритмом входная выборка данных размером Л записывается в виде таб;и1цы, имеюихей AV/i столбцов размера Гь Над точкам, образующими столбец, выпоЛНяется БПФ, а затем дл.я вычисления конечных результатов выполняется БПФ над строками. При этом для исключения операций умнон ения промежуточных результатов на комплексные коэффициенты точки в каждом стол, перед выполнением БПФ от стол.бца смещаются по кругу на al позиций, где / - номер стол.. Выходные данные в каждой строке получаются смещенными по кругу на Ьт пози-ций, где т - номер строки (нумерация идет с нуля). Так как строка имеет значительную длину, то ее, в свою очередь, можно представить в виде таблицы и вычислить БПФ от строки указанным вы|Ще способом. Таким образом, вычисление БПФ состоит из М щагов, причем на всех, кроме последнего, необходимо обработать таблицу с размером столбца г.; и строки

м Ri i rj, где i - номер тага, т. е. на

каждом щаге нужно вычислять БПФ от R: столбцов размером Г;, причем перед вычислением точки столбца смещаются по кругу на uii позиций, где / - номер столбца; а, - целочисленное рещение уравнеиия Ь,гг-аг/ ; 1; bi - также целое число. Па последнем ишге обрабатывается строка размером г и не требуются шерестаиов ки перед вы-числгииЯМИ.

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

П-1ъ,

Hk - /l;W ,

/ о где:

lF./--exp (- i-. П J

TaiK как , ,;, то если и Г; - простое число, среди W есть все Г; возможных значений и каждое из них встречается ровно одии раз. Т. е. для вычисления всех точек БПФ, кроме Но, можно использовать блок операциоцных усилителей, состоящий из двух операционных усилителей (оди« для получения действительной, другой - мнимой части результата) и набора весовых сопротивлений, что достигается многократной (г,- 1) подачей на его входы одних и тех же сигналов hj в разном порядке.

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

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

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

Обработку в 1-том каскаде можно начать, когда будет накоплено riRi данных, поступающих иа каскад последовательно. Для этого данные, поступаюп1ие по входной щине 1, вводятся в амалого1вые сдвигающие регистры 3. Длииа каждого из этих регистров Ri, а вместе они образуют кол1 цевой регистр сдвига. ОдК) новременио с накоплепием производится требуемое смещение дап.пых в столбцах по кругу, для чего на входе каждого из регистров 3 имеются переключатели 2, которые могут подключать эти входы либо к выходу предыдущего апалогового сдвигающего регистра первой группы, либо к входной щние 1. Выборочное значение, поступающее через I тактов после иачала строки, относится к столбцу с номером / и должно быть введено с круговым смещепием иа ((uil)) позиций (знаки ((х)) обозначают остаток от деления х на /,), что выполпяется введением этого сигнала через иереключатель первой группы с номером ((а,:/)) (нумерация начинается с нуля). ) Для этого соответствующий переключатель 2 по сигналу с устройства управлепия перестановкой подключает выход с ко входу а, в то время, как к выхода м остальных переключателей первой группы 2 подключены их входы Ь.

Устройство управления перестановкой состоит из счетчика управлеиия перестацовкой 11, имеющего Гг положеиий, причем управля1ОЩ1ИЙ сигнал выдается по выходу с номером, 5 равиым I, для чего счетчик считает сигиалы, поступающие по щиие импульсов дискретизации 12 и имеющие частоту, равпую частоте квантования входного сигнал а /кв и устанавливается в ноль сигналами, поступающими по 0 шине 16 в начале обработки строки.

Выходы счетчика управлеиия перестановкой 11 соединяются в управляк;щими входами у переключателей первой груипы 2 через первую ком1мутациониую панель 6, в которой 5 входы с номерами / соединены с выходами с номерами ((a,/)). После выполнения накопления в каждом из аналоговых сдвигающих регистров первой группы 3 оказывается записанной cTpOiKa матрицы, подготовлениой к обработке. Эти данные заносятся в аналоговые сдвигающие регистры второй группы 5 (группа содержит г; регистров длиной Ri каждый), для чего переключатели второй группы 4 по сигиалу счетчика управления 5 обмеиом 14, подключают входы i этих регистров |На время Ri тактов ко входам d переключателей второй группы, которые соединены со входами аналоговых сдвигающих регистров первой группы 3. Из регистров второй группы 0 5 сигналы поступают на БОУ 7 и 8, где за Ri тактов вычисляется одна строка матрицы результатов.

Если не произ водится обмен, то эти же

данные со входов / переключателей второй

5 группы 4 снова поступают в аналоговые сдангающие регистры второй группы 5 и используются в ходе вычисления следующей строки, для чего их порядо1К определеи Е1ым образом меияется. Изменение порядка осу.ществляется путем соединения выходов аналоговых сдвигающих регистров второй группы 5, кото рые в начале обработки содержат строку с номером k, через вторую коммутационную па|1ел1 13 с входами / тех переключателей второй группы 4, которые стоят на входах регистров, хранивщих в начале обработки матрицы строку с номером ((kg)). Обычно к выходной щине каскада 10 подключается БОУ 7, который вычисляет строчки HI,, где k, 2,..., Гг-1. Для вычисления Яо на время обмена к выходной шине каскада 10 через переключатель выходов усилителей 9 подключается БОУ 8.

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

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

На блок-схемах применены те же обозначения отдельных каскадов, что и на фиг. 1 и 2, а также введены следуюниге дополнительные каскады: 17 - переклю чателп третьей группы; 18-аналоговые сдвигающие регистры третьей группы; 19 - бло-к нача,льной установки.

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

Входные данные от устройства, выполняющего прямое БНФ, поступают в требуемом порядке, в то время как выходные результаты, как правило, требуется получать в естественном порядке. Поэтому аналогозьге с.Твигаю.щие регистры первой группы 3 и переключатели первой группы 2, выполняюни1е круговую перестановку, включены носле переключателя выходов уснлптелей 9. По окончании HepecTanoiBKH требхется выводить даиные сразу из всех Г; аналоговых сдв 1гаюии1х регистров первой группы 3, но устройство имеет последОВательНый выход, поэтому да1нные предварительно переписываются в аналоговые регистры третьей группы 18 через переключатели третьей группы 17. Эти же регистры и переключатели служат для накопления входных данных неред вычислением.

Для выполнения иерестаиовки выходных сигналов управляющпе входы переключателей первой группы 2 соединены через первую комМутационную панель 6 с выходами счетчика управления перестановкой 11, так что его выход с номером 5 соединяется е управляющим входом переключателя первой группы с номером ((-0,5)). Для устанения дополнительной перестановки, возникшей при вычислений г,- 1 строк в одном БСУ, необходимо в начале получения каждой строки результатов

устанавливать счетчик -правлення перестановкой 11 в положение Xfl, где / - номер получаемой строки по порядку вычисления (состояпие счетчика управления обменом 14). Значение Xjl находится из уравиеиий: / (( - /А-,,)) ((/ - яО), если /.-/ Г; - I (( - - 1)) - Г; - 1, если /-г, - 1.

Эта начальная установка осуществляется блоком начальной установки 19, которое соединено с выходами счетчика управления обменом 14, считающего импульсы с щины 16 е частотой, равпой Кроме того, к последнему выходу этого счетчика подключены управляющ:ие входы переключателей 4. Счетчик 14 вырабатывает также импульсные сигналы для шины 15 с частотой, равной fKB/-Ri i.

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

f((q))-Fo ;S /((е )).

, - ;

где

и W ехр(2кг /-,).

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

Д .Я использования в }стройстве с размером выборки или расположением каска.зов достато --ю заменить первую комм та1иоииую панель 6, .поставить ана чоговые сдвигающие регистры соответствующей

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

П р е л м е т и з о 5 ,) т е п и я

Устройство для вь;|лолиенпя быстрого иреобразовяния Фурье, содерл- ащее каскады, каждый из которых содержит две группы аналоговых сдвигающих регистров и перекчючате.чей, коммутационные панели, переключатель выходов усилителей, счетчики, блоки опотсмиюппых ус11литсле:|, о т л и ч а ю ni, е с с я ТИМ, чтэ, с целью со.кращеиия оборх довапи

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

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

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

71

Фиг. 7