LinearCode -- class of linear codes

Description

A linear code is the image of some mapping between vector spaces, where each vector space is taken to be over the same finite field. A codeword is an element of the image. A linear code in Macaulay2 is implemented as a hash table. The values of the hash table correspond to common representations of the code, as well as information about its structure. The values include the base field of the modules, a set of generators for the code, and more. To construct a linear code, see linearCode.

i1 : F1=GF(2)

o1 = F1

o1 : GaloisField

i2 : G1={{1,1,0,0,0,0},{0,0,1,1,0,0},{0,0,0,0,1,1}}

o2 = {{1, 1, 0, 0, 0, 0}, {0, 0, 1, 1, 0, 0}, {0, 0, 0, 0, 1, 1}}

o2 : List

i3 : C1=linearCode(F1,G1)

                                   6
o3 = LinearCode{AmbientModule => F1                                                            }
                BaseField => F1
                cache => CacheTable{}
                Code => image | 1 0 0 |
                              | 1 0 0 |
                              | 0 1 0 |
                              | 0 1 0 |
                              | 0 0 1 |
                              | 0 0 1 |
                GeneratorMatrix => | 1 1 0 0 0 0 |
                                   | 0 0 1 1 0 0 |
                                   | 0 0 0 0 1 1 |
                Generators => {{1, 1, 0, 0, 0, 0}, {0, 0, 1, 1, 0, 0}, {0, 0, 0, 0, 1, 1}}
                ParityCheckMatrix => | 1 1 0 0 0 0 |
                                     | 0 0 1 1 0 0 |
                                     | 0 0 0 0 1 1 |
                ParityCheckRows => {{1, 1, 0, 0, 0, 0}, {0, 0, 1, 1, 0, 0}, {0, 0, 0, 0, 1, 1}}

o3 : LinearCode

i4 : C1.Code

o4 = image | 1 0 0 |
           | 1 0 0 |
           | 0 1 0 |
           | 0 1 0 |
           | 0 0 1 |
           | 0 0 1 |

                               6
o4 : F1-module, submodule of F1

For the mapping defined above, we call the codomain of the mapping the ambient module. The length of a code is defined to be the rank of this module.

i5 : F2=GF(3)

o5 = F2

o5 : GaloisField

i6 : G2={{1,0,0,0,0,1,1,1},{0,1,0,0,1,0,1,1},{0,0,1,0,1,1,0,1},{0,0,0,1,1,1,1,0}}

o6 = {{1, 0, 0, 0, 0, 1, 1, 1}, {0, 1, 0, 0, 1, 0, 1, 1}, {0, 0, 1, 0, 1, 1,
     ------------------------------------------------------------------------
     0, 1}, {0, 0, 0, 1, 1, 1, 1, 0}}

o6 : List

i7 : C2=linearCode(F2,G2)

                                   8
o7 = LinearCode{AmbientModule => F2                                                                                                               }
                BaseField => F2
                cache => CacheTable{}
                Code => image | 1 0 0 0 |
                              | 0 1 0 0 |
                              | 0 0 1 0 |
                              | 0 0 0 1 |
                              | 0 1 1 1 |
                              | 1 0 1 1 |
                              | 1 1 0 1 |
                              | 1 1 1 0 |
                GeneratorMatrix => | 1 0 0 0 0 1 1 1 |
                                   | 0 1 0 0 1 0 1 1 |
                                   | 0 0 1 0 1 1 0 1 |
                                   | 0 0 0 1 1 1 1 0 |
                Generators => {{1, 0, 0, 0, 0, 1, 1, 1}, {0, 1, 0, 0, 1, 0, 1, 1}, {0, 0, 1, 0, 1, 1, 0, 1}, {0, 0, 0, 1, 1, 1, 1, 0}}
                ParityCheckMatrix => | 1 0 0 -1 0 -1 -1 1  |
                                     | 0 1 0 -1 0 1  0  -1 |
                                     | 0 0 1 -1 0 0  1  -1 |
                                     | 0 0 0 0  1 1  1  1  |
                ParityCheckRows => {{1, 0, 0, -1, 0, -1, -1, 1}, {0, 1, 0, -1, 0, 1, 0, -1}, {0, 0, 1, -1, 0, 0, 1, -1}, {0, 0, 0, 0, 1, 1, 1, 1}}

o7 : LinearCode

i8 : AM=C2.AmbientModule

       8
o8 = F2

o8 : F2-module, free

i9 : rank(AM)==length(C2)

o9 = true

Since a linear code $C$ is a vector subspace over some finite field, we may represent it using a Generator Matrix, i.e., a matrix whose rows form a basis for $C$. The dimension of a code is the rank of the generator matrix.

i10 : dim(C2)==rank(C2.GeneratorMatrix)

o10 = true

A linear code in Macaulay2 also includes a parity check matrix $H$, which generates the vector space orthogonal to $C$. Let $c$ be a code word in $C$ and $h$ a vector in the space generated by the rows of $H$. Then the dot product between $c$ and $h$ is zero.

