The study of axon tracts is important in neurophysiology. In this paper, we study axon tracts with arbitrary geometry and present a governing equation for ephaptic coupling among the constituent axons. We derive this equation and simulate it, obtaining a novel, geometry-dependent, delayed coupling phenomenon. This has relevance for how an axon tract communicates data in a neurological network.

A lower bound to the expected decoding time of a power constrained continuous time additive white Gaussian noise channel with perfect feedback is studied. The main assumption is of right continuity of sample paths for all processes and a Nack-continuity assumption on the Encoder. We also employ a conjecture for the continuous time case.

In this paper, we consider the design of a scheduling algorithm for downlink multiuser systems with a finite-buffer traffic model to reduce average packet delay, while maintaining the stability condition of the networks. We propose a new Buffer-Aware Adaptive (BAA) scheduler which considers both channel state and buffer conditions for resource allocation. The generalized form of the proposed algorithm is also established. Stability considerations of the proposed algorithm are provided, along with the average throughput lower bound and approximation. Both single-link and system-level simulation results demonstrate that the proposed scheduler appears to outperform existing scheduling algorithms in terms of average packet delay.

In this paper, we study the adaptive rate transmission with opportunistic scheduling in two-hop relaying networks, in which only channel state information (CSI) at receivers are available. Previous work [5] that proposed an opportunistic relaying scheme has focused on the fixed rate transmission. We develop an adaptive rate transmission scheme according to instantaneous channel connections. The scheme operates with cooperative relays and opportunistic scheduling for adaptive rate transmission, to improve the throughput performance. We obtain the exact throughput expression and we show that the advantage using adaptive rate transmission over fixed rate transmission is the multiplicative factor of log log n, where n is the number of users. Furthermore, we prove that the throughput achieved by the adaptive rate transmission scheme is actually the optimal throughput for two-hop relaying networks. Numerical results are presented, indicating the alignment with our theoretical analysis.

In this paper, we study the delay/throughput trade- off with opportunistic relaying over channels with random connections, in which the channel connections are independent and identically distributed (i.i.d.). Previous work which proposed an opportunistic relaying scheme has focused on the throughput analysis only, we show that the opportunistic relaying scheme provides an upper bound of O(n) delay, including full effects of queueing in the network model. In addition, we use the redundant scheduling algorithm to reduce the upper bound of delay scaling to O(n/√(log n)). Furthermore, we prove two key inequalities that capture the various tradeoffs inherent in the broad class of opportunistic relaying protocols, which indicate the tradeoff of delay/throughput ≥ O(n/log n), illustrating that no scheduling and routing algorithm can simultaneously yield lower delay and higher throughput.

In this paper we consider the energy-efficient resource allocation that minimizes a general cost function of average user powers for small- or medium-scale wireless sensor networks, where the simple time-division multiple-access (TDMA) is adopted as the multiple access scheme. A class of so-called ß-fair cost functions is derived to balance the tradeoff between efficiency and fairness in energy-efficient designs. Based on such cost functions, optimal channel-adaptive resource allocation schemes are developed for both single-hop and multihop TDMA sensor networks. Relying on stochastic optimization tools, we further develop stochastic resource allocation schemes which are capable of dynamically learning the intended wireless channels and converging to the optimal benchmark without a priori knowledge of channel fading distribution function.

In this paper, we consider the energy-efficient resource allocation that minimizes a general cost function of average user powers in wireless networks. A class of so-called ß-fair cost functions is derived to balance the tradeoff between efficiency and fairness in energy-efficient designs. With these novel cost functions, optimal resource allocation schemes are developed for fading time-division multiple-access (TDMA) channels. Relying on stochastic approximation tools, we further develop the corresponding stochastic schemes which are capable of dynamically learning the intended wireless channels and converging to the optimal benchmark without a priori knowledge of fading distribution function.

