1YuanLuoXi’anJan.2013OptimumDistanceProfilesofLinearBlockCodesShanghaiJiaoTongUniversity1YuanLuoXi’anJan.2013OptiHammingDistanceCodewordwithLongLengthorShortLengthOnewayis:Hammingdistance,generalizedHammingDistance,…AnotherDirectionis:Hammingdistance,distanceprofile,…Background:OurresearchesonODPoflinearblockcode:Golay,RS,RM,cycliccodes,…HammingDistanceCodewordwith3

HammingDistance3

HammingDistance4Although,thelinearcodeswithlonglengtharemostoftenappliedinwirelesscommunication,thecodeswithshortlengthstillexistinindustry,forexample,somestoragesystems,theTFCIof3G(or4G)system,somedatawithshortlengthbutneedstrongprotection,etc.CodewordwithLongLengthorShortLength4Although,thelinearcodeswi5Forthecodeswithshortlength,thepreviousclassicboundscanhelpyoudirectly.Forthecodeswithlonglength,theasymptoticformsofthepreviousclassicboundsstillwork.Inthistopic,weconsidersomeproblemsinthefieldofHammingdistancewithshortcodewordlength.5Forthecodeswithshortleng6Hammingdistanceisgeneralizedforthedescriptionoftrelliscomplexityoflinearblockcodes(DavidForney)andforthedescriptionofsecurityproblems(VictorWei).Wealsogeneralizedtheconcepttoconsidertherelationshipbetweenacodeandasubcode:Onewayis:Hammingdistance,generalizedHammingDistance,…6Hammingdistanceisgeneraliz7Inthefollowing,weconsidertheHammingdistanceinavariationalsystem.Forexample,whentheencodinganddecodingdeviceswerealmostselected,butthetransmissionratedoesnotneedtobehighinaperiod(intheeveningnotsomuchusers),seenextslide,thenmoreredundanciescanbeborrowedtoimprovethedecodingability.Whatshouldwedotorealizethisidea?Andwhatistheprinciple?AnotherDirectionis:Hammingdistance,distanceprofile,…7Inthefollowing,weconsider8TheTFCIin3Gsystem8TheTFCIin3Gsystem9DetailsInlinearcodingtheory,whenthenumberofinputbitsincreasesordecreases,somebasiscodewordsofthegeneratormatrixwillbeincludedorexcluded,respectively.9DetailsInlinearcodingtheor10

