通信系统课件：第十章 纠错控制编码

Chapter10

Error-ControlCodingProblems:(pp.696-702)10.410.7

10.1210.15

10.1710.2510.271Chapter10

Error-ControlCoding10.1Introduction10.2Discrete-MemorylessChannels10.3LinearBlockCodes10.4CyclicCodes10.5ConvolutionalCodes10.6MaximumLikelihoodDecodingofConvolutionalCodes10.7Trellis-CodedModulation10.8Turbo

Codes10.9ComputerExperiment：TurboDecoding10.10Low-DensityParity_CheckCodes10.11IrregularCodes10.12SummaryandDiscussion2第十章纠错控制编码10.1引言10.2离散无记忆信道10.3线性分组码10.4循环码10.5卷积码10.6卷积码的最大似然译码10.7网格编码调制10.8Turbo码10.9计算机实验：Turbo码的译码10.10低密度奇偶校验码10.11不规则码10.12总结与讨论3Chapter10

Error-ControlCodingTopics:Error-controlcoding---ChannelcodingImportantcodesLinearblockcodes(Cycliccodes)ConvolutionalcodesCompoundcodes(turbocodes,low-densityparity-checkcodes&irregularcodes)

410.1Introduction

Task

---transmittinginformation arate(velocity) at alevelofreliability(quality)Whyerror-controlcoding?

ForafixedEb/N0,itistheonlypracticaloption

availableforchangingdataqualityfromproblematictoacceptable.510.1Introduction

Systemparameters:transmittedsignalpowerchannelbandwidth+

powerspectraldensityofreceivernoiseSignalenergyperbit/noisepowerspectraldensity(Eb/N0)biterrorrateerrorcontrolcoding(ForfixedEb/N0)(ForfixedBER)Reducetransmittedpowerorhardwarecosts6Figure10.1

Simplifiedmodelsofdigitalcommunicationsystem.(a)Codingandmodulationperformedseparately.(b)Codingandmodulationcombined.710.1Introduction

Infig.10.1a,channelcodingandmodulationareperformedseparately.Infig.10.1b,channelcodingandmodulationarecombined(TCM).--->bandwidthefficiencyisincreased810.1Introduction

Channelencoder--addsredundancyaccordingtoaprescribedruleChanneldecoder--exploittheredundancytodecideactuallytransmittedmessagebitsAdvantage--minimizetheeffectofchannelnoise(reducetheBER)Disadvantage--increasetransmissionbandwidthandsystemcomplexity

910.1Introduction

Classification:blockcodes--absenceofmemory

convolutionalcodes--presenceofmemory

(n,k)blockcode---(n-k)redundantbitscoderater=k/nchanneldatarateR0=(n/k)*Rs

(sourcedatarate)

(n,k,N)convolutionalcodetheinputsequencetheimpulseresponseof theencoder(duration=memoryoftheencoder N)--discretetimeconvolution

1010.1Introduction

FEC(Feed-forwarderrorcorrection)redundancyusedfordetection&correctionoferrorsinreceiver(channelcoding)one-waylink&decodingcomplexitywiderinapplicationARQ(automatic-repeatrequest)redundancyusedonlyfordetectionoferrorserror-->repeattransmissionhalf-duplexorfull-duplexlinks(feed-backchannel)computercommunicationsystems1110.1Introduction

TypesofARQstop-and-waitstrategy(half-duplexlink)continuousARQwithpullback(duplexlink)continuousARQwithselectiverepeat(duplexlink)TheabovethreetypesofARQoffertrade-offbetweentheneedforahalf-duplexorfull-duplexlinkanddatathroughout.1210.2Discrete-MemorylessChannels

Memorylesswaveformchannel:thedetectoroutputinagivenintervaldependsonlyonethesignaltransmittedinthatinterval(seefig.10.1a)Discretememorylesschannel:themodulator+thewaveformchannel+thedetectorTransitionprobabilitiesp(j|i)describeadiscretememorylesschannelcompletely1310.2Discrete-MemorylessChannels

BinarysymmetricchannelFigure10.2Transitionprobabilitydiagramofbinarysymmetricchannel.1410.2Discrete-MemorylessChannels

