George W. Stimson introduction to Airborne Radar (Se)

Подождите немного. Документ загружается.

CHAPTER 20 The Digital Filter Bank and the FFT

275

χ(f) =

a(n) W

n = 0

N – 1

Output.

Filter f

Sample

Phase rotation,

Filter f,

Sample n

f = filter number = 0, 1, 2 . . . . (N – 1)

n = sample number = 0, 1, 2 . . . . (N – 1)

N = 8

DERIVATION OF THE COOLEY-TUKEY FFT

For An Eight-Filter Bank

The derivation begins with the equation for the DFT, expressed in terms of the complex operator, W.

When f and n are written in binary form and expanded, they become:

f = 4f

+ 2f

+ f

n = 4n

+ 2n

+ f

The digits, f

, f

, and n

, n

can each take on a value of 1 or 0.

Carrying out those multiplications which will produce factors of 16 and 8, and bracketing the terms containing them,

Since N = 8, phase rotations of W

and W

equal W

. Since W

= 1 (no rotation), the bracketed terms for

these rotations drop out of the equation, leaving:

(2 f

) 2n

(4 f

+ 2 f

n + f

) n

a (n

, n

)

χ(f

, f

) =

Σ Σ Σ

= 0

, n

)

= 0

, f

, n

)

, f

)

fn = (4f

+ 2f

+ f

) 4n

+ (4f

+ 2f

+ f

) 2n

+ (4f

+ 2f

+ f

) n

Writing the above expression as a power of W, and taking advantage of the fact that W

(m + n)

= W

, we have

fn = 16 f

+ 8 f

+ 4 f

+ 8 f

(2 f

+ f

) 2 n

+ (4 f

+ 2 f

+ f

) n

[][]

(2 f

+ f

) 2 n

4 f

= W

(4 f

+ 2 f

+ f

) n

Substituting this expression for W

in the equation for χ(f), writing the arguments of χ(f) and a(n) in binary

form, and replacing the single summation sign with separate signs for each binary digit of n, we have:

As indicated by the horizontal bracketing, the equation can now be broken into three recursive equations,

which specify the phase rotations and partial summations to be performed in each of the three

successives processing steps of the FFT for the eight filter bank.

= 0

, n

) =

= 0

a(n

, n

)

, f

, n

) =

= 0

a(n

, n

)

(2 f

)

, f

) =

a(n

, n

)

(2 f

+ f

) 2n

(4 f

+ 2 f

n + f

) n

χ(f

, f

) = A

, f

)

The last sum [A

, f

)] consists of the outputs of the bank's 8 filters. Note the bit reversal in

the argument of A

(16 f

+ 8 f

) (4 f

+ 2 f

+ f

) n

[]

4 f

[]

8 f

= W

(2 f

+ f

) 2 n

WWW W

(−)(−)

(−) (−) (−) (−) (−)

(−) (−)

Step

(−)(−)(−)

(−)

(−)(−)(−)

(−)(−) (−)(−)

(−)(−)(−)(−) (−)(−)(−)(−)

(−) (−)(−) (−)

4 6 1 5 3 7

PART IV Pulse Doppler Radar

276

ter bank can be generated in virtually no time at all. The

flow diagram for a 16-filter bank produced in that way and

subsequently simplified with the techniques that were

illustrated in Fig. 9 is presented in Fig. 13, above.

From it, we can conclude that in the general case of a

filter bank of any size, for every multiple of 2 that the

number of filters (N) is increased, one more processing

step must be performed.

In the first step each of the samples has added to it and

subtracted from it the sample stored N/2 memory locations

away.

In the second step, each of the resulting partial sums has

added to it and subtracted from it the partial sum N/4

memory locations away, thereby doubling the number of

samples included in each partial sum.

In the third step, each of these partial sums has added to

it and subtracted from it, the partial sum N/8 memory

locations away, again doubling the number of samples

included in each sum.

This process is continued until all N samples are includ-

ed in the final sum for each filter. A total of log

N process-

ing steps are thus carried out in forming the filter. Since

13. Basic structure of the FFT. For each multiple of 2 that the number of filters is increased, one more processing step is added. The FFT shown

here is for a 16-filter bank; hence, is a four-step procedure.

the flow diagram for even a relatively small filter bank is

unwieldy, in practice the information the diagram contains

is generally printed out in tabular form.

The FFT Butterfly. When examining Fig. 13, you may

have noticed a striking similarity in the flow patterns for

the individual partial summations. In every case, the phase

rotation (when required) is made to one of the two quanti-

ties that is to be algebraically summed—the one on the

right, in that figure—before the addition and subtraction

are performed.

The pattern for this generic operation is shown in Fig.

