1. Linear Block Codes A block code is said to be Linear Block Code if addition ( +,modulo – 2 arithmetic) of any 2 code words is the valid code word. Linear block code can be generated or implemented easily by using Modulo-2 adder.

We assume that the output of an information source is a sequence of binary digits "0" or "1." In block coding, this binary information sequence is segmented into message blocks of fixed length; each message block, denoted by u, consists of k information digits. There are a total of 2k distinct messages. The encoder, according to certain rules, transforms each input message u into a binary n-tuple v with n $\gt$ k. This binary n-tuple v is referred to as the code word (or code vector) of the message u.

Therefore, corresponding to the 2k possible messages, there are 2k code words. This set of 2k code words is called a block code. For a block code to be useful, the 2k code words must be distinct. Therefore, there should be a one-to-one correspondence between a message u and its code word v.

Definition : A block code of length n and 2k code words is called a linear (n, k) code if and only if its 2k code words form a k-dimensional subspace of the vector space of all the n-tuples over the field GF(2).

In fact, a binary block code is linear if and only if the modulo-2 sum of two code words is also a code word.

One can easily check that the sum of any two code words in this code is also a code word.

For (n,k) block code;

n – k $\gt$ No. of parity bits

k $\gt$ No. of data bits

n $\gt$ No. of bits in code words

Thus, Code Rate = k/n

Code efficiency = k/n x 100%

Hamming Codes

Hamming codes are the earliest and simplest example of linear block codes. The parameters are as follows, for m $\geq$ 2

code length: n = 2m − 1

Number of information symbols: k = 2m − m − 1

Number of parity symbols: n − k = m

Error correcting capability: t = 1

Examples are: (3, 1),(7, 4),(15, 11) and (31, 26) codes.

The parity check matrix of a Hamming code consists of all non-zero binary m-tuples. The columns may be ordered to correspond to a systematic code. Syndrome decoding of Hamming codes using the standard array is straightforward: the syndrome indicates which column of H corresponds to the error position.

2. Cyclic Codes

Definition: An (n, k) linear code C is called a cyclic code if every cyclic shift of a code vector in C is also a code vector. Code words can be represented as polynomials of degree n. For a cyclic code all code words are multiple of some polynomial g(X) modulo Xn+1 such that g(X) divides Xn+1. g(X) is called the generator polynomial.

A block code is said to be cyclic code if it satisfies the following 2 properties;

a) Linearity

b) Cyclic: It implies that cyclic rotation of any code word should be a valid code word.

All Cyclic codes are linear codes but not all linear codes are cyclic codes

Generation of Non-Systematic Cyclic Code:

C(x) = D(x) G(x)

where;

D(x) – Data Polynomial

G(x) – Generator Polynomial

C(x) – Code word Polynomial

3. Convolutional Codes

Convolutional codes differ from block codes in that the encoder contains memory and the n - encoder outputs at any time unit depend not only on the k inputs but also on m previous input blocks.

An (n, k, m) convolutional code can be implemented with a k input, n-output linear sequential circuit with input memory m.

Typically, n and k are small integers with k $\lt$ n, but the memory order m must be made large to achieve low error probabilities.

Convolutional codes are commonly described using two parameters: the code rate and the constraint length.

The code rate, k/n, is expressed as a ratio of the number of bits into the convolutional encoder (k) to the number of channel symbols output by the convolutional encoder (n) in a given encoder cycle.

The constraint length parameter, K, denotes the "length" of the convolutional encoder, i.e. how many k-bit stages are available to feed the combinatorial logic that produces the output symbols.

Closely related to K is the parameter m, which indicates how many encoder cycles an input bit is retained and used for encoding after it first appears at the input to the convolutional encoder.

The m parameter can be thought of as the memory length of the encoder.

Convolutional codes are widely used as channel codes in practical communication systems for error correction.

The encoded bits depend on the current k input bits and a few past input bits. The main decoding strategy for convolutional codes is based on the widely used Viterbi algorithm. As a result of the wide acceptance of convolutional codes, there have been several approaches to modify and extend this basic coding scheme. Trellis coded modulation (TCM) and turbo codes are two such examples.

In TCM, redundancy is added by combining coding and modulation into a single operation. This is achieved without any reduction in data rate or expansion in bandwidth as required by only error correcting coding schemes.

A simple convolutional encoder is shown in Fig. The information bits are fed in small groups of k-bits at a time to a shift register.

The output encoded bits are obtained by modulo-2 addition (EXCLUSIVE-OR operation) of the input information bits and the contents of the shift registers which are a few previous information bits.

If the encoder generates a group of "n‟ encoded bits per group of "k‟ information bits, the code rate R is commonly defined as R = k/n. In Fig., k = 1 and n = 2.

The number, K of elements in the shift register which decides for how many codemwords one information bit will affect the encoder output, is known as the constraint length of the code.

For the present example, K = 3. The shift register of the encoder is initialized to all-zero-state before encoding operation starts.

It is easy to verify that encoded sequence is 00 11 10 00 01 ….for an input message sequence of 01011….

The operation of a convolutional encoder can be explained in several but equivalent ways such as, by a) state diagram representation, b) tree diagram representation and c) trellis diagram representation.