This paper describes a multi-resolution pyramidal Gabor-eigenface (PGE) algorithm for face recognition. The PGE algorithm employs the eigenface method on the desirable Gabor facial features, which derive from the multi-resolution pyramidal Gabor wavelet (PGW) transform of face images in the spatial domain directly without a Fourier implementation. The use of eigenface method further reduces the redundancy of the images from PGW. The feasibility of the PGE algorithm has been successfully tested on face recognition using AT&T (formally Olivetti) face databases, which contain 400 face images of 40 subjects with variation in poses, facial expression, different viewing direction, and disguises. The effectiveness of the PGE algorithm is shown in terms of better accuracy, faster computational speed and much less computer memory amount.

The objective of this study is to apply and investigate a neural network-based decision feedback scheme for interference suppression in direct sequence code division multiple access (DS-CDMA) wireless networks. It is demonstrated that a decision feedback functional link equalizer (DFFLE) in combination with an eigenvector network can closely approximate a Bayesian receiver with significant advantages, such as improved bit-error ratio (BER) performance, adaptive operation, and single-user detection in a multiuser environment. It is assumed that the spreading codes of the interfering users will be unknown to the receiver. This detector configuration is appropriate for downlink communication between a base station and a mobile user in a digital wireless network. The BER performance in the presence of interfering users is evaluated. The improved performance of such a DFFLE receiver for CDMA is attributed to the nonlinear decision boundary it evaluates for the desired user. The receiver structure is also capable of rapid adaptation in a dynamic communications scenario for which there is entry/exit of users and imperfect power control. The convergence performance and error propagation of the DFFLE receiver are also considered and exhibit reasonable promise for third generation wireless DS-CDMA networks.

A novel multiple access scheme, referred to as cooperative code division multiple access (CCDMA), is analysed over a AWGN channel. Such a scheme appears to significantly increase the system capacity compared to that of current CDMA systems. This capacity increase is due to the multiple access coding scheme employed. A comprehensive analysis of a cellular wireless network uplink CCDMA architecture employing two-user asynchronous uniquely decodable (ASUD) codes and over an AWGN channel is presented. A noncoherent reception technique ensures that the CCDMA architecture is practical from an uplink synchronization standpoint. Preliminary BER and system capacity assessments are carried out and initial simulation results are presented.

The objective of this study is to characterize the multiple-access interference in a DS-CDMA integrated voice/data wireless network. The system model is designed to accommodate bursty packet-based data services in addition to stream-based services on a shared spectrum basis. A common packet data channel (CPDC) is employed to transport bursty data services, Consequently, this study incorporates features associated with packet-based services, such as higher transmitter power, short inter-arrival times, and short service time durations, as well as features associated with stream-based services, in order to provide a complete interference characterization. The results of a detailed and precise simulation study are presented in which the influence of traffic burstiness, voice activity, spatial distribution of mobiles, and transmitter powers on the fluctuation of the interference and signal-to-interference ratio (SIR) is assessed. The results obtained also quantify the impact of interference caused by CPDC services on stream-based services. The interference and SIR statistics are evaluated in terms of cumulative distribution functions. Since a DS-CDMA network is interference limited, studies of this type are essential for system design, capacity evaluation, and bandwidth management.

A common packet data channel (CPDC) architecture is proposed to support bursty, packet-based services in direct sequence code-division multiple-access (DS-CDMA) integrated wireless access networks. The architecture employs an asynchronous transfer mode (ATM) strategy in the forward CPDC link and a spread ALOHA-type random access strategy in the reverse CPDC link. A congestion control algorithm using base station broadcast and portable terminal random delay call reattempt is described. A performance analysis of the CPDC architecture and algorithms is carried out, and formulas for the bit error rate, blocking probability, system delay time, transmission time, and waiting time for packet data calls are derived. The interference caused by a CPDC to stream services in the network is determined, and the capacity of a CPDC is evaluated in terms of the number of packet data subscribers that can be served with a specified grade of service (GOS).

