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

ОП ИКАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическихРеспублик(51)М. Кд. 6 06 Е 15/34 Государственный комитет ао делам изобретений и открытийОпубликовано 25.03,80, Бюллетень М 11 Дата опубликования описания 25.03.80(72) Авторы изобретения Киевский ордена Ленина политехнический институт им. 50 в лет Великой Октябрьской социалистической революции(54) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ Изобретение относится к вычислительной технике и предназначено для выполнения алгоритма быстрого преобразования фурье (БПФ), который используется при цифровой обработке сигналов.Известны устройства для выполнения алгоритма БПФ, в которых используется память с последовательным доступом 1.Недостатком таких устройств является нели. чие адресных цепей и сложность схем управле.1 ОНаиболее близким к предлагаемому является устройство, содержащее два блока памяти на сдвиговых регистрах, процессор, мультиплексо. ры, селекторы, счетчик адреса, счетчик адреса весовых коэффициентов и, регистр итерации, неполный дешифратор, входы которого соединены с выходами регистра итерации и счетчика адреса, а выходы - со входами мультиплексоров и счетчика адреса весовых коэффициентов а. Неполный дешифратор представляет собой комбинационную схему, обеспечивающую нужную последовательность выбора секций памяти и формирования адреса весового коэффициента чч в зависимости от состояния счетчикаадреса и регистра итерации 2.Недостатком этого устройства является наличие неполного дешифратора и счетчика адреса весовых коэффициентов чч, усложняющихсхему и приводящих к излишним аппаратурным затратам,Цель изобретения - упрощение устройства.Поставленная цель достигается тем, что устройсгво содержит Р - 1 элементов И (Р - 1 -число разрядов счетчика адреса и регистраитераций, Р = 1 оц 2 1 ч,М - число выборок в одном отсчете), а каждая из двух групп блоковпамяти состоит из четырех блоков памяти,причем выходы первого и второго блоков памяти в первой группе подключены ко входампервого селектора, а третьего и четвертогоблоков памяти - ко входам второго селектора, входы первого и третьего блоков памятиво второй группе подключены к выходам первого мультиплексора, а входы второго и четвертого блоков памяти - к выходам второгомультиплексора, первый и второй входы 1 гоэлемента И (1 = 1, , Р - 1) подключены соот72358 ветственно к выходу -го разряда счетчика адреса и выходу (Р - ) го разряда регистра ите.рации, выходы элементов И подключены к адресным входам блока постоянной памяти, выход первого разряда регистра адреса подключенк управляющим входам первого и второгомультиплексоров, а выход (Р - 1)-го разряца -к управляющим входам первого и второго се.лекторов.На фиг. 1 представлена структурная схема Оустройства для выполнения БПФ; на фиг, 2 -видоизмененный граф алгоритма БПФ; нафиг. 3 - базовая операция алгоритма БПФ.Устройство содержит две группы блоковпамяти 1 и 2 на сдвиговых регистрах, процессор 153, счетчик 4 адреса, регистр 5 итераций, селекторы 6, 7, мультиплексоры 8, 9, линейку элементов И 10, блок постоянной памяти (ПЗУ)11. Выходы группы блоков памяти 1 через селекторы 6 и 7 соединены со входами проце 20сора 3, выходы которого через мультиплексоры 8 и 9 соединены со входами группы блоков памяти 2, выход младшего разряда счетчика 4 адреса соединен с управляющими входами селекторов 6, 7, старшего 1 разряда - с уп 25равляющими входами мультиплексоров 8, 9,а выход переноса - со входом регистра 5 итераций. Входы 1-го элемента И,10 ( = 1, ,Р - 1, где Р =оцй, где Л - число входныхотсчетов) соединены с -м разрядом счетчика304 адреса и (Р - )-м разрядом регистра 5 итера.ций, а выход - с -ой адресной шиной ПЗУ11 весовых коэффициентов. Выход ПЗУ 11соединен со входом процессора 3,Устройство работает по закону, который пред зставлен видоизмененным графом БПФ (фиг. 2).Характерной особенностью графа является постоянная структура на всех итерациях, что позволяет не изменять законы записи и считыванияот итерации к итерации. Через М; обозначены 40последовательные массивы данных направленного графа, через а;(и) - элементы массиваМ;, гдеизменяется от 1 до р Р+ 1, и соответствует номеру узла графа в -ом массиве. Данные исходного массива М преобразованы в двоичноинверсном порядке.Благодаря постоянной структуре графа общая формула получения элемента массиваМ+,из элементов массива М; имеет вид1 йа 1(К) = а; (2 К) + а; (2 К+1). м "20-) 50а + (К + ф-) = а; (2 К) - а; (2 К - 1) . аи я 0-4при= 1, 2, , Р;К - 0,1 -- 1,Из формулы (2) видно, что при последова.тельном вычислении элементов массива М1+4производится последовательная выборка элемен.тов массива М. 2Формула (1) представляет собой базовую операцию ЬГ 1 Ф, (граф показан на фиг. 3). Фор- мула (1) реализуется в процессоре 3.Следовательно, массив М,;+4 может быть получен из массива М после выполнения - , базовых операций. В связи с этим коэффициент пересчета счетчика 4 адреса - - - (Рразй ряд). Регистр итераций имеет Р - 1 разряд. На первой итерации его состояние00000", на второй - "00001", на -ой - "0001111111", ра Р-ой - "11111".Из массива М; образуем векторыР = а 1п 2+ -+12где п 1 изменяется от 0 до -- 1, и записы 2ваем их в соответствующие секции блока памяти.Индекс указывает на принадлежность к массиву М; (й).На примере восьми точечного БПФ рассмотрим работу устройства.В исходном состоянии вектор А образует элементы а,а, записанные последовательно в секцию А блока 1 памяти, вектор В - элементы а, аэ, последовательно, записанные в секцию. В блоке 1 памяти, вектор С, - элемен/ ты а 4, аб, последовательно записанные в сек/ цию С блока 1 памяти, вектор Р - элементы а, а, последовательно записанные в секцию Р блока 1 памяти.Двухразрядный счетчик 4 адреса находится в нулевом состоянии.В двухразрядный регистр 5 итераций записаны нули. Работа устройства начинается с подачи тактовых импульсов (ТИ) на вход счетчика 4 адреса. Выполнение одной итерации осуществляется за 4 такта, при этом на каждом такте в процессоре 3 параллельно реализуются формулы (1) и (2). При выполнении первого такта на первой итерации, которому соответствует состояние счетчика 4 адреса "00" и состояние регистра 5 итераций "00",происходит считывание эле- ментов а из секции А и а из секции В блока 1 памяти. В это же время на выходе линейки элементов И 10, входы которой определенным образом соединены с выходами счетчика 4 адреса и регистра 5 итерации, устанавливается адрес "ОО", который не изменяется на протяжении выполнения первой итерации и соответствует выбору весового коэффициента по адресу "00" (чч ).Данные а и ачерез селекторы 6 и 7, уп. равляемые старшим разрядом счетчика 4 адре 723582,:а, поступают в процессор 3, туда же поступа. ют значения весового коэффициента чч.На первом такте значения а и а получен. ные на выходе процессора через мультиплексоры 8 и 9, управляемые младшим разрядом счетчика 4 адреса, поступают соответственно в секции А и С блока 2 памяти, На этом пер. вый такт работы устройства заканчивается.На втором такте счетчик 4 адреса переходит в состояние "01", Происходит считывание эле ментов а из секции А и аз из секции В бло. ка 1 памяти и запись результатов а и аз, со 4 ответственно в секции В и О блока 2 памяти.На четвертом такте состояние счетчика 4 адреса "11", аЬ считывается из секции С, а 7 из секции О блока 1, результаты азз и а 7 записываются соответственно в секции В и О блока 2.На этом выполнение первой итерации заканчивается. Значение нуля в старшем разряде счет о чика 4 адреса обеспечивает подключение селек. торов 6 и 7 к секциям А и В, а значение еди. ницы - к секциям С и О блока 1 памяти.Значение нуля в младшем разряде счетчика 4 адреса обеспечивает подключение мультиплексоров 8 и 9 к секциям А и С, а значение единицы - к секциям В и О блока 2 памяти,3При выполнении второй итерации данные вы бираются из секций А, В, С, О блока 2 памяти и результаты записываются в секции А, В, С, О блока 1 памяти аналогично первой итерации.Цепи записи в блок 1 памяти и считывание из блока 2 памяти для простоты схемы на чертеже не показаны. З 5На первом такте второй итерации счетчик 4 адреса устанавливается в состоянии "00", а сиг. нал переноса с выхода счетчика 4 адреса поступает на вход регистра 5 итерации, устанавливая его в состояние "01".На выходе линейки 10 устанавливается адрес "00". Данные а и а выбираются из секций А и В блока 2, результаты вычисления а и а 4 записываются в секции А и С блока з з1 памяти. 45На втором такте состояние регистра итерации "01", счетчика адреса - "01, т. е. значе. ния адреса на выходе линейки 10 сохраняется.Данные аз и азз выбираются из секций А и В, результаты вычисления аз и аз записываются в секции В и О блока 1.На третьем такте состояние регистра итераций "01", счетчика адреса - "10", на выходе линейки 10 устанавливается адрес "10", что соответствует выбору весового коэффициента чч, а 4 и аз выбираются из секций С и О блока 2. Результаты вычисления аз и абз записываются в секции А и С блока 1. На четвертом такте значение адреса на выхо. де линейки 10 сохраняется, а и а выбираются.иэ секций С и О блока 2, результаты вы.з зЪ числения аз и а 7 записываются в секции В и О блока 1.При выполнении третьей, последней, итерации данные выбираются из секций А, В, С, О бло. ка 1, результаты заносятся в секции А, В, С, О блока 2, аналогично первой итерации.На первом такте счетчик 4 адреса устанавли. вается в состояние "00", а сигнал переноса с выхода счетчика 4 адреса, поступая на вход регистра 5 итерации, устанавливает в нем состоя 1 ние "11".Такое состояние регистра итераций и счетчика 4 адреса обеспечивает формирование на вы. ходной линейке 10 на первом такте адреса "00, соответствующего весовому коэффициенту чч"; на втором такте - адреса "01" соответ. .ствующего чч; на третье 4 такте - адреса "01", соответствующего чч; на четвертом такте - адреса "11" соответствующего чч .Применение. изобретения дает возможность исключить из устройства счетчик адреса весовых коэффициентов и неполный дешифратор, что приводит к экономии оборудования и упроще. нию схемы управления, При организации устрой. ства для выполнения БПФ над 1024 отсчетами объем схем управления сокращается на 50 вентилей, что составляет 41% от общего объема схемы управления.Формула изобретенияУстройство для выполнения быстрого преобразования Фурье, содержащее две группы блоков памяти, процессор, счетчик адреса, регистр итераций, два селектора, два мультиплексора, блок постоянной памяти, причем первый, второй и третий входы процессора подключены соответственно к выходам первого, второго селекторов и блока постоянной памяти, первый и второй выходы процессора - ко входу первого и второго мультиплексоров соответственно, выход переполнения счетчика адреса подключен ко входу регистра интераций, о т л ич а ю щ е е с я тем, что, с целью упрощения устройства, оно содержит Р - 1 элементов И (Р- число разрядов счетчика адреса и регистра итераций, Р = 1 ояз М, М - число выборок в одном отсчете), а каждая из двух групп блоков памяти состоит из четырех блоков памяти, причем выходы первого и второго блоков памяти в первой группе подключены ко входам первого селектора, а третьего и четвертого блоков памяти - ко входам второго селектора, входы первого и третьего блоков па.мяти во второй группе подключены к выхо.дам первого мультиплексора, а входы втордгои четвертого блоков памяти - к выходам второго мультиплексора, первый и второй входы 1-го элемента И (1 = 1, , Р - ,1) нодклю.чены соответственно к выходу 1-го разрядасчетчика адреса и выходу (Р - 1)-го разряда регистра итерации, выходы элементов И подключены к адресным входам блока постояннойпамяти, выход первого разряда регистра адре- Оса подключен к управляющим входам первого и второго мультиплексоров, а выход (Р-гооазряда - к управляющим входам первого ивторого селекторов. Источники информации,принятые во внимание при экспертизе 1. Вьюхин Н. И. Индексное устройство про. цессора для выполнения быстрого преобразова" ния Фурье, Сб, "Автометрия", М 3, 1973. 2. Патент Великобритании У 1407401,кл, 6 4 А, 1974 (прототип).723582 а,оставитель В, Березкинехред М.Келемеш Корректор М.Пожо елактор ек Заказ 28/ ТиражПИ Государственноо делам изобретении, Москва, Ж - 35, Р Подписнотета СССР ом ытииаб д. 4/5 30 ская иал ППП "Патент, г, Ужгород, ул. Проектная