The Growth of Computational Complexity in Evolving Signal Processing Algorithms

Introduction

The evolution of technical fields like RADAR (RAdio Detection and Ranging) yields higher performance of technology. Hardware, communication, and adaptability are elements in application development that impact the computational complexity of Radar algorithms. As hardware like power systems and memory capacities develop, Radar engineers have more capability to develop more efficient designs for applications. Better performing applications lead to larger computational workloads [1]. With newer applications, Radar systems need to maintain their communication and data processing systems which can be troublesome as data is sent at higher frequencies. One of the overlooked aspects of this communication is buffering. Data needs to be received in one buffer and unloaded into a program at a rapid pace. Inside these programs, the ability to process this data rapidly is required [2]. If a system is incapable of processing data or communicating with other Radar systems, the system will fail to fulfill its application. These new algorithms need to be adaptable among a variety of different Radar applications. To make algorithms adaptable, systems must run the algorithm efficiently based on processor limitations.
Without improving computational complexity, Radar systems would be unable to meet performance expectations. Engineers are looking for improvements in Radar algorithm computational complexity all around the world to improve overall efficiency. This report will discuss two main approaches to dealing with this problem of computational complexity. The first of these implementations is better performing algorithms that simplify the process altogether. The second of the two is hardware improvements that can reduce the overall workload on the processors by handling data in several different ways.

Implementations

Part 1: Software Implementations

)

In Korea, a group found that Synthetic Aperture Radar applications that implement traditional Range Migration algorithms lacked the capability of producing clear images and took up significant computational complexity. The performance issues stemmed from not accounting for the turbulence of the Radar system during flight. In order to solve these issues, the group decided to implement two “one dimension” interpolations along with a motion compensation algorithm while data is transmitted. [3] This lead to the overall complexity being reduced. However, each algorithm still required a massive workload to function and they are susceptible to a larger range of errors if they were to be implemented for future Radar systems.
Another Radar software improvement was conducted by the U.S. Air Force. In Ground Moving Target Indicator Radar, computationally complex filters and statistical algorithms must be applied to track multiple targets. Each of these processes is complex in nature and requires high-frequency processing for semi-accurate results. As an alternative, the group implemented neural nets for noise reduction thresholds to alter with readings. This improved the efficiency of the algorithm and reduced complexity by altering the real-time processing to ignore irrelevant data in the processing chain. However, a high-powered processor beyond even those used on Radars must be developed. [4]
Space Time Adaptive Processing requires a large amount processing in terms of physical area as well as time domain and frequency domain data. This kind of processing requires high-powered processors that are expensive and not always efficient based on continuous use. These processors are used in a Multiple Input Multiple Output. One group from Caltech implemented an iterative algorithm based on Single Input Multiple Ouput applications to increase performance by improving signal to noise ratios with each iteration. This algorithm takes advantage of Prolate Spheroidal Wave Functions to account for clutter space of data. While this algorithm reduces computational complexity, it fails to remove the necessary processors for a successful Space Time Adaptive Processing Application. [5]
A group from Duke University implemented a compressing sensing application that produced reconstructions of three-dimensional images using two dimensional estimations in a Single Input Multiple Output Radar system. This impelementation reduced the overall hardware needed as well as the computational complexity of three dimensional imaging. However, these estimations are subject to errors based on relying on multiple readings to produce the three dimensional images. [6]

Part 2: Hardware Implementations

)

At MIT Lincoln Laboratory, an innovative Radar antenna panel was developed for sense-and-avoid unmanned aerial vehicles. The sensor designed in the lab covers a larger imaging area and allows for a higher sampling frequency than traditional Radar sensors because the panel implements large arrays of antennas to transmit and receive data along with an optimized amplifier that filters out noise. These features make measurements more precise; therefore, less sampling overall is required. However, the cost of this panel makes this implementation suboptimal [7].
Lincoln Laboratory implements other hardware features to optimize the performance of Radar applications. In-Phase and Quadrature algorithms are complex in the various stages of processing required. These systems are typically used to track weather in real-time. Part of this algorithm is the complex process of clutter filtering. Many of these operations can occur in a parallel. Graphics Processing Units are implemented to handle computations in parallel and reduce the overall run time of the filtering by dividing the workload [8].
In the field of Radar signal processing, GPUs are a powerful method to perform complex computations at rapid rates. A research team from Sweden conducted experiments with Space Time Adaptive Radar processing algorithms to test the performance of various GPUs. They paid attention to the power consumption required for each Floating Point Operation. Their results showed that the parallel computations of these algorithms had a reduced computational runtime for large data sets and arithmetic operations. However, these GPU’s were not as efficient for serial computations [9].
The journal Computational Complexity suggests that implementing GPU’s on top of Central Processing Units is worth the performance enhancement of GROMACS simulations. The group also agrees that parallel data processing are ideal for GPUs. However, they do mention that there are limitations to the GPUs if they are overloaded with constant processing. Additionally, bottlenecks can exist in these GPUs that would reduce the overall efficiency of the computational complexity. To implement these on a large scale, many high performing GPUs would be necessary which costs a significant amount of money. This applies to Radar GPUs as well since the computational complexity of most applications in massive to begin with [10].

