基于FPGA的规则(3，6)LDPC码译码器

摘要：基于软判决译码规则，采用完全并行的解码结构，使用Verilog硬件描述语言，在Xilinx公司的FPGA（Virtex-2 xcv1000）上实现了码率为1/2、帧长为20bit的规则（3，6）LDPC码的译码器，最大传输速率可达20Mbps。对LDPC码的实际应用具有重要的推动作用。 关键词：LDPC码 变量节点 校验检点 因子图 译码 在通信系统中纠错码被用来提高信道传输的可靠性和功率利用率，低密度奇偶校验码（LDPC码）是目前最逼近香农限的一类纠错码。1962年，Gallager首次提出了LDPC码的古典模型，即规则（regular）的LDPC码：（n,j,k），校验矩阵H具有恒定的列重量和行重量。LDPC码由于比Turbo码列接近香农限的误码率性能和完全并行的迭代译码算法使其比Turbo码在部分场合具有更广泛的应用前景，从而使LDPC码成为当前纠错编码的一个研究热点。基于良好的译码性能，LDPC码被认为是通信系统的下一代纠错码。 1 规则LDPC码 1．1 因子图描述 因子图有两类顶点，分别为变量节点（variable nodes,用空的圆点表示）和校验节点（check nodes,用方框表示）。Tanner图就是这两类顶点之间的二部图，即每条边的一端与变量节点相连，另一端与校验节点相连。变量节点代表实际的变量，校验节点代表这些变量节点之间的约束。对于（j,k）-LDPC码的每个变量（bit）都受j个校验（check）的结束，因此每个变量节点应该连接j个校验节点。每个校验方程有k个变量，因此每个校验节点应与k个变量节点相连。由于LDPC是一种线性码，使得它的因子图一边为变量节点，一边为校验节点，故LDPC码的因子图表示有专用的定义：二部图（bipartite graphs）。 图1表示了校验矩阵为H的规则（3，6）LDPC的因子图，它是由10个变量定点和5个校验定点组成的二部图，边刚好对应于矩阵中1的位置，这种因子图是LDPC迭代译码算法的基础。 1．2 LDPC码的译码算法 LDPC码的译码采用信度传播（belief-propagation或BP）算法，它与因子图相对应，如图1所示，利用BP算法获得好的译码性能，LDPC码的因子图中环的长度必须尽可能地长，长度为4的环会降低BP算法的性能，H矩阵设计时应避免出现。如果直接使用BP算法，由于在迭代过程中存在大量的乘运算，将使硬件的复杂度大幅度上升，本论文采用改进的Log-BP算法，把大量的乘运算转换成加运算，从而降低硬件复杂主生产成本。 首先定义可能用到的几个变量及符号的意义：H表示一个M%26;#215;N的LDPC校验矩阵，Hi,j表示矩阵H中第i行第j列的表示。定义校验节点m上的第n个变量节点为N（m）={n:Hm,n=1}，并联在变量节点n上的第m个数验节点为M（n）={m:Hmn=1}。定义校验节点m上关联的除了第n个变量节点以外的所有变量节点为N（M），变量节点n上关联的除了第m个校验节点外的所有校验节点为M（n）。 Log-BP算法的译码过程： 译码过程： 初始化：对于接收到的每个变量节点n计算初始信道信息，并对每个点计算初始信息 迭代译码： （1）校验点计算 其中α=∑n" ∈N(m)|αm,n"| (2)变量节点计算 对于每个变量节点n，在完成变量节点计算后，对log似然率λn进行更新： (3)判决条件 (a)如果λn>0,则x"N=0;返之如果λn≤0,则x"N=1; (b)如果H%26;#183;x"=0，则迭代结束，否则跳到第2步迭代译码部分，直至校验成功或者达到最大迭代次数。 上面算法中的αm,n和βm,n都被换为外部信息，其中αm,n是从变量节点向校验节点传递的信息，βm,n是从变量节点向校验节点传递的信息。通过log-BP算法和BP算法的比较可以实现，log-BP算法中除了f(x)=log 运算，剩下的都是加法运算，从在则避免了BP算法中乘运算过多的弊病。在本文中函数f(x)利用FPGA中的查找表（Look-up Table,LUT）实现。 2 H矩阵的生成 Gallager提出的LDPC码的H矩阵必须满足以下两点： （1） H矩阵的第一列有j个1，j>=3; （2） H矩阵的第一行有k个1，k>j； 本文中选择j=3,k=6，通过编程用matalab软件生成若干满足条件的H矩阵，选择其中一个性能最好的H矩阵进行LDPC码的fpga译码实现。当n=20时，最终选择H矩阵如图2所示。 3 LDPC码完全平行译码结构 由二部图可能直接地看出，变量节点计算需要的信息只需由校验节点来提供，校验节点计算需要的信息只需要由变量节点来提供，译码器在设计时可以给每个变量节点分配一个变量节点处理单元（Variable Node processing Unit,VNU），给每个校验节点分配一个校验节点处理单元（Check Node processing Unit,CNU），从而实现译码器的完全并行结构。 译码器的核心模块是迭代译码部分，迭代译码的结构与算法是紧密相连的，译码结构的确定必须在仔细分析算法的基础上，迭代译码的过程是CNU和VNU模块计算结果的相互传递和更新。如果直接将CNU和VNU连接，不但不容易控制迭代的过程并且可能出现不稳定状态，所以需要在CNU和VNU之间安插RAM以起到数据的缓冲和控制作用。输入、输出模块分别控制数据的输入和输出，当条件满足或者迭代完成时，读入数据并把迭代结果输出。 3.1 迭代译码结构 图3表示平行迭代译码结构。其中只画出两个节点之间一条数据通路的连接方式，因为是完全平行迭代译码结构，其他节点之间数据通路的连接方式与此相同。信道初始化数据送入VNU模块进行数据处理后，送入RAM模块，数据经过CNU模块，最后再送入VNU模块，这样就完成一次迭代。数据信息从VNU到CNU与数据信息从CNU到VNU分别在不同的数据线上传输（图1）。 3.2 变量节点结构（VNU） 变量节点的结构如图4所示。从中可以看出每个变量节点的度为3(j=3)，四个5bit输入信息包含一个信道信息和三个与之相连的校验节点的信息。由log-BP算法可以看到α进行的是量化值的计算，没有牵扯到符号位，而ψm,n和λn的计算都有包含符号位的相加，实际上其中还包含了减法运算，而本文采用的符号信息位的格式不能用于减法运算，需要将其转换的其他格式。在本文进行和运算时，首先将转换为二进制补码形式，运算结束后再转换回符号量化位格式，查表（FX_LUT）进行f(x)运算。函数 可由FPGA中的逻辑单元LUT来实现。Comb模块把1bit的判决结果x、4bit的查找表运算结果与符号位合在一起作为外部信息送入校验节点（CNU）。图4上半部分为输入译码的结果，下半部分为三个数据输出通道中的一个，其余两个的结构与此完全相同，唯一不同的是加法器的输入，根据log-BP算法，其中初始化数据经过S-to-T转换后的数据输入固定，另外两个输入数据为其他两个数据通道的输入经过S-to-T转换后的数据。 图4 3.3 校验节点结构（CNU） 校验节点（CNU）结构如图5所示，每个检验节点的度数为6（k=5），图5只画出数据的一个输出通道，其余5个输出通道的结构与此完全相同，加法器为检验节点首先对外部信息中的判决结果进行验证，看是否满足H%26;#183;x T=0，满足则结束迭代。CNU模块中f(x)的x计算是只计算量化值而不管正负的，而本译码器采用的符号量化位转化为二进制初码形式。 图5 3．4 数据输入与输出 完全平行译码结构可以分为三部分：迭代译码模块、数据输入模块和数据输出模块。因为是完全平行译码方式，输入数据经过串并转换后，同时读入VNU进行迭代计算。在数据输出模块，每一次迭代完成要进行条件判别，如果CNU所有的校验结果都为零，则输出数据。或者已经完成17次迭代，此时强制输出数据。数据的输入与输出分别用不同的时钟进行控制。图6为译码器其中一帧数据的测试结果，编码之前的信息为01010101，图6中OutData为编码后数据的输出。 4 FPGA实现 根据规则（3，6）LDPC的完全平行译码结构，选择在Xilinx Virtex2 XC2V1000-fg256上对其进行物理实现，译码器采用Verilog硬件描述语言编写，用Xilinx的开发工具ISE6.1在XC2V1000上对译码器进行布局布线。通过时序分析可以看出，译码器的最大时钟频率为20MHz，以输入时钟为基准，完成17次迭代最多需要20个时钟，完成一帧数据的输入需要20个时钟，可以得出译码器的最大译码速率为：V=20%26;#215;20/20=20Mbps。图7为帧长为20bit的LDPC码的译码性能，因为码长较短，性能没有达到最好。这为更高速LDPC码译码器的设计打下坚实的基础，码长为1024bit，传输速率可进一步提高，甚至达到1Gbps，译码性能会更好。 本文基于软判译码规则，采用完全平行译码结构，设计出帧长为20bit，码率为1/2的规则（3，6）LDPC码的译码器，在Xilinx virtex2 XC2V1000-fg256上对其进行物理实现，最大迭代次数为17次，传输速率达到20Mbps。DPC码具有良好译码性能，与Turbo码相比更易于硬件实现，并能得到更高的译码速度。下一步将设计出码长为1024bit或码长更长的LDPC译码器，进一步提高传输速率，降低误码率，为加速该技术在中国的商用奠定基础。