SCCL, a new bit tracking loop based on the sample-correlate-choose-largest design principle, was shown to be an effective bit synchronizer. However, the analysis common in analyzing digital phase locked loops, proceeds on the assumption that the noise samples are independent which is not necessarily true in practice. The performance of SCCL, is analyzed without the independence assumption by considering the second-order statistics to complete the analysis. This approach is also useful to analyze other digital phase-locked loops or baseband digital signal processing schemes in digital communication systems.>

We introduce the application of SCCL that is based on sample-correlate-choose-largest procedure as a coherent baseband PN-code tracking loop applying biphase-level signals. Three adjacent estimates are formed by correlating the samples of the baseband waveform for each bit. We choose the corresponding timing (phase) of the estimate with the largest magnitude as the current correct timing (phase) and update it for each bit. Only one summation circuit is required due to the digital realization of the SCCL. The correlation properties of the samples from maximum length codes using the biphase-level signal set are investigated. Tracking performance is theoretically analyzed in both steady-state and transient conditions via a finite-state Markov chain model. The numerical results demonstrate strong PN-code tracking characteristics of SCCL.>

The authors propose a new bit tracking loop for biphase signals which is implemented like the maximum a posteriori probability (MAP) optimal bit synchronizer by the sample-correlate choose-largest algorithm except that the estimator is sampled and moved at most one sample each bit time. A mathematical Markovian model for analysis is used. The performance of the bit tracking loop, the mean square error of the jitter and the average acquisition time, are theoretically derived. The numerical results of performance analysis for various signal-to-noise ratios are found through computer evaluations. The data obtained illustrate that this new structure is a very effective bit synchronizer for digital communications systems applying digital signal processing techniques.>

Two iterative minimax algorithms are presented with associated convergence theorems. Both algorithms consist of iterative procedures based on a sequence of finite parameter sets. In general, these finite parameter sets are subsets of an infinite parameter space. To show their applicabilities, several commonly used examples are presented. It is also shown that minimax problems with or without finite parameter sets can be solved by these two algorithms numerically to any assigned degree of accuracy.>

A surprising resemblance has been found between the Remez and Chang-Davisson algorithm in the sense that the underlying idea accidentally coincides although the applications are quite different. The authors investigate the analogy between these algorithms. In particular, they look into their respective properties and differences and discuss their prospects. A comparison is then made to see their common structure and to gain insight into possible applications. It is concluded that one potential connection is to open up a new approach to digital filter design.>

The authors present a description and performance analysis of a new PN code acquisition approach for the tracking and data relay satellite system with multiple access (TDRSS MA) return subsystem. The MA subsystem uses a phased array on-board the TDRS with 30 elements whose received signals are each independently retransmitted to the ground for beam forming. In the current operational system, acquisition is performed by using a serial search of the possible PN epochs on the beam-formed 30-element signal. In contrast, the new approach performs acquisition on a single (arbitrary) element signal using a parallel (i.e., simultaneous) search of all possible PN epochs. Since only one element signal is used, no beam forming is required prior to PN acquisition. The approach is based on sampling and digital processing of the received signal. The new method also incorporates techniques which counteract the effects of Doppler and asynchronous data modulation. The probability of correct acquisition as a function of acquisition time, signal-to-noise ratio, data rate, and user satellite Doppler is analyzed.>

A version of the Arimoto-Blahut algorithm for continuous channels involves evaluating integrals over an entire input space and thus is not tractable. Two generalized discrete versions of the Arimoto-Blahut algorithm are presented for this purpose. Instead of calculating integrals, both algorithms require only the computation of a sequence of finite sums. This significantly reduces numerical computational complexity.>

The performance of a digital delta modulator when used as a repeater for binary non-return-to-zero signals between a noisy channel and an error-free link is analyzed. A Markov chain is used to model the accumulator output (observation process) of the device, and a Bayes test with a probability of error criterion is formulated to evaluate its performance in additive band-limited Gaussian channel noise. The key design parameters of sampling rate and accumulator range are varied for computation of performance degradation relative to the optional matched filter. Numerical results are presented that demonstrate the feasibility of this technique.>

Upper and lower bounds are presented on the minimax redundancy for Markov source noiseless block-to-variable universal coding. The number of states, block size, and Markov order are arbitrary but finite. Unlike earlier results, the upper and lower bounds are absolute, that is, not merely asymptotic. The upper bound is established by combinatorial bounds. The lower bound is established by a bound on the average redundancy for an arbitrary distribution on the transition probabilities. The bound can be optimized across the choice of distribution.

