HaCkEd By KaSpEr511

Parity Check Matrix and Dual Codes

July 6th, 2009

In the first post, the reason why we introduce the encoding process is so that the receiver realize if she get an altered message. Now in the other post, we introduce encoding process by using an encoding matrix $G$ . How does the receiver recognize if an error has taken place?

Note that we can consider the $n\times k$ matrix $G^T$ as a map

$\begin{aligned}G&:\mathbb{Z}_2^n\rightarrow \mathbb{Z}_2^k\\&:u\rightarrow uG^t\end{aligned}$ .

We know that $\text{ rank }G^t=k$ , hence by the rank-nullity theorem, the nullity of $G^t$ is $n-k$ . Let $H$ be the $n-k\times n$ matrix where its rows are basis of null space of $G^t$ . We call this matrix $H$ as the parity check matrix. Clearly $HG^t=0$ or equivalently $GH^t=0$ . Remember that every codeword is of the form $uG$ for some $u$ , hence if $x$ is a valid codeword then $x=uG$ for some $u$ and this implies that $xH^t=0$ . This gives the receiver a simple procedure whether the received message is a valid codeword or not. If the receiver get the message $y$ but $yH^t\neq 0$ then she knows that $y$ is not a valid codeword. There is an error on it and the receiver can ask for a retransmission.

Let $\mathcal{C}$ be an $[n,k]$ matrix and let $G$ be a generator matrix of $\mathcal{C}$ . Let $H$ be a parity check matrix as above. We have seen that $GH^T=0$ . Hence $\mathcal{C}$ is in the kernel of $H^t$ . But since the rank of $H^t$ is $n-k$ , then the rank of the kernel of $H^t$ , i.e. the nullity of $H^t$ is $n$ . Since $\mathcal{C}$ also of dimension $n$ , then two must equal. So every codes has two representation: as the image of generating matrix $G$ and as the kernel of $H^T$ - the transpose of parity check matrix $H$ .

Dual Codes

Let $\mathcal{C}$ be an $[n,k]$ code with $G$ and $H$ are its generator and parity check matrix. Let $x\cdot y$ denotes the dot product between $x$ and $y$ . We define the dual code of $\mathcal{C}$ as $\mathcal{C}^\perp$

$\mathcal{C}^\perp =\{x\mid x\cdot y=0 \quad\forall y\in \mathcal{C}\}$ .

Now if $\{v_1,\cdots,v_k\}$ is a basis of $\mathcal{C}$ , then $\mathcal{C}^\perp=\{x\mid x\cdot v_i=0 \quad \forall i=1,\cdots,k\}$ .

One can easily verify, that $\mathcal{C}^\perp$ is a vector space.

Note that we can write the dot product $x\cdot y$ as $xy^t$ . Now since the rows of $G$ are basis of $G$ and $HG^t=0$ . Then every vector of the form $uH$ is in $\mathcal{C}^\perp$ and conversely if $x\in \mathcal{C}^\perp$ we have $xG^t=0$ . So $x\in \text{ker } G^t= \text{im }H$ . Therefore $H$ is the generator matrix of $\mathcal{C}^\perp$ and one can verify that $G$ is the parity check matrix of $\mathcal{C}^\perp$ .