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

 

1. УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее три входных регистра, регистр коэффициента, умножитель, регистр произведений, два коммутатора, первый сумматор-вычитатель, четыре регистра слагае1Ф:гх и блок управления, причем выход Первого KONwyTaTopa подключен к первому информационному входу первого сумматора-вычитателя, выход которого подключен к информационному входу первого регистра слагаемых инфо;рмационный вход регистра коэффициента является входом коэффициента устройства, о т л и ч аю щ е е с я тем, что, с целью упрощения устройства, otio содержит второй сумматор-вычитатель, причем информационные входы первого и второго входных регистров подключены к последовательному входу первого и йторого операндов устройства, выход первргр входного регистра подклюЧе |: к инфЬрмационнол4у входу третьего входного регистра, выход которого подключен к первым информационным входам первого и второго коммутаторов, выход .второго коммутатора подключен к первому информационному входу рторого сумиатора-вычитателя, выход второго входного регистра и выход регистра коэффициента подключены к входам умножителя, выход которого подключен к информационному входу регистра произведений, вшгод регистра произведений подключен к вторым информационньгви входам первого, и второго сумматоров-вычйтателей, выходы первого и второго сумматоров-вычитат лёй лодключены к информационнЕлл входг1м первого и второго регистров слагаемых соответственно, выходы первого и второго регистров слагавшее подключены к информационным входам , . Третьего и четвертого регистров елагаекых соответственно, выходы третьего и четвертого регистров слагаемых,f являкадиеся выходами Действительной i и мнимой частей результата устройстBai , подключены к вторым информациой-; ным входам первого и второго Kotmty- таторов соответственно, первый выход блока управления пoдкJяoчeн к yn,S равляквдйм входам первого и второго коммутаторов, второй и третий выходы блока управления подключены к управлякадим входам первого и второго сумматоров-вычйтателей соответственно , четвертый выход блока управления подключен к синхронизирунтшм входам регистра коэффициента, регистра произведений, первого, второго , третьего и четвертого регистров слагаемых, пятый выход блока управления подключ:ен к синхронизнрукхвему ВХОДУ первого входного регистра, , шестой выход блока управления подключен к синхрониз1фуюцим входам второго и третьего входных регистров .2 . Устройство по п. 1, о тли чающееся тем, что блок упрг1вления содержит генератор тактовых импульсов , счетчик, два элемента ИЛИ и элемент НЕ, причем вьрсод генератора тактовых импульсов подключен к

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

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

