Lower bounds on the state complexity of geometric Goppa codes

DOI10.1023/A:1012512718264MaRDI QIDQ5959836zbMATH OpenFDO

Authors T. Blackmore, G. H. Norton

Publication date 11 April 2002

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/A:1012512718264

zbMATH Keywords

DLP boundgeometric Goppa codesgonality boundsHermitian codestate complexitystate space dimension equationsWolf bound

Mathematics Subject Classification ID

Applications to coding theory and cryptography of arithmetic geometry (14G50) Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27) Bounds on codes (94B65)

Review text

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)].

Recommendations

• A goppa-like bound on the trellis state complexity of algebraic-geometric codes
• Bounding the trellis state complexity of algebraic geometric codes
• Bounds on the state complexity of codes from the Hermitian function field and its subfields
• On the parameters of Goppa codes
• scientific article; zbMATH DE number 3974889

Cited in

(4)

• Bounding the trellis state complexity of algebraic geometric codes
• Determining when the absolute state complexity of a Hermitian code achieves its DLP bound
• Bounds on the state complexity of codes from the Hermitian function field and its subfields
• A goppa-like bound on the trellis state complexity of algebraic-geometric codes

This page was built for publication: Lower bounds on the state complexity of geometric Goppa codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5959836)