03.3 Linear Codes

Definition

A block code is a linear code if the codewords form a subspace of ${\mathbb{F}}^n$ for some finite field $\mathbb{F}$

Definition

The Hamming weight of $\vec{x}$ — denoted as $w(\vec{x})$ — is the number of its non-zero components — provided $\vec{x}$ is in a finite field (there has to exist the vector $\vec{0}$)

Could also be understood as the Hamming distance of $\vec{0}$ and $\vec{x}$:

$$w(\vec{x})=d(\vec{0},\vec{x})$$

Theorem

The minimum distance of a linear code $\mathcal{C}$ is the smallest weight of a codeword $\mathcal{C}$:

$$d_{\min }(\mathcal{C})=\min w(\vec{c})$$

Generator Matrix

Definition

Let $(\overrightarrow{c_1},\dots ,\overrightarrow{c_k})$ be a basis of a linear code over a finite field. Then the $k\times n$ matrix that has $\overrightarrow{c_i}$ as its $i$-th row is the generator matrix $G$ of $\mathcal{C}$

Encoding

A $k\times n$ matrix specifies an encoding map that sends an information vector.

Example

We can send the message $\vec{u}$ with the generator matrix:

$$\vec{u}=(1,0,1)\to (1,0,1)\left(\begin{array}{ccccccc}0& 0& 1& 1& 1& 0& 0\\ 0& 1& 1& 1& 0& 1& 1\\ 1& 1& 1& 0& 1& 0& 0\end{array}\right)=(1,1,0,1,0,0,0)$$

A generator matrix defines an encoding map ⇒ codeword $\vec{c}=\vec{u}G$

Definition

A generator matrix $G_s$ is in systematic form if

$$G_s=(I_k,P_{k\times (n-k)})$$

These are matrices in reduced echelon form

When these matrices are in systematic form, we write the codewords as

$$\vec{c}=\vec{u}{G}_s=(u_1,\dots ,u_k,c_{k+1},\dots ,c_n)$$

Decoding

Decoding is deciding the information word from the channel output-

If the channel output $\vec{y}$ is a codeword, then we assume that it equals the channel input

In this case, decoding is inverting the encoding map, which is easy when the generator matrix is in the systematic form.

The problem is knowing if $\vec{y}$ is a codeword → linear block code ⇒ defined by system of homogeneous linear equations → $\vec{y}$ is a codeword ⇐> satisfies those equations

We have a parity-check matrix $H$ for a linear $(n,k)$ code, which is an $(n-k)\times n$ matrix that has the coefficients of a system of a homogeneous linear equations that defines the code.

Theorem

If $G=(I_k,P)$, with $P$ a $k\times (n-k)$ matrix — which is a generator matrix of systematic form — of a linear $(n,k)$ block code, then

$$H=(-P^T,I_{n-k})$$

which is a parity-check matrix of the same $(n,k)$ code

Example

If we have the generator matrix

$$G=\left(\begin{array}{ccccc}1& 0& 0& 3& 2\\ 0& 1& 0& 3& 4\\ 0& 0& 1& 0& 0\end{array}\right),P=\left(\begin{array}{cc}3& 2\\ 3& 4\\ 0& 0\end{array}\right)$$

We therefore have $H$ the parity-check matrix defined as

$$H=\left(\begin{array}{ccccc}-3& -3& 0& 1& 0\\ -2& -4& 0& 0& 1\end{array}\right),-P^T=\left(\begin{array}{ccc}-3& -3& 0\\ -2& -4& 0\end{array}\right)$$

Definition

With $H$ the parity-check matrix of a linear block code $\mathcal{C}\in {\mathbb{F}}^n$ and $\vec{y}\in {\mathbb{F}}^n$

We have the syndrome of $\vec{y}$ the vector

$$\vec{s}=\vec{y}{H}^T$$

With, by definition

$$\vec{y}\in \mathcal{C}⟺\vec{s}=\vec{0}$$

Theorem

With $H$ a parity-check matrix of a linear code, we have the minimum distance of the code the smallest positive integer $d$, such that there are $d$ columns of $H$ which are independent

When we have $\mathcal{G}$ a commutative group and $\mathcal{H}$ a subgroup: $a\sim b$ if there exists $h\in \mathcal{H}$ such that $b=a\star h$

Example

For $\star \equiv +$, and $\mathcal{H}=\{0,5\}$, we have $[0]=\mathcal{H}=\{0,5\}$ and

$$[1]=1+\mathcal{H}=\{1,6\}$$

We call $[n]$ the coset of $\mathcal{H}$, with respect to $a$

All of them have the same cardinality as $\mathcal{H}$

Standard Array

The standard array is an array that has the elements of $\mathcal{C}$, starting with the code word $0$, and each row forms a coset of $\mathcal{C}$ — each element of ${\mathbb{F}}^n$ shows up exactly once in the standard array.

We can use this to decode.

We have each column ${\mathcal{D}}_i$. We have ${\mathcal{D}}_i=c_i+{\mathcal{D}}_0$

To find a codeword associated to $y$, we could find $y$ in the standard array and read out the entry on top of the same column — but standard array are generally too large to store.

The first column describes the geometry of all decoding regions.

Claim

In the standard array, each element of a row has the same syndrome as the coset leader.

Claim

The syndrome uniquely identifies the coset leader

Hence, a coset decoder can be implemented as follows:

1. We precompute and store the coset leaders and their corresponding syndrome
2. To decode $y$, we compute its syndrome $s=y{H}^T$
3. $s$ encodes the row of $y$
4. We use the lookup table to determine the corresponding coset leader $t_i$
5. It and $y$ uniquely determine the column of $y$, as $y=t_i+c_j$
6. Hence we have $c_j=y-t_i$
7. The decoder declares that the transmitted codeword is $\hat{c}=y-t_i$

To find the information word $\hat{u}$ that corresponds to $\hat{c}$, we solve the linear system

$$\hat{u}G=\hat{c}$$

If $G$ is in systematic form, then $\hat{u}$ consists of the first $k$ components of $\hat{c}$

Choosing Coset Leaders

There are many ways to choose the coset leaders $t_i$

In fact, we have that every element of every row could be chosen as the coset leader.

Theorem

In every row of the standard array:

Select the coset leader to be one of the minimum weight vectors in that row

Then the coset decoder is a minimum-distance decoder

Warning

This procedure requires to store $|\mathbb{F}{|}^{(n-k)}$ coset leaders and the corresponding syndrome.

A lookup table of this size will not work in most cases

Error Probability

We have seen before that we can pretty much choose any coset we want.

Here, we will see how to pick an optimal coset, reducing the chance of decoding errors.

03.4 Reed Solomon Codes