Coding and Error Control - Lecture 23

Coding and Error ControlLecture 232Digital Communication SystemInformation SourceSource EncoderChannel EncoderModulatorChannelDemodu-latorChannel DecoderSource DecoderData SinkrbrcrsJPEG, MPEG, etc.RS code, Turbo code, QPSK, QAM, BPSK, etc.Cryptography(Ciphering)SourceCodingCompressionCodingLine CodingError Control CodingError CorrectionCodingError DetectionCoding- Secrecy/ Security- Encryption (DES)- Redundancy removal: - Destructive (jpeg, mpeg) - Non-destructive (zip)- Makes bitsequal probable- Strives toutilizechannelcapacity byadding extra bits- for baseband communications- RX synchronization- Spectral shaping for BW requirements- error detection- used in ARQ as in TCP/IP- feedback channel- retransmissions- quality paid by delay= FEC- no feedback channel- quality paidby redundantbitsFEC: Forward Error CorrectionARQ: Automatic Repeat RequestDES: Data Encryption StandardHow Stuff Works4Channel CodingChannel coding refers to the class of signal transformation designed to improve communication performance by enabling the transmitted signals to better withstand the effects of various channel impairments.Channel coding can be partitioned into two areas, waveform (or signal design) coding and structured sequences (or structured redundancy.)Waveform coding deals with transforming waveforms into “better waveforms,” to make the detection process less subject to errors.Structured sequence deals with transforming data sequences into “better sequences,” having structured redundancy.5Types of Error ControlBefore we discuss the detail of structured redundancy, let us describe the two basic ways such redundancy is used for controlling errors.Error detection and retransmission, utilizes parity bits (redundant bits added to data) to detect that an error has been made and requires two-way link for dialogue between the transmitter and receiver.Forward error correction (FEC), requires a one way link only, since in this case the parity bit are designed for both the detection and correction of errors.FEC67Why Use Error-Correction CodingTrade-off:Error Performance verse BandwidthPower verse BandwidthData Rate verse BandwidthCapacity verse BandwidthCoded verse Uncoded PerformanceCoding GainsFor a given bit-error probabilities, coding gain is defined as the reduction in Eb/N0 that can be realized through the use of code.8Types of Channel CodingBlock codesExtended Golay codeHamming codeBCH codeConvolutional codesRecursive or NonrecursiveSystematic or NonsystematicReed-Solomon CodesInterleaving and Concatenated CodesTurbo Codes9=> Need channel coding and error control to improve transmissionsChannel coding (CC) = coding (discrete digital) information into a form suitable for transmission, with emphasis on enhanced reliabilityCC adds redundancy that allows for info restoration or recovery when neededPrice paid: need broader bandwidthCC ensures proper transmission qualityMeasured byBit error quality (BER) / Frame error quality (FER)Requirement of CC and ECInformation to be transmittedSource codingChannel codingModulationTransmitterChannelInformation receivedSource decodingChannel decodingDemodulationReceiverChannelcodingChannel decodingChannel coding/decoding in a wireless communication systemChannel En-De/Coding for Wireless Communication CC includes error controlError control = at least error detection , preferably also error correctionError detection w/o error correction is insufficientMeans transmission failure since requires for retransmission 12Coping with Data Transmission ErrorsError detection codesDetects the presence of an errorAutomatic repeat request (ARQ) protocolsBlock of data with error is discardedTransmitter retransmits that block of dataError correction codes, or forward correction codes (FEC)Designed to detect and correct errors131415Types of ErrorsSingle-bit errorsBurst errors16RedundancyTo detect or correct errors, redundant bits of data must be added17CodingProcess of adding redundancy for error detection or correctionTwo types:Block codesDivides the data to be sent into a set of blocksExtra information attached to each blockMemorylessConvolutional codesTreats data as a series of bits, and computes a code over a continuous seriesThe code computed for a set of bits depends on the current and previous input18XOR OperationMain operation for computing error detection/correction codesSimilar to modulo-2 addition19Block CodingMessage is divided into k-bit blocksKnown as datawordsr redundant bits are addedBlocks become n=k+r bitsKnown as codewords20Example: 4B/5B Block CodingDataCodeDataCode0000111101000 10010000101001100110011001010100101010110001110101101110111010001010110011010010101011110111011011001110111011100011101111111111101k = ?r = ?n = ?21Error Detection in Block Coding22NotesAn error-detecting code can detect only the types of errors for which it is designedOther types of errors may remain undetected.There is no way to detect every possible error23Error Correction24Example: Error Correction CodeThe receiver receives 01001, what is the original dataword?k, r, n = ?25Common Detection MethodsParity checkCyclic Redundancy CheckChecksum26Parity CheckMost common, least complexSingle bit is added to a blockTwo schemes:Even parity – Maintain even number of 1sE.g., 1011  10111Odd parity – Maintain odd number of 1sE.g., 1011  1011027Example: Parity CheckSuppose the sender wants to send the word world. In ASCII the five characters are coded (with even parity) as 1110111 1101111 1110010 1101100 1100100The following shows the actual bits sent 11101110 11011110 11100100 11011000 1100100128Example: Parity CheckReceiver receives this sequence of words: 11111110 11011110 11101100 11011000 11001001Which blocks are accepted? Which are rejected?29Parity-Check: Encoding/Decoding30Performance of Parity CheckCan 1-bit errors be detected?Can 2-bit errors be detected?:312D Parity CheckWhat is its performance?322D Parity Check: Performance332D Parity Check: Performance34Cyclic Redundancy CheckIn a cyclic code, rotating a codeword always results in another codewordExample:35CRC Encoder/Decoder36CRC Generator37Checking CRC38Polynomial RepresentationMore common representation than binary formEasy to analyzeDivisor is commonly called generator polynomial39Division Using Polynomial40Error Detection ProbabilitiesDefinitionsPb : Probability of single bit error (BER)P1 : Probability that a frame arrives with no bit errorsP2 : While using error detection, the probability that a frame arrives with one or more undetected errorsP3 : While using error detection, the probability that a frame arrives with one or more detected bit errors but no undetected bit errors41Error Detection ProbabilitiesWith no error detectionF = Number of bits per frame42Error Detection ProcessTransmitterFor a given frame, an error-detecting code (check bits) is calculated from data bitsCheck bits are appended to data bitsReceiverSeparates incoming frame into data bits and check bitsCalculates check bits from received data bitsCompares calculated check bits against received check bitsDetected error occurs if mismatch43Error Detection Process44Parity CheckParity bit appended to a block of dataEven parityAdded bit ensures an even number of 1sOdd parityAdded bit ensures an odd number of 1sExample, 7-bit character [1110001]Even parity [11100010]Odd parity [11100011]45Cyclic Redundancy Check (CRC)TransmitterFor a k-bit block, transmitter generates an (n-k)-bit frame check sequence (FCS)Resulting frame of n bits is exactly divisible by predetermined numberReceiverDivides incoming frame by predetermined numberIf no remainder, assumes no error46CRC using Modulo 2 ArithmeticExclusive-OR (XOR) operationParameters:T = n-bit frame to be transmittedD = k-bit block of data; the first k bits of TF = (n – k)-bit FCS; the last (n – k) bits of TP = pattern of n–k+1 bits; this is the predetermined divisorQ = QuotientR = Remainder47CRC using Modulo 2 ArithmeticFor T/P to have no remainder, start withDivide 2n-kD by P gives quotient and remainderUse remainder as FCS48CRC using Modulo 2 ArithmeticDoes R cause T/P have no remainder?Substituting, No remainder, so T is exactly divisible by P49