A common packet data channel (CPDC) architecture is proposed to support bursty, packet-based services in DS-CDMA integrated wireless access networks. The architecture employs a TDMA strategy in the CPDC downlink and a spread ALOHA-type random access strategy in the CPDC uplink. A congestion control algorithm using base station broadcast and portable terminal random delay call reattempt is described. A performance analysis of the CPDC architecture and algorithms is carried out, and formulae for the bit error rate, blocking probability, system delay time, and waiting time for packet data calls are derived. The capacity of a CPDC is evaluated in terms of the number of packet data subscribers that can be served with a specified grade of service (GOS).

Noisy pattern matching problems arise in many areas, e.g., computational vision, robotics, guidance and control, stereophotogrammetry, astronomy, genetics, and high-energy physics. Least-squares pattern matching over the Euclidean space E/sup n/ for unordered sets of cardinalities p and q is commonly formulated as a combinatorial optimization problem having complexity p(p-1)/spl middot//spl middot//spl middot/(p-q+1), q/spl les/p. Since p and q may be 10/sup 3/ or larger in typical applications, less than satisfactory suboptimal methods are usually employed. A hybrid approach is described for solving the pattern matching problem under rigid motion constraints, which often apply. The method reduces the complexity to l/sub 21//spl middot/n/sup 4/+l/sub 12//spl middot/p/sup 3/, where l/sub 12/ and l/sub 21/ are the number of iterations required by steepest-ascent and singular value decomposition (SVD)-based procedures, respectively.>

The throughput efficiency and probability of undetected error of automatic-repeat-request (ARQ) protocols employing slow frequency hopping over Gilbert-Elliott (1960, 1963) fading channels are investigated. Throughput efficiency formulas for the three basic ARQ schemes, "stop-and-wait" (SW), "go-back-N" (GBN), and "selective-repeat" (SR), are obtained, and the improvement in throughput efficiency due to slow frequency hopping is examined. Results are also presented on the problem of determining the number of carriers used for frequency hopping so as to minimize the effect of fading channel memory and, therefore, optimize system performance. This work has application to TDMA architectures and packet data services for third generation wireless networks, where projected data service requirements call for error rates on the order of 10/sup -9/, and the multiple service, multiple access environment demands that the delay for any service be minimized.>

Results and observations gathered while implementing the ANSI T1M1.5 GNM-T1.214 standard within an object-oriented database management system (ODBMS) framework are discussed. The generic network model (GNM) proposes a dynamic network modeling methodology that encompasses a wide spectrum of managed telecommunication network resources. Within the GNM, managed telecommunication resources are modeled from building blocks of lower-level resource elements (logical or physical). The complex relationships between GNM resource elements are described either by specialization/generalization or user/containment; therefore, an ODBMS is well suited for implementation of the GNM as compared to conventional database management systems. The ODBMS framework described also allows the database model to evolve with the GNM. It is demonstrated that a proposed refinement of the GNM into subclasses results in a functional database design that can model a large variety of network resources in accord with a standardized network view.>

The generalized type-II hybrid automatic repeat request (ARQ) scheme on Markov channels is examined in order to study the effect of feedback channel errors on the performance of ARQ systems. It is shown that it is possible to derive expressions for certain critical performance parameters, such as the throughput efficiency, the probabilities of packet loss, undetected error, and correct delivery. To provide a means of comparison, a parallel set of expressions is provided under the usual assumption of an error-free feedback channel. By use of simulations, the ARQ system performance is examined under noiseless feedback and noisy feedback. It is found that feedback channel noise can result in the loss of packets, an increase in the number of undetected errors, and the occurrence of unnecessary transmissions. To enhance the performance of the GH-II ARQ scheme, a predictor is used and found to lower the probability of undetected error, reduce the number of unnecessary transmissions, and increase the throughput efficiency. >

