关于几类线性分组码网格图复杂度的研究

《关于几类线性分组码网格图复杂度的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2001年11月通信学报V啊．22No．I1第22卷第11期JOURNALOFCHINAINn广rUTEOF(Nov∞1；学术论文l'⋯⋯⋯关于几类线性分组码网格图复杂度的研究幕建君，王新梅(西安电子科技大学综合业务网国家重点实验室．陕西西安710071)摘要：本文研究了几类线性分组码C[n．恕棚的网格图复杂度q。给出并证明了码长为奇数的两类线性分组码的网格图复杂度。同时得出了有关可纠t个错的本原BCH码【2l，2l—加l及其扩展奉原BCH码的网格图复杂度的若干结论。从而避免了必须先寻找码的直和结构才可得

2、到码的网格图复杂度的较好上界。关键词：线性分组码：网格图复杂度；晟小网格图：软判决译码中圈分类号：TN918．4文献标识码：A文章编号：1000-436X(2001)11-0006．05StudyonthetrelliscomplexityofafewtypesoflinearblockcodesMUJian-jun，WANGXin-mei(NationalKeyLabofm∞dSere,iceNelworks·XidianUnivemity·Xi’aft710071．China)Abaraet：Thet

3、relliscomplexitiesfcjofafewtypesoflinearblockcodesC≈aqarcinvestigated-Thetreliscomplexitiesoftwo嘴oflinearhleckcodeswhosecodelengthisoddarcshowlLh~aemeantimesonlgresultsareshownonthetrelliscomplexityoft-error-con'ecting13／imitiveBCHces[2l，2l—mandtheirexten

4、dedprimitiveBCHcodes．Thusfindingthedirect-sumstnlctureofcodesisavoidedbeforewesolvethesubotnimalupperboundoftheirtrelliscomplexityX野words：linearblockcodes：trelliscomplexity；minimaltrellises；soft-decisio~adecoding1引言分组码的网格图主要用于软判决译码【]】。借助于网格图用Viterbi算法实现最大

5、似然译码时需要I吲次加法和IEI—tV[+1次比较【4J，其中I目和Iy1分别表示码的网格图中的边数和顶点收稿日期：2O0O-08．29；修订日期：2001—08—2l基金项目：国家自然科学基金资助项(69972035)；华为科技基金项目作者简介：慕建君(1965一)．男，陕西吴堡人．西安电子科技大学博士生，讲师，目前的研究兴趣为编码、信息论与应用数学；王新梅(1937一)，男，浙江浦江人，西安电子科技大学教授．博士生导师t中国电子学会会士，长期从事信息论、编码和密码学的教学与研究第11期幕建君等：关于儿

6、娄线性分组码河格图复杂度的研究数。为了降低Viterbi译码的复杂度，我们必须应用码的使和I正H+1最小的网格图进行译码。而码的最小网格图定义为具有最少顶点数(状态数)的网格图(对码的确定分量顺序)。MudertSl认为网格图的复杂度fcJ应陔看作码的最基本的参数之一(其它参数：码长、维数和最d、距离)正因如此，近年来研究复杂度srcj这类问题受到了普遍关注】I]。2几个相关的定义设集合、和有限集合A分别表示有向图

7、码，线性分组码C[n，k，胡的网格图定义为一个有向图T--

8、所有边组成之集。对于线性分组码qn，丘胡的网格图，定义第f∈，_(o'1，⋯)时刻的状态空间的维数为S=log1)对于码的确定的分量顺序，线性分组码的最小网格图存在且唯一(同构意义上)[4．51，而且它有最小的边数I41和最小的IEI一114+1[71。因此，对线性分组码其最小网格图可使Viterbi译码的复杂度最小。对于码的确定分量顺序，线性分组码c【，k，胡的网格图状态空间的最大维数定义为(c)讪m)=．)Forneyt2