维普资讯 http://www.cqvip.com
第３２卷第８期 ２００６年８月 电子工｜曩 ＥＬＥＣＴＲ０ＮＩＣ ＥＮＧＩＮＥＥＲ Ｖｏ１．３２ Ｎｏ．８ Ａｕｇ．２００６ 中长帧非规则ＬＤＰＣ码译码器的．ＦＰＧＡ实现 范 雷，王琳，肖 雯 （厦门大学电子工程系，福建省厦门市３６１００５） 摘要：ＬＤＰＣ（低密度奇偶校验码）是一种优秀的线性分组码，是目前距香农限最近的一类纠错 编码。与Ｔｕｒｂｏ码相比，ＬＤＰＣ码能得到更高的译码速度和更好的误码率性能，从而被认为是下一代通 信系统和磁盘存储系统中备选的纠错编码。简要介绍了适于硬件实现的ＬＤＰＣ码译码算法，并基于软 判决译码规则，使用Ｖｅｒｉｌｏｇ硬件描述语言，在Ｘｉｌｉｎｘ Ｖｉｒｔｅｘ２ ６ＯＯＯ ＦＰＧＡ上实现了码率为１／２、帧长５０４ ｂｉｔ的非规则ＬＤＰＣ码译码器。 关键词：ＬＤＰＣ码；非规则码；ＦＰＧＡ实现 中图分类号：１’Ｎ９ｌ１．１ ０引言 为（Ｊ『、ｒ— ）×Ｎ矩阵，矩阵的每行对应一个变量节点， 每列对应一个校验节点，每行或者每列对应的１的个 数称之为该行或者该列的度。日矩阵中存在ｌ的地方 反映了变量节点和校验节点相关联的地方。一般用 Ｔａｎｎｅｒ图形象地反映日矩阵中变量节点和校验节点 的关联关系。 ＬＤＰＣ（低密度奇偶校验码）是Ｇａｌｌａｇｅｒ于１９６２年 首先发明并研究的一种线性分组码…，但由于当时计 算能力的，该码的性能并没有得到良好的验证。 随着１９９３年采用相似迭代译码算法的Ｔｕｒｂｏ码的兴 起，ＬＤＰＣ码重新得到了关注呤Ｊ。近年研究结果显示， 规则的ＬＤＰＣ码在短帧传输时优于卷积码，非规则的 ＬＤＰＣ码在长帧传输时优于Ｔｕｒｏ码。目前国内外对 ｂＬＤＰＣ码实现的研究远没有对其理论研究的深入，主 要成果包括Ｂｌａｎｋｓｂｙ和Ｈｏｗｌａｎｄ于２００２年完成的使 用ＡＳＩＣ技术实现的码长为１ ０２４ ｂｉｔ，码率为１／２的 ＬＤＰＣ码译码器 以及Ｚｈａｎｇ Ｔｏｎｇ于２００２年完成的 变量 图１ Ｈ矩阵和Ｔａｎｎｅｒ图的对应关系 对于规则ＬＤＰＣ而言，行的度和列的度的分布是 分别相等的，对于非规则ＬＤＰＣ而言，行的度和列的度 的分布则是不一定相等的。从变量点的角度而言，它 —．．。．．．．．．．，．．．．．．．．．．．．ｌ ｌ Ｈ ＝ 基于ＦＰＧＡ的码长为９ ２１６ ｂｉｔ，码率为１／２的规则（３， ６）ＬＤＰＣ码译码器 等。由于非规则ＬＤＰＣ码在实现 上存在一些困难，目前已有的研究大多集中于规则 Ｉ』）Ｐｃ码的实现。 【 从检验点得到的信息越多，就越能准确地判断出它的 正确值。相反，校验点的度数越高，就越有可能向变量 Ｏ ｌ Ｏ ｌ ｌ ０ ０ ｌ ０ ｌ ｌ ０ ｌ ０ ｌ ０ ０ ｌ ０ ｌ 、●●●ｌ●●●●●●Ｊ０ ０ ０ ０ ｌ ｌ ｌ ０ ｌ ０ 本文在Ｘｉｌｉｎｘ Ｖｉｒｔｅｘ２ ６ＯＯＯ上实现了采用并行译 码策略的非规则ＩＸ）ＰＣ码的译码器，资源占用率约为 ７５％，在系统时钟为５０ ＭＨｚ的情况下，译码速度可以 达到５０ ＭＨｚ，并且随着系统时钟的提升，译码速度还 有很大的上升空间。本文还给出了Ｌｏｇ－ＢＰ算法仿真 结果和ＦＰＧＡ硬件测试结果的对比，并对其进行了分 析。 点发出错误的信息。所以对于非规则ＬＤＰＣ码来说， 变量点最好有高的度数，校验点最好有低的度数。对 于非规则ＬＤＰＣ而言，其日矩阵的构成方法包括泊松 方式、次泊松方式、超泊松方式，其中泊松方式是完全 随机控制置ｌ的方式，超泊松方式中每行的较重的列 的分布比泊松方式分布变化更大，次泊松方式和超泊 松方式原则相反。从性能上来看，超泊松方式生成的 一 日矩阵的性能最好，但由于非规则ＬＤＰＣ码性能的优 良性是在帧长到一定程度（１０ 以上）才能充分表现出 来，所以本文采用泊松方式得到所需的日矩阵，在挑 选时注意变量点和校验点的度数分布。最终得到的日 矩阵的检验点的度为３，变量点的度在（２，３，４）之间分 布。 １ ＬＤＰＣ码的译码原理 ＬＤＰＣ码是线性分组码的一种，其校验矩阵日最 大的特征是稀疏，有大量的０和少量的１构成。假定 信息位长度为 ，编码后码字长度为Ｊ『、ｒ，则校验矩阵日 收稿日期：２００５－１１４）９；修回日期：２００６－０２－２３。 ＬＤＰＣ码的译码采用基于软判决的迭代译码。软 判决方案中，译码器计算的是某个接收码字为０或者 ・２１． 维普资讯 http://www.cqvip.com
・通信技术・ 电子工皇啊 ２００６年８月 为１的概率。在迭代译码中，变量点信息和校验点信 息通过校验矩阵的约束关系互相传递更新，称之为信 度传播算法（ＢＰ算法）。 ‘ 本文采用的是ｌｏｇ・ＢＰ算法。首先定义几个变量 及符号的意义：日表示一个Ｍ×Ｎ的ＬＤＰＣ校验矩阵， 。ｆ表示矩阵Ｈ中第 行第 列的元素。定义校验点ｍ 上的第 个变量点为 （ｍ）＝｛ｎ：日爪． ＝１｝，关联在变 量点ｎ上的第ｍ个校验点为肘（ｎ）＝｛ｍ：Ｈ…＝１｝。 输人数据为：初始概率 ＝Ｐ（ ＝０）和Ｐ ＝ Ｐ（ ＝１）＝１一Ｐ：：，ｎ＝１，２，…，Ⅳ。 输出数据为：硬判决结果 ＝｛ ， ，…， ｝。 译码过程如下： １）初始化 对于接收到的每个变量点ｎ计算初始信道信息 ｐＯ ＝ｌｏｇ ，并对每个点计算初始信息，其中（ｍ，ｎ）∈ ｛（ ， 日ｉ。，＝１｝。 Ｏｌ＝，ｎ－ｓｉｇｎ（ｙ ）ｌｏｓ（ 等） （１） 式中： ｓｉｇｎ（ｙ ）：ｆ十Ｌ一１ １ ｙ－ｙ ＜０ ｎ≥０ ２）迭代译码 ａ）校验点计算： ＝ｌｏｇ（ 者） ｓｉｇｎ（ ）（２） 式中： ０ｃ＝ ∑ ｌ ０ｃ ，ｌ （３） ｂ）变量点计算： Ｏｌ＝，ｎ＝ｓｉｇ ）ｌｏｇ（ ）（４） 式中： ｙ ＝ ＋ ∑卢 。 （５） ｍ Ｅ＾ｆ（ｎ）、ｍ 对于每个变量点ｎ，在完成变量点计算后，对Ａ 进行更新： Ａ ＝ｙ ＋∑卢 （６） ｃ）硬判决：如果Ａ ＞０，则 ＝０，反之，如果Ａ ≤ ０，则 ＝１。如果矾＝０，则迭代结束，否则跳到迭代 译码部分，直至校验成功或者达到最大迭代次数。 上面算法中的ａ…和卢～都被称为外信息，其中 ａ…是从变量点向校验点传递的信息，卢～是从校验点 向变量点传递的信息。 ・２２・ ２译码器的结构设计 译码器结构如图２所示。 ｌ 准备好信号 下一帧 硬判决结罨 信息位的 数据输出 帧同步信号一 迭代 输出 模块 校验位的 模块 ： 。校验结果 。 Ｅｎ ｏｕｔ Ｆ－ Ｅｎ ｏｕｔ 图２译码器结构 译码器的各个模块作用和译码过程如下： ａ）ＤＣＭ模块用于管理时钟，保证各个模块的时 钟的稳定和同步。 ｂ）初始化模块完成输入数据的串并转换并对信 道信息进行初始化计算，计算公式为式（１），其中ｌｏｇ ．＇ ． 一ＩＹ Ｉ ｆ、ｌ —ｅ ¨‘／ ｌ难以用ＦＰＧＡ直接计算实现，由于输入信 号共有的３２种状态，可以将输入信号的３２种状态对 应的初始值先计算好并存人查找表（ＬＵＴ）中，输入的 数据作为地址线查找对应数据作为信道初始化信息。 ｃ）迭代模块是译码器的核心模块，它实现式（２） 一式（６），完成变量点信息和校验点信息的计算和数 据的交换更新。通过分析公式可以看到，公式中需要 ・ 一１．ｖ Ｉ 进行的两种运算为加法运算和ｌｏｇ ｆ｝ 、ｌ—ｅ ¨‘／ １运算， 后者可以用上文所述的ＬＵＴ实现。 ｄ）输出模块完成的任务包括译码成功与否的判 断、迭代次数的控制和输出数据的并／串转换。当信道 条件过于恶劣的情况下，可能出现无法译出正确码字 的情况，此时需要设定最大迭代次数，当其迭代到最大 迭代次数时不再迭代下去，将译码后的数据输出，本文 设定的最大迭代次数为ｌ８次。 ３迭代模块内部结构的设计 迭代模块完成的是变量点信息和校验点信息的计 算以及信息在变量点和校验点之间的传递。通过分析 式（２）一式（５）可以知道变量点信息的计算和校验点 信息的计算是分别的，将其子模块分别命名为 ＣＮＵ（检验点计算单元）和ＶＮＵ（变量点计算单元 Ｃｏｍｐｕｔａｔｉｏｎ Ｕｎｉｔ），虽然二者结构不同，但其实现的功 能有相似之处。 以ＶＮＵ模块结构（见图３）为例说明如何实现变 量点信息的计算。译码器采用符号量化位（ｓｉｇｎ．ｍａｇ． ｎｉｔｕｄｅ）格式表示数据，由式（５）知道，某一变量点的信 息是由关联在同一校验点上的其余变量点的信息所共 维普资讯 http://www.cqvip.com
第３２卷第８期 范雷，等：中长帧非规则ＬＤＰＣ码译码器的ＦＰＧＡ实现 ・通信技术・ 同决定的，由于译码器采用的是非规则ＬＤＰｃ码的校 验矩阵，关联在同一校验点的变量点的数名是不确定 的，本译码器中Ⅳ在（２，３，４）之中变化。输出的结果 通过ＲＡＭ传给ＣＮＵ模块，作为ＣＮＵ模块的输入信 的，反映在结构上就是加法器的输入端数目不是固定 息。 圈３ ｇＮＵ模块内部结构 ４ ＦＰＧＡ验证与结论 现实时的编解码。 ４．３纠错性能分析 ４．１设计流程 由图４可以看出，硬件测试的结果与算法仿真的 设计的整个流程包括基于浮点的ｃ程序仿真、基 结果，在误码率性能上有一定的差距。根据分析，认为 于定点的ｃ程序仿真、Ｖｅｒｉｌｏｇ ＨＤＬ语言程序的编写、 造成这种结果的原因包括以下几个方面：首先，Ａ／Ｄ 功能仿真、逻辑综合、时序仿真、布局布线和下载和硬 转换时量化数量对其性能存在一定的影响，量化数量 件测试。在设计过程中，采用Ｘｉｌｉｎｘ公司的ＩＳＥ进行 过少将不能有效和精确地反映信道信息，本文的量化 逻辑综合和布局布线，采用Ｍｏｄｅｌｓｉｍ ５．５ＳＥ进行功能 数量为ｌ６，文献［４］指出，当量化数量为３２或者６４ 仿真和时序仿真，最终在Ｖｉｒｔｅｘ２ ６ＯＯＯ上实现了帧长 时，性能将有一定的改善；其次，由于完全并行的译码 为５０４ ｂｉｔ的非规则ＬＤＰＣ码的译码功能。 方式占用资源较多，在设计查找表ＬＵＴ时，采用的数 ４．２资源分析 ． 据宽度为４位，并对计算值的大小进行了，本文将 使用ＩＳＥ６．１在Ｖｉｒｔｅｘ２ ６ＯＯＯ上对译码器进行布局 其与［一４，＋４］间。 布线，资源占用率如表ｌ所示。 表１ Ｖｉｒｔｅ￣６ＯＯＯ资源占用率 通过时序分析可知，由于系统时钟为５０ ＭＨｚ，译 码器译码最多需要进行ｌ８次迭代，每次迭代需要ｌ０ 图４译码器性能 个时钟周期，在一帧数据输入的５０４个时钟周期内可 以完成ｌ８次的迭代，可以得到译码的速度与系统时钟 如图５所示增加数据宽度和计算结果的取值范围 相当为５０ ＭＨｚ。同时需要指出，由于数据输入时间要 都能有效的改善性能。因此，采用ＢＰ算法或者Ｌｏｇ— 大于迭代译码时间，所以完全并行的译码方式可以实 ＢＰ算法的ＬＤＰＣ码译码器只能在性能和资源占用之 ・２３・ 维普资讯 http://www.cqvip.com
・通信技术・ 电子工量■ ２００６年８月 间寻找平衡，目前出现新的算法，例如Ｍｉｎ—Ｓｕｍ算法 全并行的译码方式可以达到很高的编译码速度，但由 于其硬件开销比较大，适用于对速度要求比较苛刻的 场合，例如光纤通信中。在对速度要求不是很苛刻的 情况下应该优先考虑规则ＬＤＰＣ码的部分并行的译码 方式，可以有效地降低硬件开销。 参考文献 用于ＦＰＧＡ实现，可以避免ＬｕＴ的使用，从而克服了 采用ＬｕＴ所带来的资源和精度的问题。 【１］ＧＡＬＬＡＧＥＲ Ｒ Ｇ．Ｌｏｗ・ｄｅｎｓｉｔｙ ｐａｒｉｔｙ—ｃｈｅｃｋ ｃｏｄｅｓ【Ｊ］．ＩＲＥ Ｔｒａｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，１９６２，８（１）：２１－２８． ［２］ＭＡＣＫＡＹ Ｄ Ｊ Ｃ，ＮＥＡＬ Ｒ Ｍ．Ｎｅａｒ Ｓｈａｎｎｏｎ ｌｉｍｉｔ ｐｅｒｆｏｒｍ－ ａｌｉｃｅ ｏｆ ｌｏｗ—ｄｅｎｓｉｙｔ ｐａｒｉｙ－ｔｃｈｅｃｋ ｃｏｄｅｓ［Ｊ］．Ｅｌｅｃｔｒｏｎｉｃｓ Ｌｅｔ－ ｔｅｒｓ，１９９７，３３（６）：４５７－４５８． 信噪［￣／ｄＢ —－［３］ＢＬＡＮＫＳＢＹ Ａ Ｊ，ＨＯＷＬＡＮＤ Ｃ Ｊ．Ａ ６９０－ｍＷ １－Ｇｂ／ｓ １０２４－ ｂ，ｒａｔｅ－１／２ ｌｏｗ－ｄｅｎｓｉｙｔ ｐａｒｉｙ－ｔｃｈｅｃｋ ｃｄｅｏ ｄｅｃｏｄｅｒ［Ｊ］．ＩＥＥＥ Ｊｏｕｒｎａｌ ｏｆ Ｓｏｌｉｄ－ｓｔａｔｅ Ｃｉｒｃｕｉｔｓ，２００２，３７（３）：４０４－４１２． ．－Ｒａｎｇ￣（－￥，８），４ｂｉｔ； ４－Ｒａｎｇｅ（－８，８），８ｂｉｔ； ＋Ｒａｎｇｅ（－４，４），４ｂｉｔ； 一Ｒａｎｇｅ（－４，４），８ｂｉｔ 图５不同■化取值ＬＤＰＣ码误码率性能 ［４］ＺＨＡＮＧ Ｔｏｎｇ，ＰＡＲＨＩ Ｋ Ｋ．Ａ ５４ Ｍｂｐｓ（３，６）－ｒｅｇｕｌａｒ ＦＰＧＡ ＬＤＰＣ ｄｅｃｏｄｅｒ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＥＥＥ Ｗｏｒｋｓｈｏｐ ｏｎ Ｓｉｇ－ ｎａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓｔｅｍｓ（ＳＩＰＳ ０２），Ｏｃｔ １６—１８，２００２，Ｓａｎ Ｄｉｅｇｏ，ＣＡ，ＵＳＡ．Ｐｉｓｅａｔａｗａｙ，ＮＪ，ＵＳＡ：ＩＥＥＥ，２００２：１２７ １３２． ５结束语 本文通过在Ｘｉｌｉｎｘ ＦＰＧＡ上实现非规则ＬＤＰＣ码 的译码器，验证了ＬＤＰＣ高速的译码速度和良好的误 —［５］ＭＥＨＴＡ Ｇ．Ａｎ ＦＰＧＡ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ｔｈｅ ｇｒａｐｈ ｅｎｃｏｄｅｒ－ ｄｅｃｏｄｅｒ ｆｏｒ ｒｅｇｕｌａｒ ＬＤＰＣ ｃｏｄｅｓ［Ｄ］．Ｐｉｔｔｓｂｕｇｈ，ＰＡ，ＵＳＡ： Ｕｎｉｖｅｒｓｉｙ ｏｆ ｔＰｉｔｔｓｂｕｇｈ，２００２． 码率性能。非规则ＬＤＰＣ码由于其日矩阵的随机性 和非规则性，目前只能采用完全并行的译码方式。完 Ｉｒｒｅｇｕｌａｒ ＬＤＰＣ Ｃｏｄｅ Ｄｅｃｏｄｅｒ ＦＡＮ Ｌｅｉ，ＷＡＮＧ Ｌｉｎ，ＸＩＡＯ Ｍｉｎｇ （Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｘｉａｍｅｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉａｍｅｎ ３６１００５，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ（ＬＤＰＣ）ｃｏｄｅ ｉｓ ａ ｇｏｏｄ ｌｉｎｅａｒ ｂｌｏｃｋ ｃｏｄｅ，ｗｈｉｃｈ ｐｅｒｆｏｒｍｓ ａｔ ａ ｒａｔｅ ｅｘｔｒｅｍｅｌｙ ｃｌｏｓｅ ｔｏ ｔｈｅ Ｓｈａｎｎｏｎ ｌｉｍｉｔ ｃａｐａｃｉｙ．Ｃｏｍｐａｒｔｅｄ ｗｉｈ Ｔｕｒｂｏ ｃｏｔｄｅ，ＬＤＰＣ ｃｏｄｅ ｐｅｒｆｏｒｍｓ ｆａｓｔｅｒ ｄｅｃｏ— ｄｉｎｇ ｓｐｅｅｄ ａｎｄ ｂｅｔｔｅｒ ＢＥＲ ｐｅｒｆｏｒｍａｎｃｅ ａｎｄ ｉＳ ｃｏｎｓｉｄｅｒｅｄ ｔｏ ｂｅ ｏｎｅ ｏｆ ｓｕｉｔａｂｌｅ ｃｏｄｅｓ ｆｏｒ ４Ｇ ｃｏｍｍｕｎｉｃａｔｉｏｎ ｓｙｓｔｅｍ ａｎｄ ｓｔｏｒａｇｅ ｓｙｓｔｅｍ．Ｔｈｉｓ ｐａｐｅｒ ｉｎｔｒｏｄｕｃｅｓ ａ ｄｅｃｏｄｅ ａｌｇｏｒｉｈｍ ｗｈｉｔｃｈ ｉｓ ｓｕｉｔａｂｌｅ ｆｏｒ ｈａｒｄｗａｒｅ ｉｍｐｌｅｍｅｎ． ａｔｔｉｏｎ ａｎｄ ａ ｆｕｌｌｙ ｐａｒａｌｌｅｌ ｄｅｃｏｄｅｒ ｂａｓｅｄ ｏｎ ａ ｆｒａｍｅ ｏｆ ５０４ ｂｉｔｓ ｆｏｒ ｉｒｒｅｇｕｌｒ ＬＤＰＣ ｃｏａｄｅｓ ｉｓ ｉｍｐｌｅｍｅｎｔｅｄ ｏｎ Ｘｉｌｉｎｘ ＦＰＧＡ ＸＣ２Ｖ６０００ ｄｅｖｉｃｅ ｗｉｔｈ Ｖｅｒｉｌｏｇ ｌｎｇａｕａｇｅ． Ｋｅｙｗｏｒｄｓ：ＬＤＰＣ ｃｏｄｅｓ；ｉｒｒｅｇｕｌｒ ｃｏａｄｅｓ；ＦＰＧＡ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ 欢迎订阅《电子工程师》 全国各邮电局订阅零售 邮发代号：２８－２５１ 单价：８元 全年订价：９６元 电话：０２５．８３７７２７２９