linearCode -- functions to construct linear codes over Galois fields

Synopsis

Usage:

linearCode(G)

linearCode(M)

linearCode(M,L)

linearCode(F,L)

linearCode(F,n,L)

linearCode(p,r,n,L)
Inputs:
- G, a matrix,
- M, a module,
- F, a Galois field,
- p, an integer,
- r, an integer,
- n, an integer,
- L, a list,
Optional inputs:
- ParityCheck => ..., default value false
Outputs:
- an instance of the type LinearCode, $C$

Description

We present below the ways in how a linear code $C$ can be defined.

a matrix is given

Usage:

linearCode(G)
Inputs:
- G, a matrix,
Outputs:
- an instance of the type LinearCode, $C$

Given a matrix G, whose entries are in a Galois field F, this function returns a linear code $C$ over F.

If no optional input is specified, then the generator matrix of the code $C$ is G.

If the optional input ParityCheck => true is specified, then the code $C$ is the dual of the linear code generated by the matrix G.

i1 : F = GF 4;

i2 : L = apply({{1,0,1,0},{0,1,1,1}},codeword ->apply(codeword,entry->sub(entry,F)));

i3 : M = matrix L

o3 = | 1 0 1 0 |
     | 0 1 1 1 |

             2      4
o3 : Matrix F  <-- F

i4 : C = linearCode(M)

                                  4
o4 = LinearCode{AmbientModule => F                             }
                BaseField => F
                cache => CacheTable{}
                Code => image | 1 0 |
                              | 0 1 |
                              | 1 1 |
                              | 0 1 |
                GeneratorMatrix => | 1 0 1 0 |
                                   | 0 1 1 1 |
                Generators => {{1, 0, 1, 0}, {0, 1, 1, 1}}
                ParityCheckMatrix => | 1 1 1 0 |
                                     | 0 1 0 1 |
                ParityCheckRows => {{1, 1, 1, 0}, {0, 1, 0, 1}}

o4 : LinearCode

i5 : C.GeneratorMatrix

o5 = | 1 0 1 0 |
     | 0 1 1 1 |

             2      4
o5 : Matrix F  <-- F

i6 : C.ParityCheckMatrix

o6 = | 1 1 1 0 |
     | 0 1 0 1 |

             2      4
o6 : Matrix F  <-- F

This is an example using the optional argument ParityCheck=>true.

i7 : F = GF(4,Variable => a);

i8 : L = {{1,0,a,0,0},{0,a,a+1,1,0},{1,1,1,a,0}};

i9 : M = matrix L;

             3      5
o9 : Matrix F  <-- F

i10 : C = linearCode(F,L,ParityCheck => true)

                                   5
o10 = LinearCode{AmbientModule => F                                                        }
                 BaseField => F
                 cache => CacheTable{}
                 Code => image | a 0 |
                               | 1 0 |
                               | 1 0 |
                               | 1 0 |
                               | 0 1 |
                 GeneratorMatrix => | a 1 1 1 0 |
                                    | 0 0 0 0 1 |
                 Generators => {{a, 1, 1, 1, 0}, {0, 0, 0, 0, 1}}
                 ParityCheckMatrix => | 1 0 a   0 0 |
                                      | 0 a a+1 1 0 |
                                      | 1 1 1   a 0 |
                 ParityCheckRows => {{1, 0, a, 0, 0}, {0, a, a + 1, 1, 0}, {1, 1, 1, a, 0}}

o10 : LinearCode

i11 : C.GeneratorMatrix

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

              2      5
o11 : Matrix F  <-- F

i12 : C.ParityCheckMatrix

o12 = | 1 0 a   0 0 |
      | 0 a a+1 1 0 |
      | 1 1 1   a 0 |

              3      5
o12 : Matrix F  <-- F

a module is given

Usage:

linearCode(M)
Inputs:
- M, a module,
Outputs:
- an instance of the type LinearCode, $C$