Harddecisiondecoder--algebraicdecodersimplicityofimplementationirreversiblelossofinformationSoftdecisiondecoder--probabilisticdecodercomplicatestheimplementationofferssignificantimprovementinperformance15Figure10.3BinaryinputQ-aryoutputdiscretememorylesschannel.

(a)Receiverforbinaryphase-shiftkeying.(b)Transfercharacteristicofmultilevelquantizer.(c)Channeltransitionprobabilitydiagram.Parts(b)and(c)areillustratedforeightlevelsof

quantization.1610.2Discrete-MemorylessChannelsChannelcodingtheoremrevisitedChannelcapacity:maximumamountofinfor-mationtransmittedperchanneluse(inchapter9)Channelcodingtheorem:ifR(rateofsourceinformation)≤C(capacityofadiscretememorylesschannel),thenthereexistsacodingtechniquesuchthattheoutputofsourcemaybetransmittedoverthechannelwithanarbitrarilylowprobabilityofsymbolerror(Pe->0.)1710.2Discrete-MemorylessChannelsChannelcodingtheoremrevisited(cont.)Channelcodingtheoremexistenceofgoodcodesnon-constructiveerror-controlcodingtechniques:providedifferentmethodsofdesigninggoodcodesNotation

modulo-2addition--EXCLUSIVEORoperationmodulo-2multiplication--ANDoperation1810.3LinearBlockCodes

Definitionoflinearcode:

ifanytwocodewordsinthecodecanbeaddedinmodulo-2arithmetictoproduceathirdcodewordinthecode.(封闭性)Systematiccode:

themessagebitsaretransmittedinunalteredform.Itsimplifiesimplementationofthedecoder.Figure10.4Structureofsystematiccodeword.1910.3LinearBlockCodes

(n,k)linearblockcode :ncodebits :kmessagebits :(n-k)paritybits,whicharecomputedfromthemessagebitsaccordingtoaprescribedencodingrule2010.3LinearBlockCodes

Mathematicalstructurebii=0,1,..,n-k-1

mi+k-n

i=n-k,n-k+1,..,n-1

ci

=bi=p0im0+p1im1+..+pk-1,imk-1where

pji=1ifbidependsonmj

0

otherwise(10.2)(10.3)(10.1)2110.3LinearBlockCodes

Matrixformm=[m0,m1,..,mk-1]b=[b0,b1,..,bn-k-1]c=[c0,c1,..,cn-1]b=mPp00p01..p0,n-k-1p10p11..p1,n-k-1pk-1,0pk-1,1..pk-1,n-k-1P=(10.4)(10.5)(10.6)(10.7)(10.8)2210.3LinearBlockCodes

Matrixform(cont.)Fromtheequationsin(10.4)-(10.6),cmaybeexpressedasfollows:c=[b|m]

=m[P|

Ik] =mG

WhereGisthek-by-ngeneratormatrix

G=[P|Ik]

where

Ik

isthe

k-by-kidentitymatrix.

G’skrowsarelinearlyindependent.(10.13)(10.10)(10.9)(10.12)2310.3LinearBlockCodes

Matrixform(cont.)LetHdenotethe(n-k)-by-nparity-checkmatrixH=[In-k|PT]

(10.14)H’s(n-k)rowsarelinearlyindependent.Wegetparity-checkequationasfollows:cHT

=

mGHT

=

0(10.16)24Figure10.5Blockdiagramrepresentationsofthegeneratorequation(10.13)andtheparity-checkequation(10.16).usedintheencodingoperationatthetransmitterusedinthedecodingoperationatthereceiver2510.3LinearBlockCodes

Example10.1RepetitionCodes(n,1)blockcodetwocodewordsinthecode:all-zerocodeword&all-onecodewordForn=5,thegeneratormatrixisG=[1111|1]Theparity-checkmatrixisH=100010100100101000112610.3LinearBlockCodes

Syndrome:DefinitionandPropertiesLetrdenotethe1-by-nreceivedvector,weexpressthevectorrasr=c+e(10.17)Wherec--theoriginalcodevector