Least-squares pattern matching over the Euclidean space E/sup n/ for unordered sets of cardinality p is commonly formulated as a combinatorial optimization problem having complexity p times p!, p>>n. Since p may be 10/sup 3/ or larger in typical applications, less than satisfactory suboptimal methods are usually used. A powerful hybrid approach is described which casts the pattern matching problem in a differentiable setting using rigid motion constraints which often apply and reduces the complexity to l/sub 21/n/sup 4/+l/sub 12/p/sup 3/, where l/sub 12/ and l/sub 21/ are the number of iterations required by procedures based on steepest ascent and singular value decomposition (SVD), respectively.>

An attempt is made to formalize both structured covariance estimation and autoregressive process parameter estimation in terms of the underlying abstract Jordan algebra, an algebra that differs from the usual noncommutative but associative matrix algebra. The investigation puts one on a firm footing from which to attack future problems in statistical signal processing, rather in the same manner that the introduction of Lie algebra and Lie groups in control theory made a variety of new ideas and developments possible.>

A tool is presented for solving some types of pattern matching problems using the method of steepest-descent/ascent. These matching problems can be recast as function maximization problems with the functions to be maximized being constrained over the orthogonal group. The optimization of these functions is then performed using the steepest-ascent algorithm. This is made possible by representing the orthogonal group as a Lie group and then investigating the gradient vector field associated with the function to be maximized or minimized. Since the orthogonal group includes the group of permutations as a subgroup, the proposed procedure works not only for the continuous optimization problem, but also for the combinatorial problem. The conditions for the convergence of the steepest-ascent algorithms are also shown and simulations are performed.>

The authors describe the estimation of the parameters of the Gilbert and Gilbert-Elliott models for burst-noise channels. Two estimation techniques are compared. The first estimation technique was proposed by Gilbert (1960) and is found to yield good estimates of the model parameters when the error sequences are long. The second estimation technique applies the theory of hidden Markov models to the parameter estimation problem. This technique does not require error sequences as long as those for Gilbert's technique and computes estimates with a lower variance. The second estimation technique is, however, more complex than Gilbert's approach.>

Recently, Gopalakrishnan et al. (1989) introduced a reestimation formula for discrete HMMs (hidden Markov models) which applies to rational objective functions like the MMIE (maximum mutual information estimation) criterion. The authors analyze the formula and show how its convergence rate can be substantially improved. They introduce a corrective MMIE training algorithm, which, when applied to the TI/NIST connected digit database, has made it possible to reduce the string error rate by close to 50%. Gopalakrishnan's result is extended to the continuous case by proposing a new formula for estimating the mean and variance parameters of diagonal Gaussian densities.>

The concept of vector trellis quantization is presented and applied to the encoding and decoding of still images for transmission over noiseless and noisy communication channels. A design procedure for a channel-optimized vector trellis quantizer is described. The criterion used in the design procedure is the expected squared error distortion measure. Simulation results using real images and a binary symmetric channel indicate that substantial signal-to-noise ratio improvement can be achieved at low, fractional transmission rates and high bit error rates.>

A novel method for the maximum likelihood estimation of autoregressive process parameters is presented. The approach is suited to applications in which the available data vector length is of the same order of magnitude as the autoregressive process model order, and it provides more accurate results than approximate methods that yield the maximum likelihood estimates only in the limit of long data records. The difficult nonlinear optimization problem is approached by first recursively solving for the maximum likelihood estimates of the data covariances subject to certain structural constraints, and then using these estimates in the Yule-Walker equations to obtain the autoregressive process parameter estimates. Experimental results demonstrate the potential of the method for autoregressive process power spectral density estimation using short data records.>

An approach to combined source-channel coding is presented. The method applies to a scalar source encoder designed using the Lloyd-Max algorithm and uses a family of binary primitive BCH codes. The channel model used is the binary symmetric channel. A variety of experimental results are presented which illustrate the average signal-to-noise ratio gain possible over no channel coding when different numbers of source encoder output bits are protected and the overall rate is held fixed. A number of interesting conclusions are drawn which can prove helpful in attempting to match existing source and channel coding techniques.>

