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

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

Известны специализированные вычислители дая реализации БПФ, которые выполняются как однопроцессорные цифровые машины . l .

Указанные вычислители характеризуются наличием -одного арифметического уст- Q ройства и последовательной процедурой выполнения вычислений. Быстродействие этях. устройств низкое и ограничено их пропускной способностью и временем выполнения одной базовой операции.

Наиболее близким по технической суцшости к предлагаемому $тляется итеративный процессор, содержащий счетчвск итерации, N/2 решающих блоков, каждый из которых содержит четыре регист- 20 ра, причем выходь.1 действаительной и мнимой частей первого результата 2 -гo и (2 -i + 1)-го решающих блоков ( - t о - К/4) подключены к входам Дей.ствительной и мнимой частей соответственно n JBoro и второго операндов i -ix решающего блока, выходы действительной и мнимой частей втсфого резутштата 2 i го и (21+ 1)-го раиаюших блоков подключены к входам действительной к мннмой частей соответственно первого и второго операндов ( -i + N /4)-го решающего блока, входы действительной я мнимой частей первого и второго отсчетов /и-го (// О - N/2 - 1) решающего блока являются 2 /|-м и (2 + 1)-м инфсфмационными входами устройства L 2J.

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

схем, обеспечивающих вьтопнение арифметических операций.

Цепь изобретения - упрощение устрой ства.

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

инверсный выходы первого блока равнозначности в каждом решающем блоке подключены к вторым входам второй группы соответственно первого и второго элементов И-ИЛИ, прямой и инверсный вьссоды второго блока равнозначности подключены к вторым входам второй группы соответственно третьего и четвертого злеме-;тов И-ИЛИ, прямой и инверсный вьпсоды 10 третьего блока равноаначности подключены к вторым входам третьей группы соответственно первого и второго элементов И-ИЛИ, прямой и инверсный выходы чет вертого блока равнозначности подключены 15 к вторым входам третьей группы соответственно третьего и четвертого элементов И-ИЛИ, выходы элементов И-ИЛИ в каждом решающем блоке подключены к вхо дам соответствующих счетчиков, выходы . 20 которых подключены к первым входам соответствующих элементов ИЛИ, вторые входы первого и третьего элементов ИЛИ являются соответственно входом действительной и мнимой частей первого от25 счета, а вторые входы второго и четвертого элементов ИЛИ - соответственно входом действительной и мнимой частей второго отсчета решающего блока, выходы элементов ИЛИ подключены к входам 30 соответствующих регистров, выходы которых являются информационными выходами решающего блока и подключены к информационным входам соответствующих коммутаторов, управляющие входы ,j коммутаторов всех решающих блоков подключены к выходу второго блока длементов И, выхода1 первого и третьего коммутаторов являются выходами действительной и мнимой частей первогю редц эупьтата, а выходы второго и четвертого коммутаторов - выходами действительной и мнимой частей второго результата соответствукнцего решающего блока.

На чертеже представлена блок-схема

45 . устройства.

Устройство реккурентный регистр 1 сдвига два блока 2 и 3 элементов И, блок 4 элементов ИЛИ, два

сумматора 5 и 6 по модулю два, три элемента И 7-9, счетчик 1О итераций,

N/2 решающих блоков 11, каждый из которых содержит два селектора 12 и 13, четыре бпока 14 - 17 равнозначности, четьфе элемента И-Р1ЛИ 18-21, четьфе счетчика 22-25, четыре элемента ИЛИ 26 - 29, четьфе регистра 3033, четыре коммутатора 34 - 37. . 5&4 Решающий блок 11 имеет две пары входов 38 и 39 и две; пары выходов 40 и 41 для связи с другими решающими блоками, две пары входов 42 и 43 д подключения источников комплексных отсчетов, две пары выходов 44 и 45 Для комплексньк выходных отсчетов. Выходы 4О действительной и мнимой частей первого результата 2 и ( + 1)-го решающих блоков ( .- О - N/4) подключены к входам 38 и 39 действительной и мнимой частей соответственно первого и второго операндов -го решающего блока, выходы 41 действительной и мнимой частей второго результата. 2 1-го и (2 -i + 1)-го решаюших блоков подключены к входам 38 и 39 действительной, и мнимой частей соответственно первого и второго операн дов ( -i + N/4)-го решающего блока. Выходы разрядов реккурентного оегис ра 1 сдвиг а подключены к входам блоков 2 и 3 элементов И, выход блока 2 элементов И 2 подключен .к входу счетчика 10 итераций и к входу блока 4 элементов ИЛИ. Прямой выход сумкатора 5 по модутпо два подключен к первым входам элементов И 7 и 9, инверсный выход сумматора 5 по модулю два - к первому входу элемента И 8. Прямой выход сумматора 6 по модулю два подключен к входам элеме гов И 7 и 8, а инверсный выход сумматора 6 по модулю-два - к второму входу элемента И 9. Ш,1ход счетчика 1О итераштй подкл чен к управляющим входам селекторов 12 и 13 каждого решающего блока, а выход блока 4 элементов ИЛИ к информационным входам селекторов 12 и 13. Первые входы блоке® 14 и. 17 равн значиости в каждом решающем блоке подключены к входу действительной част первого операнда решающего блока, первые входы блоков 15 и 16 равнозначности подключены к входу мнимой части .первого операнда решающего блока. Вторые входы блоков 14 и 16 равнозначнос подключены к выходу селектора 12, а ;Вторые входы блоков 15 и 17 равнознач ности - к выходу селектора 13 соответствуюшего решающего блока. Выходы . элементов И 7 - 9 подключены к первым входам первой, второй и третьей групп элементов И-ИЛИ 18 - 21 всех решающих блоков, вход действительной части второго операнда в каждом решающем блоке подключен к вторым входам первой грутаты элементов И-ИЛИ 18 и 20, вход мнимой части второго операнда - к втоS .6 рым входам первой группы элементов И-ИЛИ 19 и 21. Прямой и щверсасыЯ . выходь первого блока 14 равнозначности подключены к вторым входам второй группы соответственно элементов ИИЛИ 18 и 20, прямой и инверсный выходы второго блока 17 равнозначности йодключ еяы к вторым входам второй грушты соответственно элементов И-ИЛИ 19 и 21. Прямой и инверсный выходы блока 15 равнозначности подключены к вторым входам третьей группы соответственно элементов И-ИЛИ 18 и 20, п рямой и инверсный выходы блока 16 равнозкачности подключены к вторым входам третьей группы соответственно элементов Ит-ИЛИ 19 и 21. Выходы элементов ИИЛИ 18 - 21 в каждом решающем блоке подключены к входам соответствующих счетчиков 22 - 25, выходы которых подключены к первым входам соответствующих элементов ИЛИ 26-29. Вторые входь элементов ИЛИ 26 и 27 являются соответственно входом дейртвнтельно и мнимой частей первого от;счета, а вторые входы элементов ИЛИ 28 и-29 - соответственно входом действительной .и мнимой частей второго отсчета рет1ающего блока. Выходы элементов ИЛИ 26-29 подключены к входам соответствукнцих регистров 30 - 33, выходы которых являются информационнь1ми выходами решающего блока и подключены к информационным входам соот етствующих коммутаторов 34-37. Управляющие входы коммутаторов 34 37 всех решающих блоков подключены к выходу блока 3 элементов И. Выходы коммутаторов 34 и 35 являются выхо действительной и мнимой частей первого результата, а выходы коммутато ров 36 и 37 - выходами действительной и мнимой частей второго результата соответствующего решающего блока. В решающем блоке 11 реализуются базовые операции БПФ .,.,wN , 2 где N - число отсчетов; А -и ко1лш1ексный отсчет в i-ой / игерацищ ; ..ej( Выходы 4О н 41 действтепьной и мнимой частей первого и второго отсчетов /; -го ( О - .N/2 - 1) решающего блока являются 2 XJ -м и 2 /tt+ 1-м

информационными нжодами 38 и 39 уст ройства.

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

Регистр 1 сдвига, блок 3 элементов И, коммутаторы 34 - 37, регистры 30 33 образуют преобразователь двоичных чисел регистров в псевдослучайные последовательности

Регистр 1 сдвига, блок 2 элементов И, селекторы 12 и 13, блок 4 элементов ИЛИ образуют формирователь экспоненциал1.ных коэффициентов .

Регистр 1 сдвига, сумматоры 5 и 6 по модулю два, элементы И 7 - 9 составляют формирователь несовпадающих псевдослучайных последовательностей

для представления весовых коэффигояентов при реализации операции сложения с помощью элементов И-ИЛИ 18 - 21.

Для обеспечения модуля коэффшдаента корреляции порядка 2 на входах элементов И-ИЛИ 18-21 входы сумматора 5 по модутло два подключены к выходам всех разрядов регистра 1 сдвига, а входь cyivnviaTopa 6 по модутпо два подключены к нечетным вьЕходгм разрядов регистра 1 сдвига.О

Блоки 14 - 17 равнозначности составляют умножители.,,

Для обеспечения модуля коэффициента корреляции порядка 2 последовательпостей на входах блоков 14 - 17 равнозначности входы к-го элемента И 2 (К 1, 2 ... VI- 1) присоединены к ( К + 1)-у и ( - + 1)-м инверсным . выходам разрядов регистра 1 сдвига

( К 1, 2 ... 1( ), а входы К -го элемента И 3 присоединены к { и - k )-м прямому и( V1-K+C )м инверсным выходам разрядов регистра 1 сдвига.

Счетчики 22 - 25, число разрядов которых равно И , образуют преобразователи последовательностей в двоичные коды. В VI -разрядных регистрах 30 - 3 хранятся двоичные коды входных отсчетов или результаты вычислений в Итерациях. По коду счетчика итераций ОО...О решающие блоки 11 через входы 42 и 43 подключаются к двум источникам вхоных кокплексыых цифровых отсчетов, номера которых определяются двоично-инверсной перестановкой кода порядкового номера М (М О, 1 ... , N- 1) этих источников без Kfroepciffi младшего разряда кода номере. Указанная схема соеднений рещаюшЕХ блоков позволяет использовать регистры 30-33 для хранения , входных отсчетов и результатов вычислений в итерациях.

Устройство работает следующим образом.

На выходах каждого разряда реккурентного регистра 1 генерируются псевдослучайные последовательности (М-послсдоватеяьности), которые имеют период {2 - 1) тактов и математические ожидания, пропорциональные 1/2. Эти последовательности поступают на входы элементов И 2 и 3, на выходах которых образуются последовательности с периодом 2-1 тактов к математическ.им ожиданием, пропордлональным (р 2, ... V.).

Последовательности с выходов элементов И 3 поступают -на первые входы коммутаторов 34 - 37, к вторым входам которых подключены выходы разрядов регистров 30 - 33. На выходе коммутаторов 34-37 формируются псевдослучайные последовательности, математическое ожидание которых пропорционально содержимому соответствующих регист-ров.

Последовательности с выходов элементов И 2 поступают на входы элементов |ИЛИ 4, на выходг1х которых формзфукп ся последовательности, математическое ожидание которых пропорционально значениям W,

М-последовательности с выходов разрядов регистра 1 сдвига поступают на входы сумматоров 5 и 6 по модулю два, на выходах которых образуются М-последовательностн, сдвинутые относительно разрядных последовательностей регистра 1 сдвига. Эти последовательности поступают на входы элементов И 7 - 9.

С помощью блоков 14 - 17 равнозначности выполн5потся операции умножения переменных, представленных псевдослучайными последовательностями, коэффициент взаимной коррел1ЩШ1 которых равен 2 . Эти последовательности поступают на входы блоков 14-17 равнозначности с выходов селекторов 12 и 13 и входов 38 рещающегх) блока. На первые входы И элементов И-ИЛИ 18 21 поступают последовательности с выходов блоков 14-17 равнозначности и с входов 39 решающего блока, на вторые входы И - несовместные последовательности с выходов элементов И 7-9.

-

Последовательности с выходов элементов И-ИЛИ 18 - 21 поступают в счетчшш 22 25, в которых воспрои водЕРГся в двоичном коде результат базовых вычислений в соответствии с (1) В уегройстве за 6о N итераций осуществляется параллельная обработка N отсчетов по алгоритму (1). С помощью ceneicrqpoB 12 к 13 в соответствии с кодом счетчика 1О итераций выбираются требует 1ые дня данной итерации коэффициенты . В пертой итерации производится обра . ботка входных отсчетов, которые заносятся в регистры ЗО - 33. В. последующих итерациях производится обработка результатов предыдущих итераций, За время одной итерации, равное 2 тактов, комплексные отсчеты, хранящие- , ся в регистрах 30-33, преобразуются в псевдослучайные последовательности, котсфые через выходы 40 и 41 и входы 38 и 39 роиающих блоков поступают на входы блоков 14-17 равнозначности и входы элементов И-ИЛИ 18 - 21. Результат арифметических операций, выполняемых с помощью этих элементов декодируется счетчиками 22 - 25 зе время итерации. В момент окончания итерации двоичны и код счетчиков 22-25 через элементы ИЛИ 26-29 переписывается в регистры 30 - 33 и счетчики 22 - 25 устанавливаются в исходное состояние. Сигналы переписи в регистры и установ ки в исходаые состояния счетчиков мог бы1Ъ организованы, например, как конью щш импульса с выхода ( vi-l)-ro элемента VI 2 к прямого и инверсного импульсов тактов. В последней итерации в регистрах формируются комплексные выходные отсчеты, время выполнения ал горитма БПФ T--eog;2.N(,(2) где Т - длительность тактовых импульс Введение реккурентного регистра сдв га, групп элементов И-ИЛИ, сумматоров ho модулю два для. преобразования двоич ных чисел в псевдослучайные последовательности, реализация решающих блоков устройства и схемы их соединений в соо ветствии с изобретением позволяет исключить из решающих блоков сложные наборы регистров, сумматоров, логичеоких схем и, тем самым, существенно упростить устройство. При использовании одинаковой элемен ной базы аппаратурные затраты на постр ение пр длагаемого устройства для выполнения БПФ сокращаются примерно в три раза по сравнению с известным. Формула изобретения Устройство ягея выполнения быстрого преобразования Фурье, содержащее счетчик игерапий, N/2 реихаюших блоков { N - порядок преобразования), каждый из которых содержит четыре регистра, причем выходы действительной и мнимой частей первого результата 2 1 -го и (2 i + 1)-го решающих блоков ( О - N/4) подключены к входам действительной и мнимой частей соответственно первого и второго операндов I-ro рещающего блока, выходы действительной и мнимой частей второго результата 2 4 -то и (2 i +1)-го рещаюпшх блоков подключены к входам действительной и К1нимой частей соответственно первого и второго операндов ( ч + N /4(-го решающеххэ блока, входы действительной и мнимой частей первого и второтчэ отсчетов -го ( N/2-1) рещаюшего блока являются 2 дд-м и (2/4 + 1)-м информационными входами устройства, отличающееся тем, что, с целью упрощения устройства, оно содержит реккурентный регистр сдвига, два блока элементов И, блок элементов ИЛИ, два сумматс за по модулю два, трк элемента И, а в каждом решающем блоке - два селектора, четыре блока равнозначности, четьфе элемента И-ИЛИ, четыре счетчика, четьфе элемента ИЛИ, четьфе коммутатора, причем выходы разрядов реккурентгного регистра сдвига подключены к входам, первого и второго сумматоров по модулю два и к входам первого и второго блоков элементов И, выход первого блока элементов И подключен к входу счет чика итераций и к входу элементов ИЛИ, прямой выход первого сумматора по модулю два подключен к первым входам первого и второго элементов И, инверсный выход первого сумматора по модулю два - к первому входу третьего элемента И, прямой выход второго сумматора по модулю два подключен к вторым входам первогр и третьего элементов И, а инверсный выход второго сумматора по модулю два - к второму входу второго элемента И, выход счетчика итераций подключен к управляющим входам селекторов каждого решающего блока, а выход блока элементов ИЛИ - к информационным входам селекторов, первые входы п р1юго и второго блоков равнозначности в каждом решающем блоке подключены к входу дейстнитеяыгой части первого операнда решающего блока, первые входы третьего л четвертого блоков равно3}ia4Hocrra подключены к входу /пшмой части первого операнда решающего блока вторые входы первого и четвертого блоков ровнозначностя подключены к ду первого Селектора, а вторые входы второго и третьего блоков равнозначности - к выходу второго селектора соотвеггствующего решающего блока, выходы первого, второго и третьего элементов И 11одключе1аз1 к первым входам первой, второй и третьей групп элементов И-И7Ш всех решающих блоков, вход действитель ной части второго операнда в каждом решающем блоке подключен к вторым входам первой группы первого и второго элементов И-ИЛИ, вход мнимой части второго операнда - к вторым входам первой группы третьего и четвертого элементов И-ИЛИ, прямой и инверсный выходы первого блока равнозначности в . каждом решающем блоке подключены к вторым входам второй группы соответственно первого и второго элементов И-ИЛ1-1, прямой и инверсный выходы вто porxj блока равнозначности подключены к вторым входам второй группы (роответ ственно третьего л ч€5твертого элементо И-ИЛИ, прямой и инверсный выходы тре его блока равнозначности подключены к вторым входам 1ретьей группы соответ- стве1шо второго и пс рвого элементов , прямой и штерсный выходы чет вертого блока равнозначности подключены к вторым входам третьей группы соответственно третьего и четвертого элементов И-ИЛИ, выходы элементов И-41ЛИ в каждом решающем блоке подключены к входам соответствутоших счетчиков, выходы которых подключены к первым входам соответствующих элементов ИЛИ, вторые входы первого и третьего элементов ИЛИ являются соответственно входом действительной и мнимой час-тей nefpBoro отсчета, а вторые входь второго и четвертого элементов ИЛИ - соответственно входом действительной и мш1мой частей второго отсчета решающего блока, выходы элементов ИЛИ подключены к входам соответствующих регастров, выходы которых являются информапзюннымн выходами решающего- блока и подключены к информационным входам соответствую.щих KOMN-iyTaTopOB, управляющие входы I ко1имутаторов всех решающих блоков подключен к выходу второго блока элементов И, выходы первого и третьего коммутаторов являются выходами действительной, и мнимой частей первого результата, а выходы второго и четвертого коммутаторов - выходами действительной и мнимой частей второго результата соответствующего решающего блока. .Источники 1шформаш1И, принятые во внима1Ше при экспертизе 1,Электроника, 1968, № 13, с. 3. 2. Зарубежная радиоэлектроника, 1975, № 9, с. 87 (прототип).

.«О

C

i .