Процессор быстрого преобразования фурье
Патент 928362
Авторы
Классы МПК
Процессор быстрого преобразования фурье
Иллюстрации
Реферат
Союз Советсиии
Социапнстичеснии
Респубпми
ОП ИСАНИЕ
ИЗО6РЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (t ai 928362 (61) Дополнительное к авт. саид-ву (22) Заявлено 08.05.80 (2l ) 2921832/18-24 с присоединением заявки М (23) Приоритет
Опубликовано 15.05.82. Бюллетень 1Е 18
Дата опубликования описания 15.05.82 (51)М. 9(л.
Cj 06 F 15/332
Гаеударотвеииые «омитет
СССР по делам изебретеиий и открытий (53) УДК681.32 (088.8 ) (72) Авторы изобретения.
Г. g. Бахтиаров и Ю. Н. Орлов! ! (71) Заявитель (54) HPOUECCOP БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ
Изобретение относится к специализированным вычислительным устройствам цифровой обработки сигналов, испопьзующим алгоритм быстрого преобразования Фурье (БПФ) и может быть использовано в звуко- и радиолокации, в технике связи и тепеметрии, дпя анализа биологических и сейсмических сигналов и в других обпастях техники, испопьзуюших спектрапьный и корреляционный анализ, а также
"быструю" свертку.
Известно устройство БПФ каскадного типа, которое имеет в каждом каскаде цифровые линии задержки одинаковой дпины Г11.
Однако оно требует в каждом каскаде арифметический бпок, что при бопьших существенно увеличивает объем аппаратуры.
Наиболее близким по структуре и тех20 ническим характеристикам к предлагаемому явняется устройство, в котором каждый арифметический бпок состоит из входного переключателя, соединенного через
2 цифровые пинии задержки с выходным перекпючатепем и вычислителем, а выходной перекпючатепь соединен как с вычнтатепем, так и с сумматором. Кроме- того, в каждый бпок входит умножитепь, один вход которого соединен с выходом входного перекпючатепя, другой вход - с выходом блока памяти тригонометрических коэффициентов, а выход — со входами сумматора и вычитатепя (2g.
Недостатком этого устройства явпяется то, что умножитепи, входящие в состав каждого арифметического блока, явпяются спожными и бопьшими по объему устройствами, что при больших М существенно увепичивает объем каскадного процессора БПФ в цепом. цепь изобретения — сокращение объ- ема процессора БПФ каскадного типа при сохранении других качественных и количественных характеристик.
Поставленная цель достигается тем, что он содержит М/2 коммутаторов, причем выход j -го (j = 1, 3, 5 ...) ариф928362 нечетс,-ь,. (w „ "),, mod 4„, 8Й < п осД,. )
М (и п и п= <
40 Вариант 2
4 256 4 16
4 16 4 16
3 метического блока соединен с входом к- -o (к= (7+1) /2 коммутатора, выход которого подключен к входу (j + 1)-ro арифметическогого блока, выход гй -го (и 2, 4, 6 ...) арифметического блока соединен с вторым входом 3 -го (8
th)/2) умножителя, выход которого соединен с входом (гй + 1 )-го арифметического блока, причем управляющие входы
М/2 коммутаторов соединены с выходом счетчика, при этом в 1 -ом (1 1, M) арифметическом блоке второй выход входного коммутатора подключен к вторым входами сумматора и вычитателя.
На чертеже показана функциональная схема процессора быстрого преобразова йия Фурье, Устройство содержит вход 1 процессора, входной коммутатор 2, узел 3 задержки, сумматор 4, вычитатель 5 выходной коммутатор 6, коммутатор (коммутатор-инвертор) 7, умножитель 8, блок
9 памяти коэффициентов, двоичный счетчик 10, выход 11 процессора.
Устройство работает следующим образом.
На каждый очередной входной отсчет устройство выдает. выходной отсчет, при этом операции. выполняемые устройством однозначно определяются двоичным счетчиком 10, работаюшим синхронно с входными отсчетами. Все операции производятся над комплексными числами. Каждый каскад выполняет базовую операцию, О описываемую формулами
Р
Ьк=Ок OT
" =dК М 1 где К 2 .1+1
М )и-1
М
e=- Kt —, j=0, 1,2,... (2 -1), 1-0, 1,2, „. (— и -1), qÏ . ) и — номер каскада, 8 — размер преобразуемого массива.
Входной коммутатор 2 направляет от счеты со входа каскада в узел 3 задержки (будущие с ), либо на вычитатель
5 и сумматор 4 (текушие d ) и одновременно результаты Ьщ в узел 3 задержки. Выходной коммутатор G направляет на выход каскада хранящиеся в узле 3 задержки результаты Ь,и либо результаты с сумматора 4 (текущие Ьк ) и одновременно из узла 3 задержки задержанные там d на вычитатель 5 и сумматор 4.
Коммутаторы 7, стоящие после ных каскадов, выполняют операцик>
rye j =О, 1, 2, ..., (2 — 1), и- номер нечетного каскада, после которого стоит данный коммутатор.
Умножители 8, стоящие после четырех каскадов, вщполняют операцию умножения на поворачивающие множители где = 0 1 2 ... (М- 1) g=g7 и и
B < )n — двоично-инверсное значение по ï (1 — целая часть числа.
Параметры N„, 4, Р„определяются используемым алгоритмом и, напри мер, могут принимать следующие значеМ„= яи+1
Вариант 1 и
Вариант 3 (для = 4096) 2 4 6 8 10
Ми 256 1 16 1 1
Существует много других вариантов а лгори тмов.
Поворачивающие множители на умножитель 8 подаются из блока
5 9283
Значение индекса 1 во всех формупах определяется значением с двоичного счетчика 10 (мпадшими разрядами этого счетчика, еспи максимапьное значение 1 меньше М ).
B остальном работа процессора анапогична известному. B частности, при выпопнении прямого БПФ и естественном порядке спедоваиия.входных данных выходные отсчеты будут спедовать в двоично- iÎ инверсном порядке. Длина узлов задержки при этом составпяет М/2, К/4, и т.д., начиная с 1-го каскада.
Экономия аппаратуры предлагаемого процессора достигается за счет сокраше- iS
1 ния количества. умножителей. Скорость работы процессора будет опредепяться при этом скоростью работы одного каскада, а качество работы — числом двоичных разрядов в представпении входных данных щ и тригонометрических коэффициентов, как это имеет место в известном процессоре.
Форму па изобретения д
Процессор быстрого преобразования
Фурье, содержаший М арифметических бпоков, счетчик, блок памяти, коэффициентов и М/2 умножитепей, причем выход
1-ro арифметического блока, кроме последнего, соединен с входом (i + 1)-ro арифметического бпока, а выход поспеднего арифметического блока является выходом процессора, вход 1 -го арифмети- 35 ческого блока, кроме первого, соединен с выходом (1 — 1 )-ro арифметического блока, а вход первого арифметического блока является входом процессора, выход счетчика соединен с входом бпока памяти 40 коэффициентов, выход которого соединен с первыми входами умножитепей, причем
1-й (1 — 1, N) арифметический бпок со62
Ф.
6 держит входной коммутатор, выходной коммутатор, узпы задержки, сумматор и вычитатеп1, выход которого подкпючен к первому входу входного коммутатора, первый выход которого соединен с входом узла задержки, выход которого подкпючен к первому входу выходного коммутатора, первый выход которого соединен с первым входом. вычитатепя и первым входом сумматора, выход которого соединен с вторым входом выходного коммутатора, второй выход которого является выходом арифметического блока, а второй вход входного коммутатора является входом арифметического бпока, причем управпяюшие входы входного и выходного коммутаторов соединены с выходом счетчика, отличаюшийся тем,что,сцепью сокрашения объема оборудования, он содержит М/2 коммутаторов, причем выход j -го (j — 1, 3, 5, ...) арифметического бпока соединен с входом М -го (g -(j + 1)/2) коммутатора, выход которого подкпючен к входу (j + f )-го арифметического блока, выход п -го (in= 2, 4, 6, ...) арифметического блока соедиО нен с вторым входом 0 -го (0 =тп./2) умножитепя, выход которого соединен с входом (in+ 1)-го арифметического бпо ка, причем управляющие входы N/2 коммутаторов соединены с выходом счетчика, при этом в 1 -м (1 — 1,M) арифметическом блоке второй выход входного коммутатора подкпючен к вторым входам сумматора и вычитатепя.
Источники информации, принятые во внимание при экспертизе
1. Патент США М 3746848, кл. Cg 06 F 15/32, опублик. 1973.
l Н.1.Gt о(1nckl., G.A.%Or ks. А. руре Ипе
PaS< Four ice ТгЫ5 Еа гтрк .? (Тгс п
1970, Ч. С-19, No. 11, р.р. 1015-1019 (прототип ),