Given a submodule M of a free module F$^n$, where $F$ is a Galois field, this function returns a linear code $C$ whose ambient space is F$^n$.

If no optional input is specified, then the code $C$ is generated by the elements of M.

If the optional input ParityCheck => true is specified, then the code $C$ is the dual of the linear code generated by the elements of M.

i13 : F = GF 2; G = transpose matrix {apply({1,1,1,1},entry -> sub(entry,F))};

              4      1
o14 : Matrix F  <-- F

i15 : M = image G;

i16 : C = linearCode(M)

                                   4
o16 = LinearCode{AmbientModule => F                                           }
                 BaseField => F
                 cache => CacheTable{}
                 Code => image | 1 |
                               | 1 |
                               | 1 |
                               | 1 |
                 GeneratorMatrix => | 1 1 1 1 |
                 Generators => {{1, 1, 1, 1}}
                 ParityCheckMatrix => | 1 1 0 0 |
                                      | 1 0 1 0 |
                                      | 1 0 0 1 |
                 ParityCheckRows => {{1, 1, 0, 0}, {1, 0, 1, 0}, {1, 0, 0, 1}}

o16 : LinearCode

i17 : C.AmbientModule

       4
o17 = F

o17 : F-module, free

i18 : C.BaseField

o18 = F

o18 : GaloisField

i19 : C.GeneratorMatrix

o19 = | 1 1 1 1 |

              1      4
o19 : Matrix F  <-- F

i20 : C.ParityCheckMatrix

o20 = | 1 1 0 0 |
      | 1 0 1 0 |
      | 1 0 0 1 |

              3      4
o20 : Matrix F  <-- F

a module and a list are given

Usage:

linearCode(M,L)
Inputs:
- M, a module,
- L, a list,
Outputs:
- an instance of the type LinearCode, $C$

Given a free module M$=F^n$, where $F$ is a Galois field, and a non-empty list L of vectors of M, this function returns a linear code $C$ whose ambient space is $F^n$.

If no optional input is specified, then the code $C$ is generated by the vectors of L.

If the optional input ParityCheck => true is specified, then the code $C$ is the dual of the linear code generated by the vectors of L.

i21 : F = GF(4,Variable => a); M = F^5; L = {{1,0,a,0,0},{0,a,a+1,1,0},{1,1,1,a,0}};

i24 : C = linearCode(M,L)

                                   5
o24 = LinearCode{AmbientModule => F                                                   }
                 BaseField => F
                 cache => CacheTable{}
                 Code => image | 1 0   1 |
                               | 0 a   1 |
                               | a a+1 1 |
                               | 0 1   a |
                               | 0 0   0 |
                 GeneratorMatrix => | 1 0 a   0 0 |
                                    | 0 a a+1 1 0 |
                                    | 1 1 1   a 0 |
                 Generators => {{1, 0, a, 0, 0}, {0, a, a + 1, 1, 0}, {1, 1, 1, a, 0}}
                 ParityCheckMatrix => | 1 a+1 a+1 a+1 0 |
                                      | 0 0   0   0   1 |
                 ParityCheckRows => {{1, a + 1, a + 1, a + 1, 0}, {0, 0, 0, 0, 1}}

o24 : LinearCode

i25 : C.AmbientModule

       5
o25 = F

o25 : F-module, free

i26 : C.BaseField

o26 = F

o26 : GaloisField

i27 : C.Generators

o27 = {{1, 0, a, 0, 0}, {0, a, a + 1, 1, 0}, {1, 1, 1, a, 0}}

o27 : List

i28 : C.GeneratorMatrix

o28 = | 1 0 a   0 0 |
      | 0 a a+1 1 0 |
      | 1 1 1   a 0 |

              3      5
o28 : Matrix F  <-- F

i29 : C.ParityCheckMatrix

o29 = | 1 a+1 a+1 a+1 0 |
      | 0 0   0   0   1 |

              2      5
o29 : Matrix F  <-- F

i30 : C.Code

o30 = image | 1 0   1 |
            | 0 a   1 |
            | a a+1 1 |
            | 0 1   a |
            | 0 0   0 |

                              5
o30 : F-module, submodule of F

This is an example using the optional argument ParityCheck=>true.

i31 : F = GF(8,Variable =>a); M = F^4; L = {{a+1,a+1,a+1,a+1}};

i34 : C = linearCode(M,L,ParityCheck => true)

                                   4
o34 = LinearCode{AmbientModule => F                                      }
                 BaseField => F
                 cache => CacheTable{}
                 Code => image | 1 1 1 |
                               | 1 0 0 |
                               | 0 1 0 |
                               | 0 0 1 |
                 GeneratorMatrix => | 1 1 0 0 |
                                    | 1 0 1 0 |
                                    | 1 0 0 1 |
                 Generators => {{1, 1, 0, 0}, {1, 0, 1, 0}, {1, 0, 0, 1}}
                 ParityCheckMatrix => | a+1 a+1 a+1 a+1 |
                 ParityCheckRows => {{a + 1, a + 1, a + 1, a + 1}}

o34 : LinearCode

i35 : G = C.GeneratorMatrix

o35 = | 1 1 0 0 |
      | 1 0 1 0 |
      | 1 0 0 1 |

              3      4
o35 : Matrix F  <-- F

i36 : H = C.ParityCheckMatrix

o36 = | a+1 a+1 a+1 a+1 |

              1      4
o36 : Matrix F  <-- F

a Galois field and a list are given

Usage:

linearCode(F,L)
Inputs:
- F, a Galois field,
- L, a list,
Outputs:
- an instance of the type LinearCode, $C$

Given a Galois field F, and a non-empty list L of vectors of the same size and whose entries are coercible into the field F, this function returns a linear code $C$ over the field F.

If no optional input is specified, then the code $C$ is generated by the vectors of L.

If the optional input ParityCheck => true is specified, then the code $C$ is the dual of the linear code generated by the vectors of L.

i37 : F = GF 4; L = {{1,0,1,0},{1,0,1,0}};

i39 : C = linearCode(F,L)

                                   4
o39 = LinearCode{AmbientModule => F                                           }
                 BaseField => F
                 cache => CacheTable{}
                 Code => image | 1 1 |
                               | 0 0 |
                               | 1 1 |
                               | 0 0 |
                 GeneratorMatrix => | 1 0 1 0 |
                                    | 1 0 1 0 |
                 Generators => {{1, 0, 1, 0}, {1, 0, 1, 0}}
                 ParityCheckMatrix => | 0 1 0 0 |
                                      | 1 0 1 0 |
                                      | 0 0 0 1 |
                 ParityCheckRows => {{0, 1, 0, 0}, {1, 0, 1, 0}, {0, 0, 0, 1}}

o39 : LinearCode

i40 : C.GeneratorMatrix

o40 = | 1 0 1 0 |
      | 1 0 1 0 |

              2      4
o40 : Matrix F  <-- F

i41 : C.ParityCheckMatrix

o41 = | 0 1 0 0 |
      | 1 0 1 0 |
      | 0 0 0 1 |

              3      4
o41 : Matrix F  <-- F

This is an example using the optional argument ParityCheck=>true.

i42 : F = GF(9,Variable => a); L = {{1,0,a,0,0},{0,a,a+1,1,0},{1,1,1,a,0}};

i44 : C = linearCode(F,L,ParityCheck => true)

                                   5
o44 = LinearCode{AmbientModule => F                                                        }
                 BaseField => F
                 cache => CacheTable{}
                 Code => image | a-1 0 |
                               | 0   0 |
                               | a+1 0 |
                               | 1   0 |
                               | 0   1 |
                 GeneratorMatrix => | a-1 0 a+1 1 0 |
                                    | 0   0 0   0 1 |
                 Generators => {{a - 1, 0, a + 1, 1, 0}, {0, 0, 0, 0, 1}}
                 ParityCheckMatrix => | 1 0 a   0 0 |
                                      | 0 a a+1 1 0 |
                                      | 1 1 1   a 0 |
                 ParityCheckRows => {{1, 0, a, 0, 0}, {0, a, a + 1, 1, 0}, {1, 1, 1, a, 0}}

o44 : LinearCode

i45 : C.GeneratorMatrix

o45 = | a-1 0 a+1 1 0 |
      | 0   0 0   0 1 |

              2      5
o45 : Matrix F  <-- F

i46 : C.ParityCheckMatrix

o46 = | 1 0 a   0 0 |
      | 0 a a+1 1 0 |
      | 1 1 1   a 0 |

              3      5
o46 : Matrix F  <-- F

a Galois field, a positive integer and a list are given

Usage:

linearCode(F,n,L)
Inputs:
- F, a Galois field,
- n, an integer,
- L, a list,
Outputs:
- an instance of the type LinearCode, $C$

Given a Galois field F, a positive integer n, and a non-empty list L of vectors of size n and entries that are coercible into the field F, this function returns a linear code $C$ of length n over the field F.

If no optional input is specified, then the code $C$ is generated by the vectors of L.

If the optional input ParityCheck => true is specified, then the code $C$ is the dual of the linear code generated by the vectors of L.

i47 : F = GF 4; n = 4; L = {{1,0,1,0},{1,0,1,0}};

i50 : C = linearCode(F,n,L)

                                   4
o50 = LinearCode{AmbientModule => F                                           }
                 BaseField => F
                 cache => CacheTable{}
                 Code => image | 1 1 |
                               | 0 0 |
                               | 1 1 |
                               | 0 0 |
                 GeneratorMatrix => | 1 0 1 0 |
                                    | 1 0 1 0 |
                 Generators => {{1, 0, 1, 0}, {1, 0, 1, 0}}
                 ParityCheckMatrix => | 0 1 0 0 |
                                      | 1 0 1 0 |
                                      | 0 0 0 1 |
                 ParityCheckRows => {{0, 1, 0, 0}, {1, 0, 1, 0}, {0, 0, 0, 1}}

o50 : LinearCode

i51 : C.GeneratorMatrix

o51 = | 1 0 1 0 |
      | 1 0 1 0 |

              2      4
o51 : Matrix F  <-- F

i52 : C.ParityCheckMatrix

o52 = | 0 1 0 0 |
      | 1 0 1 0 |
      | 0 0 0 1 |

              3      4
o52 : Matrix F  <-- F

This is an example using the optional argument ParityCheck=>true.

i53 : F = GF(9,Variable => a); n = 5; L = {{1,0,a,0,0},{0,a,a+1,1,0},{1,1,1,a,0}};

i56 : C = linearCode(F,n,L,ParityCheck => true)

                                   5
o56 = LinearCode{AmbientModule => F                                                        }
                 BaseField => F
                 cache => CacheTable{}
                 Code => image | a-1 0 |
                               | 0   0 |
                               | a+1 0 |
                               | 1   0 |
                               | 0   1 |
                 GeneratorMatrix => | a-1 0 a+1 1 0 |
                                    | 0   0 0   0 1 |
                 Generators => {{a - 1, 0, a + 1, 1, 0}, {0, 0, 0, 0, 1}}
                 ParityCheckMatrix => | 1 0 a   0 0 |
                                      | 0 a a+1 1 0 |
                                      | 1 1 1   a 0 |
                 ParityCheckRows => {{1, 0, a, 0, 0}, {0, a, a + 1, 1, 0}, {1, 1, 1, a, 0}}

o56 : LinearCode

i57 : C.GeneratorMatrix

o57 = | a-1 0 a+1 1 0 |
      | 0   0 0   0 1 |

              2      5
o57 : Matrix F  <-- F

i58 : C.ParityCheckMatrix

o58 = | 1 0 a   0 0 |
      | 0 a a+1 1 0 |
      | 1 1 1   a 0 |

              3      5
o58 : Matrix F  <-- F

