Ellipsoidal lists and maximum-likelihood decoding
Ilya I. Dumer · IEEE Transactions on Information Theory · 2000
We study an interrelation between the coverings generated by linear (n,k)-codes and complexity of their maximum-likelihood (ML) decoding. First , discrete ellipsoids in the Hamming spaces E/sub 1//sup n/ are introduced. These ellipsoids represent the sets of most probable error patterns that need to be tested in soft-decision ML decoding. We show that long linear (n,k)-codes surrounded by ellipsoids of exponential size 2/sup n-k/ can cover the whole space E/sub 2//sup n/. Then it is proven that ML decoding of most long (n,k)-codes needs only about 2/sup n-k/ most probable error patterns to be tested on any quantized memoryless channel. Finally, ML decoding complexity is bounded from above by 2/sup k(n-k)/n/. This substantially reduces the general trellis complexity 2/sup min{n-k,k}/.