2024-02-28--linear.md

---

title: Linear codes
date: 2024-02-28

---

\newcommand{\F}{\mathbb{F}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\NN}{\mathbb{N}} \newcommand{\CC}{\mathbb{C}} \newcommand{\e}{\mathbf{e}} \newcommand{\h}{\mathbf{h}} \newcommand{\bb}{\mathbf{b}} \newcommand{\vv}{\mathbf{v}} \newcommand{\xx}{\mathbf{x}}

\newcommand{\uu}{\mathbf{u}} \newcommand{\ww}{\mathbf{w}}

\newcommand{\Null}{\operatorname{Null}} \newcommand{\Hom}{\operatorname{Hom}}

\newcommand{\weight}{\operatorname{weight}}

\newcommand{\PP}{\mathbb{P}}

\newcommand{\dist}{\operatorname{dist}} \newcommand{\floor}[1]{\lfloor #1 \rfloor}

\newcommand{\tr}{\operatorname{tr}}

Dual codes and weight enumerators

Consider a $[n,k]_q$-code $C$, and write ParseError: KaTeX parse error: Undefined control sequence: \F at position 31: …\cdot \rangle: \̲F̲_q^n \times \F_… for the standard inner product; if ParseError: KaTeX parse error: Undefined control sequence: \e at position 1: \̲e̲_1,\cdots,\e_n are the standard basis vectors, then we have ParseError: KaTeX parse error: Undefined control sequence: \e at position 9: \langle \̲e̲_i,\e_j \rangle…

We write $C^\perp$ for the dual code to $C$ defined by the rule ParseError: KaTeX parse error: Undefined control sequence: \ww at position 14: C^\perp = \{ \̲w̲w̲ ̲\in \F_q^n \mid…

Observe that the natural mapping ParseError: KaTeX parse error: Undefined control sequence: \F at position 1: \̲F̲_q^n \to C^* given by ParseError: KaTeX parse error: Undefined control sequence: \ww at position 1: \̲w̲w̲ ̲\mapsto \langle… is a surjection with kernel $C^\perp$. It thus follows that $$\dim C^\perp = n - \dim C^* = n - \dim C = n -k.$$

In particular, $C^\perp$ is an $[n,n-k]_q$-code.

Remark : If $C = C^\perp$, we say that $C$ is self-dual. Note that if $C$ is self dual we must have $k = n-k$ so that $n = 2k$ is even.

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

``` python
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 $C \subset C^\perp$ and thus $C =
C^\perp$ since $\dim C = 4 = 8-4 = \dim C^\perp$.

Weight enumerators

Consider the polynomial with natural-number coefficients ParseError: KaTeX parse error: Undefined control sequence: \uu at position 14: A(T) = \sum_{\̲u̲u̲ ̲\in C} T^{\weig…

We evidently have $$A(T) = \sum_{i=0}^n A_i T^i = 1 + \sum_{i=1}^n A_i T^i$$ where ParseError: KaTeX parse error: Undefined control sequence: \uu at position 11: A_i = \#\{\̲u̲u̲ ̲\in C \mid \wei… (note that $A_0 = 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^\perp(T)$ for the weight enumerator. We are going to prove a formula relating $A(T)$ and $A^\perp(T)$ due to McWilliams.

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

Characters of ParseError: KaTeX parse error: Undefined control sequence: \F at position 1: \̲F̲_q-vector spaces.

Let ParseError: KaTeX parse error: Undefined control sequence: \tr at position 1: \̲t̲r̲:\F_q \to \F_p be the trace map.

For any finite degree field extension $E \supset F$ we have a trace mapping ParseError: KaTeX parse error: Undefined control sequence: \tr at position 1: \̲t̲r̲:E \to F; for $\alpha \in E$, ParseError: KaTeX parse error: Undefined control sequence: \tr at position 1: \̲t̲r̲(\alpha) is the trace of the $F$-linear mapping $E \to E$ given by $x \mapsto \alpha x$.

Proposition : If $E \supset F$ is a finite Galois extension, and if $\Gamma = \operatorname{Gal}(E/F)$ is the galois group, then for $\alpha \in E$ we have ParseError: KaTeX parse error: Undefined control sequence: \tr at position 1: \̲t̲r̲(\alpha) = \sum…

Proposition : If $q = p^2$, then ParseError: KaTeX parse error: Undefined control sequence: \tr at position 1: \̲t̲r̲:\F_q \to \F_p is given by the formula ParseError: KaTeX parse error: Undefined control sequence: \tr at position 1: \̲t̲r̲(\alpha) = \alp…

The importance to us of the trace mapping is this: we know how to describe complex characters of ParseError: KaTeX parse error: Undefined control sequence: \F at position 1: \̲F̲_p, and we use these together with the trace to describe complex characters of ParseError: KaTeX parse error: Undefined control sequence: \F at position 1: \̲F̲_q.

Fix $\zeta_p = \exp\left ( \dfrac{2\pi i}{p} \right) \in \CC^\times.$

For a vector ParseError: KaTeX parse error: Undefined control sequence: \uu at position 1: \̲u̲u̲ ̲\in \F_q^n, we define a group homomorphism ("character") ParseError: KaTeX parse error: Undefined control sequence: \uu at position 6: \chi_\̲u̲u̲:\F_q^n \to \CC… by the rule ParseError: KaTeX parse error: Undefined control sequence: \uu at position 6: \chi_\̲u̲u̲(\vv) = \zeta_p…

Observe that since ParseError: KaTeX parse error: Undefined control sequence: \tr at position 1: \̲t̲r̲(\alpha) \in \F… for ParseError: KaTeX parse error: Undefined control sequence: \F at position 12: \alpha \in \̲F̲_q, the complex number ParseError: KaTeX parse error: Undefined control sequence: \tr at position 10: \zeta_p^{\̲t̲r̲(\alpha)} is always well-defined.

Remark : Arguing as in an earlier homework exercise, it is easy to see that ParseError: KaTeX parse error: Undefined control sequence: \F at position 10: \widehat{\̲F̲_q^n} = \Hom(\F….

For a finite abelian group $A$, recall that we write $$\langle \chi,\phi \rangle_A = \dfrac{1}{|A|} \sum_{a \in A} \chi(a) \overline{\phi(a)}$$ for the character inner product; here $\chi,\phi \in \widehat{A} = \Hom(A,\CC^\times)$.

We have the following result from character theory:

Proposition : For ParseError: KaTeX parse error: Undefined control sequence: \xx at position 1: \̲x̲x̲ ̲\in \F_q^n, we have $$\sum_{\uu \in C} \chi_\uu(\xx) \left \{ \begin{matrix} 0 & \text{if $\xx \not \in C^\perpParseError: KaTeX parse error: Expected 'EOF', got '}' at position 1: }̲ \\ |C| & \tex…\xx \in C^\perpParseError: KaTeX parse error: Expected 'EOF', got '}' at position 1: }̲ \end{matrix…$

Proof : We know that ParseError: KaTeX parse error: Undefined control sequence: \uu at position 6: \chi_\̲u̲u̲\mid_C is a character of $C$; i.e. an element of $\widehat{C}$.

Now,
\begin{align*}
\sum_{\uu \in C} \chi_\uu(\xx) &= \sum_{\uu \in C} \zeta_p^{\tr(\langle \uu, \xx \rangle )} 
= \sum_{u \in C} \chi_\xx(\uu) \\
&= |C| \langle \chi_\xx, \mathbf{1}_C \rangle_C \\
&= \left \{ \begin{matrix} |C|  & \text{if $\chi_\xx = \mathbf{1}_C$} \\ 
0 & \text{otherwise}
\end{matrix} \right .
\end{align*}
where $\mathbf{1}_C$ denotes the trivial homomorphism $C \to \CC^\times$.

Now the result follows from the observation that $\chi_\xx = \mathbf{1}_C$ if and only
$\langle \xx,\uu \rangle = 0 \quad \forall \uu \in C$ if and only if $\xx \in C^\perp$.

Theorem (McWilliams' Identity) : If $C$ is an $[n,k]_q$-code, then $$q^k A^\perp(T) = (1 + (q-1)T)^n \cdot A\left(\dfrac{1-T}{1+(q-1)T}\right).$$

Proof : see [@ballCourseAlgebraicErrorCorrecting2020, Theorem 4.13 page 56]

Bibliography

::: {.refs} :::