一种短码长下最优LDPC码的启发性搜索算法
0 引言
低密度校验(LDPC)码[1]由Gallager于1962年提出，并于上世纪90年代中期被重新发现并推广。LDPC码由于具有逼近Shonnon限的优越性能和低的译码复杂度而受到人们的普遍关注，成为目前最具前景的纠错编码技术之一。LDPC码在结构上可用二部图来表示，称为Tanner图[2]。Tanner图由变量结点和校验结点构成(如图1所示)。特别是短环会影响LDPC码译码迭代次数，降低迭代译码收敛速度，Tanner图中最短环的长度称为该Tanner图的围长。对于等码长LDPC码来说，由于围长不同其译码性能差异也会很大。根据该理论，用Mackay2A[3]方法构造随机矩阵，然后以树结构形式展开求其平均围长，在随机生成的码中求出平均围长最大的码，最后与其它随机码比较译码性能差异。分析平均围长对LDPC码译码性能的影响。 1 围长及围长分布
按照Mackay2A方法构造随机矩阵，然后转化为相应的Tanner图，按树结构形式展开，计算其围长及围长分布。构造稀疏随机校验矩阵m×n规则如下[3](如图1所示)： ①把矩阵m×n分成左右两个子矩阵m×（m/2）和m×（n-m/2）；
②子矩阵m×（m/2）每列‘1’的个数是2，由上下两个对
角子矩阵组成；
③子矩阵m×（n-m/2）每列‘1’的个数是3；
④矩阵m×n中任意两列之间在同一行的位置1的个数不大于1，即保证不存在4环；
⑤矩阵m×n中每行‘1’的数目尽可能一致；
一般地，围长指图中最短环的长度，这里意思扩大为节点的围长[4]，节点v的围长指通过v的最短环的长度，计算变量节点围长的基本思想为：将Tanner图中以某一变量结点为根节点按树结构形式展开，树的偶数层由校验结点组成，树的奇数层由变量结点组成，当展到树中某层（k层）出现相同结点且为根结点的不同孩子时就会构成最短环即该变量结点的围长，大小为2k，如图1（右边）所示，变量节点v1的围长为6。围长分布则是指围长为l的变量节点占所有变量节点N的比率。 围长分布是影响迭代译码性能的一个重要因素。对于一个无环TG图[5]，采用基于置信传播BP的迭代译码算法具有良好性能。然而对于有环TG图来说，从一个变量结点传播消息然后回到该结点，结点的围长就是所传播最短路径的长度，即最小迭代译码次数。由于围长的存在使得信息不能传播到图的所有结点，降低了迭代译码传递消息的可靠性及收敛速度或使其无法收敛，严重影响译码性能。为了提高译码性能，需要使变量节点的围长尽可能地大，即使较多变量节点有较大围长。 2 基于启发式的最优码搜索算法
要在很多等长码中搜索最优码，即搜索最大平均围长码，必须先计算出码中每个变量节点的围长，然后求出每个码的围长分布和平均围长，计算出随机生成的q个码的围长分布的平均值及标准差，最后从q个码中选出围长平均值最大的码，以便分析其码的性能。具体算法描述如下所示： ①初始化i=1，j=1；
②构造码长为N的随机矩阵，相应的Tanner图为G，G有n个变量节点为v1，v2，…，vn；
③将G以变量节点vj为根节点按树结构展开，当展到树中某层（k层）出现相同结点且为根节点的不同孩子时就会构成该变量结点的围长，围长为2k；把围长依次存放在一个大小为n的数组中；j++，若j≤n，转向②继续；
④计算该码的围长分布gi（l），l=4，6，…，lmax，lmax是Tanner图中最大围长，平均围长 ；并记录到大小为n的数组中。 i++，若i