e--theerrorvectororerrorpattern.

ei

=

1ifanerrorhasoccurredintheithlocation0otherwise(10.18)2710.3LinearBlockCodes

Syndrome(cont.)DefinitionTheerror-syndromevector(or

syndrome)is

definedas:

s=rHT

(10.19)Property1Thesyndromedependsonlyontheerrorpattern,andnotonthetransmittedcodeword.

s=eHT

(10.20)2810.3LinearBlockCodes

Syndrome(cont.)Property2

Allerrorpatternsthatdifferbyacodewordhavethesamesyndrome.

Wedefinethe2kdistinctvectorsei

as

ei

=

e+

ci

(10.21)WegeteiHT=eHT

(10.22)Cosetofthecode--thesetofvectors{ei,i=0,1,..,2k-1}2910.3LinearBlockCodes

Syndrome(cont.)FromEqu.(10.22),weget

s=eHT

=eiHT

Sotheinformationcontainedinthesyndromesabouttheerrorpatterneisnotenoughforthedecodertocomputetheexactvalueofthetransmittedcodevector.Nevertheless,knowledgeofthesyndromesreducesthesearchforthetrueerrorpatternefrom2nto

2n-kpossibilities.3010.3LinearBlockCodes

MinimumdistanceconsiderationsHammingdistanced(c1,c2)--thenumberoflocationsinwhichtheirrespectiveelementsdifferHammingweightw(c)--thenumberofnonzeroelementsinthecodevectorminimumdistance

dmin

--thesmallesthammingdistancebetweenanypairofcodevectorsinthecodeminimumdistancedmin

=smallestHammingweightofthenonzerocodevectors3110.3LinearBlockCodes

Minimumdistanceconsiderations(cont.)relationbetweentheminimumdistancedmin

andtheparity-checkmatrixH

ExpressthematrixHintermsofitscolumns

H=[h1,h2,..,hn]Andacodevectorcsatisfytheequation

HcT

=

0→dmin≤n-k+1Hence,theminimumdistanceofalinearblockcodeisdefinedbytheminimumnumberofcolumnsofthematrixH(orrowsofthematrixHT)

whosesumisequaltothezerovector.3210.3LinearBlockCodes

relationbetweentheminimumdistancedmin

andtheerror-correctingcapabilityofthecodestrategy

forthedecoder--pickthecodevectorclosesttothereceivedvectorr.DetectallerrorpatternsofHammingweightw(e)≤t1 ifandonlyif dmin≥t1+1CorrectallerrorpatternsofHammingweightw(e)≤t2ifandonlyifdmin≥2t2+1DetectallerrorpatternsofHammingweightw(e)≤t1,andcorrectallerrorpatternsofHammingweightw(e)≤t2 ifandonlyif dmin≥t1+t2+1(t1>t2)33Figure10.6

(a)Hammingdistanced(ci,cj)2t1.(b)Hammingdistanced(ci,cj)2t.Thereceivedvectorisdenotedbyr.3410.3LinearBlockCodes

Sputethesyndromes=rHT

2.accordingtos,identifythecosetleader,putethecodevector

c

=

r+

e0as

thedecodedversionofthereceivedvectorrNote:

eachcosetleaderhastheminimumHammingweightinitscoset

35Figure10.7

Standardarrayforan(n,k)blockcode.SubsetD1D2D2kcosetCosetleader3610.3LinearBlockCodes

Example10.2HammingCodesBlocklength:n=2m-1(m≥3)Numberofmessagebits:k=2m-1-mNumberofparitybits:m=n-kminimumdistance:dmin

=

3generatormatrixparity-checkmatrixrelationbetweentheminimumdistancedminandtheparity-checkmatrixHsyndromedecoding3710.3LinearBlockCodes

DualCode

Every

(n,k)linearblockcodewithgeneratormatrix

Gandparity-checkmatrix

Hhasadualcodewithparameters(n,n-k),

generatormatrix

Handparity-checkmatrix

G.3810.4CyclicCodes

