Proof of a conjecture of McEliece regarding the expansion index of the minimal trellis
Alexander Vardy, Frank R. Kschischang · IEEE Transactions on Information Theory · 1996
We prove a conjecture of McEliece, establishing that for each fixed order of positions of a linear code C, the minimal trellis minimizes the quantity |E|-|V|+1, where |E| and |V| stand for the number of edges and vertices in the trellis, respectively. As a consequence, it follows that the minimal trellis uniquely minimizes the total number of operations required for Viterbi decoding of a given code. Moreover, we show that these results extend to the general class of rectangular codes (namely, the class of codes that admit a biproper trellis presentation), which includes all group codes and many other useful nonlinear codes.