i11 : c=matrix{G2_0}

o11 = | 1 0 0 0 0 1 1 1 |

               1       8
o11 : Matrix ZZ  <-- ZZ

i12 : h=transpose matrix({(entries(C2.ParityCheckMatrix))_0})

o12 = | 1  |
      | 0  |
      | 0  |
      | -1 |
      | 0  |
      | -1 |
      | -1 |
      | 1  |

               8       1
o12 : Matrix F2  <-- F2

i13 : c*h

o13 = 0

               1       1
o13 : Matrix F2  <-- F2

Caveat

While some functions may work even when a ring is given, instead of a finite field, it is possible that the results are not the expected ones.

Functions and methods returning an object of class LinearCode :

cyclicCode -- cyclic codes
cyclicCode(GaloisField,RingElement,ZZ) -- see cyclicCode -- cyclic codes
cyclicCode(GaloisField,ZZ,ZZ) -- see cyclicCode -- cyclic codes
dualCode(LinearCode) -- see dualCode -- dual of a code
genericCode -- ambient space of a code
genericCode(LinearCode) -- see genericCode -- ambient space of a code
hammingCode -- generates a Hamming code
hammingCode(ZZ,ZZ) -- see hammingCode -- generates a Hamming code
linearCode(GaloisField,List) -- see linearCode -- functions to construct linear codes over Galois fields
linearCode(GaloisField,ZZ,List) -- see linearCode -- functions to construct linear codes over Galois fields
linearCode(Matrix) -- see linearCode -- functions to construct linear codes over Galois fields
linearCode(Module) -- see linearCode -- functions to construct linear codes over Galois fields
linearCode(Module,List) -- see linearCode -- functions to construct linear codes over Galois fields
linearCode(ZZ,ZZ,ZZ,List) -- see linearCode -- functions to construct linear codes over Galois fields
locallyRecoverableCode -- constructs a locally recoverable code (LRC)
locallyRecoverableCode(List,List,RingElement) -- see locallyRecoverableCode -- constructs a locally recoverable code (LRC)
quasiCyclicCode -- constructs a quasi-cyclic code
quasiCyclicCode(GaloisField,List) -- see quasiCyclicCode -- constructs a quasi-cyclic code
quasiCyclicCode(List) -- see quasiCyclicCode -- constructs a quasi-cyclic code
randomCode -- constructs a random linear code over a finite field
randomCode(GaloisField,ZZ,ZZ) -- see randomCode -- constructs a random linear code over a finite field
randomCode(QuotientRing,ZZ,ZZ) -- see randomCode -- constructs a random linear code over a finite field
repetitionCode(GaloisField,ZZ) -- see repetitionCode -- repetition code
shorten -- shortens a code
shorten(LinearCode,List) -- see shorten -- shortens a code
shorten(LinearCode,ZZ) -- see shorten -- shortens a code
universeCode(GaloisField,ZZ) -- see universeCode -- linear code $\mathtt{F}^\mathtt{n}$
zeroCode(GaloisField,ZZ) -- see zeroCode -- zero code
zeroSumCode(GaloisField,ZZ) -- see zeroSumCode -- linear code in which the entries of each codeword add up zero

Methods that use an object of class LinearCode :

alphabet(LinearCode) -- see alphabet -- elements of the base ring of a code
ambientSpace(LinearCode) -- see ambientSpace -- recovers the ambient module of a code
chooseStrat(LinearCode) -- see chooseStrat -- Estimate the optimal strategy to compute the minimum weight of a linear code.
codewords(LinearCode) -- see codewords -- codewords of the code
dim(LinearCode) -- dimension of a linear code
field(LinearCode) -- see field -- the field of a code
informationRate(LinearCode) -- see informationRate -- information rate of a code
length(LinearCode) -- returns the length of a linear code
LinearCode == LinearCode -- determines if two linear codes are equal
messages(LinearCode) -- see messages -- set of messages to be encoded by a code
minimumWeight(LinearCode) -- see minimumWeight -- computes the minimum weight of a linear code
ring(LinearCode) -- the ring of a code
size(LinearCode) -- gives the number of codewords in a linear code
syndromeDecode(LinearCode,Matrix,ZZ) -- see syndromeDecode -- syndrome decoding on a code
toString(LinearCode) -- string with the vectors of a generator matrix of a code
vectorSpace(LinearCode) -- see vectorSpace -- vector space of a code

For the programmer

The object LinearCode is a type, with ancestor classes HashTable < Thing.

ambientSpace -- recovers the ambient module of a code
bitflipDecode -- an experimental implementation of a message passing decoder
Code -- a code as image
codewords -- codewords of the code
GeneratorMatrix -- gives the generator matrix of a linear code
informationRate -- information rate of a code
linearCode -- functions to construct linear codes over Galois fields
messages -- set of messages to be encoded by a code
weight -- Hamming weight of a list
syndromeDecode -- syndrome decoding on a code
LinearCode == LinearCode -- determines if two linear codes are equal