asubclassoflinearblockcodeseasytoencodepossessawell-definedmathematicalstructureefficientdecodingschemestwofundamentalproperties:linearitypropertycyclicproperty3910.4CyclicCodes

Codepolynomial

c(X)=

c0+c1X+c2X2+...+cn-1Xn-1

(10.27)whereXisanindeterminate.Forbinarycodes,thecoefficientsci

are1sand0s.Multiplicationofthepolynomialc(X)byXmaybeviewedasashifttotheright.Lemma:

Ifc(X)isacycliccodepolynomial,thenthepolynomial

c(i)(X)=Xic(X)mod(Xn+1)

(10.33)isalsoacodepolynomialforanycyclicshifti.4010.4CyclicCodes

Generatorpolynomial

g(X)=

1+g1X+g2X2+...+gn-k-1Xn-k-1+Xn-k

(10.34)wherethecoefficientsgi

isequalto1or0.

Note:Acycliccodeisuniquelydeterminedbythegeneratorpolynomialg(X).g(X)isapolynomialofdegree(n-k)(thepolynomialofleastdegreeinthecode).g(X)isafactorof(Xn+1).4110.4CyclicCodes

Encodingprocedureforan(n,k)systematiccycliccode1.Multiplythemessagepolynomialm(X)byXn-k

.

m(X)=

m0+m1X+...+mk-1Xk-1

(10.36)2.DivideXn-k

m(X)

bythegeneratorpolynomialg(X),obtainingtheremainderb(X).3.Addb(X)toXn-k

m(X)

,obtainingthecodepolynomialc(X).

c(X)=b(X)+Xn-k

m(X)

4210.4CyclicCodes

Parity-checkPolynomial

(10.40)wherethecoefficientshi

are1or0.

Note:Acycliccodeisalsouniquelyspecifiedbythegeneratorpolynomialh(X).h(X)isapolynomialofdegreek.h(X)isalsoafactorof(Xn+1)anditsatisfies

g(X)h(X)=Xn

+1

(10.42)4310.4CyclicCodes

GeneratorandParity-checkMatricesGeneratormatrixP arity-checkmatrix

4410.4CyclicCodes

EncoderforcycliccodesEncodingprocedureforan(n,k)systematiccycliccode

1.multiplicationofthemessagepolynomialm(X)byXn-k

2.divisionofXn-k

m(X)

bythegeneratorpolynomialg(X)toobtaintheremainderb(X)3.additionofb(X)toXn-k

m(X) ThesethreestepscanbeimplementedbymeansoftheencodershowninFig.10.8,consistingofalinearfeedbackshiftregisterwith(n-k)stages.45Figure10.8

Encoderforan(n,k)cycliccode.4610.4CyclicCodes

Encoderforcycliccodes(cont.)

TheoperationoftheencodershowninFig.10.8proceedsasfollows:Thegateisswitchedon.Hence,thekmessagebitsareshiftedintothechannel.Assoonasthekmessagebitshaveenteredtheshiftregister,theresulting(n-k)bitsintheregisterformtheparitybits.Thegateisswitchedoff,therebybreakingthefeedbackconnections.Thecontentsoftheshiftregisterarereadoutintothechannel.4710.4CyclicCodes

Calculationofthesyndrome

Letthereceivedwordberepresentedbyapolynomialasfollows:r(X)=

r0+r1X+...+rn-1Xn-1

(10.46)

andr(X)maybeexpressedas:

r(X)=q(X)g(X)+s(X)

(10.47)whereq(X)denotesthequotientands(X)denotesthesyndromepolynomial(remainder,degree≤n-k-1).Fig.10.9showsasyndromecalculator.(identicaltotheencoderofFig.10.8)48Figure10.9

Syndromecalculatorfor(n,k)cycliccode.4910.4CyclicCodes

Propertiesofthesyndromepolynomial1.Thesyndromeofareceivedwordpolynomialisalsothesyndromeofthecorrespondingerrorpolynomial.2.Lets(X)bethesyndromeofareceivedwordpolynomialr(X).Then,thesyndromeofXr(X),acyclicofr(X),isXs(X)(modg(X)).3.Thesyndromepolynomials(X)isidenticalto(=)theerrorpolynomiale(X),assumingthattheerrorsareconfinedtothe(n-k)parity-checkbitsofthereceivedwordpolynomialr(X).5010.4CyclicCodes

