通信原理（英文版）第10章

Chapter10ChannelCodingandErrorControl10.1IntroductionChannelcoding:Purpose:

toimprovethereliabilityofsignaltransmission.Method:toaddsomeredundantbitsinordertodiscoverorcorrecterrors.

Errorcontrol:allerrorcorrectionmeasuresincludingchannelcoding.Causationsforproducingerrorsymbols:Intersymbolinterferenceevokedbymultiplicativeinterference.Signaltonoiseratioreductioncausedbyadditiveinterference.

1Classificationofchannels:accordingtothestatisticalcharacteristicsoftheerrorsymbolscausedbyadditiveinterference,Randomchannel:Errorsymbolsoccurrandomly,e.g.,errorsymbolscausedbyadditivenoise.

Burstchannel:theoccurrenceisrelativelyconcentrated,e.g.,theerrorsymbolscausedbypulseinterference.

Mixedchannel2KindsoferrorcontroltechniquesErrordetectionandretransmission:Theerrorsymbolscanbediscovered,butthelocationsoftheerrorscan’tbedetermined.Thecommunicationsystemsneedtohavethebidirectionalchannels.

FEC:utilizestheerrorcontrolsymbolsattachednotonlytodiscovertheerrorsymbols,butalsotocorrecttheerrorsymbols.Feedbackcheck:Thereceivedsymbolswillbereturnedtothetransmitterforcomparisonofthemwiththeoriginaltransmittedsymbols.Disadvantages:needofbidirectionalchannelandratherlowtransmissionefficiency.3Errordetectionanddeletion:Whentheerrorsymbolsarediscoveredinthereceiver,theywillbedeletedimmediately.Itissuitableonlyinsystemswherealotofredundancyexistsinthetransmittingsymbols,andthedeletedpartofthereceivedsymbolsdoesn’tinfluencetheapplication.

4Parametersofthecodesequencen－totalnumberofsymbolsinthecodesequencek－numberofinformationsymbolsinthecodesequencer

－numberoferrorcontrolsymbolsinthecodesequencek/n

－coderate(n-k)/k=r/k－redundancy5ARQsystemStop-and-waitARQ

systemPullbackARQ

systemStop-and-waitARQsystemReceiveddataACKACKNAKACKACKNAKACK1233455tTransmittingdata12334556tBlockinerrorBlockinerrorPullbackARQsystem214365798ReceiveddataBlockinerrorBlockinerror91011101112576ACK1NAK5NAK9ACK55769521436798Transmittingdata1011101112RetransmittedblockRetransmittedblock6SelectiverepeatARQ

systemARQincomparisonwithFECAdvantagesLessparitysymbols,highercoderateThecalculationcomplexityoferrordetectionislow.ItcanadaptthedifferentcharacteristicsofthechannelsDisadvantagesItrequiresduplexchannels

cannotbeusedintheunidirectioncommunicationsystemsorbroadcastingsystems.Thetransmissionefficiencyisdecreasedduetoretransmission.Whenthechannelinterferenceisserious,communicationisvirtuallyinterrupted.

SelectiverepeatARQsystem9ReceiveddataBlockinerrorBlockinerror21436575981011131412Transmittingdata995852143671011131412RetransmittedblockRetransmittedblockNAK9ACK1NAK5ACK5ACK9710.2BasicPrinciplesofErrorControlCodingBlockcode–asanexampleAssume:thereisacodecomposedof3binarysymbols,sothereare23=8differentpossiblecodewords:

000–fine 001–cloud 010–overcast011–rain 100–snow101–frost 110–fog 111–hail

Now,iftheerrorsymbolsoccur,thenerrorinformationwillbereceived.Ifonly4codewordsamongthese8codewordsareallowedtobeusedfortransmissionoftheweather,e.g.,let

000–fine011–cloud101–overcast110–rain

arepermissioncodewords,

other4kindsareforbiddencodewords.

