Transcript UNIT III

UNIT III
Linear Block Codes


A linear code is an important type of block code used
in error correction and detection schemes. Linear codes
allow for more efficient encoding and decoding
algorithms than other codes (cf. syndrome decoding).
Linear codes are applied in methods of transmitting
symbols (e.g., bits) on a communications channel so
that, if errors occur in the communication, some errors
can be detected by the recipient of a message block.
The "codes" in the linear code are blocks of symbols
which are encoded using more symbols than the
original value to be sent. A linear code of length n
transmits blocks containing n symbols.
Syndrome decoding
We construct a Hamming code C, encode an
information word using C, introduce one error,
and then decode by calculating the syndrome of
the ``received'' vector and applying the
CosetLeaders map to the syndrome to recover
the original vector.
Cyclic Codes








cyclic codes find an important application in error detection and correction.
Let C be a linear code over a finite field A of block length n. C is called a cyclic code, if
for every codeword c=(c1,...,cn) from C, the word (cn,c1,...,cn-1) in An obtained by a
cyclic right shift of components is also a codeword from C.
Sometimes, C is called the c-cyclic code, if C is the smallest cyclic code containing c, or,
in other words, C is the linear code generated by c and all codewords obtained by cyclic
shifts of its components.
Cyclic codes can be linked to ideals in certain rings. Let R = A[x] / (xn − 1). Identify the
elements of the cyclic code C with polynomials in R such that maps to the polynomial :
thus multiplication by x corresponds to a cyclic shift. Then C is an ideal in R, and hence
principal, since R is a principal ideal ring. The ideal is generated by the unique element in
C of minimum degree, the generator polynomial g. [1] This must be a divisor of xn − 1.
If the generator polynomial g has degree d then the the rank of the code C is n − d.
For example, if A= and n=3, the codewords contained in the (1,1,0)-cyclic code are
precisely
(0,0,0),(1,1,0),(0,1,1) and (1,0,1).
It corresponds to the ideal in generated by (1 + x).