Linear Block Coding

Linear Block Coding is an #Error Control Coding using $(n, k)$ linear Block Code# where $k$ is the number of message bits and $n$ is the number of codeword bits. The first portion of $k$ bits is always identical to the message sequence to be transmitted. The total number of code word could be derived by computing $2^k$. The second portion is a $n - k$ bits generalised parity check bits or parity bits. They are computed from the message bits using an encoding rule shown later. The basic property of Linear Block Coding is closure, where the sum of any two codes results in another code word.

The code structure is shown below using equations:

$$ \begin{align} c_i &= \begin{cases} b_i & i=0,1,2,\ldots,n-k-1\\ m_{i+k-n} & i=n-k,n-k+1,\ldots,n-1 \end{cases}\\ b_i &= p_{0i}m_0 + p_{1i}m_1 + \ldots + p_{k-1,i}m_{k-1}\\ p_{ij} &= \begin{cases} 1 & \text{ if } b_i \text{ depends on } m_j\\ 0 & \text{ otherwise} \end{cases} \end{align} $$

Where:

$b$ is the parity bit
$m$ is the message bit
$p$ is the coefficient in such a way that $n-k$ parity equations are unique and the rows of the Generator Matrix#, $G$ are linearly independent (no other can expressed in similar linear combination)

We could express them into a compact form using matrix notation:

$$ \begin{align} m &= [ m_0 \quad m_1 \quad \ldots \quad m_{k-1} ]\\ b &= [ b_0 \quad b_1 \quad \ldots \quad b_{n-k-1} ]\\ c &= [ c_0 \quad c_1 \quad \ldots \quad c_{n-1} ]\\ \end{align} $$

Which we’ll get $b = mP$ where $P$, the $k$ by $n-k$ coefficient matrix is defined below:

$$ P = \left[ \begin{array}{ccccc} p_{00} & p_{01} & p_{02} & \cdots & p_{0,n-k-1}\\ p_{10} & p_{11} & p_{12} & \cdots & p_{1,n-k-1}\\ \vdots & \vdots & \vdots & & \vdots\\ p_{k-1,0} & p_{k-1,1} & p_{k-1,2} & \cdots & p_{k-1,,n-k-1} \end{array} \right] $$

We can express the $c$ as a partitioned row vector, and substitute $b$ with $mP$. And we can further factor out the $m$ from the equation, thus get the following simplified formulae, which is the equation used to generate a full set code words:

$$ \begin{align} c &= [ b \vdots m ] = [ mP \vdots m ]\\ c &= m [ P \vdots I_k ]\\ c &= mG \end{align} $$

Where:

$I_k$ is the $k$ by $k$ identity matrix#
$G$ is the Generator Matrix#

The parity bits will be checked against on the receiver side using the mathematical relationship of the parity bit and message bit represented by Parity-Check Matrix#.

Utilising the nature of $H^T$, we could have a parity check equation based on the encoding formula:

$$ cH^T = mGH^T = 0 $$

We can calculate the Minimum Distance# of a linear block code by finding the minimum Hamming Weight# of any non-zero code word in the code. And from here, we can know the error detection capability of a linear block code, $\varepsilon$ with the equation:

$$ \varepsilon = d_{\text{min}} - 1 $$

Other than that, we can know the error correcting capability of a linear block code $t$ with the equation:

$$ t \le \left \lfloor \frac{1}{2} (d_{\text{min}} - 1) \right \rfloor $$

Links to this page

TIT3131 Chapter 3: Linear Block Coding

Linear Block Coding
Syndrome Decoding

With syndrome decoding a $(n,k)$ #linear block code can correct up to $t$ errors per code word, provided that $n$ and $k$ satisfy the Hamming bound.
Parity-Check Matrix

Parity-Check Matrix is used to check the parity of a #linear code.
Hamming Code

Hamming Code is a $(n,k)$ #Linear Block Code that can correct only single errors#. It must satisfy the following property:
Generator Polynomial

Generator Polynomial $g(D)$ is equivalent to the Generator Matrix in Linear Block Coding sense. Its degree is equal to the number of parity bits in the code which is $n-k$. It is unique as it is the only code word polynomial of minimum degree $n-k$, and any multiplication done on it is a #Code Word Polynomial.
Generator Matrix

$P$ is the $k$ by $n-k$ coefficient matrix defined in #Linear Block Coding
Error Control Coding

Linear Block Coding#
Cyclic Code

Cyclic Code is a #Linear Block Code that shows linear property and cyclic property. Linear property means that the sum of two code words in a set is also a code word (in the set). Cyclic property means that shifting done on a code word will produce another code word within the set.