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

 

Изобретение относится к В1)1числительиой технике и предназначено для выполнения быстрого нреобразования Фурье, которое используется ири цифрово обработке сигналов. Цель изобретенияупрощение устройства. Поставленная нель достигается за счет того, что устройство имеет две грунпы блоков регистров 1, 2. арифметический блок 3, содержаии1Й сумматор 4, вычитатель 5 и умножитель ( комплексных чисел и два элемента задержки 7, 8, блок синхронизации 9, содержании э.мемент задержки И) и триггеры 11, 12, коммутаторы 13, 14, счетчик разрядов 15, счетчик адреса 1(, сдвиговый регистр итерани11 17, блок 18 -. 1емемтов И, блок постоянной памяти 19, коммутатор 20. Устройство реализует алгоритм быстрого преобразования Фурье с прореживанием 110 частоте и постоянной структурой от итерапии к итерации. 1 з. п. ф-лы, 4 ил. С (Л СО ГчЭ с:

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК (19) (11) А1 (51) 4 С> 06 I: 15 332 ю(гл (° !

3,,,",, ц

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

i 11 Ь41 l1u rel(P

Фиг. >

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

К А BTOPCHOMY СВИДЕТЕЛЬСТВУ (21) 4001671/24-24 (22 ) 30. 12.85 (46) 23.05.87. Ьк)л. № ) 9 (72) С. В. Редькин, С. )!. Васянин и С. Б. Плешаков (53) 681.32 (088.8) (56) Макаревич О. Ь., Спиридонов Б. Г.

I 1,ифровые IIp(>li«((. (>pt>I обработки на основе ЬИС. Заруб(..жная алектронная т(хника, № 1 (25!)), 1983.

Авторское свидетел ьство (.С(.Р

¹ 723582, кл. (> 06 F 15/332, 1977. (54) УСТРОГ!СТВО Д.>1Я ВЫПОЛНЕНИЯ

Г>Г>!СТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬ( (57) Изобретение относится к вычислительной технике и предназначено для выполнения быстрого преобразования Фурье, которое используется ири >(ифроиой Обработке

С И Г H (3 Ë (> В . 1 ) е.з Ь И 3 О О р (Те I I И я 3 I t p (> l I t(н И (. ссстроистВс>. 1Оста В, >(н н с) с) Il(х t t до(TH Гс)ется за Сч T ТОГО, IT(> VCTpOH(. T(3(> H %1(. (Т дв(. I pVII tt t>l блоков регистров 1, 2. арифметический блок 3, содержащий сумматор 4, вычитатель 5 и умножитсль 6 комнл h(ных чисел и два элемента зад pit(hH 7, 8, блок «инхронизации 9, содержащии элемент задержки 10 и триггеры l l, 12, к(>ммутаторы !3, 14, счетчик разрядОВ 15, сч(T IHh 3;(р(. i> 1(>, (. ;((3ВГОвый регистр итераций 17, блок 18 >лементов

И, блок постоянной памяти 19, коммутатор 20. У(Tpot)cTI)o pe;t;IH:3y(T;tлгоритм быстI l p (06 p;t:30 I3;t t l H >I Ф л р» (. (I I p () p (ж и В «ниеvl ио частоте и постоянной структурой от итерации к итерации. 1 з. и. ф-лы, 4 ил.

1312611 а ++=а „,+а з Ф/;

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

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

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

Устройство содержит две группы блоков 1 и 2 (сдвиговых) регистров, каждая из которых состоит из четырех блоков 1.1, 1.2, 1.3, 1.4 (2.1, 2.2, 2.3, 2.4), арифметический блок 3, содержагций сумматор 4 комплексных чисел, вычитатель 5 комплексных чи c;I, у множитель 6 комплексных чисел н два элемента 7 и 8 задержки, блок 9 синхронизации, состоящий из элемента !О задержки и двух триггеров 11 и 12, два коммутатора 13 и 14, счетчик 15 разрядов, счетчик 16 адреса, сдвиговый регистр 17 итераций, блок 18 элементов И, блок 19 постоянной памяти и коммутатор 20 тактовых импульсов.

Устройство реализует алгоритм БПФ с прореживанием по частоте и постоянной структурой от итерации к итерации, граф которого изображен на фиг. 2, где через

М, (i =0, 1, ..., )og!N) обозначены последовательные массивы данных направленного

i рафа, а через а „элементы массива М, (n=0, 1, ..., N — 1). ! акой алгоритм позволяет не менять порядок выбора операндов из памяти и записи и память результатов расчетов на всех этапах вычисления БПФ. При этом векторы массива М

А „,= Q „,);

В,« =I a «+ i I

С =I a „,+N/2I; а

D = ао„, i+N/2, где m=0, 1, ..., N/2 — 1, хранятся соответственно в секциях А, В, С kl D блока f le M HTH.

Общая формула получения элемента массива М,+ 1 из элементов массива М, имеет вид

<+! C

a»m+ 1=(Qm — - IV 2) ® Ж ,гк где Ф =в К; 1= g — 1.

Согласно формуле (1) при вычислении значений пары соседних элементов а + и а, „ > массива М, + производится выбор пары элементов а „, и a „,q N/ из первой и второй половин массива М, и поворотного множителя Ф "" из известной таблицы комплексных коэффициентов.

11а структурной схеме это соответствует выбору пары одноименных элементов из бло5

55 ков 1.1 (2.1) и 1.3 (2.3) или 1.2 (1.2) и 1.4 (2.4) одной группы и передаче их на первый и второй входы арифметического блока 3 с помощью коммутатора данных, причем выбор четных либо нечетных элементов определяется значением младшего разряда счетчика 16 адреса, подключенного к управляющему входу коммутаторов 13 и 14 и к управляющему входу коммутатора 20. Запись результатов производится в блоки 2.1 (1.1) и 2.2 (1.2) или 2.3 (1.3) и 2.4 (1.4) другой группы в зависимости от значения старшего разряда счетчика 6 адреса, подключенного к управляющему входу коммутатора 20 через элемент 10 задержки. Выбор нужного поворотного множителя Ю", W, ..., 1V из блока 19 постоянной памяти производится по адресу, который формируется в соответствии с формулой (1) с помощью блока 18 элементов, счетчика 16 адреса и регистра 7 итераций, состояние которого на первой итерации устанавливается «11...111», на второй — «11...110», на третьей — «11...110», на P-й — «00...000».

В исходном состоянии в группе блоков регистров имеется Лl элементов исходной выборки, счетчик 16 адреса и счетчик 15 разрядов сброшены, низким уровнем сигнала с выхода триггера 11 открыт коммутатор 18 и закрыт коммутатор 14.

Работа устройства начинается с подачи тактовых импульсов (ТИ) на счетный вход счетчика 15 разрядов и через коммутатор 20 на управляющие входы блоков 1.1 и 1.3 первой и 2.1 и 2.3 второй групп блоков регистров куда записывается информация с выходов арифметического блока 3. ТИ вызывают также считывание одноименных разрядов операндов ао, а и W соответственно из о о о блоков 1.1 и 1.3 групп блоков 1 регистров через коммутатор 13 и из блока 19 памяти на первый, второй и третий входы арифметического блока 3 и далее на входы сумматора 4, вычитателя 5 и элемента 7 задержки.

Разряды суммы Qo+Qgy с выхода сумматора 4 поступают на вход элемента 7 задержки, а соответствующие разряды разности ao-ag с выхода вычитателя 5 — — на первый вход умножителя 6, на второй вход которого поступают одноименные разряды поворотного множителя Ф, задержанные на нужное число тактов элементов 8 задержки.

Одноименные разряды результата аоо и

ai появляются на первом и втором выходах арифметического блока 3, являющихся выходами элемента 7 задержки и умножителя 6 через К ТИ.

Сигналом переноса счетчика 15 разрядов, завершающим выдачу первой пары операндов, изменяется уровень сигнала с выхода счетчика 16 адреса, по которому коммутатор 20 переключает ТИ с входов блоков 1.1 и 1.3 на входы блоков 1.2 и 2.9 группы блоков 1 регистров, а выходы последних подключаются через коммутатор 13 к первому

1312611 и второму входам арифметического блока 3, обеспечивая ввод в него разрядов операндов о (> а > и а>х4 > одновременно с одноименными разрядами коэффициента из блока 19 постоянной памяти.

По сигналу с выхода старшего разряда счетчика 16 адреса, задержанному на К тактов элементом 10 задержки, коммутатор 20 производит переключение ТИ с входов ззполненых блоков 2.1 и 2.2 нз входы блоков

2.3 и 3.4 группы блоков 2 регистров.

После выдачи в арифметический блок 3

ПОСЛЕДНИХ РаЗРЯДОВ ОПЕРаНДОВ а, ф I, а в и И сигнал на выходе Р— 1-го разряда счетчика 16 адреса переходит в исходное состояние, сдвигает кодовук> комбинацию в регистре !7 итераций на одну позицию в сторону старших разрядов и взводит триггер 12, сигнал на выходе которого удерживает счетчик 15 разрядов в сброшенном (остоянии до конца итерации, запрещая дальнейшее считывание операндов из блока 19

llOCTOHHHOH llBMBTH. 33llHCb ари(>метическом блоке 3 разрядов результата а> 2 и а„> в блоки 2.3 и 2.4 группы бло1 ков 2 регистров продолжается в течение еще

К тактов, после чего сигнал на выходе элемента 10 задержки переходит в исходное состояние, сбрасывает триггер 12, снимая тем самым блокировку со счетчика 15, и переключает триггер 11, выходной сигнал которого переключает коммутатор 20 для выдачи ТИ на входы блоков 1.1 и 1.3 второй и 1.1 и 1.2 первой групп блоков регистров, закрывает коммутатор 13 и открывает коммутатор 14, подготавливая устройство к следуюгцей итерации, выполнение которой полностью аналогично рассмотренной.

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

l. Устройство для выполнения быстрого преобразования Фурье, содержащее первую и вторую группы блоков регистров, по четыре блока регистров в каждой, первый и второй коммутаторы, арифметический блок, блок постоянной памяти, блок э Iew IIToB И, сдвиговый регистр итераций и счетчик адреса, информационный выход которого подклк>чен к первому входу блока элементов И, выход которого подключен к первому адресному входу блока постоянной памяти, выход которого подключен к входу задания коэффициентов арифметического блока, а выход сдвигового регистра итераций подключен к второму входу блока элементов И, отличающееся тем, что. с целью упрощения устройства, оно содержит третий коммутатор, первый и второй триггеры, счетчик разрядов и элемент задержки, выход которого подключен к тактовым входам первого и второго триггеров и первому управляюц(ему входу третьего коммутатора, выходы с первого

1О

Но четвертый которого подклк)ч klt>l к такт(>вым входам соответствующих блоков регистров первой группы, выходы которых подклк)чены к соответствукнцим информационным входам первоп> коммутатора, первый и второй выходы которого соединены соответственно с первым и вторым выходами второго коммутатора и подключены к входам соответствеHHo первого и второго операндов арифметического блокз, первый выход результата которого подключен к информационным входам первых и третьих блоков реги(тров первой и второй групп, информационные входы вторых и четвертых блоков регистров которых подключены к второму выходу результата арифметического блока, выход первого триггера подключен к первым управляющим входам первого и второго коммутаторов, второму управляюгцему Входу третьего Koммутзтора, выходы с пятого по восьмой которого подключены к тактовым вх(>дам соответствующих блоков регистров второй группы, выходы которыx подключены к соответствующим информационным Входам второп> коммутатора, выход младшего разряда счетчика адреса подключен к вторым упрзвлякнцим входам первого и второго комму T B To l) o (3 и т р(. т ье м х $ II l> B B 1 ÿ Io I lf,ñ м p входу третьего коммутатора, информационныи вход которого соединен со счетным Входом счетчика разрядов и является тактовым входом устройства, выход старшего разряда счетчика адреса подключен к тактовому входу сдвигового регистра итераций, входу элемента задержки и установочному входу второго триггера, выход которого подключен к входу разрешения счета счетчика разрядов выход переноса и информационный выход которого подключены соответственно к счетному входу счетчика адреса и второму адресному входу блока постоянной памяти.

2. Устройство»о и. 1, отличающееся тем, что арифметический блок содержит первый и второй элементы задержки, умножитель комплексных чисел, вычитзтель комплексных чисел и сумматор комплексных чисел, выход которого подключен к входу первого элемента зздержки, выход которого является выходом первого результата блока. выходом второго результата которого является выход умножителя комплексных чисел, первый f3XO)1 KOTOPOI ПОДКЛК)ЧЕН К Bt>1 ХОД\ ВЫчитателя комплексных чисел, первый вход которого соединен с первым входом сумматора комплексных чисел и является входом первого операнда блока, входом BT()!)()I операнда которого являются соединенные между собой вгорые входы сумматора комплексных чисел и вычитзтеля комплексны. чисел, второй вход умножитег(я K(>÷ï.f(êcных чисел подклк>чен к выходу второго элемента задержки. вход которого является вхо,(ом задания коэффициентов блока.

1312611 м,

Qm„a

lue2

II т

+- — х м

Составитель А Варанов

Редактор Н. Рогулич Техред И. Верее Корректор А. Тяско

Заказ 1845/49 Тираж 673 Подписное

Б11ИИГЗИ осударствснного комитета О:(:Р но делам изобретений и открытий

I 13035, Москва, Ж 85, Раунгская наб., д. 415

ПроизводствеHHo-нолиграфическ<н преднриягис, г Ужгород, ул. Проектная, 4