The dual code

The space of all vectors orthogonal to a code $C$ is another code. Since the ground field is finite, it is possible for all the codewords in a code to be orthogonal to themselves!

Definition 3.4.29   If $C$ is a $[n,k]$-code then the dual code $C^\perp$ is a $[n,n-k]$-code defined by

$$C^\perp = \{ {\bf v}\in F^n\ \vert\ {\bf v}\cdot {\bf c}=0, \ \forall {\bf c}\in C\},$$

where

$${\bf v}\cdot {\bf w}=v_1w_1+v_2w_2+...+v_nw_n\in F,$$

for all ${\bf v}=(v_1,...,v_n)$ and ${\bf w}=(w_1,...,w_n)$.

Example 3.4.30   As a very simple example, let $C$ be the binary repetition code of length $2$:

$$C:=\{(0,0),(1,1)\}.$$

This is self-dual: $C=C^\perp$.

Finally, we can show that a parity check matrix exists.

Proposition 3.4.31   Let $C$ be a linear code. A parity check matrix of $C$ exists.

proof: Any generating matrix for $C^\perp$ is a parity check matrix of $C$. $\Box$

Exercise 3.4.32   Show $(C^\perp)^\perp = C$.