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

 

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

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

Сою» Советсиик

Социалистмчасииа раснубиии

< 940168 (6I ) Дополнительное к авт, свил-ву (51) М. Кл.

@06 F 18/332 (22)Заявлено 02.03..80(21) 2863056/18-24 с присоединением. заявки И

9вударстеа««М кем«тет

СССР ае делам «эобрете««й

«вткрмт«й (23) П риоритет

Опубликовано 30.06.82. Бюллетень № 24

Дата опубликования описания 01.07.82 (53) УД К681. .3(088.8) !

В. М. Ерухимович, Б. Ж! Зелкин и В..Г. Казаков

) 6 (72) Авторы изобретения (71) Заявитель (54} УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО

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

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

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

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

Наиболее близким по технической сущности к предлагаемому является итеративный процессор, содержащий счетчик итерапий, М/2 решающих блоков, каждый из которых содержит четыре регист- о ра, причем выходы дейстннтельной и мнимой частей первого результата 2 1-го и (2 1 + 1)-го решакапнх блоков (* 0 - т/4) подключены к входам дей2

:ствнтельной и мнимой частей соответственно первого и второго операндов j -го решающего блока, выходы действительной и мнимой частей второго результата 2 го и (2 + 1)-го решаюших блоков подключены к sxopaM действительной и мнимой частей соответственно первого и второго операндов (1 + М /4)-го решающего блока, входы действительной и мнимой частей первого и второго отсчетов ,0-го (,ст 0 - И/2 - 1) решающего блока являются 2,ц-м и (2,О+ 1)-м информационными входами ус гройства $ 2).

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

KOQ Й, где N - число входных отсчетов, что повышает быстродействие пропессора. В каждом решающем блоке выполняются арифметические операпии над комплексными числами. Однако блоки являются сложными устройствами и содержат наборы регистров, сумматоров, логических

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

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

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

ИЛИ, два сумматора по модулю два, три элемента И, а в каждом решающем блоке - два селектора, четыре блока равно значности, четыре элемента И-ИЛИ, четыре счетчика, четыре элемента ИЛИ, четыре коммутатора, причем выходы разряДов реккурентного регистра сдвига подключены к входам первого и второго сумматоров по модулю два и к входам первого и второго 6локов элементов И, выход первого блока элементов И подключен .к входу счетчика итераций и к входу 6лока элементов ИЛИ, прямой вы« ход первого сумматора по модулю два подключен к первым входам первого и второго элементов И, инверсный выход первого сумматора по модулю два — к первому входу третьего элемента И, пря мой выход второго сумматора по модулю два подключен к вторым входам первого и третьего элементов И, а инверсный вы ход второго сумматора по модулю двак второму входу второго элемент® И, выход счетчика Итераций подключен к уп равляюшим входам селекторов каждого решающего блока, 8 выход блока элементов ИЛИ вЂ” к информационным входам селекторов, первые входы первого и второго блоков равнозначности в каждом решающем 6локе подцпочены к входу действительной части первого операнда решающего 6лока, первые входы третьего и четвертого блоков равнозначности подключены к входу мнимой части первого операнда решающего блока, вторые входы первого и четвертог о блоков равнозначности подключены к выходу первого селектора, а вторые входы второго и третьего блоков равнозначности - к выходу второго селектора соответствующего решаютцего блока, выходы первого, второго и третьего элементов И подключены к первым входам первой, второй и третьей групп элементов И-ИЛИ всех решающих блоков, вход действительной части второго операнда в каждом решающем 6локе подипочен к вторым входам первой группы первого и второго элементов И-ИЛИ, вход мнимой части второго операнда - к вторым входам первой группы третьего и четвертого элементов И-ИЛИ, прямой и

0188 4 инверсный выходы первого блока равнозначности в каждом решающем блоке подклточены к вторым входам второй группы соответственно первого и второго элеменТоВ И-ИЛИ, прямой и инверсный 13blxollbI второго блока равнозначности подключены к вторым входам второй группы соответственно третьего и четвертого элеме-..тов И-ИЛИ, прямой и инверсный выход

l î третьего блока равнозначности подключены к вторым входам третьей группы соответственно первого и второго элементов

