Invariants of a Code#

Basic Numerical Invariants#

Length(C): Code -> RngIntElt#: Given an \([n, k]\) code \(C\), return the block length \(n\) of \(C\).

Dimension(C): Code -> RngIntElt#
NumberOfGenerators(C): Code -> RngIntElt#: The dimension \(k\) of the \([n, k]\) linear code \(C\).

# C: Code -> RngIntElt#: Given a code \(C\), return the number of codewords belonging to \(C\).

InformationRate(C): Code -> FldPrElt#: The information rate of the \([n, k]\) code \(C\). This is the ratio \(k/n\).

The Ambient Space and Alphabet#

AmbientSpace(C): Code -> ModTupRng#: The ambient space of the code \(C\), i.e. the generic \(R\)-space \(V\) in which \(C\) is contained.

RSpace(C): Code -> ModTupRng#
VectorSpace(C): Code -> ModTupFld#: Given an \([n, k]\) linear code \(C\), defined as a subspace \(U\) of the \(n\)-dimensional space \(V\), return \(U\) as a subspace of \(V\) with basis corresponding to the rows of the generator matrix for \(C\).

Generic(C): Code -> Code#: Given an \([n, k]\) code \(C\), return the generic \([n, n, 1]\) code in which \(C\) is contained.

Alphabet(C): Code -> Rng#
Field(C): Code -> Rng#: The underlying ring (or alphabet) \(R\) of the code \(C\).

The Code Space#

GeneratorMatrix(C): Code -> ModMatFldElt#
BasisMatrix(C): Code -> ModMatRngElt#: The generator matrix for the linear code \(C\), returned as an element of \({\operatorname{Hom}}(U, V)\) where \(U\) is the information space of \(C\) and \(V\) is the ambient space of \(C\).

Basis(C): Code -> [ ModTupRngElt ]#: The current vector space basis for the linear code \(C\), returned as a sequence of elements of \(C\).

Generators(C): Code -> { ModTupFldElt }#: The current vector space basis for the linear code \(C\), returned as a set of elements of \(C\).

C . i: Code, RngIntElt -> ModTupFldElt#: Given an \([n, k]\) code \(C\) and a positive integer \(i\), \(1 \le i \le k\), return the \(i\)-th element of the current basis of \(C\).

The Dual Space#

Dual(C): Code -> Code#: The code that is dual to the code \(C\).

ParityCheckMatrix(C): Code -> ModMatFldElt#: The parity check matrix for the code \(C\), returned as an element of \({\operatorname{Hom}}(V, U)\).

Example: Generator Matrix (ex-7ec540)#

We create a Reed–Muller code and demonstrate some simple relations.

> R := ReedMullerCode(1, 3);
> R;
[8, 4, 4] Reed-Muller Code (r = 1, m = 3) over GF(2)
Generator matrix:
[1 0 0 1 0 1 1 0]
[0 1 0 1 0 1 0 1]
[0 0 1 1 0 0 1 1]
[0 0 0 0 1 1 1 1]
> G := GeneratorMatrix(R);
> P := ParityCheckMatrix(R);
> P;
[1 0 0 1 0 1 1 0]
[0 1 0 1 0 1 0 1]
[0 0 1 1 0 0 1 1]
[0 0 0 0 1 1 1 1]
> G * Transpose(P);
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
> D := LinearCode(P);
> Dual(R) eq D;
true

Run in calculator

Hull(C): Code -> Code#: The Hull of a code is the intersection between itself and its dual.

The Information Space and Information Sets#

InformationSpace(C): Code -> ModTupFld#: Given an \([n, k]\) linear code \(C\), return the \(k\)-dimensional \(R\)-space \(U\) which is the space of information vectors for the code \(C\).

InformationSet(C): Code -> [ RngIntElt ]#: Given an \([n, k]\) linear code \(C\) over a finite field, return the current information set for \(C\). The information set for \(C\) is an ordered set of \(k\) linearly independent columns of the generator matrix, such that the generator matrix is the identity matrix when restricted to these columns. The information set is returned as a sequence of \(k\) integers, giving the numbers of the columns that correspond to the information set.

AllInformationSets(C): Code -> [ [ RngIntElt ] ]#: Given an \([n, k]\) linear code \(C\) over a finite field, return all the possible information sets of \(C\) as a (sorted) sequence of sequences of column indices. Each inner sequence contains a maximal set of indices of linearly independent columns in the generator matrix of \(C\).

StandardForm(C): Code -> Code, Map#

Given an \([n, k]\) linear code \(C\) over a finite field, return the standard form \(D\) of \(C\). A code is in standard form if the first \(k\) components of the code words correspond to the information set. Magma returns one of the many codes in standard form which is isomorphic to \(C\). (The same code is returned each time.) Thus, the effect of this function is to return a code \(D\) whose generators come from the generator matrix of \(C\) with its columns permuted, so that the submatrix consisting of the first \(k\) columns of the generator matrix for \(D\) is the identity matrix. Two values are returned: The standard form code \(D\);

(b): An isomorphism from \(C\) to \(D\).

Example: Standard Form (ex-8132b6)#

We construct a Reed–Muller code \(C\) and its standard form \(S\) and then map a codeword of \(C\) into \(S\).

> C := ReedMullerCode(1, 4);
> C;
[16, 5, 8] Reed-Muller Code (r = 1, m = 4) over GF(2)
Generator matrix:
[1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1]
[0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
[0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1]
[0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1]
[0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1]
> InformationSet(C);
[ 1, 2, 3, 5, 9 ]
> #AllInformationSets(C);
2688
> S, f := StandardForm(C);
> S;
[16, 5, 8] Linear Code over GF(2)
Generator matrix:
[1 0 0 0 0 1 1 1 0 1 1 0 1 0 0 1]
[0 1 0 0 0 1 1 0 1 1 0 1 0 1 0 1]
[0 0 1 0 0 1 0 1 1 0 1 1 0 0 1 1]
[0 0 0 1 0 0 1 1 1 0 0 0 1 1 1 1]
[0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1]
> u := C.1;
> u;
(1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1)
> f(u);
(1 0 0 0 0 1 1 1 0 1 1 0 1 0 0 1)

Run in calculator

The Syndrome Space#

SyndromeSpace(C): Code -> ModTupFld#: Given an \([n, k]\) linear code \(C\), return the \((n-k)\)-dimensional vector space \(W\), which is the space of syndrome vectors for the code \(C\).

The Generator Polynomial#

The operations in this section are restricted to cyclic codes.

GeneratorPolynomial(C): Code -> RngUPolElt#: Given a cyclic code \(C\) over a finite field, return the generator polynomial of \(C\). The generator polynomial of \(C\) is a divisor of \(x^n - 1\), where \(n\) is the length of \(C\).

CheckPolynomial(C): Code -> RngUPolElt#: Given a cyclic code \(C\) over a finite field, return the check polynomial of \(C\) as an element of \(K[x]\). If \(g(x)\) is the generator polynomial of \(C\) and \(h(x)\) is the check polynomial of \(C\), then \(g(x)h(x) = 0\) (mod \(x^n - 1\)), where \(n\) is the length of \(C\).

Idempotent(C): Code -> RngUPolElt#: Given a cyclic code \(C\), return the (polynomial) idempotent of \(C\). If \(c(x)\) is the idempotent of \(C\), then \(c(x)^{2} = c(x)\) (mod \(x^n - 1\)), where \(n\) is the length of \(C\).

Example: Generator Polynomial (ex-889cde)#

We find the generator and check polynomials for the third order Hamming code over GF(2).

> K<w> := GF(2);
> P<x> := PolynomialRing(K);
> H := HammingCode(K, 3);
> g := GeneratorPolynomial(H);
> g;
x^3 + x + 1
> h := CheckPolynomial(H);
> h;
x^4 + x^2 + x + 1
> g*h mod (x^7 - 1);
0
> forall{ c : c in H | h * P!Eltseq(c) mod (x^7-1) eq 0 };
true
> e := Idempotent(H);
> e;
x^4 + x^2 + x
> e^2;
x^8 + x^4 + x^2

Run in calculator