无线通信与网络chap8

CodingandErrorControlChapter8CopingwithDataTransmissionErrorsErrordetectioncodesDetectsthepresenceofanerrorAutomaticrepeatrequest(ARQ)protocolsBlockofdatawitherrorisdiscardedTransmitterretransmitsthatblockofdataErrorcorrectioncodes,orforwardcorrectioncodes(FEC)DesignedtodetectandcorrecterrorsErrorDetectionProbabilitiesDefinitionsPb:Probabilityofsinglebiterror(BER)P1:ProbabilitythataframearriveswithnobiterrorsP2:Whileusingerrordetection,theprobabilitythataframearriveswithoneormoreundetectederrorsP3:Whileusingerrordetection,theprobabilitythataframearriveswithoneormoredetectedbiterrorsbutnoundetectedbiterrorsErrorDetectionProbabilitiesWithnoerrordetectionF=Numberofbitsperframe0113121PPPPPFbErrorDetectionProcessTransmitterForagivenframe,anerror-detectingcode(checkbits)iscalculatedfromdatabitsCheckbitsareappendedtodatabitsReceiverSeparatesincomingframeintodatabitsandcheckbitsCalculatescheckbitsfromreceiveddatabitsComparescalculatedcheckbitsagainstreceivedcheckbitsDetectederroroccursifmismatchErrorDetectionProcessParityCheckParitybitappendedtoablockofdataEvenparityAddedbitensuresanevennumberof1sOddparityAddedbitensuresanoddnumberof1sExample,7-bitcharacter[1110001]Evenparity[11100010]Oddparity[11100011]CyclicRedundancyCheck(CRC)TransmitterForak-bitblock,transmittergeneratesan(n-k)-bitframechecksequence(FCS)ResultingframeofnbitsisexactlydivisiblebypredeterminednumberReceiverDividesincomingframebypredeterminednumberIfnoremainder,assumesnoerrorCRCusingModulo2ArithmeticExclusive-OR(XOR)operationParameters:T=n-bitframetobetransmittedD=k-bitblockofdata;thefirstkbitsofTF=(n–k)-bitFCS;thelast(n–k)bitsofTP=patternofn–k+1bits;thisisthepredetermineddivisorQ=QuotientR=RemainderCRCusingModulo2ArithmeticForT/Ptohavenoremainder,startwithDivide2n-kDbyPgivesquotientandremainderUseremainderasFCSFDTkn2PRQPDkn2RDTkn2CRCusingModulo2ArithmeticDoesRcauseT/Phavenoremainder?Substituting,Noremainder,soTisexactlydivisiblebyPPRPDPRDPTknkn22QPRRQPRPRQPTCRCusingPolynomialsAllvaluesexpressedaspolynomialsDummyvariableXwithbinarycoefficientsXRXDXXTXPXRXQXPXDXknknCRCusingPolynomialsWidelyusedversionsofP(X)CRC–12X12+X11+X3+X2+X+1CRC–16X16+X15+X2+1CRC–CCITTX16+X12+X5+1CRC–32X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1CRCusingDigitalLogicDividingcircuitconsistingof:XORgatesUpton–kXORgatesPresenceofagatecorrespondstothepresenceofaterminthedivisorpolynomialP(X)AshiftregisterStringof1-bitstoragedevicesRegistercontainsn–kbits,equaltothelengthoftheFCSDigitalLogicCRCWirelessTransmissionErrorsErrordetectionrequiresretransmissionDetectioninadequateforwirelessapplicationsErrorrateonwirelesslinkcanbehigh,resultsinalargenumberofretransmissionsLongpropagationdelaycomparedtotransmissiontimeBlockErrorCorrectionCodesTransmitterForwarderrorcorrection(FEC)encodermapseachk-bitblockintoann-bitblockcodewordCodewordistransmitted;analogforwirelesstransmissionReceiverIncomingsignalisdemodulatedBlockpassedthroughanFECdecoderForwardErrorCorrectionProcessFECDecoderOutcomesNoerrorspresentCodewordproducedbydecodermatchesoriginalcodewordDecoderdetectsandcorrectsbiterrorsDecoderdetectsbutcannotcorrectbiterrors;reportsuncorrectableerrorDecoderdetectsnobiterrors,thougherrorsarepresentBlockCodePrinciplesHammingdistance–for2n-bitbinarysequences,thenumberofdifferentbitsE.g.,v1=011011;v2=110001;d(v1,v2)=3Redundancy–ratioofredundantbitstodatabitsCoderate–ratioofdatabitstototalbitsCodinggain–thereductionintherequiredEb/N0toachieveaspecifiedBERofanerror-correctingcodedsystemHammingCodeDesignedtocorrectsinglebiterrorsFamilyof(n,k)blockerror-correctingcodeswithparameters:Blocklength:n=2m–1Numberofdatabits:k=2m–m–1Numberofcheckbits:n–k=mMinimumdistance:dmin=3Single-error-correcting(SEC)codeSECdouble-error-detecting(SEC-DED)codeHammingCodeProcessEncoding:kdatabits+(n-k)checkbitsDecoding:comparesreceived(n-k)bitswithcalculated(n-k)bitsusingXORResulting(n-k)bitscalledsyndromewordSyndromerangeisbetween0and2(n-k)-1Eachbitofsyndromeindicatesamatch(0)orconflict(1)inthatbitpositionCyclicCodesCanbeencodedanddecodedusinglinearfeedbackshiftregisters(LFSRs)Forcycliccodes,avalidcodeword(c0,c1,…,cn-1),shiftedrightonebit,isalsoavalidcodeword(cn-1,c0,…,cn-2)Takesfixed-lengthinput(k)andproducesfixed-lengthcheckcode(n-k)Incontrast,CRCerror-detectingcodeacceptsarbitrarylengthinputforfixed-lengthcheckcodeBCHCodesForpositivepairofintegersmandt,a(n,k)BCHcodehasparameters:Blocklength:n=2m–1Numberofcheckbits:n–k£mtMinimumdistance:dmin³2t+1CorrectcombinationsoftorfewererrorsFlexibilityinchoiceofparametersBlocklength,coderateReed-SolomonCodesSubclassofnonbinaryBCHcodesDataprocessedinchunksofmbits,calledsymbolsAn(n,k)RScodehasparameters:Symbollength:mbitspersymbolBlocklength:n=2m–1symbols=m(2m–1)bitsDatalength:ksymbolsSizeofcheckcode:n–k=2tsymbols=m(2t)bitsMinimumdistance:dmin=2t+1symbolsBlockInterleavingDatawrittentoandreadfrommemoryindiffere