错误更正码简介

在现今使用的通讯系统中，错误更正码一直扮演着举足轻重的脚色，其主要作用在于更正经过传输媒介时所产生的错误。目前广泛地应用于各式的有线通讯、无线通讯以及各式的储存装置中。从另一方面来说，使用更错能力较好的错误更正码可以容许资料传送端以较小的功率传送信号，而接收端依然能正确地解回信号，达到减少耗能的效果。

目前常见的错误更正码包含里德所罗门码（Reed-Solomon Codes）、涡轮码（Turbo code）及低密度奇偶校验码（Low-density Parity-check Codes）等。其中的低密度奇偶校验编码（简称为LDPC）最早是由Robert Gallager博士在1962年于其博士论文中发表[1]，并且已被证实具有极为优越的性能。然而当时的科技却无法实现这种编码系统，低密度奇偶校验编码也就逐渐被人们所遗忘。直至三十多年后，随着科技的进步和超大型晶体电路的制程不断的演进，要实现低密度奇偶校验编码系统已不再是不可能的任务；同时以往所使用的编码系统已渐渐无法满足人类对于资料传输正确率与日俱增的需求，低密度奇偶校验编码终于在1995年由MacKay与Neal两位博士重新发现并加以研究，能够将资料传输正确率推至趋近向农极限（Shannon limit）[2]，如图一所示。因此，低密度奇偶校验编码已广受通讯标准制定者的兴趣。

《图一 位错误率（BER）与信噪比（SNR）的比较图。[2]》

低密度奇偶校验码简介

低密度奇偶校验编码是定义在一个稀疏矩阵（sparse matrix）上，在矩阵之中大部分的元素为0，只有​​少数的元素为1。而一个（n,k）低密度奇偶校验编码所对应奇偶校验矩阵的维度是（nk）*n，如图二是一个（16,8）低密度奇偶校验编码所对应的奇偶校验矩阵。

《图二 （16,8）低密度奇偶校验编码的奇偶校验矩阵。》

在解码上，可以把奇偶校验矩阵转换为二分图（bipartite graph），如图三为（16,8）低密度奇偶校验编码的二分图。转换方式是将奇偶校验矩阵中的列和行分别对应成图三的方形实心图案和圆形空心图案，其对应处理单元分别为检查点单元（Check Node Unit；CNU）和变数点单元（Bit Node Unit；BNU）。再将元素为1所对应行列的处理单元，用直线相连。每条直线代表检查点单元和变数点单元之间讯息的传递。在一般实际的应用上，低密度奇偶校验矩阵的长度至少是数百甚至可达数万之谱，因此矩阵中元素1的量也会很大，对应到实际的硬体架构时，也代表CNU和BNU之间的连线会非常复杂，同时也使得硬体所需面积增大。

《图三（16,8）低密度奇偶校验编码的二分图。 》

在CNU和BNU这两种运算单元中执行的运算有数种不同的演算法，目前较常使用的有和积演算法（Sum-product Algorithm；SPA）以及最小和演算法（Min-sum Algorithm；MSA ）。前者的错误更正能力极佳，但是牵涉的运算相当复杂，对硬体上的实现较为不利；后者则可视作是SPA简化后的版本，在表现上虽会略差一点，但是却大大地降低了运算复杂度。为了弥补MSA在表现上的不足，近期也有相当多的论文专门探讨如何增加些许额外的运算就能让MSA的错误更正能力更接近SPA，此类的方式也称作修正最小和演算法（Modified Min -sum Algorithm）。

在硬体的实现上大致可分为全平行式（Fully-parallel）和部分平行式（Partially-parallel）运算。全平行式的运算方式需要较多的运算单元，但是由于其平行展开的特性，所以特别适用于有高速度需求的通信系统；部分平行式的运算架构相对于前者则只需要较少的运算单元，但是缺点是速度也会比全平行式运算架构降低不少，适用于低传输低功率消耗要求的系统。

在众多低密度奇偶校验码的矩阵设计方式中，为了兼顾错误更正能力和硬体实现上的复杂度，于是发展出了一种称为准循环式（Quasi-cyclic）的矩阵结构。此种架构虽然会使得LDPC的错误更正能力变差一些，但是由于它具有局部性循环的效果，得使硬体设计的复杂度大大降低，目前如IEEE 802.11n和IEEE 802.16e皆采用此类结构。