Example10.3Hammingcodesrevisited

(7.4)cycliccodegeneratorpolynomialparity-checkpolynomialconstructionofacodewordinsystematicformgeneratormatrixparity-checkmatrixencoder(Fig.10.10)syndromecalculator(Fig.10.11)*AnycycliccodegeneratedbyaprimitivepolynomialisaHammingcodeofminimumdistance3.

51Figure10.10

Encoderforthe(7,4)cycliccodegeneratedbyg(X)1X

X3.52Figure10.11

Syndromecalculatorforthe(7,4)cycliccodegeneratedbythepolynomialg(X)1X

X3.5310.4CyclicCodes

Example10.4Maximal-Lengthcodes

Blocklength: n=2m-1

(m≥3)Numberofmessagebits:k=mMinimumdistance: dmin

=2m-1Generatorpolynomial

g(X)=(Xn

+1)/h(X) (10.52)whereh(X)isanyprimitivepolynomialofdegreem.*Maximal-lengthcodesarethedualofHammingcodes.Thepolynomialh(X)definesthefeedbackconnectionsoftheencoder.Thegeneratorpolynomialg(X)definesoneperiodofthemaximal-lengthcode,assumingtheinitialstateis00...01.5410.4CyclicCodes

Example10.4Maximal-Lengthcodes

(7,3)maximal-lengthcode--dualofthe(7,4)HammingcodeBlocklength:n=7

Numberofmessagebits:k=3Minimumdistance:dmin

=4 h(X)=1+X+X3 g(X)=1+X+X2+X4

initialstate:001outputsequence:111010055Figure10.12

Encoderforthe(7,3)maximal-lengthcode;theinitialstateoftheencoderisshowninthefigure.5610.4CyclicCodes

Cyclicredundancycheck(CRC)codeswell-suitedfor

errordetectioncandetectmanycombinationsoflikelyerrorseasyimplementationofbothencodinganderror-detectingcommonlyusedinautomatic-repeatrequest(ARQ)strategiesdigitalsubscriberlines5710.4CyclicCodes

Cyclicredundancycheck(CRC)codeserrorpatternsthatbinary(n,k)CRCcodescandetectAllerrorburstsoflengthn-korless.Afractionoferrorburstsoflengthequalton-k+1;thefractionequals1-2-(n-k-1).Afractionoferrorburstsoflengthgreaterthann-k+1;thefractionequals1-2-(n-k-1).Allcombinationsofdmin-1(orfewer)errors.Allerrorpatternswithanoddnumberoferrorsifthegeneratorpolynomialg(X)forthecodehasanevennumberofnonzerocoefficients.5810.4CyclicCodes

Bose-Chaudhuri-Hocquenghem(BCH)codest-errorcorrectingcycliccodes(candetect&correctuptotrandomerrorpercodeword)offerflexibilityinthechoiceofcodeparameters(blocklength&coderate)beamongthebestknowncodethesameblocklengthandcoderatePrimitiveBCHcodesBlocklength: n=2m-1

(m≥3)Numberofmessagebits: k≥n-mtMinimumdistance: dmin

≥2t+1Maximumnumberofdetectableerrors:t

5910.4CyclicCodes

Reed-Solomon(RS)codessubclassofnonbinaryBCHcodest-error-correctingRScodesBlocklength:n=2m-1

symbolsMessagesize:ksymbolsParity-checksize:n-k=2tsymbolsMinimumdistance:dmin

=2t+1symbols6010.4CyclicCodes

ReasonsforwideapplicationofRScodesmakehighlyefficientuseofredundancyblocklengthsandsymbolsizescanbeadjustedtoaccommodateawiderangeofmessagesizesprovideawiderangeofcoderatesefficientdecodingtechniquesareavailableforuse6110.5ConvolutionalCodesCharacteristic:messagebitscomeinseriallyratherthaninlargeblocksencodergeneratesredundantbitbyusingmodulo-2convolutionsrate1/n

