Lower bounds on the state complexity of geometric Goppa codes (Q5959836)

For a linear \([n,k]\) code \(C\), the state complexity \(s(C)\) of \(C\) measures the complexity of trellis-based decoding algorithms for \(C\). An upper bound on \(s(C)\) is given by the Wolf bound \[ s(C)\leq\min(k,n- k) \] [\textit{J. Wolf}, IEEE Trans. Inf. Theory 24, 76-80 (1978; Zbl 0371.94027)]. In this article the authors study the case of geometric Goppa codes \(C=C_L(D,G)\). They first reinterpret the state space dimension equations of \(C\) in geometric terms. As a consequence they prove that \(s(C)\) reaches the Wolf bound except perhaps in the case \[ \deg(G)\in [(n-1)/2, (n-3)/2+ 2g], \] where \(g\) is the genus of the underlying curve. In this case three new bounds on \(s(C)\) are provided, based on the theorem of Clifford and the gonality sequence of the curve. Finally, the case of codes coming from the Hermitian curve is treated in some detail: the authors compute the DLP bound on \(s(C)\) and prove that it coincides with their gonality bounds. Some explicit examples are included. Some results of this paper (mainly concerning the translation of the state space dimension equations of \(C\) in geometric terms) have been independently obtained by \textit{Y. Be'ery} and \textit{Y. Shany} [IEEE Trans. Inf. Theory 46, 1523-1527 (2000; Zbl 0999.94041)].