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

 

Изобретение относится к технике спектрального анализа методом дискретного преобразования Фурье (ДПФ) и может быть использовано в радиотехнике , геофизике, вычислительной технике при построении спектроанализаторов различного назначения. Цель изобретения - повышение точности вычислений . ПсГставленная цель дбстигается тем, что первый блок постоянной памяти подключен к первому блоку памядам блоков ДПФ первой группы, выходы которых подключены к входу второго блока памяти, выход которого подключен к входам блоков ДПФ второй . .группы, выходы которых подключены к входу третьего блока памяти, выход которого подключен к входу второго блока постоянной памяти. Зил, 2 табл.

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

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„.SU,» 1254505 (59 4 G 06 F 15 332

В(" : "ч q

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

Н ABTOPCHOMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3822847/24-24 (22) 07.12.84 (46) 30.08.86. Бюл. Р 32 (71) Марийский ордена Дружбы народов политехнический институт им.А.M.Ãoðüкого (72) Е.К.Лебедев, Н.А.Галанина и В.Ю.Лапий (53) 681.32(088.8) (56) Коча В.M., Ланнэ А.А. Аппаратурная реализация цифровых фильтров.

Зарубежная радиотехника, 1981, Н - 9, с. 49-67.

Маккелланд Дж., Рейдер Ч.M. Применение теории чисел в цифровой обработке сигналов. N.: Радио и связь.

1983, с. 264. (54) УСТРОЙСТВО ДЛЯ ДИСКРЕТНОГО ДВУ. МЕРНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к технике спектрального анализа методом дискретного преобразования Фурье (ДПФ) и может быть использовано в радиотехнике, геофизике, вычислитЕльной технике при построении спектроанализаторов различного назначения. Цель изобретения — повышение точности вычислений. Поставленная цель дбстигается тем, что первый блок постоянной памррти подключен к первому блоку памяти, выход которого подключен к входам блоков ДПФ первой группы, выходы которых подключены к входу второго блока памяти, выход которого подключен к входам блоков ДПФ второй .ж

С2 ,группы, выходы котОрых подключены к входу третьего блока памяти, выход которого подключен к входу еторого блока постоянной памяти. 3 ил, 2 табл.

11

k =(7 К,П Я/Я >

S=1

5 . modN

5 J

При

К = cU К + 11

1 1 2 сложности, Известно, что

U = N-1-U

2 1

1 12-1

xfn, n ) N1-1 "1И

Г (k,К )=

h =Î

,к

° M н

R R +)log Rf к,= к„,+ 3»е к

50 — 1, М

1 1?

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

Цель изобретения — увеличение точности

Алгоритм многомерного ПДПФ содерI жит две переиндексации данных для перехода от одномерного случая к многомерному и обратно, а также 11 последовальных групп одномерных N -точечных устройств ДПФ.

В соответствии с алгоритмом Гуда на первом шаге осуществляется переиндексация одновременного массива при N = N "N ... N<, если общее

1 г число отсчетов N разбито на группы

N (все N — взаимно простые)

1 ((И/N )n )

5=1 н где .> — операция вычета по

N модулю N.

В дальнейшем рассматривается двумерный ПППФ. Тогда

n=CN n +Ы и > г 1 1 г М

После переиндексации вычисляется

N N -точечных ПДПФ. Порядок очередл ности должен выбираться, исходя из минимальной временной и аппаратурной

Для первой группы из N N --точеч% ных порязрядных преобразованйй в

S-том разряде й;1

F, (k,, и, ) = В (х,(п „, п,5 — 1)

a,=о

1 1 2 л к и (2) После поразрядного суммирования

k-1

Г (k,,n) = F (k, n).

5=0

Суммирование необходимо в связи с перегруппировкой данных для осу54505 2 ществления N последующих М -точеч1 г ных ПДПФ

1 1 - 1

5 Г (к k ) = 6 f F (k,, п ) 1) Кт 1 1 т

В результате получают

10 К-1

F (k„, k ) -,« F (с, 1с,) . а=о

Переупорядочиванием выходных значений многомерного массива определяется F (К). Это достигается двумя способами:

I где U определяется из соотношений !

N N > = 1, S = 1, .

2. 1с = 11К >

9=1 где каждое из U определяется иэ группы сравнений

U 1 modN U = О modN

1 1

Разрядность чисел после каждого шага преобразования .растет. После первого преобразования, если К 16 где R. — разрядность комбинационных слоев, хранящихся в ПЗУ;

ax(— ближайшее целое, не меньше х.

После второго преобразования

На фиг. 1 представлена схема устройства для дискретного двумерно го преобразования Фурье; на фиг. 2— блок дискретного преобразования

Фурье.-N, являющийся составной частью многомерного ПППФ (для примера выбрано i = б4); на фиг. 3 — временные диаграммы работы устройства.

3 1?54505

Устройство двумерного ПДПФ содер- Устройство работает следующим жит блок 1 постоянной памяти 1, груп- образом. пы блоков дискретного преобразования Числовая R-разрядная последоваФурье 2 -?,, 3, -3, блок 4 посто- тельность х(п) поступает из шины янной памяти, блоки 5-7 памяти. данных на блок 1, работающий по алгоритму (1). Например, при N = 15;

Блоки 2 и 3 дискретного преобраN, = 3; N, = 5, в соответствии с (фиг. 2) содержат y3 bI (4) 5 + 3

8 постоянной памяти, сумматоры

9 и 10, узел 11 памяти и ана- = 0 2; n = 0,4. Тогда алгоритм прялого — цифровой преобразователь

10 мой переиндексации можно представить (АЦП) 1 2. таблицей 1.

Т а б л и ц а I и 0 5 10 3 8 13 б 11 1 9 14 4 12 2 7 п,п.О,01,02,0011,12,1021,22,2 0,313230,41,42,4

Т а блица 2

0 33 66 99 132 165 198 231 364 297

15,0 16,0 17,0 18,0 19,0 и, п10,,0 11,,0 12,0 13,0 14,0 и 330 363 396 429 462 495 528 561 594 627

n„, и 20,0

21,0 22,0 23,0 24,0 25,0 26,0 27,0 28,0 29,0 и 660 693 726 759 792 825 858 891 924 957

n„,,n 300 0,1 1,1 2 1 3,1 41 5 1 6,1 7, l 8,1

С выхода блока 1 двумерный массив записывается в блок 5 и из него считывается в блок 2 в порядке, указанном на фиг. 1, в соответствии с ал25 горитмом: на первый сверху блок

2, подается х jn =0, N,-i; n = 0); на второй — х jn =0 N -1 и = 1

1 Я и т.д. Из группы блоков 2 считываются числа в соответствии с (2). Числа

F (k„,.n ) записыаются в блок 6.

Числа из блока 6 в порядке, указан ном на схеме, считываются на вторую группу блоков 3, состоящую из N„ поразрядных блоков ДПФ íà N точек каждый. С выхода этих блоков 3 сни- З5 маются сигналы F (k„, k ), поступаю2 шие в блок 7 и из него через блок 4, преобразуясь в F(K), — в шину данных.

По шине управления подаются сигналы

2 эти сигналы управляют расположением данных. Сигналы "К " и "К " в бло / - 1 z ках 2 и 3 выбирают соответствующую и страницу для всех F (K, n ) и всех (Э g °

F(K „, К ), компоненты которых

Приведены таблицы прямого и обратного преобразования для практически интересного случая N = 1023, N„=

= 32, N = 33. Первая ступень такого спектроанализатора осуществляет

33 31-точечных ПДПФ, а вторая — 31

33-точечных ПДПФ. Для такого преобразования n = <33 n + 31 п > ! о З

Тогда прямая перестановка имеет вид, показанный в табл. 2.

) 254505

Ь

Продолжение табл. 2

31 64 96 130 163 196 229 262 ?95

10,1 11,1 12,1 13,.1 14,1 15, l 16,1 17,1 18,1

n, n 9,1

1 и 328 361 394 427 460 493 526 559 592 625

n„, п 19.,1 20,1 21,1 22,1 23,1 27,1 28,1 и 658 691 7?4 757 790 823 856 889 9?2 95" и, п 29,1 30 1

1 . и .Т.ц. и 988 1021

?9,32 30,32 п 0,32 l,32 2,32 3,32

926 959 п 992 - 35 68

Г(2,0) - Ь (33); Г(3,0) — -Г(561);

Г(4,0) — - F(66); F(5,0) — Г(594); О

F(6,0) — - Г(59);

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

Обратная перестаноька проводится по алгоритму

К = <528 К, + 496 К >

9 Р2з

Тогда Р(0,0) -F(O); Г(1,0) --Г(528)-;

Работа схемы (фиг. 2) одномерного

ПДПФ осуществляется по алгоритму

Пеледа-Лиу и представлена на временных диаграммах (фут. 3). По одиннад" цатиразрядным ПБ-входам узлов подается 6 разрядов кода частоты (команда "F- "), возбуждая во всех узлах 8 страницу Г . Затем командой Р" в ветвь 1 считываются младшие (первые) разряды чисел Х L1j, Х I ?),,; „Х (643, в ветвь 2 — вторые разряды этих чисел, в ветвь  — старшие К-тые раз-. ряды. 64- битовое слова каждой ветви разделено на 13 слов — по числу используемых корпусов узлов 8. 5-битовое слово первый разрядоз чисел

Х(11, Х(2l, ..., Х1Я подаются а

DS --входы первого узда 8, 5-битовое слово первых разрядов чисел Х(6), Х (71, ..., X L10) подается на DS-вхоI ды 2-го узла Я первой ветви. 5-битовое слово первых разрядов чисел

Х (601, Х (611, ..., Х (64 j подае гся

na DS — входя 13-го узла 8 первой ветви. Лналогично и одновременно 5-битовые слова вторых, третьих.

R-тых разрядов тех же чисел подаются па. DS-snopes» ace < узлов 8 второй, R-той ветвей. После сложения чисел от каждого узла Я в сумматорах

9 и поразрядных составляющих — в сумматоре 10 команда Г выбирает другую

К страницу узла Я и т.д.

Устройство для дискретного двумерного преобразования Фурье, содержащее первую группу из _#_ блоков

2 дискретного преобразования Фурье (И вЂ” вторая размерность преобразования), вторую группу из N, блоков дискретного преобразования Фурье

7 1 (N — первая размерность преобразо1 вания), первый и второй блоки постоянной памяти, второй и третий блоки памяти, адресные входы которых являются входами задания номеров отсчетов группы устройства, о т л и ч аю щ е е с я тем, что, с целью увеличения точности, вь:ход первого блока постоянной памяти подключен к информационному входу первого блока памяти, выход которого подключен к информационным входам блоков дискретного преобразования Фурье, первой группы, выходы которых поключены к информационному входу второго блока памяти, выход которого,подключен к информационным входам блоков дискретного преобразования Фурье второй группы, выходы которых под254505 8 ключены к информационному входу третьего блока памяти, выход которого подключен к адресному входу второ го блока постоянной памяти, выход которого является информационным выходом устройства, информационным входом которого является адресный вход первого блока постоянной памяти, входы задания коэффициента блоков р дискретного преобразования Фурье первой группы соединены между собой и являются входом задания номера первой размерности гармоники устройства, входы задания коэффициентов

15 блоков дискретного преобразования

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

1754505 Риь. z

Qgg .. «Я

Р F Г

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

Техоед И.Попович Корректор С. Черни

Редактор И. Касарда

Заказ 4723 /54 ираж 671

Подписное

БНИИПИ Государственного комитета СССР по делам изобретений и открытий

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

Проиэвс ственно-полиграФическое предприятие, г. Ужгород, ул. Проектная, 4