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

I

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

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

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

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

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

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

Поставленная цель достигается тем, что устройство содержит Р-1 элементов И (Р-1 - число разрядов счетчика адреса и регистра итераций, Р logj N,N - число выборок в одном отсчете),. а каждая из двух групп блоков памяти состоит из четырех блоков памяти, причем выходы первого и второго блоков памя ти в первой фуппе подключены ко входам первого селектора, а третьего и четвертого блоков памяти - ко входам второго селектора, входы первого и третьего блоков памяти во второй группе подключены к выходам первого мультиплексора, а входы второго и четвертого блоков памяти - к выходам второго мультиштексора, первый и второй входы i-го элемента И (i 1, ..., Р-1) подключены соответсгвенно к выходу i-ro разряда счетчика адреса и выходу (P-i)-ro разряда регистра итеравди, выходы элементов И подключены к адресным входам блока постоянной памяти, выход первого разряда регистра адреса подключен к управляющим входам первого и второго мультиплексоров, а выход (Р-1)-го разрада - к управляюидим входам первого и второго селекторов. На фиг. 1 представлена структурная схема устройства для выполнения БПФ; на фиг. 2 видоизмене1шый граф алгоритма БПФ; на фиг. 3 - базовая операция алгоритма БПФ. Устройство содержит две группы блоков памяти I и 2 на сдвиговых регистрах, процессор 3, счетчик 4 адреса, регистр 5 итераци, селекторы 6, 7, мультиплексоры 8, 9, линейку элементов И 10, блок постоянной памяти (ПЗУ) 11. Выходы группы блоков памяти 1 черкез селекторы 6 и 7 соединены со входами процессора 3, выходы которюго через мультиплексоры 8 и 9 соединены со входами группы блоков памяти 2, выход младшего разряда счетчика 4 адреса соединен с управляющими входами селекторов 6, 7, старшего разряда - с управляющими входами мультиплексоров 8, 9, а выход переноса - со входом регистра 5 итераций. Входы i-ro элемента И . 10 (i 1, ..., Р-1, где P log2N, где-N - число входных отсчетов) соединены с i-м разрядом счетчика 4 адреса и (Р-)-м разрядом регистра 5 итераций, а выход - с i-ой адресной шиной ПЗУ 11 весовых коэффициентов. Выход ПЗУ 11 соединен со входом процессора 3. Устройство работает по закону, который пре ставлен видоизмененным графом БПФ (фиг. 2). Характерной особенностью графа является постоянная структура на всех итерациях, что позволяет не изменять законы записи и считывани от итерадии к итерации. Через Mj обозначены последовательные массивы данных направленного графа, через aj (п) - элементы массива Mj, где i изменяется от 1 до р Р + 1, п соответ ствует номеру узла графа в i-ом массиве. Данные исходного массива М преобразованы в дво ичноинверсном порядке. Благодаря постоянной структуре графа общая формула получения элемента массива Мд. элементов массива Mj имеет вид (К) а| (2К) + aj (2К+1)- w ) n-aCr-i) (К+-|-) aj(2K) -aj(2K-l) при i 1, 2, К 0, 1, .... Из формулы (2) видно, что при последовательном вычислении элементов массива М. . производится последовательная выборка элемен тов массива М. Формула (1) представляет собой базовую операцию БПФ, (граф показан на фиг. 3). Формула (1) реализуется в процессоре 3. Следовательно, массив может быть получен из массива М после выполнения - базовых, операций. В связи с этим коэффициент пересчета счетчика 4 адреса - - (Р-1 разряд). Регистр итераций имеет Р-1 разряд. На первой итерации его состояние 00...000, на второй - 00...001, на i-ой - 00011111...11, р Р-ой - 11...111. Из массива Mj образуем векторы а. - - 1, и записыгде m изменяется от О до ваем их в соответствующие секции блока памяти. Индекс указывает на принадлежность к массиву Mj (N). На примере восьми точечного БПФ рассмотрим работу устройства. В исходном состоянии вектор АЗ образует элементы а ai, записанные последовательно в секцию А блока 1 памяти, вектор В - элементы а, аз, последовательно .записанные в секцию. В блоке 1 памяти, вектор С - элемен аб, последовательно записанные в секС блока 1 памяти, вектор D2 - элементы as, ат, последовательно записанные в секцию D блока 1 памяти. Двухразрядный счетчик 4 адреса находится в нулевом состоянии. В двухразрядный регистр 5 итераций записаны нули. Работа устройства начинается с подачи тактовых импульсов (ТИ) На вход счетчика 4 адреса. Выполнение одной итерации осуществляется за 4 такта, при этом на каждом такте в прюцессоре 3 параллельно реализуются формулы (1) и (2). При выполнении первого такта на первой итераЦии, которому соответствует состояние счетчика 4 адреса 00 и состояние регистра 5 итераций 00,происходит считывание элементов адИЗ секции А и а из секции В блока 1 памяти. В это же время на выходе линейки элементов И 10, входы которой определенным образом соединены с вб1ходами счетчика 4 адреса и регистра 5 итерации, устанавливается адрес 00, который не изменяется на протяжении выполнения первой итерации и соответствует выбору весового коэффициента по адресу 00 (w ). Данные а и а через селекторы 6 и 7, управляемые ст.ршим разрядом счеиика 4 адрега, поступают в процессор 3, же поступают значения весового коэффициента w°. На первом такте значения а и а, полученные на выходе процессора через мультиплексоры 8 и 9, управляемые младшим разрядом счетчика 4 адреса, поступают соответственно в секции А и С блока 2 памяти. На этом первый такт работы устройства заканчивается. На втором такте счетчик 4 адреса переходит в состояние 01. Происходит считьтание элементов an из секоди А и аз из секции В блока 1 памяти и запись результатов а и а| соответственно в секции В и D блока 2 памяти. На четвертом такте состояние счетчика 4 адреса И, а считывается из секции С, а - из секции D блока 1, результаты а и 87 записываются соответственно в секции В и D блока 2. На этом выполнение первой итерации заканчивается. Значение нуля в старшем разряде сче чика 4 адреса обеспечивает Подключение селекторов 6 и 7 к секциям А и В, а значение еди ницы - к секциям С и D блока 1 памяти. Значение нуля в младшем разряде счетчика 4 адреса обеспечивает подключение мультиплексоров 8 и 9 к секциям А и С, а значение единицы - к секциям В и D блока 2 памяти. При выполнении второй итерации данные вы бираются из секций А, В, С, D блока 2 памяти и результаты записываются в секции А, В, С, D блока 1 памяти аналогично первой итерации. Цепи записи в блок 1 памяти и считывание из блока 2 памяти для простоты схемы на чер теже не показаны. На первом такте второй итерации счетчик 4 адреса устанавливается в состоянии 00, а сиг нал переноса с выхода счетчика 4 адреса поступает на вход регистра 5 итерации, устанавливая его в состояние 01. На выходе ли 1ейки 10 устанавливается адрес 00. Данные а и а выбираются из секций А и В блока 2, результаты вычисления а записываются в секции А и С блока I памяти. На втором такте состояние регистра итерации 01, счетчика адреса - 01, т. е. значения адреса на выходе линейки 10 сохраняется Данные а| и аз выбираются из секций А и В, результаты вычисления а и 3$ записываются в секции В и D блока 1. На третьем такте состояние регистра итераций 01, счетчика адреса - 10, на выходе линейки 10 устанавливается адрес 10, что соответствует выбору весового коэффициента w, 34 и а| выбираются из секций С и D бло ка 2. Результаты вычисления а и al записыва ются в секции А и С блока I. 7 .6 .На четвертом такте значение адреса на выходе линейки 10 сохраняется, а и а выбираются из секций С и D блока 2, результаты вычисления эз и 87 записываются в с екции В и D блока 1. При выполнении третьей, последней, итерации данные выбираются из секций А, В, С D блока 1, результаты заносятся в секции А, В, С, D блока 2, аналогично первой итерации. На первом такте счетчик 4 адреса устанавливается в состояние 00, а сигнал переноса с выхода счетчика 4 адреса, поступая на вход регистра 5 итерации, устанавливает в нём состояние 11. Такое состояние регистра итераций и счетчика 4 адреса обеспечивает формирование на выходной линейке 10 на первом такте адреса 00, соответствующего весовому коэффициенту w°; на втором такте - адреса 01 соответствующего w;: на TpeTbeiyi такте - адреса 01, соответствующего w ; на четвертом такте - адреса И соответствующего w. Применение- изобретения дает возможность исключить из устройства счетчик адреса весовых коэффициентов и неполный дешифратор, что приводит к экономии оборудования и упрощению схемы управления. При организации устройства для выполнения БПФ над 1024 отсчетами объем схем управления сокра1цается на 50 вентилей, что составляет 41% от общего объема схемы управления. Формула изобретения Устройство для выполнения быстрого преобразования Фурье, содержащее две группы блоков памяти, процессор, счетчик адреса, регистр итераций, два селектора, два мультиплексора, блок постоянной памяти, причем первый, второй и третий входы процессора подключены соответственно к выходам первого, второго селекторов и блока постоянной памяти, первый и второй выходы процессора - ко входу первого и второго мультиплексоров соответственно, выход переполнения счетчика адреса подключен ко входу регистра интераций, отличаю щ е е с я тем, что, с целью упрощения устройства, оно содержит Р-1 элементов И (Р-1 - число разрядов счетчика адреса и регистра итераций, Р log2N, N - число выборок в одном отсчете), а каждая из двух групп блоков памяти состоит из четырех блоков памяти, причем выходы первого и второгЪ блоков памяти в первой группе подключены ко входам первого селектора, а третьего и четвертого блоков памяти - ко входам второго селектора, входы первого и третьего блоков памяти во второй группе подключены к выходам первого мультиплексора, а входы второго и четвертого блоков памяти - к выходам второго мультиплексора, первый и второй входы 1-го элемента И (i 1, ..., Р-1) подключены соответственно к выходу i-ro разряда счетчика адреса и выходу (P-i)-ro разряда регистра итерации, выходы элементов И подключены к адресным входам блока постоянной памяти, выход первого разряда регистра адреса подключен к управляющим входам первого 7 28 и второго мультиплексоров, а выход (Р-1)-го разряда - к управляющим входам первого и второго селекторов. Источники информащш, принятые во внимание при экспертизе 1.Вьюхин Н. И. Индексное устройство процессора для выполнения быстрого преобразования Фурье. Сб. Автометрия,№ 3, 1973. 2.Патент Великобритании № 1407401, кл. G 4 А, 1974 (прототип).

Ш-ЁО L. 1 Г