A generalized hybrid automatic-repeat-request (GH-ARQ) scheme using hard-decision decoding and variable depth (redundancy) for adaptive error control in digital communications systems has recently been proposed by S.D. Morgera and H. Krishna (see Digital Signal Processing over Finite Fields: Applications to Communications and Algebraic Coding Theories. New York: Academic, 1988). An important feature of the GH-ARQ scheme is that variable depth and, consequently, variable minimum distance, is possible with a single encoder/decoder configuration. The present authors use binary PSK signaling, an additive white Gaussian noise (AWGN) channel, and several relevant code parameter choices in computer simulations to illustrate the improvement in throughput efficiency when soft-decision decoding is used in the GH-ARQ method. From the computational complexity standpoint, the use of GH-ARQ soft-decision decoding is feasible, since the code lengths used are relatively short. Comparison of simulation results is also made to the soft-decision ARQ scheme of G. Benelli (see ibid., vol.COM-33, p.285-8, Mar. 1985).>

The authors present a very efficient minimum mean-squared error (MMSE) encoding method useful for vector quantization. Using this method results in a considerable reduction in the number of multiplications and additions. The increase in the number of comparisons is moderate, and therefore the overall saving in the number of operations is still considerable. Very little precomputation and extra storage is required.>

The stepup (stepdown) procedure is an algorithm for computing the predictor polynomial (reflection) coefficients from the knowledge of the reflection coefficients (predictor polynomial). Here, both real as well as complex cases are considered, and several computationally efficient algorithms for the stepup and stepdown computations are presented. They are intimately related to recently reported alternative algorithms for computing the predictor polynomial associated with real, symmetric, and Hermitian Toeplitz matrices.>

Random field models have found applications in many areas including image analysis and processing. Techniques include the simultaneous (AR, MA, and SARMA) models and the conditional Markov (CM) models. To motivate the long correlation (LC) models examined, a brief review of both the SARMA and CM methods is provided. The LC random field models are then presented; these models are a generalization of SAR models and possess only a few parameters. Simulations are provided to illustrate the affect of parameter variation on the correlation, or texture, of the resulting random field. Very general experiments jointly employing SMA and LC models are also described; a combination of models of this type is seen to permit exceptionally flexible control over both low and high frequency random field behavior.>

A recursive algorithm is developed for finding the eigenvalues of a Hermitian Toeplitz matrix order n. The algorithm presented represents a generalization to the Hermitian case of one proposed by D.M. Wilkes and M.H. Hayes (1987) for the symmetric Toeplitz case. The method proposed uses Levinson's algorithm, or the more computationally efficient Hermitian Levinson algorithm of S.D. Morgera and H. Krishna (1987), at step k to form the characteristic equation of the next-larger principal submatrix of order k+1. The eigenvalues are then determined from the characteristic equation. The important issue of eigenvalue accuracy, which also applies to the Wilkes-Hayes procedure, is addressed.>

This work extends, unifies and generalizes the relationships between classical polynomial and matrix theory as it relates to the Levinson recurrence for a Hermitian Toeplitz operator. Several new classes of computationally efficient algorithms are presented for the Levinson recurrence on polynomial spaces satisfying certain symmetry properties. This approach also leads to new algorithms for solving systems of linear equations when the coefficient matrix is Hermitian Toeplitz. These algorithms lead to significant improvements in the computational complexity as compared to the previously best known recursive algorithms. They also provide further insight into the mathematical properties of the structurally rich Toeplitz matrices.

In this work, we present a very efficient search method useful for vector quantization, and other nearest neighbor search problems. The algorithm first finds a small area around the input vector with one codevector on its boundary. After finding such an area, the codebook is searched to determine whether there is any other codeword inside this area or not. This search is performed employing two tests, avoiding distortion calculation for those codewords which fail these tests. Using this algorithm the saving in the number of multiplications can be over 99%, in comparison with the conventional full search method, with the number of additions being reduced by as much as 82%. The price paid is a moderate increase in the number of comparisons.