A new approach to the classical fixed-length noiseless source coding problem is proposed for the case of finite ergodic Markov sources. This approach is based on simple counting arguments. The central notion of "Markov type" (a set containing all the source sequences having the same transition counts from letter to letter) is introduced and the cardinality of such a set is evaluated via graph theoretical tools. The error exponent is shown to be a weighted average of informational divergences, and the universal character of the result is stressed. As a corollary, the classical source coding theorem (determining the achievable rates) is rederived.

Although the existence of universal noiseless variable-rate codes for the class of discrete stationary ergodic sources has previously been established, very few practical universal encoding methods are available. Efficient implementable universal source coding techniques are discussed in this paper. Results are presented on source codes for which a small value of the maximum redundancy is achieved with a relatively short block length. A constructive proof of the existence of universal noiseless codes for discrete stationary sources is first presented. The proof is shown to provide a method for obtaining efficient universal noiseless variable-rate codes for various classes of sources. For memoryless sources, upper and lower bounds are obtained for the minimax redundancy as a function of the block length of the code. Several techniques for constructing universal noiseless source codes for memoryless sources are presented and their redundancies are compared with the bounds. Consideration is given to possible applications to data compression for certain nonstationary sources.

A source matching approach is presented to the problem of finding minimax cedes for classes of memoryless sources. The approach leads to a channel capacity problem so that Blahut's algorithm can be used to find approximations to the minimax code. Closed form solutions are presented for the class of monotonic sources and for a class of Bernoulli-like sources. For extensions of finite alphabet memoryless sources, a modified Lynch-Davisson code has performance close to that of the minimax code. The exact solution to the source matching problem and the resulting codes are presented for the extensions of binary codes up to blocklength 31.

A decision-directed detection scheme for multiple hypotheses is developed and analyzed. It is assumed that the probability density functions\{f_{i}(x)\}under each of them+1hypotheses are known, and the prior probablities\{\pi_{i}\}are unknown and sequentially estimated on the basis of previous decisions. Using a set of nonlinear transformations of the data and applying results from the stochastic approximation theory, improved algorithms are given for achieving asymptotically unbiased estimates and accelerated convergence to the true priors.

Two results on the coding of stationary nonergodic sources are presented. The first is a source coding theorem stating that there exist variable-rate codes with performance arbitrarily close to the rate-distortion function of the stationary nonergodic source. The second is a converse information transmission theorem. It is shown that the distortion which results when the source is transmitted across a channel with capacityCis no less than the least distortion achievable by fixed-rate codes with rateC.

This paper is concerned with two problems in the theory of source coding subject to a maximum average distortion constraint. The first problem involves the coding of a nonergodic discrete time source and the second involves coding for a class of ergodic discrete time sources. Coding theorems are given for both of these situations for very general source alphabets. The codes that are obtained here will, in general, be variable length codes so that average code rate and average distortion are the measures of performance.

A simple upper bound is derived to the difference in performance obtained from applying a given quanfizer to two different sources. This provides a bound on the performance loss or mismatch resulting when applying a quantizer designed for one source to another. The bound is in terms of a generalization of the Vasershtein distance between the source random variables and does not depend on the particular quantizer chosen. In particular, if two sources are sufficiently close in this sense, then any quantizer results in nearly identical performance on either source. Implications for optimal performance bounds are discussed and examples are given.

In this paper we provide an alternate method of proving the existence theorem for the coding of discrete stationary ergodic sources subject to a fidelity constraint. This method differs from previously published proofs for sources with memory in that a random coding argument is obtained directly for the coding of sourcen-tuples. The main advantage of the technique employed in this paper is that it can easily be extended to yield the basis for the proof of the coding theorem for more general sources (e.g., nonergodic) and for sources with unknown parameters.

A three-element detector, consisting of anRCfilter with time constant1/a, a hard limiter, and finally anRCfilter with time constant1/b, is considered. The detector is stimulated by a nonzero-mean white Gaussian noise input, and the system output is observed. A Markov assumption on the hard limiter output leads to a closed-form expression for the output density, which is verified to be close to the actual output density of the detector by computer simulations.

In recent years adaptive linear estimation based upon the gradient-following algorithm has been proposed in a wide range of applications. However, little analysis on the convergence of the estimation has appeared when the elements of the data sequence are dependent. This paper presents such an analysis under the assumptions of stationarity andM-dependence (all data sets separated by more than a constantM < \inftyare statistically independent). It is shown that for a sufficiently small adaptation constant, the mean error in the estimator weights converges to a finite limit, generally nonzero. In addition, hounds on the norm of the mean weight-deviation and on the mean norm-square of the weight-deviation are found and shown to converge to asymptotic bounds, which can be made arbitrarily small by decreasing the adaptation constant and increasing the data block length over which gradient estimates are made.

A unified theory is developed for fixed rate block source encoding subject to a fidelity criterion in incompletely or inaccurately specified stationary statistical environments. Several definitions of universal encoding are given and compared, and the appropriate theorems are stated and proved for each. The new results and approaches are compared and contrasted with earlier related results of Ziv.

