Some Improvements of a Decoding Algorithm for Line

SomeImprovementsofaDecodingAlgorithmforLinearCodesMrMiodragZivkovicDecember2,2005AbstractAprobabilisticmethodfordecodinglinearcodesisconsidered,whereaposterioriprobabilitiesoferror(APPE)arerepeatedlycom-puted.MethodsformorepreciseandmoreecientcomputationofAPPEareproposed.Thesemethodsareusefulwhencombinedwithsomeinformationsetdecodingmethod.TheauthoriswiththeInstituteforappliedmathematicsandelectronics,Beograd,Yugoslavia;mailingaddressis:MiodragZivkovic,11000Beograd,Paunova61/16,Yugoslavia1IntroductionBinarylinear(n;k)codeCwiththeparitycheckrnmatrixHisthenull-spaceofH,wherer=nk.Additions,denotedby,andmultiplicationsareoperationsoftheeldGF(2).Unlessotherwisespecied,allvectorswillbeassumedtobecolumnvectors.Letusintroducethefollowingusefulnotation.SupposeMisamatrix,andletJbeanarbitrarysubsetofthesetofcolumnindicesinM.ThenMJwilldenotethematrixwhosecolumnsareallthecolumnsofMwithindicesinJ,inthesameorderastheyappearinM.IfMisacolumnvector,thenMTJTwillbewrittensimplyasMJ.HereTstandsfortheoperationofthematrixtransposition.IfJ=fjg,theninsteadofMfjgitwillbewrittenMj.Forabinaryvectorutheweightofu,i.e.thenumberofonesamongitscoordinateswillbedenotedbyW(u).LetE=[E1;E2;:::;En]Tdenotetheerror{vector,i.e.then{dimensionalbinaryrandomvectorwithpairwiseindependentcoordinates,havingtheprobabilitydistributiongivenbyPfEi=1g=pi;PfEi=0g=qi=1pi;1in:Letx2Cbearbitrarycodeword.ThenthevectorY=xEiscalledthereceivedmessage,becauseitisformedfromthecodewordxbyincludingrandomerrors.Todecodeareceivedmessagey,therealizationoftherandomvariableY,meanstondacodeword^x2Csuchthatforeveryx02CthefollowinginequalityholdsPfE=^xygPfE=x0yg:Symbol{by{symboldecodingmethodforlinearcodes[5]consistsofcom-plementingthosebitsofthereceivedmessagewhichhaveaposterioriproba-bilityoferrorgreaterthan1=2.Itisoftenpracticallyimpossibletocomputeexactlyaposterioriprobabilitiesoferror(APPE),becausetheydependinaverycomplicatedwayonallbitsofthereceivedmessage.ThereasonablesolutiontothatproblemistocomputetheapproximatevaluesoftheAPPE,usingonlyapartofparitychecksforeverybitofthereceivedmessage.Afterthat,onecanreplacetheaprioriprobabilitiesoferrorbysocomputedAPPE,thentocomputethenewAPPE,andsoon(seeforexample[2,pp.157],[4];also[1]).InformationsetofthecodeCisanysubsetofkcoordinatesofacodeworduniquelydeterminingallothercoordinatesofthecodeword.Using2avectorofAPPE,onecanrandomlychoosesomenumberofhighlyreliableinformationsets,(informationsetssuchthattherespectivecoordinatesofsomeAPPE{vectorarecloseto0or1)andthentocomputethecodewordsdenedbyyandtheseinformationsets.Iftherearenotmanyerrorsinthereceivedmessage,thenallthecomputedcodewordswillbeequaltothecodeword^x.ItispossibletocorrectallerrorsinthereceivedmessageusingtheAPPE{vector.AposterioriprobabilitiesoferroraretheconditionalprobabilitiesPi=PfEi=1gjnH(i)E=H(i)yo(1)=PnH(i)E=H(i)y;Ei=1oPfH(i)E=H(i)yg;1in:ThematrixH(i);1in;withrirowsandncolumns,hasallonesinthei{thcolumn,andthespaceCisasubspaceofthenull{spaceofthematrixH(i)(seeforexample[3]).ItispossibletochooseH(i)=Hforalli;1in;butinthatcasethecomplexityofthecomputingoftheAPPEmightbeinconvenientlylarge.Wearegoingtodescribeadecodingalgorithmforlinearcodes.LetFy:[0;1]n![0;1]nbethefunctiontransformingtheprobabilityvectorpintotheAPPE{vectorP,Fy(p)=P:Decodingalgorithmundertheconsiderationstartsbycomputingsomenum-berg1ofvectorsfromthesequencenP(j)oj1givenbytherstmemberP(0)=pandbytherecurrentrelationP(j+1)=FyP(j):Thenextstepistoformthevectory,correctedversionofthereceivedmessagey,yi=(yi;P(g)i1=21yi;P(g)i1=2;1in(2)Undersomeconditionsconnectedwiththeerror{vector(whichwillnotbeconsideredinthispaper,seeforexample[1])thevectoryisequalto^x,oratleastsomeofitshighlyreliablecoordinates,formingtheinformationset,areequaltothecorrespondingcoordinatesofthevector^x.Thatmeansthat3thevectorycanbetakenastheresultofdecodingofthereceivedmessagey.ItiswellknownthatthecomplexityofthecomputingtheAPPEgrowsexponentiallywiththeexponentminfki;rig.Amethodforreducingthiscomplexityusingtheequivalent,butsmaller,paritycheckmatricesisgiveninSection1.Themethodisgeneralizationofthemethodusedin[1].IncomputingthevectorsnP(j)o1jg,anumericalproblemmayarise.Namely,thecoordinatesofthesevectorscangetverycloseto0or1,andconsequentlytheycannotbedistinguishedfromthattwovalues.InSection2.asolutionwillbegivenforthisproblem.ThesequenceofthealgebraicvaluevectorsiscomputedinsteadoftheAPPE{vectors.InSection3.isgivenanexample.1AmethodforcomputingtheAPPEIntheequation(1)itcanbesupposedwithoutlossofgeneralitythat0pi1=2,foralli;1in.Thatcanbeseenbythefollowingreasoning.LetE0bearandombinaryvectorgivenbyE0=Ed,wheredi=(0;pi1=21;pi1=2;1in:Thenforalli;1in;itisobviouslyPfE0i=1g=p0i1=2.Ifthevectory0isdenedbyy0=yd,thentheequalitiesH(i)E=H(i)yandH(i)E0=H(i)y0areequivalent.ThuswehaveP0i=PfE0i=1gjnH(i)E0=H(i)y0o=PfEidi=1gjnH(i)E=H(i)yo=(Pi;pi1=21Pi;pi1=2:ThesetCiofthebinaryvectorsdenedbyCi=ne2BnjH(i)e=0(r)o(whereB=f0;1gand0(r)denotesther{dimensionalvectorwithallcoordi-natesequaltozero)isagro