Foragivenlinearblockcode,weconsider:※howtoselectageneratormatrixandthen※howtoincludeorexcludethebasiscodewordsofthegeneratoronebyone※whilekeepingtheminimumdistances(ofthegeneratedsubcodes)aslargeaspossible.10ForagivenlinearblockBigProblemIngeneralcase,thealgebraicstructuremaybelostinsubcodealthoughthepropertiesoftheoriginalcodearenice.Thenhowtodecode?11BigProblemIngeneralcase,th12OneexampleLetCbeabinary[7,4,3]HammingcodewithgeneratormatrixG1:12Oneexample13ItiseasytocheckthatifweexcludetherowsofG1fromthelasttothefirstonebyone,thentheminimumdistances(adistanceprofile)ofthegeneratedsubcodeswillbe:444(fromlefttoright)13Itiseasytocheckthatif14Andyoucannotdobetter,i.e.byselectingthegeneratormatrixordeletingtherowsonebyoneinanotherway,youcannotgetbetterdistanceprofileinadictionaryorder.14Andyoucannotdobetter,i15Note:wesaythatthesequence 3468isbetterthan(oranupperboundon)thesequence 3459 indictionaryorder.15Note:wesaythatthesequen16AnotherexampleLetCbethebinary[7,4,3]HammingcodewithgeneratormatrixG2:16Anotherexample17ItiseasytocheckthatifweincludetherowsofG2fromthefirsttothelastonebyone,thentheminimumdistances(adistanceprofile)ofthegeneratedsubcodeswillbe:3337(fromrighttoleft)17Itiseasytocheckthatif18Andyoucannotdobetter,i.e.byselectingthegeneratormatrixoraddingtherowsonebyoneinanotherway,youcannotgetbetterdistanceprofileinaninversedictionaryorder.Note:wesaythatthesequence 3689 isbetterthan(oranupperboundon)thesequence 3779 ininversedictionaryorder.18Andyoucannotdobetter,i19MathematicalDescription(2010IT)19MathematicalDescription(20202021Optimumdistanceprofiles21Optimumdistanceprofiles22TheOptimumDistanceProfilesoftheGolayCodesForthe[24,12,8]extendedbinaryGolaycode,wehave22TheOptimumDistanceProfile232324Forthe[23,12,7]binaryGolaycode,wehave24Forthe[23,12,7]binaryG252526Forthe[12,6,6]extendedternaryGolaycode,wehave26Forthe[12,6,6]extended27Forthe[11,6,5]ternaryGolaycode,wehave27Forthe[11,6,5]ternary28FortheresearchesonReedMullercodes,seeYanlingChen’spaper(2010IT).MaybeLDPC…inthefuture?28FortheresearchesonReedM29Todealwiththebigproblem,weconsidercycliccodeandcyclicsubcode.GOODNEWS:Forgenerallinearcode,thecorrespondingproblemisnoteasysincefewalgebraicstructuresareleftinitssubcodes.Butforcycliccodesandsubcodes,itlooksOK29Todealwiththebigproblem30GOODNEWS:Forgeneralfixedlinearcode,thelengthsofallthedistanceprofilesarethesameastherankofthecode.Forcyclicsubcodechain,thelengthsofthedistanceprofilesarealsothesame.30GOODNEWS:31GOODNEWS:Forgeneralfixedlinearcode,thedimensionprofilesarethesame,andanydiscussionisundertheconditionofthesamedimensionprofile.Itisunluckythat,thedimensionprofilesofthecyclicsubcodechainsarenotthesame,sowecannotdiscussthedistanceprofilesdirectly.Butbyclassifyingthesetofcyclicsubcodechains,wecandealwiththeproblem.31GOODNEWS:32MathematicsDescription32MathematicsDescription33ClassificationontheCyclicSubcodeChains33ClassificationontheCyclic341ThelengthofitscyclicsubcodechainsisandJ(ms)isthenumberoftheminimalpolynomialswithdegreemsinthefactorsofthegeneratorpolynomial.341Thelengthofitscyclic352Thenumberofitscyclicsubcodechainsis3Thenumberofthechainsineachclassis:352Thenumberofitscyclics364Thenumberoftheclassesis:5Forthespecialcasen=qm-1,wehavewhereistheMobiusfunction.364Thenumberoftheclasses37Example:Thenumberofitscyclicsubcodechainsis24Thelengthofitscyclicsubcodechainsis4Thenumberofthechainsineachclassis2Thenumberoftheclassesis1237Example:Thenumberofitscy3838393940FornewresultsabouttheODPofcycliccodes,pleaserefertoourmanuscriptonthepuncturedReedMullercodes.40FornewresultsabouttheOD謝謝謝謝42YuanLuoXi’anJan.2013OptimumDistanceProfilesofLinearBlockCodesShanghaiJiaoTongUniversity1YuanLuoXi’anJan.2013OptiHammingDistanceCodewordwithLongLengthorShortLengthOnewayis:Hammingdistance,generalizedHammingDistance,…AnotherDirectionis:Hammingdistance,distanceprofile,…Background:OurresearchesonODPoflinearblockcode:Golay,RS,RM,cycliccodes,…HammingDistanceCodewordwith44

HammingDistance3

HammingDistance45Although,thelinearcodeswithlonglengtharemostoftenappliedinwirelesscommunication,thecodeswithshortlengthstillexistinindustry,forexample,somestoragesystems,theTFCIof3G(or4G)system,somedatawithshortlengthbutneedstrongprotection,etc.CodewordwithLongLengthorShortLength4Although,thelinearcodeswi46Forthecodeswithshortlength,thepreviousclassicboundscanhelpyoudirectly.Forthecodeswithlonglength,theasymptoticformsofthepreviousclassicboundsstillwork.Inthistopic,weconsidersomeproblemsinthefieldofHammingdistancewithshortcodewordlength.5Forthecodeswithshortleng47Hammingdistanceisgeneralizedforthedescriptionoftrelliscomplexityoflinearblockcodes(DavidForney)andforthedescriptionofsecurityproblems(VictorWei).Wealsogeneralizedtheconcepttoconsidertherelationshipbetweenacodeandasubcode:Onewayis:Hammingdistance,generalizedHammingDistance,…6Hammingdistanceisgeneraliz48Inthefollowing,weconsidertheHammingdistanceinavariationalsystem.Forexample,whentheencodinganddecodingdeviceswerealmostselected,butthetransmissionratedoesnotneedtobehighinaperiod(intheeveningnotsomuchusers),seenextslide,thenmoreredundanciescanbeborrowedtoimprovethedecodingability.Whatshouldwedotorealizethisidea?Andwhatistheprinciple?AnotherDirectionis:Hammingdistance,distanceprofile,…7Inthefollowing,weconsider49TheTFCIin3Gsystem8TheTFCIin3Gsystem50DetailsInlinearcodingtheory,whenthenumberofinputbitsincreasesordecreases,somebasiscodewordsofthegeneratormatrixwillbeincludedorexcluded,respectively.9DetailsInlinearcodingtheor51

Foragivenlinearblockcode,weconsider:※howtoselectageneratormatrixandthen※howtoincludeorexcludethebasiscodewordsofthegeneratoronebyone※whilekeepingtheminimumdistances(ofthegeneratedsubcodes)aslargeaspossible.10ForagivenlinearblockBigProblemIngeneralcase,thealgebraicstructuremaybelostinsubcodealthoughthepropertiesoftheoriginalcodearenice.Thenhowtodecode?52BigProblemIngeneralcase,th53OneexampleLetCbeabinary[7,4,3]HammingcodewithgeneratormatrixG1:12Oneexample54ItiseasytocheckthatifweexcludetherowsofG1fromthelasttothefirstonebyone,thentheminimumdistances(adistanceprofile)ofthegeneratedsubcodeswillbe:444(fromlefttoright)13Itiseasytocheckthatif55Andyoucannotdobetter,i.e.byselectingthegeneratormatrixordeletingtherowsonebyoneinanotherway,youcannotgetbetterdistanceprofileinadictionaryorder.14Andyoucannotdobetter,i56Note:wesaythatthesequence 3468isbetterthan(oranupperboundon)thesequence 3459 indictionaryorder.15Note:wesaythatthesequen57AnotherexampleLetCbethebinary[7,4,3]HammingcodewithgeneratormatrixG2:16Anotherexample58ItiseasytocheckthatifweincludetherowsofG2fromthefirsttothelastonebyone,thentheminimumdistances(adistanceprofile)ofthegeneratedsubcodeswillbe:3337(fromrighttoleft)17Itiseasytocheckthatif59Andyoucannotdobetter,i.e.byselectingthegeneratormatrixoraddingtherowsonebyoneinanotherway,youcannotgetbetterdistanceprofileinaninversedictionaryorder.Note:wesaythatthesequence 3689 isbetterthan(oranupperboundon)thesequence 3779 ininversedictionaryorder.18Andyoucannotdobetter,i60MathematicalDescription(2010IT)19MathematicalDescription(20612062Optimumdistanceprofiles21Optimumdistanceprofiles63TheOptimumDistanceProfilesoftheGolayCodesForthe[24,12,8]extendedbinaryGolaycode,wehave22TheOptimumDistanceProfile642365Forthe[23,12,7]binaryGolaycode,wehave24Forthe[23,12,7]binaryG662567Forthe[12,6,6]extendedternaryGolaycode,wehave26Forthe[12,6,6]extended68Forthe[11,6,5]ternaryGolaycode,wehave27Forthe[11,6,5]ternary69FortheresearchesonReedMullercodes,seeYanlingChen’spaper(2010IT).MaybeLDPC…inthefuture?28FortheresearchesonReedM70Todealwiththebigproblem,weconsidercycliccodeandcyclicsubcode.GOODNEWS:Forgenerallinearcode,thecorrespondingproblemisnoteasysincefewalgebraicstructuresareleftinitssubcodes.Butforcycliccodesandsubcodes,itlooksOK29Todealwiththebigproblem71GOODNEWS:Forgeneralfixedlinearcode,thelengthsofallthedistanceprofilesarethesameastherankofthecode.Forcyclicsubcodechain,thelengthsofthedistanceprofilesarealsothesame.30GOODNEWS:72GOODNEWS:Forgeneralfixedlin