Source coding theorems are proved for discrete-time stationary processes subject to a fidelity criterion. The alphabet of the process is assumed to be a separable metric space, but the process is not assumed to be ergodic. When the process is not ergodic, the minimum average distortion for a fixed-rate code is not given by the distortion-rate function of the source as usually defined. It is given instead by a weighted average of the distortion-rate functions of ergodic subsources comprising the ergodic decomposition of the source. Potential applications to universal source coding with a fidelity criterion are discussed.

The ergodic decomposition is discussed, and a version focusing on the structure of individual sample functions of stationary processes is proved for the special case of discrete-time random processes with discrete alphabets. The result is stronger in this case than the usual theorem, and the proof is both intuitive and simple. Estimation-theoretic and information-theoretic interpretations are developed and applied to prove existence theorems for universal source codes, both noiseless and with a fidelity criterion.

Universal coding is any asymptotically optimum method of block-to-block memoryless source coding for sources with unknown parameters. This paper considers noiseless coding for such sources, primarily in terms of variable-length coding, with performance measured as a function of the coding redundancy relative to the per-letter conditional source entropy given the unknown parameter. It is found that universal (i.e., zero redundancy) coding in a weighted sense is possible if and only if the per-letter average mutual information between the parameter space and the message space is zero. Universal coding is possible in a maximin sense if and only if the channel capacity between the two spaces is zero. Universal coding is possible in a minimax sense if and only if a probability mass function exists, independent of the unknown parameter, for which the relative entropy of the known conditional-probability mass-function is zero. Several examples are given to illustrate the ideas. Particular attention is given to sources that are stationary and ergodic for any fixed parameter although the whole ensemble is not. For such sources, weighted universal codes always exist if the alphabet is finite, or more generally if the entropy is finite. Minimax universal codes result if an additional entropy stability constraint is applied. A discussion of fixed-rate universal coding is also given briefly with performance measured by a probability of error.

Suppose white noise is put into anRCfilter with time constant1/awhose output is hard limited and fed into a secondRCfilter with time constant1/b. The density of the outputy(t)of the system has been the subject of several investigations. Most recently, Pawula and Tsai made the conjecture that for Gaussian white noise they(t)density is given by a certain expression, a special case of which was derived earlier by Doyle, McFadden, and Marx forb/a = 2. In this paper an expression for thenth moment ofy(t)is found. From the expression for the fourth moment, it is proven that the Pawula-Tsai conjecture is not true in general. It is further found that if the output of the hard limiter were wide-sense Markov, the Pawula-Tsai conjecture would be true.

This paper examines the performance of a digital communication system operating in the presence of additive Gaussian noise when a bandpass hard limiter is inserted into the system. In contrast with earlier published work for large time-bandwidth product systems, small signal-time-duration-noise-bandwidth products at large SNR's are considered. It is found that the degradation introduced by the limiter is more severe under these conditions.

This paper examines the performance of a two-link digital communication system operating in the presence of Gaussian noise on both links when bandpass limiters are inserted into the system. The product of the signal time duration and the noise bandwidth for the systems under consideration is small. It is concluded that under certain conditions, the presence of a limiter can improve the performance of the system. Also, a simplification of previous work is presented when an infinite clipper is introduced at baseband in the detector.

Intersymbol interference degrades the performance of digital communication systems: A practical method of reducing this type of distortion is provided by transversal filter equalization at the receiver. Lucky has shown that, if the unequalized peak distortion is less than 100 percent, then theNfilter tap gains minimize the equalized peak distortion if the intersymbol interference contribution from the correspondingNdelays is set equal to zero. This correspondence presents two extensions of Lucky's theorem. The first states that if the peak distortion is greater than 100 percent, the conclusion of the theorem does not hold in general. A second theorem gives two conditions where the conclusion does hold.

This paper considers the steady-state mean-square error when an adaptive linear estimator is used on a stationary time series. The estimator weights are adjusted periodically by moving a small increment in the direction of the estimated gradient. Under very general conditions the asymptotic mean-square error is bounded and under more restrictive conditions is evaluated exactly.

In certain stochastic-approximation applications, sufficient conditions for mean-square and probability-one convergence are satisfied within some unknown bounded convex set, referred to as a convergence region. Globally, the conditions are not satisfied. Important examples are found in decision-directed procedures. If a convergence region were known, a reflecting barrier at the boundary would solve the problem. Then the estimate would converge in mean square and with probability one. Since a convergence region may not be known in practice, the possibility of nonconvergence must be accepted. LetAbe the event where the estimation sequence never crosses a particular convergence-region boundary. The sequence of estimates conditioned onAconverges in mean square and with probability one, because the sequence of estimates is the same as if there were a reflecting barrier at the boundary. Therefore, the unconditional probability of convergence exceeds the probability of the eventA. Starting from this principle, a lower bound on the convergence probability is derived in this paper. The results can also be used when the convergence conditions are satisfied globally to bound the maximum-error probability distribution. Specific examples are presented.

