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

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

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

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

Устройство (фиг.1 и 2) содержит информационный вход 1, входной ком- мутатор 2, арифметический блок 3, коммутатор операндов 4, блоки 5-1C памяти, бло к 11 постоянной памяти (весовых коэффициентов), 1 элементов И 12.1-12.1 -(где 1 logЈN-1) ,счетчик 13 (по модулю N), сдвиговый регистр 14, счетчик 15 итераций, блок 16 постоянной памяти, коммутаторы 17,1-17,6, тактовый вход 18, вход 19 установки, элементы НЕ 20 и 21, информацией- ный выход 22 устройства, элемент ИЛИ 23, входы управления записью - считыванием 24, 1-24„6 блоков 5-10 памяти, адресные входы 25.1-25.6 блоков 5-10;памяти, выход 26 пер- БОГО разряда счетчика 13.

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

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

Арифметический блок 3 устройст- ва производит вычисление базовой операции алгоритма БПФ за два такта. Входные операнды А и В в тече - ние двух тактов подаются на одноименные, информационные входы. Весовой коэффициент также в течение двух тактов поступает на соответствующие вхды. В первом такте на управляющем вхде нулевое значение. Сумматоры 27 и 28 вычисляют ReC - ReА + ReB и ImC ImA -i- ImB соответственно, которые чере коммутаторы 40 и 41 поступают на выход блока 3. Вычитатели 29 и 30 вычисляют ReC ReA - ReB и ImC ImA ImB соответственно. При этом зняче- ние ReC ReA - ReB поступает на первый вход умножителя 36, а значение ImC 1mA - ImB на первый вход умножители 37. На вторые входы умножителей 36 и 37 поступают значения соответственно.

С приходом синхроимпульса на управляющем входе блока 3 появляется единичное значение. В регистрах 38 и 39 записываются значения (ReA- ReB)ReW и (imA-ImB)lmW соответственно. На первые входы умножителей 36 и 37 поступают значения ImA-ImB и ReA-ReB соответственно, на вторых входах умножителей 36 и 37 - значения ReW и ImW соответственно, на выходах умножителей 36 и 37 - значения (ImA-ImB)ImW и (ReA-ReB)ImW соответственно, на выходе вычитателя 35 - значение ReD (ReA-ReB)ReW- -(ImA-ImB)ImW, которое через коммутатор 40 поступает на выход действительной части блока 3, на выходе сумматора 42 - значение ImD (1mA- ImB)PeW + (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, разрешающее параллельное занесение информации в регистр. До поступления на вход 19 нижнего логического уровня все узлы находятся в описанном состоянии. По51

еле поступления Лог,0 на вход 19 начинается этап загрузки входной информации в блоки памяти устройства. Входные отсчеты Х (n О, N-1) поступают последовательно на вход 1 устройства. На входах элемента ИЛИ 23 нулевое значение, поскольку регистр 14 находится в обнулении. На вход управления коммутатора 2 поступает Лог.О с выхода элемента 23, разрешающий передачу информации с входа 1 .

В первые четыре такта на выходах 25.1-25.6 второй группы управляющих выходов блока ПЗУ 16 - состояние 100000 соответственно, которое разрешает работу блока 5 памяти. На управляющих входах коммутаторов 17.1- 17.6 - значение соответственно 00000 которые разрешают прохождение тактовых импульсов с первого входа коммутатора 17.1 на вод 24.1 блока 5 памяти. Через четыре такта входные отсчеты X , X,, Х, Х5 записаны последовательно в блок 5 памяти. В следую щие четыре такта на входах 25.1-25.6 блоков 5-10 памяти - значения 010000 соответственно. На управляющих входа коммутаторов 17.1-17.6 значения не меняются. При этом следующие четыре отсчета Х4, , Х6, Х7 записаны в блок 6 памяти. В третьей четверке татов на управляющих входах 25.1-25.6 блоков 5-10 памяти - значения 001000 соответственно.

На управляющих входахJ7.1-17.6 значения не меняются. Поэтому отсче- ты Xg,Xg, Хи, X 4 записаны в блок 7 памяти. Аналогичным образом отсчеты Х,з,Х,,},Х i$ записаны в блок 8 памяти. При этом на управляющих входах 25.1-25.6 блоков 5-10 памяти значения 000100 соответственно. На управляющих входах коммутаторов 17.1- 17.6 значения не меняются.

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

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

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

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

93006

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

с 5-10 памяти значения 10101. На управляющих входах коммутаторов 17.1- 17.6 значения 101000 соответственно, которые разрешают коммутаторам 17.1 и 17.3 передачу информации с вторых

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

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

до конца вычислений передает инфор- , мацию на выход с выхода арифметического блока 3. На всех диаграммах стрелками АЙВ условно показаны выходы

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

30 операнда), записываемый в соответствующих блоках 5-10 памяти.

Первый такт (фиг.4). На первом входе А арифметического блока 3 значение Х0, на втором - Хв. На выходе

35 блока 3 значение Y на входах весового коэффициента блока 3 установлено значение соответствующего поворачивающего множителя, которое поступает с соответствующих выходов бло-

40 ка 11 постоянной памяти.

Второй такт (фиг.5). На входах А и В арифметического блока не меняется. Значение Ґ„ записано в первый регистр д5 блока 9 памяти.

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

Четвертый такт (фиг.7). Все режимы блоков аналогичны предыдущим тактам. 5 Происходящую попутно запись информации в блоки 5 и 7 памяти в дальнейшем учитывают и для простоты на диа- граммах свободные ячейки этих блоков заполняются нулями:

В следующей четверке тактов на входах 25,1-25.6 блоков 5 и 10 памяти значение 101001 соответственно. На управляющих входах коммутаторов 17.1- 17.6 значения 101000 соответственно. Расположение операндов в этой четверке тактов показано на диаграммах (фиг.8-11).

В тактах 9-12 (фиг.12-15) информация на вход А блока 3 поступает с выхода блока 6 памяти, на вход В блока 3-е выхода блока 8 памяти. Запись информации производится в блок 5 памяти. На входах 25.1-25.6 уп- равления блоков памяти 5-10 - значени 11011. На входах управления коммутаторами 17.1-17.6 значения 010100. Расположение информации в этих тактах показано на фиг.12-15.

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

водится в блок 7 памяти. На входах 25.1-25,6 блоков 5-10 памяти значения 011100. На управляющих входах коммутаторов 17.1-17.6 значения 010100 соответственно .

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

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

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

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

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

9памяти.

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

10

кия соз

я 25 6193008

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

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

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

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

С приходом импульса переноса с выхода счетчика 13 на последней итерации на последнем выходе регистра 14 появляется нулевое значение, которое обнуляет через элемент НЕ 21 счетчик 15 итераций и переводит в режим параллельной записи регистр 14. Коммутатор 2 при этом передает информацию с первого входа. При этом происходит загрузка в блоки 5-10 памяти следующего массива.

20

0

5

5

,,..

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

1 . Устройство для вычисления быстрого преобразования Лурье, содержащее арифметический блок, шесть блоков памяти, первый блок постоянной памяти, 1 (1 где N - размер преобразования) элементов И, сдвиговый регистр, счетчик, выход 1-го, i 2,1 И) разряда которого подключен к первому входу (i-l)-ro элемента И, выход которого подключен к (i-1)- му адресному входу первого блока постоянной памяти, первый и второй выходы которого подключены к входам соответственно реальной и мнимой частей коэффициента арифметического блока, первый тактовый вход которого соединен со счетным входом счетчика и дс является тактовым входом устройства, установочным входом которого является вход обнуления счетчика, выход переноса которого подключен к тактовому входу сдвигового регистра, выход j-го (j 1,1) разряда которого подключен к второму входу j-ro элемента И, последовательный вход сдвигового регистра является входом задания логического нуля устройства, входом задания логической единицы которого является параллельный вход сдвигового регистра, о т л и ч a join e e с я тем, что, с целью упрощения устройства, оно содержит два

50

55

элемента НЕ, элемент ИЛИ, счетчик итерации, второй блок постоянной памяти, входной коммутатор, комму10

татор операндов и шесть коммутаторов, причем выходы блоков памяти с первого по шестой подключены к информационным входам соответственно с первого по шестой коммутаторы операндов, первый и второй выходы которого подключены к входам соответственно первого и второго операндов арифметического блока, выход которого является информационным выходом устройства и подключен к первому информаци- Хсд арифметического блока, вход пер- снному входу входного коммутатора, вого операнда которого образует выход которого подключен к информаци- соединенные между, собой первые входы онным входам блоков памяти с первого первых ж сумматора и вычитателя и сое- по шестой, выход первого разряда счет- диненные между собой первые входы вто чика подключен к первому информацией- 2Q рых сумматора и вычитателя, вторые

входы которых соединены между собой

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

30

35

ному входу m-го (го 1,6) коммутатора и второму тактовому входу арифметического блока, выход первого разряда сдвигового регистра подключен к пер- Вому входу элемента ИЛИ, выход которого подключен к управляющему входу входного коммутатора, второй информационный вход которого является информационным входом устройства, установочный вход которого подключен к входу первого элемента НЕ, выход которого подключен к входу- обнуления сдвигового регистра, выход (1+1)-го разряда которого подключен к второму входу элемента ИЛИ и входу второго элемента НЕ, выход которого подключен к входу управления сдвигом сдвигового регистра и входу обнуления счетчика итераций, информационный выход которого подключен к первому адресному входу второго блока постоянной памяти, m-й адресный и т-й управляющий выходы которого подключены соответственно к адресному входу m-го блока памяти и управляющему входу m-го коммутатора, выход которого подключен к входу управления запись-считыванием, m-го блока памяти, выход переноса счетчика подключен к счетному входу счетчика итераций, выходы (1-1)-го и 1-го разрядов счетчика подключены к второму адресному входу второго блока постоянной памяти, седьмой и восьмой управляющие входы которого подключены соответственно к первому и второму управляющим входам коммута40

50

55

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

Хсд арифметического блока, вход пер- вого операнда которого образует соединенные между, собой первые входы первых ж сумматора и вычитателя и сое- диненные между собой первые входы вто рых сумматора и вычитателя, вторые

тора операндов, а второй информационный вход m-го коммутатора гюдкли- чея к тактовому входу устройства.

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

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

Изобретение относится к вычислительной технике и может быть исполь-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

21

28

19

30

41

±

I

/POriJ

n

с

37

39

53

18

yi

Уп

WU2M

У г

Фиг.6

в

У1

Фиг.8

У

Фиг. 5

У,

Фиг Л

8

У1

Фиг. 9

в

М Мф

IWcb

9

9

ft

01

1

21 гпф

Ы глф

ft

fr

9

OOC619I

«6.

в

Фиг.№

Л

Фиг.18

Фиг. 20

У,

8

Фиг. Л

&

Фиг.19

Фиг.21

CPU г. 2 2