И-ИЛИ, прямой и инверсный выходы четвертого блока равнозт:.ачности подключены

1 к вторым входам третьей группы соответственно третьего и четвертого элементов

И-ИЛИ, выходы элементов И-ИЛИ в каждом решающем блоке подключены к входам соответствующих счетчиков, выходы . го которых подключены к первым входам соответствуюших элементов ИЛИ, вторые входы первого и третьего элементов ИЛИ являются соответственно входом дейст» вительной и мнимой частей первого от2s счета, а вторые входы второго и четвертого элементов ИЛИ - соответственно входом действительной и мнимой частей второго отсчета решающего блока, выходы элементов ИЛИ подключены к входам щ соответствующих регистров, выходы которых являются информационными выходами решающего блока и подключены к информационным входам соответствующих коммутаторов, управляющие входы

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

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

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

Устройство содержит реккурентный регистр 1 сдвига; два блока 2 и 3 элементов И, блок 4 элементов ИЛИ, два сумматора 5 и 6 по модулю два, три элемента И 7 - 9, счетчик 10 итераций, М/2 решающих блоков 11, каждый из которых содержит два сетектора 12 и

13, четыре блока 14 - 17 равнозначности, четыре элемента И-ИЛИ 18-21, четыре счетчика 22-25, четыре элемента ИЛИ 26 - 29, четыре регистра 30ЗЗ, четыре коммутатора 34 - 37. Р" =Е (1" ") Р

Выходы 40 и 41 действительной и мнимой частей первого и второго отсчетов p --ro (,0 0 - .N/2 - 1) решающего блока являются 2,О -м и 2 A+ 1-м

5 94.016

Решающий блок ll имеет две пары входов 38 и 39 и двс пары выходов

40 и 41 для связи с другими решающими блоками, две пары входов 42 и 43 для подключения источников комплексных от- s

1 счетов, две пары выходов 44 и 45 дпя комплексных выходных отсчетов.

Выходы 40 действительной и мнимой частей первого результата 2 -го и (2 + 1)-го решающих блоков (л - ..!О

= 0 - N/4) подключены к входам 38 и

39 действительной и мнимой частей соответственно первого и второго операндов 1-го решающего бпока, выходы 41 действительной и мнимой частей второго 1S результата 2 i -го и (2 1 + 1)-го решающих блоков подключены.к входам 38 и 39 действительной и мнимой частей соответственно первого и второго операндов (ri + Й/4)-го решающего блока. 2О

Выходы разрядов реккурентного регистра 1 сдвига подключены к входам блоков

2 и 3 элементов И, выход блока 2 элементов И .2 подключен к входу счетчика

10 итераций и к входу блока 4 элементов ИЛИ. Прямой выход сумматора 5 по модулю два подключен к первым входам элементов И 7 и 9, инверсный выход сумматора 5 по модулю два — к первому входу элемента И 8. Прямой выход 3О сумматора 6 по модулю два подключен к вторым входам элементов И 7 и 8, а инверсный выход сумматора 6 по модутп два - к второму входу элемента

И 9. Выход счетчика 10 итерапий подклю-З5 чен к управляющим входам селекторов

12 и 13 каждого решающего блока, а выход блока 4 элементов ИЛИ - к информационным входам селекторов 12 и

13, Первые входы блоков 14 и. 17 равно щО значности s каждом решающем блоке подключены к входу действительной части первого операнда решающего блока, первые входы блоков 15 и 16 равнозначности подключены к входу мнимой части 45 ,первого операнда решающего блока, Вторые входы блоков 14 и 16 равнозначности подключены к выходу селектора 12, а ,вторые входы блоков 15 и 17 равнозначности — к выходу селектора 13 соответствующего решающего блока. Выходы элементов И 7 — 9 подключены к первым входам первой, второй и третьей групп элементов И-ИЛИ 18 - 21 всех решаюших блоков, вход действительной части второго операнда в каждом решающем блоке подключен к вторым входам первой грутты элементов И-ИЛИ 18 и 20, вход мнимой части второго операнда - к вто8 6 рым входам первой группы элементов

И-ИЛИ 19 и 21. Прямой и инверсный . выходы первого блока 14 равнозначности подкпючены к вторым входам второй группы соответственно элементов ИИЛИ 18 и 20, прямой и инверсный выходы второго блока 17 равнозначности йодключены к вторым входам второй группы соответственно элементов И-ИЛИ 19 н

