ECE 4371, Fall, 2014 Introduction to Telecommunication Engineering/Telecommunication LaboratoryOutlineARQTypes of Error Correcting CodesHamming CodeHamming Code ExampleError CorrectionImportant Hamming CodesAnother Example: EncodingExample: Add noiseExample: Testing the messageExample: Repairing the messageCoding GainCoding Gain ExampleEncoder/Decoder of Linear CodeReed–Muller codeCyclic codeBASIC DEFINITION of Cyclic CodeFREQUENCY of CYCLIC CODESEXAMPLE of a CYCLIC CODEPOLYNOMIALS over GF(q)EXAMPLECyclic Code EncoderCyclic Code DecoderCyclic Redundancy Checks (CRC)Example of CRCChecking for errorsCapability of CRCBCH CodeBCH PerformanceReed-Solomon Codes1971: Mariner 91979+: Voyagers I & IIModern CodesError Correcting CodesECE 4371, Fall, 2014Introduction to Telecommunication Engineering/Telecommunication Laboratory Zhu HanDepartment of Electrical and Computer EngineeringClass 17Oct. 29th, 2014OutlineOutlineQuick Review of last class Line Code–Hamming code Cyclic code–CRC–BCH, RS4117 –S352 access, crowded–Call me or go to W319 if you cannot enter–USRP2 lab 1 Lab 2ARQARQAcknowledgments from receiver–Positive: “okay” or “ACK”–Negative: “please repeat that” or “NACK”Timeout by the sender (“stop and wait”)–Don’t wait indefinitely without receiving some response–… whether a positive or a negative acknowledgmentRetransmission by the sender–After receiving a “NACK” from the receiver–After receiving no feedback from the receiverTypes of Error Correcting CodesTypes of Error Correcting CodesRepetition CodeLinear Block Code, e.g. HammingCyclic Code, e.g. CRCBCH and RS CodeConvolutional Code–Tradition, Viterbi Decoding–Turbo Code–LDPC CodeCoded Modulation–TCM –BICMHamming CodeHamming CodeH(n,k): k information bit length, n overall code lengthn=2^m-1, k=2^m-m-1: H(7,4), rate (4/7); H(15,11), rate (11/15); H(31,26), rate (26/31)H(7,4): Distance d=3, correction ability 1, detection ability 2.Remember that it is good to have larger distance and rate.Larger n means larger delay, but usually better codeHamming Code ExampleHamming Code ExampleH(7,4)Generator matrix G: first 4-by-4 identical matrixMessage information vector pTransmission vector xReceived vector rand error vector eParity check matrix HError CorrectionError CorrectionIf there is no error, syndrome vector z=zerosIf there is one error at location 2New syndrome vector z iswhich corresponds to the second column of H. Thus, an error has been detected in position 2, and can be correctedImportant Hamming CodesImportant Hamming CodesHamming (7,4,3) -code. It has 16 codewords of length 7. It can be used to send 27 = 128 messages and can be used to correct 1 error.•Golay (23,12,7) -code. It has 4 096 codewords. It can be used to transmit 8 3888 608 messages and can correct 3 errors.Quadratic residue (47,24,11) -code. It has 16 777 216 codewords and can be used to transmit 140 737 488 355 238 messages and correct 5 errors.Another Example: EncodingAnother Example: Encodingwe multiply this matrix1111000011010010100101100001HBut why?You can verify that:To encode our messageBy our messagemessage code HHamming[1 0 0 0]=[1 0 0 0 0 1 1]Hamming[0 1 0 0]=[0 1 0 0 1 0 1]Hamming[0 0 1 0]=[0 0 1 0 1 1 0]Hamming[0 0 0 1]=[0 0 0 1 1 1 1]Where multiplication is the logical ANDAnd addition is the logical XORExample: Add noiseExample: Add noiseIf our message isMessage = [0 1 1 0]Our Multiplying yieldsCode = [0 1 1 0 0 1 1]Lets add an error, so Pick a digit to mutate        1100110011010010100101111000001101001101001011100001011110000110100101001011000010110Code => [0 1 0 0 0 1 1]Example: Testing the messageExample: Testing the messageWe receive the erroneous string:Code = [0 1 0 0 0 1 1]We test it: Decoder*CodeT=[0 1 1]And indeed it has an errorThe matrix used to decode is:To test if a code is valid:Does Decoder*CodeT=[0 0 0]–Yes means its valid–No means it has error/s101010111001101111000DecoderExample: Repairing the messageExample: Repairing the messageTo repair the code we find the collumn in the decoder matrix whose elements are the row results of the test vectorWe then change We trim our received code by 3 elements and we have our original message.[0 1 1 0 0 1 1] => [0 1 1 0]Decoder*codeT is[ 0 1 1]This is the third element of our codeOur repaired code is[0 1 1 0 0 1 1]101010111001101111000DecoderCoding GainCoding Rate R=k/n, k, no. of message symbol, n overall symbolWord SNR and bit SNRFor a coding scheme, the coding gain at a given bit error probability is defined as the difference between the energy per information bit required by the coding scheme to achieve the given bit error probability and that by uncoded transmission.Coding Gain ExampleCoding Gain ExampleEncoder/Decoder of Linear CodeEncoder/Decoder of Linear CodeEncoder: just xor gatesDecoder: SyndromeReed–Muller codeReed–Muller codeCyclic codeCyclic codeCyclic codes are of interest and importance because– They posses rich algebraic structure that can be utilized in a variety of ways.– They have extremely concise specifications.– They can be efficiently implemented using simple shift register– Many practically important codes are cyclicIn practice, cyclic codes are often used for error detection (Cyclic redundancy check, CRC) –Used for packet networks –When an error is detected by the receiver, it requests retransmission –ARQBASICBASIC DEFINITIONDEFINITION of Cyclic Code of Cyclic CodeFFREQUENCY of CYCLIC CODESREQUENCY of CYCLIC CODESEXAMPLE of a CYCLIC CODEEXAMPLE of a CYCLIC CODEPOLYNOMIALS POLYNOMIALS over over GF(GF(qq))EXAMPLEEXAMPLECyclic Code EncoderCyclic Code EncoderCyclic Code DecoderCyclic Code DecoderDividerSimilar structure as multiplier for encoderCyclic Redundancy Checks (CRC)Example of CRCChecking for errorsCapability of CRCCapability of CRCAn error E(X) is undetectable if it is divisible by G(x). The following can be detected.–All single-bit errors if G(x) has more than one nonzero term–All double-bit errors if G(x) has a factor with three terms–Any odd number of errors, if P(x) contain a factor