Hamming Codes

One Good Code is the Hamming Code (it's a ``perfect code").
Define Hamming Code in terms of Its parity check matrix:
*n= $\frac{q^n-1}{q-1}$ $n-k=$ dimension of the code. *parity check matrix has all columns pairwise linearly independent. Ex q=2, k=3, working over $\mathbb{F}_{2}$
n= $\frac{q^3-1}{q-1}=\frac{2^3-1}{2-1}=7$
$\mathbb{F}_{2}^4\longrightarrow\mathbb{F}_{2}^7$

Ex q=2, k=2, n= $\frac{2^2-1}{2-1}=3$ $\mathbb{F}_{2}^1\rightarrow\mathbb{F}_{2}^3$

$$H = (1 1 1 1 1)$$

$$= (-P^t I_{n-(n-k)} )$$

$$= (-P^t I_k)$$

$$= (-P^t \begin{array}{cc}1&0 0&1 \end{array}) k=2$$

$$= \left( \begin{array}{c\vert cc} 1&1&0 1&0&1 \end{array}\right) \textrm{ over } \mathbb{F}_{2}$$

$-P^t= {1 \choose 1}$ P=(-1 -1)
G=($I_{dim}$ P)= ($I_{n-k}$ P)= ($I_1$ P)= (1 -1 -1)
C=span( $\left( \begin{array}{c}1 -1 -1 \end{array}\right)$ )
$\mathbb{F}_{2}^1\rightarrow\mathbb{F}_{2}^3$
(1) $\rightarrow \left( \begin{array}{c}1 -1 -1 \end{array}\right)$ G= generating matrix $\left( \begin{array}{c}\vec c_1t \vec c_2t \vec c_3t \end{array}\right) = \left( \begin{array}{cccc} 1&0&0&1 0&1&0&1 0&0&1&1 \end{array}\right)\\ =$rows of a generating matrix for a basis for the codewords. This matrix is in reduced-echelon form, and if not we can make it so.
$\therefore$ write G = ($I_k$ P) is an n$x$k matrix. $I_k$ is the identity matrix for a k-dimensional code, and there are n rows because the code is a subspace of $\mathbb{F}_{2}^n$. C will always reduce to a reduced echelon matrix or the columns wouldn't be independent and C wouldn't be a code. H= parity check matrix = ($P^t$ $I_{n-k}$) G= ($I_k$ P) Ex Parity $\mathbb{F}_{q}^3 \longrightarrow \mathbb{F}_{q}^4$

$$G = \left( \begin{array}{ccc\vert c} 1&0&0&1 0&1&0&1 0&0&1&1 \end{array}\right)$$

$$G = \left(I_k \vert P\right)$$

$$P = \left( \begin{array}{c}1 1 1 \end{array}\right)$$

$$P^t = ( 1 1 1 )$$

$$-P^t = ( -1 -1 -1 )$$

H= $( -P^t$ $I_1)$= ( -1 -1 -1 1 ) [= ( 1 1 1 1 ) over $\mathbb{F}_{2}$ ] $H \vec x$ x $\epsilon \mathbb{F}_{q}^n$ then $H \vec x= 0$ $\Leftrightarrow$ $\vec x$ is a codeword.

One way to define a code is through the parity check matrix. Ex Parity codes have H= $\overbrace{(\textrm{ -1 -1 -1 $\hdots$ -1 1})}^{-P^t}$ (there are k-ones)
then G=($I_k$ P)

Ex q=1, k=3, n=7 $\mathbb{F}_{2}^4\rightarrow\mathbb{F}_{2}^7$

$$H = (-P^t I_k)= \left( \begin{array}{cccc\vert ccc} 1&0&1&1&1&0&0 1&1&0&1&0&1&0 0&1&1&1&0&0&1 \end{array}\right)$$

$$-P^t = \left( \begin{array}{cccc} 1&0&1&1 1&1&0&1 0&1&1&1 \end{array}\right)$$

$$P = \left( \begin{array}{ccc} -1&-1&0 0&-1&-1 -1&0 &-1 -1&-1&-1 \end{array}\right)$$

$$G = (I_{n-k} P)= \left( \begin{array}{cccc\vert ccc} 1&0&0&0&-1&-1&0 0&1&0&0&0&-1&-1 0&0&1&0&-1&0 &-1\\ 0&0&0&1&-1&-1&-1 \end{array}\right)$$

rows of G are a basis for C. 4 rows $\Rightarrow$ 4 elements in basis, C is dim-4.

$$\left( \begin{array}{c}1 0 0 0 \end{array}\right) \rightarrow \left( \begin{array}{c}1 0 0 0 -1 -1 0 \end{array}\right)$$

$$\left( \begin{array}{c}0 0 0 1 \end{array}\right) \rightarrow \left( \begin{array}{c}0 0 0 1 -1 -1 -1 \end{array}\right)$$

$$\left( \begin{array}{c}0 0 1 0 \end{array}\right) \rightarrow \left( \begin{array}{c}0 0 1 0 -1 0 1 \end{array}\right)$$

$$\left( \begin{array}{c}0 1 0 0 \end{array}\right) \rightarrow \left( \begin{array}{c} 0 1 0 0 0 -1 -1 \end{array}\right)$$

Ex q=4, k=2, n=5, dim(c)=n-k=5-2=3, $\mathbb{F}_{4}^3 \rightarrow \mathbb{F}_{4}^5$
H=($-P^t$ $I_k$), now find peicewise linearly independent vectors in $\mathbb{F}_{4}^2$
$\mathbb{F}_{4}=\{a+bx\vert a,b \epsilon \mathbb{F}_{4} \}$ = 0, 1, a, b (a=x, b=x+1)

$$H = \left( \begin{array}{ccc\vert cc} 1&a&b&1&0 1&b&a&0&1 \end{array}\right)$$

$$P = \left( \begin{array}{cc} -1&-1 -a&-b -b&-a \end{array}\right)$$

$$G = \left( \begin{array}{ccccc} 1&0&0&-1&-1 0&1&0&-a&-b\\ 0&0&1&-b... ...left( \begin{array}{ccccc} 1&0&0&1&1 0&1&0&a&b 0&0&1&b&a \end{array}\right)$$

$$C = Span(\left( \begin{array}{c}1 0 0 1 1 \end{array}\right),... ...end{array}\right), \left( \begin{array}{c}0 0 1 b a \end{array}\right))$$

$$\mathbb{F}_{4}^3 \longrightarrow \mathbb{F}_{4}^5$$

$$\left( \begin{array}{c}1 0 0 \end{array}\right) \longrightarrow \left( \begin{array}{c}1 0 0 1 1 \end{array}\right)$$

$$\left( \begin{array}{c}0 1 0 \end{array}\right) \longrightarrow \left( \begin{array}{c}0 1 0 a b \end{array}\right)$$

$$\left( \begin{array}{c}0 0 1 \end{array}\right) \longrightarrow \left( \begin{array}{c} 0 0 1 b a \end{array}\right)$$

Check is x= $\left( \begin{array}{c}1 0 0 a b \end{array} \right)$ a codeword? Use parity check matrix. Hx= $\left( \begin{array}{ccccc} 1&a&b&1&0 1&b&a&0&1 \end{array}\right) \left( \begin{array}{c}1 0 0 a b \end{array}\right)$ = $\left( \begin{array}{c}1+a 1+b \end{array}\right) \neq 0$ Not a codeword. If you had received x, it was an error, and you would have to request it again.

Where was the error in $\left( \begin{array}{c}1 0 0 a b \end{array} \right)$ ?
*Can we change one element to get a codeword?
C= Span( $\left( \begin{array}{c}1 0 0 1 1 \end{array}\right), \left( \begin{arr... ...nd{array}\right) = \left( \begin{array}{c}1 0 0 a b \end{array}\right)$

Theorem Hamming codes have a minimum distance of 3. (Perfect) $\Rightarrow$ we can fix one error
If x had been $\left( \begin{array}{c}a 0 0 a b \end{array}\right)$ or some such vector, then there would have only been one error and we could have fixed it.