Designing Lexicographic Codes
With a Given Trellis Complexity¹²

Ari Trachtenberg³⁴

Abstract:

We generalize constructions of lexicographic codes to produce locally optimal codes with a desired trellis decoding complexity. These constructions are efficient for high rate codes and provide a means for automated code design. As a byproduct, we improve known bounds on the parameters of lexicodes.

Keywords: code design, lexicographic codes, minimal trellises, trellis decoding

• A version of this paper appeared in the IEEE Transactions on Information Theory, Volume 48, Number 1, Jan. 2002, pp. 89.
• A version also appeared with Alexander Vardy at the 31st Annual Conference on Information Sciences and Systems.