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

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

Иллюстрации

Показать все

Реферат

 

ОП ИКАНИЕ

ИЗОБРЕТЕНИЯ

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

Союз Советских

Социалистических

Республик

< 723582 (61) Дополнительное к авт. свид-ву— (22) Заявлено 10.10.77. (21) 2533256/18-24 с присоединением заявки М (23) П риоритет (G))M. Кл.

G 06 F 15/34

Государственный комитет ао делам изобретений и открытий

Опубликовано 25.03,80. Бюллетень М 11

Дата опубликования описания 25.03.80 (53) УДК а81.3 (088,8) Ю. С. Каневский, Н. Е. Мадянова, Б. А. Некрасов, Ю. В. Раубе и О. А. Федотов (72) Авторы изобретения

Киевский ордена Ленина политехнический институт им. 50 †лет

Великой Октябрьской социалистической революции (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО

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

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

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

Недостатком таких устройств является наличие адресных цепей и сложность схем управле10 ния.

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

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

Поставленная цель достигается тем, что устройсгво содержит Р— 1 элементов И (Р— 1— число разрядов счетчика адреса и регистра итераций, P = log2 N,N — число выборок в одном отсчете), а каждая из двух групп блоков памяти состоит из четырех блоков памяти, причем выходы первого и второго блоков памя» ти в первой группе подключены ко входам первого селектора, а третьего и четвертого блоков памяти — ко входам второго селектора, входы первого и третьего блоков памяти во второй группе подключены к выходам первого мультиплексора, а входы второго и четвертого блоков памяти — к выходам второго мультиплексора, первый и второй входы i-ro элемента И {i = 1, ..., P-— - 1) подключены соот72358 ветственно к выходу i-го разряда счетчика адреса и выходу (Р— i)-го разряда регистра итерации, выходы элементов И подключены к адресным входам блока постоянной памяти, выход первого разряда регистра адреса подключен к управляющим входам первого и второго мультиплексоров, а выход (P — 1)-го разряца— к управляющим входам первого и второго селекторов.

На фиг. 1 представлена структурная схема to устройства для выполнения БПФ; на фиг.2— видоизмененный граф алгоритма БПФ; на фиг. 3 — базовая операция алгоритма БПФ.

Устройство содержит две группы блоков памяти l и 2 на сдвиговых регистрах, процессор 15

3, счетчик 4 адреса, регистр 5 итераций, селекторы 6, 7, мультиплексоры 8, 9, линейку элементов И 10, блок постоянной памяти (ПЗУ)

11. Выходы группы блоков памяти 1 через селекторы 6 и 7 соединены со входами проце 2о сора 3, выходы которого через мультиплексоры 8 и 9 соединены со входами группы блоков памяти 2, выход младшего разряда счетчика 4 адреса соединен с управляющими входами селекторов 6, 7, старшего1 разряда — с уп25 равляющими входами мультиплексоров 8, 9, а выход переноса — co входом регистра 5 итераций. Входы i-ro элемента И, 10 (i = 1, ..., Р— 1, где Р = i+gg N, где Л вЂ” число входных отсчетов) соединены с i-м разрядом счетчика

ЗО

4 адреса и (Р— i)-м разрядом регистра 5 итераций, а выход — c i-ой адресной шиной ПЗУ

11 весовых коэффициентов. Выход ПЗУ 11 соединен со входом процессора 3.

Устройство работает по закону, лсоторый пред 35 ставлен видоизмененным графом БПФ (фиг. 2).

Характерной особенностью графа является постоянная структура на всех итерациях, что позволяет не изменять законы записи и считывания от итерации к итерации. Через М; обозначены 4О последовательные массивы данных направленного графа, через а;(n) — элементы массива

М;, где i изменяется от 1 до р Р+ 1, и соответствует номеру узла графа в i-ом массиве. Данные исходного массива М преобразованы в дво- 45 ичноинверсном порядке.

Благодаря постоянной структуре графа общая формула получения элемента массива

М +, из элементов массива М; имеет вид

1И а„ <(К) = а;(2К) + а;(2К+1)- щ" <0 -1) ьО а „+ „(K + - -) = а; (2К) — а; (2К вЂ” 1) . w

> (г-4 при i = 1, 2, ..., Р;

К вЂ” 0,1,..., — — 1.

Из формулы (2) видно, что при последовательном вычислении элементов массива М

1+1 производится последовательная выборка элементов массива М.

2 4

Формула (1) представляет собой базовую операцию ЬГ1Ф, (граф показан на фиг. 3). Фор- мула (1) реализуется в процессоре 3.

Следовательно, массив М,;+< может быть получен из массива М после выполнения —, базовых операций. В связи с этим коэффициент пересчета счетчика 4 адреса — — — (P — 1 разй ряд). Регистр итераций имеет P — 1 разряд. На первой итерации его состояние "00...000", на второй — "00...001", íà i-ой — "00011111...11", pa P-ой — "11...111".

Из массива М; образуем векторы

D = (а ) и+ -+1

Z где m изменяется от 0 до — 1- — 1, и записы2 ваем их в соответствующие секции блока памяти.

Индекс указывает на принадлежность к массиву М; (1ч).

На примере восьми точечного БПФ рассмотрим работу устройства.

В исходном состоянии вектор А образует элементы а, „а>, записанные последовательно в секцию А блока 1 памяти, вектор Вq — элементы а„, а, последовательно записанные в секцию. В блоке 1 памяти, вектор С, — элемен-! ты а4, а, последовательно записанные в сек-! цию С блока 1 памяти, вектор 0 — элементы а, а, последовательно записанные в секцию D блока 1 памяти.

Двухразрядный счетчик 4 адреса находится в нулевом состоянии.

В двухразрядный регистр 5 итераций записаны нули.

Работа устройства начинается с подачи тактовых импульсов (ТИ) на вход счетчика 4 адреса. Выполнение одной итерации осуществляется за 4 такта, при этом на каждом такте в процессоре 3 параллельно реализуются формулы (1) и (2). При выполнении первого такта на первой итерации, которому соответствует состояние счетчика 4 адреса "00" и состояние регистра 5 итераций "00",происходит считывание эле- ментов а из секции А и а из секции В блока

1 памяти. В это же время на выходе линейки элементов И 10, входы которой определенным образом соединены с выходами счетчика

4 адреса и регистра 5 итерации, устанавливается адрес "00", который не изменяется на протяжении выполнения первой итерации и соответствует выбору весового коэффициента по адресу "00" (w ).

Данные а и а „через селекторы 6 и 7, управляемые ст ршим разрядом счетчика 4 адре723582.

:а, поступают в процессор 3, туда же поступают значения весового коэффициента w .

На первом такте значения а и а 4, полученные на выходе процессора через мультиплексоры 8 и 9, управляемые младшим разрядом счетчика 4 адреса, поступают соответственно в секции А и С блока 2 памяти. На этом первый такт работы устройства заканчивается.

На втором такте счетчик 4 адреса переходит в состояние "01". Происходит считывание эле- 1о ментов а из секции А и аз из секции В блока 1 памяти и запись результатов а и аз, со4 ответственно в секции В и D блока 2 памяти.

На четвертом такте состояние счетчика 4 адреса "11", а Ь считывается из секции С, а из секции D блока 1, результаты а з и а7 записываются соответственно в секции В и D блока 2.

На этом выполнение первой итерации заканчивается. Значение нуля в старшем разряде счет- о чика 4 адреса обеспечивает подключение селекторов 6 и 7 к секциям А и В, а значение единицы — к секциям С и 0 блока 1 памяти.

Значение нуля в младшем разряде счетчика

4 адреса обеспечивает подключение мультиплексоров 8 и 9 к секциям А и С, а значение единицы — к секциям В и 0 блока 2 памяти.

При выполнении второй итерации данные вы. бираются из секций А, В, С, D блока 2 памяти и результаты записываются в секции А, В, С, 0 блока 1 памяти аналогично первой итерации.

Цепи записи в блок 1 памяти и считывание из блока 2 памяти для простоты схемы на чертеже не показаны. з

На первом такте второй итерации счетчик 4 адреса устанавливается в состоянии "00", а сигнал переноса с выхода счетчика 4 адреса поступает на вход регистра 5 итерации, устанавливая его в состояние "01".

На выходе линейки 10 устанавливается адрес "00". Данные а и а4 выбираются из секций А и В блока 2, результаты вычисления а и а4 записываются в секции А и С блока з з

1 памяти. 45

На втором такте состояние регистра итерации "01", счетчика адреса — "01*, т. е. значения адреса на выходе линейки 10 сохраняется.

Данные а2 и а з выбираются из секций А и В, результаты вычисления аз и аз записываются в секции В и D блока 1.

На третьем такте состояние регистра итераций "01", счетчика адреса — "10", на выходе линейки 10 устанавливается адрес "10", что соответствует выбору весового коэффициента

w а4 и а2 выбираются из секций С и 0 блока 2. Результаты вычисления аз и абз записываются в секции А и С блока 1.

На четвертом такте значение адреса на выходе линейки 10 сохраняется, а и а> выбираются -иэ секций С и 0 блока 2, результаты выз з

Ъ числения аз и а записываются в секции В и

D блока 1.

При выполнении третьей, последней, итерации данные выбираются из секций А, В, С, D блока 1, результаты заносятся в секции А, В, С, 0 блока 2, аналогично первой итерации.

На первом такте счетчик 4 адреса устанавливается в состояние "00", а сигнал переноса с выхода счетчика 4 адреса, поступая на вход регистра 5 итерации, устанавливает в нем состоя|ние "11".

Такое состояние регистра итераций и счетчика 4 адреса обеспечивает формирование на выходной линейке 10 на первом такте адреса

"00 *, соответствующего весовому коэффициенту w; на втором такте — адреса "01" соответ.ствующего w;. на третье 4 такте — адреса "01", соответствующего w; на четвертом такте — адреса "11" соответствующего w .

Применение. изобретения дает возможность исключить из устройства счетчик адреса весовых коэффициентов и неполный дешифратор, что приводит к экономии оборудования и упрощению схемы управления. При организации устройства для выполнения БПФ над 1024 отсчетами объем схем управления сокращается на 50 вентилей, что составляет 41% от общего объема схемы управления.

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

Устройство для выполнения быстрого преобразования Фурье, содержащее две группы блоков памяти, процессор, счетчик адреса, регистр итераций, два селектора, два мультиплексора, блок постоянной памяти, причем первый, второй и третий входы процессора подключены соответственно к выходам первого, второго селекторов и блока постоянной памяти, первый и второй выходы процессора — ко входу первого и второго мультиплексоров соответственно, выход переполнения счетчика адреса подключен ко входу регистра интераций, о т л ич а ю щ е е с я тем, что, с целью упрощения устройства, оно содержит P — 1 элементов И (Р— 1 — число разрядов счетчика адреса и регистра итераций, Р = log N, N — число выборок в одном отсчете), а каждая из двух групп блоков памяти состоит из четырех блоков памяти, причем выходы первого и второго блоков памяти в первой группе подключены ко входам первого селектора, а третьего и четвертого блоков памяти — ко входам второго селектора, входы первого и третьего блоков па723582 мяти во второй группе подключены к выходам первого мультиплексора, а входы втордго и четвертого блоков памяти — к выходам второго мультиплексора, первый и второй входы i-го элемента И (i = 1, ..., P —,1) одключены соответственно к выходу i-го разряда счетчика адреса и выходу (P — i)-го разряда регистра итерации, выходы элементов И подключены к адресным входам блока постоянной памяти, выход первого разряда регистра адре- 10 са подключен к управляющим входам первого и второго мультиплексоров, а выход (Р--1)-го оазряда — к управляющим входам первого и второго селекторов.

Источники информации, принятые во внимание при экспертизе

1. Вьюхин Н. И. Индексное устройство процессора для выполнения быстрого преобразова" ния Фурье. Сб. "Автометрия",. N 3, 1973.

2. Патент Великобритании У 1407401, кл. G 4 А, 1974 (прототип).

723582 (8) о

1 а, Ф

à26 с 8m+1

Составитель В. Березкин

Редактор Л, Алексеенко Техред M.Kåëåìåø Корректор M.Ïoæî

Заказ 28/14 Тираж 751 Подписное

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

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

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