纠错编码习题解答

纠错编码习题解答第一章1.1Solution:p=0.05(1)ThecorrectdecodingPcisPc=P0=C40p0(1-p)4=0.8145(2)ThedecodingerrorPeisPe=P2+P4=C42p2(1-p)2+C44p4(1-p)0=0.0135(3)ThedecodingfailurePfisPf=C41p(1-p)3+C43p3(1-p)=0.17201.2Solution:Becausethesuccessratedoesnotfallbelow99%,thenthedecodingfailurePf<1%.Andp<<1,Pf=P1=n*0.001*0.999n-1<0.01Son<=10.thenthemaximumblocklengthnsuchthatthesuccessratedoesnotfallbelow99%is10.1.3Solution:p=0.01Pf=P2=C42p2(1-p)2=C42*0.012*0.992=0.000588Sothedecodingfailurerateis0.000588.1.4Solution:(a)Error:Thereisoneerror(b)Correct(c)Failure(d)Error:Thereistwoerror1.5Solution:S1=v1+v2+v3+v4+v6+v8+v9+v12S2=v2+v3+v4+v5+v7+v9+v10+v13S3=v3+v4+v5+v6+v8+v10+v11+v14S4=v1+v2+v3+v5+v7+v8+v11+v15ErrorpatterneErrorSyndromes(e1,e2,e3,e4,e5,e6,e7,e8,e9,e10,e11,e12,e13,e14,e15)(s1,s2,s3,s4)00000000000000000000000000000000010001000000000000010001000000000000010001000000000000010001000000000000010000001100000000010000001100000000010000001100000000010000000101100000010000000001010000010000000001010000010000000000011100010000000000011100010000000000001111010000000000000110110000000000000010011.6Solution(1)s=(0000)~e=000000000000000~c=~e+v1=(000000000000000)+(100010011001001)=(100010011001001)(2)s=(1011)~e=000000010000000~c=~e+v2=(000000010000000)+(001001110100110)=(001001100100110)1.7Solution(1)v=(1011110)s=(110)~e=(0010000)~c=(1001110)(2)v=(1100110)s=(100)~e=(0000100)~c=(1100010)(3)v=(0001011)s=(000)~e=(0000000)~c=(0001011)第二章2.1Solution:cisins0000000000000111001011010010100101001110011101110011001101001011001101011010111101111110Fromthetable,wecanknoweveryCi’hasonlyCj.2.2Solution1111111r1-r21000101G2=0111010r2-r30100111=G1001110100101100001011r3-r40001011G1issystematicform.AndeverylinercoderisequivalenttoasystematiclinearcodeSothe(7,4)linearcodesgeneratedbyG1andG2equivalent.2.3SolutionInformationwordCodeword000000000001001110010010101011011011100100011101101101110110110111111000(a)C0=(000)G=(000000)C1=(001)G=(001110)C2=(010)G=(010101)C3=(011)G=(011011)C4=(100)G=(100011)C5=(101)G=(101101)C6=(110)G=(110110)C7=(111)G=(111000)(b)Ifp=0thenInformationwordCodeword000000000001001001010010010011011011100100100101101101110110110111111111Ifp=1thenInformationwordCodeword0000001110010011100100101010110111001001000111011010101101100011111110002.4SolutionBecausethe(4,3)even-paritycodeisalinearcode,Theminimumdistanced(Ci,Cj)=Wmin=2TheerrordetectionlimitisL=2-1=1Theerrorcorrectionist=(2-1)/2=0.5.Namely0.2.5Solution111010001110100001110100r4-r3-r2-r101110100H=11010010110100101111111110110001Sothesystematicformsis11101000011101001101001010110001BecauseH=[PT|In-k]andG=[Ik|P]ThenG=100010110100111000101101000101112.6Solution11101000101101110100HT=1111H=1101001011011111111101111001010100110001Soeivi=c+eisi=viHTei~~ci=vi+ei~conclusion000001000110011101010000010001100011Correctcodeword01010000001100111000absentDecodingfailure000110100111100111010010000001011001Incorrectcodeword第三章3.1solutionBecausex3+1x4+x+1x7+x3+1x7+x4+x3x4+1x4+x+1xthenq(x)=x3+1andr(x)=xcheckanswer:p1(x)q(x)+r(x)=(x3+1)(x4+x+1)+x=x7+x3+1=p2(x)sothesolutioniscorrect.3.2Solution(a)x3+x2+1x+1x4+x2+x+1x4+x3x3+x2+x+1x3+x2x+1x+10R(x+1)(x4+x2+x+1)=0(b)x3+x2+x+1x2+x+1x5+x3+x2+x+1x5+x4+x3x4+x2+x+1x4+x3+x2x2+x+1x3+x2+xx3+x2x2+x+1xsoR(x2+x+1)(x5+x3+x2+x+1)=x3.3Solution(1)Systematiccode:x3i(x)=x3(x3+x2+x+1)=x6+x5+x4+x3x3+x2+1x3+x+1x6+x5+x4+x3x6+x4+x3x5x5+x3+x2x3+x2x3+x+1x2+x+1soq(x)=Qg(x)(x3i(x))=x3+x2+1r(x)=Rg(x)(x3i(x))=x2+x+1thenc(x)=x3i(x)+r(x)=x6+x5+x4+x3+x2+x+1orc(x)=q(x)g(x)=(x6+x5+x4+x3)(x3+x+1)=x6+x5+x4+x3+x2+x+1(2)Nonsystematiccode:C(x)=i(x)g(x)=(x3+x2+x+1)(x3+x+1)=x6+x5+x3+13.4SolutionWhenthecodewordpolynomialsisx6+x3+x2+xThens(x)=Rg(x)(c(x)+e(x))=Rg(x)(x6+x3+x2+x+x3)=Rg(x)(x6+x2+x)x3+x+1x3+x+1x6+x2+xx6+x4+x3x4+x3+x2+xx4+x2+xx3x3+x+1x+1sos(x)=Rg(x)(c(x)+e(x))=x+1Whenthecodewordpolynomialsisx5+x3+x2Thes(x)=Rg(x)(c(x)+e(x))=Rg(x)(x5+x3+x2+x3)=Rg(x)(x5+x2)x2+1x3+x+1x5+x2x5+x3+x2x3x3+x+1x+1sos(x)=Rg(x)(c(x)+e(x))=x+1sotheresultingsyndromepolynomialsarethesame.3.5Solution(a)Thenumberofcycliccodeswithblocklength15isC51+C52+C53+C54=5+10+10+5=30(b)Thenumberof(15,11)cycliccodesis3.wheng(x)=x4+x+1org(x)=x4+x3+1org(x)=x4+x3+x2+x+1(c)Thegeneratorpolynomialsforthe(15,7)cycliccodesisg1(x)=(x4+x+1)(x4+x3+1)=x8+x7+x5+x4+x3+x+1 g2(x)=(x4+x+1)(x4+x3+x2+x+1)=x8+x7+x6+x4+1g3(x)=(x4+x3+1)(x4+x3+x2+x+1)=x8+x4+x2+x+13.6SolutionTheparity-checkpolynomialh(x)=(x15+1)/g(x)Andg(x)=x10+x8+x5+x4+x2+x+1x5+x3+x+1x10+x8+x5+x4+x2+x+1x15+1x15+x13+x10+x9+x7+x6+x5x13+x10+x9+x7+x6+x5+1x13+x11+x8+x7+x5+x4+x3x11+x10+x9+x8+x6+x4+x3+1x11+x9+x6+x5+x3+x2+xx10+x8+x5+x4+x2+x+1x10+x8+x5+x4+x2+x+10Soh(x)=x5+x3+x+1h*(x)=x5(x-5+x-3+x-1+1)=x5+x4+x2+1Sotheblocklengthofthecycliccodethatisdualtothe(15,5)codeis15andtheinformationlengthis15-5=10第四章4.1Solutionp(x)=x5+x4+xFromtheLFSR,weknowg(x)=x3+x2+x+1Shiftbinb0b1b2bfr(x)000000111111x2+x+1210110x2+x301101x+1400110x2+x510010x2601111x2+x+1Fromthechart,weobtainq(x)=x5+x3+1g(x)=x3+x2+x+1r(x)=x2+x+1soq(x)g(x)+r(x)=(x5+x3+1)(x3+x2+x+1)+(x2+x+1)=x3(x5+x4+x)=xrp(x)4.2Solutiong(x)=x4+x3+1Fromthestructureweobtainb3=bf=b2+bfb2=b1=b0=bin+bfshiftbinb0b1b2b3binr(x)0000000111000012111000x+13001100x2+x4110110x3+x2+15011001x+16111100x2+x+1Fromthechart,weknowthatq(x)=xr(x)=x2+x+1Soq(x)g(x)+r(x)=x(x4+x3+1)+(x2+x+1)=x5+x4+x2+1=p(x)4.3Solutionr(x)=Rg(x)[x8i(x)]=R(x8+x4+x+1)[x8(x5+x2+1)]x5+x2+x+1x8+x4+x+1x13+x10+x8x13+x9+x6+x5x10+x9+x8+x6+x5x10+x6+x3+x2x9+x8+x5+x3+x2x9+x5+x2+xx8+x3+xx8+x4+x+1x4+x3+1sor(x)=x4+x3+1thenthecodewordis010010100011001.4.4Solution(1)s(x)=Rg(x)[e(x)],syndrometablefor(15,11)errorcorrectingcodeshifter(x)s1000000000000001100012000000000000010x00103000000000000100x201004000000000001000x310005000000000010000x+100116000000000100000x2+x01107000000001000000x3+x211008000000010000000x3+x+110119000000100000000x2+1010110000001000000000x3+x101011000010000000000x+1001112000100000000000x3+x2+x111013001000000000000x3+x2+x+1111114010000000000000x3+x2+1110115100000000000000x3+11001（2）Whens(x)=Rg(x)[xn-ke(x)],syndrometablefor(15,11)errorcorrectingcodeshifter(x)S’1100000000000000x3+110012010000000000000x3+x2+111013001000000000000x3+x2+x+111114000100000000000x3+x2+x11105000010000000000x+100116000001000000000x3+x10107000000100000000x2+101018000000010000000x3+x+110119000000001000000x3+x2110010000000000100000x2+x011011000000000010000x+1001112000000000001000x3100013000000000000100x2010014000000000000010x001015000000000000001100014.5SolutionLow-orderinputi(x)=x8+x6+x+1withg(x)=x4+x+1shiftbinb0b1b2b3bfd0d1d2d3c0~c14S(x)000000000000000000000000010000000000000000000000000020000000000000000000000000031100001000000000000000000140010000100000000000000000x51101001010000000000000000x2+160010100101000000000000000x3+x70111010010100000000000000x2+x+180011100001010000000000000x3+x2+x90111110000101000000000000x3+x2+x+1101001111000010100000000000x3+x2111010111100001010000000000x3+x12-111010110000101000000000x2+x+113-011100011000010100000000x3+x2+x14-111110001100001010000000x3+x2+x+115-101110000110000101000000x3+x2+116-0101-0000111000010100010x3+x17-0010-0000111100001010001x218-0001-0000011110000101000x319-0000-00001011110000101000Soc(x)=(001010000111101)c(x)=x12+x10+x5+x4+x3+x2+14.6Solutionv(x)=x6+x4+x3+x2g(x)=x4+x+1bv(x)bv(x)=x6+x4+x3+x2s(x)=Rg(x)[v(x)]=x+1e(x)=x4Soc(x)=v(x)+e(x)=x6+x3+x2第五章5.1Solution(a)No.Becausethissetdoesnothaveauniqueidentityelement.(b)No.Becausethissetdoesnothaveauniqueinverse.(c)Yes.(d)No.Becausethissetdoesnotsatisfythepropertyofclosure.5.2Solutionx属于{0，1,2,3,4,5}Module-6addition+0123450012345112345022345013345012445012355012345.3SolutionModule-5additionModule-5multiplication+01234001234112340223401334012440123X123411234224133314244321additioninversemultiplicationinverse00-141233322414Module-7addition+012345600123456112345602234560133456012445601235560123466012345Module-7multiplication+123456112345622461353362514441526355316426654321+additioninversemultiplicationinverse00-1612543454325236165.4SolutionModulo-5arithmetic(a)2*7+6=2*2+6=4+6=4+1=0(b)(4-8)*3-2=(4+2)*3-2=1*3-2=1(c)(3+6)/2-4/3=4*3-4*2=2-3=2+2=4Modulo-7arithmetic(a)2*7+6=2*0+6=6(b)(4-8)*3-2=(4+6)*3-2=3*3-2=2-2=0(c)(3+6)/2-4/3=2*4-4*5=1-6=1+1=25.5SolutionBecause(01010)+(10110)=(11100)(10011)+(10110)=(00101)(11001)+(10110)=(01111)donotbelongtoanyoneofthesetofvectors.SothesetofvectorsdoesnotformavectorsubspaceofV5.5.6SolutionThethreevectorsare(00101),(11100)and(01111)10Takeany2linearlyindependentvectors,say(01010).(10110)astheinitialsetofvectorswhichisnotabasisofthegivensubspace.20Oftheremaining5nonzerovectors(11100)=(01010)+(10110)islinearlydependentonthe2vectoralreadyintheset.Anyoneoftheremaining5nonzerovectorsexcept(11100)canbeappendedtotheinitialset.30Taking,say,(00101)asthe3rdbasisvectorwefindallthevectorswithinthesubspace.V=a1(01010)+a2(10110)+a3(00101)VectorsofthesubspaceCoefficientsofthelinearcombination(a1,a2,a3)(00000)(000)(01010)(100)(11001)(111)(10011)(011)(10110)(010)(00101)(001)(11100)(110)(01111)(101)Soabasisofsubsetis(01010),(10110),(00101)andthedimensionofsubspaceis3becausethereare3basisvectors.5.7SolutionBecauser=n-k=kthecodeis(8,4),thenitsatisfythislaw.Becauseaself-dualcodeshouldsatisfyH=G.G=[Ik|P]1110100010011100H=[PT|In-k]=01110100r1+r21010011011010010r2+r30110001110110001r3+r4101100010010110100101101r1+r410001010r4+r1+r210001011r2+r10100111001001110r3+r310110001000101111000101101001110=G0010110100010111101111101000PPT=11100111=0100=I110111010010011110110001Sothe(8,4)codewithgeneratormatrixisself-dual.第六章6.1Solution(1)p1(x)=x4+x3+x+1(a)p1(1)=1+1+1+1=0Thenp1(x)isnotirreducible.(b)p1(x)isnotprimitive.(2)p2(x)=x2+x+1(a)p2(0)=p2(1)=1Thenp2(x)isirreducible.(b)Imagea2+a+1=0,thena2=a+1aisarootanda∈GF(22)Sop2(x)isprimitive.(3)p3(x)=x3+x2+1(a)p3(0)=p3(1)=1.Thenp2(x)isirreducible.(b)Imagea3+a2+1=0,thena3=a2+1aisarootanda∈GF(23)Sop3(x)isprimitive.6.2Solution000101a10a2=a+111Imagea2+a+1=0,thena2=a+1ThefieldelementsofGF(22)P(0)=0+0+1=1P(1)=1+1+1=1P(a)=a2+a+1=a+1+a+1=0P(a2)=a4+a+1=(a+1)2+a+1=0Sotherootofp(x)=0arex=aandx=a