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

со

оо оо

00

со 4

Изобретение относится к автоматике и вычислительной технике, в частности к цифровой обработке сигналов и может быть использовано в устройствах спектрального анализа. Цель изобретения - расширение области применения за счет реализации возможности N-точечного преобразования Фурье (N 2). Поставленная цель достигается за счет того, что в устройство входят коммутатор 1, входной регистр 2, умножитель 3, регистры 4, 5, сумматор 6, блок памяти 7, входной регистр 8, коммутатор 9, выходные регистры 10 - 13, коммутатор 14, входной регистр 15 и блок синхронизации 16 с соответствующими связями. 3 ил.

N)

1

Изобретение относится к автоматике и вычислительной технике, в частности к цифровой обработке сигналов, может быть использовано в устройствах спектрального анализа и является усовершенствованием устройства по авт.св. № 1149275.

Цель изобретения - расширение области применения за счет реализации возможности N-точечного преобра.зова- ния Фурье (N 2).

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

к А,

д - . К-1

1 - А ..

АГ -A-.W,;

ReA i ReA ;

т А -г I j ImA ReA, ReA ,

k-1

ImA

it-t

.. . K- f

IinA , -ReA ;,,- ImW,-. ImA 7,,- ReW,-,

где A ,A . - исходные (входные) 30

i-f 1

A:.,

i

W, . N

отсчеты 1-го этапа преобразования Фурье; преобразованные отсчеты (выходные) i-ro этапа преобразо-35 вания Фурье; весовой коэффициент;

VI-1;

N - количество отсчетов в исходном массиве;

Re - действительная часть отсчета;

Im - мнимая часть отсчета Рассмотрим работу устройства при вьшолнении восьмиточечного быстрого преобразования Фурье (фиг.2), временная диаграмма которого приведена на фиг.З. На ней показаны моменты изменения состояний отдельных узлов устройства. Номер узла приведен слева, номера тактов привед ены вверху. Период работы устройства составляет 48 тактов. Для входного регистра и входного регистра 8 приведена информация, записываемая в них либо с информационного входа устройства, либо из блока 7 памяти, что определяет

аграмма, иллюстрирующая работу устройства.

Арифметическое устройство для быстрого преобразования Фурье состо-г кт из коммутатора 1, входного регистра 2 (чисел), умножителя 3, регистра 4, регистра 5, сумматора 6, блока 7 памяти, входного регистра 8 (чисел), коммутатора 9, выходных регистров 10-13, коммутатора 14, входного регистра 15 (коэффициентов) и блока 16 синхронизации.

Устройство вьшолняет быстрое преобразование Фурье, в основе крторого лежит базовая операция быстрого преобразования Фурье по основанию два:

A

ReW . - IraA

K-1

k1

Ml

H , -ReW.-t- IraA ;

.. . K- f

IraW ImA .,

K-1 i +1

Im

IraW

;,,- ImW,-. ImA 7,,- ReW,-,

0

5

0

5

0

5

ся третьим коммутатором I, который, как видно из диаграммы, с первого по шестнадцатый такты пропускает на свой выход информацию входа устройства, а в тактах с 17-го по 48-инфор- мацию из блока 7 памяти. Для блока 7 памяти указана информация на входе Адрес и на входе Запись, обеспечивающая надлежащую выборку и запись отсчетов. Для второго коммутатора 14 указаны моменты времени, когда на его выходах появляются выходные отсчеты восьмиточечного быстрого преобразования Фурье. В конце первого такта по сигналу с пятнадцатого выхода блока 16 синхронизации коммутатор 1 подключает к входам входного регистра 2 вход устройства и по сигналу с второго выхода блока 16 синхронизации поступающая на второй вход устройства действительная часть ReA° входного отсчета А° записыва1 .I