14, along with the corresponding processing instruction.

Because of its wing-like shape when diagramed, this

instruction is called the FFT butterfly.

Having determined the appropriate pairings of memory

positions for each processing step, the entire filter bank

can be formed by iteratively carrying out this basic instruc-

tion on the contents of each successive pair of memory

positions.

Rules of Thumb for Estimating Number of Computations

While the tremendous reduction in computing load

which may be realized through the use of the FFT should

by now be apparent, it is interesting to consider quantita-

tively what it amounts to in the more general case of large

filter banks

If we were to use the DFT to form an N-filter bank, we

would expect to have to perform one phase rotation and

one complex addition for each sample per filter. Since N

samples must be summed to form a filter and the bank con-

tains N filters, forming the bank would require a total of N

phase rotations and N

complex additions.

On the other hand, to form the bank with the FFT, we

would expect to have to perform N phase rotations and N

CHAPTER 20 The Digital Filter Bank and the FFT

277

14. Derivation of the FFT butterfly instruction from the generic flow

pattern of the individual partial summations which are the

building blocks of the FFT algorithm.

= x

+ W

= x

– W

(–)

Generic FFT

Processing Flow

Pattern

The FFT Butterfly Instruction

–

PART IV Pulse Doppler Radar

278

complex additions in each of only log

N processing steps,

for a total of N log

N rotations and N log

N additions.

However, as the FFT butterfly diagram makes clear, half of

the rotations are eliminated (as was illustrated in Fig. 9) by

substituting for them changes in algebraic sign. Thus, the

total processing requirements for the FFT are:

Phase rotations . . . 0.5 N log

Complex additions . . . N log

As we have seen, for small filter banks the FFT reduces

the number of phase rotations substantially more than the

above rule implies. But for the general case of larger banks,

the required number of rotations closely approaches that

given by the rule.

To illustrate the FFT’s efficiency, it will be instructive to

apply these rules to a reasonably large bank, say, one con-

taining 2,048 filters.

Since log

2,048 = 11, the bank can be formed with 0.5

x 2,048 x 11 = 11,264 phase rotations. Each of these

requires 6 simple mathematical operations—4 multiplica-

tions, 1 addition, and 1 subtraction—for a total of 67,584.

Adding to this figure two simple operations for each of

2,048 x 11 complex additions, brings the total number of

simple operations needed to form the bank with the FFT

to 112,640.

By contrast, to form the same bank directly with the

DFT, it would take 2,048 x 2,048 x 8 = 33,554,432 simple

operations (Fig.15). That is roughly 300 times as much

computing!

Moreover, because the number of processing steps

increases only as the logarithm of the number of filters, as

the size of the filter increases, the reduction in computa-

tions achievable with the FFT increases dramatically.

Summary

The FFT is an algorithm which vastly reduces the

amount of processing necessary to form a bank of digital

filters with the DFT. Its efficiency is achieved primarily by

choosing the parameters of the bank so that they are har-

monically related and consolidating the formation of the

filters into a single multiple-step process.

By making the number of filters, N, equal to a power of

two and the number of samples summed equal to N, the

processing is accomplished in log

N steps. In the first

step, each sample is algebraically summed with one of the

other samples. In each succeeding step, certain phase rota-

tions are performed, and each partial sum is algebraically

15. Reduction in number of computations achieved by forming a

filter bank with the FFT rather than with the DFT. As the num-

ber of filters in the bank increases, the reduction becomes

immense.

Number of Filters, N

FFT

0.1

1024512256

DFT

2048

Simple Computations (Millions)

summed with one of the other partial sums.

The required phase rotations and pairing of the quanti-

ties to be summed in each step can readily be determined

mathematically. The basic processing instruction for per-

forming the individual partial summations—consisting of

a phase rotation, a complex addition, and a complex sub-

traction—is called the FFT butterfly. The phase rotations

themselves are performed the same way as in the DFT.

The partial sums are returned to the same memory loca-

tions as held the quantities that were summed. The final

sums are read out in the order of the filter numbers they

apply to, by labeling the memory locations with the num-

bers—in binary form—of the samples they originally held

and reversing the order of the bits in these numbers.

Whereas N

complex multiplies and N

complex addi-

tions must be performed to form an N-filter bank with the

DFT, only 0.5 N Log

N complex multiplies and N Log

complex additions must be performed to form the same

bank with the FFT.

CHAPTER 20 The Digital Filter Bank and the FFT

279

A POINT OF NOMENCLATURE

In this chapter, we have described the filter

banks formed with the FFT in terms of the number of

filters they contain, N, or of the number of samples

summed to form the filters—the two numbers being

the same for any one bank.

Signal processing experts, however, commonly

