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

113

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

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

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

Устройство содержит две группы бло ков 1 и 2 памяти с произвольно выборкой, каждая из которых состоит из дпух блоков 1.1 и 1.2 (2.1 и 2.2), арпфме гически; б:гок 3, содержащий сумматор 4 i oMn:i(jKCHhix чисел, вычита- 1 ель 5 комплексных чисел, у июжитель

6KOMnjleKCHbix чисел и два элемента

7и 8 задержки, блок 9 синхронизации, содержащий два триггера 10 и 11

и элемент 12 задержки, дна коммутатора 13 и 14 данных, два счетчика адреса 15 и 16, дешифратор 17 адреса, сдвиговый регистр 18 итераций, блок элемеитогз И 19, блок 20 постоянной памяти и кo мyтaтop 21 сиг налов записи .

Устройство реализует алгоритмы БПФ с прореживанием по частоте и постоянной структурой от итерации к итерации, граф которого изображен на фиг.2, где через М (i 0,1,..., logjN) обозначены последовательные массивы данных Н 1Г1равленного графа, а через а| - элементы массива ЬГ (п 0,1..., N). Такой алгоритм позволяет не менять порядок ныбора операндов из памяти и записи в память результатоЕ) расчетов на всех этапах вычисления БПФ, а также дает возможность разделить каждый блок памяти только на две секции при простейшей организации буфера ввода-вывода.

При этом векторы массива М;

2т 2т

2m L lrathjiJ L 2 m-и N/2 J

хранятся соответственно в четньсх. и нечетных ячейках секций А и В блока памяти.

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

а

т+ N12

, , , ., (I) 2п,,, «-

1-де m 0,1,..., -т -

i 0,0,...,

Согласно формуле (I) при вычислении значений пары соседних элементов

массива М;, произво1 « i

Я о И а.

7т V m«i

15

дится выбор пары элементов а

и

а к,, из первой и второй половин

ГТ1 + /2

массина М и поворотного множителя