ется во входной регистр 2 (фиг.3.2). Одновременно по управляющему сигналу во входной регистр 15 коэффициентов записьшается действительная часть ReW коэффициента W (фиг.З. 15) Во втором такте выполняется умножение в умножителе 3 и произведение ReAV ReW с, по сигналу с первого выхода блока 16 принимается в регистр А (фиг.3,4). Поэтому же сигналу в регистр 15 принимается мнимая часть ImWo весового коэффициента Wj,, а по сигналу с третьего выхода блока 16 во входной регистр 8 (фиг.3,8) - действительная часть ReA , исходного отсчета А г,.

45 третьем такте вьшолняется умножение и произведение ReA, по сигналу с блока 16 синхронизации принимается в регистр 4, по этому же сигналу в регистр 5 принимается прои во входной ре

регистр изведение ReA° ReW

гистр 15 мнимая часть linW весового коэффициента W. Во входной регистр 2 по сигналу из блока 16 принимается мнимая часть ImA исходного от.0

счета Aj.

В четвертом такте в умножителе 3 выполняется умножение, и произведение ImAi- ImWo по сигналу из блока 16 синхронизации принимается в регистр 4, по этому же сигналу в регистр 5 принимается произведение ImWp,a во входной регистр 15 - действительная часть ReW весового коэффициента W. По сигналу с третьего выхода блока 16 во входной регистр 8 принимается мнимая часть ImA исходного отсчета А, комму- та.тор 9 по сигналу с четвертого выхода блока 16 синхронизации подключает к входу сумматора 6 выход входного регистра 8 (фиг.3,10). Сумматор 6 по сигналам из блока 16 вьтолняет операцию сложения в первой половине четвертого такта, а операцию вычитания - во второй половине четвертого такта, а операцию вычитания - во второй половине (фиг.3,7), соответственно сумма ReA°-+ ReA° ReW по сигндлу из блока 16 принимается в вы

ходной регистр 10 в середине четвер- лс рой половине шестого такта по сигна-

. .1%л J ,

