slides_08_4_4

of 7
5 views
PDF
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Document Description
S-72.3410 Linear Codes (1) 1 ' & $ % Block Codes block code A code C that consists of words of the form (c 0 , c 1 , . . . , c n−1 ), where n is the number of coordinates (and is said to be the length of the code). q-ary code A code whose coordinate values are taken from a set (alphabet) of size q (unless otherwise stated, GF(q)). encoding Breaking the data stream into blocks, and mapping these blocks onto codewords in C. The encoding process is depicted in [Wic, Fig. 4-1]. c
Document Share
Document Tags
Document Transcript
  -72.3410 Linear Codes (1) 1 '&   $   % Block Codes block code A code C  that consists of words of the form( c 0 ,c 1 ,...,c n − 1 ), where n is the number of  coordinates (and issaid to be the length  of the code). q -ary code A code whose coordinate values are taken from a set(alphabet) of size q (unless otherwise stated, GF( q )). encoding Breaking the data stream into blocks, and mappingthese blocks onto codewords in C  .The encoding process is depicted in [Wic, Fig. 4-1]. c  Patric¨Osterg˚ard-72.3410 Linear Codes (1) 2 '&   $   % Redundancy If the data blocks of a q -ary code are of length k , then there are M  = q k possible data vectors. (But all data blocks are notnecessarily of the same length.)There are q n possible words of length n , out of which q n − M  arenot valid codewords. The redundancy r of a code is r = n − log q M, which simplifies to r = n − k if  M  = q k . c  Patric¨Osterg˚ard-72.3410 Linear Codes (1) 3 '&   $   % Code Rate The redundancy is frequently expressed in terms of the code rate.The code rate R of a code C of size M  and length n is R =log q M n. Again, if  M  = q k , R = k/n . c  Patric¨Osterg˚ard-72.3410 Linear Codes (1) 4 '   &   $   % Transmission Errors The corruption of a codeword by channel noise, modeled as anadditive process, is shown in [Wic, Fig. 4-2]. error detection Determination (by the error control decoder)whether errors are present in a received word. undetectable error An error pattern that causes the receivedword to be a valid word other than the transmitted word. error correction Determine which of the valid codewords is mostlikely to have been sent. decoder error In error correction, selecting a codeword otherthan that which was transmitted. c  Patric¨Osterg˚ard  -72.3410 Linear Codes (1) 5 '&   $   % Error Control The decoder may react to a detected error with one of the followingthree responses: automatic repeat request (ARQ) Request a retransmission of the word. For applications where data reliability is of greatimportance. muting Tag the word as being incorrect and pass it along. Forapplications in which delay constraints do not allow forretransmission (for example, voice communication). forward error correction (FEC) (Attempt to) correct theerrors in the received word. c  Patric¨Osterg˚ard-72.3410 Linear Codes (1) 6 '&   $   % Weight and Distance (1) The (Hamming) weight of a word c , denoted by w ( c ) (or w H  ( c )), is the number of nonzero coordinates in c . Example. w ((0 ,α 3 , 1 ,α )) = 3, w (0001) = 1.The Euclidean distance between v = ( v 0 ,v 1 ,...,v n − 1 ) and w = ( w 0 ,w 1 ,...,w n − 1 ) is d E ( v , w ) =   ( v 0 − w 0 ) 2 + ( v 1 − w 1 ) 2 + ··· + ( v n − 1 − w n − 1 ) 2 . c  Patric¨Osterg˚ard-72.3410 Linear Codes (1) 7 '&   $   % Weight and Distance (2) The Hamming distance between two words, v = ( v 0 ,v 1 ,...,v n − 1 ) and w = ( w 0 ,w 1 ,...,w n − 1 ), is the number of coordinates in which they differ, that is, d H  ( v , w ) = |{ i | v i  = w i , 0 ≤ i ≤ n − 1 }| , where the subscript H  is often omitted. Note that w ( c ) = d ( 0 , c ),where 0 is the all-zero vector, and d ( v , w ) = w ( v − w ).The minimum distance of a block code C  is the minimumHamming distance between all pairs of distinct codewords in C  . c  Patric¨Osterg˚ard-72.3410 Linear Codes (1) 8 '   &   $   % Minimum Distance and Error Detection Let d min denote the minimum distance of the code in use. For anerror pattern to be undetectable, it must change the values in atleast d min coordinates.  A code with minimum distance d min can detect all  errorpatterns of weight less than d min .Obviously, a large number of error patterns of weight w ≥ d min canalso be detected. c  Patric¨Osterg˚ard  -72.3410 Linear Codes (1) 9 '&   $   % Forward Error Correction The goal in FEC systems is to minimize the probability of decodererror given a received word r . If we know exactly the behavior of the communication system and channel, we can derive theprobability p ( c | r ) that c is transmitted upon receipt of  r . maximum a posteriori decoder (MAP decoder) Identifies thecodeword c i that maximizes p ( c = c i | r ). maximum likelihood decoder (ML decoder) Identifies thecodeword c i that maximizes p ( r | c = c i ). Bayes’s rule p ( c | r ) = p C ( c )  p ( r | c )  p R ( r ) . c  Patric¨Osterg˚ard-72.3410 Linear Codes (1) 10 '&   $   % Minimum Distance and Error Correction The two decoders are identical when p C  ( c ) is constant, that is,when all codewords occur with the same probability. Themaximum likelihood decoder is assumed in the sequel.The probability p ( r | c ) equals the probability of the error pattern e = r − c . Small-weight error patterns are more likely to occurthan high-weight ones ⇒ we want to find a codeword thatminimizes w ( e ) = w ( r − c ).  A code with minimum distance d min can correct all  errorpatterns of weight less than or equal to  ( d min − 1) / 2  .It is sometimes possible to to correct errors with w >  ( d min − 1) / 2  . c  Patric¨Osterg˚ard-72.3410 Linear Codes (1) 11 '&   $   % Decoder Types A complete error-correcting decoder is a decoder that, given areceived word r , selects a codeword c that minimizes d ( r , c ).Given a received word r , a t -error-correcting bounded-distancedecoder selects the (unique) codeword c that minimizes d ( r , c ) iff  d ( r , c ) ≤ t . Otherwise, a decoder failure is declared. Question. What is the difference between decoder errors anddecoder failures in a bounded-distance decoder? c  Patric¨Osterg˚ard-72.3410 Linear Codes (1) 12 '   &   $   % Example: A Binary Repetition Code The binary repetition code of length 4 is { 0000 , 1111 } .Received Selected Received Selected0000 0000 1000 00000001 0000 1001 0000 or 1111 ∗ 0010 0000 1010 0000 or 1111 ∗ 0011 0000 or 1111 ∗ 1011 11110100 0000 1100 0000 or 1111 ∗ 0101 0000 or 1111 ∗ 1101 11110110 0000 or 1111 ∗ 1110 11110111 1111 1111 1111 ∗ Bounded-distance decoder declares decoder failure. c  Patric¨Osterg˚ard  -72.3410 Linear Codes (1) 13 '&   $   % Error-Correcting Codes and a Packing Problem A central problem related to the construction of error-correctingcodes can be formulated in several ways: 1. With a given length n and minimum distance d , and agiven field GF( q ), what is the maximum number A q ( n,d )of codewords in such a code? 2. What is the minimum redundancy for a t -error-correcting q -ary code of length n ? 3. What is the maximum number of spheres of radius t thatcan be packed in an n -dimensional vector space over GF( q )? c  Patric¨Osterg˚ard-72.3410 Linear Codes (1) 14 '&   $   % The Hamming Bound The number of words in a sphere of radius t in an n -dimensionalvector space over GF( q ) is V  q ( n,t ) = t  i =0  ni  ( q − 1) i . Theorem 4-1. The size of a t -error-correcting q -ary code of length n is M  ≤ q n V  q ( n,t ) . c  Patric¨Osterg˚ard-72.3410 Linear Codes (1) 15 '&   $   % The Gilbert Bound Theorem 4-2. There exists a t -error-correcting q -ary code of length n of size M  ≥ q n V  q ( n, 2 t ) . Proof: Repeatedly pick any word c from the space, and after eachsuch operation, delete all words w that satisfy d ( c , w ) ≤ 2 t fromfurther consideration. Then the final code will have minimumdistance at least 2 t + 1 and will be t -error-correcting. The theoremfollows from the fact that at most V  q ( n, 2 t ) words are deleted fromfurther consideration in each step.  c  Patric¨Osterg˚ard-72.3410 Linear Codes (1) 16 '   &   $   % Comparing Bounds Theorems 4-1 and 4-2 say that for the redundancy r of a code,log q V  q ( n,t ) ≤ r ≤ log q V  q ( n, 2 t ) . These bounds for binary 1-error-correcting codes are compared in[Wic, Fig. 4-3]. c  Patric¨Osterg˚ard
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x