convolutionalencoderconsistsof:anM-stageshiftregisternmodulo-2addersamultiplexerserializestheoutputsoftheaddersconstraintlengthK=M+162Figure10.13

(a)Constraintlength-3,rate-convolutionalencoder.(b)Constraintlength-2,rate-convolutionalencoder.*Theuseofnonsystematiccodesisordinarilypreferredoversystematiccodesinconvolutionalcoding.6310.5ConvolutionalCodesGeneratorpolynomial

(10.55)

whereD---theunit-delayvariable

()---thegeneratorsequence,denotethe impulseresponseoftheithpath.Here,theimpulseresponsemeanstheconnectionbetweentheoutputandtheinputofaconvolutionalencoder.1ifaconnectionexistsbetweentheithoutputandthej-stagedelayoftheinput

0otherwise6410.5ConvolutionalCodesExample10.5(Fig.10.13a)generatorpolynomial(path1&path2)messagepolynomialforsequence(10011)outputpolynomial(path1&path2)encodedsequenceNote:

ThemessagesequenceoflengthLproducesan encodedsequenceoflengthn(L+K-1).

Aterminatingsequenceof(K-1)zerosisappendedtothelastinputbitofthemessagesequence,inordertorestoretheshiftregistertoitszeroinitialstate.6510.5ConvolutionalCodesGraphicalformstoportraythestructuralproperties(orinput-outputrelation)ofaconvolutionalencoderCodeTree(Fig.10.14)Note:Thetreebecomesrepetitiveafterthefirst Kbranches.Trellis(Fig.10.15)StateDiagram(Fig.10.16)66Figure10.14

CodetreefortheconvolutionalencoderofFigure10.13a.67Figure10.15

TrellisfortheconvolutionalencoderofFigure10.13a.68Figure10.16

(a)AportionofthecentralpartofthetrellisfortheencoderofFigure10.13a.(b)StatediagramoftheconvolutionalencoderofFigure10.13a.6910.6MaximumLikelihoodDecodingofConvolutionalCodesTask:decoding--Giventhereceivedvector

r,makeanestimateofthemessagevector.Method:mone-to-onecorrespondencec(messagevector)(transmittedcodevector)putifandonlyifDecodingrule:

minimizetheprobabilityofdecodingerror(optimumrule).7010.6MaximumLikelihoodDecodingofConvolutionalCodesTheoryofmaximumlikelihooddecodingForequiprobablemessages,theprobabilityofdecodingerrorisminimizediftheestimateischosentomaximizethelog-likelihoodfunction.Decisionrule:

Choosetheestimateforwhichthelog-likelihoodfunctionlogp(r|c)ismaximum. (10.56)wherep(r|c)--conditionalprobability7110.6MaximumLikelihoodDecodingofConvolutionalCodes

Forbinarysymmetricchannel,r&carebinarysequencesoflengthN.

p(r|c)= (10.57)so

logp(r|c)= (10.58)where

(10.59)logp(r|c)=dlogp+(N-d)log(1-p) =dlog[p/(1-p)]+Nlog(1-p)(10.60)

whered

istheHammingdistancebetweenrandc.

p(ri|ci)

=

pifri≠ci1-p

ifri=ci

7210.6MaximumLikelihoodDecodingofConvolutionalCodesMaximumlikelihooddecodingruleforBSC

logp(r|c)=dlog[p/(1-p)]+Nlog(1-p)Forp<1/2,log[p/(1-p)]andlog(1-p)arenegative.Sothedecisionruleis:ChoosetheestimatethatminimizestheHammingdistancebetweenthereceivedvectorrandthetransmittedvectorc.

(10.61)maximumlikelihooddecoder→minimumdistancedecoder7310.6.1TheViterbiAlgorithmTheViterbialgorithm–maximumlikelihoodsequenceestimator(MLSE)

Itisanefficientalgorithmforpracticalimplementationofthemaximumlikelihooddecoding.Wemaydecodeaconvolutionalcodebychoosingapathinthecodetrelliswhosecodedsequencediffersfromthereceivedsequenceinthefewestnumberofplaces.7410.6.1TheViterbiAlgorithm

