1、YuanLuoXianJan.2013OptimumDistanceProfilesofLinearBlockCodesShanghaiJiaoTongUniversityHammingDistanceCodeword with Long Length or Short LengthOne way is:Hamming distance,generalized Hamming Distance,Another Direction is:Hamming distance,distance profile,Background:OurresearchesonODPoflinearblockcode
2、:Golay,RS,RM,cycliccodes,HammingDistanceAlthough,the linear codes with long length are most often applied in wireless communication,the codes with short length still exist in industry,for example,some storage systems,the TFCI of 3G(or 4G)system,some data with short length but need strong protection,
3、etc.Codeword with Long Length or Short LengthFor the codes with short length,the previous classic bounds can help you directly.For the codes with long length,the asymptotic forms of the previous classic bounds still work.In this topic,we consider some problems in the field of Hamming distance with s
4、hort codeword length.Hamming distance is generalized for the description of trellis complexity of linear block codes(David Forney)and for the description of security problems(Victor Wei).We also generalized the concept to consider the relationship between a code and a subcode:One way is:Hamming dist
5、ance,generalized Hamming Distance,In the following,we consider the Hamming distance in a variational system.For example,when the encoding and decoding devices were almost selected,but the transmission rate does not need to be high in a period(in the evening not so much users),see next slide,then mor
6、e redundancies can be borrowed to improve the decoding ability.What should we do to realize this idea?And what is the principle?Another Direction is:Hamming distance,distance profile,TheTFCIin3GsystemDetailsIn linear coding theory,when the number of input bits increases or decreases,some basis codew
7、ords of the generator matrix will be included or excluded,respectively.Foragivenlinearblockcode,weconsider:howtoselectageneratormatrixandthenhowtoincludeorexcludethebasiscodewordsofthegeneratoronebyonewhilekeepingtheminimumdistances(ofthegeneratedsubcodes)aslargeaspossible.BigProblemIn general case,
8、the algebraic structure may be lost in subcode although the properties of the original code are nice.Then how to decode?OneexampleLet C be a binary 7,4,3 Hamming code with generator matrix G1:lIt is easy to check that if we exclude the rows of G1 from the last to the first one by one,then the minimu
9、m distances(a distance profile)of the generated subcodes will be:3444(fromlefttoright)And you can not do better,i.e.by selecting the generator matrix or deleting the rows one by one in another way,you can not get better distance profile in a dictionary order.Note:we say that the sequence 3 4 6 8is b
10、etter than(or an upper bound on)the sequence3 4 5 9in dictionary order.AnotherexampleLet C be the binary 7,4,3 Hamming code with generator matrix G2:It is easy to check that if we include the rows of G2 from the first to the last one by one,then the minimum distances(a distance profile)of the genera
11、ted subcodes will be:3337(fromrighttoleft)And you can not do better,i.e.by selecting the generator matrix or adding the rows one by one in another way,you can not get better distance profile in an inverse dictionary order.Note:we say that the sequence 3 6 8 9is better than(or an upper bound on)the s
12、equence3 7 7 9in inverse dictionary order.MathematicalDescription(2010IT)OptimumdistanceprofilesTheOptimumDistanceProfilesoftheGolayCodesFor the 24,12,8 extended binary Golay code,we haveFor the 23,12,7 binary Golay code,we havel For the 12,6,6 extended ternary Golay code,we havelForthe11,6,5ternary
13、Golaycode,wehaveFortheresearchesonReedMullercodes,seeYanlingChenspaper(2010IT).MaybeLDPCinthefuture?Todealwiththebigproblem,weconsidercycliccodeandcyclicsubcode.GOODNEWS:Forgenerallinearcode,thecorrespondingproblemisnoteasysincefewalgebraicstructuresareleftinitssubcodes.Butforcycliccodesandsubcodes,
14、itlooksOKGOODNEWS:For general fixed linear code,the lengths of all the distance profiles are the same as the rank of the code.For cyclic subcode chain,the lengths of the distance profiles are also the same.GOODNEWS:For general fixed linear code,the dimension profiles are the same,and any discussion
15、is under the condition of the same dimension profile.It is unlucky that,the dimension profiles of the cyclic subcode chains are not the same,so we cannot discuss the distance profiles directly.But by classifying the set of cyclic subcode chains,we can deal with the problem.MathematicsDescriptionClas
16、sificationontheCyclicSubcodeChains1Thelengthofitscyclicsubcodechainsisand J(ms)is the number of the minimal polynomials with degree ms in the factors of the generator polynomial.34-2Thenumberofitscyclicsubcodechainsis3Thenumberofthechainsineachclassis:35-4Thenumberoftheclassesis:5Forthespecialcasen=qm-1,wehavewhere is the Mobius function.36-Example:Thenumberofitscyclicsubcodechainsis24Thelengthofitscyclicsubcodechainsis4Thenumberofthechainsineachclassis2Thenumberoftheclassesis12For new results about the ODP of cycliccodes,please refer to our manuscript on the puncturedReedMullercodes.41-