Certain algorithms and their computational complexity are examined for use in a VLSI implementation of the real-time pattern classifier described in Part I of this work. The most computationally intensive processing is found in the classifier training mode wherein subsets of the largest and smallest eigenvalues and associated eigenvectors of the input data covariance pair must be computed. It is shown that if the matrix of interest is centrosymmetric and the method for eigensystem decomposition is operator-based, the problem architecture assumes a parallel form. Such a matrix structure is found in a wide variety of pattern recognition and speech and signal processing applications. Each of the parallel channels requires only two specialized matrix-arithmetic modules. These modules may be implemented as linear arrays of processing elements having at most O(N) elements where N is the input data vector dimension. The computations may be done in O(N) time steps. This compares favorably to O(N3) operations for a conventional, or general, rotation-based eigensystem solver and even the O(2N2) operations using an approach incorporating the fast Levinson algorithm for a matrix of Toeplitz structure since the underlying matrix in this work does not possess a Toeplitz structure. Some examples are provided on the convergence of a conventional iterative approach and a novel two-stage iterative method for eigensystem decomposition.

This paper introduces the concept of a generalized hybrid ARQ (GH-ARQ) scheme for adaptive error control in digital communication systems. This technique utilizes the redundant information available upon successive retransmissions in an efficient manner so as to provide high throughput during poor channel conditions. A new class of linear codes is proposed for the GH-ARQ system application. The main feature of this class of codes is that the encoder/decoder configuration does not change as the length of the code is varied. As a result, the receiver uses the same decoder for decoding the received information after every retransmission while the error correcting capability of the code increases, thereby leading to an improved performance and minimum complexity for the overall system implementation.

A simple, but efficient, nearest neighbor search algorithm is proposed and simulation results demonstrating its effectiveness in the case of vector quantization for a given source are presented. The simulation results indicate that use of this approach reduces the number of multiplications and additions to as low as 9 percent of those required for the conventional full search method. The reduction in the number of subtractions is also considerable. The increase in the number of comparisons is moderate, and therefore, the total number of operations can be as low as 28 percent of those required by the full search method. An additional advantage of the described algorithm is the fact that it requires no precomputations and/or extra memory.

In this work, we study restoration of digital images degraded by white and colored noise using the Wiener filtering technique. It has been established that the Karhunen-Loeve transform (KLT) of the covariance matrix of a first order Markov process can be closely approximated by the discrete cosine transform (DCT) [1]. This property is used to establish that the Wiener filtering equations for an (n × n) image (a linear system of order n2) degraded by white noise can be transformed using the DCT to obtainnsets of linear equations, each of ordern. The solution for each of thensystems can be computed inO(n)computations. Thus, the complete algorithm requiresO(2n^{2}\log_{2}n)computations, which is approximately half of the computations required for the previously described algorithms [2]. Also, it is shown that the approximation of the KLT by DCT may be interpreted as a modification in one of the boundary conditions (horizontal or vertical) of the noisy image. The algorithms obtained are generalized to include the case of images degraded by colored noise. The rise in computational complexity of the algorithm for such a case is marginal.

A new iterative image restoration method is presented which incorporates a priori knowledge concerning the image and noise statistics directly in the iterative procedure. The iterative algorithm is computationally efficient in that only a small number of computations per pixel are required and appears to exhibit neither high noise sensitivity nor significant loss of resolution. It is demonstrated that for image signal-to-noise ratio,L, greater than someL_{\min}, the procedure converges to the best mean-square estimate of the image. The value ofL_{\min}is derived and shown to depend on the correlation parameters of the image model. The basic iterative algorithm is then modified so that the modified algorithm converges to the best mean-square estimate of the image for all values of L. An interesting feature of this technique is that the noisy observed image is taken as the initial approximation to the best estimate. In general, an attractive advantage of iterative algorithms for image restoration is that they readily facilitate man-machine interaction.

