20 Coding Theory

Magma provides support for several different branches of Coding Theory. These include:-

20.1 Linear Codes over Finite Fields

20.1.1 Linear Codes: Creation

  • Creation from a subspace of a vector space

  • Creation in terms of a generator matrix

  • Creation from a design

  • Creation from a finite plane

  • Construction of a cyclic code given the generator polynomial

  • Construction of a cyclic code given the roots of the generator polynomial

  • Universe code, repetition code, zero code

  • Random linear code

20.1.2 Operations on Codewords

  • Vector space operations: sum, difference scalar multiplication

  • Syndrome

  • Distance and weight

  • Coordinates, support

  • Trace

20.1.3 Elementary Operations

  • Sum, intersection

  • Dual code

  • Hull of a code

  • External direct sum, Plotkin sum

  • Modifying the codewords: augment, extend, expurgate, lengthen, puncture, shorten, etc.

  • Subcode generated by given codewords

  • Subcode of a specified dimension

  • Subcode generated by words of a given weight

  • Coset leaders (in the case of a small code)

20.1.4 Basic Properties

  • Standard form

  • All information sets of a code

  • Idempotent of a cyclic code

  • Properties: cyclic

  • Properties: even, doubly even, equidistant

  • Properties: self-dual, weakly self-orthogonal

  • Properties: perfect, nearly perfect

  • Properties: maximum-distance separable, equidistant

  • Properties: optimal for the Griesmer bound

  • Properties: projective

  • Determine whether two codes are equivalent

20.1.5 Weight Distribution

  • Minimum weight (Zimmermann algorithm)

  • Weight distribution, weight enumerator

  • MacWilliams transform

  • Complete weight enumerator, MacWilliams transform

  • Number of words of designated weight

  • Number of words of constant weight

  • List all words of designated weight

  • List all words of constant weight

  • Coset weight distribution, covering radius, diameter

Carefully crafted algorithms are provided for computing the minimum weight, the weight distribution, and word collection algorithms. For example, computation of the minimum weight of a [96,60,8] code takes 77 seconds; computation of the weight distribution of the [64,22,16] Reed-Muller code (r = 2,m = 6) takes 1.4 seconds.

20.1.6 Construction of Families

  • Hamming code, simplex code

  • Reed-Muller codes

  • Quadratic residue code, Golay codes, doubly circulant QR-code, twisted QR-code, power residue code

  • BCH code

  • Goppa code

  • Chien-Choy code

  • Alternant code, Fire code, Gabidulin code

  • Srivastava, generalized Srivastava codes

  • Reed-Solomon code, generalized Reed-Solomon code, Justesen code

  • Maximum distance separable code

20.1.7 Algebraic-Geometric codes

Functions are provided for the construction of algebraic–geometric codes. The user chooses a plane curve X, and specifies a set of places of degree 1 on X and a divisor on X.

20.1.8 Decoding Algebraic-Geometric codes

Algebraic-geometric codes can be decoded efficiently up to the Goppa designated distance.

20.1.9 Changing the Alphabet

  • Extension of the base field

  • Restricting the alphabet to a subfield

  • Subfield subcode

  • Trace code

  • Rewriting the alphabet, taken as the elements of GF(qm), as m-dimensional vectors over GF(q)

20.1.10 Combining Codes

  • Concatenation of two codes

  • Concatenated code

  • Construction X

  • Construction X3

  • Construction XX

  • Zinoviev code

  • Construction Y1

20.1.11 Bounds

  • BCH bound on minimum distance

  • Upper and lower bounds on the cardinality of a largest code having given length and minimum distance

  • Upper asymptotic bounds on the information rate

  • Tables of best known bounds, based on the codes database

20.1.12 Best Known Codes

Magma incorporates databases containing constructions of the best known linear codes over Fq for q = 2,3,4,5,7,8,9. These databases contain codes of length up to 256 for q = 2,4; of length up to 243 for q = 3; of length up to 130 for q = 5,8,9; and of length up to 100 for q = 7.

