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

1

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

Целью изобретения является новы- шенио быстродействия устройства.

На фиг.1 представлен алгоритм быстрого преобразования Фурье (вПФу; ,па фиг.2 - функциональная схема устройства: на фиг.З -- функциональная схема арифметического б лока; на фиг.4 - схема блока элементов И; на фиг.5 - схема блока реверсивных счетчиков; на фиг.6 - схема блока элементов ИЛИ: на фиг.7 - схема блока с 1 етчпков; на фиг.8 - схема блока управления; на фиг.9 - схема первого дешифратора; на фиг.10 - схема второго дешифратора.

Устройство для реализации БПФ (фиг.2) содержит блок 1 (оператив- Hoi i) памяти, арифметически блок 2, блок 3 постоянной памяти, блок 4 элементов П, блок 5 реверсивных счетч1Н ов, блок 6 элементов 1-Ш11, блок 7 счетчиков, блок 8 управления, первый дешифратор 9, второй де- 1: пфратор 10, информационный вход 11 устройства, вход 12 запуска устройства, вход 13 задания числа итераций устройства, счетиьй вход 14.

1242985.2

является пятым входом арифметического блока 2, на него поступает сигнал управления при вычислении второй диагонали. Выход : 36 - 39 являются . 5 выходами арифметического блока 2,

причем выход 36 является выходом действительной части комплексного числа первого операнда, выход 37 - мнимой частью комплексного числа первого опе- 0 ранда, выход 38 - действительной

частью комплексного числа второго операнда, выход 39 - мнимой частью комп- лексно1 о И1сла второго операнда.

15

20

25

30

Блок 4 элементов И (фиг.4) содержит первые элементы И-НЕ 40, вторые элементы И-НЕ 41 и элементы НЕ 42. Вход 43 является первым входом блока 4, вход 44 - вторым входом блока 4, а выход 45 - выходом блока 4. Блок 5 реверсивных счетчиков (фиг.5) содержит счетчик 46, вход 47 является первым входом блока 5, вход 48 -- вторым входом блока 5, вход 49 - третыи-1 входом блока 5, вход 5.0 - четвертым входом блока 5, а выход. 51 - выходом блока 5.

Блок 6 элементов lUEi-IlE (фиг.6) содержит элементы Ш1И-НЕ 52 и эле- t-ieirru lUIi-I 53. Вход 54 является первым входом блока 6, вход 55 - вторым входом блока 6, вход 56 - третьим входом блока 6, а выход 57 - выходом блока 6.

Лрифметпческгш блок 2 (фиг.З) со- л,с-р,к 1т преобразователь 15 кода, пер- jjbU мультиплексор 16, второй мультиплексор 17, сумматоры 1.8 - 20, вы- чптатели 21 - 23, умножители 24 - 27.

Входа 28 - 31 являются иервьми входами арифметического блока 2, причем на вход 28 поступает действительная часть комплексного числа первого операнда, на вход 29 - мнш«/ая часть кошшексного числа первого операнда, па вход 30 действительная часть ког-цшекспого числа второго операнда, на вход 31 - мнимая часть комгшексного числа второго операнда. . Вход 32 является .вторым входом арифметического блока 2, на который поступает действительная часть комплексного весового коэффициента. Вход 33 является третьим входом арифметического блока 2, па который подается мнимая часть комплексного весового коэ41фи- циента. Вход ЗА является четвертым входом арифметического блока 2, на Hei o поступает сигнал управления при вычислепии первой диагонали. Вход 35

5

0

5

0

5

Блок 4 элементов И (фиг.4) содержит первые элементы И-НЕ 40, вторые элементы И-НЕ 41 и элементы НЕ 42. Вход 43 является первым входом блока 4, вход 44 - вторым входом блока 4, а выход 45 - выходом блока 4. Блок 5 реверсивных счетчиков (фиг.5) содержит счетчик 46, вход 47 является первым входом блока 5, вход 48 -- вторым входом блока 5, вход 49 - третыи-1 входом блока 5, вход 5.0 - четвертым входом блока 5, а выход. 51 - выходом блока 5.

Блок 6 элементов lUEi-IlE (фиг.6) содержит элементы Ш1И-НЕ 52 и эле- t-ieirru lUIi-I 53. Вход 54 является первым входом блока 6, вход 55 - вторым входом блока 6, вход 56 - третьим входом блока 6, а выход 57 - выходом блока 6.

Блок 7 счетчиков (фиг.7) содержит счетчик 58, вход 59 является первым входом блока 7, вход 60 - вторым входом блока 7, вход 6 - третьим входом блока 7, а выход 62 - выходом блока 7. Блок 8 управления (фиг.8) содержит счетчики 63-67, элементы И-НЕ 68-71, элементы НЕ 72-76, одновибра- торы 78-80. Вход 81 является первьп 1 входом блока В, вход 82 - вторым входом бло ка 8, вход 83 - третьим вхо- дом блока 8, вход 84 - четвертым входом блока 8, вход 85 - пятым входом блока 8, вход 86 - шестым входом блока 8, а выход 87 - первым выходом блока 8, выход 88 - вторым выходом блока 8, выход 89 - третьим выходом блока 8, выход 90 четвертым выходом 8, выход 91 - njiTbiM выходом блока 8, выход 92 - шестым выходом блока 8.

Первый дешифратор 9 (фиг.9) содержит дешифратор 93, элементы НЕ 94. Вход -95 является входом первого дешифратора 9, а выход 96 - первым

40

50

55

25

выходом, и выход 97 - вторым выходом nqpBoro дешифратора 9.

Второй дешифратор 10 (фиг.10) содержит дешифратор 98, элементы НЕ 99, элемент И-Е1Е 100. Вход 10 является входом второго дешифратора 10, а выход Г02 - первым выходом, выход 103 - вторым выходом , выход 10А - третьим выходом, выход 105 - четвертым выходом второго дешифратора 10.

Быстрое преобразование Фурье осуществляется по алгоритму Кули-Тыоки (фиг.1), в котором входные отсчеты сигнала расположены в обычном порядке, а выходные спектральные состав- ляющие расположены в двоично-инверсном порядке. Вычисление базовой операции выполняется с замещением данных в оперативной памяти.

Последовательность вычисления базовых операций в алгоритме Кули-Тью- ки определяется за счет группирования базовых операций, соответствую- 1ЦИХ двум точкам БПФ, четырем точкам БПФ, восьми точкам БПФ и т.д. Расположение этой последовательности базовых операций в алгоритме Кули Тьюки (фиг.1 ) имеет вид диагонали, проходящей из части алгоритма на начальных итерациях в верхнюю часть к последней итерации. На основании тдкого наглядного сравнения введем понятие диагональ, которая будет состоять из базовых операций, имеющих одинаковое число окружностей (фнг.1). Диагональ имеет свой номер, который соответствует числу окружностей в базовой операции, входящей Б данную диагональ. Число диагоналей в алгоритме БПФ равно числу „ г итерац1-ш. Минимальный номер диагонали равен единице, максимальный номер диаг онали равен п .

Начало вычислений для каждой диагонали расположено в алгоритме БПФ в 5 завпсг мости от номера диагонали и со- ответствует: для Первой диагонали вычисления начинаются на первой итерации, для второй диагонали - на второй итерации, для третьей диагонали - на 50 третьей итерации, и т.д.

Окончание вычислений для всех диагоналей расположено в алгоритме БПФ на последней П итерации.

.Вычисление БПФ по алгоритму 55 (фиг.1) осуществляется путем вычисления диагонали с последовательным увеличением номера диагонали, на30

35

5

10

{5

0

0.

чиная от единицы и кончая номером диагонали t .

Кроме введенного понятия - диагональ, и известного понятия базовая операция определиь еще понятие базового блока в алгоритме БПФ (фиг.1) . как группу базовых операций на итерации, имеющую одинаковые весовые коэффициенты. Базовый блок может состоять из одной, двух, четырех и т.д. - до N/2 базовых операций. На первой итерации в базовый блок входит N/2 базовых операций; на второй итерации,.- N/4 базовых операций и т.д., и на последней л итерации в базовый блок входит одна базовая операция.

Для первой и второй диагоналей в алгоритме БПФ (фиг.1) на каждой итерации расположен один базовый блок. Для третьей, четвертой, пятой и т.д. - до (д диагонали в алгоритме БПФ на каждой итерации расположено, соответствегчо, два, четыре, ;восемь и т.д. - до N/4,базовых блоков.

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

Рассмотрим работу устройства (фиг.2) на примере вычисления шестнадцатиточечного БПФ.

Вычисление шестнадцатиточечного БПФ состоит из вычисления четырех диагоналей. В первой диагонали на

каждо итерации имеется один базовый блок, в KOTOpbu-i .lia первой итерации входит восемь базовых операций, VU4 второй итерации - четыре базовых операций, па третьей ,- две, и па четвертой - одна. В первой диагопали переход с одной итерации па другую j пе требует смещения зпачепия адреса nepBoi o операнда, поэтому в блоке 5 при вычислении первой диагопали пе производится загрузки начального адреса.

Вторая диагональ также состоит из одного базового блока па ,итера- uiui, по при переходе в вычи/глениях с итерации па итерацию происходит слйщение адреса. Поэтому в блоке 5 при переходе к следующей .итерации осуществляется загрузка начального адреса. На третьей и четвертой диа- I OiajLSX находятся, соответствелню, два и четыре базовых блока. Поэтому после вычисления базового блока .1 при переходе к вычислениям на сле- ;i,yKuu,eii итерац1П1 для третье} и чет- . партой диагоналей происходит смещение адреса, следовательно, в этих случаях необходимо вшюлнить начальную загрузку адреса в блоке 5.

Загрузка адреса в блок 5 выпол- 1ыется по сигналу, поступающему на вход с второго выхода блока 8 управления. Начальное значение адреса поступает на вход блока 5 с выхода блока.4. При начале вычисления каждой диагонали импульсом, поступающим па ззход блока 5 с шестого выхода блока 8 управления, происходит установка в нуль адреса первого операнда. Текущее значение адреса первого опе- рапда при вычислении базовых опера- впутри базового блока определяется путем добавлепия единицы к зна- ,чению адреса при поступлении каждого тактового импульса па вход блока 5 .

Число базовых операцш с первого выхода первого дещифратора 9 поступает па входы блока 4 и блока 6. Значение адреса первого операнда с ,; выхода блока 5 поступает на входы блока 4. На выходе блока 4 по сигналам, поступающим на его вход, формируется начальное значение ад- роса первого операнда. В блоке 6 по сигналам, .поступающим на его входы, вычисляется значение адреса второго операнда, Под воздействием сигнала,

поступающего на вход блока 6, па его выход поступает либо значение адреса первого операнда с входа, либо полученное в блоке 6 значение адреса второго операнда.

С выхода второго дещифратора 10 на вход блока 7 поступает начальное значение адреса коэффициентов. По сигналу с третьего 8 управления, поступающему на вход блока 7, выполпяется предварительная запись в блоке 7 начального значения адреса коэффициентов.

На вход блока 7 адреса коэффици- 5 . е.нтов с пятого выхода блока 8 управления поступает сигнал, который задает в блоке 7 текущее значение адреса )фицие 11тов.

Перед началом работы устройства 0 необходимо на вход 13 блока 8 управления подать сигнал числа итераций, для рассматриваемого примера этот сигнал равен двоичному коду числа четыре. Начало работы устройства 5 деляется нриходом импульса Пуск па первый вход 12 блока 8 управления после этого тактовые импульсы, ступающие на третий вход 14 блока 8 управления и вход блока 5, обеспечивают последовательную передачу сигналов между блоками.

| С пер)зого выхода блока 8 управле- 1ПИЯ на вход первого дешифратора 9 подается код помера итерации, по которому определяется число базовых операций в базовом блоке. С четвертого выходгг блока 8 управления на вход второго дешифратора 10 подается код номера диагонали, но которому определяется число базовых блоков и начальное значение адреса коэффициентов.

