Proceedings Volume 0977

Real-Time Signal Processing XI

J. P. Letellier
cover
Proceedings Volume 0977

Real-Time Signal Processing XI

J. P. Letellier
View the digital version of this volume at SPIE Digital Libarary.

Volume Details

Date Published: 16 December 1989
Contents: 1 Sessions, 31 Papers, 0 Presentations
Conference: 32nd Annual International Technical Symposium on Optical and Optoelectronic Applied Science and Engineering 1988
Volume Number: 0977

Table of Contents

icon_mobile_dropdown

Table of Contents

All links to SPIE Proceedings will open in the SPIE Digital Library. external link icon
View Session icon_mobile_dropdown
  • All Papers
All Papers
icon_mobile_dropdown
Optical Symbolic Computing
John A. Neff
Experiments originating from Gestalt psychology have shown that representing information in a symbolic form provides a more effective means to understanding. Computer scientists have been struggling for the last two decades to determine how best to create, manipulate, and store collections of symbolic structures. In the past, much of this struggling led to software innovations because that was the path of least resistance. For example, the development of heuristics for organizing the searching through knowledge bases was much less expensive than building massively parallel machines that could search in parallel. That is now beginning to change with the emergence of parallel architectures which are showing the potential for handling symbolic structures. This paper will review the relationships between symbolic computing and parallel computing architectures, and will identify opportunities for optics to significantly impact the performance of such computing machines. Although neural networks are an exciting subset of massively parallel computing structures, this paper will not touch on this area since it is receiving a great deal of attention in the literature. That is, the concepts presented herein do not consider the distributed representation of knowledge.
Optically Controlled Fiber Optic Logic Arrays
T. Wang, M. Arshad, R. Arrathoon
A second generation of fiber optic based optoelectronic programmable logic arrays (OPLA's) is introduced. The relative merits of these devices is critically examined with respect to first generation OPLA technology. Specific applications are cited including a novel type of fiber optic based OPLA operating as an optically controlled crossbar switch. The concept of bit-slice reconfigurability with such a switch is discussed. System descriptions and system photographs are presented for two prototype bit-slice crossbar switches that have been constructed. A comparison of the capabilities of various categories of optical crossbar switches is presented.
Optical Clock Signal Distribution With Holographic Optical Elements
Raymond K. Kostuk, Lon Wang, Y-T. Huang
An overview of the problems in generating a synchronous clock signal for electrical very large scale integration (VLSI) and multi-processor systems is given. Alternative clocking schemes using optical distribution techniques are then presented and compared with the electrical methods. Issues related to holographic signal distribution are discussed in detail.
Optical Integrated Reconfigurable Interconnections For Real-Time Signal Processing
Tomasz Jannson, Freddie Lin
Physical Optics Corporation (POC) proposes a new type of highly reconfigurable optical interconnects. This will be accomplished as a hybridization of intergrated planar holo-graphic interconnects and fast addressing, based either on acousto-optic modulators or smectic-A liquid crystals. The basic novelty of POC's approach is in using permanent holograms instead of dynamic holograms (which are slow, expensive and exhibit low efficiency) but in which the reconfigurability is shifted to an electro-optic (or magneto-optic) addressing system. Thus, POC's approach can combine the superior interconnect-ability ruggedness, compactness, and efficiency of permanent planar Bragg holograms with the ruggedness and nanosecond responses time of the fastest optoelectronic addressing systems. POC's reconfigurable holographic interconnects will have the following superior features: A) High interconnectability and parallelity ( > 104-fan-out) B) Compactness, micro-electronic packaging compatibility C) Highly rugged, environmentally and mechanically stable D) Low insertion loss ( < 1db/channel) and low cross-talk ( < -20db), with diffraction efficiency up to 99% E) Fast accessing-switching time ( < lnsec., for acousto-optic modulators (AOMs) and, <20nsec, for smectic-A liquid crystals (LCs)) F) High throughput ( > 1011 channels/sec.) G) Low cost H) Flexible interconnect topology While the properties (A,B,C,D,E) are considered to be necessary conditions for the majority of real-time computing applications, the current state-of-the-art optical interconnects can never satisfy more than two of these requirements. Thus, the proposed interconnects go far beyond the state-of-the-art.
Discrete Steepest Descent Algorithms And Their Realization On Optical Analog Processors
Eugene Pochapsky, David Casasent
We consider an analog (linear) heterodyned linear algebraic optical processor for adaptive phased array radar (APAR). Its use in solving the discrete steepest descent (DSD) algorithm is considered. New stability and performance measure expressions are used (that relate the scenario and the processor's accuracy) and their verification is obtained by scenario tests. Extensions to more complex problems by terminating the number of iterations and by matrix preconditioning are discussed and demonstrated.
Optical AI Approach For Object Recognition Using Dempster-Shafer Theory Of Evidence
M. H. Hassan, P. Siy
The problem of object recognition in simple and complex images, where the information about the scene may be incomplete, uncertain, or imprecise, is addressed. The general outline of the proposed approach consists of four stages: (a) Preprocessing, to convert raw data into more usable intrinsic forms. (b) Segmentation, to find visually meaningful image objects perhaps corresponding to world objects or their parts. This processing is used to define a region in the image models by a set of attributes. The set of attributes represents the ordered set of vertices of the polygonal approximation of the region. Each vertex is defined by its internal angle and the lengths of segments around it. (c) Optical mapping, to find the appropriate representation of the image optically. (d) Optical understanding, to relate optically the image objects to the domain from which the image arose. As a step of this process the evidences related to each object with corresponding models are evaluated based on Dempster-Shafer theory of evidence. The approach could be implemented on optoelectronic processing unit using the fan-in and fan-out capabilities of fiber-optics system. Illustrative examples are provided where the approach yields excellent results in noisy images and images with overlapping objects.
Real-Time Signal And Image Thresholding Using Advanced Low-Pass Filtering
M. H. Hassan, P. Siy
Real-time signal and image processing techniques have recently gained popularity, due to its importance in many potential applications such as communications, robotic vision, military target detection, and part inspection. This paper presents a simple scheme for thresholding signals and grayscale images dynamically and in real-time. The scheme utilizes the transfer function of a simple low-pass filter and an advanced zero-order hold device where the input is the raw signal or the image' s grayscale values, and the output is the corresponding dynamic thresholds. The scheme features high reliability of the results and is effectively applicable for signals and images with different background illumination and different shape, such as noisy step signals, ramp signals, or their combination. Software and hardware experiments have confirmed the method' s viability.
Programmable Optical Processor For Associative Retrieval
Bahram Javidi, Souheil Odeh
A programmable optical associative memory for two-dimensional image retrieval is described. Both the stored image and the input image are displayed spatially; therefore, they can be updated in real time more conveniently. The integral product between the input image and the stored images is obtained by nonlinear correlation technique which has a superior performance compared with the conventional optical correlation techniques in the areas of the light efficiency and the correlation signal quality. Thus, better quality images can be reconstructed and the need for optical gain and the optical feedback may be eliminated. There are small losses in the system since no halograms are employed.
A New Architecture For 2-D Array Neural Nets With An Electro-Optical Implementation
Fathi M. A. Salam, Yiwen Wang
A new formulation for the processing of 2-D array images is introduced. The formulation is based on neural networks; consequently it possesses inherent fault-tolerance capabilities and exhibits impressive processing powers. The formulation essentially processes the 2-D input array to: (i) undergo two matrix multiplications, and then (ii) be processed via the usual thresholding and feedback which are characteristic of neural nets. Then an electro-optical implementation of our formulation is described. The implementation includes adaptations of the available incoherent optical techniques for the real-time multiplication of multiple matrices.
Algorithms And Architecture Constraints For A Class Of Real-Time Image Processing Problems
John A. Board Jr., Geoffrey A. Frank
Many important problems in real-time image processing involve both high computational requirements and a complex and substantial data flow. The system designer must weigh the difficulty of partitioning the problem to fit onto commercial hardware versus the expense of embedding the algorithm in an ASIC or an ASIC chip set subject to constraints on device and pin count, data path complexity, etc. A consistent system architecture evaluation methodology and tool set for addressing the implementation of such problems in a combination of software and hardware is sorely needed; this paper presents first steps in that direction. In order to demonstrate a typical set of trade-offs, we cite the pan-zoom-rotate (PZR) problem, i.e., the problem of processing an input scene for viewing at arbitrary translation, rotation, and magnification in real time. This problem requires both a very high computational rate and high image data bandwidth; sophisticated memory addressing and management are also needed, as access patterns to the input data are non-trivial. We are using the Architecture Design and Assessment System (ADAS) and a number of other tools to determine and model the computational and data flow constraints of this problem and to experiment with different partitioning strategies for the algorithms. We describe the methods we have used to determine these constraints, why these constraints rule out implementation via commercial DSP chips, and how our architecture assessment tools have been used to develop candidate, highly pipelined ASIC architectures with sophisticated internal data buffering which meet these constraints.
Algorithm-Based Error Detection Of A Cholesky Factor Updating Systolic Array Using Cordic Processors
S. I. Chou, Charles M. Rader
Lincoln Laboratory has developed an architecture for a folded linear systolic array using fixed-point CORDIC processors, applicable to adaptive nulling for a radar sidelobe canceler. The algorithm implemented uses triangularization by Givens rotations to solve a least-squares problem in the voltage domain. In this paper, the implementation of an inexpensive algorithm-based error-detection scheme is proposed for this systolic array. Column average checksum encoding is intended to detect most errors caused by the failure of any single arithmetic unit. It retains or almost retains the 100% processor utilization of Lincoln Laboratory's novel design. For the case of 64 degrees of freedom, the increase in time complexity is only 3%. The increase in hardware is mainly two adders and two comparators per CORDIC processor. We believe that the small increase in cost will be amply offset by the improvement in system performance brought about by this error detection.
Symbolic And Numeric Real-Time Signal Processing
John S. Baras
We consider real-time sequential detection and estima-tion problems for non-gaussian signal and noise models. We develop optimal algorithms and several architectures for real-time implementation based on numerical algorithms, including asynchronous implementations of multigrid algorithms. These implementations are of high complexity, costly and cannot easily accomodate model variability. We then propose and analyze a different class of algorithms, which are symbolic, of the neural network type. The preliminary results presented here demonstrate that these algorithms have remarkably lower complexity and cost, work well under model variability and their performance is nearly optimal. We also discuss how these type of algorithms are incorporated in the DELPHI system for integrated design of signal processing systems.
The Video Analysis Transputer Array (VATA)
Jerome J. Symanski, Keith Bromley, Thomas Henderson
This paper presents (a) an overview of the Inmos transputer and its use in parallel arrays for image processing, (b) a functional block level description of IBM-AT-compatible boards for signal/image processing research using transputers with reconfigurable interconnection topologies, and (c) an overview of the OCCAM and C programming tools for placing parallel algorithms onto such a processor. The hard-ware consists of two custom printed-circuit boards (and two commercially available boards) within an IBM AT host. The first provides a flexible input/output interface between a general-purpose high-speed input-data bus and the transputer array. The second contains 32 transputers and 4 programmable crossbar-switch interconnection chips. Several copies of the second board can be cascaded (or even partially-unpopulated) to provide for an arbitrary number of transputer chips. Each one of these boards will perform about 128 million Whetstones or, for highly regular algorithms, a sustained 48 MFLOPS.
The Domain Parallel Computation Model On Warp
P. S. Tseng, Monica Lam, H. T. Kung
This paper introduces a new computation model for distributed memory multiprocessor systems: the domain parallel computation model. This computation model does not depend on a specific communication mechanism, thus making a domain parallel program portable among different parallel and sequential machines. Based on the domain computation model, a programming language called AL was defined and its compiler was implemented for the Warp systolic computer, a linear array of 10 processors. AL has been successfully used as a programming tool for scientific computing on Warp. Examples of LU decomposition, QR decomposition, and singular value decomposition (S VD) were given in this paper to illustrate the use of AL in applications. These AL procedures were rewritten from the LINPACK FORTRAN programs; their algorithms and numerical properties were kept the same as the UNPACK implementations. More than 27 MFLOPS (out of 100 MFLOPS peak) on matrices of order 300 were achieved for these procedures.
Multiple Signal Classification (MUSIC) Algorithm Hosted On The High Speed Systolic Array Processor (HISSAP)
Joseph P. Loughlin
A direction of arrival estimator based on the MUSIC algorithm hosted on a microprogrammed systolic array processor testbed system will be presented. The mapping approach is discussed and the major parts of the algorithm demonstration application are identified. The impact of manipulating complex sample data within the MUSIC algorithm is also discussed. The use of parallel programming tools custom built to translate, debug and evaluate systolically hosted signal processing algorithms will be described.
Sample Estimators For Entropic Measures Of Mutual Information
R. C. McCarty
A nonlinear, entropic measure of mutual information (statistical dependence), I(X1,...,Xnin ≥ 2) = ∫-∞+∞...∫-∞+∞log [(f(x1,...xn)/(Πf1(x1))]dF(x1,...,xn)≥0 was proposed in 1966 by Blachman for a set of continuous random variables, (X1,..., X,ni-∞ < Xt < +∞, i= 1,..., n; ≥ 2) with continuous distribution F(xi,...,xn).
Arrays For Partitioned Matrix Algorithms: Tradeoffs Between Cell Storage And Cell Bandwidth
Jaime H. Moreno, Tomas Lang
A graph-based partitioning method for designing systolic arrays for matrix computations is extended to apply it to processing elements with a small local memory. The introduction of this memory produces a reduction in the cell communication bandwidth and facilitates the use of pipelining within cells. As a consequence, efficient arrays can be designed using the extended method combined with technological parameters that define the ratio between processor speed and communication bandwidth. The extended partitioning method also allows evaluating tradeoffs between linear and two-dimensional arrays. We illustrate the method using a cube-shaped canonical algorithm, which is communication and computation intensive, and triangularization by Givens' rotations.
Back Propagation On Warp
George L. Gusciora
We describe two fast back-propagation algorithms for a linear array of processors. Results of the implementation of both algorithms on Warp, a ten processor, programmable systolic array computer, are reviewed and compared with back-propagation implementations on other machines. Our fastest Warp simulator is about 11 times faster at simulating the NETtaik text-to-speech network than the fastest back-propagation simulator previously reported in the literature. This fast simulator on Warp is being used routinely in autonomous navigation experiments, image processing experiments and speech recognition experiments at Carnegie Mellon. Our results indicate that linear systolic array machines can be efficient neural network simulators.
Data Parallelism And The Processor Farm Model For Image Processing And Synthesis On A Transputer Array
Peter M. Dew, Han Wang
Computational models have been introduced by Kung as a technique for specifying the usage patterns for parallel architectures. The purpose of this paper is to consider the processor farm for applications that are amenable to data parallelism and show its relationship to the computational models. The processor farm is a general abstract machine model for VLSI processor arrays based on the Communicating Sequential Processing (CSP) model of computation and is widely used to program networks of INMOS transputers. The paper reports on recent work at Leeds applying the processor farm to a range of image processing and synthesis computations.
Application-Specific Super Computer
Raymond J. Lackey, Herbert F. Baurle, John Barile
Super Computer processing levels will be necessary to implement real time functions in radar and communication systems. Design and fabrication of such systems require innovative approaches in addressing the problem rather than the normal methods of solution. The mathematical solution to multiple simultaneous equations is the optimum solution in many signal processing problems in radar and communications. Historically this optimum solution was not directly possible, so approximations were derived through various signal processing techniques. The advent of high-speed digital processing devices in concurrent processing architectures has raised the possibility of achieving the optimum solution. This mathematical solution is applicable to many adaptive signal processing problems including spatial, spectral, temporal, and moving target indication filtering. Hazeltine, under contract with RADC on the Systolic Array Processor Brassboard program, has built a processor solving this class of problems in a highly concurrent systolic processing architecture. The application-specific processor built on this program performs over 1.25 billion floating point operations per second (BFLOPS), solving equations with up to twelve complex variables.
Fast Mapping Of A Kalman Filter On Warp
David R. O'Hallaron, Radhakisan S. Baheti
A parallel algorithm for solving an n-state Kalman filter on an (n+2)-cell linear array is described. The algorithm is the basis for the mapping of a 9-state target tracking filter on the Warp computer. The Warp implementation is written in a high-level language and achieves a measured speedup of almost 300 over the same filter running on a Sun workstation.
Canonical Correlations And Generalized SVD: Applications And New Algorithms
L. Magnus Ewerbring, Franklin T. Luk
In this paper we consider canonical correlations and a generalization of the singular value decomposition (SVD) that involves three matrices. We show how the two matrix problems are related and how they can be used in important applications such as weighted least squares and optimal prediction. We present two new computational procedures for the problems based on implicit SVD methods for triple matrix products. Our algorithms are well suited for parallel implementation.
A Two-Dimensional Processor Array For Wavefront Reconstruction
P. Johnson, G. Newman, L. Haynes, et al.
Current and future adaptive optical systems that utilize deformable or segmented mirrors as the adaptive element may require that matrix calculations be performed on a real time basis to keep the mirror properly figured. A two-dimensional array of processor nodes (the "Solver") has been developed that is capable of computing the required positions of several hundred to several thousand mirror actuator elements in a real time environment. The processor has been demonstrated as a two-board system capable of performing 3.4 x 109 integer operations per second, and with input/output (I/O) bandwidth of 200 Mbytes/sec. The architecture is well suited to matrix algebra and iterative type operations and is scalable to larger computational rates. System costs have been kept low and software tools have been developed to ease the implementation of algorithms. This work has been performed under contract with the Office of Naval Research, and the authors thank them for their support.
Real-Time Signal Processing By Markovian Random Walk Approach
Yung-Lung Ma, Tsing-Yee Tu, Chialo Ma
A moving object recognition approach is presented in this paper. The motion of an object includes the linear or nonlinear translation and rotation. For a 3-D object, the images taken by a camera are in planar form. They are varied by different distances between camera and the object, variant angles and timing for taking. pictures. However, the change rate among these images taken at different instant are logically related. The brightness level between any two neighbour string cells of machine digital scanning raster varies according to the Markovian random walk process. Thus, the direction and position of a moving object can be found by the variations of the cell random walk. The angles between a machine digital scanning raster and the edges of an object in a planar image are called pseudo-refractional angles. The variations of angles can be used as features for object recognition. Together with the Kolmogorov complexity program, the probability function of the process can be changed into a finite length of string arrays to simplify the recognition procedure. The distance between camera and the object can be measured by a radar or supersonic signal for military or industrial applications.
Realtime Processors For Optical Networks
John F. Dove
This paper discusses the design, component, and performance requirements for successful fabrication and demonstration of a high-speed (gigabits/sec) optical communication network. The successes and problems encountered during design and fabrication of such a network will also be discussed, and future needs in materials, components, and devices for higher throughput systems will be delineated (Table 1).
Optical Laboratory Solution And Error Model Simulation Of A Linear Time-Varying Finite Element Equation
B. K. Taylor, D. P. Casasent
We detail the use of simplified error models to accurately simulate and evaluate the performance of an optical linear algebra processor. The optical architecture used to perform banded matrix-vector products is reviewed along with the linear dynamic finite element case study. The laboratory hardware and AC-modulation technique used are presented. The individual processor error source models and their simulator implementation are detailed. Several significant simplifications are introduced to ease the computational requirements and complexity of the simulations. The error models are verified with a laboratory implementation of the processor, and are used to evaluate its potential performance.
Optical Dynamic Matched Filtering With Electron Trapping Devices
Alastair D. McAulay, Junqing Wang, Chen-Tai Ma
A new electron trapping material is described together with a preliminary characterization. The material is used for correlation in the space domain between many stored images and an incoming image. As the material may be written and read it is possible to store the images against which the input is to be matched on film and then to map these one at a time onto the material for correlation. It would be useful if the material could be used for matched filtering in the frequency domain because this provides shift invariance. The difficulty of having different frequencies for read and write is shown to be unimportant. However, present samples cannot be used in the frequency because of scattering.
Fiber Optic Signal Processors For High-Speed Code Generation
A. P. Goutzoulis, D. K. Davies
We have been exploring the use of fiber optics for the application of very high speed (>>1 Gbit/s) binary code generation. In this paper we present our initial results which involve fiber optic generators based on time-multiplexing and fiber optic analogues of electronic digital PN shift register-based generators where the XOR operation is accomplished via a pair of laser diodes connected back-to-back. Experimental results of a 500 Mbit/s (RZ) 32 laser diode prototype and a 3.85 Gbit/s (RZ) 4 diode system are presented along with experimental results of a laser diode-based XOR prototype.
Digital Optical Arithmetic Processor Based On Symbolic Substitution
Ho-In Jeon, Mustafa A. G. Abushagur, Han-Kyu Park
In this paper, we propose a digital optical arithmetic processor design based on symbolic substitution using holographic matched and space-invariant filters. The proposed system performs Boolean logic, binary addition and subtraction in a highly parallel manner, i.e., the processing time depends on the word size but not on the array size. A skew problem occuring when symbolic substitution is applied to binary addition and subtraction with space-invariant systems is addressed and its solution is suggested. Crosstalk in symbolic substitution is described and new symbols which can prevent the crosstalk are introduced. System analysis and fundamental limitations of the proposed system are also presented.
CCD Focal Plane Array Analog Image Processor
E-S. Eid, E. R. Fossum
A focal plane array designed for real-time, general-purpose, image preprocessing is described. The analog charge-coupled device-based array operates in the charge domain and has sensing, storing, and computing capabilities. It captures the image data and performs local neighborhood operations. The array is digitally programmable and various image preprocessing tasks can be implemented. It uses a single instruction, multiple data parallel architecture with one processing element serving four pixels. It can be programmed to perform A/D conversion prior to output. The ultra-compact image processor is currently being fabricated with a 3-um, double-poly, double-metal process. The 48 X 48 pixel array is projected to achieve an internal throughput as high as 576 Mops with a 54 dB dynamic range (9-bit equivalent accuracy) and 180 um detector pitch. The total power dissipation is estimated to be 12 mW or less. The total size of the 59-pad chip is 9.4 X 9.4 mm2.
Analysis Of Nonlinear Optical Correlation
Bahram Javidi
A nonlinear joint transform image correlator is investigated. The Fourier transform interference intensity is thresholded to provide higher correlation peak intensity and better defined correlation spot. Analytical expressions for the thresholded joint power spectrum is provided. The effects of the nonlinearity at the Fourier plane on the correlation signals at the output plane is investigated. The correlation signals are determined in terms of the nonlinear characteristics of the spatial light modulator (SLM) at the Fourier plane. We show that thresholding the interference intensity results in a sum of infinite harmonic terms. Each harmonic term is envelope modulated due to the nonlinear characteristics of the device, and phase modulated by m times the phase modulation of the nonthresholded joint power spectrum. The correct phase information about the correlation signal is recovered for the first order harmonic of the thresholded interference intensity. We show that various types of correlation signals can be produced simply by varying the severity of the nonlinearity and without the need to synthesize the specific matched filter. For example, a phase-only correlation signal is produced by selecting the appropriate nonlinearity.