2l. Прямой и инверсный выходы блока

15 равнозначности подключены к вторым входам третьей группы соответственно элементов И-ИЛИ 18 и 20, прямой и инверсный выходы блока 16 равнозначности подключены к вторым входам третьей группы соответственно элементов

И-.ИЛИ. 19 и 21. Выходы элементов ИИЛИ 18 - 21 в каждом решающем блоке подключены к входам соответствуюпих счетчиков 22 — 25, выходы которых подключены к первым входам соответствующих элементов ИЛИ 26 — 29.

Вторые входы элементов ИЛИ 26 и

27 являются соответственно входом дейСтвительноФ и мнимой частей первого отсчета, а вторые входы элементов ИЛИ 28 и.29 — соответственно входом действительной и мнимой частей второго отсчета решающего блока. Выходы элементов ЕЛИ 26 - 29 подключены к входам соответствующих регистров 30 — 33, выходы которых являются информационными выходами решающего блока и подключены к информационным входам соответствующих коммутаторов 34 — 37.

Управляющие входы коммутаторов 34

37 всех решающих блоков подключены к выходу блока 3 элементов И. Выходы коммутаторов 34 и 35 являются выходами действительной и мнимой частей первого результата, а выходы коммутато ров 36 и 37 — выходами действительной и мнимой частей второго результата соответствующего решающего блока.

В решающем блоке 11 реализуются базовые операции БПФ (4+4) (g) °, р„() " N(g 2- gg 2Ф+1 W т.де и - число отсчетов;

Д "1 -й комплексный отсчет в 1-ой итерапхпп

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

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

Регистр l сдвига, блок 3 элементов

И, комму гвторы 34 - 37, регистры 3033 образуют преобразователь двоичных чисел ф" регистров в псевдослучайные

44 последовательности.

Регистр 1 сдав, блок 2 элементов

И, селекторы 12 и 13, блок 4 элементов ИЛИ образуют формирователь экспоненцивльных коэффициентов БПФ Vl " .

Регистр 1 сдвига, сумматоры 5 и 6 по модулю два, элементы И 7 — 9 составляют формирователь несовпвдвюших псевдослучайных последовательностей 20 для представления весовых коэффшиентов при реализации операции сложения с помошью элек.ентов И-ИЛИ 18 — 21.

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

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

Для обеспечения модуля коэффициента корреляции порядка 2 " последовательностей на входах блоков 14 — 17 равнозначности входы у,-го элемента И 2 (V = 1, 2 ... Ч вЂ” 1) щжсоединены к (К + 1)-у и (< — + 1)-м инверсным выходам разрядов регистра l сдвига 40 ((= 1, 2 ... k), а входы К-гоэле» мента И 3 присоединены к (и - К )-м прямому и(М вЂ” К + 0 )-м инверсным выходам разрядов регистра 1 сдвига, Счетчики . 22 — 25, число разрядов 45 которых равно И, образуют преобразоватоли последовательностей в двоичные коды. 3 и -разрядных регистрах 30 - 33 хранятся двоичные коды. входных отсчетов или результаты вычислений в итера- 50 циях. 1io коду счетчика итераций 00...0 решаюшие блоки 11 через входы 42 и

43 подключаются к двум источникам входных комплексных цифровых отсчетов, номера которых определяются двоично-ин55 версной перестановкой кода порядкового номера М (М = О, 1 ..., N — 1) этих источников без инверсии младшего раз» ряда кода но 1ерв. Указанная схема соеди68 8 нений решающих блоков позволяет использовать регистры 30 — 33 для хран ния ,входных отсчетов и результатов вычис- лений в итерациях.

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

На выходах каждого разряда реккурентного регистра 1 генерируются псевдослучайные последовательности (М-последовательности), которые имеют период

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

2 — 1 тактов и математическим ожиданием, пропорциональным 2 (р = 2, ° ° ° ) °

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

Последовательности с выходов элементов И 2 поступают на входы элементов