того такта, а разность ReA - ReA It ReW(, - по сигналу из блока 16 в конце четвертого такта в. выходной регистр 11.,

В пятом такте в умножителе 3 выполняется умножение и произведение 1тА°|. ReWg по сигналу из блока 16 принимается в регистр 4, произведение ItnA ImWo этому же сигналу принимается из регистра 4 в регистр 5, а во входной регистр 15 - действительная часть ReW во входной регистр 2 по сигналу из блока 16 принимается через коммутатор 1 с перво-

50

55

лу из блока 16 из регистра 11 вьвдает- ся разность ReA°,; - ReA° ReWj, и в конце такта по сигналу из блока 16 в блок 7 памяти по адресу 2 принимается сз мма ReA. -ReA ,-ReW , + + ImA° - ImW.

В СЕДЬМОМ такте в умножителе 3 вы полняется умножение и произведение ReA° -ImW по сигналу из блока 16 принимается в регистр 4, в регистр 5 ,по этому же сигналу принимается про- изведение ReA°

ReW, а во входной

регистр 15 - мнимая часть ТтУ,, весового коэффициента Wo. Коммутатор 1

го входа устройства действительная часть ReA° исходного отсчета следующего канала. Коммутатор 9 по сигналу из блока 16 подключает к входу сумматора 6 выход входного регистра 9. Сумматор 6 по сигналам из блока 16 выполняет операцию сложения в первой половине пятого такта и операцию вычитания - во второй половине. Соответственно в середине пятого такта сумма ImAj + ReA°- ImW по сигналу из блока 16 принимается в выходной регистр 12, а в конце пятого такта

а разность ImA - ReA°

ImW,

по сиг5

0

5

0

5

0

налу из блока 16 принимается в выходной регистр 13.

В шестом такте в умножителе 3 выполняется умножение и произведение ReWj, по сигналу из блока 16 принимается в регистр 4, в регистр 5 по этому сигналу принимается произведение ImAV ReWp, а в регистр 15 - мнимая часть ImWo весового коэффициента во входной регистр 8 по сигналу с третьего выхода блока 16 принимается действительная часть ReA4 исходного отсчета k° . По сигналу из блока 16 объединенный выход регистров 10-13 через коммутатор 9 подключается к входу сумматора 6, который по сигналам из блока 16 выполняет операцию вычитания в первой половине шестого такта и операцию сложения - во второй. В первой половине шестого такта по сигналу из блока 16 из регистра 10 выдается сумма ReA ч + ReA X ReWfl и после вьшолнения вычитания на выходе сумматора 6 появ ляется действительная часть преобразованного отсчета ReA ReA l + ReAVReW - - ImA°-ImWp, которая по сигналу из блока 16 запишется в блок 7 памяти по адресу 1 (фиг.3,7 адрес). Во вто ,

лу из блока 16 из регистра 11 вьвдает- ся разность ReA°,; - ReA° ReWj, и в конце такта по сигналу из блока 16 в блок 7 памяти по адресу 2 принимается сз мма ReA. -ReA ,-ReW , + + ImA° - ImW.

В СЕДЬМОМ такте в умножителе 3 выполняется умножение и произведение ReA° -ImW по сигналу из блока 16 принимается в регистр 4, в регистр 5 ,по этому же сигналу принимается про- изведение ReA°

ReW, а во входной

регистр 15 - мнимая часть ТтУ,, весового коэффициента Wo. Коммутатор 1

остается в состоянии подключения к входу входного регистра 2 второго устройства, по сигналу из блока 16 во входной регистр 2 принимается мнимая часть ImAg исходного отсчета AS коммутатор 9 по сигналу из блока 16 подключает к входу сумматора 6 объединенный выход регистров 10-13. Сумматор 6 по сигналам из блока 16 вьтолняет операцию сложения и вычитания соответственно в первой и второй половинах седьмого такта. В первой половине седьмого такта по сигналу из блока 16 из регистра 12 вы- дается сумма ImA + ReA°- ImW,, и после выполнения операции сложения на - выходе сумматора 6 появляется мнимая часть преобразованного отсчета

imA IniA ) +ImA V ReWo , которая по сигналу из блока 16 запишется в блок 7 памяти по адресу 3, Во второй половине седьмого такта по сигналу из блока 16 в блок 7 памяти принимается по адресу 4 мнимая часть преобразованного отсчета ImA ImA° - ReA°-ImWo - ImA ImWo.

В восьмом такте в умножителе 3 выполняется умножение, и произведени ImWo по сигналу из блока 16 принимается в регистр 4. В регистр 5 по этому же сигналу принимается произведение ReAVlroWn, а в регистр 15

э о действительная часть ReW

весового

коэффициента Wo. В регистр 2 по сигналу из блока.16 синхронизации при- « нимается мнимая часть ImA исходного отсчета А4, коммутатор 10 по сигналу из блока 16 подключает к входу сумма35

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

тора выход входного регистра 8 чисел. 40 которого является информационным вхоСумматор 6 вьтолняет операции сложения и вычитания в первой и второй половинах такта соответственно. В первой половине восьмого такта по

сигналу из блока 16 в регистр 10 при-45 подключены соответственно к шестнаднимается сумма ReA4 + ReAj-ReWj, во второй половине восьмого такта по

с

0 5

0

5

сигналу из блока 16 в регистр 11 принимается разность ReA4 - ReWp.

В последующих тактах работа устройства будет отличаться поступающими отсчетами во входные регистры 2, 8 и 15 (фиг.З). Блок 7 памяти будет задействован кроме записи также для считьшания информации. С 37 до 51 такты через коммутатор 14 на вход устройства поступают входные отсчеты (фиг.3,14) с сумматора 6 или с объединенного выхода регистров 10-13 в зависимости от значения управляющего сигнала с блока 16 синхронизации. Начиная с 49-го такта устройство будет работать с циклом 48 тактов аналогично тому, как оно работало с 1 по 48 такты.

Формула изобретения

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

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

цатому и семнадцатому вькодам блока синхронизации.

.

1 :f -«;

j

;

i i f/ .V .,; A A Фиг. 2