Generator Matrices
Contents
A linear code $C$ is a vector space over some field $F$.
Usually $F$ is finite.
Equivalently, a linear code is the null-space or kernel $C = {x \in F^n : Hx^T = 0}$
For a $n$ column parity check matrix.
$m$ is the number of leading columns - these will be the check bits (by choice)
$k$ = $n - m$ is the number of non-leading columns - the information bits (by choice)
Given a code, finding basis: Gram-Schmidtt
- G has size $k * n$
- H has size $m * n$
- $k + m = n$
Can apply row operations on a generator / parity check matrix and it will still be a generator / parity check matrix
The RREF of the generator matrix G for C is also a generator matrix for C
Example, G = [0;1|1;1|1;0|1;1] spans the linear code C = {0000, 0110, 1101, 1011}
G’ = [1;0|0;1|1;1|1;0]
–
Standard form of a parity check matrix
$H = (I_m | B)$ where B is an $m * k$ matrix
Standard form of a generator matrix
$G = (D|I_k)$ where D is a $k * m$ matrix
I_...
is the identity matrix
Finding a generator matrix
For a linear code $C$ of dimension $k$ and length $n = k + m$
$G = (B|I_k)$ is a generator matrix for $C$ iff $H = (I_m | -B^T)$ is a parity check matrix for $C$
- This can work the other way around too, to find a parity check matrix.
Example
A linear code C over $Z_3$ has generator matrix
1 2 | 1 2 0 1 0 2 2 0 0 1 |
We can see the identity matrix in the last two columns.
The first three columns can then be regarded as $B$
$-B^T$ is then
1 2 3 | -1 -2 -2 -2 0 0 |
So then,
$H = (I_m | -B^T)$
which is
1 2 3 | 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 |
(remember, 2 = -2 = 0, -1 = 1 in binary)
Linear codes are equivalent if C’ is obtained by permuting the codeword entries of C by a fixed permutation
$C’ = CP = {xP : x in C}$ for some permutation matrix $P$
$G’ = GP$ and $H’ = HP$
For example,
1 2 3 4 5 | 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 switch 3 and 4 |
1 2 3 | 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 |
Code Operations
Puncturing
Shortening
Extending
The extension of a linear code, is adding an extra bit such that the sum of a code is zero
The extension $\hat{C}$ is a linear code with minimum distance $d©$ or d© + 1
Furthermore, if H is a parity check matrix for C, then,
H hat
1 2 3 4 5 6 | 1 1 . . . 1 0 . . H . 0 |
Hhat x^T = 0
??
–
Radix $r$ Hamming codes
Let $r$ be a prime number and $m\ge1$ for some integer
Write the numbers $1,…,r^m - 1$ in base $r$, as length $m$ column vectors
Of each set of $r-1$ parallel columns, delete all whose first nonzero entry is not 1
This gives the radix $r$ Hamming code of length \$n= (r^m-1)/(r-1)
? ? ?
Error Correcitng in Radix $r$
Let $x\inC$ and suppose that $x->y$ with $s$ errors
Then $y = x + a_1 e_i_1 + … + a_s e_i_s$ where $a_i$ are non-zero scalars
The syndrome of \$y\$ is \$S(y) = Hy^T = \$H(x^T + a*1 e*(i*1)^T) + … + a_s e*(i_s)^T)\$
= Hx^T + a1 H e(i1)^T + … + a_s H e(i_s)^T
= 0 + a1 H e(i1)^T + … + a_s H e(i_s)^T
= a1 H e(i1)^T + … + a_s H e(i_s)^T
$Hy^T$ is a linear combination of s columns
If $2s < d©$ then $S(y)$ is a unique linear combination of columns of H
–
example
Correcting radix:
Find the column that is a scalar multiple (a) of the result, then correct that column, SUBTRACTING a
(Don’t evaluate the result to a number)