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

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

Иллюстрации

Показать все

Реферат

 

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

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

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