First we want to introduce the dual code $C^{\perp}$ of a linear code $C$. To this end we have to introduce an inner product. For words $v, w \in \mathbb{Z}{2}^{n}$ we define the inner product $$=\sum{i=1}^{n} v_{i} w_{i}$$
Let $C$ be a linear binary code of length $n$ and dimension $k$. The dual code $C^{\perp}$ is defined as
$$C^{\perp}=\left{v \in \mathbb{Z}_{2}^{n}:=0 \text { for all } u \in C\right}$$
Show that $C^{\perp}$ defines indeed a linear binary code of length $n$, provided $\left|C^{\perp}\right| \geq 2 .$
The next theorem gives the relationship between a code and its dual in terms of the generator and parity check matrices.

Let $C$ be a linear binary code of length $n$ and dimension $k<n$. Then $C^{\perp}$ is a linear binary code of length $n$ and dimension $n-k$. Moreover, $H$ is a parity check matrix for $C$ if and only if $H$ is a generator matrix for $C^{\perp}$.

As a reminder of Theorem $14.3$, if $C$ has a generator matrix $G$ in standard form $G=$ $\left(I_{k} \quad A\right)$ then
$$\left(\begin{array}{ll} A^{t r} & I_{n-k} \end{array}\right)$$
is a parity check matrix for $C$.

Show that $\left(C^{\perp}\right)^{\perp}=C$. (Hint: Clearly $C \subset\left(C^{\perp}\right)^{\perp}$, for the other inclusion compare dimensions.) Conlcude that $H$ is a parity check matrix for $C^{\perp}$ if and only if $H$ is a generator matrix for $C$.

For example, if $G=\left(I_{k} \quad A\right)$ is the standard form generator matrix for the square code, then applying Theorem $14.3$ to $G$, we get the parity check matrix already found in Example $14.2(2)$
Example 16.5. Let $C_{\text {ext }}$ be as in (1). Then
$$C_{\text {ext }}^{\perp}={00000,11111}$$
is the binary repetition code of length 5 , and
$${00000,11111}^{\perp}=C_{\text {ext }}$$

Categories: 数学代写