The discrimination information of a set of stochastic vectors is utilized to define a measure of the information theoretic complexity of the associated covariance matrix. Bounds are developed that relate the covariance complexity to the maximum distance, or speed, between the characteristic roots of the covariance. A computationally efficient algorithm is devised for finding the elements of a diagonal operator for minimizing the covariance complexity when the covariance is of the Toeplitz form. Experimental results show that the algorithm reduces the information theoretic complexity and also is capable of appreciably increasing the maximum ratio of the characteristic roots of the covariance. A preprocessing operation of this type is important in data compression or feature selection for pattern recognition.

In general, the direct solution of an n-dimensional system of linear, equations requires O(n3) arithmetic operations. Frequently in high data rate signal processing, fast algorithms of complexity order3are required to solve a large system of linear equations. In several interesting applications, the specific structure of the coefficient matrix associated with the linear system may be used to reduce the required number of operations. Fast algorithms have been developed when the coefficient matrix is a Toeplitz matrix, a Hankel matrix, or when it can be represented as a sum of Toeplitz and Hankel matrices. The arithmetic complexity associated with these fast algorithms is O(n2). In this paper, fast algorithms of O(n) are presented that can be used for a class of matrices called diagonal innovation matrices (DIM). Previous results for this class of matrices require an arithmetic complexity of O(n2). A number of results are presented regarding the linear problems in signal processing with such matrices and several special cases are studied. The effect of recursively increasing the order of the coefficient matrix on the number of operations is studied and some observations are made.

Several authors have studied the problem of dimensionality reduction or feature selection using statistical distance measures, e.g., the Chernoff coefficient, Bhattacharyya distance, I-divergence, and J-divergence because they generally felt that direct use of the probability of classification error expression was either computationally or mathematically intractable. We show that for the difficult problem of testing one weakly stationary Gaussian stochastic process against another when the mean vectors are similar and the covariance matrices (patterns) differ, the probability of error expression may be dealt with directly using a combination of classical methods and distribution function theory. The results offer a new and accurate finite dimensionality information-theoretic strategy to feature selection, and are shown, by use of examples, to be superior to the well-known Kadota-Shepp approach which employs distance measures and asymptotics in its formulation. The present Part I deals with the theory; Part II deals with the implementation of a computer-based real-time pattern classifier which takes into account a realistic quasi-stationarity of the patterns.

The structure of bilinear cyclic convolution algorithms is explored over finite fields. The algorithms derived are valid for any length not divisible by the field characteristic and are based upon the small length polynomial multiplication algorithms. The multiplicative complexity of these algorithms is small and depends on the field of constants. The linear transformation matricesA, B(premultiplication), andC(postmultiplication) defining the algorithm have block structures which are related to one another. The rows ofAandBand the columns ofCare maximal length recurrent sequences. Because of the highly regular structure ofA, B, andC, the algorithms can be very easily designed even for large lengths. The application of these algorithms to the decoding of Reed-Solomon codes is also examined.

By making an example of the earlier proposed cyclic convolution algorithms, the computational efficiency of the multidimensional techniques over finite fields is investigated. It is shown that the multidimensional techniques are inferior to the directly designed algorithms for all lengths except when applied to lengths whose exponents are relatively prime. Relations between the complexities of the directly designed algorithms and those derived through the multidimensional techniques are also established in various cases.

We continue the research begun in 1975 on structured estimation. The original work in 1976 by Morgera and Cooper dealt with the Gaussian two-category classification problem when the common covariance matrix is unknown and must be estimated in order to approximate the hyperplane for decisionmaking, which is optimum for the true covariance matrix. We formulate the probability density function (pd0 estimation problem as a multivariate extension of the Rosenblatt-Parzen kernel method in which the multivariate characteristic function (cf) is estimated. A Gaussian form is assumed for the underlying probability distribution, and two methods are presented for the estimation of the covariance matrix in the cf: 1) a maximum-likelihood (MLE) general sample covariance matrix estimate, and 2) a constrained Toeplitz form estimate which takes full advantage of the structure imposed by weak stationarity of the underlying probability distribution. It is shown that both resulting cf estimates are asymptotically unbiased and consistent, albeit the structured covariance matrix estimate is itself only a {\em first approximation to the MLE} and may not be positive definite. It is, however, apparently this difference in the estimators which gives rise to a considerable difference in finite sample sire performance. Typical calculations show that the effective sample size increase of the structured estimate can be considerable, a fact very important in nonparametric problems in which data are limited, or in which the sample size-to-dimensionality ratio is small. Applications of this research to the areas of nonparametric pattern recognition and communications theory are discussed.

