ERROR DETECTION AND CORRECTION
• Errordetection • ErrorCorrection
Copyright By PowCoder代写 加微信 powcoder
Types of Errors
• Datacanbecorruptedduringtransmission.
• Someapplicationsrequirethaterrorsbedetectedand corrected.
• single-bit error means that only 1 bit of a given data unit (such as a byte, character, or packet) is changed from 1 to 0 or from 0 to 1
• burst error means that 2 or more bits in the data unit have changed from 1 to 0 or from 0 to 1
Redundancy
• Thecentralconceptindetectingorcorrectingerrorsis redundancy
• Tobeabletodetectorcorrecterrors,weneedtosend some extra bits with our data. These redundant bits are added by the sender and removed by the receiver. Their presence allows the receiver to detect or correct corrupted bits
Detection vs. Correction
Thecorrectionoferrorsismoredifficultthanthe detection
Inerrordetection,weareonlylookingtoseeifany error has occurred. The answer is a simple yes or no
In error correction, we need to know the exact number of bits that are corrupted and, more importantly, their location in the message. The number of errors and the size of the message are important factors
• Redundancyisachievedthroughvariouscoding schemes
• Thesenderaddsredundantbitsthroughaprocessthat creates a relationship between the redundant bits and the actual data bits
• Thereceivercheckstherelationshipsbetweenthetwo sets of bits to detect errors
• Theratioofredundantbitstodataisanimportant factors in any coding scheme,
– coderate=msg/(msg+redundant)
Block Coding
• Inblockcoding,wedivideourmessageintoblocks, each of k bits, called datawords. We add r redundant bits to each block to make the length n = k + r
• Withkbits,wecancreateacombinationof2k datawords; with n bits, we can create a combination of 2n codewords
• Sincen>k,thenumberofpossiblecodewordsislarger than the number of possible datawords.
• Theblockcodingprocessisone-to-one;thesame dataword is always encoded as the same codeword.
• This means that we have 2n − 2k codewords that are not used
Encoder/Decoder Structure
Error Detection
• Ifthecodewordismodifiedduetonoisethereis2 choices:
– The codeword is changed such that it does not match any codeword, error is detected
– The codeword is changed such that it became a different codeword, error is not detected
– An error-detecting code can detect only the types of errors for which it is designed; other types of errors may remain undetected
Hamming Distance
• Oneofthecentralconceptsincodingforerrorcontrolis the idea of the Hamming distance. The Hamming distance between two words (of the same size) is the number of differences between the corresponding bits
• Example:
– The Hamming distance d(000, 011) is 2
because (000 ⊕ 011) is 011 (two 1s).
– The Hamming distance d(10101, 11110) is 3
because (10101 ⊕ 11110) is 01011 (three 1s)
Minimum Hamming Distance
• The minimum Hamming distance is the smallest Hamming distance between all possible pairs of codewords
• Toguaranteethedetectionofuptoserrorsinallcases,
the minimum Hamming distance in a block code must be:dmin =s+1
Parity-Check Code
• parity-check code: k-bit dataword is changed to an n- bit codeword where n = k + 1.
• Theextrabit,calledtheparitybit,isselectedtomake the total number of 1s in the codeword even
• TheminimumHammingdistanceforthiscategoryis dmin = 2, which means that the code is a single-bit error-detecting code
Simple parity-check code C(5, 4)
Parity-Check Code Encoder & Decoder
Parity-Check Code Example
• Letuslookatsometransmissionscenarios.Assumethe sender sends the dataword 1011. The codeword created from this dataword is 10111, which is sent to the receiver.
• Noerroroccurs;thereceivedcodewordis10111.The
syndrome is 0
• Onesingle-biterrorchanges,e.g.receivedcodewordis 10011. The syndrome is 1
• Two-biterror,e.g.00110.Thesyndromeis0,noerror is detected
• A simple parity-check code can detect an odd number of errors
Cyclic Redundancy Check
• Cyclic codes are special linear block codes with one extra property. In a cyclic code, if a codeword is cyclically shifted (rotated), the result is another codeword
• Oneofthemostpowerfulerror-detectingcodesisthe
cyclic redundancy check (CRC)
• Givenak-bitblockofbits,thetransmittergeneratesa sequence, known as a frame check sequence (FCS), such that the resulting frame, consisting of n bits, is exactly divisible by some predetermined number.
• Thereceiverthendividestheincomingframebythat number and, if there is no remainder, assumes there was no error
Modulo 2 Arithmetic
• Modulo2arithmeticusesbinaryadditionwithno carries, which is just the exclusive-OR (XOR) operation
• Binarysubtractionwithnocarriesisalsointerpretedas the XOR operation
Division in CRC encoder
CRC Decoder
• Thecodewordcanchangeduringtransmission.
• Thedecoderdoesthesamedivisionprocessasthe encoder.
• Theremainderofthedivisionisthesyndrome.
• Ifthesyndromeisall0s,thereisnoerrorwithahigh probability, otherwise, everything is discarded
CRC Divisor
• Wemaybewonderinghowthedivisor1011ischosen.
• Thisdependsontheexpectationwehavefromthe code. We will show some standard divisors later after we discuss polynomials
Polynomials
• Abetterwaytounderstandcycliccodesandhowthey can be analyzed is to represent them as polynomials
Polynomials
• DegreeofaPolynomial:Thedegreeofapolynomialis
the highest power in the polynomial
• AddingandSubtractingPolynomials:Addingand subtracting polynomials in mathematics are done by adding or subtracting the coefficients of terms with the same power
– (x5 +x4 +x2)+(x6 +x4 +x2)=(x6 +x5) • MultiplyingorDividingTerms:
– x3 × x4 = x7 – x5/x2=x3
Polynomials
• MultiplyingTwoPolynomials:Multiplyingapolynomial
by another is done term by term
– (x5 +x3 +x2 +x)(x2 +x+1)=x7 +x6 +x5 +x5 + x4 +x3 +x4 +x3 +x2 +x3 +x2 +x
=x7 +x6 +x3 +x
Polynomials
• DividingOnePolynomialbyAnother:Divisionof polynomials is conceptually the same as the binary division
Cyclic Code Analysis
• Wecananalyzeacycliccodetofinditscapabilitiesby using polynomials. We define the following polynomials:
– Dataword: d(x)
– Codeword: c(x)
– Generator: g(x)
– Syndrome: s(x) =
– Error: e(x)
– Received codeword c’(x)= c(x) + e(x)
– The receiver divides the received codeword c’ by g(x) to get the syndrome
– In a cyclic code, those e(x) errors that are divisible by g(x) are not caught
Standard Polynomials
The polynomial must not have a root in the field, e.g. x8+x2+x+1 dose not have a root in [0, 28-1]
Hardwired design of the divisor in CRC
Simulation of division in CRC encoder
CRC encoder design using shift registers
Encoder / Decoder
• Atthesource,themessageisfirstdividedintom-bit units. The generator then creates an extra m-bit unit called the checksum, which is sent with the message.
• Atthedestination,thecheckercreatesanewchecksum from the combination of the message and sent checksum. If the new checksum is all 0s, the message is accepted; otherwise, the message is discarded
Forward Error Correction (FEC)
• todetectserrors,theminimumHammingdistance shouldbedmin =s+1
• Tocorrecterrors,theminimumHammingdistance should be dmin = 2s + 1
Error Correction Process
References
• DataCommunicationsandNetworking5thedition– 2013, Behrouz A. Forouzan; Chapter 10
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com