describe filter banks in terms of points, the word

"point" meaning the number of data points (samples)

used to form the bank. A 16-filter bank, for example,

is referred to as a 16-point filter, or a 16-point FFT.

Accordingly, in a functional block diagram, a filter

bank may be conveniently represented by a box with

the number of points written beneath it:

FFT

16 point

281

Measuring Range Rate

1. Range rate, R

⋅

, corresponds to the slope of a plot of range

versus time.

n many radar applications, knowing a target’s present

position (angle and range) relative to the radar is not

enough. Often one must be able to predict the target’s

position at some future time. For that, we must also

know the target’s angular rate and its range rate.

Range rate may be determined by one of two general

methods. In the first, called range differentiation, the rate is

computed on the basis of the change in the measured

range with time. In the second and generally superior

method, the radar measures the target’s doppler frequen-

cy—which is directly proportional to the range rate.

In this chapter, we will look at both methods briefly. We

will then take stock of potential doppler ambiguities and

see how they may be resolved.

Range Differentiation

If we plot the range of a target versus time, the slope of

the plot is the range rate (Fig. 1). A downward slope corre-

sponds to a negative rate; an upward slope, to a positive

rate.

Determining the slope—hence the range rate—is easy.

You select two points on the plot which are separated by a

small difference in time and pick off the difference in their

ranges. Dividing the range difference by the time difference

yields the range rate

⋅

∆R

∆t

where

⋅

= range rate

∆R = difference in range

∆t = difference in time

Click for high-quality image

4. The shorter ∆t is, the more the measured range rate may differ from the actual rate as a result of noise in the measured range.

PART IV Pulse Doppler Radar

282

If ∆R is taken as the difference between the current range

and the range ∆t seconds earlier, R

⋅

corresponds to the cur-

rent range rate. This process approximates differentiation

(Fig. 2).

In essence, range rate is measured in this way both by

non-doppler radars and by doppler radars when operating

under conditions where doppler ambiguities are too severe

for range rate to be measured directly by sensing doppler

frequency.

If the range rate is changing, the shorter ∆t is made, the

more closely the measured rate, R

⋅

, will follow the changes

in the actual rate; i.e., the less the measured rate will lag

behind the actual rate (Fig. 3)—a quality referred to as good

dynamic response.

2. Slope of range plot can be found by taking difference in range

(∆R) at points separated by short increment of time (∆t).

3. The shorter ∆t is made, the closer the measured slope will fol-

low changes in the actual range rate.

1. With differentiation, the time

difference (∆t) is infinitesimal.

Unfortunately, a certain amount of random error, or

“noise” is invariably present in the measured range. Though

small in comparison to the range itself, the noise can be

appreciable in comparison to ∆R. In fact, the shorter ∆t is

made, the smaller ∆R will be and therefore the greater the

extent to which the noise will degrade the rate measure-

ment (Fig. 4).

Click for high-quality image

The noise can be reduced by subsequently “smoothing”

the measured range rate, but the effect of smoothing on

response time is essentially the same as that of increasing

∆t. The performance achieved with this method of range

rate measurement is thus a compromise between smooth

tracking and good dynamic response.

When a target is tracked without stopping the antenna’s

search scan (track-while-scan), the dynamic response is

still further limited by the fact that ∆t is stretched to a full

scan frame time. If the radar’s range measurement sensitivi-

ty is sufficiently high, though, a useful estimate of the range

rate can usually be provided during the dwell time by

extrapolation.

Doppler Method

A doppler radar can not only measure range rates with

greater precision than is possible with range differentiation,

but make the measurement directly.

In the absence of doppler ambiguities, a target’s doppler

frequency may be determined simply by noting in which fil-

ter of the doppler filter bank the target appears (Fig. 5), or,

if it appears in two adjacent filters, by interpolating between

the center frequencies of the filters on the basis of the differ-

ence in their outputs. In translating the doppler spectrum to

the frequency of the filter bank, accurate track must have

been kept of the relative position of the transmitter frequen-

cy, f

. To measure the doppler frequency, one need only

count down the bank from the target’s position to the fre-

quency corresponding to f

—or, if the doppler spectrum has

been offset from f

to put the mainlobe clutter at zero fre-

quency, count to the bottom of the filter and add the offset.

The doppler frequency is determined with greater preci-

sion during single-target tracking. In this mode, the receiver

output is usually applied in parallel to two adjacent doppler

filters, whose passbands overlap near their –3 dB points

(Fig. 6).

CHAPTER 21 Measuring Range Rate

283

5. A target’s doppler frequency may be determined simply by

noting the target’s position in the filter bank.

6. In single-target tracking, an offset is added to the target’s frequen-