На четвертый вход блока 8 управле- пия поступает .сигнал управления при вычислеьши первой диагонали. 1а пятый вход блока 8 управления с выхода первого дешифратора 9 поступает сигнал числа базовых операций. По шестому входу в блок 8 управления с выхода второго дешифратора 10 поступает сиг- пал числа базовых блоков. ,

На вход 11 устройства поступают выборки сигнала в обычном порядке, которые занисываются в блоке I опера- памяти. В блоке 3 постояшюй памяти записахш комплексные значения коэ(15фнциентов, расположенные в дво- ично-инверсном порядке следования своих номеров.

0

0

5

0

5

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

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

Арифметический блок 2 (фиг.З) ра- ботает таким образом, что вычисления базовых операций па первой ;г второй

диагоналях состоят в выполнении сум мы и разности на сумматорах 18 и 19 и вычнтателях 21 и 22 между действителышми и мнимыми частями комплексных значений первого и второго операнда. При вычислении оставшихся диа гоналей кроме первой и второй, что соответствует отсутствию сигналов управления, поступающих на входы ЗА и 35, вычисления базовой операции выполняются с подключенными умножи- гелями 24 - 27, сумматором 20 и вы- читателем 23 с дальнейшим выполнением операции суммы и разности на сумматорах 18 и 19 и вычитателях 21 и 22.

На фиг. 4-10 показаны примеры практической реализации блоков вновь внедренных в устройство для реализации БПФ. Максимальное число итераций которое может быть иснэльзовано в при-- веденных нримерах, равно семи.

На фнг.4 показан пример практической реализации блока 4. Последний является комбинационной схемой, по вхо .ду 43 поступает число базовых опера- ций, которое совместно со значением текущего адреса первого операнда, поступающего по входу 44, на элемек

5 О

0

0

5

тах 2И-НЕ 40 и 4 и злементе НЕ 42 вычисляет начальное значение адреса первого операнда при переходе к вычислениям следующег о базового блока на выполняемой итерации.

На фиг.5 показан пример практической реализации блока 5. Последний выполнен на двоичном счетчике 46, по первому входу 47 поступает импульс записи информации с входа 49 в счетчик 46, по входу 48 поступает импульс сброса в нуль счетчика 46, по входу 50 поступают счетные импульсы. Двоич- лй код адреса первого операнда с выходов счетчика 46 поступает на вход вход 51..

На фиг.6 показан пример практической реализации блока 6 второго операнда. Блок 6 представляет собой комбинационную схему на элементах 2ИЛИ-НЕ 52 и элементах 2 ИЛИ 53. При отсутствии на третьем входе 56 логической едини:;ы адрес первого операнда с входа 55 поступает на выход 57. Вычисление адреса второго операнда происходит при поступлении на вход 56 логического пуля, тогда по соответствующему разряду с входа 54 к адресу первого операнда по схеме КПП добавляется единица, в результате чего па выходе 57 формируется значение адреса второго операнда.

На фиг.7 показан пример практичес- ;кой реализации блока 7. Последний выполнен на двоичном счетчике 58, по входу 59 поступает импульс записи информации с входа 61 в счетчик 58, по входу 60 поступают счетные импульсы. Двоичный код адреса коэффициентов с выходов счетчика 58 поступает на выход 62.

На фиг.8 показан пример практической реализации блока управления, который состоит из счетчиков 63 - 67; элементов И-НЕ 68 - 71, элементов НЕ 12 - Id, элемента И 77, одновибрато- ров 78-80. На первый вход 81 поступает с ггнал логической 1 определяющий пуск устройства для реализации БПФ.На второй вход 82 поступает код числа итераций. На вход 83 поступают тактовые импульсы, кaждьri приходящий тактовый импульс определяет одну выполненную базовую операцию БПФ. По четвертому входу 84 на элемент 2И-НЕ 71 поступает сигнал управления о вычислении первой диагонали. По пятому входу 85 на счетчик 63 поступает код

912

числа базовых операций, которые необходимо выполнить в-базовом блоке БПФ По шестому входу 86 на счетчик 64 поступает код числа базовых блоков, которые необходимо выполнить на итер цпи.

С выхода счетчика 65 код номера итерации поступает на первыГ выход Р)7. С выхода элемента И-НЕ 71 им- иульс окончания вычисления всех ба-

