The RASSP Digest - Vol. 3, September 1996

Numeric and Symbolic Algorithms for Signal Processing

by Alan Oppenheim

Abstract

The overall goals of the RASSP Technology Base program at the Massachusetts Institute of Technology involve the areas of algorithms (numeric and symbolic) design for signal processing applications. Specifically, the task focuses on identifying and developing approximate classes of emerging and classical algorithms which will exercise and challenge RASSP tools and process.

1. Objectives

The following were the main technical objectives of our RASSP program at MIT.

Develop and analyze algorithms for approximate signal processing and incremental refinement.
Develop and analyze algorithms for low-power signal processing.
Develop and implement signal processing systems using both numeric and symbolic processing representations.
Develop and analyze new methods for algorithm-based fault tolerance.
Investigate novel algorithms based on emerging mathematical paradigms.

We will now describe each of these objectives and their associated activities briefly.

2. Activities and Accomplishments

2.1 Approximate Algorithms

In the area of approximate algorithms, a number of incremental refinement (IR) algorithms have been proposed for various DSP transforms. Specifically, an IR approach was developed for FFT-based Maximum Likelihood (ML) detection. We have also recently extended previous work on an IR approach to approximation of the Discrete Fourier Transform/Short Time Fourier Transform (STFT) by analyzing the probability of achieving a desired tradeoff between cost and quality for a given class of signals. We have also extended these algorithms to support mixed-radix signal representations, allowing a greater computational efficiency to be achieved in the IR context.

Our current activities in this area are directed to obtaining specific performance results for IR FFT-based ML detector on real sinusoids in noise, and considering techniques for reducing memory and hardware requirements for the IR two-dimensional Inverse Discrete Cosine Transform (IDCT) [3-5].

2.2 Low Power Signal Processing

In the area of low power design, we are investigating algorithmic and architectural approaches to reformulating algorithms to minimize power consumption. We have examined the tradeoffs between accuracy and power consumption and demonstrated low power implementations in FIR and IIR filters using adaptive approximate processing concepts. We have also investigated the links between "activity" and optimum ordering of filtering operations.

This work has resulted in new techniques that dynamically adjust filter order based on signal statistics, and demonstrate low power filter implementations. A Matlab-based simulation was also developed to evaluate transition activity of various ordering schemes.

Our future activities in this area include methods to quantify power reduction in IIR filter structures, and apply low power techniques to image coding. Extensions to adaptive wordlengths are also to be investigated. Tradeoffs between memory-based (lookup) and arithmetic-based signal processing will be evaluated from these viewpoints.

2.3 Numeric/Symbolic Signal Processing

In this area, we and our subcontractors at Boston University led by Professor Nawab, have investigated the design and implementation for a variety of DSP algorithms. The application of knowledge-based control to signal processing systems has been studied, resulting in a Integrated Processing and Understanding of Signals Architecture (IPUS) within existing design environments [6].

A number of new developments include upgrading our IPUS C++ platform to support full IPUS functionality. We have integrated this into the Ptolmey design environment from UC Berkeley to obtain an IPUS domain. A number of testbeds for clutter analysis have been implemented within Ptolemy, using the IPUS domain.

Our future activities in this area are to release the IPUS domain for Ptolemy in version v.0.6 in Summer 1996. We will also develop a support for heterogeneous simulation with the IPUS domain using Ptolemy's wormhole feature.

2.4 Algorithm-based Fault Tolerance

Researchers at the University of Illinois (Abraham et al, 1984) proposed algorithm-based fault tolerance (ABFT) to protect algorithms against faults using the following steps:

Step 1: Encode operands to introduce redundancy.

Step 2: Modify algorithms for encoded data.

Step 3: Check for and correct codes.

Step 4: Decode.

Our approach is based on the following steps:

Recognize algebraic structure in algorithms (e.g., groups, rings, vector spaces, semigroups and dynamical computational processes).
Encode by well-behaved algebraic mapping to larger algebraic set to introduce redundancy (Step 1 above).
Alegebraic structure then points to necessary modification of the algorithms (Step 2), error checking and correcting (Step 3), decoding (Step 4).
Extract hardware implementations.

A number of accomplishments include algebraic tools and methods for incorporating error detecting and correcting capabilities into nonlinear signal processing algorithms. We have also characterized all parity-type codes for fault-tolerant computations for certain algebraic structures, and included mechanisms to support ABFT in hardware, [8].

2.5 Emerging Mathematics for Signal Processing

In this area we have studied non-linear signal processing algorithms for the application of chaotic systems, soliton systems, and stochastic resonance systems and their implication in the development of DSP systems. This has also been directed at implementation aspects of next-generation wireless communications, a "spread-signature CDMA" system that combats strong multipath fading [1,2,5].

Our current work at the MIT RASSP group in this area includes developing fractal models for data traffic and the development of protocols for efficient traffic management. We will also continue to examine real-time DSP-based implementation of spread-signature CDMA systems for wireless applications, and explore the use of stochastic resonance systems in noise suppression [7].

3. Summary

Significant accomplishments in the areas listed above have been documented in technical reports, papers, and software releases as outlined in this article. Refer to the RASSP server for further information on the MIT Technology Base program.

4. Selected Publications

[1] K. Cuomo, A. Oppenheim, S. Strogatz, "Robustness and Signal Recovery in a Synchronized Chaotic System", International Journal of Bifurcation and Chaos, Vol. 4, No. 6, pp 1629-1638, 1993.

[2] E. Weinstein, A. Oppenheim, M. Feder “Iterative and Sequential Algorithms for Multisensor Signal Enhancement,” IEEE Trans. on Signal Processing, Vol 42, No. 4, April 1994.

[3] J. Winograd, S. H. Nawab, “Incremental Refinement of DFT and STFT Approximations,” IEEE Signal Processing Letters, February 1995.

[4] S. Nawab and E Dorken, “A Framework for Quality vs Efficiency Tradeoffs in STFT Analysis,” IEEE Trans. on Signal Processing, April 1995.

[5] G. Wornell, “Spread-Signature CDMA: Efficient Multiuser Communication in Presence of Fading,” IEEE Trans. on Information Theory, September 1995.

[6] J. Winograd, S. Nawab, “A C++ Software Environment for the Development of Embedded Signal Processing,” IEEE Intl. Conf. on Acoustics, Speech and Signal Processing, ICASSP-95, Detroit, 1995.

[7] J. Winograd, S. Nawab, A. Oppenheim, “FFT-based Incremental Refinement of Suboptimal Detection,” IEEE Intl. Conf. on Acoustics, Speech and Signal Processing, ICASSP-96, Atlanta, 1996.

[8] C.N. Hadjicostis and G.C. Verghese, “Fault-Tolerant Computation in Semigroups and Semirings,” submitted for journal review, 1996.

A. V. Oppenheim
DSP Group, RLE
MIT
Cambridge, MA 02139
avo@allegro.mit.edu

Newsletter Index

The RASSP Digest - Vol. 3, September 1996
newsletter/html/96sep/news_7.html