A mathematical approach to image analysis and synthesis in the combined frequency-position space is presented. The formalism is based on the Zak (1967) transform, which provides one of the most fundamental tools for studies of nonstationary processes and images as such. Algorithms suitable for computation of Gabor (1946) expansion coefficients are presented and compared with regard to stability and computational complexity.>

The finite Zak transform is introduced into the problem of signal detection in a noisy environment. The main advantage of the Zak transform over the Wigner distribution approach is the linearity. Thus there are no cross terms in a multicomponent signal environment. The theory has been applied to separate chirp signals.>

Tools are presented for the extension of the Cooley-Tukey (1965) and Pease (1968) fast Fourier transform algorithms to arbitrary dimensions in a compact Kroenecker product formulation. Several variations of the vector radix algorithm (VRA) are presented using this formulation, and an algorithm suitable for spatial concurrency is derived. The tools presented are the multidimensional stride and partitioning permutations together with the multidimensional lower-ordered transforms. The concepts of partitioning permutation and multidimensional perfect shuffle permutations are studied. The first enables one to apply a divide-and-conquer strategy used in Cooley-Tukey algorithms to multidimensions and the second defines algorithm data flow in a lattice.>

A mathematical approach to image analysis and synthesis in the combined frequency- position space is presented. The formalism is based on the Weil map - Zak transform, which provides one of the most fundamental tools for studies of nonstationary processes and images as such. Algorithms suitable for computation of Gabor expansion coefficients are presented.

A parallel algorithm is proposed for the two-dimensional discrete Fourier transform (2-D DFT) computation which eliminates interprocessor communications and uses only O(N) processors. The mapping of the algorithm onto architectures with broadcast and report capabilities is discussed. Expressions are obtained for estimating the speed performance on these machines as a function of the size N*N of the 2-D DFT, the bandwidth of the communications channel, the time for an addition, the time T(F/sub N/) for a single processing element to perform an N-point DFT, and the degree of parallelism. For single I/O channel machines that are capable of exploiting the full degree of parallelism of the algorithm, attainable execution times are as low as the time T(F/sub N/) plus the I/O time for data upload and download. An implementation on a binary tree computer is discussed.>

The problem of optimal scheduling of a job system for two dedicated processors is presented. A machine model with two functional units which can be either sequential or pipelined is considered. The complexity of optimal scheduling for a set of expressions on such machines is investigated. Some previous NP-completeness results are reviewed and several new ones are presented. For one restricted case, a polynomial-time algorithm is described and analyzed.>

Consider a pipelined machine that can issue instructions every machine cycle. Sometimes, an instruction that uses the result of the instruction preceding it in a pipe must be delayed to ensure that a program computes a right value. We assume that issuing of such instructions is delayed by at most one machine cycle. For such a machine model, given an unbounded number of machine registers and memory locations, an algorithm to find a shortest schedule of the given expression is presented and analyzed. The proposed algorithm is a modification of Coffman-Graham's algorithm [7], which provides an optimal solution to the problem of scheduling tasks on two parallel processors.

The authors propose and discuss hybrid VLSI architectures for implementing the Wigner distribution in any dimension. Two contributions are made to the analysis of pipelined architectures for digital signal processing. The first is in introducing the notion of asymptotic area efficiency which in addition to AT/sup 2/ is used as another focal point in the analyses. The second is in presenting a basic design methodology for pipelining arrays under construction of I/O bandwidth by matching their data rate ratios. Well-matched arrays yield good area-time performance with high efficiency. The pipeline methodology forms the basis for new architectures by a systematic construction from arrays that compute subproblems. The authors systematically search for an optimal structure for computing the Wigner distribution in any dimension from arrays that compute subproblems and (static) permutation networks. The pipelining technique yields several structures of which the optimal designs in the sense of AT/sup 2/ and area efficiency are extracted.>

It is often desirable in modern signal processing applications to perform two-dimensional or three-dimensional Fourier transforms. Until the advent of VLSI it was not possible to think about one chip implementation of such processes. In this paper several methods for implementing the multidimensional Fourier transform together with the VLSI computational model are reviewed and discussed. We show that the lower bound for the computation of the multidimensional transform is O(n2log2n). Existing nonoptimal architectures suitable for implementing the 2-D transform, the RAM array transposer, mesh connected systolic array, and the linear systolic matrix vector multiplier are discussed for area time tradeoff. For achieving a higher degree of concurrency we suggest the use of rotators for permutation of data. With ``hybrid designs'' comprised of a rotator and one-dimensional arrays which compute the one-dimensional Fourier transform we propose two methods for implementation of multidimensional Fourier transform. One design uses the perfect shuffle for rotations and achieves an AT2pof O(n2log2n· log2N). An optimal architecture for calculation of multidimensional Fourier transform is proposed in this paper. It is based on arrays of processors computing one-dimensional Fourier transforms and a rotation network or rotation array. This architecture realizes the AT2plower bound for the multidimensional FT processing.

A new technique is proposed for analyzing models of (paged) virtual memory management This technique, which is based on recent developments in the theory of optimal control, permits the use of a very general model of program behavior.In contrast to existmg studies of program behawor, staUstically confined to Markov models, a general jump stochastic process is used here to describe the page reference generator A model of memory management is formally defmed as three component processes: the program behavior, the memory allocation, and the control process.Equations linking the evolution of the memory allocation process with the other two processes are derived.Necessary and sufficient conditions for an optimal control policy are given as a set of optunality equations.Although these equaUons can be numerically solved for small s~ze problems, an analyUc solution is presented for the case of stationary ranking of pages.The equations of motion of the memory allocation process are used m apphcations where the performance of a given control pohcy is to be assessed for specified program behavior Another use of the proposed technique is the formulation of a Markov phase behavior model The hfetime function calculated in this model is shown to be m good agreement with empirical results.

A lower bound on the mean square error for an estimate of unknown parameter is derived for the case where the observation noise is a martingale with jump discontinuities.