On the absolute state complexity of algebraic geometric codes

Abstract

A trellis of a code is a labeled directed graph whose paths from the initial to the terminal state correspond to the codewords. The main interest in trellises is due to their applications in the decoding of convolutional and block codes. The absolute state complexity of a linear code C is defined in terms of the number of vertices in the minimal trellises of all codes in the permutation equivalence class of C. In this thesis, we investigate the absolute state complexity of algebraic geometric codes. We illustrate lower bounds which, together with the well-known Wolf upper bound, give a good idea about the possible values of the absolute state complexities of algebraic geometric codes. A key role in the analysis is played by the gonality sequence of the function field that is used in code construction.