This paper describes a highly parallel system of computational processors specialized for real-time adaptive antenna nulling computations with many degrees of freedom, which the author calls MUSE, and a specific realization of MUSE for 64 degrees of freedom. Each processor uses the CORDIC algorithm and has been designed as a single integrated circuit. Ninety-six such processors working together can update the 64-element nulling weights based on 300 new observations in only 6.7 milliseconds. This is equivalent to 2.88 Giga-ops for a conventional processor. The computations are accurate enough to support 50 dB of S/N improvement in a sidelobe canceller. The connectivity between processors is quite simple and permits MUSE to be realized on a single large wafer, using restructurable VLSI. The complete design of such a wafer is described.>

A wafer-scale VLSI system is being built to determine the weights for an adaptive antenna application. The data are sampled N-component vector time series X(n), with components that are time functions observed at N individual antenna ports. The processed output, y(n), is a weighted sum of the components, e.g. W/sup t/X(n). In practice, the author expects to computer W a few hundred times per second, based on observations of many exponentially windowed samples of X which arrive two-orders-of-magnitude more frequently. The algorithm used for determining W is based on the use of Givens transformations to rotate the original data into a lower triangular matrix, after which the desired weights are the solution to a triangular set of linear equations. The computational cost of this algorithm (and of almost all other algorithms which find the optimum weights) increases with N, the number of degrees of freedom, as N/sup 3/, so for sufficiently large N, some degree of parallelism must be used. An advanced architecture which uses N/2 processors connected in a linear chain, suitable for realizing this algorithm for N=64 in a systolic VLSI wafer-scale design, is described.>

A class of transformation matrices, analogous to the Householder matrices, is developed with a non-orthogonal property designed to permit the efficient deletion of data from least squares problems. These matrices, which we term hyperbolic Householder, are shown to effect deletion, or simultaneous addition and deletion, of data with much less sensitivity to rounding errors than exists for techniques based on normal equations. When the addition/deletion sets are large, this numerical robustness is obtained at the expense of only a modest increase in computations, but if a relatively small fraction of the data set is modified, there is a reduction in required computations.

Dynamic Programming has been applied to a number of digital signal processing problems. In this paper we discuss its well known application to the problem of determining the optimum order of sections in a digital filter realization. We show that the method is quite insensitive to the specific details of the problem; it is applicable over a wide range of possible optimality criteria, various kinds of arithmetic, scaling options, etc. This is characteristic of the application of dynamic programming to many signal processing problems. Also, since a problem, to be solved by dynamic programming, must be represented as the traversal of a directed graph, we usually discover unsuspected structure in the problem when we attempt to solve it using dynamic programming. Quite often it is necessary to recognize this structure in order to solve the problem efficiently. In the case of ordering of filter sections the structure leads to an efficient utilization of memory.

Management of the memory contents in a Viterbi decoder is a major design problem for both hardware and software realizations. In a naive implementation, every bit in the memory must be changed (read, modified, and rewritten) for each message bit decoded, and, in addition, some double buffering is required. An especially annoying feature is the need to read and rewrite long words, forty bits in a typical case. In this note we describe a memory organization which overcomes these problems. The techniques described here are not novel, but neither are they widely known.

A transform analogous to the discrete Fourier transform is defined in the ring of integers with a multiplication and addition modulo a Mersenne number. The arithmetic necessary to perform the transform requires only additions and circular shifts of the bits in a word. The inverse transform is similar. It is shown that the product of the transforms of two sequences is congruent to the transform of their circular convolution. Therefore, a method of computing circular convolutions without quantization error and with only very few multiplications is revealed.

This paper contains a description of the architecture of the fast digital processor (FDP), a general purpose digital attachment to a UNIVAC 1219 computer facility. The main purpose of the FDP is to enhance the capability of the UNIVAC facility for performance of digital signal processing operations such as digital filtering and discrete Fourier transforms. The structural design evolved during a series of discussions among the four authors. The FDP is presently being constructed under the supervision of one of the authors, P. McHugh, and should be completed in late 1970.