低密度奇偶校验解码器实现之挑战

在实现LDPC编解码器的过程中，最大的困难有以下几点：

解码矩阵不易建立

依照最原始的理论来说，想要求得一个解码效果好的矩阵只要让矩阵中数值的位置随机散布即可，但是依这种方式建构出的矩阵由于不具规律，所以相当不利于实际LDPC解码器的硬体实现；然而太有规律的矩阵则会损害其解码的成效。因此如何在两者间取得一个平衡也是一门重要的课题。

编码器的硬体复杂度高

因为所谓的低密度矩阵指的是解码端的矩阵，若直接由此倒推回编码端的编码矩阵通常不是一个低密度矩阵，而且也难以找到规律，间接造成编码端的复杂度大大地提高。

硬体有效使用率低

由于LDPC解码时事迭代地来回运算,所以并非所有的运算单元随时都在运作,同时也造成解码时间上的浪费。

多模式操作

现今的通信系统中几乎都有多模式操作的特性，主要是为了配合不同的传输通道情形以及不同使用者的需求而设置。那么在解码端的设计上如果只是直接地做出数个LDPC解码器将是十分缺乏效率的作法，只会浪费大量的硬体面积。

降低耗能

耗能的议题在行动通讯系统中特别重要，假设装备同样的电池，若是晶片耗能越低则该设备的使用时间就可越长。就一般的LDPC解码方式而言，在解码端需要经过多次叠代运算才能将正确的资讯解出，若能有效地减少此处的叠代运算次数，或是减少在运算时的大量记忆体耗能，必能达到低耗能的目的。

绕线（Routing）复杂度高

在硬体实作的最后一步就是如何布置各单元间的绕线，由于LDPC的运算特性会使得绕线特别复杂，甚至常会有绕不出来的情况，所以如何将各个单元做适当的摆置以简化绕线难度也是不可忽视的问题。

低密度奇偶校验编解码器之实现

以目前最热门的两个规格—IEEE 802.16e和IEEE 802.11n来说：前者是应用于移动中的车辆环境，后者则是适用于局部性的区域网路。其著眼点各有不同，应用于前者的LDPC编解码器相当需要有低耗能的特性；用于后者则要求要有极高的解码速率，其吞吐量（Throughput）的要求甚至是前者的数十倍。

以下以IEEE 802.16e（Mobile WiMAX）规格为范例，展示一个可提供19个模式之LDPC解码晶片，这19个模式各有自己定义的原始讯息长度（information bits）、编码后长度（codeword）。由于在订定规格时就已经将LDPC解码端的矩阵订好，所以此处我们并不讨论解码矩阵的制定方式。我们在此提出一个简单的解码器架构设计：（1）以重新排列矩阵的方式减少解码时间，（2）做出支援多模式之位址产生器，（3）采用了提前终结机制以减少运算耗能，（4）使用棋盘式的摆置方法放置记忆体以降低绕线复杂度。

解码矩阵重新排列

由于LDPC解码时是由两种不同的运算单元叠代解码，若照原本的作法每次都只会有一半的运算单元运作，而另一半的运算单元则处于闲置状态，换句话说解码端运算单元的硬体使用率只有50％，不啻是硬体的浪费，也间接地增加了解码所需的时间。我们可以在完全不影响解码效能的情况下做矩阵的重新排列，借此达到两种运算单元可以在部分时间同时运算的效果，增加硬体使用率也同时减少解码所需的时间。最后可以将各时间的硬体平均使用率提高至75％，解码时间也可以缩短为原本的67％，而所花费的成本仅是少许的控制电路。

多模式位址产生器

为了能同时支援Mobile WiMAX LDPC 19个模式，我们仔细观察解码端的低密度矩阵，在不同的操作模式下，各个运算单元和其所对应记忆体的存放位址会有所不同，最直接的方式当然是将各个运算单元与可能所需的记忆体以多工器（Multiplexer）相连，但是这样的方式缺乏效率，而且为数众多的多工器也会占去不少的硬体面积。于是我们最后找出这19个模式互通的规律，做出适用于此规格的记忆体存取位址产生器，有效地达成同时支援19个模式的目标。

提前终结机制