Then,thereceivercandetectoneerrorsymbolinacodeword.Thiscodecanonlydetecttheerrorsymbols,andcannotcorrecttheerrorsymbols.

8Ifonlytwopermissioncodewordsaredefined:

forexample

000–fine111–rain

thenthecodecandetectatmosttwoerrorsymbols,orcorrectoneerrorsymbol.

9ConceptofblockcodeBlockcodeword＝informationbits＋checkbitsExpressionofblockcode:(n,k) where

n－totallengthofcodeword

k－numberofinformationbits

r=n–k

－numberofofcheckbits

Thecodewordinthetableisa(3,2)code.InformationbitsCheckbitsFine000Cloud011Overcast101Rain11010Structureofblockcode:Parametersofblockcode:Codeweight:numberof1sinthecodewordCodedistance:thenumberofbitswhichhavedifferentvaluesinthecorrespondinglocationsoftwocodewords,andalsocalledHammingdistanceMinimumcodedistance

(d0):minimumdiatanceamongthecodewordskinformationbitsrcheckbitsan-1an-2...arar-1an-2...a0tCodelengthn=k+r11Geometicmeaningofcodedistance:byusingacodewithn=3

asexampleGeneralspeaking,codedistanceistheHammingdistancebetweenthevertexesofaunitregularpolyhedroninanndimensionalspace.(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a112Errorcorrectionanddetectionabilitiesofacodearedecidedbytheminimumcodedistance

d0

.Fordetectinge

errorsymbols,requireForcorrecting

terrorsymbols,

requireed00123BAHammingdistanceTwocodewordswithcodedistance3tAtd0B301245Twocodewordswithcodedistance5Hammingdistance13Forcorrectingt

errorsymbols,anddetectinge

errorsymbolsatthesametime,require

Errorcorrectionanddetectioncombinationmode:Whenthenumberoferrorsymbolsissmall,thesystemoperatesaccordingtotheFECmodesoastosaveretransmissiontimeandimprovetransmissionefficiency.

Whenthenumberoftheerrorsymbolsislarge,thesystemoperatesaccordingto

errordetectionwithretransmissionmodesoastoreducethetotalbiterrorprobability.

HammingdistanceABe1tt(c)Twocodewordswithcodedistance(e+t+1)1410.3PerformanceofErrorCorrectionSystem10.3.1Relationshipbetweenerrorsymbolprobabilityand bandwidth

Adoptingerror-correctioncodingfordecreaseoferrorsymbolprobability,thepricepaidisincreaseofbandwidth.10-610-510-410-310-210-1PeCDE2PSKAftercodedABEb/n0(dB)1510.3.2Relationshipbetweenpowerandbandwidth Iftheerrorsymbolprobabilityiskeptunchanged,whenthereiscodingforsavingpower,thenthepriceisstillthebandwidthincreased.

10-610-510-410-310-210-1PeCDE2PSKAftercodedABEb/n0(dB)16

10.3.3Relationshipbetweentransmissionrateandbandwidth

Foragiventransmissionsystem,therelationshipbetweenitstransmissionrateandEb/n0：

whereRB

－symbolrate.

Iftheerrorcorrectioncodingisusedtoincreasethetransmissionrateandkeeptheerrorsymbolprobabilityunchanged,thenthepricepaidisstilltheincreaseofthebandwidth.10-610-510-410-310-210-1PeCDE2PSKAftercodedABEb/n0(dB)1710.3.4Codinggain

Definition:Undertheconditionofconstanterrorsymbolprobability,thesignaltonoiseratioEb/n0savedbyusingerrorcorrectioncodingiscalledcodinggain

where(Eb/n0)u

－signaltonoiseratiobeforecoding(dB)；

(Eb/n0)c

－necessarysignaltonoiseratioaftercoding

(dB)1810.4Parity-CheckCodes

10.4.1Onedimensionalparity-checkcodeOddparitycode－classifiedintooddparitycodeandeven paritycode.Intheparity-checkcode,thereisonlyonecheckbit,sothecoderateequalsk/(k+1).Intheevencheckcode,thecheckbitissodesignedthatthesummationofallthebitsinthecodewordyieldsanevenresult: wherea0

isthecheckbit,otherbitsareinformationbits.Thecheckbitinoddcheckcodesmakesthenumberof1sinthecodewordbeodd:19Errordetectionability－candetectodderrorsymbols.

Assume:

thelengthofthecodewordisn,andtheoccurrencesoferrorsymbolsinthecodewordareindependentandhaveequalprobability,thentheprobabilityofjerrorsymbolsthatoccurinacodewordis

where

—thenumberofcombinationsofjerrorsymbolsoccurredinn

codewords.Parity-checkcodescan’tdetectevenerrorsymbolsinacodeword,hencetheprobabilitythattheerrorsymbolsinacodewordcan’tbedetectedequals:

－when

niseven －when

n

isodd

20[Example]Thecodein thetableisaneven

paritycode.Assumethe

errorsymbolprobability ofthechannelis10-4,and

theoccurrencesoferror areindependent.

Calculate theundetectablesymbolerrorprobability.

Substitutingthegivenconditionintothecalculationresultis

Ascanbeseenfromtheresult,thiscodecanreducetheerrorsymbolprobabilityfromtheorderofmagnitude10-4to10-8.InformationbitCheckbitFine000Cloud011Overcast101Rain1102110.4.2Twodimensionalparity-checkcodeCoderateequalsCandetectevenerrorsymbols.SuitablefordetectingbursterrorsymbolsCancorrectapartoferrorsymbols………………………2210.5LinearBlockCodesBasicconceptAlgebraiccode－utilizationofalgebraicequationstogeneratetheparity-checkbits.Linearblockcode－therelationshipbetweentheparity-checkbitsandtheinformationbitsisdeterminedbylinearalgebraicequations.Hammingcode－akindoflinearblockcodes,whichcancorrectoneerrorsymbol.

syndrome:S

Ineverparitycheckcode,calculate

i.e.,practicallycalculate

andchecktheSisequalto0

ornot.

Siscalledsyndrome.Parity-checkrelationship:23BasicprinciplesoferrorcorrectionIn,Shasonlytwovalues,henceitcanonlyexpresserrorornoerror,butcan’tdeterminethelocationoftheerror.

Ifthelengthofthecodewordincreasesonebit,thus,twosyndromescanbeobtained.Thepossiblevaluesoftwosyndromeshave4combinations,i.e.,00,01,10,and11;hencetheycanexpress4differentkindsofinformation.Ifoneofthecombinationsisusedtoexpressnoerrorsymbol,thentheother3combinationscanbeusedtoindicate3differentlocationsofanerrorsymbol.Therefore,itmayhavetheabilityoferrorcorrection.24Generallyspeaking,iftherearerparity-checkrelationships,thenrsyndromescanindicate(2r–1)differentlocationsofanerrorsymbol.

Onlyifthenumberoferrorsymbollocationswhichcanbeindicatedbythesyndromesisequalto,orlargerthan,thelengthnofthecodeword,theerrorsymbolinanylocationofthecodewordcanbecorrected;i.e.,require25HammingcodeExample:Assumeitisrequiredtodesignablockcode(n,k)whichcancorrect1errorsymbol,andthereare4informationbitsinagivencodeword,i.e.,k=4.

From

Nowitisrequiredthatthenumberofparity-checkbitsr

3。Iflet

r=3,then

n=k+r=7.Here,

a6

a5

a4

a3

a2

a1

a0

areusedtoexpressthese

7symbols,andS1S2

S3

areusedtoexpresssyndromes,thenthe

3

syndromescanjustindicate23–1=7locationsoferrorsymbols.26IftherelationshipbetweenthesyndromesandthelocationsoftheerrorsymbolscanbedefinedbythefollowingTable,thenonlywhenthereiserrorsymbolinthelocationsa6

a5

a4

a2,thevalueofthesyndromeS1equals1;otherwise,thevalueofS1equalszero.Itmeansthatthe4symbolsa6

a5

a4anda2formevenparity-checkrelationship:Similarly,wehaveS1S2S3错码位置S1S2S3错码位置001a0101a4010a1110a5100a2111a6011a3000无错码27Duringcoding,thevaluesofinformationbitsa6

a5

a4

a3aredecidedbytheincomingsignal,whicharerandom.Theparity-checkbitsa2

a1

a0aredeterminedbytheparity-checkrelationship,andtheyshouldensurethatthesyndromesintheabove3equationsequalzero,i.e.,Iftheinformationbitshavebeengiven,thenforcalculationofparity-checkbitstheaboveequationcanbewrittenasTheresultofcalculationaccordingtotheaboveequationis:Informationbita6a5a4a3Checkbita2a1a0Informationbita6a5a4a3Checkbita2a1a0000000010001110001011100110000101011010010001111010110010100110110000101011011101010011001111101000111000111111128Duringdecodinginthereceiver,syndromesS1，S2,andS3arecalculatedaccordingto thenaccordingtothefollowingtabletodecidethelocationoftheerrorsymbol:

Example:Ifthereceivedcodewordis0000011,thenaccordingtotheabove3equationstheresultofcalculationis:

S1=0，S2=1，S3=1。Thus,accordingtothetable,thelocationoftheerrorsymbolisa3.S1S2S3LocationoferrorsymbolS1S2S3Locationoferrorsymbol001a0101a4010a1110a5100a2111a6011a3000无错码29Intheaboveexample,theHammingcodeisa(7,4)

code,itsminimumcodedistance

d0=3.Fromtheequation weknowthatthiscodecandetect2errorsymbols,orcorrect1errorsymbol.CoderateofHammingcode:

Whenr(orn)isverylarge,theaboveequationapproaches1.Therefore,Hammingcodesarehighefficientcodes.30GeneralprinciplesoflinearblockcodesTherelationshipbetweentheparity-checkbitsandtheinformationbitsoflinearblockcodes

canberewrittenas

intheaboveequation,

hasbeenwrittenas+forshort.

31Parity-checkmatrix:Theaboveequation

canberewrittenasthefollowingmatrixequation

（mod2）

Theaboveequationcanbesimplifiedas

HAT=0Tor

AHT=032

HAT=0T

where

－calledparity-checkmatrixPropertiesofparity-checkmatrixH

H

decidestherelationshipbetweeninformationbitsandparity-checkbitsinthecodeword.ThenumberofrowsofH

isthenumberofparity-checkequations,i.e.,thenumberofparity-checkbitsr.Thelocationsof1sineachrowofHindicatethatthecorrespondingsymbolsareinvolvedintheparity-checkequations.

A=[a6

a5

a4

a3

a2

a1

a0]

0=[000]33Hcanbedividedintotwoparts,e.g., －typicalparity-checkmatrixwherePisamatrixwiththeorderofr

k,andIr

isaunitsquarematrixwiththeorderofr

r.TherowsinanHmatrixshouldbelinearlyunrelated;otherwise,rlinearlyunrelatedparity-checkequationscannotbeobtainedIfamatrixcanbewrittenastypicalmatrix[PIr],thenitsrowsarecertainlylinearlyunrelated.34GeneratormatrixExample:

canbewrittenas

Aftertransposingthetwosidesoftheaboveequationseparately,itbecomeswhereQ

isamatrixwiththeorderofk

r,

itisthetranspositionofP

,i.e.,

Q=PT

35

Aunitsquarematrixwiththeorderofkisaddedtotheleft-handsideofQtoformthefollowingmatrix:

－calledgeneratormatrix

Giscalledgeneratormatrix,becauseitmaybeusedtogeneratethewholeofcodewords

A,i.e.,36PropertiesofgeneratormatrixGeneratormatrixwiththeformof[IkQ]iscalledtypicalgeneratormatrix.

InthecodewordAgivenbythetypicalgeneratormatrix,iftheparity-checkbitsareinsertedaftertheinformationbits,thenthecodeiscalledsystematiccode.

TherowsofmatrixGmustalsobelinearlyunrelated.

Iftherearealreadyklinearlyunrelatedcodewords,thentheycanbeusedasgeneratormatrixG,andothercodewordscanbegeneratedfromit.37Errorpattern

Assume:

thetransmittingcodeword

A

isarowmatrixwith

n

columns:

ThereceivedcodewordisarowmatrixBwithncolumns:

Letthedifferencebetweenthereceivedcodewordandthetransmittingcodewordbe

whereE

istherowmatrixoftheerrorsymbols.

－calledtheerrorpattern

where

(i=0,1,…,n-1) If

ei

=0,thenitexpressnoerror;ifei=1,thenitexpressthatthereisanerror.

B–A=E(mod2)38Syndromematrix

B–A=EcanberewrittenasB=A+E TheaboveequationshowsthatthesumofthetransmittingcodewordAandtheerrorsymbolmatrixEequalsthereceivedcodewordB.

Example:Ifthetransmittingcodeword

A=[1000111],theerrorsymbolmatrixE=[0000100],then

thereceivedcodewordB=[1000011].

39Duringdecodinginthereceiver,

substitutethereceivedcodeword

B

forthelocationofAinequation

AHT=0. Ifthereisnoerrorinthereceivedcodeword,thenE=0，B=A.Afterthesubstitution,theequationstillholds,i.e.:

BHT=0 Assumetheleft-handsideoftheequationequalsS,i.e.,

BHT=S Substituting

B=A+Eintotheaboveequation,obtain S=(A+E)HT=AHT+EHT40

S=(A+E)HT=AHT+EHTthefirsttermintheright-handsideoftheaboveequationequals0,therefore

S=EHT

－syndromematrix

WhenHhasbeendetermined,SintheaboveequationisonlyrelatedtoE,andisunrelatedtoA.

ThismeansthatthereisadefinitelineartransformrelationshipbetweenSanderrorsymbolsE.

IfSandEhaveaone-to-onecorrespondingrelationship,thenScanrepresentthelocationsoferrorsymbols.41Closenessoflinearcode:

IfA1andA2aretwocodewordsofalinearcode,then(A1+A2)isstillacodewordinthatlinearcode.『Proof』If

A1andA2aretwocodewords,thenwehave: A1HT=0,A2HT=0 Addingtheabovetwoequations,weobtain

A1HT+A2HT=(A1+A2)HT=0

Therefore(A1+A2)isalsoacodeword.

Sincethelinearcodehascloseness,thedistancebetweentwocodewords(A1andA2)mustbetheweight(i.e.,thenumberof“1”s)ofanothercodeword(A1+A2).Hence,theminimumdistanceofthecodeisjusttheminimumweightofthecode.4210.6Cycliccodes

10.6.1Conceptofcycliccodes

Cyclicityisdesignatedinawaythat

anycodewordobtainedbyanend-aroundshiftofacodewordinacodeisalsoacodewordinthiscode.

Example:

Allcodewordsofa

(7,3)cycliccodeareasfollows:

Ifthesecondcodewordinthistableshiftedonebittotheright,thenitwillbecomethefifthcodeword;ifthefifthcodewordcyclicshiftsonebittotheright,thenitwillbecometheseventhcodeword.No.ofcodewordInformationbitParity-checkbitNo.ofcodewordInformationbitParity-checkbita6a5a4a3a2a1a0a6a5a4a3a2a1a0100000005100101120010111610111003010111071100101401110018111001043Generalcondition

If(an-1

an-2…a0)isacodewordofacycliccode,thenthecodewordsaftercyclicshift

(an-2

an-3…a0

an-1) (an-3

an-4…an-1

an-2) …… (a0

an-1…a2

a1)arestillthecodewordsofthiscode.Polynomialexpression

Acodeword

(an-1

an-2…a0)withlengthncanbeexpressedas

xintheaboveequationhasnotanymeaning,andonlyitspowerisusedtorepresentthelocationofthesymbol.Forexample:thecodeword1100101

canbeexpressedas4410.6.2OperationofcycliccodesModulo-noperationofintegers

Thereismodulo-noperationintheintegeroperation.Forexample,inmodulo-2operation,thereare

1+1=20(mod2)，1+2=31(mod2)，23=60(mod2)

Generallyspeaking,ifanintegermcanbeexpressas

whereQisaninteger,theninmodulo-n

operation,

wehave

m

p(modn) Therefore,inmodulo-noperation,anintegermequalstheremainderresultingfromdividingitbyn.45Modulooperationofcodepolynomial

IfanarbitrarypolynomialF(x)isdividedbyapolynomialN(x)ofdegreen,theresultobtainedisaquotientQ(x)andaremainderR(x)ofdegreelessthann,i.e.,

TheninthearithmeticofmoduloN(x),wehave

Nowtheoperationofcoefficientsofcodepolynomialisstilldoneaccordingtomodulo-2.Forexample,x3isdividedby(x3+1),andtheremainderis1:

Example:

Since

x

x3+1x4+x2+1

x4+x

x2+x+1

Additionandsubtractionarethesameinmodulo-2operation.46Mathematicalexpressionofcycliccodes

Incycliccodes,letT(x)beacodewordwithlengthn,

if

thenT(x)isalsoacodewordofthatcode.

[Proof]Assumeacycliccodeisthenwehave

T(x)intheaboveequationistheresultofleft-handcyclicshiftitimesofthecodewordT(x).

Example:acycliccodewordis1100101,i.e.,

Iflet

i=3,thenwehave

Thecodewordcorrespondingtotheaboveequationis0101110.Itistheresultofleft-handshift3timesofT(x).Conclusion:

Acycliccodewordwithlengthnmustbearemainderofoperationmodulo-(xn+1).47GenerationofcycliccodesThewholecodewordcanbegeneratedfromthekinformationbits,ifwehavethegeneratormatrix

G.

Example:

where

EachrowofthegeneratorG

isacodeword.Hence,ifk

codewordshasbeenfound,thenwecanconstructG.Asmentionedabove,thekknowncodewordsmustbelinearlyunrelated.Incycliccodes,a(n,k)codehas2kdifferentcodewords.Ifg(x)expressesthecodeword,andtheforegoing(k-1)bitsofitareall0s,theng(x)，xg(x)，x2

g(x)，，xk-1

g(x)areallcodewords,andthisk

codewordsarelinearunrelated.

Hence,theycanbeusedtoconstructG.48Inadditiontothecodewordofall0s,thereisnotanycodewordwhichhascontinuousk0sincycliccodes.Otherwise,afterseveralcyclicshifts,acodewordwherekinformationbitsareall0s,buttheparity-checkbitsarenotall0s,willbeobtained.Obviously,thisisimpossibleinlinearcodes.Hence,g(x)mustbea(n–k)degreepolynomial,theconstanttermofwhichisnotzero.Andthisg(x)istheonlypolynomialofdegree(n–k)inthis(n,k)code.Sinceifthereweretwo,thentheadditionofthesetwoshouldbealsoacodewordduetotheclosenessofthecode,andthedegreeofthepolynomialofthiscodewillbesmallerthan(n–k),i.e.,thenumberofcontinuous0sislargerthan(k–1).Obviously,thisiscontradictorytotheaboveconclusion.Thisexclusive(n–k)degreepolynomialg(x)iscalledgeneratorpolynomialofthecode.Onceg(x)isdetermined,thenthewhole(n,k)cycliccodeisdetermined.49Therefore,generatormatrixGof cycliccodescanbewrittenasExample:ThecodeintheaboveTableisa(7,3)cycliccode,whosen=7,k=3,andn–k=4.Theexclusive(n–k)=4degreecodepolynomialrepresentsthesecondcodeword,0010111;thecorrespondingcodepolynomial,i.e.thegeneratorpolynomial,isg(x)=x4+x2+x+1.No.ofcodewordInformationbitParity-checkbitNo.ofcodewordInformationbitParity-checkbita6a5a4a3a2a1a0a6a5a4a3a2a1a0100000005100101120010111610111003010111071100101401110018111001050

g(x)=x4+x2+x+1is“10111” Substitutingg(x)intotheabovematrix,obtain

or SincetheaboveequationdoesnotaccordwiththeformG=[IkQ],itisnotatypicalgeneratormatrix.However,afterlineartransformation,itisnotdifficulttobeconvertedtoatypicalgeneratormatrix.

51ThepolynomialexpressionT(x)ofthecycliccodewordis TheaboveequationilluminatesthatallcodepolynomialsT(x)canbedividedexactlybyg(x),andanarbitrarypolynomialofthedegreenotlargerthan(k–1)multipliesg(x)resultingacodepolynomial.52Findcodegeneratorpolynomial

SinceanarbitrarypolynomialT(x)ofacycliccodeisthemultipleofg(x),itcanbewrittenas

T(x)=h(x)g(x) andgeneratorpolynomialg(x)itselfisalsoacodeword,i.e.,

T

(x)=g(x) SincecodewordT

(x)isapolynomialofdegree(n–k),xkT

(x)isapolynomialofdegreen.Itisknownfrom

xk

T

(x)isalsoacodewordintheoperationof

modulo-(xn+1),sowehave

Thenumeratoranddenominatorintheleft-handsideoftheaboveequationarepolynomialsofdegreen,sothequotientofdivisionQ(x)=1.Hence,theaboveequationcanbewrittenas

53Substituting

T(x)=h(x)g(x)andT

(x)=g(x)into

Aftersimplifiedweobtain Theaboveequationilluminatesthatthegeneratorpolynomialg(x)shouldbeafactorof(xn+1).Forexample,(x7+1)canbedecomposedas

Tofindthegeneratorpolynomialg(x)of(7,3)cycliccode,itisnecessarytofindafactorofdegree(n–k)=4.Itisnotdifficulttoseethattherearetwosuchfactors,i.e.,

Theabovetwoequationsmaybethegeneratorpolynomial.

However,differentgeneratorpolynomialgeneratesdifferentcycliccodes.5410.6.3CodingofcycliccodesTomultiplym(x)byxn-k.Thisoperation,infact,istoattach(n–k)0stotheendoftheinformationbits.Forexample,iftheinformationbitsare110,thenitspolynomialism(x)=x2+x.Whenn–k=7–3=4,xn-km(x)=x4(x2+x)=x6+x5,anditexpressescodeword1100000.Todividexn-km(x)byg(x),theresultsarethequotientQ(x)andtheremainderr(x),i.e.,wehaveForexample,ifg(x)=x4+x2+x+1isgiven,thenwehave

Theaboveequationistheoperationexpressedbycodepolynomial.Itisequivalenttothefollowingequation:CodewordT(x)obtainedis:T(x)=xn-k

m(x)+r(x)

IntheaboveexampleT(x)=1100000+101=1100101 55

10.6.4DecodingofcycliccodesForerrordetection:Whenthereisnoerrorinthereceivedcodeword,thereceivedcodeword

R(x)canbeexactlydividedbyg(x);

i.e.,inth