Sequential decoding of lattice codes
Vahid Tarokh, Alexander Vardy, K. Zeger · 2002
We consider lattice tree-codes based on a lattice /spl Lambda/ having a finite trellis diagram T. Such codes are easy to encode and benefit from the structure of /spl Lambda/. Sequential decoding of lattice tree-codes is studied, and the corresponding Fano (1963) metric is derived. An upper bound on the running time of the sequential decoding algorithm is established, and found to resemble the Pareto distribution. Our bound indicates that the order of label groups in T plays an important role in determining the complexity of sequential decoding. Furthermore, it is proved that lattice tree-codes of arbitrarily high rate, based on /spl Lambda/ and T, can be sequentially decoded with the same complexity, and without any possibility of buffer overflow.