A recursive approach to low complexity codes

TLDR

The paper proposes a method to build long error‑correcting codes by combining shorter subcodes via a bipartite graph. The construction uses a bipartite graph to select digit subsets that must belong to subcodes, enabling encoders and decoders to exploit the explicit subcode decomposition for simplified computation. The authors derive lower bounds on rate and distance, establish performance bounds for two decoders, analyze asymptotic decoding complexity, show that probabilistic channel information can be leveraged efficiently, and demonstrate that an appropriate digit transmission order yields strong burst‑error correction.

Abstract

A method is described for constructing long error-correcting codes from one or more shorter error-correcting codes, referred to as subcodes, and a bipartite graph. A graph is shown which specifies carefully chosen subsets of the digits of the new codes that must be codewords in one of the shorter subcodes. Lower bounds to the rate and the minimum distance of the new code are derived in terms of the parameters of the graph and the subeodes. Both the encoders and decoders proposed are shown to take advantage of the code's explicit decomposition into subcodes to decompose and simplify the associated computational processes. Bounds on the performance of two specific decoding algorithms are established, and the asymptotic growth of the complexity of decoding for two types of codes and decoders is analyzed. The proposed decoders are able to make effective use of probabilistic information supplied by the channel receiver, e.g., reliability information, without greatly increasing the number of computations required. It is shown that choosing a transmission order for the digits that is appropriate for the graph and the subcodes can give the code excellent burst-error correction abilities. The construction principles