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.6.1   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.6.2   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.6.3   Let $C$ be a linear code. A parity check matrix of $C$ exists.

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

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