Efficient permutation criterion for obtaining minimal trellis of a block code

Efficient permutation criterion for obtaining minimal trellis of a block code

For access to this article, please select a purchase option:

Buy article PDF
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
Electronics Letters — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

To reduce the decoding complexity efficiently when using a trellis, a criterion is introduced, which can indicate at each stage of decoding whether or not the appropriate permutations on columns of the generator or parity-check matrix of the code are needed to obtain the minimal trellis in terms of its complexity. This criterion can also be used as a guide for finding a way to carry out column permutations more efficiently, as will be shown in an example.


    1. 1)
      • L.R. Bahl , J. Cocke , F. Jelinek , J. Raviv . Optimal decoding of linear codes for minimizing symbol error rate. IEEE Trans. Inf. Theory , 284 - 287
    2. 2)
      • Massey, J.L.: `Foundations and methods of channel coding', Proc. Int. Conf. Inform. Theory andSystems, 1978, 65, p. 148–157.
    3. 3)
      • T. Kasami , T. Takata , T. Fujiwara , S. Lin . On the optimal bit orders with respect to the statecomplexity of trellis diagram for binary linear codes. IEEE Trans. Inf. Theory , 242 - 245
    4. 4)
      • G.D. Forney . Dimension/length profiles and trellis complexity of linear block codes. IEEE Trans. Inf. Theory , 1741 - 1752
    5. 5)
      • Dolinar, S., Ekroot, L., Kiely, A., Lin, W., McEliece, R.T.: `The permutationtrellis complexity of linear block codes', Proc. 32nd Anun. Allerton Conf., 1994, p. 60–74.
    6. 6)
      • Kschschang, F.R., Horn, G.B.: `A heuristic for ordering a linear block code to minimize trellis statecomplexity', Proc. 32nd Anun. Allerton Conf., 1994, p. 75–84.
    7. 7)
      • F.J. MacWilliams , N.J.A. Sloane . (1977) The theory of error-correcting codes.
    8. 8)
      • A. Lafourcade , A. Vardy . Lower bounds on trellis complexity of block codes. IEEE Trans. Inf. Theory , 1938 - 1954

Related content

This is a required field
Please enter a valid email address