低密度奇偶校验编码简介

由于低密度奇偶校验编码（low-density parity-check code）提供极高的编码增益，已经纳入成为新世代通讯标准的一部份。相较于涡轮码（Turbo code），在妥善的设计下，低密度奇偶校验编码译码器具有较低的计算复杂度。完全平行译码的实现方式，必须面对极高的绕线复杂度与大量硬件计算资源需求等问题。虽然完全序列处理可以用最少的硬件完成译码器的设计，但是这样的译码器的译码速度也是最慢的。部分平行译码的硬件架构可以提供不同应用领域一个复杂度与传输速率平衡点。

二阶段的讯息传递（two-phase messaging passing）译码过程中，在第一阶段的每一个讯息都会与通一列的讯息经过一个列运算（row operation），并产生第二阶段所需要的讯息。讯息经过第一阶段的处理后，每一个在同一行的讯息将经过一个行运算（column operation）。在每一个讯息完成二阶段的运算后，称为完成一次迭代译码(decoding iteration)。当没有使用任何排程算法时，二阶段讯息传递译码必须先完成所有的列运算后才可以执行行运算。在此种情况下造成负责计算列运算或是行运算的硬件相互等待，导致硬件使用效率（hardware utilization efficiency）低落。

在设计者在设计低密度奇偶校验编码时，同时都会考虑编码设计对于译码器的影响。许多的设计者采用类回旋低密度奇偶校验编码（Quasi-cyclic low-density parity-check code），利用此种编码结构化（structured）的特性降低译码器设计的复杂度。相对于随机数生成的编码方式（Random code），传统的类回旋奇偶校验编码在编码长度大时，编码增益（coding gain）低落。

阶层式类回旋低密度奇偶校验编码

由于类回旋低密度机偶校验编码的奇偶校验矩阵（parity-check matrix）是由多个循环矩阵（circulant matrix）组成，因此此种非常适合用于硬件实现。阶层式类回旋奇偶校验编码的建构方式，则是先建立一个 m x n 的二元核心矩阵（core matrix）。将此核心矩阵中的1与0分别以大小为 q1 x q1循环矩阵与q1 x q1零矩阵（zero matrix）取代，在这样的矩阵展开（matrix expansion）后，可产生一个如同传统类回旋奇偶校验编码的奇偶校验矩阵。对此已展开的矩阵再以q2 x q2 的循环矩阵与q2 x q2零矩阵取代1与0。在经过两次的矩阵扩展后，可以得到一个二阶层的阶层式类回旋（two-level hierarchical quasi-cyclic）奇偶校验编码的奇偶校验矩阵。

《图一 二阶层阶层式类回旋奇偶校验编码校验矩阵》

二阶层的阶层式类回旋奇偶校验编码除了与传统类回旋奇偶校验编码一样易于硬件实现。在计算机仿真的结果显示（图二），可以发现二阶层的类回旋奇偶校验编码提供接近随机编码的编码增益外，也没有如同类回旋奇偶校验编码在高信号噪声比（signal to noise ratio）区的error floor现象。二阶层的阶层式类回旋奇偶校验编码可以套用任何可使用在类回旋奇偶校验编码上的排程算法。Jump-Reset排程算法[1]（图三）是一个可以使用在类回旋奇偶校验编码的排程算法，此排程算法的效率优于Y. Chen [2] 所提出的排程算法。Jump-Reset排程算法亦符合Y. Dai [3] 所提出的最佳算法的约束（constraint），且利用在二阶层的阶层式类回旋奇偶校验编码时可以将硬件使用效率从50%提升至100%。

《图二 类回旋编码、随机码与二阶层的类回旋编码仿真结果》

《图三 Jump-Reset排程算法》 - BigPic:678x197

二阶层的阶层式类回旋奇偶校验编码提供了两个参数q1, q2 ，其中q1提供编码长度的调整（即编码增益）。在相同的编码率（code rate）下，编码长度较长的编码可以提供较好的编码增益（相对的，硬件复杂度与硬件资源需求也会增加）。此外，由于译码器硬件实现上，在一个频率周期完成q2个讯息计算。因此q2则是提供译码平行度的调整，使得译码器架构可以适用不同性质的应用。

实验结果

为了提供高硬件使用效率，除了排程算法的使用外，内存也必须要能够支持列运算硬件与行运算硬件同时存取（concurrent access）。(表一)整理了一个二阶层的阶层式类回旋奇偶校验编码译码器硬件实现的成果。此译码器已经实现了Jump-Reset排程算法的技术但是尚未使用了内存交错（memory interleaving），目前传输速率已可以达到298.10Mbps。为了实现高硬件使用效率，未来的硬件实现套用内存交错可以在增加低于10%的逻辑单元提升50%的硬件使用效率外亦方便于工作频率的提升，达到780Mbps以上的传输速率。

（图四）比较传统类回旋奇偶校验编码与二阶层的阶层式类回旋奇偶校验编码之硬件实现的编码和软件实现的编码增益损失。类回旋奇偶校验编码译码器在编码增益的部分优于传统的类回旋编码，且硬件实现于位错误率（bit error rate）10-5，仅因为有限的精准度而损失0.05dB以下。

《图四 软件实现与硬件实现的编码增益比较》

结论

软件实现与硬件实现的编码增益比较

二阶层的类回旋奇偶校验编码搭配Jump-Rest排程算法与内存交错，可以提升硬件使用效率从50%至100%。此外，亦可以搭配合适硬件架构并藉由调整q1、q2参数广泛的使用于不同的应用领域。

（顾孟恺先生为美国加州大学洛杉矶分校电机工程博士，现任台湾大学信息工程研究所教授。

参考文献

[1] Yi-Hsing Chien, Mong-Kai Ku, "A High Throughput H-QC LDPC Decoder," accepted by IEEE International Symposium on Circuits and Systems 2007 (ISCAS 2007)

简义兴先生为台湾大学信息工程研究所博士生。）

[2] Y. Chen and K. K. Parhi, “Overlapped message passing for quasi-cyclic low-density parity check codes,” IEEE Trans. Circuits and Syst. I, vol. 51, pp. 1106–1113, Jun. 2004.