Online Learning Platform

Information Theory and Coding > Error Control Coding > What do you mean by Linear Block Code?

Block Code: A Block Code consists of a set of fixed length codewords. The fixed length of these codewords is called the Block Length and is typically denoted by n. Let, a code of block length n consists of a set of codewords having n components and each block contains k bits, and each k bits of a block defines a dataword. Hence, the overall datawords will be 2^k

Example: code C = { 00000, 10100, 11110, 11001} is a block code of block length equal to 5.

A block code of size M defined over an alphabet with q (=2) symbols is a set of M q-ary sequences, each of length n. Usually, M = q^k for some integer k, and we call such a code an (n, k) code.

Uncoded bits	Codewords
00	00000
01	10100
10	11110
11	11001

Here M= 4, k= 2 and n = 5

Linear Code: A linear code has the following properties:

Modulo-2 sum of two codewords belonging to the code is also a codeword belonging to the code.
All-zero word is always a codeword.
Minimum Hamming distance between two codewords of a linear code is equal to the minimum weight of any non-zero codeword,

Example:

code C = {0000, 1010,0101, 1111} is a linear block code of block length n = 4.

Because all the ten possible sums of the codewords

Condition 1:

Sum	Hamming Distance	Hamming Weight
0000 + 0000 = 0000,	0	0, 0
0000 + 1010 = 1010,	2	0, 2
0000 + 0101 = 0101,	2	0, 2
0000 + 1111 = 1111,	4	0, 4
1010 + 1010 = 0000,	0	2, 2
1010 + 0101 = 1111,	4	2, 2
1010 + 1111 = 0101,	2	2, 4
0101 + 0101 = 0000,	0	2, 2
0101 + 1111 = 1010 and	2	2, 4
1111 + 1111 = 0000	0	4, 4

Condition 2: also satisfied

Condition 3:

For all-zero codeword in C, the minimum distance of this code is d^* = 2.

Linear Block Coding

A linear block code is a type of error-correcting code for which any linear combination of codewords is also a codeword. A codeword is a block of symbols that are encoded using more symbols than the original value to be sent. A linear block code divides the data into blocks of equal length and adds parity bits to each block to enable error detection and correction. A linear block code is characterized by its length, dimension, and distance, denoted by [n, k, d], where n is the number of bits in a codeword, k is the number of bits in a dataword, and d is the minimum Hamming distance between any two codewords.

Suppose each block of a message, called dataword, contains k bits. Hence, the overall datawords will be 2^k. In order to perform encoding, parity bit has been added and datawords are encoded as codewords having n number of bits i.e n>k. so the size of the parity bit is n-k. parity bits are selected using some rules.

Hence, the possible codewords will be 2ⁿ out of which 2^k contains datawords. During transmission, if errors are introduced in the message bits then it will not match with the parity bits which can be detected as an error by the receiver.