cy to center it exactly between two filters. The doppler shift is then

determined by precisely measuring the offset.

Click for high-quality image

7. Hypothetical situation used to illustrate conditions under which

doppler measurements may be significantly ambiguous.

PART IV Pulse Doppler Radar

284

An automatic tracking circuit (velocity servo) then shifts

the doppler spectrum so it is offset from f

by just enough

to cause the target to produce equal outputs from the two

filters. The offset is thus maintained equal to the target’s

doppler frequency, and the doppler frequency is measured

by measuring the offset.

The range rate is computed from the doppler frequency

with the inverse of the expression for doppler frequency

derived in Chap. 15:

⋅

= –

where

⋅

= range rate

= doppler frequency

λ = wavelength

The rules of thumb we learned in that chapter can simi-

larly be inverted. For an X-band radar, range rate in feet per

second is nearly equal to the doppler frequency in hertz

divided by 20.

And in knots, the range rate is nearly equal to the

doppler frequency in hertz divided by 35.

But how do we know that it is the target echoes’ carrier

frequency we have observed and not a sideband frequency

some multiple of f

above or below the carrier? Isn’t any

doppler frequency we measure, hence the range rate we

compute from it, inevitably ambiguous?

Yes. But whether the ambiguity is significant depends on

the PRF and the magnitudes of the closing rates that may

be encountered.

Potential Doppler Ambiguities

To get a feel for the significance of doppler ambiguities at

different PRFs, let us consider a hypothetical operational

situation.

Hypothetical Situation. We’ll assume that a radar is

operating against targets that may be detected anywhere

within a 120˚-wide sector, dead ahead (Fig. 7). The targets

may be flying in any direction.

Their speeds, too, may vary but are not expected to

exceed 1000 knots. The maximum speed of the aircraft car-

rying the radar, we’ll say, is also 1000 knots.

Under these conditions, the maximum closing rate

which the radar might encounter—i.e., the rate when both

the radar-bearing aircraft and the target are flying at maxi-

mum speed, nose-on (R

⋅

is negative for such approaches) —

would be –1000 – 1000 = –2000 knots (Fig. 8). At X-band,

this rate would produce a doppler shift of roughly 2000 x

35 = 70 kHz.

The maximum opening rate (R

⋅

is positive) would occur if

a target were at the largest azimuth angle (60º) and flying at

maximum speed away from the radar, while the radar-bear-

ing aircraft was flying at its minimum cruising speed. That

speed, we’ll say, is 400 knots. The range rate then would be

+1000 – (0.5 x 400) = +800 knots. This rate produces a

doppler shift of – 800 x 35 Hz = –28 kHz.

Thus, provided the radar does not encounter a signifi-

cant target whose speed exceeds 1000 knots or whose

azimuth exceeds 60º, the spread between maximum posi-

tive and negative doppler frequencies would be 70 – (–28)

= 98 kHz (Fig. 9).

CHAPTER 21 Measuring Range Rate

285

8. Flight geometry producing maximum negative doppler frequency,

left; maximum positive doppler frequency, right.

Remember that negative range

rates (range decreasing, – R

⋅

)

result in positive doppler fre-

quencies and vice versa accord-

ing to the equation

=–

⋅

PRF Greater Than Spread of Doppler Frequencies.

Suppose, now, that in the above described situation, the

radar’s PRF is 120 kilohertz. To cover the band of anticipat-

ed doppler frequencies (–28 kilohertz to +70 kilohertz)

with a little room to spare, let’s say we provide a doppler fil-

ter bank having a bandwidth extending from a little below

–28 kilohertz to a little above +70 kilohertz (Fig. 10).

If we encounter a target having the maximum anticipated

closing rate—doppler frequency of +70 kilohertz—the car-

rier frequency (central spectral line) of its echoes will fall

just inside the high frequency end of the passband. Since

the first pair of sidebands are separated from the carrier by

the PRF (120 kilohertz), the sideband nearest the passband

will have a frequency of 70–120 = –50 kHz, well below the

lower end of the passband.

Similarly, if we encounter a target having the maximum

anticipated negative doppler frequency (–28 kilohertz), the

carrier frequency of its echoes will fall just inside the lower

end of the passband (Fig. 11). The nearest sideband in this

case will have a frequency of –28 + 120 = 92 kHz, well

above the upper end of the passband.

9. Spread between maximum positive and negative doppler fre-

quencies for hypothetical situation.

10. If PRF

exceeds

spread between the maximum positive and

negative doppler frequencies, carrier of most rapidly closing

target will fall in passband and nearest sideband will lie

below it.

11. Carrier of maximum opening-rate target will similarly fall in

passband and nearest sideband will lie above it.

Click for high-quality image