The box and match decoding algorithm (BMA) significantly reduces the computational complexity of the ordered statistic decoding algorithm at the expense of increased memory requirements. A soft-input/soft-output version of the BMA is developed. Additional complexity-reduction techniques are also described.

In this paper, we improve the ordered statistics decoding algorithm by using matching techniques. This allows us: to reduce the worst case complexity of decoding (the error performance being fixed) or to improve the error performance (for a same complexity); to reduce the ratio between average complexity and worst case complexity; to achieve practically optimal decoding of rate-1/2 codes of lengths up to 128 (rate-1/2 codes are a traditional benchmark, for coding rates different from 1/2, the decoding is easier); to achieve near-optimal decoding of a rate-1/2 code of length 192, which could never be performed before.

The main reference of this paper is the sphere-packing bound of 1967 (SP67) derived by Shannon, Gallager, and Berlekamp. It offers a lower bound on the decoding error probability over a very large variety of channels. If it has failed so far to provide any usable material in practical implementation of telecommunication systems, it is due to an original focus on asymptotic results (making it inapplicable for moderate code lengths) and to the difficulty of the involved methods (which makes the derivation of SP67 quite hermetic and uninspiring for further research). The purpose of this paper is two-fold: 1) to stir up some renewed interest in the topic on which Shannon concluded his career in information theory thanks to a qualitative (rather than technical) review of the derivation of SP67, introduced by a review of the simpler sphere-packing bound derived by Shannon in 1959; 2) to prove the practical interest of SP67 by extending its field of application to continuous output channels and particularly the additive white Gaussian noise (AWGN) channel used with any particular modulation scheme, and by improving its lower bound for the moderate code length case so that it becomes the best lower bound for most iteratively decodable codes (turbo codes, low-density parity-check (LDPC) codes, repeat-accumulate (RA) codes, etc.) of usual lengths.

The order statistic decoding (OSD) algorithm is a probabilistic list decoding algorithm which allows to achieve practically optimum soft decision decoding of binary linear block codes of length up to 128. Recently, matching techniques were applied to the OSD algorithm to reduce both the worst case and average complexities of decoding at the expense of memory. The corresponding box-and-match algorithm (BMA) allows to achieve near optimum decoding of codes of length up to 192. In this work, we investigate the application of iterative information set reduction to the BMA, which provides further refinements in the trade-offs between error performance and decoding complexity.

Many decoding algorithms need to compute some lists of binary vectors that minimize a given weight function. Furthermore, it is often desirable that these vectors are generated by increasing weight. The considered weight function is usually decreasing in the a priori likelihood that the vector yields correct decoding. We present a new technique to generate candidates for error patterns from the most a priori likely to the least, that proves significantly more efficient than any other known method.