1ИЛИ 4, на выходах которых формируются последовательности, математическое ожидание которых пропорционально значениям 9jPj, М-последовательности с выходов разрядов регистра 1 сдвига поступают на входы сумматоров 5 и 6 по модулю двв, нв выходах которых образуются M-последовательности, сдвинутые относительно разрядных последовательностей регистра

1 сдвига. Эти последовательности поступают на входы элементов И 7 — 9.

С помошью блоков 14 - 17 равнозначности выполняк гся операции умножения переменных, представленных псевдослучайными последовательностями, коэ ффицнент взаимной корреляции которых равен 2 . Эти последовательности поступают на входы блоков 14 — 17 равнозначности с выходов селекторов 12 и

l3 и входов 38 решающего блока. На первые входы И элементов И-ИЛИ 1821 поступают последовательности с выходов блоков 14 - 17 равнозначности и с входов 39 решающего блока, на вторые входы И - несовместные последователыости с выходов элементов И 7-9. .с

Последовательности с выходов элементов И-ИЛИ 18 — 21 поступают в

9 940 168 10 с етчяии 22 - 25, в которых воспроиз- полнения БПФ сокращаются ПТимерно в водится в двоичном коде результат ба- трн раза по сравиению с известным зовых вычислений в соответствии с (1).

