A Hybrid Coding Scheme for Discrete Memoryless Channels

It is well known that the use of block coding and maximum-likelihood decoding permits transmission of information at rates up to the capacity of a discrete memoryless channel with an error probability which decreases exponentially with the code block length.1-4 A discrete memoryless channel (DMC) may be an adequate model for some types of real one-way digital communication channels consisting of a transmission medium, transmitting and receiving equipment and modulation-demodulation scheme. An arbitrary DMC is assumed to have * T h i s research is partly based on a Ph.D. thesis, D e p a r t m e n t of Electrical Engineering, Massachusetts Institute of Technology, 1966, carried out at the Research Laboratory of Electronics, Massachusetts Institute of Technology, supported by the National Aeronautics and Space Administration ( G r a n t NsG334) and a Hughes Industrial Fellowship. 691 692 THE BELL SYSTEM TECHNICAL JOURNAL, MARCH 1969 a P-symbol input alphabet and a Q-symbol output alphabet. During each channel use, an input symbol is selected and transmitted and an output symbol is received. Successive input-to-output transitions are random and statistically independent; the probability that the output is symbol ; (; = 1, 2, . . . , Q), given that the input is symbol i (i = 1, 2, . . . , P), is qi}. (Table I contains a list of the symbols used throughout this paper) Maximum-likelihood decoding, which is known to be optimum, involves the cross-correlation of a received block code word with all possible transmitted code words.