The binary codes database is complete in the sense that it contains a construction for every set of parameters, with the codes of length up to 31 known to be optimal. The database for codes over F3 is more than 78% complete (and complete up to length 100), with codes of length up to 21 known to be optimal. The database for codes over F4 is more than 65% complete (and complete up to length 97), with codes of length up to 18 known to be optimal. Further details are summarised in the table below.

The Magma BKLC database makes use of the tables of bounds compiled by A.E. Brouwer. It should be noted that the Magma BKLC database is unrelated to the similar (but rather incomplete) BKLC database forming part of GUAVA, a share package in GAP3. A significant number of entries in the Magma BKLC database provide better codes than the corresponding ones listed in the Brouwer tables.

The construction of the Magma BKLC database has been undertaken by John Cannon (Sydney), Markus Grassl (Karlsruhe) and Greg White (Sydney).

F2

F3

F4

F5

F7

F8

F9

nmax

256

243

256

130

100

130

130

nopt

31

21

18

15

14

14

16

ncomplete

256

100

97

80

68

76

93

total

33 152

29 889

33 152

8 645

5 150

8 645

8 645

missing

0

6 545

11 379

527

381

1 763

1 333

filled

100%

78.10%

65.67%

93.90%

92.60%

79.61%

84.58%

20.1.13 Decoding Algorithms

  • Syndrome decoding

  • Alternant decoding

20.1.14 Automorphism Group

  • Automorphism groups of linear codes over GF(p) (prime p), GF(4)

  • Testing pairs of codes for isomorphism over GF(p) (prime p), GF(4)

  • Group actions on a code

Automorphism groups may be computed over any field Fp, p a prime, and F4, again using Leon's PERM package.

20.1.15 Attacks on the McEliece Cryptosystem

All of the best known decoding attacks on the McEliece cryptosystem are available, as well as improved attacks.

  • McEliece's attack

  • Lee and Brickell's attack

  • Leon's attack

  • Stern's atack

  • Canteaut and Chabaud's attack

  • Generalized combinations of attacks

20.2 Low-Density Parity-Check Codes

Low-density parity-check (LDPC) codes are among the best performing linear codes in practice, being capable of correcting n errors, where n is close to the Shannon bound. Currently, there exist few techniques for the explicit construction of LDPC codes. Typically, these codes are selected at random from an ensemble, and their properties determined through simulation. An LDPC code can be decoded in time that is linear in its block length through use of iterative belief propagation techniques.

  • Construction of LDPC codes from sparse matrices

  • Gallager's construction

  • The group-based construction of Margulis

  • Deterministic LDPC constructions

  • Random constructions from regular and irregular LDPC ensembles

  • Construction of the Tanner graph of an LDPC code

  • Ensemble rate

  • Iterative decoding of LDPC codes

  • Simulation of decoding performance on specified channels

  • Density evolution and threshold determination for binary symmetric and Gaussian channels for given channel parameters

  • A small database of good irregular LDPC ensembles is provided

20.3 Linear Codes over Finite Rings

In the 1990's it was discovered that certain good nonlinear codes could be obtained by applying the Gray mapping to certain linear codes defined over the ring ℤ4. This led to a great deal of research into the properties of codes over finite rings. This section describes the facilities which are provided in Magma for studying linear codes over finite rings. Magma currently supports basic facilities for codes over integer residue rings and Galois rings, including the construction of cyclic codes, and the calculation of the complete weight enumerator. Additional functionality is available for the special case of codes over ℤ4.

20.3.1 Constructions

  • Creation from a subspace of a vector space

  • Creation in terms of a generator matrix

  • Construction from a permutation

  • Construction of a cyclic code given the generator polynomial

  • Construction of a cyclic code given the roots of the generator polynomial

  • Universe code, repetition code, zero code

  • Random linear code

  • Construction of the Kerdock and Preparata codes (over Z4)

