Linear codes

Posted on 2024-02-28

Dual codes and weight enumerators

Consider a [n,k]q-code C, and write ,:Fqn×FqnFq for the standard inner product; if e1,,en are the standard basis vectors, then we have ei,ej=δij.

We write C for the dual code to C defined by the rule C={wFqnw,C=0}={wFqnw,x=0xC}.

Observe that the natural mapping FqnC given by w,w=(xx,w) is a surjection with kernel C. It thus follows that dimC=ndimC=ndimC=nk.

In particular, C is an [n,nk]q-code.

Remark

If C=C, we say that C is self-dual. Note that if C is self dual we must have k=nk so that n=2k is even.

For example, the following is a self-dual [8,4]2 code.

k = GF(2)
V = VectorSpace(k,8)

C = V.subspace([V([1,0,0,0,1,1,1,0]),
                V([0,1,0,0,1,1,0,1]),
                V([0,0,1,0,1,0,1,1]),
                V([0,0,0,1,0,1,1,1])])

# generator matrix
G = MatrixSpace(k,4,8).matrix(C.basis())

G * G.T
=>

[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]

We see for this example that CC and thus C=C since dimC=4=84=dimC.

Weight enumerators

Consider the polynomial with natural-number coefficients A(T)=uCTweight(u)N[T].

We evidently have A(T)=i=0nAiTi=1+i=1nAiTi where Ai=#{uCweight(u)=i} (note that A0=1). We call A(T) the weight-enumerator polynomial of C.

Example
Consider the self-dual [8,4]2-code C introduced above; namely:
 k = GF(2)
 V = VectorSpace(k,8)
 
 C = V.subspace([V([1,0,0,0,1,1,1,0]),
                 V([0,1,0,0,1,1,0,1]),
                 V([0,0,1,0,1,0,1,1]),
                 V([0,0,0,1,0,1,1,1])])

We compute its weight-enumerator:

R.<T> = PolynomialRing(ZZ)
 
## compute the weight enumerator, as an element of R
def WE(C):
    return sum([ T^weight(c) for c in C ])

WE(C)
=>
T^8 + 14*T^4 + 1	

Write A(T) for the weight enumerator. We are going to prove a formula relating A(T) and A(T) due to McWilliams.

The proof involves some character theory. We need a few extra tools.

Characters of Fq-vector spaces.

Let tr:FqFp be the trace map.

For any finite degree field extension EF we have a trace mapping tr:EF; for αE, tr(α) is the trace of the F-linear mapping EE given by xαx.

Proposition
If EF is a finite Galois extension, and if Γ=Gal(E/F) is the galois group, then for αE we have tr(α)=σΓσ(α).
Proposition
If q=p2, then tr:FqFp is given by the formula tr(α)=α+αp+αp2++αps1.

The importance to us of the trace mapping is this: we know how to describe complex characters of Fp, and we use these together with the trace to describe complex characters of Fq.

Fix ζp=exp(2πip)C×.

For a vector uFqn, we define a group homomorphism (“character”) χu:FqnC× by the rule χu(v)=ζptr(u,v)=exp(2πiptr(u,v))

Observe that since tr(α)Fp=Z/pZ for αFq, the complex number ζptr(α) is always well-defined.

Remark
Arguing as in an earlier homework exercise, it is easy to see that Fqn^=Hom(Fqn,C×)={χuuFqn}.

For a finite abelian group A, recall that we write χ,ϕA=1|A|aAχ(a)ϕ(a) for the character inner product; here χ,ϕA^=Hom(A,C×).

We have the following result from character theory:

Proposition
For xFqn, we have uCχu(x){0if xC|C|if xC
Proof

We know that χuC is a character of C; i.e. an element of C^.

Now, uCχu(x)=uCζptr(u,x)=uCχx(u)=|C|χx,1CC={|C|if χx=1C0otherwise where 1C denotes the trivial homomorphism CC×.

Now the result follows from the observation that χx=1C if and only x,u=0uC if and only if xC.

Theorem (McWilliams’ Identity)
If C is an [n,k]q-code, then qkA(T)=(1+(q1)T)nA(1T1+(q1)T).
Proof
see (Ball 2020, Theorem 4.13 page 56)

Bibliography

Ball, Simeon. 2020. A Course in Algebraic Error-Correcting Codes. Compact Textbooks in Mathematics. Cham: Springer International Publishing. https://doi.org/10.1007/978-3-030-41153-4.