Linear Block Codes - mohammad alshaikh site.ppt

Linear Block Codes,Mahdi BarhoushMohammad Hanaysheh,Introduction to Block Codes,*Block codes introduce controlled amounts of redundancy into a transmitted data stream.*Block code systems divide uncoded data stream into fixed size blocks(k symbol),then add redundancy to each block(n-k symbols)to form the encoded data stream.*(k information symbol)+(n-k parity check symbol)(n symbol code word)*Parity or redundancy bits are used for error detection and correction.,*Here,we have(n,k)code with rate R=k/n.*If the symbol is either 0 or 1 Binary block code,symbols are named bits.*There are 2n possible code words in a binary block code of length n.*From these,we choose 2k code words to be mapped to M=2k different message.*Thus,a block of k information bits is mapped into a code word of length n selected from the set M=2 k code words.*Any code has a weight which is the number of nonzero elements that it contains.,*Hamming distance is the number of differences between the corresponding elements in any two code words.(measure of difference between any two code words)Ex.dh(1100,1111)=2 dh(1100,1101)=1Then 1100 is closer to 1101*The smallest hamming distance between any two code words is called the minimum hamming distance dh min.*The idea with error correction codes is to pick the 2k code words of the 2n total possible code words which are far enough apart(in terms of Hamming distance)to guaranteeyou are able to correct a certain number of errors.*dh min=2*Ct+Dt+1,Linearity:*The block code is called linear block code if the addition of any two code words is also a code word.*The addition is performed under Galois Field GF(2)in binary block code.*Linearity implies that the linear block code must contain the all zeros code word.,How to generate a linear code?,Using linear algebra and matrices representation:C=m.GWhereC is 1 X n code matrix.m is 1 X k message matrix.G is k X n Generation matrix of the code(The rows of the generator matrix are linearly independent and so G has a rank k.),Ex.Let,Find the code for m=1001Solution C=m.G=1001.G=0111001,Linear systematic block code:In symmetric form,the code word C is compromised of a k information segment and a set of n-k symbols that are linear combination of certain information symbols determined by the P matrix.m=m1 m2 m3 m4 C=C1 C2 C3 C4 C5 C6 C7=m1 m2 m3 m4 C5 C6 C7 Then,G=Ik P Ik is the identity matrix P is k X(n-k)matrix,Parity check matrix H:The(n,k)linear code can be also specified by an(n k)X n matrix H Such that any code C satisfies C.T(H)=0000.The above formula implies that G.T(H)=0For systematic linear block code H=T(P)I n-k,Example.,Types of liner block codes:1.Hamming code.2.Cyclic Codes.3.Polynomial Codes.4.Reed Solomon Codes.5.Algebraic Geometric Codes.6.Reed-Muller Codes.7.Perfect Codes.8.Repetition Codes.,Hamming code:*(n,k)=(2w-1,2w-1-w),w is any positive integer let w=3(7,4)hamming code*In Hamming code,the parity check matrix H,the n column consists of all possible binary vectors except the all zero vectors.*dh min=3 can correct one error.*We have 2k=16 codes such that C.T(H)=0,Hamming code,single error correction:*Suppose that a single error occurred to the transmitted code CIn the i th place,the received vector r=C+e(i)e(i):zero row vector with length n except for the i th position.Using the barity check matrix H for decoding r.T(H)=(C+e(i).T(H)=C.T(H)+e(i).T(H)=e(i).T(H)Gives the location of the error,