A systematic technique is presented for synthesizing and efficiently performing large discrete Fourier transformations (DFT’s) in the range from 60 to 5000 points. The technique is termed the mutual prime factor cyclic algorithm (MPFCA). The mutual prime factor portion of the algorithm is attributed originally to L. H. Thomas, with generalization supplied by I. J. Good; the cyclic aspect of the algorithm has recently been formalized by S. Winograd. Three methods are described for implementing the MPFCA; computational complexity (multiplications and additions) is estimated for each method and compared with the fast Fourier transform (FFT). For special purpose hardware, the MPFCA is at least twice as efficient as the FFT. A major result of importance is the realization that the three considerably different implementation methods presented lead to rather similar multiplication complexities for large size DFT’s; furthermore, the resulting multiplication complexity is considerably higher than that achieved for small size DFT’s. It is felt that further substantial improvements for large size DFT’s built up using mutually prime factors will require more general theoretical results in addition to long, tedious hours spent with computer based formula manipulation systems.

In this work we explore a number of questions arising in the Gaussian two-category classification problem when the common covariance matrix is unknown and must be estimated in order to approximate the hyperplane for decisionmaking, which is optimum for the true covariance matrix. Computed curves and, in some cases, closed form expressions are presented for describing the performance of such adaptive systems as a function of data dimensionality and learning sample size. In particular, we show that a considerable improvement in performance can be realized through the use of some {\em a priori} knowledge of covariance matrix structure. We use the adaptive filter output signal-to-interference noise power ratio (SIR) as a measure of detection performance to compare estimators designed for a weakly stationary stochastic process (Toeplitz form covariance matrix) with an estimator designed for a general sample covariance matrix. The ratio of expected SIR performance for a generalized covariance estimate to that for a filter which is optimum for the true covariance matrix is shown to be\cong [1 - N/N_{s} - 7/N_{s}], whereNis the filter (data) dimension, andN_{s}is the sample size. For a constrained Toeplitz form covariance matrix estimate, it is argued that the expected SIR approaches the optimum SIR as\cong [1 - \pi' (N;B)/N_{s} - 7 \pi'(N;B)/NN_{s}], with\pi'(N;B) \cong A + (B + 1) \ln N + 1/2N, whereA = 0.577is Euler's constant, and0 \leq B < Nis the input data correlation time normalized by the sampling period. Therefore, the constrained Toeplitz covariance matrix estimate appears to operate with an "effective sample size" equal toN'_{s} \cong [N/ \pi' (N;B)]N_{s}and offers the potential of high expected SIR at a sample sizeN_{s}for which the generalized estimator may provide poor results. The effective sample size is shown to be {\em even greater} if the dimensionality of the constrained Toeplitz covariance matrix estimate is tailored to the input data correlation time in the sense that only a band of lags about the main diagonal is estimated. In this case,N'_{s} \cong (kN^{2})N_{s}, where k is a constant, independent of N. An estimate of the computational error associated with the results, and due primarily to a quadratic approximation employed for the SIR, is derived and compared with the normal statistical error. Because closed form solutions for adaptive filter performance generally involve tedious calculations and involved expressions, certain other workers have relied on a similar approximation, but without the benefit of knowing the quality of the approximation for a givenNandN_{s}. Insight is also provided into other matters such as the effect of the specific form of the category mean value vector (signal) on adaptation performance. It is felt that many application areas will benefit from the results presented here, e.g., biomedical image recognition, earth resource satellite multispectral data classification, adaptive linear prediction, adaptive antenna array processing, etc. The manner in which the results impact the array processing area is discussed in some detail.