Modern radars perform nearly the entire required signal processing digitally. The most common digital signal processing technique used is Fast Fourier Transform (FFT). Within radar datapaths, this algorithm is used in areas such as beamforming, pulse compression and Doppler processing. To get started, a brief introduction to the FFT follows.
Fast Fourier Transform
The FFT technique is simply a highly optimized implementation of the Discrete Fourier Transform (DFT). Both FFT and DFT produce identical results, but the FFT requires a small fraction of the computational effort compared to the DFT.
DFT is a transform upon an input sequence of sampled data (a signal), producing the frequency content, or spectral representation of that sampled data sequence. This will give the representation of the signal in the frequency domain.
There is also an Inverse Discrete Fourier Transform (IDFT) and an Inverse Fast Fourier Transform (IFFT). Again, the IFFT is simply an optimized form of the IDFT. They both compute the time domain representation of the signal from the frequency domain information. Using these transforms, it is possible to go back and forth between the time domain signal and the frequency domain spectral representation.
The DFT is performed over the complex input data sequence “xi” of length N. To use the much more computationally efficient FFT, N must be of length 2n, where n is any positive integer. Lengths less than this can zero extend to the next 2n length. The complex output sequence “Xk” is also of length 2n. The DFT converts a sampled time domain signal (xi) to a sampled frequency domain (Xk) spectral representation. So rather than computing sampled frequency ω continuously from –π to π, it will instead compute at N equally spaced points over an interval of 2π. Both indexes i and k will run from 0 to N-1.
DFT and IDFT transform equations
The DFT and IDFT equations are both summations of N complex exponentials. As seen below, these equations appear to be very similar:
Intuitively, what the DFT does is correlate the input data samples against N
equally spaced frequency signals. The frequency domain representation Xk
is simply the weighting of each of these correlations, in both magnitude and phase. If the input signal does not have any of a particular frequency present, then the resulting correlation will be zero and the value of Xk for that frequency is zero. The values of Xk
therefore give the magnitude and phase of each frequency component in the signal.
The only differences in the DFT and IDFT equations are the negative sign on the exponent on the DFT equation and the factor of 1/N
on the IDFT equation. Notice the DFT equation uses each and every one of the time domain samples to compute each frequency domain sample. And the IDFT equation requires that each and every one of the frequency domain samples be used to compute each time domain sample.
So to compute a single sample of either transform requires N
complex multiplies and additions. To compute the entire transform will require computing N
samples, for a total of N2
multiplies and additions. The FFT is much more computationally efficient, as shown in Table 1. For example, using a 1024 point sequence, the FFT can be computed with only 1% of the effort required by the DFT.
Table 1. FFT and DFT computational efforts
Again, the values of Xk
represent the amount of signal energy at each frequency point, equally spaced across the sampled frequency spectrum. Since is a complex number, it provides both the magnitude and phase of each frequency component. These points in the frequency spectrum are often referred to as frequency bins. As N
becomes larger, the spectrum is divided into more bins, with closer frequency spacing, providing for finer frequency discrimination.
Beamforming is a digital technique that focuses the radar transmitter and receiver in a particular direction. The side to side direction is commonly referred to as the azimuth and the up and down direction as the elevation. Beamforming can be used to focus the radar over both azimuth and elevations.
Early airborne radars, and many ground and naval radars used the more familiar parabolic type antennas shown in Figure 1. The parabolic shape focuses both receive and transmit energy in the direction of the antenna. The antenna may be rotated to search in all directions or aimed in the azimuth and elevation of interest.
Figure 1. Parabolic antenna
In order to search across the area of interest, the antenna must mechanically be aimed or rotated to steer its beam in the desired direction. In many military applications, this function is often performed electronically, using active electronically scanned array (AESA), which is an electronically steerable antenna. This allows very rapid steering of the radar beam, which is particularly useful for military airborne radars. This technique is known as “beamforming”, which references the electronic steering of the main antenna lobe or beam.
An AESA is built from many small antennas or individual elements. Each antenna element has a transmit and a receive module. Therefore, each element can individually vary the phase and amplitude of both receive and transmit signals. These changes, particularly in phase, provide for steerable directivity of the antenna beam over both azimuth and elevation. Only when the receive signal arrives in-phase across all the antenna elements will the maximum signal be received. This provides the ability to “aim” the main lobe of the antenna in a desired direction. The process is reciprocal, meaning that the same antenna lobe pattern will exist on both receive and transmit (assuming common frequency for receive and transmit).
Each antenna element must have a delay, or phase adjustment, such that after this adjustment, all elements will have a common phase of the signal. If the angle θ = 0, then all the elements will receive the signal simultaneously, and no phase adjustment is necessary. At a non-zero angle, each element will have a delay to provide alignment of the wavefront across the antenna array, as shown in Figure 2. Once each antenna element input is downconverted to baseband by a common clock and local oscillator, each antenna input is delayed by the correct amount so that the wave front arriving from a given direction is aligned. This delay can be digitally implemented by phase rotations, or multiplication by Wi
i. For better side lobe control, the amplitude can also be varied, by using Wi
i. By adaptively changing Wi
for each antenna input, the beamforming can be accomplished.
Figure 2. Active digital beamforming
The transmit direction works in the same manner. The advantage is very rapid steering, which can allow fast searching as well as tracking of objects. Mechanical movement and motors can be eliminated. Using a technique called “lobing”; the radar beam can be rapidly steered on either side of a target. By noting where the stronger return is, the target movement can be more accurately tracked.
Digital beamforming can also be used in another capacity. In some systems, it is desired to receive and transmit separate signals in different directions simultaneously. This can be accomplished by using the FFT algorithm. Normally, FFTs are used to take a time domain signal and separate it into its different frequency components. In this case, the FFT will separate the incoming signal into its different spatial components or angle of arrival components. The input signals are sorted by the FFT into bins corresponding to different angles of arrival, as shown in Figure 3. Similarly, in the transmit direction, a signal fed into each FFT bin input will be transmitted in a specific direction, corresponding to a specific antenna lobe. If the input to a FFT bin is zero, no energy will be transmitted in that direction; the transmit lobe will be “missing”.
Figure 3. FFT beamforming
The FFT method of beamforming is computationally very efficient and allows for multiple directional signals to be simultaneously received and transmitted. This can be a very useful capability in multi-mode radar, which must track multiple targets simultaneously. However, the spacing and direction of the N
antenna beams are fixed and equally spaced in direction, ranging over 180 degrees from the antenna array. In keeping with the characteristics of the FFT, the peak of any given antenna beam lies exactly on the null of the sidelobes of all the neighboring antenna beams. This characteristic is known as orthongonality.
The next steps in receive processing are typically pulse compression and Doppler processing. Pulse compression is simply matched filtering or filtering of the received signal against the transmitted pulse shape. This type of filtering gives the maximum response when the received signal exactly matches the transmitted signal, indicating that it is indeed a reflected and delayed version of the transmit pulse (also known as auto-correlation). The order of pulse compression and Doppler processing can be interchanged, but here pulse compression is assumed to occur first and Doppler processing afterwards.
Figure 4. Pulse compression using a FIR filter
In Figure 4, the pulse compression is depicted as a FIR filter being performed on the receive samples of each PRF interval. For example, assume that the radar is sampling at 100 MHz with a PRF of 10 kHz. For each PRF, there are 10,000 complex samples received in each vertical bin. Each bin of samples is then passed through a matched filter. When reflections of the transmit pulse are received, these will cause a response in the output of the matched filter.
Transmit pulses are often in a pseudo-random sequence, perhaps modulated using phase or frequency changes. The pseudo-random, or PN sequences, are designed to have strong auto-correlation properties. This means that the matched filter will only produce an output when the received pulse is precisely matched, which allows for the arrival time of the received pulse to be determined in an equally precise manner. Correlating, or matching to PN sequences also tends to produce very low outputs for any other signal or noise other than the transmit pulse. Different radar applications and modes will require different transmit waveforms and this is quite a large subject in itself.
The matched filter FIR function can be implemented in the frequency domain. In this case, the receive signal spectrum is obtained though FFT processing of the received data. Then the frequency spectrum of the transmit pulse is masked onto the frequency response of the receive signal. The greatest response occurs when the two match. The result is then converted back to the time domain using the IFFT and can be Doppler processed next. This may seem to be a complicated alternative, but the FFT algorithm is so efficient that this method can result in lower computations than FIR filtering.
In Part 2
of this series on Radar Basics, Doppler processing was discussed. In Figure 5, Doppler processing is depicted across the radar data array. The columns of data correspond to the pulse compression filtering of each PRF received data buffer. The number of N columns is the number of transmit pulses in the coherent processing interval (CPI). Recall that all of the radar data is complex, having magnitude and phase. The CPI has to do with the phase relationships between data across the array. Over time, slight clock drifts and jitter can in the clocking circuits, data convertors and phase locked loops used in the RF and digital circuits can cause relative phase shifts between samples. For airborne or vehicle mounted radar, movement of the radar can also disturb phase relationships. The longer the elapsed time across the receive data samples, the greater the likelihood of relative phase degradations. In addition, any radar frequency mode changes or PRF changes can cause a discontinuity in phase. The CPI is a measure of the time interval over which these phase differences carry useful information or are coherent and can therefore be used for frequency domain processing, such as Doppler processing. It normally extends over multiple PRF time periods.
Notice that the received sample output from the pulse compression processing are loaded in columns for each PRF. The Doppler processing occurs across rows or across the N PRFs. The data must be collected over a time interval where the data can be considered coherent or within the CPI.
Figure 5. Doppler processing “Corner Turn”
This data flow is known as a “corner turn” in radar vernacular, because the data goes in vertically and comes out horizontally or turns the corner. This processing requires that all the data be present in the array before any Doppler processing can be performed. The amount of data can be quite large and for high performance radar processing, needs to be accessed with very low latency. This either requires very high on-chip memory resources or a very low latency, fast random access external memory array coupled with a high performance memory access controller. Since the data comes in columns and is read in rows, the read and write accesses cannot both be sequential, making it difficult to meet the low latency requirements with traditional caches and DDR memory chips.
Radar processing requirements can be quite high. The receiver needs to process the input data continuously, in real time. Fortunately, much of this can be implemented using parallel processing structures. Beamforming is one example. There can be hundreds or even thousands of separate receive/transmit units in an AESA antenna. The antenna may be tracking targets in multiple directions, requiring separate processing for each. The processing must be performed over two dimensions, both time (pulse compression) and frequency (Doppler). Furthermore, in installment #4 of this Radar Basics series, how an additional processing dimension, spatial, can be added in the space-time adaptive processing (STAP), which will cause a further dramatic increase in digital signal processing requirements.
Numerical accuracy concerns
Radar systems are very challenging to design, partly because of the dynamic range of the signals involved. Referring back to the radar range equation, the signal level at the receiver is proportional to the fourth power of the distance to target. The sensitivity levels required by a radar receiver are far more demanding than any wireless communications system. Simultaneously, the radar receiver must cope with potentially very high receive signal levels due to clutter, jamming, interference, close range targets, or even from the transmitter itself.
This requires high, numerical fidelity digital signal processing techniques. In order to achieve proper system performance with potentially very low signal levels and high level of interference, the quantization noise levels introduced during digital processing must be well below the receiver noise floor. And the large undesired signals must be represented simultaneously with very small desired receive signals. This means high precision and high dynamic range of the datapath must be maintained.
Fixed point precision and dynamic range is defined by the bit width. The dynamic range is 6x the number of bits. For example, a 16 bit width provides for 96 dB dynamic range. This may sound like a lot, but the signal has to have guard bits to ensure no overflow and small signal could be 100 dB or more below interfering signals. For reasonable detection, the desired signal needs to be 30 dB or more above interference and noise by the time it reaches the detection processing. Maintaining adequate SNR can be difficult. After each stage of the processing, the signal level needs to be adjusted to stay within the fixed point bit width. Further, consider the FFT algorithm. In the process of converting between time and frequency domain, there is an increase in required bit width, typically of n
bits for a 2n
size data length.
Most processors and digital signal processors (DSPs) operating with 16 bit word lengths are not sufficient for many aspects of radar processing. Another option is to use floating point processors. With single precision floating point, a 24 bit mantissa (including sign bit) provides 144 dB. And the floating point exponent (8 bits) allows this 144 dB range to automatically adjust or “float” to the signal level at each operation, providing tremendous dynamic range. However, the floating point processors often found in radar systems, such as Analog Device’s Tigersharc or Freescale’s PowerPC, have limited processing capability. Newer processor architectures offer higher levels of floating point processing capability, primarily though the use of many cores. The trade-off is a more difficult development environment, requiring complex data flow management and that the data dependencies be eliminated between various functions in order to be partitioned across multiple processors without stalling. Power consumption can also be a challenge in these architectures.
Field programmable gate arrays (FPGAs) provide an alternative digital signal processing platform. Typically, FPGAs are used for front end radar processing, such as beamforming and pulse compression. For high throughput, the parallel structure of FPGAs has tremendous advantages over the processors. The FPGA industry standardized on 18 bit DSP structures over ten years ago. This was an improvement over the 16 bit fixed point precision offered by most processor architectures.
FPGA vendor Xilinx
later standardized on the 18x25 size multiplier with the DSP48E architecture (so named for its 48 bit accumulator). This was to better support FFTs, where bit growth occurs in the data path as described above. The twiddle factors, or coefficients remain at 18 bits, while the 18 bit data can grow up to 7 more bits, to 25 bits. FPGA vendor Altera
countered with an 18x36 multiplier mode. The latest innovation occurred with Altera’s 28nm Stratix V FPGAs, offering a new Variable Precision DSP architecture. This architecture has native support for 18x18, 18x36 and 27x27 precision multipliers, all featuring 64 bit accumulators. It supports higher precision fixed point processing for FIR filters, correlators, accumulators and FFTs, and also includes a highly efficient 18x25 complex multiplication mode specifically designed for fixed point FFTs. The 18x25 complex mode can be with only three multipliers rather than the normally required four multipliers, by leveraging built in pre-adders and post adders.
Another recent FPGA innovation is high-performance floating-point support that enables the FPGA parallel hardware architecture advantages to be used in applications the dynamic range of floating-point is required such as radar processing. This is now available from Altera, using the Variable Precision DSP hardware architecture and new floating-point tool flow known as “Fused Datapath”.
Table 2. Floating-point FFT FPGA performance
Table 2 shows the performance and resource usage of fourteen single precision complex floating point FFTs, each 1024 points, built using the Altera FFT Megacore IP (which incorporates “Fused Datapath” technology). This example demonstrates that FPGAs can now implement large floating point designs in high density FPGAs. Also, this is full floating point, not “block” floating point. Block floating point uses a common exponent for the complete input data set and output data set of the FPGA, which scales the data samples group, but cannot provide high dynamic range. This is because very small data values must use the exponent of the largest data value, which means they cannot be properly represented. Block floating point leads to many of the same numerical issues as fixed point.
In Part 4
of this Radar Basics series, Space Time Adaptive Processing (STAP) radar processing will be examined. This class of algorithms provides capabilities beyond that of Doppler radar processing, but has extremely high processing requirements and also requires the dynamic range of floating point.
Until recently, only the most advanced computer types have been able to implement this type of algorithm, due to these extreme processing requirements. However, now FPGAs can provide complex floating point processing at the performance levels required. As will be shown, STAP requires the processing capability to invert matrices containing of 100,000 or more elements in well under a millisecond.
Also see Part 1
and Part 2
of this five-part mini-series on “Radar Basics”.
About the author
As senior DSP technical marketing manager, Michael Parker is responsible for Altera’s DSP-related IP, and is also involved in optimizing FPGA architecture planning for DSP applications.
Mr. Parker joined Altera in January 2007, and has over 20 years of DSP wireless engineering design experience with Alvarion, Soma Networks, TCSI, Stanford Telecom and several startup companies.