т( W из габ.гп1цы комплексных коэффициептов. На с.груктурной схеме это соотве 1 ствует выбору пары одноименных элементов из блоков 1.1(2.1) и 1.2(2.2) одной группы и передаче их на первый и второй информационные

входы блока 3 с помощью коммутатора да1П1ых. Причем выбор четных либо нечетных элементов определяется значением +1-ГО разряда счетчика 15 адреса, соединенного с переключающим

входом коммутаторов 13 и 14 данных.

Запис1 результатов производится в соседние ячейки блоков 2.1(1.1) или 2.2(1.2) другой группы в зависимости от значения старшего разряда

счетчика 16 адреса, соединенного с ьходом коммутатора 21 импульсов записи. Выбор нужного поноротного мно,,0 t ,. N/2 -I ,ж-ителя W , W , . . . , W из блока 20 ПОСТОЯННО памяти производится

по адресу, который формируется в со- ответст1 ии с формулой (1) с помощью блока элементов И 19, счетчика 15 адреса и рег истра 18 итераций, состояние которого на первой итерации

I 1 . . . I 1 I , на второй - 1 1 ... 1 1 О , на третьей - 11...100, на Р-й - 00...000.

Перед началом выполнения БПФ в блоке 1 (оперативной памяти) имеется

N элементов исходной выборки. Счетчики 15 и 16 адреса сбропгены. Счетчик 16 заблокирован низким уровнем сигнала с выхода элемента 12 задержки. Счетчик 15 разблокирован высоким

уровнем сиг нала с выхода тригтера II . Низким уровнем сигнала с выхода тригтера 10 открыт коммутатор 13 и закрьп коммутатор 14. Дешифратор 17 адреса установлен в положение, в котором выходы счетчикон 15 и 16 адреса подключены соответственно к адрес- HI.IM входам секций первого и второго блокон памяти.

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

вызывая считывание одноименных раэря- Q 17 выходы счетчиков 15 и дов операндов а°, ащ и W° из блока 16 и разблокирует сче этом счетчик 16 блс1кируе с выхода элемента 12 зад гер 10, на счетный вход тупил сигнал переполнени 16, переключается, закры тор 13, открывая при это 14, подключает с помощью

ным входам блоков групп редством коммутатора 21 ледним режимы чтения и ветственно .

ков оперативной 1 и постоянной 20 памяти на входы арифметического блока 3 и далее - на входы сумматора 4, вычитателя 5 и элемента 8 задержки 8. Соответствующие разряды суммы (г

поступают на вход элемента 7 задерж

а одноименные разряды разности

о

а

N12

- на вход умножителя 6, на

другой вход которого приходят соответствующие разряды поворотного множителя W°, задержанные на нужиое число тактов элементом 8 задержки.

Через К тактов импульсов ТИ на первом и втором выходах арифметического блока 3, являющихся выходами элемента 7 задержки и умножителя 6, появляются одноименные разряды результата а и а,. На выходе элемента 12 задержки появляется высокий уровень сигнала с выхода триггера 11 которым разрешается счетный режим счетчика 16 адреса и открывается коммутатор 21 сигналов записи. Запись указанных разрядов результата производится в блок 2 памяти по адресу, который определяется состоянием выхода счетчика 16.

После выдачи в арифметический блок 3 последних разрядов операндов ы;-: -1

а,

и W

сигнал перепеладреса поступает итераций и триг

N/2-1 N- 1

нения с счетчика 15 на входы регистра 1

гера 11. В регистре 18 итераций происходит сдвиг кодовой комбинации на одну позицию в сторону старших разрядов. Триггер 11 сбрасывается и блокирует счетчик 15, запрещая дальнейшее считывание операндов из блока 1 оперативной и блока 20 постоянной памяти.

Запись оставшихся в арифметическом блоке 3 разрядов операндов а.

(„

и а продолжается в течение еде К

тактов, после чего триггер 11 взводится сигналом переполнения счетчи

17 выходы счетчиков 15 и

ка 16 и разблокирует счетчик 15. При этом счетчик 16 блс1кируетгя сигналом с выхода элемента 12 задержки. Триггер 10, на счетный вход которого поступил сигнал переполнения счетчика 16, переключается, закрывает коммутатор 13, открывая при этом коммугатор 14, подключает с помощью дешифратора

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

Этим завершается первая итерация вычисления БПФ. Остальные итерации выполняются аналогично.

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

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

рым выходами второго коммутатора и п(1дключены к входам соотЕ)етственно парного и второго операндов арифметического блока, первый и второй выходы результатов которого подключены к входам соответственно правой и левой частей операнда информационных входов первого, второго, третьего и четвертого блоков памяти, второй выход дешифратора адреса подключен к лдреснь1М входам третьего и четвертого блоков памяти, выходы реальной и мнимой частей операнда которых подключены соответственно к первому, второму, третьему и четвертому информационным входам второго коммутатора, управлякш ий вход которого сое- л,инпн с первым управляющим входом первого коммутатора и ходу L+1-го (L-разрядность операнда) разряда первого счетчика адреса,счетный вход которого соединен с информационным входом третьего коммутатора, счетным входом второго счетчика адреса и является тактовым входом устройства, выходы разрядов с первого по L-й первого адресного счетчика подключены к входам соответствующих разрядов второго адресного входа блока постоянной памяти, выход переноса первого счетчика адреса подключен к установочному входу первого триггера, выход которого подключен к входу разрешения счета первого счетчика адреса и входу элемента задержки, выход которого подключен к первому управляющему входу третьего коммутато337904 ра

10

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

15

25

2, Устройство по п.1, отличающееся тем, что арифметический блок содержит два элемента задержки, ум)ожитель комплексных чисел,

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

35

7904 ра

6

10

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

Изобретение относится к области вычислительной техники и предназначено для выполнения алгоритма быстрого преобразования Фурье (БПФ), используемого при цифровой обработке сигналов. Цель изобретения - упрощение устройства. Поставленная цель достигается за счет того, что устройство состоит из двух групп блоков памяти 1,2, арифметического блока 3, содержащего сумматор 4, вычитатель 6, умножитель 7 комплексных чисел и элементы задержки 7,8, блока синхронизации 9, состоящего из триггеров 10,11 и злемента задержки 12, коммутаторов 13 и 14, счетчиков адреса 15 и 16, дешифратора адреса 17, сдвигового регистра итераций 18, блока элементов И 19, блока постоянной памяти 20 и коммутатора 21. Устройство реализует алгоритмы БПФ с прореживанием по частоте и постоянной структурой от итерации к итерации. 1 з.п,. ф-лы, 3 ил. i 1сл DO САЭ СО

г /тг

ФиеЗ