Reduced State Distance Spectrum Computation for General Trellis Codes
Weimin Zhang, Christian B. Schlegel, Michael J. Miller · International Symposium on Information Theory and its Applications · 1994
For an N state nonlinear trellis code the distance spectrum computation requires an N2 state distance generating trellis. This and the search algorithm often make the problem prohibitively complex. In this paper, the classical finite state machine theory is applied to derive a general and efficient algorithm. The distance generating matrix is first obtained by a Kronecker type product. It is then reduced by the systematic state space partitioning process. The search algorithm is also replaced by the recursive matrix multiplications with distance truncations. Since no condition is pre-required, the algorithm can handle all trellis codes and/or ISI channels. However, if some symmetrical property of the code/channel is known, such as linearity or quasi-regularity, then the state reduction process can be bypassed for further efficiency. With minor modifications, the algorithm can also be used for calculation of product distance spectrum.