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

 

Изобретение относится к вычислительной технике и может быть исполь-1 зовано в системах цифровой обработки сигналов. Цель изобретения - уп-1 решение устройства. Поставленная цель достигается за счет того, что 1 состав устройства входят входной оммутатор 2, арифметический блок 3, коммутатор 4 операндов, блоки 5-10, блок 11 постоянной памяти, элементы И 12, счетчик 13, сдвиговый регистр 14, счетчик 15 итераций, блок ( 16 постоянной памяти, коммутаторы 17.1-17.6, элементы НЕ 20, 21, элемент ИЛИ 23. 1 з.п.ф-лы, 22 ил. 7 J (Я со Фиг.1

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

З«Л Ю

РЕСПУБЛИК

09) 00 рц С 06 Р 15/332

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

ПО ИЗОБРЕТЕНИЯМ И ОТНЯТИЯМ

ПРИ ГКНТ СССР

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

К A STOPCHOMY СВИДЕТЕЛЬСТВУ (21) 4654485/24 (22) 23.02.89 (46) 07.01.91. Бюл. № 1 (72) Д.В.Корчев и О.M.Ïoâàðåíêî (53) 681.32(088.8) (56) Рабинер Л., Гоулд Б. Теория и

;применение цифровой обработки сигналов. М.: Мир, 1978.

Авторское свидетельство СССР ,¹ 723582, кл. G 06 F 15/332, 1978. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БЫСТ;РОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ. (57) Изобретение относится к вычисли2 тельной технике и может быть исполь- зовано в системах цифровой обработки сигналов. Цель изобретения — уп рощение устройства. Поставленная цель достигается за счет того, что состав устройства входят входной оммутатор 2, арифметический блок 3, коммутатор 4 операндов, блоки 5-10,. блок 11 пос-.îÿííîé памяти, элементы И 12, счетчик 13, сдвиговый регистр 14, счетчик 15 итераций, блок

".16 постоянной памяти, коммутаторы

17. -17.6, элементы HF. 20, 21, элемент ИЛИ 23. 1 з.п.ф-лы, 22 ил.

1619300

Изобретение относится к вычислительной технике и .может быть использовано в системах цифровой обработки сигналов, 5

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

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

Устройство (фиг.1 и 2) содержит информационный вход 1, входной комMJTBTop 2, арифметический блок 3, коммутатор операндов 4, блоки 5-10 памяти, блок 11 постоянной памяти (весовых коэффициентов), 1 элементов

И 12.1-12. 1.(где 1 = 1оp

ИЛИ 23, входы управления записью— считыванием 24. 1-24.,6 блоков 5-10 памяти, адресные входы 25.1-25.6 блоков 5-10,памяти, выход 26 пер вого разряда счетчика 13.

Арифметический блок 3 (фиг.3) содержит сумматор (действительной части)

27, сумматор (мнимой части) 28, вычитатель (действительной части) 29, вычитатель (мнимой части) 30, коммутатор (разностей) 31 и 32, входы реальной 33 и мнимой 34 частей весового коэффициента, вычитатель 35, умножители 36 и 37, регистры 38 и 39, коммутаторы (выходные) 40 и 41, сум- матор 42.

Рассмотрим работу отдельных узлов устройства.

Арифметический блок 3 устройст- 45 ва производит вычисление базовой операции алгоритма БПФ за два такта. Входные операнды А и В в тече ние двух тактов подаются на одноименные. информационные входы. Весовой коэффициент также в течение двух тактов поступает на соответствующие входы. В первом такте на управляющем входе нулевое значение..Сумматоры 27 и .8> вычисляют ReC =- РеА + ReH u ImC = ImA + 55

+ ImB соответственно, которые через коммутаторы 40 и 41 поступают на выход блока 3. Вычитатели 29 и 30 вычисляют ReC = ReA — ReB u ImC = ImA—

ImB соответственно. При этом значение ReC = ReA — ReB поступает на первый вход умножителя 36, а значение

ImC = ImA — ImB на первый вход умножители 37. На вторые входы умножителей 36 и .37 поступают значения соответственно.

С приходом синхроимпульса на управляющем входе блока 3 появляется единичное значение. В регистрах 38 и 39 записываются значения (ReAReB)ReW и (ImA — ImB)ImW соответственно. На первые входы умножителей

36 и 37 поступают значения ImA-ImB и ReA-ReB соответственно, на вторых входах умножителей 36 и 37 — значения ReW u ImW соответственно, на выходах умножителей 36 и 37 — значения (ImA-ImB)ImW и (ReA-ReB)ImW соответственно, на выходе вычитателя

35 — значение ReD = (ReA-ReB)ReW†(ImA-ImB)ImW, которое через коммутатор 40 поступает на выход действительной части блока 3, на выходе сумматора 42 — значение ImD = (ImAImB)ReW + (ReA-ReB)ImW, которое поступает через коммутатор 41 на выход мнимой части арифметического блока 3.

Формирование весовых коэффициентов производится блоком 11 памяти и элементами 12.1-12.6.

На итерациях алгоритма БПФ происходит подача нулей на вторые входы соответствующих элементов 12.1-12.6, что приводит к требуемому прорежи- . ванию весовых коэффициентов.

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

Будем рассматривать работу устройства на примере N = 16. На вход 18 поступает последовательность тактовых импульсов. На вход 19 установки поступает верхний логический уровень, который производит установку в нулевое состояние счетчика 13, регистра 14. Со старшего выхода регистра 14 поступает значение "Лог.О", которое обнуляет через элемент НЕ 21 счетчик 15 итерации и устанавливает на управляющем входе регистра 14 значение "Лог.1", разрешающее параллельное занесение информации в регистр. До поступления на вход !9 нижнего логического уровня все узлы находятся в описанном состоянии. По5 16193 сле поступления "Лог.О" на вход 19 начинается этап загрузки входной информации в блоки памяти устройства. Входные отсчеты Х„ (II = О, И-!) поступают последовательно на вход 1 устройства. На входах элемента ИЛИ

23 нулевое значение, поскольку регистр 14 находится в обнулении.

На вход управления коммутатора 2 поступает "Лог.О" с выхода элемента

23, разрешающий передачу информации с входа 1.

В первые четыре такта на выходах

25.1-25.6 второй группы управляющих выходов блока ПЗУ 16 — состояние

100000 соответственно, которое разрешает работу блока 5 памяти. На управляющих входах коммутаторов 17.117.6 — значение соответственно 000000,20 которые разрешают прохождение тактовых импульсов с первого входа коммутатора 17.1 на вод 24,1 блока 5 памяти. Через четыре такта входные отсчеты Х, Х, Х, Х> записаны после- 25 довательно в блок 5 памяти. В следую-, щие четыре такта на входах 25.1-25.6 блоков 5-10 памяти — значения 010000 соответственно. На управляющих входах коммутаторов 17.1-17.6 значения не 30 меняются. При этом следующие четыре отсчета Х4, Хз-, Х, Х> записаны в блок 6 памяти. В третьей четверке тактов на управляющих входах 25.1-25.6 блоков 5-10 памяти — значения 001000

35 соответственно.

На управляющих входах «17.1-17.6 значения не меняются. Поэтому отсчеты Х,Х, Х, Х ц записаны в блок 7 памяти. Аналогичным образом отсче- 40 ты Х, Х,,Х1 Х I5 записаны в блок Я памяти. При этом на управляющих входах 25.1-25.6 блоков 5-10 памяти значения 000100 соответственно. На управляющих входах коммутаторов 17.1- 45

17.6 значения не меняются.

После выдачи импульса переноса с выхода счетчика 13 происходит запись всех единиц в регистр 14. При этом регистр 14 переходит в режим 5р сдвига, а со счетчика 15 снимается сигнал обнуления.

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

Первая итерация.

Расположение информации в блоках

5-10 памяти показано на диаграмме (фиг.4). Условные обозначения блоков

00 6 памяти соответствуют блокам 5-10 сверху вниз. Первые четыре такта на уп— равляющих входах 25.1 25.6 блоков

5-10 памяти значения l0101. На управляющих входах коммутаторов 17.1—

17.6 значения 101000 соответственно, которые разрешают коммутаторам i7.1 и 17.3 передачу информации с вторых входов. Поэтому блоки 5 и 7 памяти сдвигают информацию с частотой, равной половине тактовой, а блоки 9 памяти с частотой, равной тактовой. На первый управляющий вход коммутатора

4 приходит код, разрешающий передачу информации с первого входа на первый выход. На второй управляющий вход коммутатора 4 приходит код, разрешающий передачу информации с третьего входа на второй выход. Коммутатор 2 до конца вычислений передает информацию на выход с выхода арифметическо-, го блока 3. На всех диаграммах стрелками A И В условно показаны выходы блоков 5-10 памяти, подключенные через коммутатор.4 к соответствующим входам блока 3. Входной стрелкой на диаграммах показан результат Y

4 (где i — номер итерации, k — номер операнда), записываемый в соответствующих блоках 5-10 памяти.

Первый таку (фиг.4). На первом входе А арифметического блока 3 значение Хо, на втором — Х . На выходе блока 3 значение У на входах весо-! вого коэффициента блока 3 установлено значение соответствующего поворачивающего множителя, которое поступает с соответствующих выходов блока 11 постоянной памяти.

Второй такт (фиг.5). На входах А и В арифметического блока не меняется.

Значение У, записано в первый регистр блока 9 памяти, Третий такт (фиг.б). На входах А и В блока 3 значения Х» и Х соотственно. Запись,,информации йроисхсдит последовательно в блок 9 памяти. На входах весового коэффициента блока 3 следующее значение поворачивающего множителя.

Четвертый такт (фиг.7). Все режимы блоков аналогичны предыдущим тактам.

Происходящую попутно запись информации в блоки 5 и 7 памяти в дальнейшем учитывают и для простоты на диаI граммах свободные ячейки этих блоков заполняются нулями;

1619300

В следующей четверке тактов на входах 25. 1-25.6 блоков 5 и 10 памяти значение 101001 соответственно. На управляющих входах коммутаторов 17.117.6 значения 101000 соответственно.

Расположение операндов в этой четверке тактов показано на диаграммах (фиг.8-11) .

В тактах 9-12 (фиг. 12-15) информация на вход А блока 3 поступает с выхода блока 6 памяти, на вход В блока 3. — с выхода блока 8 памяти.

Запись информации производится в блок

5 памяти. На входах 25.1-25.6 управления блоков памяти 5-10 — значения

11011. На входах управления коммутаторами 17.1-17.6 значения 010.100. Расположнние информации в этих тактах показано на фиг.12-15.

В тактах 13-16 (фиг.16-19) считывание информации производится также из блоков 6 и Я памяти, а запись производится в блок 7 памяти. На входах

25.1-25.6 блоков 5-10 памяти значения 25

011100. На управляющих входах коммутаторов 17.1-17.6 значения 010100 соответственно.

Расположение операндбв после первой итерации показано на фиг.20. После выдачи импульса переноса с выхода счетчика 13 в первый разряд регистра 14 записывается нулевое значение. Счетчик 15 установлен в значение 01. Нулевое значение с первого выхода регистра 14 через элемент И 12.1 поступает

35 на младший адресный разряд блока 11 постоянной памяти. Это приводит к двукратному прореживанию весовых коэффициентов на второй итерации вычисления БПФ.

Вычисление второй итерации производится по такому же принципу, как описано.

В первой четверке тактов на входы

В и А блока 3 информация поступает с блоков 9 и 5 памяти соответственно, а запись — н блок 6.

Вторая четверка тактов отличается,только тем, что информация записывается в блок 8 памяти.

В третьей четверке тактов на входы

А и В блока 3 информация поступает с ныходсв блоков 10 и 7 памяти соответственно. Запись проводится н блок

9 памяти.

SS

Последняя четверка от предыдущей отличается только тем, что.запись информации проводится н блок 9 памяти.

Расположение операндов в блоках 5-10 памяти после второй итерации показано на диаграмме (фиг.21).

Расположение информации н блоках

5-10 памяти после третьей итерации показано на диаграмме (фиг.2?).

На четвертой итерации проводят выбор только тех блоков 5-10 памяти, из которых проводят считывание информации.

Результаты четвертой итерации поступают на выход 22 устройства.

С приходом импульса переноса с выхода счетчика 13 на последней итерации на последнем выходе регистра 14 появляется нулевое значение, которое обнуляет через элемент HE 21 счетчик 15 итераций и переводит в режим параллельной записи регистр 14.

Коммутатор 2 при этом передает информацию с первого входа. При этом происходит загрузка н блоки 5-10 памяти следующего массива, формулаизобретения

1. Устройство для вычисления быстрого преобразования Фурье, содержащее арифметический блок, шесть блоков памяти, первый блок постоянной памяти, 1 (1 =, 1о8 И-1; где N — размер преобразования) элементов И, сдниговый регисстр, счетчик, выход i ãî, !

2,1+1) разряда которого подключен к первому входу (i-1)-го элемента ,И, выход которого подключен к (i-1)— му адресному входу первого блока постоянной памяти, первый и второй выходы которого подключены к входам соответственно реальной и мнимой ча,стей коэффициента арифметического блока, первый тактовый вход которого соединен со счетным входом счетчика и является тактовым входом устройства, установочным входом которого является вход обнуления счетчика, выход переноса которого подключен к тактовому входу сднигоного регистра, выход j-го (j =1,1) разряда которого подключен к второму входу j-го элемента И, последовательный вход сднигоного регистра является входом задания логического нуля устройства, входом задания логической единицы которого является параллельный вход сднигового регистра, о т л и ч а юш е. е с я тем, что, с целью упрощения устройства, оно содержит два

1619300 элемента HF., элемент ИЛИ, счетчик итерации, второй блок постоянной памяти, входной коммутатор, коммутатор операндов и шесть коммутаторов

Э причем выходы блоков памяти с первого по шестой подключены к информационным входам соответственно с первого по шестой коммутаторы операн дов, первый и второй выходы которого подключены к входам соответственно первого и второго операндов арифметического блока, выход которого является информационным выходом устрсй1 ства и подключен к первому информационному входу входного коммутатора, выход которого подключен к информационным вхоцам блоков памяти с первого по шестой, выход первого разряда счетчика подключен к первому инфсрмацисн- 2О ному входу m-го (m =1,6) коммутатора и второму тактовому входу арифметическбго блока, выход первого разряда сдвигового регистра подключен к пер вому входу элемента HJIH вьжсд которого подключен к управляющему входу входного коммутатора, второй информационный вход которого является информационным входом устройства, установочный вход которого подключен к входу первого элемента HF. выход которого подключен к входу- обнуления сдвигового регистра, выход (1+1)-ro разряда которого подключен к второму входу элемента ИЛИ и входу второго элемента НЕ, выход которого подключен к входу управления сдвигом сдвигового регистра и входу обнуления счетчика итераций, информационный выход которого подключен к первому адресному входу второго блока постоянной памяти, m-й адресный и ш-й управляюший выходы которого подключены соответственно к адресному входу m-го блока памяти и управляющему входу m-го коммутатора, выход которого подключен к входу управления запись -считыванием, m-го блока памяти, выход переноса счетчика подключен к счетному входу счетчика итераций, выходы (1-1)-гс и

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

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

Рр ж 1,„Ф

Фиг. 3! б19300

1 6! 93.00 . Рог.11

Юыг, D

Q7Lrz 15

16! 9300

1619300

Составител А.Баранов

Техред М.Моргентал Корректор Н.Ревская

Редактор М.Бланар

-Заказ 50 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 101