×

Concatenated codes. (Каскадные коды. Translation from the English by V. V. Zyablov und O. V. Popov. Edited by S. I. Samoĭlenko.) (Russian) Zbl 0264.94006

M.I.T. Research Monograph, No. 37. The M.I.T. Press, Cambridge, Mass., xi, 147 p. (1966); Moskva: Izdat. ”Mir”. 207 p. R. 0.84 (1970).
From the text: Concatenation is a method of building long codes out of shorter ones; it attempts to meet the problem of decoding complexity by breaking the required computation into manageable segments. We present theoretical and computational results bearing on the efficiency and complexity of concatenated codes; the major theoretical results are the following:
1. Concatenation of an arbitrarily large number of codes can yield a probability of error that decreases exponentially with the over-all block length, while the decoding complexity increases only algebraically; and
2. Concatenation of a finite number of codes yields an error exponent that is inferior to that attainable with a single stage, but is nonzero at all rates below capacity.
Computations support these theoretical results, and also give insight into the relationship between modulation and coding.
This approach illuminates the special power and usefulness of the class of Reed- Solomon codes. We give an original presentation of their structure and properties, from which we derive the properties of all BCH codes; we determine their weight distribution, and consider in detail the implementation of their decoding algorithm, which we have extended to correct both erasures and errors and have otherwise improved. We show that on a particularly suitable channel, RS codes can achieve the performance specified by the coding theorem.
Finally, we present a generalization of the use of erasures in minimum-distance decoding, and discuss the appropriate decoding techniques, which constitute an interesting hybrid between decoding and detection.
Table of contents:
I. INTRODUCTION (Coding Theorem for Discrete Memoryless Channels, Concatenation Approach, Modulation, Channels with Memory, Concatenating Convolutional Codes, Outline).
II. MINIMUM-DISTANCE DECODING (Errors-Only Decoding, Deletions-and-Errors Decoding, Generalized Minimum-Distance Decoding, Performance of Minimum Distance Decoding Schemes).
III. BOSE-CHAUDHURI-HOCQUENGHEM CODES (Finite Fields, Linear Codes, Reed-Solomon Codes, BCH Codes).
IV. DECODING BCH CODES (Introduction, Modified Cyclic Parity Checks, Determining the Number of Errors, Locating the Errors, Solving for the Values of the Erased Symbols, Implementation).
V. EFFICIENCY AND COMPLEXITY (Asymptotic Complexity and Performance, Coding Theorem for Ideal Superchannels, Performance of RS Codes on the Ideal Superchannel, Efficiency of Two-Stage Concatenation).
VI. COMPUTATIONAL PROGRAM (Coding for Discrete Memoryless Channels, Coding for a Gaussian Channel, Summary).
APPENDIX A: Variations on the BCH Decoding Algorithm. APPENDIX B: Formulas for Calculation.
References
This is the author’s doctoral thesis available at
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.87.8263&rep=rep1&type=pdf.

MSC:

94B35 Decoding
94B70 Error probability in coding theory
94-02 Research exposition (monographs, survey articles) pertaining to information and communication theory
94Bxx Theory of error-correcting codes and error-detecting codes