Search

It is shown that when Pierce's pulse-position modulation scheme with 2 to the L power positions (where L is some positive integer) is used on a self-noise-limited direct-detection optical communication channel, there results a (2 to the L power)-ary erasure channel that is equivalent to the parallel combination of L completely correlated binary erasure channels. The capacity of the full channel is the sum of the capacities of the component channels, but the cutoff rate of the full channel is shown to be much smaller than the sum of the cutoff rates. An interpretation of the cutoff rate is given that suggests a complexity advantage in coding separately on the component channels. It is shown that if short-constraint length convolutional codes with Viterbi decoders are used on the component channels, then the performance and complexity compare favorably with the Reed-Solomon coding system proposed by McEliece (1979) for the full channel. The reasons for this unexpectedly fine performance by the convolutional code system are explored in detail, as are various facets of the channel structure.

It is shown that Pierce's pulse position modulation scheme with 2 to the L pulse positions used on a self-noise-limited direct detection optical communication channel results in a 2 to the L-ary erasure channel that is equivalent to the parallel combination of L completely correlated binary erasure channels. The capacity of the full channel is the sum of the capacities of the component channels, but the cutoff rate of the full channel is shown to be much smaller than the sum of the cutoff rates. An interpretation of the cutoff rate is given that suggests a complexity advantage in coding separately on the component channels. It is shown that if short-constraint-length convolutional codes with Viterbi decoders are used on the component channels, then the performance and complexity compare favorably with the Reed-Solomon coding system proposed by McEliece for the full channel. The reasons for this unexpectedly fine performance by the convolutional code system are explored in detail, as are various facets of the channel structure.

The very low error probability obtained with long error-correcting codes results in a very small number of observed errors in simulation studies of practical size and renders the usual confidence interval techniques inapplicable to the observed error probability. A natural extension of the notion of a 'confidence interval' is made and applied to such determinations of error probability by simulation. An example is included to show the surprisingly great significance of as few as two decoding errors in a very large number of decoding trials.

In a spread-spectrum communication system, a data sequence of +1's and -1's is expanded into a sequence of +x's (bottom bar) and -x's (bottom bar) where x (bottom bar) is a length n sequence of +1's and -1's. A sub-baud code is the assignment of a different such baud sequence to each of M users with the objective of reducing interference between users. It is shown that this interference can be described in terms of the even and odd correlation functions between pairs of sequences. A technique for deriving sub-baud codes from cyclic error-correcting codes is given, and a theorem proved which bounds the quality of the resultant code. A specific such cyclic code construction procedure is given which, for any M, yields a sub-baud code for which the mutual interference can be made arbitrarily small by choosing n sufficiently large.

A new R = 1/2 K = 32 quick-look-in code is described and compared to the R = 1/2 K = 32 Massey-Costello code now used in some NASA systems. The new code, has the optimum distance profile property. This new code is shown, by comparison of Fano sequential decoding performance on a simulated Gaussian noise channel, to be computationally superior to the Massey-Costello code. The new code is also shown to be superior to the Massey-Costello code according to several analytical code criteria.

A regular Markov source is defined as the output of a deterministic, but noisy, channel driven by the state sequence of a regular finite-state Markov chain. The rate of such a source is the per letter uncertainty of its digits. The well-known result that the rate of a unifilar regular Markov source is easily calculable is demonstrated, where unifilarity means that the present state of the Markov chain and the next output of the deterministic channel uniquely determine the next state. At present, there is no known method to calculate the rate of a nonunifilar source. Two tentative approaches to this unsolved problem are given, namely source identical twins and the master-slave source, which appear to shed some light on the question of rate calculation for a nonunifilar source.

Results of research on the use of convolutional codes in data communications are presented. Convolutional coding fundamentals are discussed along with modulation and coding interaction. Concatenated coding systems and data compression with convolutional codes are described.

The degradation of the performance of digital communication systems because of ionospheric scintillation effects can be reduced either by diversity techniques or by coding. The effectiveness of traditional space-diversity, frequency-diversity and time-diversity techniques is reviewed and design considerations isolated. Time-diversity signaling is then treated as an extremely simple form of coding. More advanced coding methods, such as diffuse threshold decoding and burst-trapping decoding, which appear attractive in combatting scintillation effects are discussed and design considerations noted. Finally, adaptive coding techniques appropriate when the general state of the channel is known are discussed.

It is shown that the fraction p of ones in the Mn positions of M distinct binary n-tuples satisfies a given inequality. This inequality, which simplifies the derivation of the distance property of the Justesen codes, is proved using an elegant information-theoretic argument due to Kriz.

The modulator structure consisting of a single-input two-output sequential transducer whose output sequences control the modulated signal in the manner s(t) = x(i)p(t) + y(i)q(t) is considered. Here, iT is less than or equal to t, which is less than iT + T, where T is the modulation bit duration and where x(i) and y(i) take values in /+1, -1, 0/. The behavior of a sequential transducer is characterized by means of a 'trellis'. It is shown that, provided only that the 'carriers' p(t) and q(t) have the same energy in every bit interval, the optimum demodulator for the additive white Gaussian noise channel need process the received signal over only two bit intervals in making each data bit decision. It is demonstrated that particular choices of the sequential transducer yield differential minimum shift keying and differential staggered quadriphase shift keying. Possible generalizations of this approach are discussed.