зовых онераций в базовом блоке БПФ для дисггоналей с номерйми не менее второй поступает на второй выход 88. С выхода элемента ПЕ 73 импульс начала вычисления на итерации ноступа- ет на третий выход 89, С выхода счетчика 67 код номера диаго11а1П1 поступает па четвертый выход 90. С выхода нервого одновибратора 78 импульс окончания вычисления всех ба- зов1.Х операций в базового блоке БПФ поступает па пятый выход 91. С выхода элемента 2И-ПЕ 70 импульс начала Еычмсле П1я диагонали поступает па uiecToii выход. 92.

Одповнбраторы 78-80 обеснечит ают сч етпые импульсы в моменты обпулеппя счегчикон 63-65. Логичес сие элемепты 60-77 формируют импульсы записи П1- ({юрмации в счетчики 63--67, Выход элемента И 77 обеспечивает продолжепие БПФ для следующего массива входных ( отсчетов случайио1 о входного сигнала .

На фиг. 9 показап прпмер практической реализац1П1 первого дешифратора, состоящего из дешифратора 93 три линии на восемь и элементов ПЕ 94. Па вход 95 поступает код номера ите- рацип, па первом выходе 96 получаетс 1П1верспый -код числа базовых операцнй в бг зовом блоке БПФ, а после элемеп- тов ЫЕ 94 па второй выход 97 поступает прямой код.числа базовых опера- дни в базовом блоке БПФ.

Па фиг.10 показап пример практической реализации второго дешифрато-- .ра, состоящего из дешифратора 98 три линии на восемь, элементов ПЕ 99 и элемента 2И-НЕ 100. Па вход 101 поступает код помера диагонали, на r.epBbiii выход 102 поступает сигнал управления при вычпслепии nepBoii диа- ronajHi, на третий выход 104 посту- пает сигнал управления при 1зычнсле-- П1П1 второй диагонали. Па второй выход 103 и четвертый выход 105 поступает

10

базовых блоков на

зобретен и я

Устройство для реализации быстрого преобразования Фурье, содерлсащее блок памяти, первый ипформационный выход которого подключен к входу опе- рапдов арифметического блока, входы реальной и мнимой частей коэффициента которого подключены соответственно к первому и второму выходам блока постоянной памяти, а выход результата арифметического блока подключен к нервому ипформацпонному входу блока памяти, второй ипформационный вход которого является информационным входом устройства, блок управления, отличающее- с я тем, что, с целью повынгения . быстродействия, в него введены блок элементов ГЦ блок элемептов , блок реверсивных-счетчиков, блок счетчиков, первый и второй дешифраторы, причем второй выход блока памяти 11одключен к первому вхоДу блока элементов 1ШИ, выход которого подключен к адресному входу блока памяти, первый выход первого дешифратора под- ключеп i: второму входу блока элементов 1 1ЛИ и первому входу блока элементов lij выход которого нодключен к информационному входу блока реверсивных счетчиков, информационный выход кототорого подключен к третьему входу блока элементов ИЛИ и второму входу блока элементов И, адресный вход постоянной памяти подключен ft ннформац1юнному выходу блока счетчиков, информационный вход которого нодключен к первому выходу второго дешифратора, второй и третий выходы которого под.ключепы соответственно к пер- вому и второму входам кода помера базовой операции арифметического блока, при этом блок управлепия: содержит семь счетчиков,.три одновибратора,. четыре элемента И-ПЕ, пять элементов НЕ и элемент И, выход которого подключеп к первым входам первого, второго и третьего элементов И-НЕ., счетному входу первого счетчика и выходу первого элемента НЕ, выход которого подюночен к установочному входу второго счетчнка, вход суммирования которого соединен с входом вычитания первого счетчика н подключен к

11

12 ковыходу первого одновибратора, вход торого соединен с вторыми входами первого, второго и третьего злементоп И-НЕ и подключен к выходу nepeiioca третьего счетчика, вход вычитания которого .подключен к выходу второго однойибраторсЭ, вход которого соединен с третыши входами первого и элементов II-HE и подключен к переноса четвертого счетчика вычитания которого подключен переноса пятого счетчика, вход, вычитания которого подключен к выходу третьего одновибратора, вход которого соединен с четвертым входом первого элемента П-ИЕ, входом второго элемент к выходу переноса шес вход вычитания которовыходу переноса седь- счетный вход которого

с счетным входом шестого и подключен к выходу

второго выходу

вход ; к выходу

НЕ и подключен того счетчиксТ,

го подключен к мох о счетчика, соединен счетчика

третьего элемента НЕ, вход которого подключен к выходу первого элемрлгга И-ПЕ, выход второго элемента И-ПЕ подключен к входу четвертого элемента НЕ, выход которого гсодгОшчен к счетным входам четвертого и пятого счетчиков, выход третьего элемента И-НЕ подключен к входу пятого элемента НЕ, выход которого подключен к счетному входу третье1 о счетчика, инфор- .мациошшй вход которого подключен к информационному выходу первого счет ХЮ)

242985 опн о 15 та с-

to у

20

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

т

Ш)

r

ТГ17J f

39

фиг. г

фиг.

фиг. 5

. vt

иг

Si.

-as or

. да

-/

--/

6

CQ-

}

