Lower Bounds on the State Complexity of Geometric Goppa Codes

Blackmore, T. and Norton, G. H. (2002) Lower Bounds on the State Complexity of Geometric Goppa Codes. Designs Codes and Cryptography, 25 1: 95-115. doi:10.1023/A:1012512718264

Author Blackmore, T.
Norton, G. H.
Title Lower Bounds on the State Complexity of Geometric Goppa Codes
Journal name Designs Codes and Cryptography   Check publisher's open access policy
ISSN 0925-1022
Publication date 2002-01
Sub-type Article (original research)
DOI 10.1023/A:1012512718264
Volume 25
Issue 1
Start page 95
End page 115
Total pages 21
Editor D. Jungnickel
J. D. Key
S. A. Vanstone
Place of publication United States
Publisher Kluwer Academic Press
Collection year 2002
Language eng
Subject C1
230103 Rings And Algebras
780101 Mathematical sciences
01 Mathematical Sciences
Abstract We reinterpret the state space dimension equations for geometric Goppa codes. An easy consequence is that if deg G less than or equal to n-2/2 or deg G greater than or equal to n-2/2 + 2g then the state complexity of C-L(D, G) is equal to the Wolf bound. For deg G is an element of [n-1/2, n-3/2 + 2g], we use Clifford's theorem to give a simple lower bound on the state complexity of C-L(D, G). We then derive two further lower bounds on the state space dimensions of C-L(D, G) in terms of the gonality sequence of F/F-q. (The gonality sequence is known for many of the function fields of interest for defining geometric Goppa codes.) One of the gonality bounds uses previous results on the generalised weight hierarchy of C-L(D, G) and one follows in a straightforward way from first principles; often they are equal. For Hermitian codes both gonality bounds are equal to the DLP lower bound on state space dimensions. We conclude by using these results to calculate the DLP lower bound on state complexity for Hermitian codes.
Keyword Computer Science, Theory & Methods
Mathematics, Applied
Geometric Goppa Codes
Hermitian Codes
State Complexity
Gonality Sequence
Dimension/length Profiles
Clifford's Theorem
Generalized Hamming Weights
Q-Index Code C1

Document type: Journal Article
Sub-type: Article (original research)
Collections: Excellence in Research Australia (ERA) - Collection
School of Physical Sciences Publications
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 1 times in Thomson Reuters Web of Science Article | Citations
Google Scholar Search Google Scholar
Created: Tue, 14 Aug 2007, 17:24:26 EST