книги / Цифровые устройства селекции движущихся целей
..pdfПриведенные расчеты показывают, что число доплеровских фильтров для построения фильтровой системы СДЦ достаточно велико, и аналоговая реализация фильтров требует значительных аппаратных затрат. Поэтому в качестве фильтровой системы спектрального анализа будем рассматривать ее цифровую реализацию с использованием алго ритма быстрого преобразования Фурье (БПФ).
2.2. Использование алгоритмов дискретного преобразования Фурье в задачах оптимальной частотной фильтрации
Оптимальный обнаружитель должен формировать логарифм отношения правдоподобия и сравнивать его с порогом обнаружения. Если в качест ве модели шума принять нормальный белый шум, То оптимальный об наружитель реализует алгоритм оптимальной частотной фильтрации [7]. В р е зн ы х , усдовия^,,наблюдения скоррсть цели, как прцвцло, неиз вестна и, следовательно, неизвестно и доплеровское смещение частоты
отракённЬго |
ейгйала. Диапазон возможных доплеровских |
частот |
Уд min - Уд mux |
определяется диапазоном скоростей Kmin... К1Пах |
ЭТО' об |
стоятельство приводит к тому, что устройство оптимальной фильтрации становится многоканальным по частоте.
Таким образом, задача обнаружения сигналов сводится к синтезу набора фильтров, перекрывающих возможный диапазон доплеровских частот и отстоящих друг от друга на равные частотные интервалы. На бор таких фильтров, реализованный в цифровой форме, вычисляет дис кретное преобразование Фурье (ДПФ) входного сигнала и может быть осуществлен одним из следующих методов: корреляционным, фильтро вым и алгоритмическим.
Алгоритм ДПФ эквивалентен фильтрации входного сигнала с по мощью набора фильтров. Амплитудно-частотная характеристика одного фильтра пропорциональна функции sincx, а полоса пропускания
(2.1)
где N - объем выборки (число импульсов в пачке); Тп - период повто
рения импульсов.
Ширина спектра сигнала, отраженного от цели, обратно пропор циональна времени облучения, что составляет
1
( 2. 2)
NT„'
а форма спектра сигнала определяется формой диаграммы направленно сти антенны, которая в большинстве случаев хорошо аппроксимируется
функцией sine*. Следовательно, набор цифровых фильтров, вычис ляющих дискретный спектр, реализует алгоритм оптимальной частот ной фильтрации, поскольку в этом случае достигается оптимальное со гласование как по форме спектра сигнала, так и по его ширине. В слу чае, когда форма спектра отраженного сигнала пропорциональна какойлибо другой функции, введением предварительной весовой обработки при нимаемого сигнала добиваются согласования по форме спектра сигнала.
Сигнал на выходе приемника представим в виде
U(0 = Лсо8[27Г(/пр + Уд)/ + %] + (О, |
(23) |
где А - амплитуда сигнала; / прпромежуточная частота; / д -
доплеровское смещение частоты; <р0неизвестная начальная фаза;
{/,„(/) - шумовое напряжение.
Шумовое напряжение можно представить следующим образом:
и ш(/) = Л,(0соз(2я/П + <рш(/)), |
(2.4) |
где Лш(/) и <рш(/) - случайные, медленно меняющиеся функции.
Сигналы на выходе фазового детектора можно выразить соотноше ниями:
Uc(t) = A(l)cos(2njat + %)■
и ш0) = AjOcos срш(1).
После аналого-цифрового преобразования имеем:
Uc[n] = A(t)cos(2KfanT + <р0 );
UUiM = Au(t)COS(pui(t)i
где п - текущий номер принимаемого импульса; п = О N -1. Алгоритм вычисления дискретного спектра Имеет вид [3]
1 "У |
/ |
|
|
А'(А-) = — ^-vOOcxpl -j |
¥ " * } |
<2,) |
|
" п=0 |
\ |
||
где к - текущий |
номер |
гармоники спектра; |
к = О N -1 ; х[п] *= |
=УЛп]+ УшМ ~ массив входных данных.
Сучетом (2.7) гармонику доплеровского спектра можно предста вить как
Х(к) =— \x ( n ) c o s — nk - j — У |
х{п)sin — Пк. |
(2.8) |
|
N to |
N |
N |
|
С учетом (2.8) прямое вычисление дискретного спектра по алгй-
32
ритму (2.7) приводит к корреляционно-фильтровой схеме (рис.2.2), ко торая состоит из набора N фильтров, перекрывающих возможный диа пазон доплеровских частот. Каждый фильтр состоит из двух квадратур ных каналов для вычисления действительной и мнимой частей спектра, которые после возведения в квадрат суммируются в выходных сумма торах фильтров. Такое построение блока ДПФ (2.8) предполагает нали чие блока памяти для хранения весовых коэффициентов:
kci =cos(2;rF-.nT)\ |
( 2.9) |
|
и |
' |
|
ksi =sm(2KFinT)) |
|
|
где F |
j частота настройки / -го фильтра; |
п = О N -1 - текущий номер |
импульса. |
|
Рис. 2.2
При практической реализации алгоритмов ДПФ, в случае большо го объема обрабатываемых данных предпочтительнее использовать ал горитмический метод вычисления спектра. В этом случае применяются алгоритмы БПФ как наиболее оптимальные с точки зрения вычисли тельных затрат. Рассмотрим возможные реализации алгоритмов БПФ.
2.3.Реализация алгоритмов быстрого преобразования Фурье
2.3.1.Реализация алгоритмов БЦФ по основанию 2. Дз анализа фор мулы (2.7) видно, что в случае; когда последовательность jt(/i) является
действительной, при прямом вычислении дискретного спектра нужно
33
выполнить |
(N - 1)2 умножений комплексного числа на действительное |
и N ( N - 1) |
комплексных сложений. Следовательно, при больших N |
прямое вычисление дискретного спектра по алгоритму (2.7) требует большого количества вычислительных операций, что не всегда прием лемо на практике. Основная идея БПФ состоит в том, чтобы исходную TV-точечную последовательность разбить на две N /2 -точечные после довательности, из дискретных преобразований Фурье которых путем взвешенного алгебраического сложения можно получить ДПФ ис ходной последовательности. Такой подход приводит к алгоритмам БПФ с прореживанием по времени.
Рассмотрим |
входную N -точечную последовательность х(п) , |
||
считая, что N |
равно |
степени 2. |
введем. t ДЗР .N А2 -точечные |
последовательности *,(«,) |
и х2(п2) из четных и нечетных членов/jr(/i)>r |
||
x](nl) =x(2n),.ntlp2ny я = 0,N/2-I; |
^ 1( |
JC2(/22) = *(2л + 1), п2 =2rt + l, /i-0,yV /2 -l.
Тогда ДПФ исходной последовательности можно запйсатЪ в Виде
ЛМ |
ЛМ |
|
|
Х(к) = £ * ( « ) < |
+ '£ х(п)Щ к, |
(2.11) |
|
/1=0 |
ii=0 |
||
|
|||
п четные |
п нечетные |
|
. 2/г |
пк] - поворачивающий множитель. |
|
где Wtf =ехр[-у— |
||
N |
|
|
Соотношение (2.11) с учетом (2.10) можно преобразовать к виду |
||
N / 2 - 1 |
N / 2 - 1 |
|
Х(к) = £ х(2п)\У%,к+ £ |
x(2n +l)tVtfn+nk ^ |
|
/1=0 |
/»=о |
^2 j2) |
N / 2 - 1 |
N ! 2 - 1 |
|
= x |
£ x2(n2w ”kn . |
|
/1=0 |
/1=0 |
|
При выводе (2.12) использовалось равенство W^j =WNJ1.
Таким образом, имеем окончательный результат
X{k) =X,{k) + WkX 2{k\ |
(2.13) |
|
где Х {(к) Х^(к) |
N /2 -точечные дискретные преобразования Фурье |
|
последовательностей |
*,(л,); и x2(h2) i |
1 |
Формула (2.13) определена для 0< |
к < N '/2 ^ 1. Аналогичное вы |
ражение при к > N 12, можно,получить, учитывая/свойство периодично сти ДПФ [4];
34
X(k) = X l(k -N /2 )+ W ^X 2(k - N /2 ) . |
(2.14) |
Пара преобразований (2.12) и (2.13) определяет алгоритм быстрого преобразования Фурье по основанию два с прореживанием по времени.
Последовательности JC|(/1,) |
и х2{п2) можно разбить на последователь- |
||
■ |
к |
. |
• |
ности *,(/*,) и х, (л,), |
х2(щ)\\ х2(п2). Каждая пара содержит четные и |
||
нечетные члены |
*,(л,) |
и |
х2(п2). Далее по алгоритмам (2.12) и (2.13) |
определяются Х {(к) и Х 2(к) . Эту процедуру можно повторять до тех пор,
пока разбиваемые последователь ности не будут содержать два чле на. Согласно (2.7), ДПФ 2-точеч- ных последовательностей опреде ляется как
х ( 0 ) = х ( 0 ) + т |
(215) |
|
Х(\) =х(0)-х(\). |
1 |
' |
Алгоритм (2.15) |
называется |
базовой операцией БПФ, графи ческое изображение которой по казано на рис.2.3.
На рис.2.4 в качестве при мера представлен направленный граф 8-точечного (БПФ) по ос нованию 2 с прореживанием по времени.
Анализ направленного гра фа БПФ показывает, что особенностью алгоритма является двоично
инверсная перестановка номеров элементов входного массива данных. Это обстоятельство можно пояснить следующим примером. Рассмотрим
8-точечный массив входных данных х(п), п = 0,7
Прямой порядок номеров элементов в десятичном коде будет сле дующий:
0,1,2,3,4,5,6,7. |
(2.16) |
Записывая ряд (2.16) в двоичном коде, а затем инвертируя порядок следования двоичных разрядов каждого номера, получаем:
000,100,010,110,001,101,011,111.
Если числа такого ряда записать в десятичном коде, то получим двоично-инверсную перестановку номеров входных элементов:
35
0,4,2,6,1,5,3,7.
Анализ графа на рис.2.4 и процедура последовательного сокраще ния вдвое размеров преобразований показывает, что на каждом этапе БПФ необходимо выполнить N / 2 -умножений действительного числа на комплексное. Поскольку число этапов БПФ равно
M2 = log2yV |
(2.17) |
то число умножений алгоритма БПФ по основанию 2 определяется как
My= y lo g 2/V. |
(2.18) |
Формула (2.18) позволяет оценить выигрыш в количестве операций ум ножения при вычислении дискретного спектра методом БПФ. При этом объем вычислений сокращается приблизительно на два порядка, что позволяет выполнять обработку сигналов в реальном времени.
В случае использования алгоритма БПФ с прореживанием по час тоте входная N -точечная последовательность х(п) разбивается на две
равные последовательности следующим образом:
*|(Л|) = *(л). « 1 =п, n =0 ,N /2 - \, |
|
|||
х2(п2) =х(п + JV/2), п2 =пу л = 0,7V/2 —1. |
|
|||
Тогда ДПФ исходной последовательности определяется |
|
|||
|
N 1 2 - 1 |
|
N - \ |
|
Х(к)= |
£ |
x (n w * + |
X х( " Ж к = |
|
|
/i= 0 |
|
n = N / 2 |
|
N 1 2 - 1 |
|
N 1 2 - 1 |
|
|
= |
x(nW tf+ £ |
x{n + N/2Wh"*Nn)k |
|
|
//=0 |
|
11=0 |
|
|
Учитывая, что W„l2k = Qxp(-jKk), имеем |
|
|||
|
7 V /2 - 1 |
|
|
|
Х(к)= |
^ |
[х\(п{) + x2(n2)Qxp(-jnk)]lV^. |
(2.20) |
|
|
п=0 |
|
|
|
Выражение (2.20) для четных и нечетных гармоник ДПФ примет вид:
i V / 2 - l |
N 1 2 - 1 |
*(2*)= X |
[*|("|) + *2(я2)]И^"* = |
X [*|(«.)+ *2(«2)]##2; (2.21) |
//=0 |
|
//=() |
/V/2-1 |
N 1 2 - 1 |
|
Х{2к +1) = X |
К (л.)+^(«2)]< * +1)" |
=X |
//=0 |
п=0 |
|
|
|
( 2.22) |
36
Из выражений (2.21) и (2.22) видно, что четные и нечетные отсче ты ДПФ можно получить из N / 2 -точечных ДПФ последовательностей j\n ) и g(n)
f(n) = xl(n{) + x2(n2) ;
g(«) = [*1 (Л|) - *2(Л2 )WN, Л = о, N / 2 -1.
Таким образом, вычисление ДПФ исходной последовательности удалось свести к комбинации ДПФ двух последовательностей: дг,(л,) и
х2(п2). В свою очередь, каж
дое |
ДПФ |
последовательно- |
||
стей |
*,(л,) |
и х2(п2Х>(/ь) |
можно |
|
определить, |
используя |
выше |
||
описанную |
методику. |
На |
||
рис. |
2.5 в качестве примера |
|||
представлен |
направленный |
|||
граф |
8-точечного БПФ |
по |
основанию 2 с прореживани ем по частоте.
При сравнении алгорит мов БПФ с прореживанием по
времени и частоте необходимо отметить следующие два различия:
а) у алгоритмов БПФ с прореживанием по частоте порядок следо вания номеров элементов входного массива данных - прямой, а для номеров элементов выходного массива - двоично-инверсный;
б) несколько иной порядок выполнения базовой операции: при прореживании по частоте умножение комплексного числа на дейст вительное выполняется после алгебраического сложения.
Как показывает анализ направленного графа на рис. 2.5, число ум ножений для алгоритма БПФ определяется формулой (2.18).
2.3.2. Реализация алгоритмов БПФ по основанию 4. Если число N является степенью 4, то его можно записать как (N/4)4; аналогич
но: N /4 = (N/16)4.
В результате элементы исходного одномерного массива можно расположить таким образом, чтобы элементарные операции представ ляли собой четырехточечные ДПФ.
Из N -точечной последовательности х(п) сформируем четыре N /4 -точечные последовательности следующим образом:
37
*|(л) = *(4л); |
|
|
*2(л) = *(4л + 1); |
(2.23) |
|
*3(л) = .х(4л + 2); |
||
|
*4(л) = *(4,2+ 3)> л = (О /V / 4) —1.
Тогда с учетом (2.7) ДПФ исходной последовательности можно представить в виде
/V/4-1 |
Л//4-1 |
|
|
||
вд= X *(4я)и#* +X ^(4'2+о^Г,+,)" + |
|
||||
/1=0 |
|
/1=0 |
|
|
|
УУ/4-1 |
|
|
Л//4-1 |
|
|
+ £ *(4л + 2)><"+2)* + |
£ |
х(4« + 3 ) ^ 4"+3)* |
|
||
/ 1=0 |
|
|
/1=0 |
|
|
С учетом того, что W^ = ^ |
/4 |
данное выражение преобразуется к виду |
|||
i V / 4 - i |
|
N i A - \ |
|
||
*(*) = £ |
x(4nW fiA+ir* |
X 44л +1)»^4 + |
|
||
/7=0 |
|
|
/ 1=0 |
|
|
Л//4-1 |
|
|
|
Л//4-1 |
|
X |
Л<4л + 2) ^ /4 + К |
X х(4п + 3) ^ м = |
(2.24) |
||
/1=0 |
|
|
|
/1=0 |
|
= x {(k ) + x 2{k)wkN+ |
|
|
+ x A{k)WH, |
|
где к) у / = 1,4 - ДПФ последовательностей хДл), которые, в свою
очередь, могут быть определены с помощью вышеописанной вычисли тельной процедуры путем разбиения каждой из четырех последова
тельностей хДл), / = 1,4 на четыре N/16 - точечные последовательно
сти. Процесс разбиения последовательностей необходимо продолжать до тех пор, пока они не будут содержать четыре члена.
Базовая операция БПФ по основанию 4 согласно (2.7) принимает
вид
X (0) = х(0) + х(\) + дДЗ); |
|
|
т =Х(0) - jx(I) - х(2) + М 3); |
(2 25) |
|
X (2) = дс(0) - х(1) + х(2) - х(3); |
1 |
' |
X (3) = х(0) + ух(1) - х(2) - jx(3). |
|
|
Из анализа (2.25) видно, что базовая операция комплексных умножений не содержит, а включает в себя операции суммирования и поворота фазы, т.е. умножения на ±j
38
На рис.2.6 представлен полный направленный граф 16-точечного БПФ по основа нию 4 с прореживанием по времени. Процедура последо вательного сокращения вчет веро размеров преобразований показывает, что на каждом этапе БПФ необходимо вы полнить N умножений ком плексного числа на действи
тельное. |
|
Поскольку число этапов БПФ равно |
~~ |
, КА= log4iV„ |
(2.26) |
то число умножений алгоритма БПФ по основанию 4 определяется как |
|
Kv = N lo g AN, |
(2.27) |
Особенностью алгоритма БПФ с таким основанием является чет верично-инверсный порядок следования номеров элементов входного массива данных. Ниже, в табл.2.1 представлен алгоритм четверично инверсного порядка, аналогичный алгоритму двоично-инверсного по рядка лишь с той разницей, что на промежуточных этапах десятичные числа записываются в четверичном коде.
Таблица 2.1.Алгорит м четверично-инверсного порядка.
Н ом ер: |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|
Ч етверичны й |
0 |
0 |
02 |
03 |
10 |
II |
12 |
13 |
20 |
21 |
22 |
23 |
30 |
31 |
32 |
33 |
|
код |
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
И нверсия |
0 |
10 |
20 |
30 |
01 |
II |
21 |
31 |
02 |
12 |
22 |
32 |
03 |
13 |
23 |
33 |
|
И н версн ы й |
0 |
4 |
8 |
12 |
1 |
5 |
9 |
13 |
2 |
6 |
10 |
14 |
3 |
7 |
II |
15 |
|
|
ном ер
Алгоритм с прореживанием по частоте выводится аналогичным образом.
При выборе алгоритма БПФ решающую роль играет объем вычис лений, значительную часть которого обставляет число умножений дей ствительных^ комплексных чисел [8].
Анадиз соотношений (2.J5) и (2.25) показывает, что базовые одег рации БПФ по основаниям 2 и 4 таких умножений не содержат. Следо вательно, основной вклад в вычислительные затраты составляют опера
39
ции умножения на поворачивающие множители. Формулы (2.18) и (2.27) позволяют определить число таких операций для алгоритмов БПФ по основаниям 2 и 4 соответственно. Однако полученные величи ны не в полной мере характеризуют объем вычислений, так как для ряда
операций поворачивающие множители W'* не являются комплексным числом. Если W* - нетривиальное, т.е. комплексное число, то проце
дуры (2.13), (2.14) и (2.24) называются нетривиальными умножениями', их число, в основном, и определяет вычислительные затраты.
Число нетривиальных умножений, выполняемых при TV-точечном БПФ по основанию 2, можно определить с помощью соотношения [4]:
м т |
N Л^ |
2 2" -1 N |
'3 |
(2.28) |
X |
l ~ a = : |l o g 2N - ± N .+ Z |
|||
Формулу, аналогичную (2.28) для алгоритма. БПФ по основанию; 4, |
||||
можно получить, |
анализируя |
вычислительную процедуру; (2.24) нена |
||
правленный граф БПФ. |
|
|
||
Пусть п - текущий номер этапа БПФ; м=0,/С4-1. Тогда на каж* |
||||
дом этапе выполняется следующее число базовых операций: |
|
|||
K{= N/ 4. |
|
|
|
На каждом этапе они объединяются в разное число групп: на пер вом - в одну группу, на втором - в четыре группы и т.д. Число групп, в которые объединяются /С базовых операций каждого этапа, равно
К2= 4/,_|.
Следовательно, на каждом этапе в одной группе содержится Къ
операций:
Ky = Kl/K 2 = N/4"
Так как базовая операция БПФ (2.25) имеет четыре выходных чле на, то, согласно (2.24), четвертая часть всех выходных чисел этапа в
умножениях на W'* не участвует, поскольку поворачивающий множи тель при х,(А') в (2.24) отсутствует. Все остальные числа умножаются на
W'H , однако на каждом этапе три таких множителя являются тривиаль
ными, т.е. не комплексными числами, что наглядно иллюстрируется направленным графом рис. 2.6. С учетом этого можно получить форму лу, позволяющую определить число нетривиальных умножений для ал горитма БПФ по основанию 4 [8]:
40