Conclusions
Each kind of implementation has strengths and weaknesses. Software implementations attempt to optimize the performance of algorithms by breaking down the computations into smaller modules rather than one overarching algorithm. While this tends to be effective in improving the computational complexity of the radar applications, new problems stem in terms of sacrificing precision in results and opening new windows for errors within the algorithms This becomes problematic in maintaining these algorithms for future use. Hardware implementations offer improvements in the physical radar systems themselves which can optimize the precision and accuracy of the data sent between systems. Additionally, GPUs are a proven processing unit that handle complex computations by dividing computations amongst smaller processing units. The major downside to hardware advancements is constant implementation cost. Wear and tear plays an important role with hardware because it often leads to the need for a replacement system or an even new design. Knowing both approaches presents a large scope of potential innovations in the field of Radar
While both types of implementations have their faults, they are better off being used based on the design constraints. This does not necessarily mean that one should ignore software optimization for a hardware focused design and vice-versa. Incorporating an innovative software element to a hardware focused design can help save on the cost of design and implementation. Likewise, using a new GPU or sensor can help maintain precision and reduce errors in algorithms that focus on using estimations to determine information. Overall, advancements in software and hardware systems allows for more capability in Radar systems altogether. Radar signal processing engineers should be willing to try out a solution best meets their design needs. As real world constraints are introduced to Radar projects like budgets and performance optimization, engineers are able to handle computational complexity knowing that they can attempt a wide range of implementation strategies to reach their objectives.

Works Cited

[1] B. Himed and M.C. Wicks, “Four Problems in RADAR,” Air Force Research Laboratory, Technical Report, 26 Electronic Parkway Rome, New York 13441-4514, 2013
[2] M.S. Greco et al. “Introduction to the Issue on Advanced Signal Processing Techniques for Radar Applications,” IEEE Journal of selected topics in signal processing, VOL. 9, NO. 8, pp. 1363-1365, December 2015
[3] K.T. Kim, and S.H. Park, “MOTION COMPENSATION FOR SQUINT MODE SPOTLIGHT SAR IMAGING USING EFFICIENT 2D INTERPOLATION,” Pukyong National University Research Fund, Technical Report, Busan, Korea, 2012
[4] L.I. Perlovski and R. W. Deming, “Concurrent Detection and Tracking for GMTI” Air Force Research Laboratory, Technical Report, Lexington, Massachusetts, 2013
[5] C.Y. Chen, “Signal Processing Algorithms for MIMO Radar”, California Institute of Technology, Thesis, Pasadena
[6] T. Fromentez et al. “Single-Shot Compressive Multiple-Inputs Multiple-Outputs Radar Imaging Using a Two-Port Passive Device”, Duke University, Technical Report, Durham, North Carolina, 2016
[7] S.M. Duffy, “Airborne Sense and Avoid Radar Panel,” MIT Lincoln Laboratory, Technical Report, Lexington, Massachusetts, 2014
[8] J.Y.N. Cho, “Signal Processing Algorithms for the Terminal Doppler Weather Radar: Build 2,” MIT Lincoln Laboratory, Technical Report, Lexington, Massachusetts, 2010
[9] J. Pettersson and I. Wainwright, “Radar Signal Processing with Graphics Processors,” Uppsala University, Thesis, Uppsala, Sweden, 2010
[10] C. Kutzner et al, “Best Bang for Your Buck: GPU Nodes for GROMACS Simulations,” Computational Chemistry, Technical Report. 2015