最后解码的错误多寡与否其实和信号通过传输介质后所得的信噪比（Signal-to-Noise Ratio；SNR）有很大的关系：若传输通道的杂讯越强，所得信噪比越低，不利于解码；反之，若传输通道的杂讯越小，所得信噪比越高，有利于解码。在信噪比越低的情况下，通常需要越多的叠代运算次数才能达到应有的效能；相反来说，在高信噪比的情况下可能只需要少数几次的叠代运算就能将所有信号正确解出。

若能在仅损失些许的解码效能前提下，达到提前结束不必要解码运算的功能，将能大幅地减少解码端的耗能。依此原则，有各式不同的机制被提出，有些机制较复杂但比较不会影响解码效能，有些则强调其机制的简易性。无论是何种机制，基本上都是在资源（硬体面积、耗能）和效能两方面做取舍。

棋盘式摆放记忆体

在Mobile WMAX标准中所定义的LDPC解码矩阵属于准循环式矩阵，也就是在该大矩阵下的每一个小区块中都有自己的局部循环性规律，在此设计中共有上百个记忆体。采取的是棋盘式的摆设方式，如图四所示，如此排列的好处在于使运算单元至各个记忆体间不会形成过长的路径，也同时减低绕线的复杂度。并能将不需要使用的记忆体关闭，达到节能的效果。

《图四 芯片的布线图，其中的黑色方块是内存所在位置。》

结论与未来展望

本文运用数个技巧实现了一个适用于Mobile WiMAX多模式低功率低密度奇偶校验编解码器，其硬体实作数据摘要和比较如表一所示。

低密度奇偶校验码在错误更正能力上的优良是无庸置疑的，目前已引起全世界学术界跟业界的注意，目前台大实作出了第一颗同时支援Mobile WiMAX多模式的LDPC晶片，也已经发表在2007 IEEE Symposium on VLSI Circuits（SOVC）会议上。但是仍然碍于实作时面积太大，尤其是其中大部分的空间都是用于绕线，致使要完全实际纳入商品规格中仍有困难。未来或许可朝向如何解决绕线问题以及如何以合理的硬体达到高速的LDPC设计为目标继续研究。

《表一 LDPC芯片比较表》

参考资料

[1] R. Gallager, “Low-Density Parity-Check Codes,” IRE Trans. Inf. Theory, vol. 7, pp. 21–28, Jan. 1962.

[2] D. J. C. MacKay, “Good Error-Correcting Codes based on Very Sparse Matrices,” IEEE Trans. Inf. Theory, vol. 45, no. 3, pp. 399–431, Jan. 1999.

[3] X.-Y. Hu, E. Eleftheriou, D.-M. Arnold, and A. Dholakia, “Efficient implementations of the sum-product algorithm for decoding LDPC codes,” in Proc. IEEE Globecom, vol 2, Nov. 2001, pp. 1036–1036.

[4] D. J. C. MacKay, “Good Error-Correcting Codes based on Very Sparse Matrices,” IEEE Trans. Inf. Theory, vol. 45, no. 3, pp. 399–431, Jan. 1999.

[5] D. J. C. MacKay, “Good Error-Correcting Codes based on Very Sparse Matrices,” IEEE Trans. Inf. Theory, vol. 45, no. 3, pp. 399–431, Jan. 1999.

[6] I. C. Park and S.H. Kang, “Scheduling algorithm for partially parallel architecture of LDPC decoder by matrix permutation," in Proc. IEEE ISCAS, May 2005, pp. 5778–5781.

[7] S. M. Kim and K. K. Parhi%2C “Overlapped decoding for a class of quasi-cyclic LDPC codes%2C” in Proc. IEEE SiPS%2C Aug. 2004%2C pp. 113–117.

[8] Blanksby, AJ and Howland, CJ, “A 690-mW 1-Gb/s 1024-b, rate-1/2 low-density parity-check code decoder, ” IEEE Journal of Solid-State Circuits, Volume 37 , Issue 3, March 2002, pp. 404 - 412

[9] Darabiha, A., Carusone, A.C., and Kschischang, F.R., “Multi-Gbit/sec low density parity check decoders with reduced interconnect complexity, ” ISCAS 2005, Vol. 5, May 2005, pp.5194 – 5197

[10] Mansour, M.M. and Shanbhag, NRA 640-Mb/is 2048-bit programmable LDPC decoder chip, ”IEEE Journal of Solid-State Circuits, Volume 41, Issue 3, March 2006, pp. 684 – 698