This paper investigates the effects of dependence on rank tests, in particular on a class of recently defined nonparametric tests called "mixed" statistical tests. It is shown that the mixed test statistic is asymptotically normal for Gaussian processes with mild regularity properties justifying the use of asymptotic relative efficiency (ARE) as a figure of merit. Results are presented in terms of variations on three well-known statistics--the one-sample Wilcoxon, the two-sample Mann-Whitney, and the Kendall\tau. It is found that the effects of dependence on ARE with respect to a parametric test can be offset to some extent by appropriately grouping sample values. If, however, a constant false-alarm rate is to be attained, either the form of the dependence must be known or some learning scheme must be applied.

A decision-directed receiver (DDR) uses previous outputs (decisions) to estimate unknown parameters and, on the basis of these estimates, modifies the detector structure for subsequent decisions. Although the DDR is less complex to instrument than other adaptive schemes, inherent in the decision-directed approach is the possibility of a runaway. This occurs when the detector commits a sequence of decision errors resulting in a degradation of parameter estimates, which, in turn, results in a further deterioration of detector performance. Because of the dependencies introduced by the learning process, runaway is difficult to analyze. In this paper, a DDR with unknown a priori probabilities is considered. The priors are estimated by the relative frequency of decisions of that event. For binary detection, it is shown that there is a positive probability of a runaway (the estimates converge to 1 or 0), which equals 1 if the signal-to-noise ratio is below a critical value. A tight bound on the probability of a runaway is obtained by approximating the learning process by a random walk with independent increments. The analysis demonstrates that a runaway is quite improbable even for moderate signal-to-noise ratios. The analysis is extended to multiple signals and to the situation where the estimates of the priors are updated continuously through exponential weighting rather than allowed to converge.

One simple method of data compression relies on the approximation of the source output by polynomial segments or "interpolators." The parameters of each polynomial are transmitted in place of the original data. This paper presents a method of theoretically analyzing such techniques. Straight line interpolation is considered specifically although the ideas can he readily generalized. It is shown that the class of compression methods considered may or may not perform well depending on the data and, thus, that in some cases more complex techniques, including possibly adaptive methods, might he used, depending on the knowledge of the data statistical model.

A recent work by the authors describes a new class of nonparametric statistics formed by summing the rank statistics on data subsets of a fixed number of sample valuesm. This paper derives the locally-most-powerful tests of this class under the assumption of independent sampling.

This paper presents results applicable to data-compression systems of the prediction-comparison type. In this type of system advantage is taken of the inherent predictability of the data. Any sample which can be predicted to within some threshold is not transmitted and the prediction is inserted in place of the actual sample in the data. This error feedback affects data predictability in a nonlinear fashion resulting in a difficult theoretical problem. In this paper the probability of prediction is given asymptotically as the error threshold goes to zero for a stationary Gaussian time series using linear prediction. The effect of error feedback is shown to be of prime significance. A comparison is made between the optimum open-loop predictor, the optimum closed-loop predictor, and a polynomial approximation. It is shown that the optimum closed-loop system is significantly better than the other two. Computer simulations confirm the theoretical results.

Mixed statistical tests are described. It is shown that these tests have a much higher efficiency than conventionally used statistics such as the sign test and polarity coincidence correlation without the high operational complexity of the Wilcoxon, Mann-Whitney, Kendall\tau, or Fisher-Yates: Terry-Hoeffding tests.

This paper considers the adaptive signal extraction problem for time-discrete data when only very general a priori assumptions regarding the distributions of signal and noise are possible. Specifically, it is assumed that the noise is white, additive, and signal independent with mean zero and unknown variance and that the signal is band-limited. No stationarity assumptions are required. After a procedure is found under these conditions, the mean-square-error is derived asymptotically under narrower conditions-stationary Gaussian data with mean zero. Finally, a method of estimating the error variance from the data (without knowing the signal directly) is found.

In prediction problems of communication and control theory, it has become increasingly obvious that there are many applications in which a priori assumptions regarding data statistics are not justified. Thus, systems must be designed to take maximum advantage of whatever statistics are encountered. Unfortunately, these systems are inherently nonlinear in operation, which makes it difficult, ff not impossible, to evaluate their performance. In this paper the asymptotic form of the mean square prediction error is found for a stationary Gaussian time series when the prediction is a linear weighting of the immediate past, the weights being "learned" from the data. Computer results are given to demonstrate the usefulness of the asymptotic formula.