РЕСПУБЛИН (3% (И»

3(5В

15/33

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ЩНРЦТИЙ (21) 3395645/18-24 .(22) 23.12.81 (46) 30.05.83. Бюл. 9.20 (72) Ю.С. Каневский, С.Э.. Котов, Н.Е. Куц, Б.A. Некрасов и О.A. Федотов (71) Киевский ордена Ленина политехнический институт им. 50-летия Великой Октябрьской социалистической революции .(53) 681.3(088.8) (56) 1. Авторское свидетельство СССР

Р 399859, кл. G 06 F 7/38, 1971.

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

9 736113, кл. (06 F 15/332, 1977 (прототий) . (54) (57) 1 ..УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ

БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее три входных регистра, регистр коэффициента, умножитель, регистр произведений, два коммутатора, пер-. вый сумматор- вычитатель, четыре регистра слагаемых и блок управления, причем выход первого коммутатора подключен к первому информационному входу первого сумматора-вычитателя, выход которого подключен .к информационному входу первого регистра слагаемых, информационный вход регистра коэффициента является входом коэффициента. устройства, о т л и ч аю щ е е с я .тем, что, с целью упрощения устройства, оно содержнт второй сумматор-вычитатель, причем информационные входы первого и второго входных регистров. подключены к последовательному входу первого и второго операндов устройства, выход первого входного регистра.подключеН „к информационному входу третьего входного регистра, выход которого подключен к первым информационным. входам первого и второго коммутаторов, выход второго коммутатора подключен к первому информационному входу второго сумматора-вычитателя,.выход второго входного регистра и выход регистра коэффициента подключены к входам умножителя, выход которого подключен к информационному входу регистра произведений, выход регистра произведений подключен к вторым информационным входам первого и второго сумматоров-вычитателей, выходы первого и второго сумматоров-вычитателей подключены к информационным входам первого и второго регистров слагаемых соответственно, выходы первого и второго регистров слагаемых под- ключены к информационным входам третьего и четвертого регистров слагаемых соответственно, выходы третьего и четвертого регистров-слагаеьых Е являющиеся выходами действительной . г и мнимой частей результата устрайст- ва, подключены к вторым информацион-. ным входам первого и второго коммутаторов соответственно, первый выход блока управления подключен к yg-,Я равляющим входам первого и второго коммутаторов, второй и третий sumo» ды блока управления подключены к управляющим входам первого и второго сумматоров-вычитателей соответственно, четвертый выход блока управления подключен к синхроиизирующим входам регистра коэффициента, ре- гистра произведений, первого, второго, третьего и четвертого регистров слагаемых, пятый выход блока управления подключен к синхронизирующему входу первого входного регистра, шестой выход блока управления подключен .к сннхронизирующим входам второго и третьего входных регистров.

2. Устройство по п. 1, а т л и— ч а ю щ е е с я тем, что блок управления содержит генератор тактовых импульсов, счетчик, два элемента ИЛИ и элемент НБ, причем выход генератора тактовых импульсов подключен к

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

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

Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении устройств, реализующих алгоритм быстрого преобразования Фурье (БПФ2 °

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

Однако это устройство требует большого количества оборудования.

Наиболее близким к предлагаемому является устройство для выполнения быстрого преобразования Фурье, содержащее три входных регистра, регистр коэффициента, умножитель, регистр произведений, два коммутатора, первый сумматор-вычитатель, четыре регистра слагаемых, блок управления и дополнительно к этому четвертый входной регистр, второй регистр коэф- 5 фициента и второй регистр произведений 2 j.

-Недостатком известного устройства является его сложность, Цель изобретения - упрбщение,зо устройства.

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

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

Блок управления содержит генератор тактовых импульсов, счетчик, два элемента ИЛИ и элемент.НЕ, причем

1020833

4 выход генератора тактовых импульсов подключен к входу счетчика, выход второго разряда счетчика подключен к первым входам первого и второго элементов ИЛИ и к входу элемента НЕ, выход третьего разряда счетчика подклю- 5 чен к вторым входам первого и второго элементов ИЛИ, выход третьего разряда счетчика, выходы первого и вто. рого элементов ИЛИ, выходы первого и второго разрядов счетчика и выход fÎ ,элемента HE являются соответственно первым, вторым, третьим, четвертым, пятым и шестым выходаьи блока управления.

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

Устройство для выполнения быстрого.ïðåîáðà3îâàíèÿ Фурье содержит три входных регистра 1-3, предназначенных для приема исходных отсчетов, регистр 4 коэффициента, умножитель 5, регистр 6 произведений,- коммутаторы ,7 и 8, сумматоры-вычитатели 9 и 10, регистры 11-14 слагаемых, блок 15 управления, выходы 16-21 блока управления. Блок управления состоит из генератора 22 тактовых импульсов,. счетчика 23,элементов НЕ 24, ИЛИ 25 и 26. ЗО

Устройство для выполнения быстрого преобразования Фурье выполняет базовую операцию БПФ по основанию 2:

Я;-B;+C,.ч

Я В-С и1

1+1 1 1 йеЯрРеб.+ йе С Re& - Знс. Эгп ч

4 1 ф

ЗтЯлЗмВ + йеС.Этл19+З пС. ReW

1 j йеЯ. = йе9 -RqC; КеЖ +Эгпс,.Згп о 4()

З ОЯ. =ЗАТЬ вЂ” РеС.Эп Щ -Зт С.- Rem

i+< 4 i где В; и-С;. — исходные отсчеты;

А1 и A„+„ преобразованные отсчеты,, 27ti

Ю вЂ” весовой коэффициент, Ю=е N " количество отсчетов в исходном массиве; Re — действительная часть числа; З вЂ” мнимая часть числа.

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

На фиг. 3 показаны сигналы, поступающие на управляющие входы элементов устройства для выполнения быстрого преобразования Фурье с вы ходов блока 15 управления; Кроме то- . го, сделанные надписи поясняют выполняемую операцию (для сумматоров- 60 вычитателей и коммутаторов) и принимаемую информацию (для регистров).

В первом такте по сигналу с выхода 20 блока 15 управления во входной регистр (операндов) .2 принима- 65 ется действительная часть ReB. исходного отсчета В, .

Во втором такте по сигналу с выхода 21 блока 15 управления во входной регистр (операндов) 1 принимается действительная часть ReC исход I ного отсчета С а во входной регистр (операндов) 3 из регистра 2 пеРеписывается ReB,â регистр 4 коэффициента по сигналу с выхода 19

%лона 15 управления принимается действительная часть ReW весового коэффициента Wf.

В третьем такте по сигналу с выхода 19 блока 15 управления произведение Р„(;> — ReC. ВеИ принимается в регистр б произведений, коммутаторы 7 и 8 по сигналам с выхода 16 бло- ка 15 управления подключают выход регистра 3 к входам сумматоров-вычитателей 9 и 10, сумматор-вычитатель 9 в соответствии с управляющими сигналами с выхода 17 блока 15 управления выполняет операцию вычитания, сумматор-вычитатель 10 в соответствии с управляющими сигналами с выхода 18 блока 15 управления — операцию сложения. Кроме того, в регистр 2 по сигналу с выхода 20 блока -15 управления принимается мнимая часть 1mB исходного отсчета В, а в регистр 4 по сигналу с выхода 19 блока 15 управления принимается мнимая часть

ImW весового коэффициента И .

В четвертом такте по сигналу с выхода 19 блока 15 управления в регистры 11 и 12 слагаемых принимают3 ся соответственно ВеА;+„=ИВ --ВеС; х хаеЫ1 и ВеА1=вев1+Вес) - ReW1þ в регистр б пройзведений йринимается произведение Р(,.)=ReC;-ImW, в регистр 3 по сигналу с выхода 21 блока 15 управления переписывается содержимое регистра 2 (ImB ), коммутаторы по сигналу с выхода 16 блока

l5 управления подключают к входам сумматоров-.вычитателей 9 и 10 выход регистра 3, сумматоры-вычитатели в соответствии с сигналами с выходов

17 и 18 блока 15 управления выполняют операции вычитания (9) и сложения (10). Кроме того, в регистр 4 коэффициента по сигналу с выхода 19 блока 15 управления принимается мнимая (асть ImW весового коэффициента W а в регистр 1 по сигналу с выхода 21 — мнимая, часть ImC исход1 ного отсчета С;.

В пятом такте по сигналу с выхода 19 блока 15 управления в регистры 13 и 14 переписывается содержимое

1регистров 11 и 12 соответственно, т.е.,в регистр 13..ВеА(„=йеВ;-ReC; x

kReW ; в регистр 14:РеА,=ВеВ;+ВеС;

xReW ó в регистры ll и 12 прйнимаются соответственно ImA ; „ =ImB;

ReC - - ImW и ImA. =ImB. + ReC - - ImW ; в

1 i регистр 6 произведений принимается

1020833

Х„,С,.lmW B регистр 2 по си налу с вйхода 20 блока 15 управления принимается действительная часть

КеВ „B;+„. В регистр 4 по сигналу с выхода 19 блока 15 управления принимается действительная часть ReW весового коэффициента W . Коммутаторы 7 и 8 по сигналу с выхода lб блока 15 управления подключают к входам сумматоров-вычитателей 9 и 10 выходы регист-1О . ров 13 и 14 слагаемых соответственно.

Сумматоры-вычитатели 9 и 10 в соответствии с управляющими сигналами, поступающими с выходов 17 и 18, вы.,полняют операции сложения (9) и вычитания (10).

В шестом такте в регистры 13 и

14 слагаемых переписывается содержимое регистров 11 и 12 соответствен- 2О но, т.е. ImA + lmB;-ReC ° ImW1 в регистр 13; ImA> =ImB;+ReC> ImW в регистр 14; в регистры 11 и 12 слагаемых принимаются соответственно действительные части ReA +„ =ReB;-11еС; х, 25 хВеИ +ImC; -ImW и КеА =ИВ;+ йеС;.ReW -ImC;.ImW преобраэовайных отсчетов

A>+,и A в регистр б произведений прийимается произведение Р (1

=ImC; ReW . Коммутаторы 7 и 8 подключают к входам сумматоров-вычитателей 9 и 10 выходы регистров 13 и

14 соответственно, сумматоры-вычитатели в соответствии с сигналами, поступающими с выходов 17 и 18 блока

15 управления, выполняют операции вычитания (9) и сложения (10), В регистр 3 принимается действительная часть ReE исходного отсчета

i+1

В- в регистр 1 - действительная (+1 к

4ф часть ReC + исходного отсчета С; „ . В

В регистр 4 принимается действительная часть ReW +"весового коэффициента W + ".

В седьмом такте в регистры 13 и

14 слагаемых переписывается и выдается на выход устройства содержимое регистров 11 и 12 слагаемых,т.е.

ВеА +„ — в регистр 13; ReA — в регистр 14; в регистры 11 и 12 принимаются соответственно мнимые части

ХпА;+1 и ImAN преобразованных отсчетов А; „и А,;, в регистр б произведений принимается произведение

P„ .,„ ReC;+„ ReW" . Коммутаторы 7 и

8 йоДключают выход регистра 3 к входам сумматоров-вычитателей 9 и 10, выполняющих операции вычитания и слржения соответственно. В регистр

4 принимается мнимая часть ImW +" весового коэффициента W +, во входной регистр 2 принимается мнимая часть ImB;.+1 исходного отсчета B;+ .

В восьмом такте в регистры 13 и 14 слагаемых переписывается и выдается на выход устройства содержимое регистров ll и 12 слагаемых, т.е. ХНА;+., — в регистр 13; ImA, — в регистр 14; в регистры ll и 12 при-! нимаются соответственно ReA .i =

= Re ;+„-ВеС;+„ReW +" и ReA ;+2-ВеВ;+1+

+ReC; КеИ1+"; в регистр б произведейий принимается произведение

Р (., =ReC;+„ fmW +". В регистр 3

2(1+ ( прийимается мнимая часть 1mB< „ исходного отсчета В;+1, коммутаторы

7 и 8 подключают вйход регистра 3 к входам сумматоров-вычитателей 9 и 10, выполняющих соответственно операции вычитания и сложения. В регистр 1 принимается мнимая часть

ImC1+1 исходного отсчета С1+1 а в регйстр 4 принимается мнимая часть

ImW +" весового коэффициента W +". . Далее работа устройства аналогична.

Преиму®ество предлагаемого устройства перед известным состоит в меньшем.числе регистров H MefnuIeM числе информационных входов коммутаторов.

1020833

1020833

1020833

Заказ 3899/42

Тираж 706 Подписное

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

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

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

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

Редактор С. Квятковская Техред О.Неце Корректор А. Ференц