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

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

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

На фиг. 1 представлена структурная схема устройства для выполнения БГ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 комплексных чисел, умножитель 6 комплексных чисел и два элемента 7 и 8 задержки, блок 9 синхронизации, состоящий из элемента 10 за- держкн и двух трип-еров 11 и 12, два ком- мутатора 13 и 14, счетчик 15 разрядов, счетчик 16 адреса, сдвиговый регистр 17 итераций, блок 18 элементов И, блок 19 постоян- Н1)й памяти и ко.ммутатор 20 тактовых импульсов.

Устройство реализует алгоритм БПФ с прореживанием по частоте и постоянной структурой от итерации к итера 1ии, граф которого изображен на фиг. 2, где через М, (/(), 1 logi/V) обозначены последовательные .массивы данных направленного графа, а через а „ элементы массива М, (, 1 ,V-1).

Гакой алгорит.м позволяет не менять порядок выбора операндов из памяти и записи в память результатов расчетов на всех этапах Р ычнслепия БПФ. При этом векторы массива М

,,r,

В т ;

,+ 72|;

Dm + /V/2|,

где , 1, ..., /2-,

хранятся соответственно в секциях А, В,

С и D блока памяти.

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

ггт1 + п+л/2;

гт

U2m I

(а „-а ;„ + Л/2)-№(

-,-f Г Ц-, .

(1)

где 6Согласно формуле (1) при вычислении значений пары соседних элементов d и aSm ) I массива М,+ | производится выбор пары элементов а „, и a ,,,)( из первой и второй половин массива М, и поворотного мно- жите.:1я из известной таблицы комплексных коэффициентов.

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

,5 20 -

-зп

5

40

45

50

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) другой группы в зависимости от значения старшего разряда счетчика 16 адреса, подключенного к управляющему входу коммутатора 20 через элемент 10 задержки. Выбор нужного поворотного множителя W°, W , ..., из блока 19 постоянной памяти производится по адресу, который формируется в соответствии с формулой (1) с помощью блока 18 элементов, счетчика 16 адреса и регистра 17 итераций, состояние которого на первой итерации устанавливается «11...111, на второй - «11..,110, на третьей - «11...110, на Я-й «00...000.

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

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

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

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

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

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

После выдачи в арифметический блок 3 последних разрядов операндов а).)-, а| i и t/ 2-i сирнал на выходе Р-1-го разряда счетчика 16 адреса переходит в исходное состояние, сдвигает кодовую комбинацию в регистре 17 итераций на одну позицию в сторону старших разрядов и взводит триггер 12, сигнал на выходе которого удерживает счетчик 15 разрядов в сброшенном состоянии до конца итерации, запрещая дальнейшее считывание операндов из блоки 19 постоянной памяти. Запись оставшихся в арифметическом блоке 3 разрядов результата ai-,2 и в блоки 2.3 и 2.4 группы блоков 2 регистров продолжается в течение еще К тактов, после чего сигнал на выходе элемента 10 задержки переходит в исходное состояние, сбрасывает триггер 12, снимая тем самым блокировку со счетчика 15, и переключает триггер 11, выходной сигнал которого переключает коммутатор 20 для выдачи ТИ на входы блоков 1.1 и 1.3 второй и 1.1 и 1.2 первой групп блоков регистров, закрывает коммутатор 13 и открывает коммутатор 14, подготавливая устройство к следующей итерации, выполнение которой полностью аналогично рассмотренной.

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

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

0

5

0

5

0

5

0

5

по четвертый которого подключены к тактовым входам соответствующих блоков рег ист- ров первой группы, выходы которых подключены к соответствующим информационным входам первого коммутатора, первый и второй выходы которого соединены соответственно с первым и вторым выходами второго коммутатора и подключены к входам соответственно первого и второго операндов ари(}).метическо1 о блока, первый выход результата которого подключен к информационным входам первых и третьих блоков регистров первой и второй групп, информационные входы вторых и четвертых блоков регистров которых подключены к второму выходу результата арифметического блока, выход первого триггера подключен к первым управляющим входам первого и второго коммутаторов, второму управляюп1ему входу третьего коммутатора, выходы с пятог о но восьмой которого подключены к тактовым входам соответствующих блоков регистров второй группы, выходы которых подключены к соответствующим информационным входам второго коммутатора, выход млад1нег-о разряда счетчика адреса подключен к вто- рьз1м унравляющим входам первого и второго коммутато)ов и третьему управляющему входу третьего коммутатора, информационный вход которого соединен со счетным входом счетчика разрядов и является тактовым входом устройства, выход старшего разряда счетчика адреса подключен к тактовому входу сдвигового регистра итераций, входу элемента задержки и установочно.му входу BTopoi o триггера, выход которого подключен к входу разрегнения счета счетчика разрядов выход переноса и информационный выход которого подключены соответственно к счетному входу счетчика адреса и второму адресному входу блока постоянной памяти. 2. Устройство по п. 1, отличающееся тем, что арифметический блок содержит первый и второй элементы задержки, умножитель комплексных чисел, вычитатель комплексных чисел и сумматор ком1и 1ексных чисел, вь1ход KOTopoi o подключен к входу первого элемента задержки, выход которого является выходом первого результата блока, выходом BTcjporo результата которого являе1ся выход умножителя комнлексных чисел, первый которого подключен к выходу вы- читателя комплексных чисел, первый вход которого соединен с первым входом сумматора ком 1лексных чисел и является входом нервого операнда блока, входом второго операнда которого являются соединенные между собой вторые входы сумматора комплексных чисел и вь 1читателя комплексных чисел, второй вход умножителя комплексных чисел подключен к выходу второго элемента задержки, вход которого является вхо.чом задания коэффициентов блока.

9ие2

(2т а иг.Ъ

Изобретение относится к В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 ил. С (Л СО ГчЭ с: