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 and Parity Check Matrices (ex-7ec540)

Run in calculator (opens in a new tab)

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 (opens in a new tab)

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 of a Code (ex-8132b6)

Run in calculator (opens in a new tab)

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 (opens in a new tab)

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 and Check Polynomials (ex-889cde)

Run in calculator (opens in a new tab)

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 (opens in a new tab)