A generalized modulation scheme, which includes minimum shift keying (MSK) and staggered quadriphase shift keying (SQPSK) as special cases, is analyzed. The general modulator is realized as a one-input, two-output sequence transducer whose outputs select the carrier signal for each band. This form of the modulator has the practical advantage of not requiring any RF filtering since there is no actual mixing of the carriers with the modulating signals. It is shown that the optimum demodulator (whether hard-decision or soft-decision) always can make its decisions from the received waveform over two bands when the interference is additive white Gaussian noise, thus generalizing a well-known result for hard decision demodulation of MSK and SQPSK signals. The power spectra of MSK and SQPSK signals are derived to isolate the role played by coherency between the modulating signals and the carriers.

Comparison of the energy to noise ratio necessary to obtain a given modulation bit error probability has indicated that three-phase modulation is about 0.75 db superior to four-phase. It is shown that this apparent superiority results entirely from the greater bandwidth required by the three-phase system for the same bit transmission rate. Two further comparison criteria are proposed, which are based on the cut-off rate R sub 0 of the discrete channel created by the modulation system. For the criterion which constrains both the bandwidth and transmitted power, it is shown that four-phase modulation is always superior to three-phase modulation. The conclusion is that three-phase modulation offers no practical advantage over four-phase modulation.

Work on partial unit memory codes continued; it was shown that for a given virtual state complexity, the maximum free distance over the class of all convolutional codes is achieved within the class of unit memory codes. The effect of phase-lock loop (PLL) tracking error on coding system performance was studied by using the channel cut-off rate as the measure of quality of a modulation system. Optimum modulation signal sets for a non-white Gaussian channel considered an heuristic selection rule based on a water-filling argument. The use of error correcting codes to perform data compression by the technique of syndrome source coding was researched and a weight-and-error-locations scheme was developed that is closely related to LDSC coding.

Virtually all previously-suggested rate 1/2 binary convolutional codes with KE = 24 are compared. Their distance properties are given; and their performance, both in computation and in error probability, with sequential decoding on the deep-space channel is determined by simulation. Recommendations are made both for the choice of a specific KE = 24 code as well as for codes to be included in future coding standards for the deep-space channel. A new result given in this report is a method for determining the statistical significance of error probability data when the error probability is so small that it is not feasible to perform enough decoding simulations to obtain more than a very small number of decoding errors.

Summary of the most important results so far obtained in the theory of coding for the correction and detection of errors in computer arithmetic. Attempts to satisfy the stringent reliability demands upon the arithmetic unit are considered, and special attention is given to attempts to incorporate redundancy into the numbers themselves which are being processed so that erroneous results can be detected and corrected.

It is shown that the metric proposed originally by Fano for sequential decoding is precisely the required statistic for minimum-error-probability decoding of variable-length codes. The analysis shows further that the 'natural' choice of bias in the metric is the code rate and gives insight into why the Fano metric has proved to be the best practical choice in sequential decoding. The recently devised Jelinek-Zigangirov 'stack algorithm' is shown to be a natural consequence of this interpretation of the Fano metric. Finally, it is shown that the elimination of the bias in the 'truncated' portion of the code tree gives a slight reduction in average computation at the sacrifice of increased error probability.

Description of a class of rate 1/2 nonsystematic convolutional codes with the following desirable properties: (1) an undetected decoding error probability verified by simulation to be much smaller than for the best systematic codes of the same constraint length; (2) computation behavior with sequential decoding verified by simulation to be virtually identical to that of the best systematic codes; (3) a ?quick-look-in' feature that permits recovery of the information sequence from the hard-decisioned received data without decoding simply by modulo-two addition of the received sequences; and (4) suitability for encoding by simple circuitry requiring less hardware than encoders for the best systematic codes of the same constraint length. Theoretical analyses are given. These codes have been adopted for use in several forthcoming space missions.

Convolutional coding techniques for data protection

Sequential decoding algorithms and flow charts for convolutional coding techniques

Satellite communications performance improvement by use of multipath signal for channel models including noncoherent FSK

General inverses for linear sequential circuits and continuous dynamical systems

Convolutional coding techniques for data protection

Invertibility of linear time invariant dynamical control systems, discussing L-inverses, sequential circuits, inherent integration, reproducibility, pointwise and functional inverses

Convolutional coding techniques for data protection

Algorithms for convolutional codes and development of linear sequential machines

Linear shift register synthesis algorithm found to coincide with Berlekamp iterative algorithm for decoding BCH codes

Existence and construction of modified L lag inverses solution method for linear dynamical systems

Convolutional coding techniques for data protection

Catastrophic error propagation in convolutional codes

Trunk and tree searching properties of Fano sequential decoding algorithms

Upper and lower bounds for feedback decoding and definite decoding minimum distances of binary convolutional codes

Automata and continuous system theories and relationships between convolutional codes and zero state automata and cyclic codes and zero input automata

Existence of q-ary uniform convolutional codes where q is any prime-power, noting error- correcting ability comparable to familiar maximal- length block codes

Study of certain polynomials with the 'weight-retaining' property that any linear combination of these polynomials with coefficients in a general finite field has Hamming weight at least as great as that of the minimum-degree polynomial included. This fundamental property is used in applications to Reed-Muller codes, a new class of 'repeated-root' binary cyclic codes, two new classes of binary convolutional codes derived from binary cyclic codes, and two new classes of binary convolutional codes derived from Reed-Solomon codes.

This paper considers the optimum method for locating a sync word periodically imbedded in binary data and received over the additive white Gaussian noise channel. It is shown that the optimum rule is to select the location that maximizes the sum of the correlation and a correction term. Simulations are reported that show approximately a 3-dB improvement at interesting signal-to-noise ratios compared to a pure correlation rule. Extensions are given to the phase-shift keyed sync case where the detector output has a binary ambiguity and to the case of Gaussian data.