a prime number, two positive integers and a list are given

Usage:

linearCode(p,r,n,L)
Inputs:
- p, an integer,
- r, an integer,
- n, an integer,
- L, a list,
Outputs:
- an instance of the type LinearCode, $C$

Given a prime number p, positive integers r and n, and a non-empty list L of vectors of size n and entries that are coercible into the Galois field GF$(\mathtt{p}^\mathtt{r})$, this function returns a linear code $C$ of length n over the Galois field GF$(\mathtt{p}^\mathtt{r})$.

If no optional input is specified, then the code $C$ is generated by the vectors of L.

If the optional input ParityCheck => true is specified, then the code $C$ is the dual of the linear code generated by the vectors of L.

i59 : p = 2; r = 2; n=4; L = {{1,0,1,0},{0,1,1,1}};

i63 : C=linearCode(p,r,n,L)

                                        4
o63 = LinearCode{AmbientModule => (GF 4)                        }
                 BaseField => GF 4
                 cache => CacheTable{}
                 Code => image | 1 0 |
                               | 0 1 |
                               | 1 1 |
                               | 0 1 |
                 GeneratorMatrix => | 1 0 1 0 |
                                    | 0 1 1 1 |
                 Generators => {{1, 0, 1, 0}, {0, 1, 1, 1}}
                 ParityCheckMatrix => | 1 1 1 0 |
                                      | 0 1 0 1 |
                 ParityCheckRows => {{1, 1, 1, 0}, {0, 1, 0, 1}}

o63 : LinearCode

i64 : p = 3; r = 2; n = 5;

i67 : ambient GF(p,r)

         ZZ
         --[a]
          3
o67 = ----------
       2
      a  - a - 1

o67 : QuotientRing

i68 : L = {{1,0,a,0,0},{0,a,a+1,1,0},{1,1,1,a+1,0}};

i69 : C=linearCode(p,r,n,L)

                                        5
o69 = LinearCode{AmbientModule => (GF 9)                                                  }
                 BaseField => GF 9
                 cache => CacheTable{}
                 Code => image | 1 0   1   |
                               | 0 a   1   |
                               | a a+1 1   |
                               | 0 1   a+1 |
                               | 0 0   0   |
                 GeneratorMatrix => | 1 0 a   0   0 |
                                    | 0 a a+1 1   0 |
                                    | 1 1 1   a+1 0 |
                 Generators => {{1, 0, a, 0, 0}, {0, a, a + 1, 1, 0}, {1, 1, 1, a + 1, 0}}
                 ParityCheckMatrix => | 1 -1 -a+1 -a 0 |
                                      | 0 0  0    0  1 |
                 ParityCheckRows => {{1, -1, - a + 1, -a, 0}, {0, 0, 0, 0, 1}}

o69 : LinearCode

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.

Ways to use linearCode :

linearCode(GaloisField,List)
linearCode(GaloisField,ZZ,List)
linearCode(Matrix)
linearCode(Module)
linearCode(Module,List)
linearCode(ZZ,ZZ,ZZ,List)

For the programmer

The object linearCode is a method function with options.

cyclicCode -- cyclic codes
dualCode -- dual of a code
genericCode -- ambient space of a code
hammingCode -- generates a Hamming code
locallyRecoverableCode -- constructs a locally recoverable code (LRC)
ParityCheck -- an optional input for the linearCode constructor
randomCode -- constructs a random linear code over a finite field
repetitionCode -- repetition code
shorten -- shortens a code
universeCode -- linear code $\mathtt{F}^\mathtt{n}$
zeroCode -- zero code
zeroSumCode -- linear code in which the entries of each codeword add up zero

linearCode -- functions to construct linear codes over Galois fields

Synopsis

Description

a matrix is given

a module is given

a module and a list are given

a Galois field and a list are given

a Galois field, a positive integer and a list are given

a prime number, two positive integers and a list are given

Caveat

Ways to use linearCode :

For the programmer

Menu

Constructions of linear codes