Engineering topics
Publications and source records attributed to Mceliece, Robert J..
Report surveys state of art of coding digital data for nearly errorless communication over long distances. Coding techniques described include mainly ones that have been or might be used to transmit imagery and/or other data from spacecraft to receivers on Earth.
Practical Viterbi decoders often fall significantly short of full maximum likelihood decoding performance because of survivor truncation effects. In the present work the authors study the tradeoff between truncation length and performance loss for the two most common variations of Viterbi's algorithm: best-state decoding (BSD) and fixed-state decoding (FSD). It is found that FSD survivors should be about twice as long as BSD survivors for comparable performance.
A class of codes called finite-state (FS) codes is defined and investigated. The codes, which generalize both block and convolutional codes, are defined by their encoders, which are finite-state machines with parallel inputs and outputs. A family of upper bounds on the free distance of a given FS code is derived. A general construction for FS codes is given, and it is shown that in many cases the FS codes constructed in this way have a free distance that is the largest possible. Catastrophic error propagation (CEP) for FS codes is also discussed. It is found that to avoid CEP one must solve the graph-theoretic problem of finding a uniquely decodable edge labeling of the state diagram.
McEliece and Swanson (1986) offered an upper bound on P(E)u, the decoder error probability given u symbol errors occur. In the present study, by using a combinatoric technique such as the principle of inclusion and exclusion, an exact formula for P(E)u is derived. The P(E)u of a maximum distance separable code is observed to approach Q rapidly as u gets large, where Q is the probability that a completely random error pattern will cause decoder error. An upper bound for the expansion P(E)u/Q - 1 is derived, and is shown to decrease nearly exponentially as u increases. This proves analytically that P(E)u indeed approaches Q as u becomes large, and that some laws of large number come into play.
Techniques from coding theory are applied to study rigorously the capacity of the Hopfield associative memory. Such a memory stores n-tuple of + or - 1s. The components change depending on a hard-limited version of linear functions of all other components. With symmetric connections between components, a stable state is ultimately reached. By building up the connection matrix as a sum-of-outer products of m fundamental memories, it may be possible to recover a certain one of the m memories by using an initial n-tuple probe vector less than a Hamming distance n/2 away from the fundamental memory. If m fundamental memories are chosen at random, the maximum asymptotic value of m in order that most of the m original memories are exactly recoverable is n/(2 log n). With the added restriction that every one of the m fundamental memories be recoverable exactly, m can be no more than n/(4 log n) asymptotically as n approaches infinity. Extensions are also considered, in particular to capacity under quantization of the outer-product connection matrix. This quantized memory-capacity problem is closely related to the capacity of the quantized Gaussian channel.
The observations of Posner (1983) that on a wideband Gaussian broadcast channel ordinary time-shared coding performs almost as well as broadcast coding are investigated. A quantitative version of Posner's results is derived. A numerical example comparing the performance of broadcast coding and time-shared coding for a Gaussian broadcast channel model is presented.
Upper bounds on the decoder error probability for Reed-Solomon codes are derived. By definition, decoder error occurs when the decoder finds a codeword other than the transmitted codeword; this is in contrast to decoder failure, which occurs when the decoder fails to find any codeword at all. The results imply, for example, that for a t error-correcting Reed-Solomon code of length q - 1 over GF(q), if more than t errors occur, the probability of decoder error is less than 1/t. In particular, for the Voyager Reed-Solomon code, the probability of decoder error given a word error is smaller than 3 x 10 to the minus 14th power. Thus, in a typical operating region with probability 100,000 of word error, the probability of undetected word error is about 10 to the minus 14th power.