Codetrellisfor(n,k,K)

convolutionalcode2k(K-1)nodesinthetrellis2kbranchesdepartingeachnodeinthetrellisatlevelj≥K,2kpathsenteringanyofthenodesinthetrellis7510.6.1TheViterbiAlgorithmTheViterbialgorithm

Initialization

Labeltheleft-moststateofthetrellis(i.e.,theall-zerostateatlevel0)as0.Computationstepj+1

Letj=0,1,2,...,andsupposethatatthepreviousstepjwehavedonetwothings:Allsurvivorpathsareidentified.Thesurvivorpathanditsmetricforeachstateofthetrellisarestored.7610.6.1TheViterbiAlgorithmTheViterbialgorithm(cont.)Then,atlevelj+1,computethemetricforallthepathsenteringeachstateofthetrellisbyaddingthemetricoftheincomingbranchestothemetricoftheconnectingsurvivorpathformleveljforeachstate,identifythepathwiththelowestmetricasthesurvivorofstepj+1,therebyupdatingthecomputationFinalstep

Continuethecomputationuntilthealgorithmcompletesitsforwardsearchandreachestheterminationnode(i.e.,all-zerostate).7710.6.1TheViterbiAlgorithmDecodingwindow Whenthereceivedsequenceisverylong,adecodingwindowoflengthlisspecified,andthealgorithmoperatesonacorrespondingframeofthereceivedsequence,alwaysstoppingafterlsteps.Adecisionisthenmadeonthe"best"pathandthesymbolassociatedwiththebranchonthatpathisreleasedtouser.Next,thedecodingwindowismovedforwardonetimeinterval,andadecisiononthenextcodeframeismade,andsoon.7810.6.1TheViterbiAlgorithmExample10.6CorrectDecodingofReceivedAll-ZeroSequence

Encoder: Fig.10.13aTransmittedsequence:all-zerosequenceReceivedsequence:(0100010000...)

Decoder(Viterbialgorithm):Fig.10.1779Figure10.17

IllustratingstepsintheViterbialgorithmforExample10.6.8010.6.1TheViterbiAlgorithmExample10.7IncorrectDecodingofReceivedAll-ZeroSequence

Encoder: Fig.10.13aTransmittedsequence:all-zerosequenceReceivedsequence:(1100010000...)

Decoder(Viterbialgorithm):Fig.10.1881Figure10.18

IllustratingbreakdownoftheViterbialgorithminExample10.7.8210.6.2FreeDistanceofaConvolutionalCodeWhy?Thefreedistanceisthemostimportantsinglemeasureofaconvolutionalcode’sabilitytocombatchannelnoise.Definition

Thefreedistance(dfree)isdefinedastheminimumHammingdistancebetweenanytwocodewordsinthecode.Itcanbeobtainedquitesimplyfromthestatediagramoftheconvolutionalencoder.8310.6.2FreeDistanceofaConvolutionalCodeConsideranexample encoder: Fig.10.13a statediagram: Fig.10.16b signal-flowgraph(modifiedstatediagram:) Fig.10.19signal-flowgraphconsistsof:asingleinput&asingleoutputnodes&directedbranches84Figure10.19

Modifiedstatediagramofconvolutionalencoder.D,L--dummyvariablesexponentofD--HammingweightoftheencoderoutputexponentofL--lengthofeachbranch(alwaysequaltoone)8510.6.2FreeDistanceofaConvolutionalCodeOperatingrulesofasignal-flowgraphAbranchmultipliesthesignalatitsinputnodebythetransmittancecharacterizingthatbranch.Anodewithincomingbranchessumsthesignalsproducedbyallofthosebranches.Thesignalatanodeisappliedequallytoallthebranchesoutgoingfromthatnode.Thetransferfunctionofthegraphistheratiooftheoutputsignaltotheinputsignal.8610.6.2FreeDistanceofaConvolutionalCodeInput-outputrelationsinFig.10.19

b=D2La0+Lc c=DLb+DLd d=DLb+DLd a1