аг

. м

-ss

.w

(16

//(

Sa

57

фиг S

61

2

J

59

60

1риг6

бг

58

1 г

4 8

J 4

/5Q-

58

/ 2 4 8

/50- Ф-

-CZl S3

-

фиг.7

ss

97

S4 l

IL

Lrфиг. го

Изобретение относится к вычислительной технике и может быть использовано дня цифровой обработки сигналов, спектрального анализа различных случайных нроцессов. Цель изобретения - повышение быстродействия устройства. Устройство для реа;лизации быстрого преобразования Фурье (БПФ) содержит блок памяти, арифметический блок, блок постоянной памяти, блок управления, а для достижения цели в него введены блоки элементов И и ИЛИ, блокн счетчи-- ков и реверсивных счетчиков, два дешифратора, соединенные соответствующим образом. Быстрое преобразование Фурье осуществляется по алгоритму Кули-Тьюки, в котором входные отсче-: ты сигналов расположены в обычном порядке, а выходные спектральные составляющие расположены в двоично-инверсном порядке. Вычисление базовой операции выполняется с замещением данных в оперативной памяти. Последо- вательнасть вычисления базовых операций в алгоритме Кули-Тьюки определяется за счет группирования базовых операций, соответствующих двум, четырем, восьми точкам БПФ и т.д. 10 ил. (Л