20.3.2 Elementary Operations and Properties

  • Syndrome

  • Hamming distance, Hamming weight

  • Lee distance, Lee weight (over ℤ4)

  • Coordinates, support

  • Trace

  • Module operations: sum, difference, scalar multiplication

  • Dual code

  • External direct sum, Plotkin sum

  • Obtaining a new code by modifying codewords: Augment, extend, expurgate, lengthen, puncture, shorten, etc.

  • Coset leaders (in the case of a small code)

  • Standard form, Gray map, Lee weights (over ℤ4)

  • Determine whether cyclic, even, self-dual, self-orthogonal (over ℤ4)

20.3.3 Weight Distribution

  • Minimum Hamming weight

  • Hamming weight distribution

  • Hamming weight enumerator

  • Complete weight enumerator

  • Minimum Lee weight via the Zimmermann algorithm (over ℤ4)

  • Lee weight distribution (over ℤ4)

  • Symmetric weight enumerator (over ℤ4)

  • Lee weight enumerator (over ℤ4)

20.4 Additive Codes

Given a finite field F and the space of all n-tuples of F, an additive code is a subset of F(n) which is a K-linear subspace for some subfield K⊆F. Additive codes have become increasingly important recently due to their application to the construction of quantum error-correcting codes, though they are also of interest in their own right. The Magma package for quantum error-correcting codes is built on the machinery for additive codes.

20.4.1 Constructions

  • Additive codes defined as some K-additive subspace of Fn for some subfield K of F.

  • Creation in terms of a generator matrix

  • Construction of a cyclic code given the generator polynomial

  • Universe code, repetition code, zero code

  • Random additive code

  • Sum, intersection of two codes

  • Dual code, symplectic dual code

  • Plotkin sum

  • Obtaining a new code by modifying codewords: augment, extend, lengthen, puncture, shorten, etc.

  • Subcode generated by given codewords

  • Subcode of a specified dimension

  • Subcode generated by words of a given weight

  • Construction of a cyclic (quasicyclic) code from parameters

20.4.2 Operations and Properties

  • Vector space operations: sum, difference scalar multiplication

  • Distance and weight

  • Coordinates, support

  • Trace

  • Determine whether cyclic, self-dual, self-orthogonal, symplecic self-dual, symplectic self-orthogonal

  • Automorphism and permutation groups of additive codes over GF(4)

  • Group actions on a code

20.4.3 Weight Distribution

  • Minimum weight (Zimmermann algorithm)

  • Weight distribution, weight enumerator

  • MacWilliams transform

  • Complete weight enumerator, MacWilliams transform

  • Number of words of designated weight

  • Number of words of constant weight

  • List all words of designated weight

  • List all words of constant weight

The fast algorithm used for determining the minimum weight and word collection is adapted from the one used for linear codes and provides performance similar to a calculation with an equivalently-sized linear code.

20.5 Quantum Error-Correcting Codes

In 1995 Shor showed that it was possible to encode quantum information in such a way that errors can be corrected. Following this discovery, a class of quantum error-correcting codes known as stabilizer codes was developed. It turned out that these stabilizer codes can be represented by additive codes over finite fields. This remarkable result reduces the problem of constructing fault-tolerant encodings on a continuous Hilbert space to that of constructing certain discrete codes, thereby permitting the application of many of the tools developed in classical coding theory.

20.5.1 Constructions

  • Quantum stabilizer codes defined by symplectic self-dual additive codes.

  • Creation in terms of a generator matrix

  • Construction of a cyclic code given the generator polynomial

  • Universe code, repetition code, zero code

  • Random quantum code

  • Construction of new codes via direct sums

  • Construction of new codes extending or shortending existing codes

  • Families: Cyclic codes, quasicyclic codes, CSS code,

20.5.2 Quantum Codes: Basic Properties

  • Properties: Cyclic, quasicyclic

  • Properties: Self-dual

  • Properties: Stablizer code

  • The group of errors on a quantum space

  • Stabiliser group associated with a quantum code

  • Minimum weight (Zimmermann algorithm)

  • Weight distribution, weight enumerator

  • Complete weight enumerator

  • Automorphism and permutation groups of binary quantum codes (codes based on quaternary stabilizer codes)

The algorithm for determining the minimum weight applies the Zimmermann algorithm to the underlying self-dual code.