В устройстве за Ь(г Й итераций осуществляется параллельная обработка s Ф о р м у л а и з о б р е т e H H II г отсчетов по алгоритму (1). С помощью селекторов 12 и 13 s соответ- Устройство для выполнения быстрого ствии с кодом счетчика 10 итераций преобразования Фурье, содержашее счегвыбираются требуемые дпя данной ите- чик нгерацнй, К/2 рещакапих блоков рации коэффщиеиты Ф " 1о (й - порядок преобразования), каждый

В первой итерации производится обра- из которых содержит четыре регистра, ботка входных отсчетов, которые зано- причем выходы действительной и мним и мнимой сятся в регистры 30 - 33. В. последую- частей первого результата 2 4 -го и ших итерациях производится обработка (2.1 + 1)-го решаюших блоков ( результатов предыдуших итераций. „1s 0 - й/4) подключены к входам дейЗа время одной итерации, равное 2 -1 ствительной и мнимой частей cocrmåòñò. тактов, комплексные отсчеты„храняшие- венно первого и второго операндов 1 -го, ся в регистрах 30-33, преобразуются решаюшего бпока, выходы действительв псевдослучайные последовательности, ной и мнимой частей второго результата которые через выходы 40 и 41 и входы ?II 2 4 -го и (2 1 +1)-го решаюпшх блоков

38 и 39 решающих блоков поступают подключены к входам действительной и на входы блоков 14 - 17 равнозначнос- мнимой частей соответственно первого и т и и входы элементов И-ИЛИ 18 - 21. второго операндов (I + > /4(-го Решаюельной и мниРезультат арифметических операций, шеГО блокар ВхОды действитепьнОй и выполняемых с помошью этих элементов, 25 IIog частей первого и ВтОРОгО отсчетов декодируется счетчиками 22 — 25 за,О го (ц = 0 - М/2 - 1) решаюш.его время итерацют. блока являются 2 р-м и (2p + 1) -м

В момент окончания итерации двоич- информационными входами устройства, ный код счетчиков 22 - 25 через эле- о т л и ч а ю 1ц е е с я тем, что, с менты ИЛИ 26 - 29 переписывается в зо целью упрощения устройства, оно содержит егистры 30 - 33 и счетчики 22 — 25 реккурентный регистр сдвига, два блока

Ре и устанавливаются в исходное состояние. элементов И, блок элементов, дв

Си пере и в perH I и y o c по моду ю д, три жемеа ки в исходные состояния счетчиков могут И, а в каждом решающем блоке - два себыть органнзОваны, например, как коньюк- лектора, четьГре блОка равнозначнос-"Гиэ ции импульса с выхода (и-1)-го эле- четыре элемента И-ИЛИ, четыре счетчика, мента И 2 и прямого и инверсного им- четыре элемента ИЛИ, четыре коммутапульсов тактов. B последней итерацни тора, причем выходы разрядов реккурентв регистрах формируются комплексные ного регистра сдвига подключены к вхоabmomIbIe отсчеты, время выполнения ал- 4„дам. первого и второго сумматор по гОритма БПФ модулю два и к входам первого и второго т=го блоков элементов И, выход первого блоТ =ГОАР (2 )) C (2) ка элементов И подключен к входу счетгде Г - длительность тактовых импульсов. чика итераций и к ду и и к вхо элементов ИЛИ, Введение реккурентного регистра сди - 4> прямой ерв ямой выход и ого сумматора по мога, групп элементов», сучжаторов пе вого и вто го элементов И., инвероный выход первого сумматора по модулю ных чисел в псевдослучайные последовательности, реализация решаюших блоков два — P мУ Р ва — к пе вому входу третьего элемента И, прямой вьmод второго сумматора устройства и схемы их соединений в соот» по модно два подключен к вторым входам ветстшпл с изобретением позволяет исключить из решающих блоков сложные и Рв гР Р пе о и третьего элементов И, а иннабо еги, сумматоров, логичес- версный выход второго сумматора по модупо два - к второму входу второго ких схем и, тем самым, существенно элемента И, выход счетчика итераций упро g po ° стить ст и ство. подключен к управляюиптм входам селекто*

П анни одинаковой элеменч ров каждого решающего блока, а выход ным входам селекгоров, первые входы ение предлагаемого устройства для вы11 9401 пс ртюго и второго блоков равнозначности в каждом решающем блоке подключены к входу действителыюй части первого

Операнда решающего блока, первые входы трстього H четвертого блОкОВ pGBHo 5 значнОС Ги подключены K Bxo мнимОЙ част первого операнда рлиаюшего блока, вторые входы первого и четвертого блоков равнозначносчМ подключены к выходу первого селектора, а вторые входы tp второго и третьего блоков равнозначности — к выходу второго селектора соответствующего решающего блока, выходы первого, второго и третьего элементов

И ?подключены к первым входам первой, второй и третьей трупп элементов И-ИЛИ всех решаюших блоков, вход действительной части второго операнда в каждом решающем блоке подключен к вторым

ВхОдам и ерВОЙ группы перВОгО и Второго gp элементов И-ИЛИ, Вход мнимой части второго операнда - к вторым входам первой грутпты третьего и четвертого элементов И-ИЛИ, прямой и инверсный выходы первого блока равнозначности в . каждом решаюшем блоке подключены к вторым входам второй группы соответственно первого и второго элементов

И-ИЛИ, прямой и инверсный выходы второго блока равнозначности подключены к вторым входам второй грутпты соответственно третьего и четвертого элементов

И-ИЛИ, прямой и инверсный выходы треть его блока равнозначности подключены к вторым входам третьей грутты соответ35 ственно второго и п<.рвого элементов

68 12

И-ИЛИ, прямой и инверсный выходы четВертого блока равнозначности подключены к вторым входам третьей группы соответственно третьего и четвертого элементов И-ИЛИ, выходы элементов И-ИЛИ в каждом решающем блоке подключены к входам соответствующих счетчиков, вь ходы которых подключены к первым входам соответствующих элементов ИЛИ, вторые входы первого и третьего элементов ИЛИ являются соответственно входом действительной и мнимой частей первого отсчета, а вторые входы второго и четвертого элементов ИЛИ вЂ” соответственно входом действительной и мнимой частей второго отсчета решающего блока, выходы элементов ИЛИ подключены к входам соответствуюпих регистров, выходы которых являются информационными выходами решающего блока и подключены к информапионным входам соответствующих коммутаторов, управляющие входы коммутаторов всех решающих блоков подключены к Выходу второго блока элементов И, выходы первого и третьего коммутаторов являются выходами действительной. и мнимой частей первого результата, а выходы второго и.четвертого коммутаторов — выходами действительной и мнимой частей второго результата соответствующего решающего блока. . Источники информапии, принятые во внимание при экспертизе

1. Электроника", 1968, % 13, с. 3.

2. "Зарубежная радиоэлектроника", 1975, No 9, с. 87 (прототип).

940168

etc

Составитель В. Байков

Редактор С. Крупенина Tezpep И. Гергель Корректор М. Коста

Заказ 4669/71 Тираж 731 Подписное . ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

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

Филиал ППП »Патент » г. Уиа ород, ул. Проектная, 4