datasheet
超过460,000+ 应用技术资源下载
pdf

高吞吐量LDPC码编码构造及其FPGA实现

  • 1星
  • 日期: 2014-03-05
  • 大小: 1.13MB
  • 所需积分:1分
  • 下载次数:1
  • favicon收藏
  • rep举报
  • 分享
  • free评论
标签: 高吞吐量LDPC码编码构造及其FPGA实现

低密度校验码(LDPC,Low Density Parity Check Code)是一种性能接近香农极限的信道编码,已被广泛地采用到各种无线通信领域标准中,包括我国的数字电视地面传输标准、欧洲第二代卫星数字视频广播标准(DVB-S2,Digital Video Broadcasting-Satellite 2)、IEEE 802.11n、IEEE 802.16e等。它是3G乃至将来4G通信系统中的核心技术之一。 当今LDPC码构造的主流方向有两个,分别是结合准循环(QC,Quasi Cyclic)移位结构的单次扩展构造和类似重复累积(RA,Repeat Accumulate)码构造。相应地,主要的LDPC码编码算法有基于生成矩阵的算法和基于迭代译码的算法。基于生成矩阵的编码算法吞吐量高,但是需要较多的寄存器和ROM资源;基于迭代译码的编码算法实现简单,但是吞吐量不高,且不容易构造高性能的好码。 本文在研究了上述几种码构造和编码算法之后,结合编译码器综合实现的复杂度考虑,提出了一种切实可行的基于二次扩展(Dex,Duplex Expansion)的QC-LDPC码构造方法,以实现高吞吐量的LDPC码收发端;并且充分利用该类码校验矩阵准循环移位结构的特点,结合RU算法,提出了一种新编码器的设计方案。 基于二次扩展的QC-LDPC码构造方法,是通过对母矩阵先后进行乱序扩展(Pex,Permutation Expansion)和循环移位扩展(CSEx,Cyclic Shift Expansion)实现的。在此基础上,为了实现可变码长、可变码率,一般编译码器需同时支持多个乱序扩展和循环移位扩展的扩展因子。本文所述二次扩展构造方法的特点在于,固定循环移位扩展的扩展因子大小不变,支持多个乱序扩展的扩展因子,使得译码器结构得以精简;构造得到的码字具有近似规则码的结构,便于硬件实现;(伪)随机生成的循环移位系数能够提高码字的误码性能,是对硬件实现和误码性能的一种折中。 新编码器在很大程度上考虑了资源的复用,使得实现复杂度近似与码长成正比。考虑到吞吐量的要求,新编码器结构完全抛弃了RU算法中串行的前向替换(FS,Forward Substitution)模块,同时简化了流水线结构,由原先RU算法的6级降低为4级;为了缩短编码延时,设计时安排每一级流水线计算所需的时钟数大致相同。 这种码字构造和编码联合设计方案具有以下优势:相比RU算法,新方案对可变码长、可变码率的支持更灵活,吞吐量也更大;相比基于生成矩阵的编码算法,新方案节省了50%以上的寄存器和ROM资源,单位资源下的吞吐量更大;相比类似重复累积码结构的基于迭代译码的编码算法,新方案使高性能LDPC码的构造更为方便。以上结果都在Xilinx Virtex II pro 70 FPGA上得到验证。 通过在实验板上实测表明,上述基于二次扩展的QC-LDPC码构造和相应的编码方案能够实现高吞吐量LDPC码收发端,在实际应用中具有很高的价值。 目前,LDPC码正向着非规则、自适应、信源信道及调制联合编码方向发展。跨层联合编码的构造方法,及其对应的编码算法,也必将成为信道编码理论未来的研究重点。

上海交通大学 硕士学位论文 高吞吐量LDPC码编码构造及其FPGA实现 姓名:张晨 申请学位级别:硕士 专业:通信与信息系统 指导教师:徐友云 20080101 摘要 高吞吐量 LDPC 码编码构造及其 FPGA 实现 摘要 低密度校验码(LDPC,Low Density Parity Check Code)是一种性能接 近香农极限的信道编码,已被广泛地采用到各种无线通信领域标准中,包 括我国的数字电视地面传输标准、欧洲第二代卫星数字视频广播标准 (DVB-S2, Digital Video Broadcasting-Satellite 2)、IEEE 802.11n、IEEE 802.16e 等。它是 3G 乃至将来 4G 通信系统中的核心技术之一。 当今 LDPC 码构造的主流方向有两个,分别是结合准循环(QC, Quasi Cyclic)移位结构的单次扩展构造和类似重复累积(RA, Repeat Accumulate) 码构造。相应地,主要的 LDPC 码编码算法有基于生成矩阵的算法和基于 迭代译码的算法。基于生成矩阵的编码算法吞吐量高,但是需要较多的寄 存器和 ROM 资源;基于迭代译码的编码算法实现简单,但是吞吐量不高, 且不容易构造高性能的好码。 本文在研究了上述几种码构造和编码算法之后,结合编译码器综合实 现的复杂度考虑,提出了一种切实可行的基于二次扩展(DEx, Duplex Expansion)的 QC-LDPC 码构造方法,以实现高吞吐量的 LDPC 码收发端; 并且充分利用该类码校验矩阵准循环移位结构的特点,结合 RU 算法,提出 了一种新编码器的设计方案。 基于二次扩展的 QC-LDPC 码构造方法,是通过对母矩阵先后进行乱序 扩展(PEx,Permutation Expansion)和循环移位扩展(CSEx,Cyclic Shift Expansion)实现的。在此基础上,为了实现可变码长、可变码率,一般编 译码器需同时支持多个乱序扩展和循环移位扩展的扩展因子。本文所述二 次扩展构造方法的特点在于,固定循环移位扩展的扩展因子大小不变,支 持多个乱序扩展的扩展因子,使得译码器结构得以精简;构造得到的码字 具有近似规则码的结构,便于硬件实现;(伪)随机生成的循环移位系数能 够提高码字的误码性能,是对硬件实现和误码性能的一种折中。 第I页 摘要 新编码器在很大程度上考虑了资源的复用,使得实现复杂度近似与码 长成正比。考虑到吞吐量的要求,新编码器结构完全抛弃了 RU 算法中串行 的前向替换(FS, Forward Substitution)模块,同时简化了流水线结构,由 原先 RU 算法的 6 级降低为 4 级;为了缩短编码延时,设计时安排每一级流 水线计算所需的时钟数大致相同。 这种码字构造和编码联合设计方案具有以下优势:相比 RU 算法,新方 案对可变码长、可变码率的支持更灵活,吞吐量也更大;相比基于生成矩 阵的编码算法,新方案节省了 50%以上的寄存器和 ROM 资源,单位资源下 的吞吐量更大;相比类似重复累积码结构的基于迭代译码的编码算法,新 方案使高性能 LDPC 码的构造更为方便。以上结果都在 Xilinx Virtex II pro 70 FPGA 上得到验证。 通过在实验板上实测表明,上述基于二次扩展的 QC-LDPC 码构造和相 应的编码方案能够实现高吞吐量 LDPC 码收发端,在实际应用中具有很高 的价值。 目前,LDPC 码正向着非规则、自适应、信源信道及调制联合编码方向 发展。跨层联合编码的构造方法,及其对应的编码算法,也必将成为信道 编码理论未来的研究重点。 关键词:低密度校验码,重复累积码,编码器,现场可编程门阵列 第 II 页 ABSTRACT CODE CONSTRUCTION AND ENCODER IMPLEMENTATION OF HIGH PAYLOAD LOW DENSITY PARITY CHECK CODE ABSTRACT LDPC codes perform close to the Shannon limit. It has been widely adopted by standards in the field of wireless communication, including DVB-TH, DVB-S2, IEEE 802.11n and IEEE 802.16e. LDPC codes have become one of the key technologies in 3G and even the next generation communication network. Today, there are two popular ways of constructing LDPC codes, namely Single Expansion code construction and Repeat Accumulate like code construction, both of which take advantage of the Quasi Cyclic structure. Corresponding to the two kinds of LDPC codes, two popular encoding algorithms apply, namely algorithm based on generation matrix and algorithm based on iterative decoding. The algorithm based on generation matrix can achieve a high payload, while it consumes lots of registers and ROM. The algorithm based on iterative decoding can be easily implemented, while LDPC codes with relatively high performance are hard to construct. After a detail analysis of the above construction methods and encoding algorithms, with consideration to the codec complexity, a flexible construction method called Duplex Expansion is proposed to achieve a high payload. Taking advantage of the Quasi Cyclic structure of the sparse H matrix, a new encoder algorithm is also presented. Duplex Expansion code construction is usually realized through a 第 III 页 ABSTRACT Permulation Expansion on mother matrix followed by a Cyclic Shift Expansion on base matrix. For flexible code rate and code length, multiple Permulation Expansion factors (PEx) and Cyclic Shift Expansion factors (CSEx) shall be supported by codec. The features of Duplex Expansion code construction illustrated in this article lie in: fixed CSEx factor and flexible PEx factors, facilitating decoder implementation; approximate regular LDPC code, making codec complexity low; pseudo random chosen PEx factors, improving performance. Thus, this specific Duplex Expansion code construction achieves a good tradeoff between hardware complexity and performance. The new encoding algorithm has enabled resource sharing wherever possible, which makes the encoder complexity in linear proportion to the code length. Fully considering a high payload, the forward substitution in RU algorithm is removed. Meanwhile, the number of pipeline stages has been reduced from 6 to 4. In order to reduce the encoding latency, all pipelines are designed to consume approximately the same number of clocks. Compared to RU algorithm, this proposed scheme is more flexible to support multiple code rates and code lengths with much higher payload. Compared to the algorithm based on generation matrix, it consumes much lower register and ROM resources, thus achieves a higher payload per unit resource. Compared to the algorithm based on Repeat Accumulate structure and iterative decoding algorithm, it is much easier to construct the codes with high performance. All the results have been proven by Xilinx Vertex II pro 70 FPGA. Upon board level testing, results show that the above Duplex Expansion code construction and encoder design of LDPC code can achieve a high payload with rather low resources. It enjoys a fairly high merit in practical application. Nowadays, irregular, flexible and joint source-channel-modulation LDPC code design has become the focus of future research. And the construction method of joint source-channel-modulation code and its corresponding encoding algorithm will continue to be studied in detail. KEY WORDS: LDPC, Repeat Accumulate, encoder, FPGA 第 IV 页 上海交通大学 学位论文原创性声明 本人郑重声明:所呈交的学位论文,是本人在导师的指导下,独立进行 研究工作所取得的成果。除文中已经注明引用的内容外,本论文不包含任何 其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献 的个人和集体,均已在文中以明确方式标明。本人完全意识到本声明的法律 结果由本人承担。 学位论文作者签名: 日期: 年 月 日 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定,同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版,允许论文被查 阅和借阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本 学位论文。 保密□,在 年解密后适用本授权书。 本学位论文属于 不保密□。 (请在以上方框内打“√”) 学位论文作者签名: 日期: 年 月 日 指导教师签名: 日期: 年 月 日 第一章 绪论 第一章 绪论 伴随着集成电路的飞速发展,以及摩尔定律的延续,上世纪 90 年代初,信道编码 迭代译码的方法再一次受到人们广泛的关注。随着 Turbo 码[1][2]、Turbo 乘积码[3](TPC, Turbo Product Code)的横空出世,以及 LDPC 码的重新发现,香农极限不再是遥不可及 的,人们把信道编码向着极限推进了一大步。本章将从信道编码基本理论开始,简述信 道编码的概念,从而引出本文的重点——LDPC 码,并对其基本概念、发展情况以及应 用前景作简要介绍。 1.1 信道编码基本理论 现实生活中,信息的传递难免受到信道的干扰,特别是无线通信系统中,信道的不 确定性导致了接收端接收信号质量的下降,信道编码存在的目的就是尽量减少接收端错 误接收的信息比例,从而做到信息的可靠传输。 信道编码的容错能力,是通过在传输码字中增加冗余实现的。冗余的作用是加大有 效码字之间的距离,这样接收端就能把有效码字和无效码字区分开来。最佳的接收方法 是最大似然的译码方法,在收到当前码字后,通过统计所有有效码字发送的可能性,将 可能性最大的那个有效码字判为接收到的正确信息。一般认为,有效码字集合中任意两 个码的距离越大,则这个码的性能越好。在几种特殊类型的码中间,这种距离是可以衡 量的。例如线形分组码就能用最小码距 dmin 来衡量其优劣,同样地,卷积码的优劣就能 用自由距离 dfree 来衡量。然而,最大似然的译码方法,在实际中却是难以实现的。它的 求取一般涉及遍历整个有效码字空间的操作,现实中仅可能对短码长的码采用,其余情 况下采用的都是一些次最优的,计算较为简单的算法,以降低译码复杂度,然而这样会 牺牲一定的误码性能。 这些简化的译码算法,并非很多时候都和最大似然算法保持着相当的性能差距,迭 代译码方法的出现使得人们找到了一种次最优的译码算法,随着硬件技术的发展,这一 算法在今天终于成为了现实,而它最成功的应用当属 LDPC 码。 第1页 第一章 绪论 1.2 LDPC 码简介 LDPC 码是低密度校验码(Low Density Parity Check Code)的简称,最早由 R.G.Gallager[4][5]在 1962 年提出,当时由于硬件技术的限制,其重要性没有为人们所广泛 认识。直到上世纪 90 年代前,学术界只有为数不多的学者发表了相关的论文,这些人 包括 Margulis[6]、Tanner[7]以及 Zyablov 和 Pinske[8]等。随着迭代译码方法在 Turbo 码上 的成功应用,MacKay[9][10]、Neal[10]和 Wiberg[11]又分别重新发现了 LDPC 码。LDPC 码 是一种线性分组码,顾名思义,校验矩阵的稀疏性是它的特点所在。LDPC 码最先使用 了循环迭代的方法进行译码,使现实可行的译码算法在性能上迅速逼近最佳算法,使信 道编码技术向香农极限又迈进了一步。 根据校验矩阵的某些特征,可以对 LDPC 码进行分类。如果校验矩阵是由一系列循 环移位方阵拼接而成的,则称之为准循环移位 LDPC(QC-LDPC)码;如果校验矩阵右 边的方阵仅有主对角线和一条次对角线上的元素非零,则称之为重复累积(RA)码; 如果校验矩阵所有的行重和列重相同,则称之为规则码,反之,则称之为非规则码。规 则码有其相应的表示方法,一般记作( N, dv, dc ),其中 N 表示码长,dc 表示行重,dv 表 示列重。这里给出了一个( 12, 3, 6 )规则 LDPC 码的校验矩阵,如图 1-1所示。 0 1 1 1 0 1 0 0 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 0 H = 1 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1 1 0 0 1 0 1 0   0 0 0 0 0 1 1 0 0 1 0 1 1 1 1 0 1 0 1 1 1 0 0 1   图1-1 一个( 12, 3, 6 )规则 LDPC 码的校验矩阵 Fig.1-1 An H matrix example of a ( 12, 3, 6 ) regular-LDPC code 1.3 LDPC 码的发展概况 自从上世纪 90 年代 LDPC 码被重新发现以来,学术界对它的研究就遍地开花,一 直如火如荼的进行着。 在误码性能方面,Shokrollari、Spielman、Luby、Mitzenmacher 和 Stemann 等人研 究了二进制擦除信道(BEC, Binary Erasure Channel)和二进制对称信道(BSC, Binary Symmetric Channel)下 LDPC 码的误码性能,并证明了在 BEC 信道下,随着码长的增 第2页 第一章 绪论 长,利用置信传播算法(BPA, Belief Proporgation Algorithm)[12][13]译码的 LDPC 码的性 能将逼近香农极限。Urbanke 和 Richardson 等人用密度演化(DE, Density Evolution)的 方法研究了 LDPC 码结合置信传播译码算法在其它信道下的误码性能,指出 LDPC 码在 其它很多信道中的传输速率都能趋近于信道容量。文献[14]对瑞利衰落信道中的 LDPC 码进行了性能分析,并且提出了相应的构造方法,得到了一种误码性能优于 Turbo 码的 LDPC 码。文献[15][16]结合了 LDPC 码与 OFDM 两种先进技术,提出了一种在 MPSK 调制下的 OFDM 系统中 LDPC 码的译码算法,并给出了性能分析。 在码字构造方面,人们从 LDPC 码的最小码距着手,通过有限几何的方法得到了一 些性能相当接近香农极限的 LDPC 码[17][18][19][20],文献[21]从译码角度出发,结合译码器 硬件结构,提出了一种码构造的方法。为了编码器实现方便,Hui Jin,Divsalar 以及 McEliece 等人提出了 RA[22]码,这种码的特点在于编码直接,非常适合低传输速率场合。 伴随着 RA 码的出现,一系列类 RA 码[23]迅速涌现,它们无不有着编码器设计简单的优 点,为 LDPC 码构造的发展提供了另一个方向。 在编码方面,Richardson 和 Urbanke 最先提出了将校验矩阵下三角化的想法[24],以 使编码复杂度降低到与码长近似成正比的程度。沿着这个角度出发,文献[25]在构造时 就将校验矩阵设计成下三角形式,但是这样做减少了校验矩阵的随机性,势必会影响误 码性能的提升。之后 Hui Jin,Divsalar 等人从码字构造方面开创了简单编码器的架构[22], 为人们实际寻找更简单的编码方法开辟了蹊径。随着准循环移位结构日渐成为 LDPC 码 的主流,Zongwang, Li 和 Shu,Lin 等人提出了基于生成矩阵的编码算法[26],作为 QC-LDPC 码编码的普适算法有着举足轻重的地位。最近 Shaqfeh 和 Goertz 又提出了基 于迭代译码的编码算法[27],对于某些特殊的校验矩阵而言,编码算法可以变得和 RA 码 一样简单。 在译码方面,置信传播算法一直占据着主流的地位。但是由于其复杂度仍然较高, 因此一系列简化算法应运而出,其中包括最小和算法、改进的最小和算法和分层的改进 最小和算法等。结合不同信道和调制方式,一些更简单的迭代算法也有着应用空间,比 如一些硬判决、软判决相结合的译码算法[28][29]。随着分层迭代译码思想的出现,LDPC 码译码器的吞吐量得以提升。文献[30]实现了最大净吞吐量 1Gbps 的译码器,当然它是 建立在硬件全并行的基础上的,H 矩阵的每一行和每一列都被固定成一个硬件处理单 元,将置信传播算法直接映射到了硬件上。文献[31]对 Turbo 码和 LDPC 码的译码复杂 度进行了比较,指出 LDPC 码译码器实现起来更简单。文献[32]对 LDPC 码译码器的定 点化进行了讨论。 第3页 第一章 绪论 1.4 LDPC 码的应用前景 LDPC 码的最大亮点是其接近香农极限的误码性能,这在当今强调低辐射、低功耗 的时代背景下显得尤其重要。 对于无线通信而言,终端设备一般具有体积小、携带方便、能耗低的特点。无线设 备的续航能力正日益为人们所重视,因此如何降低上行通信中的发射功率和下行通信中 的接收功率就成了人们当务之急,降低发射功率带来的必然结果是降低接收机的信噪 比,使得接收变得异常困难,而因为 LDPC 能在接近于香农极限的性噪比条件下正常工 作,因此它能够得到广泛的认可。国际上,LDPC 码已经被列入 IEEE 802.11n、IEEE 802.16e 等标准;在欧洲,LDPC 码已被用于第二代卫星数字视频广播标准(DVB-S2); 在我国,数字电视地面传播标准已经正式颁布并于今年 8 月强制执行,这标志着 LDPC 码已经正式走入国人的生活。 当然,我们也不能忽视了 LDPC 码在其他电子领域的应用。例如采用 LDPC 码进行 压缩和加密数据。在现今 TB 级的大容量硬盘中,为了延长硬盘使用寿命、降低硬盘功 耗,需要降低硬盘中的信噪比,这样就会对编码和纠错算法提出很高的要求,LDPC 码 有望解决这个难题。 如今在信道编码这一领域,LDPC 码面临的潜在竞争来自于 Turbo 码以及 Turbo 乘 积码等几种同样基于迭代译码的信道编码。拿 Turbo 码作对比,LDPC 码的优势在于译 码的并行性,而 Turbo 码的译码难以并行实现。另外,LDPC 码的译码要比 Turbo 码方 便,结构也更简单。然而,除了 RA 码和一些类似 RA 结构的码以外,其余 LDPC 码的 编码复杂度仍然比较高,这可能是制约 LDPC 码发展的一个重要瓶颈。 1.5 本章小结 本章首先简要介绍了信道编码的基本理论,进而引出了 LDPC 码,给出了其基本原 理、发展概况和应用前景。 一般情况下,信道编码的最佳译码方法是最大似然算法,在接收到一个码字时,它 通过计算所有有效码字的发送概率并取最大的那个码字来实现最佳译码,然而这样的复 杂度一般来说是不能接受的。迭代译码的引入为人们找到了一种次最优的译码方法,由 于硬件实现复杂度的关系直到上世纪 90 年代才为人们所关注。LDPC 码由于其校验矩 阵是稀疏的,因此在一次迭代中信息传递的次数不会很多,从而非常适合迭代译码,代 表着信道编码技术新的发展方向。 第4页 第一章 绪论 截止目前,LDPC 码已经被我国采用到数字电视地面传播标准中,并且 IEEE 802.16e (WiMax)、IEEE 802.11n 以及 DVB-S2 也已率先采用了这一编码技术,可见其有着广 阔的发展前景。 LDPC 码比起 Turbo 码有着天然的并行优势,因此它将是下一代无线通信系统中最 具有竞争力的信道编码方案。 第5页 第二章 LDPC 码译码算法 第二章 LDPC 码译码算法简介 迭代译码方法的可行性长久以来一直是 LDPC 码没能得到重视的主要原因,人们试 图从硬件和算法两方面改变这样的情况。自从摩尔定律提出之日起,至今一直是有效的, 当半导体技术顺利攻克 45 纳米后,在未来 10 年内,摩尔定律仍然是可以依赖的,这也 就为迭代译码算法提供了硬件上的保障。与此同时,人们也尽可能地降低迭代译码算法 的复杂度,由于算法复杂度与性能之间总保持着一种折中关系,因此如何在性能不损失 很多的前提下找到简化的译码算法也就成了人们努力的方向。 本章将首先介绍基于 Tanner 图的 LDPC 表示方式,然后给出经典的信息传递译码 算法(MPA, Message Passing Algorithm),其中将简要介绍置信传播算法及其几种比较常 用的简化算法。 2.1 LDPC 码的 Tanner 图表示 线性分组码既可以用它的生成矩阵 G 来表示,也可以用校验矩阵 H 来表示,对于 LDPC 码来说,由于校验矩阵是稀疏的,因此更容易用来表示,我们从以下汉明码的校 验矩阵看起: 1 0 1 0 1 0 1 H= 0 1 1 0 0 1 1 (2-1) 0 0 0 1 1 1 1 把 H 矩阵的每一列看作一个重复码,对应一个比特节点 xi;把 H 矩阵的每一行看 作一个类奇偶校验码,对应一个校验节点 fi;把 H 矩阵中 j 行 i 列的非零元素看作连接 上述比特节点 xi 和校验节点 fj 的一条边。 于是,对应式(2-1),可以得到图 2-1所示的 Tanner 图[7]。图中用等号表示一个比特 节点,用加号表示一个校验节点。 第6页 第二章 LDPC 码译码算法 + f1 + f2 + f3 ======= x1 x2 x3 x4 x5 x6 x7 图2-1 Tanner 图示例 Fig.2-1 An Example of Tanner Graph 显然,迭代译码时信息的传递是以 Tanner 图中的边为介质的,而 LDPC 码以其稀 疏的校验矩阵大大降低了 Tanner 图中边的数量,进而降低了迭代译码的复杂度,因此 LDPC 码的出现使得基于 Tanner 图的迭代译码算法得以真正有效地应用。那稀疏的结构 会不会影响 LDPC 码的误码性能呢? LDPC 码所引入的稀疏矩阵对于迭代译码性能的损失是很小的。假设实际传输需要 达到信道容量的 1-δ 倍(这里 δ 是某个趋近于零的正常数),可以证明:当 δ 趋向于零 的时候,校验矩阵 H 中“1”的个数只需要有 Nln(1/δ)的数量级,基于 Tanner 图的迭代译 码质量就不会明显下降,这里 N 是 LDPC 码码长。稀疏的校验矩阵带来的好处是,在 δ 趋向于零的情况下,每比特译码迭代总复杂度的数量级为 1/δln(1/δ);而在最大似然译码 算法中,当传输速率趋近信道容量时,这个复杂度函数是 1/δ 的指数函数。因此,LDPC 码迭代译码的理论基础是非常充实的。 2.2 信息传递算法 信息传递算法是一种常用的 LDPC 译码算法,其中置信传播算法(BPA,Belief Propagation Algorithm)是目前已知误码性能最好的 LDPC 译码算法。 首先我们看一下比特节点和校验节点分别是如何工作的。 第7页 第二章 LDPC 码译码算法 a1 e3 = a2 a4 e6 + a5 图2-2 信息在比特节点和校验节点的计算示意图 Fig.2-2 Illustration of information processing at bit node 图 2-2给出了信息在比特节点和校验节点的计算示意图。其中比特节点的外信息 e3 由式(2-2)决定,校验节点的外信息 e6 由式(2-3)决定: e3 = a1a2 + a1a2 (1− a1)(1− a2 ) (2-2) e6 = a3 (1− a4 ) + (1− a3 )a4 (2-3) 图中比特节点接收除了目标校验节点外其余所有校验节点传递的外信息以及信道 信息,计算后将互信息传递给目标校验节点。校验节点接收除了目标比特节点外其余所 有比特节点传递的外信息,计算后将互信息传递给目标比特节点。 这里,式(2-2)和(2-3)只是作示例用,实际情况下比特节点和校验节点的输入可能远 远大于两路,本章稍后部分将会作详细介绍。 在所有的信息传递算法中,置信传播算法是最常用的,对它稍作修正还能得到许多 简化算法。 2.2.1 置信传播算法 如式(2-2)、(2-3)所指出的那样,置信传播算法在 Tanner 图的边上传递的并不是硬值, 而是概率值,它是一种软值,相对硬值保留了更多的信息,相应地使译码性能得到很大 提高,所牺牲的复杂度也还是可以接受的。 为了说明置信传播算法,首先给出一些符号定义,并假定发送码字 c 的每一个比特 具有独立的分布: Rj = {i : H ji = 1},表示 H 矩阵第 j 行中非零元素列位置的集合; 第8页 第二章 LDPC 码译码算法 Rj \ i = {i ' : H ji' = 1} \ {i} ,表示 H 矩阵第 j 行中,除了第 i 列外非零元素列位置的集 合; Ci = { j : H ji = 1} ,表示 H 矩阵第 i 列中非零元素行位置的集合; Ci \ j = { j ' : H j'i = 1} \ { j} ,表示 H 矩阵第 i 列中,除了第 j 行之外非零元素行位置的 集合; Pi = Pr(ci = 1/ yi ) ,表示在信道接收信息 yi 前提下,信息节点 i 取 1 的概率; qij (b) 表示在已知除第 i 个校验方程外其他所有校验方程以及信道的信息时,发送 码字 ci = b 的概率; rji (b) 表示当 ci = b 时,第 j 个校验方程被满足的概率。 2.2.1.1 概率域上的置信传播算法 初始化:对于每一对满足 Hij = 1 的( i, j ),令: qij (0) =1− Pi = Pr( xi =1| yi ) = 1+ 1 e−2 yi /σ 2 (2-4) qij (1) = Pi = Pr( xi = −1 | yi ) = 1+ 1 e2 yi /σ 2 (2-5) 第一步:对每一个校验方程 j 以及相应的每一个 Rj 中的 i,计算以下两个概率度量: ∏ rji (0) = 1 2 + 1 2 i '∈R j \i (1 − 2qi ' j (1)) (2-6) rji (1) = 1− rji (0) (2-7) 第二步:利用上一步计算所得的 rji (0) 和 rji (1) 更新概率值 qij (0) 和 qij (1) ,对于每一个 j 进行以下计算: ∏ qij (0) = Kij (1− Pi ) rj'i (0) j '∈Ci \ j ∏ qij (1) = Kij Pi rj'i (1) j '∈Ci \ j (2-8) (2-9) 第9页 第二章 LDPC 码译码算法 ∏ 其中,常数 Kij 是归一化系数,使得 qij (0) + qij (1) = 1; rj'i (0) 表示信息比特取值 j '∈Ci \ j ∏ 为 0 时所有的校验方程得到满足的概率; rj'i (1) 表示信息比特取值为 1 时所有的校 j '∈Ci \ j 验方程得到满足的概率。 第三步:对于每一个 i,计算比特 i 取值为 0 和 1 的后验概率 Qi (0) 和 Qi (1) : ∏ Qi (0) = Ki (1− Pi ) rji (0) j∈Ci ∏ Qi (1) = Ki Pi rji (1) j∈Ci (2-10) (2-11) 其中,常数 Ki 是归一化系数,使得 Qi (0) + Qi (1) = 1。 硬判输出:对于每一个 i,进行如下判决 cˆi = 1  0 if else Qi (1) > 0.5 (2-12) 如果此时 cˆH T = 0 ,则译码成功并停止迭代;否则判定此次译码失败,若此时的迭 代次数少于最大预设迭代次数,则回到第一步;若达到最大迭代次数仍未成功,则宣告 译码失败。 实际应用中,由于概率域上的置信传播算法涉及的大多是乘法操作,因此不利于硬 件实现,一个自然的想法是利用取对数的方法将乘法转化为加法,因此就得到了下述对 数域上的置信传播算法。 2.2.1.2 对数域上的置信传播算法 在进一步研究对数域上置信传播算法前,需要在已有定义的基础上,增加对数域上 相应概念的定义。 来自信道的信息定义为: L(ci ) ≡ log Pr( xi Pr( xi = = +1 | −1 | yi ) yi ) ; ( ) 在比特节点上,定义 L(qij ) ≡ log qij (0) qij (1) ,αij ≡ sign L(qij ) 表示输出互信息的符号位, ( ) βij ≡ L qij 表示输出互信息幅度的绝对值; 第 10 页 第二章 LDPC 码译码算法 在校验节点上,定义 L(rji ) ≡ log rji (0) rji (1) ; 译码器输出定义为 L(Qi ) ≡ log Qi (0) Qi (1) ; 这些都是概率比的对数值,称它们为对数似然比(LLR,Log-Likelihood Ratio)。此 外,定义函数 φ ( x) − log tanh   1 2 x   = log ex ex +1 −1 ,当 x>0 时,容易证明: φ −1(x) = φ(x) (2-13) 以下过程描述对数域置信传播算法: 初始化:对于每一对满足 Hij = 1 的( i, j ),令: L(qij ) = L(ci ) = 2 yi / σ 2 (2-14) 第一步:对每一个校验方程 j 以及相应的每一个 Rj 中的 i,计算以下对数域度量: ∏ ∑ ( )    L(rij ) =  i'∈Rj \i αi' j φ  i'∈Rj \i φ βi' j  第二步:对于每一个 j,利用第一步的计算结果,计算以下对数域度量: ∑ L(qij ) = L(ci ) + L(rj'i ) j '∈Ci \ j 第三步:对于每一个 i,计算: ∑ L(Qi ) = L(ci ) + L(rji ) j∈Ci 硬判输出:对于每个 i,进行如下判决 (2-15) (2-16) (2-17) cˆi = 1  0 if else L(Qi ) < 0 (2-18) 如果此时 cˆH T = 0 ,则译码成功并停止迭代;否则判定此次译码失败,若此时的迭 代次数少于最大预设迭代次数,则回到第一步;若达到最大迭代次数仍未成功,则宣告 译码失败。 从上述算法过程中可见,对数域上的置信传播算法只涉及加减法和查表操作,比较 适合硬件实现。然而,由于式(2-15)的查表复杂度直接决定了对数域上置信传播算法的 实现复杂度,因此对该式的简化将有助于译码算法复杂度的大幅降低。 第 11 页 第二章 LDPC 码译码算法 2.2.2 最小和算法 由于置信传播译码算法的复杂度集中在(2-15)式的计算上,因此寻找一种简单函数 ( ) ∑ 来逼近式(2-15)的结果会是比较理想的。根据函数φ(x) 的特性, φ βi' j 的值可以用 i '∈Rj \i ( ) 最小的 βi' j 所对应的φ βi' j 的值来近似,于是 ∏ ∑ ( ) ∏ ( ) ∏ ( )   L(rij ) =  i '∈Rj αi' \i j φ  i '∈R j φ \i βi' j   =   i '∈R j \i αi' j iφ φ min i '∈Rj \i βi' j  = i '∈Rj αi' \i j i min i '∈Rj \i βi' j (2-19) 这就是“最小和”的原意。 然而,对置信传播算法的简化必然会带来算法性能上的损失,包括收敛速度和误码 性能,为了最大程度上弥补这些损失,人们又在最小和算法的基础上提出了一些改进算 法。 2.2.3 各种基于最小和算法的改进算法 ( ) ∑ 由函数φ(x) 的性质可知,最小和算法会得到比真实 φ βi' j 值更大的结果,因此 i '∈Rj \i 人为加入加性或者乘性因子可以修正这种误差,从而改善译码的性能,这一类算法统称 为改进的最小和算法(MMSA, Modified Minimum Sum Algorithm)。仿真证明改进的最 小和算法能够小幅提高译码器的误码性能。 由于改进的最小和算法的收敛速度和置信传播算法几乎一样,因此在某些需要高速 译码的领域,人们又引入了分层的改进的最小和算法(LMMSA, Layered Modified Minimum Sum Algorithm)。分层的概念就是把原先的一次迭代分解为现在的几次小迭 代,虽然几次小迭代所需要的总的时钟数和原先一次迭代的时钟数相同,但是这几次小 迭代之间是有信息互通的,虽然这样做会少量增加译码器的硬件资源,但是由于 LMMSA 算法可以使收敛速度增加一倍,即置信传播算法 20 次迭代等价于 LMMSA 算 法的 10 次迭代,因此从吞吐量的角度上来看仍然有着非常大的改善。 鉴于置信传播译码算法的变体还有很多种,在此不再一一列举。 2.3 本章小结 本章从 LDPC 的 Tanner 图表示开始,介绍了最常用的 LDPC 码迭代译码算法—— 第 12 页 第二章 LDPC 码译码算法 信息传递算法。其中一类置信传播算法目前广泛地应用于各类 LDPC 码译码器中。 2.2.1 给出了置信传播算法在概率域及对数域上计算的具体步骤,由于它传递的是 软信息,因此比一般传递硬值的译码算法需要更多的量化资源,但是由于软信息得到了 保留,因此误码性能有大幅的提高。由于传统的置信传播算法复杂度仍然较高,因此在 硬件实现上一般采用最小和算法代替。为了补偿最小和算法带来的性能损失,又引入了 加性或乘性因子,使最小和算法性能非常接近对数域的置信传播算法。由于改进的最小 和算法收敛速度不够快,在要求高吞吐量的领域一般采用分层的改进最小和译码算法, 虽然这样做会增加硬件资源,但是单位吞吐量所需的资源消耗仍然是下降的。 迭代译码的出现使得 LDPC 码在实际应用中具有了接近香农极限的误码性能,这也 促使 LDPC 码跻身各大通讯标准中。 在介绍完 LDPC 码基本译码算法后,下一章起将介绍本文的重点——高吞吐量 LDPC 码编码构造及其编码器实现方法。 第 13 页 第三章 主流 LDPC 码构造方法与编码算法 第三章 主流 LDPC 码构造方法与编码算法 比起 Turbo 码而言,LDPC 码在译码方面有着并行和简单的结构,然而较复杂的编 码结构始终是摆在 LDPC 码构造者面前的难题。尽管有普遍适用的 LDPC 编码算法存在, 但是由于其较高的复杂度,以及很少考虑资源的复用,一般在实际中不能直接采用,因 此简单的编码算法仍然需要基于特殊的码字构造。本章将简要介绍当今主流的码字构造 及其相应得编码算法,这也是第四章提出的一种高吞吐量 LDPC 码构造和编码的基础。 RU 算法作为最先提出的普适的 LDPC 码编码算法,为后来很多编码算法奠定了基 础,许多码构造和编码算法是通过在 RU 算法上作改进实现的。RU 算法也是本文提出 的编码算法的基础,3.1 将会简要介绍 RU 算法。 现在的 LDPC 码构造,一般都是建立在循环移位结构的基础上的。这样的构造需要 对基矩阵作单次扩展,其中基矩阵一般根据理论优化得到的度分布对确定校验矩阵的行 重和列重,所作的单次扩展则确定校验矩阵的细节,一般会尽量使校验矩阵满秩。优化 校验矩阵环长的过程同时存在于确定基矩阵和单次扩展之中。然而即使本质上都采用基 于循环移位结构的单次扩展方法,目前各大标准中所使用的构造仍然可以明显地分为两 个方向: 第一种方法根据优化理论得到的度分布对,或者某些优化环长的算法,例如边增长 (PEG, Progressive Edge Growth)算法确定基矩阵。我国数字电视地面传输标准中使用 的就是这种码构造方法。3.2 将对这种构造方法作相应的介绍,并且给出一种基于生成 矩阵的编码算法,这种算法可以解决几乎所有该类码构造的编码问题。 第二种方法对基矩阵的非零元素位置作了一定的规定,如要求最右边的方阵非零元 素占满主对角线和一条次对角线等。这种方法是受到 RA 码结构的启发,它的编码复杂 度和 RA 码相近,但是其吞吐量比传统 RA 码要高很多,原因在于引入了并行的累加结 构,并且它的译码器也比传统 RA 码容易实现。由于基于生成矩阵的编码算法对于寄存 器和 ROM 资源需求很大,并且和码长的平方成正比,在码长很长时就不适用了,因此 类似 RA 码的构造算法非常适合长码长情况。IEEE 802.11n、IEEE 802.16e 以及欧洲的 DVB-S2 标准中使用的就是这种码构造方法。3.3 将对这种构造方法作简要介绍,并且 给出相应的基于迭代译码的编码算法。 第 14 页 第三章 主流 LDPC 码构造方法与编码算法 3.1 RU 算法 作为一种线形分组码,LDPC 码可以使用信息比特 s 与生成矩阵 G 相乘的方法得到 编码后的码字 c,即 c = s·G。这样做的缺点是很明显的,由于 G 矩阵是通过对 H 矩阵 进行某些非线性操作得到的,因而一般是一个非稀疏的矩阵,而且很难保证有什么规律, 因此这种做法没有利用到 H 矩阵的任何特性,包括最明显的稀疏特性,是很不经济的。 既然从上述生成矩阵的方程式出发不能得到一种简单的编码算法,一个很自然的想法就 是从校验方程式 HcT = 0T 出发进行编码。 Richardson 和 Urbanke 在文献[24]中回答了这个问题。他们指出,针对任何一个普通 的校验矩阵 H,只需要对其进行一次软件上的简单预处理,使它变成一种类似下三角阵 的结构,就能进行简单编码了。并且这种编码算法的复杂度在大多数情况下近似与码长 成正比,因此它是一种具有普适意义的简单 LDPC 码编码算法。 3.1.1 RU 算法 RU 算法主要分为三个阶段:预处理阶段、编码阶段和码字交换阶段。 假设 H 矩阵是 M×N 维的,预处理通过对校验矩阵 H 作行交换和列交换,目的是把 H 矩阵变为如图 3-1所示的类似下三角的矩阵,其中矩阵 A 的大小为(M-g)×(N-M), 矩阵 B 的大小为(M-g)×g,下三角矩阵 T 的大小为(M-g)×(M-g),矩阵 C 的大小为 g×(N -M),矩阵 D 的大小为 g×g,矩阵 E 的大小为 g×(M-g)。同时需要保证由ϕ = −ET −1B + D 所定义的矩阵ϕ 是可逆的,如果本次预处理时ϕ 不可逆,则可以将矩阵 B、D 所在的某 些列进行内部交换或者与矩阵 A、C 的某些列互换,并进行下一次试探,直到ϕ 满秩为 止。由于预处理涉及的矩阵操作只涉及初等变换中的行交换和列交换,因此,经过预处 理后的矩阵 H*矩阵仍然是稀疏的。 第 15 页 第三章 主流 LDPC 码构造方法与编码算法 N-M g M- g A B T M-g M C D Eg N 图3-1 经行交换、列交换后的类似下三角校验矩阵 H* Fig.3-1 The reformed parity check matrix H* in approximately low triangle form 经过处理后的矩阵H*也是M×N维的,由图3-1可知,矩阵H*可以表示成如下形式: H * =  A C B D T E  (3-1) 为了推导简单,以下将 H*记作 H,事实上从校验方程式的角度上看,使用 H*和 H 的区别只是在于是否需要对 c 进行一次列交换,由于在 RU 编码的第三阶段——码字交 换阶段会对 c 进行从 H*到 H 的逆向列交换过程,因此这两次列交换过程在计算推导时 完全可以认为是透明的。 在式(3-1)两边同时左乘下三角矩阵    − I ET −1 O I    ,得到:  − I ET −1 O I  ⋅ H =  − ET A −1 A + C B − ET −1B + D T O  (3-2) 由校验方程式可知,编码后码字 c 满足 HcT = 0T。在此对 c 进行分割,令 c = ( s, p1, p2 ),其中 s 表示信息位,p1 和 p2 联合表示校验位,实际中分别对应矩阵 B、D 和 T、E 所在的列,则校验位的 p1 长度为 g,p2 长为(M-g)。由校验方程式,可将(3-2)式作如下 分解: AsT + Bp1T + Tp2T = 0 (3-3) (−ET −1A + C)sT + (−ET −1B + D) p1T = 0 (3-4) 定义矩阵ϕ = −ET −1B + D ,于是得到校验位 p1 和 p2 的表示式: 第 16 页 第三章 主流 LDPC 码构造方法与编码算法 p1T = −ϕ −1(−ET −1 A + C)sT (3-5) p2T = −T −1( AsT + Bp1T ) (3-6) 至此完成了RU算法的编码计算过程,以下我们简单分析RU算法的编码复杂度。在 式(3-5)中,由于ϕ −1 是大小为g×g的非稀疏矩阵,因此(3-5)式的计算复杂度与g2成正比。 同样地,在式(3-6)中,T-1是大小为(M-g)×(M-g)的非稀疏矩阵,但是由于T本身是下 三角的,因此T-1也是下三角的,于是其与向量的乘法可以使用文献[24]提出的前向替换 的方法来简化。这样,RU算法的编码复杂度就可以减少到O(N+g2),所以在编码预处理 阶段,要求g尽可能的小,也就要求下三角阵T的维数尽量大。RU算法的编码流程如图 3-2所示,除去输入输出级的话,一共需要6级流水线。 信息比特s 流水线 分级 被A乘 被T-1乘 被C乘 被E乘 异或 被φ-1乘 异或 被B乘 被T-1乘 校验比特p2 校验比特p1 图3-2 RU 编码算法流程图 Fig.3-2 Flow chart of RU encoding algorithm 第 17 页 第三章 主流 LDPC 码构造方法与编码算法 3.1.2 RU 算法的优缺点 RU算法从校验方程式出发,绕开了非稀疏的生成矩阵对LDPC码进行编码,充分利 用了校验矩阵稀疏的特点,是LDPC码第一种比较理想的编码方式。不仅如此,它通过 有限的两种初等变换求得一个维数较大的下三角方阵,利用其逆矩阵也是下三角的特 点,应用前向替换将非稀疏矩阵与向量的乘法简化,使得整体计算复杂度从O(N2)降低 到了O(N+g2)。 但是,RU算法的缺点也是比较明显的。首先,RU算法的流水级安排不合理,这里 指的是每一级流水线所消耗的时钟数相差比较大。拿码长为1536的LDPC码来说,算上 输入、输出两个缓存级,流水级所需的时钟数从1095到3906不等,这就会导致某些流水 级长时间不在工作状态,降低了硬件的利用效率。其次,在ϕ −1 没有被强制设计为某些 特殊简单矩阵的情况下,它与向量的乘法没有办法做任何简化,这会使RU算法在支持 自适应编码时显得力不从心。最后,前向替换方法是一把双刃剑,在解决了下三角非稀 疏矩阵与向量乘法的同时,也引入了串行的计算结构,使得目标向量中下一个分量的求 解依赖于该向量之前求得的所有分量,因此前向替换必须一位一位进行,大大限制了吞 吐量的提升,这一点和3.3 所介绍的一种传统RA码的累加结构是类似的。 综上所述,在硬件资源有限的前提下,RU算法只适合应用在吞吐量要求不太高、 码长不太长、不要求自适应编码的场合。然而在结合了准循环移位结构后,对其算法作 一些改进能得到一些非常实用的算法,因此RU算法的理论指导意义很大。 3.2 基于生成矩阵的编码算法 RU算法的普适性使得它能够解决一般LDPC码的编码问题,从3.1 的介绍中我们可 以看到,RU算法考虑的只是校验矩阵的稀疏性,它不对校验矩阵作任何其它假定,于 是当校验矩阵仍存在某种其他规律时,RU算法显然是不能预计的。正是由于RU方法存 在的这一不足,使得它与实际理想LDPC的编码算法仍有一定距离,这也促使人们往校 验矩阵上施加更多的约束,以达到简化编码算法的目的。 随着准循环移位结构的流行,人们开始重新审视基于生成矩阵的编码方法。此时的 生成矩阵已经不再是那种没有规律的非稀疏阵,在某些条件下,生成矩阵也具有了准循 环移位结构的特点。这种构造及编码方法的典型应用在于我国的数字电视地面传输标 准。本节将会简单介绍基于单次扩展的QC-LDPC码以及针对这一类码的基于生成矩阵的 第 18 页 第三章 主流 LDPC 码构造方法与编码算法 编码算法。 3.2.1 基于单次扩展的 QC-LDPC 码 首先给出一些关于QC-LDPC码的基本定义。若一个方阵可由单位矩阵经循环右移n 位后得到,那么这个矩阵称为循环移位单位阵(CSI, Cyclic Shift Identity);一般地,若 一个方阵除去第一行后的每一行都可由该方阵上一行经循环右移一位后得到,并且第一 行是最后一行经循环右移一位后得到,那么这个方阵称为循环移位阵(CSM, Cyclic Shift Matrix)。进一步,如果将zPEx个大小相同的循环移位单位阵和zPEx×(zPEx-1)个相同大小 的零阵拼接得到方阵,并且该方阵的行重、列重均为1,那么这个方阵称为准循环移位 单位阵(QCI, Quasi Cyclic Identity);一般地,如果将zPEx×zPEx个大小相同的循环移位阵 或者零阵拼接得到方阵,那么这个方阵称为准循环移位阵(QCM, Quasi Cyclic Matrix)。 显然,准循环移位单位阵是一种特殊的准循环移位阵。文献[26]证明了准循环移位阵的 加、减、乘、求逆运算(如果存在)所得仍是准循环移位阵。如果一个LDPC码的校验 矩阵由且仅由大小相同的循环移位阵或零阵拼接而成,那么此LDPC码称为QC-LDPC 码。 假设H矩阵的基矩阵大小是m×n的,一般 m ≤ n 。图3-3给出了QC-LDPC码校验矩阵 的模型,其中Hi,j (1 ≤ i ≤ m,1 ≤ j ≤ n) 为大小相同的循环移位阵或者零阵。 H1,1 H2,1 … H1,2 H H1,n-1 1,n … H2,2 H H2,n-1 2,n … … … … … … Hm,1 Hm,2 H Hm,n-1 m,n 图3-3 QC-LDPC 码校验矩阵 Fig.3-3 Parity Check matrix of QC-LDPC code 第 19 页 第三章 主流 LDPC 码构造方法与编码算法 3.2.2 基于生成矩阵的编码算法 基于生成矩阵的编码算法前提是构造出具有类似于图3-3的具有循环移位结构的生 成矩阵,即使在绝大多数情况下,该矩阵不是稀疏的。假设上述Hi,j的大小是zCSEx×zCSEx 的,即循环移位扩展的扩展因子是zCSEx。文献[26]分别给出了在下述三种情况下准循环 移位生成矩阵的构造方法: (1)当校验矩阵行满秩,且存在大小为(m×zCSEx)×(m×zCSEx)的由循环移位阵构成的 满秩子方阵; (2)当校验矩阵行满秩,但不存在大小为(m×zCSEx)×(m×zCSEx)的由循环移位阵构成 的满秩子方阵; (3)校验矩阵行不满秩; 为简单起见,仅就第一种情况作简要介绍。文献[26]给出了此时系统生成矩阵的形 式,如图3-4所示:其中I表示大小为zCSEx×zCSEx的单位阵,O表示大小为zCSEx×zCSEx的零矩 阵,Gi,j (1 ≤ i ≤ n − m,1 ≤ j ≤ m) 表示大小为zCSEx×zCSEx的循环移位阵。 … … I O O G1,1 G1,2 G1,m … … O I O G2,1 G2,2 G2,m … … … … … … O O… I … Gn-m,1 Gn-m,2 Gn-m,m 图3-4 第一种情况下 QC-LDPC 校验矩阵对应的系统型生成矩阵 Fig.3-4 The systematic generation matrix of type 1 QC-LDPC code 由于该生成矩阵是系统的,因此基于生成矩阵的编码算法如下: c = s ⋅G = s ⋅(I | P) = (s | s ⋅ P) (3-7) 其中,s是输入的信息比特,矩阵P对应矩阵G循环移位的部分。在作向量与非稀疏 矩阵P的乘法时,可以将P分拆成循环移位阵进行运算,循环移位阵的存储只需要存储首 行或者首列,应用循环移位寄存器就能得到下一行或者下一列。 因此,在Gi,j是循环移位阵的情况下,存储G矩阵所需要的ROM资源可以降低到一 第 20 页 第三章 主流 LDPC 码构造方法与编码算法 般基于生成矩阵编码算法的的1/zCSEx,在zCSEx相对码长较大的情况下,该算法还是可以 接受的。例如,在我国的数字电视地面传输标准中,码长7493,zCSEx = 127,使用该编 码算法仍比较经济。 3.2.3 基于生成矩阵编码算法的优缺点 由于形如图3-4的系统型生成矩阵一般都能够得到,因此基于生成矩阵的编码算法 可以通过许多并行的循环移位寄存器将ROM的存储资源降低到原先的1/zCSEx,通常zCSEx 都比较大,因此能大大降低ROM资源消耗。由于该算法从系统型生成矩阵出发,因此计 算步骤比起从校验方程式出发的RU算法显得简单、明了。由于不需要流水线结构,因 此编码延时几乎可以忽略不计。鉴于循环移位寄存器模块数量可以灵活配置,因此这种 编码方式可以控制吞吐量的大小,从串行结构到并行乃至全并行结构,根据实际需求吞 吐量可以相差两个数量级。由于循环移位寄存器可以为不同的LDPC码所共用,因此很 容易就能实现可变码长、可变码率的自适应LDPC码编码,当几种码的循环移位扩展因 子zCSEx相同时,这种复用将变得更为直接。 然而,它最大的不足在于,提升吞吐量时所需要花的代价是迅速提升寄存器数量, 两者几乎是呈线性关系的,这与我们有限资源下追求大吞吐量的设计是背道而驰的。另 外,无论是串行、并行还是全并行结构,在码率固定的情况下,寄存器数量总是与码长 成正比,因而在长码长的情况下,这种算法就显得不经济了。 综上所述,在硬件资源有限的前提下,基于生成矩阵的编码算法适合应用在吞吐量 要求不太高、码长不太长的场合,并且它能够支持可变码长、可变码率的自适应编码。 由于基于单次扩展的QC-LDPC码的性能和伪随机构造码相差无几,因而该算法比起RU 算法有着明显的优势,在现实中也有其用武之地。在我国的数字电视地面传输标准中, 结合实际传输对吞吐量的需求,规定LDPC码码长7493,支持0.4、0.6、0.8三种不同码 率,并且净吞吐量达到30Mbps左右,这正是基于生成矩阵编码算法最具优势的范围。 3.3 基于迭代译码的编码算法 尽管基于生成矩阵的编码算法已经可以在某些实际领域中直接应用,但是由于硬件 复杂度所限,在长码长、高吞吐量领域仍然缺乏竞争力。从3.2 的介绍中可以看到,基 于生成矩阵的编码算法在RU算法的基础上对校验矩阵施加了准循环移位结构的约束, 从而达到了简化编码算法的目的,那么一个自然的想法就是,如果进一步在此结构上增 加约束条件,是不是可以找到更加简单直接的编码算法呢? 第 21 页 第三章 主流 LDPC 码构造方法与编码算法 Hui Jin等人提出的RA码[22]为人们指明了方向。传统RA码可以同时被看作串行级联 Turbo码和LDPC码的特殊形式,因此可以利用类似Turbo码的简单编码方式,不需要利 用非稀疏的生成矩阵,从而使ROM的存储量保持在较低的水平,同时它也不需要进行流 水线分割,保持着较低的编码延时。然而传统RA码的一大缺点在于校验比特一般只能 串行输出,直到基于单次扩展的重复累积码的出现,校验比特的并行计算才得以实现, 吞吐量也得到了大幅提高。这种构造及编码方法已经广泛地应用在IEEE 802.11n、IEEE 802.16e等国际标准中。本节将会简单介绍基于单次扩展的重复累积码以及针对这一类码 的基于迭代译码的编码算法。 3.3.1 基于单次扩展的重复累积码 本节首先给出RA码的简要介绍。顾名思义,传统RA码的构造过程涉及三个阶段: 重复、交织、累加。由于RA码构造的这三个阶段是在Tanner图上进行的,因此校验矩阵 可以直接由Tanner图得到。传统RA码分为规则RA码和非规则RA码[23],它们的编码算法 一般是先采用低密度生成矩阵(LDGM, Low Density Generation Matrix)与输入向量相 乘,之后将结果输入累加器进行累加,图3-5给出了传统RA码的编码流程。RA码编码算 法复杂度很低,与码长成线性关系,并且不涉及任何非稀疏矩阵,这样的复杂度比起RU 算法乃至基于生成矩阵的算法都有着明显的改善。尽管连RA码的性能都堪比性能良好 的伪随机构造的LDPC码[22],但是RA码串行的累加计算使得这种编码器的吞吐量较小, 很难适应某些高吞吐量应用的需求。这里的累加器结构其实和3.1 所述的RU算法中的前 项替换模块有着异曲同工之处,都可以看作是下三角方阵与向量的乘法,所不同的只是 RA码的下三角方阵仅在主、次对角线上有非零元素。 n n LDGM qn 累加器 qn n LDGM (q-1)n 累加器 (q-1)n 规则RA码 非规则RA码 图3-5 传统 RA 码编码流程 Fig.3-5 Flow chart of RA encoding algorithm IEEE 802.11n和IEEE 802.16e分别定义了一种基于单次扩展的重复累积码,它仍然属 于3.2 所述QC-LDPC码的范畴,这类校验矩阵H完全由循环移位单位阵构成。假设H矩 阵的基矩阵大小是m×n的,循环移位扩展因子为zCSEx。H可以分成两部分,HS记为H的 第 22 页 第三章 主流 LDPC 码构造方法与编码算法 对应信息比特的子矩阵,HP记为H的对应校验比特的子矩阵,H = [HS, HP]。其中HP可 以被进一步分解成如下形式:  h0 0 −1   h1 00 −1 −1 −1 −1 Hp = hp H ′ p  =   h2  −1 0  0 −1 (3-8)  −1 −1  hm−1 −1 −1 0 0  −1 0  式中0表示大小为zCSEx×zCSEx的单位阵, −1表示大小为zCSEx×zCSEx的零矩阵。被记作列向 量形式的hP是由列重为3的列所组成,也就是说,hp = [1, −1,..., −1, 0, −1,..., −1,1]T ,这里的 1表示循环移位因子为1的大小为zCSEx×zCSEx的循环移位单位阵。于是,H就具有如下的形 式:  h0,0   h1,0  H =  hx,0   hm−1,0 h0,1 h1,1 hx,1 hm−1,1 h0,k −1 h1,k −1 hx,k −1 hm−1,k −1 10 −1 0 0 −1 1 −1 −1 −1 −1 0 −1 −1  00    −1 −1  0  (3-9) 其中x就是hP中大小为zCSEx×zCSEx的单位阵所对应的基矩阵中的行号。 由式(3-9)所定义的H矩阵之所以被称作基于单次扩展的重复累积码,不仅因为H矩 阵基矩阵靠右的方阵具有典型的双对角线结构,而且在作循环移位扩展时,右边方阵循 环移位阵的移位因子几乎都置为0,因此H矩阵本身靠右的方阵仍然大致具有双对角线的 结构,只是其中一条对角线不再是次对角线而已。 3.3.2 基于迭代译码的编码算法 基于迭代译码的编码方法的主要原理[27]是,把编码过程看成是一个编码后码字经过 二进制擦除信道(BEC)后的置信传播译码的恢复过程。具体说来,可以从译码器的角 度出发,认为编码后码字经过BEC后,所有信息比特均得到保留,所有校验比特均被擦 除。BEC信道模型下的迭代译码要比一般噪声信道模型下的迭代译码简单,这里比较典 型的噪声信道有加性高斯白噪声(AWGN)信道等,迭代译码简单是由于比特节点和校验 第 23 页 第三章 主流 LDPC 码构造方法与编码算法 节点之间传递的信息只有两种,从概率上来说就是1和0.5。 基于迭代译码的编码方法的基本思想是,如果某个校验比特所参与的任意一个校验 方程中,除该校验比特之外的所有一起参与校验方程的比特均是已知的,那么这个校验 比特就能被正确恢复。图3-6给出了基于迭代译码的编码方法的示例: 1 1 0 ??? 第一次迭代 110 01? 第二次迭代 11 001 0 信息比特节点 校验比特节点 校验节点 图3-6 基于迭代译码的编码方法的示例 Fig.3-6 An example of encoding algorithm based on iterative decoding 该编码方法需要对校验矩阵H做一些软件上的预处理。具体说来,它要求H矩阵的 由校验比特所组成的子集中不存在停止集(SS, Stopping Set)。停止集的定义是:如果S 是变量节点V的一个子集,并且所有与S相连的校验节点至少与S连接两次,那么S就称 为一个停止集。去除停止集的过程可以反向进行,通过使用贪婪算法寻找集合K,使得 集合K是变量节点V的一个子集,并且使V\K中不包含任何停止集。 以下给出基于迭代译码的LDPC码编码具体流程: (1) 删去H矩阵的冗余行,使得H#矩阵行满秩。 (2) 使用贪婪算法寻找矩阵变量节点集合K,使得V\K中不包含任何停止集。 (3) 对H#矩阵进行列交换得到H*,使得H* = [V\K对应的列,K对应的列]。 (4) 确定信息比特对应后K列中的位置。对H*进行高斯消元,后K列中列重不为1 的列对应的是信息比特的位置,否则对应的是需要提前判决的校验比特。 (5) 重新排列H#矩阵的列,使得由(4)确定的信息比特对应的列排在最左边, 需要提前判决的校验比特所对应的列排在中间,剩下的列排在右边,并将H* 中需要提前判决的校验比特所在列非零元素对应的行添加进来得到H~。 (6) 编码第一阶段根据H~中新加的行得到需要提前判决的校验比特的值。 (7) 编码第二阶段进行迭代译码。 然而,由于传统RA码的校验矩阵H结构很特殊,它的校验比特节点集中不存在任何 停止集,因此,在使用上述算法进行编码时不需要进行任何列交换或者添加任何新行, 第 24 页 第三章 主流 LDPC 码构造方法与编码算法 这是RA码的另一种可行的编码方法。 图3-7举例说明了RA码的校验矩阵H及其Tanner图示,图3-8说明了图3-7定义的RA 码相应的基于迭代译码的编码实现结构。 信息比特 校验比特 S0 S1 S2 S3 P0 P1 P2 P3 m0 1 0 0 1 1 0 0 0 校验方程 m1 0 1 1 0 1 1 0 0 m2 0 1 0 1 0 1 1 0 m3 1 0 1 0 0 0 1 1 变量节点 S0 S1 S2 S3 P0 P1 P2 P3 校验节点 m0 m1 m2 m3 图3-7 RA 码校验矩阵实例及其 Tanner 图示 Fig.3-7 H matrix and Tanner graph of an RA code 变量节点 S0 S1 S2 S3 校验节点 m0 m1 m2 m3 P0 P1 P2 P3 图3-8 RA 码基于迭代译码的编码实现结构 Fig.3-8 Encoding algorithm of an RA code based on iterative decoding 借鉴RA码的基于迭代译码的编码算法,对于式(3-9)给出的这类基于单次扩展的重 复累积码,基于迭代译码的编码过程也可以大大简化。存在一种新的预处理方法不仅可 以避免列交换,并且不需要向H矩阵添加任何新行,只要修改预处理方式,具体方法如 下: 将输入信息比特记为s,并且将它分为k = n-m组,每组包含zCSEx比特数据,则 s = [s0 , s1,…, sk−1] (3-10) 第 25 页 第三章 主流 LDPC 码构造方法与编码算法 其中si都是长度为zCSEx的行向量。相应地,校验比特也能被划分为长度为zCSEx的行 向量。于是,编码后码字就能记作 c = [s, ] [ ] p = s0 , s1,…sk−1, p0 , p1,… pm−1 (3-11) 根据HcT = 0,将其按行展开,得到: ∑  k−1  h0, j s j + ∏1 p0 + p1 = 0 (第0行)  j=0 ∑   hi, j s j + pi + pi+1 = 0 (i ≠ 0, x, m −1) j ∑   j hx, j s j + p0 + px + px+1 = 0 (第x行) ∑ ( )   j hm−1, j s j + ∏1 p0 + pm−1 = 0 第m-1行 (3-12) 其中 ∏1 p0 就是p0循环右移1位的结果,将(3-12)中所有式子相加,得到: m−1 k −1 ∑ ∑ p0 = hi, j s j i=0 j=0 (3-13) 可见一旦得到p0,由于[ p1, p2,…, pm−1]所对应的H矩阵具有类似RA码双对角线的结 构,之后的迭代译码就能由类似图3-8的结构实现了。 3.3.3 基于迭代译码编码算法的优缺点 首先值得肯定是,基于迭代译码的编码算法是继RU算法之后又一种普适的编码算 法,或许能够开创LDPC码编码的一个新的方向,对于编码工作者而言又多了一种选择。 同RU算法一样,在进一步对校验矩阵施加约束并对编码算法稍作修改后就能够获得复 杂度非常低的编码方法。由于它在对基于单次扩展的重复累积码这一类码进行编码的时 候不涉及任何非稀疏矩阵的操作,比起3.1 的RU算法和3.2 的基于生成矩阵的编码算法 都要简单许多,因此它在一定场合下是一种非常理想的编码方法。另外可以看到,由于 每个时刻可以同时计算zCSEx个校验比特,因此它的吞吐量要比传统的RA码高出zCSEx倍。 但事实上,除了RA码和上述基于单次扩展的重复累积码之外,还没有找到第三种 特殊码型,可以使得该算法复杂度明显降低。目前看来,这个问题很大程度上限制了误 码性能的提升,由于双对角线结构在上述两种H矩阵中的存在,引入了非常多的度二节 点,这给高性能码的构造增加了不少的难度。在绝大多数情况下,需要添加到H~的新行 都是非稀疏的,所以它会大大增加编码器的存储资源消耗。同样,很多时候需要提前判 第 26 页 第三章 主流 LDPC 码构造方法与编码算法 决的校验比特占所有校验比特的百分比还是很大的,并且列交换会使得原有的H矩阵的 特殊结构消失殆尽,例如循环移位结构,因此只有继续寻找这样的校验矩阵,使得预处 理尽量简单,才能使基于迭代译码的编码方法更流行。 综上所述,如果能够构造出性能足够好的基于单次扩展的重复累积码,基于迭代译 码的编码算法还是非常具有竞争力的。由于完全不涉及非稀疏矩阵的运算,因此它消耗 相对最少的资源,进而可以支持长码长的LDPC码。由于一个时钟周期内同时可以计算 zCSEx个校验比特,因此它可以支持相对较高的吞吐量。由于没有流水线结构,它可以简 单地支持可变码长、可变码率的自适应编码。IEEE802.11n、IEEE 802.16e标准中都给出 了这样的码字构造显然也是对这种编码方式的认可。 3.4 本章小结 本章花了一定量的篇幅介绍了现今主流的几种码构造及相应的编码方法,是为了第 四章提出的基于二次扩展的构造方法和相应的新编码算法作铺垫。 这里首先介绍了普适的RU算法,然后逐渐对校验矩阵施加约束,引出了QC-LDPC 码以及基于单次扩展的重复累积码,并介绍了相应的基于生成矩阵的编码算法和基于基 于迭代译码的编码算法。RU算法由于其内在的串行性,涉及非稀疏矩阵的处理,现在 已经甚少采用;基于生成矩阵的编码算法尽管可以达到相对最高的吞吐量,但是其资源 消耗在与码长成线形关系的前提下,又会随着吞吐量的增加而线形增长;基于迭代译码 的编码算法应用于基于单次扩展的重复累积码时具有内在的并行性,且不涉及任何非稀 疏矩阵的处理,是一种比较理想的编码算法,但是相应的高性能的码字却难于构造;因 此在硬件条件允许的情况下,如何找到一种既方便构造,又能够实现高吞吐量的码构造 及编码方法就成为了下一章的内容。 第 27 页 第四章 基于二次扩展的 QC-LDPC 码构造及其编码算法 第四章 基于二次扩展的 QC-LDPC 码构造及其编码算法 面对现实可行的高性能、自适应、高吞吐量LDPC码的构造要求,第三章中所述的 码构造和编码方法似乎都不尽如人意。RU算法由于对校验矩阵没有特殊要求,因而一 般误码性能比较高,但它不能做到高吞吐量、自适应地编码;基于生成矩阵的编码算法 可以满足高性能、自适应的要求,但是在资源有限的情况下,不能满足高吞吐量的要求; 基于迭代译码的编码算法对校验矩阵施加的约束过多,其右边方阵的近似双对角线结构 限制了码构造时的度分布对的优化范围,对于实现高性能码字构造非常困难。 RU算法限制吞吐量的瓶颈主要有两个,一是串行的前向替换过程,二是非稀疏矩 阵ϕ −1 与向量的乘法无法高速进行,然而,在校验矩阵本身具有循环移位结构的情况下, 是不是能够对这两处计算进行并行化处理呢?本章在RU算法的基础上提出了一种简化 的编码算法,其基础是建立在一种基于二次扩展的QC-LDPC码构造前提下的。该构造方 案固定了循环移位扩展的扩展因子大小不变,支持多个乱序扩展的扩展因子,使得译码 器结构得以精简,以确保译码器实现高性能、高吞吐量、自适应地译码;构造得到的码 字具有近似规则码的结构,便于编码器硬件实现;(伪)随机生成的循环移位系数能够 提高码字的误码性能,是对实现和性能的一种折中。与之对应的新编码器充分考虑了硬 件的可重用性,方便支持可变码长、可变码率的自适应编码,并且拥有近似基于生成矩 阵编码算法的最大吞吐量,是高吞吐量LDPC码的理想实现方法。 4.1 基于二次扩展的 QC-LDPC 码构造 4.1.1 近似规则 LDPC 码的二次扩展构造方法 一般的基于单次扩展的LDPC构造方法如3.2.1 所述,这里我们引入一种基于二次扩 展的QC-LDPC码,它对于基于循环移位结构的LDPC译码算法来说没有什么影响,然而 可以找到相对应的编码算法以实现高吞吐量、自适应的LDPC编码。 之所以在单次扩展的基础上引入二次扩展的构造的方法,其目的也是很明确的,那 就是在基矩阵上施加更多的约束,从而寻找更加简单的编码方法。因此,基于二次扩展 的LDPC码事实上也是QC-LDPC码的一种。纵观第三章的讨论,这一思想其实已经在基 第 28 页 第四章 基于二次扩展的 QC-LDPC 码构造及其编码算法 于单次扩展的重复累积码上有所应用,在3.3.1 中,校验矩阵H的基矩阵正是施加了类似 RA码的约束。 纵观校验矩阵H的基矩阵,一种自然的想法是,如果令其中非零元素的分布更加均 匀,是不是有并行处理的可能性呢?答案是肯定的。 近似规则码的二次扩展构造方法可以大致分为母矩阵确定、乱序扩展、基矩阵微调、 循环移位扩展等四个阶段: 母矩阵HM确定:由于构造的是规则码,因此使用元素为全“1”的dv×dc母矩阵,这 里dv表示目标校验矩阵H的列重,dc表示目标校验矩阵H的行重,由于在基矩阵微调步骤 中会涉及目标H矩阵的非规则化,因此这里的列重和行重仅仅代表绝大多数列重和行重 的值。一旦母矩阵确定,校验矩阵中准循环移位(单位)阵的数量也就随之确定了,一 般来说,校验矩阵有dv×dc个准循环移位(单位)阵。 第一次扩展——乱序扩展:将母矩阵中所有非零元素用大小为zPEx×zPEx的单位矩阵 的列乱序组合来代替,这里的zPEx称为乱序扩展因子。由于理论研究表明,环四的存在 会影响误码性能,需要在最终的校验矩阵中限制环四,因此此时不允许矩阵中存在环四。 基矩阵微调:仍然使用类似RU算法对矩阵的分割方法,此时限定矩阵T对应母矩阵 右上角的一个非零元素所在的位置。在进行完乱序扩展后,为了满足RU算法中ϕ 的可 逆性,需要对刚才得到的矩阵进行微调,一般需要删除某些位置上的非零元素,由于ϕ 的可逆与否很大程度上取决于矩阵D,因此在矩阵D所对应的部分作这样的操作最为合 适,这样的删除操作越少越好,一般控制在两次,且对应不同的两列,此时得到基矩阵 HB。 第二次扩展——循环移位扩展:将基矩阵HB中所有非零元素用大小为zCSEx×zCSEx的 循环移位单位阵代替,和第三章一样,这里的zCSEx仍然称为循环移位扩展因子。循环移 位因子决定扩展时单位矩阵循环右移的位数,如果为负表示循环左移的移位位数。参照 3.2.1 的定义,此时的校验矩阵H由dv×dc个准循环移位单位阵组成,而每个准循环移位 单位阵又由zPEx×zPEx个循环移位单位阵组成。 图4-1给出了近似规则码的二次扩展方法示意图,图中省略了基矩阵微调等中间步 骤。 第 29 页 第四章 基于二次扩展的 QC-LDPC 码构造及其编码算法 111111 111111 111111 乱序 扩展 zPEx×zPEx zCSEx×zCSEx的循环移位单位阵 循环移 T T 位扩展 HM HB H (zPEx×zCSEx)×(zPEx×zCSEx) 的准循环移位单位阵 图4-1 近似规则码的二次扩展构造示意图 Fig.4-1 Duplex Expansion Code Construction of approximately regular LDPC code 从上述构造方法中可见,为了实现编译码器的自适应,构造多个LDPC码时主要有 三大类方法可以选择。第一类方法是固定乱序扩展因子zPEx不变,只改变循环移位扩展 因子zCSEx;第二种方法是固定循环移位扩展因子zCSEx不变,只改变乱序扩展因子zPEx;第 三种方法则是同时改变乱序扩展因子zPEx和循环移位扩展因子zCSEx。鉴于译码器实现复 杂度和循环移位扩展因子zCSEx呈近似线性关系,因此实际中我们固定循环移位扩展因子 zCSEx不变。 4.1.2 实际码字及其性能 使用上述二次扩展构造得到的近似规则QC-LDPC码的各项参数如表4-1所示: 表4-1 基于二次扩展的近似规则 LDPC 码参数 码长N 2304 2304 2304 4608 4608 4608 码率R 7/8 3/4 1/2 7/8 3/4 1/2 行重dv 24 12 6 24 12 6 列重dc 3 3 3 3 3 3 乱序扩展因子zPEx 3 6 12 6 12 24 循环移位因子zCSEx 32 32 32 32 32 32 图4-2给出了码长2304的三种LDPC码与相同码长、码率随机构造的LDPC码的软件 仿真性能比较,仿真是在高斯加性白噪声(AWGN,Additive Whit Gaussion Noise)信 道下进行的,所使用的调制方式是二进制相移键控(BPSK,Binary Phase Shift Keying), 第 30 页 第四章 基于二次扩展的 QC-LDPC 码构造及其编码算法 所使用的译码算法是置信传播算法(BP,Belief Propagation),其最大迭代次数为100次。 可见,基于二次扩展构造的近似规则QC-LDPC码和随机码的性能没有明显区别。 图4-2 码长 2304 的 LDPC 码与随机码的性能比较 Fig.4-2 Performance comparison between proposed LDPC codes and randomly constructed code 4.2 基于二次扩展的 QC-LDPC 码编码算法 参考RU算法对校验矩阵的分类,我们同样可以把基于二次扩展的LDPC校验矩阵划 分成类似图3-1的结构,图4-3给出了这种划分。 s p1 p2 … … A1,1 B A1,dc-dv 1,1 T B1,dv-1 1,1 … … C1,1 D C1,dc-dv 1,1 E D1,dv-1 1,1 … … … … … … … Cdv-1,1 D Cdv-1,dc-dv dv-1,1 E Ddv-1,dv-1 dv-1,1 图4-3 基于二次扩展的 QC-LDPC 码校验矩阵示例 Fig.4-3 Parity check matrix of QC-LDPC codes based on duplex expansion 第 31 页 第四章 基于二次扩展的 QC-LDPC 码构造及其编码算法 由于矩阵D对应的基矩阵在微调时被删除过两个非零元素,并且矩阵D在之后的编 码算法中也没有直接参与,因此以下对校验矩阵特征的描述一般不包括矩阵D。由图4-3 可 见 , 校 验 矩 阵 H 共 包 含 dv×dc 个 小 方 块 , 每 一 块 都 代 表 了 一 个 大 小 为 (zPEx×zCSEx) ×(zPEx×zCSEx)的准循环移位单位阵,而每一个准循环移位单位阵都是由zPEx×zPEx个大小为 zCSEx×zCSEx的循环移位单位阵或者零阵构成的。 对应RU编码算法的划分,矩阵A由(dc-dv)个准循环移位单位阵构成,列重仅为1; 矩阵B由(dv-1)个准循环移位单位阵构成,列重同矩阵A一样仅为1;矩阵T仅由一个准 循环移位单位阵构成,这与RU算法中要求T是下三角矩阵是完全不同的,进而可以采用 不同的处理方法完全避免下三角矩阵乘向量时串行的前向替换结构的使用;矩阵C由(dv -1)×(dc-dv)个准循环移位单位阵构成,矩阵D由(dv-1)×(dv-1)个准循环移位单位阵构 成;矩阵E由(dv-1)个循环移位单位阵构成,因此行重仅为1。 这种基于二次扩展的QC-LDPC码校验矩阵的结构决定了它能够同时结合RU算法和 利用循环移位的结构。从本质上来看,它仍然是QC-LDPC码的一种,只是其基矩阵上非 零元素的分布更加均匀而已;它又能够大致匹配RU算法对校验矩阵的划分,只是T矩阵 的大小被限制在一个准循环移位单位阵上。这样,T不再需要是下三角矩阵,并且T-1不 再是非稀疏矩阵,这对RU算法流水级的重新划分有着重要意义,使得前向替换不再成 为编码器吞吐量的瓶颈。尽管由于矩阵T大小的大幅减小,此时的非稀疏矩阵ϕ −1 不再像 RU算法中那么小,但是由于可以借鉴基于生成矩阵的编码算法,在硬件上引入循环移 位寄存器结构,因此在相比RU算法牺牲了一点ROM和寄存器资源后,非稀疏矩阵乘向 量的乘法也能够高速并行计算。上述两点为最终编码器的高吞吐量奠定了基础。 4.2.1 RU 算法流水级的简化 在3.1.2 叙述RU算法的优缺点时,提到了各级流水级之间的不平衡性以及前向替换 方法的串行性。流水级间的不平衡主要是指它们各自运算所需的时钟数不平衡,最大差 异可以达到4倍;前向替换方法解决的是非稀疏下三角矩阵的逆矩阵与向量的乘法,利 用了逆矩阵的下三角特性减少了资源消耗,却限制了编码器的吞吐量。然而,基于二次 扩展的QC-LDPC码构造方法的出现为同时解决这两个问题提供了可行性。 由于准循环移位阵的加、减、乘、求逆运算(如果存在)所得的结果仍是准循环移 位阵,因此把T构造成准循环移位阵就显得非常有意义。由于T-1也是准循环移位单位阵, 重新观察式(3-5),(3-6),可见经过准循环移位单位阵的分块计算后,矩阵ET-1A、T-1A 和T-1B都由准循环移位单位阵组成,这些计算完全可以提前到预处理中进行,使得矩阵 第 32 页 第四章 基于二次扩展的 QC-LDPC 码构造及其编码算法 T的存在对编码器完全透明,这样就能够完全避免前向替换的过程,为整个流水级的优 化奠定了基础。 p1T = −ϕ −1(−ET −1 A + C)sT (4-1) p2T = −T −1( AsT + Bp1T ) (4-2) 将RU算法中式(4-1)、(4-2)按照上述准循环移位单位阵的算法对某些矩阵操作进行 合并,就能够改写成: p1T = −ϕ −1(−E((T −1 A)sT ) + CsT ) (4-3) p2T = −((T −1 A)sT + (T −1B) p1T ) (4-4) 在式(4-3)、(4-4)中,由于矩阵T-1A和T-1B分别可以视作一个整体,因此在编码时没 有必要将矩阵A、B、T分开存储;尽管矩阵ET-1A也可以在预处理中进行,但是由于计 算向量T-1AsT是编码计算的必然步骤,因此向量ET-1AsT只需要在此基础上作一次准循环 移位单位阵与向量的乘法就行,也就没有必要对矩阵ET-1A进行预处理。 基于式(4-3)、(4-4)的新编码算法的流程图如图4-4所示,与图3-2所示的RU算法流程 图相比,矩阵T对于编码算法已经完全透明,这也就完全除去了串行的前线替换步骤, 使得流水线级数从原先的6级减少到现在的4级,不仅缩短了编码延时,而且增加了吞吐 量。通过下一章对各个主要运算模块的具体分析还将看到,新编码方案每一级流水线计 算所需要的时钟数是基本相等的,这也为进一步提高编码吞吐量奠定了基础。 第 33 页 第四章 基于二次扩展的 QC-LDPC 码构造及其编码算法 流水线 分级 信息比特 s 被T-1A乘 被C乘 被E乘 异或 被φ-1乘 异或 被T-1B乘 校验比特p2 校验比特p1 图4-4 新编码算法流程图 Fig.4-4 Flow chart of proposed encoding algorithm 由图4-4的编码流程可知,新编码算法主要涉及三种运算,分别是向量加法(VA, Vector Addition),准循环移位单位阵乘向量(CSIMV, Cyclic Shift Identity Matrix Vector Multiplication)和准循环移位阵乘向量(CSDMV, Cyclic Shift Dense Matrix Vector Multiplication)。其中向量加法包括向量ET-1AsT与向量CsT以及向量T-1AsT与向量T-1Bp1T 的加法,它们都可以通过将向量分为长度zPEx×zCSEx的段逐比特并行实现;准循环移位单 位阵乘向量涉及矩阵T-1A、T-1B、C、E与向量的乘法;准循环移位阵乘向量涉及矩阵ϕ −1 与向量的乘法。 在下一章中可以看到,新编码方案的所有运算都是以准循环移位(单位)阵为基本 单位并行计算的,本章暂时只对单个准循环移位(单位)阵乘向量的运算进行描述 4.2.2 准循环移位单位阵乘向量 由3.2.1 的定义可知,准循环移位单位阵是由zPEx个大小相同的循环移位单位阵和 zPEx×(zPEx-1)个相同大小的零阵拼接得到的方阵,它作为特殊的准循环移位阵,不但在 第 34 页 第四章 基于二次扩展的 QC-LDPC 码构造及其编码算法 于它是由循环移位单位阵构成,而且它的行重、列重均为1。图4-5给出了一个zPEx = zCSEx =3的准循环移位单位阵的例子,可见由于其特殊的结构特别适合分块的串行或并行计 算,这种分块计算的最小单位其实就是循环移位单位阵乘向量的运算。 大小为3×3的循环移位单位阵 1 1 1 1 1 1 1 1 1 图4-5 zPEx = zCSEx = 3 的准循环移位单位阵示例 Fig.4-5 Example of Quasi-Cyclic-Identity with zPEx = zCSEx = 3 循环移位单位阵乘向量运算相当于将被乘向量进行循环移位。具体来说,如果大小 为zCSEx×zCSEx的循环移位单位阵的移位因子是α,它与一个长度为zCSEx的向量相乘,其结 果向量就是将输入向量循环上移α位。 综上所述,准循环移位单位阵乘向量运算可以通过zPEx个循环移位单位阵乘向量串 行运算实现,而循环移位单位阵乘向量就是对向量进行循环上移。对长度为zCSEx的向量 进行循环上移是通过逐比特循环读取存储该向量的RAM实现的,一共需要zCSEx个时钟, 因此准循环移位单位阵乘向量的运算可以在zPEx×zCSEx个时钟周期内完成。 硬件实现准循环移位单位阵乘向量运算时,需要预先生成输入向量RAM的读地址, 对于准循环移位单位阵中每一个非零的循环移位单位阵需要存储一个这样的读地址在 ROM中。由于输入向量的长度为zPEx×zCSEx,而每个循环移位单位阵对应的向量长度仅为 zCSEx,因此上述读地址可以看作由高、低两段组成,高段指示当前循环移位单位阵在准 循环移位单位阵中的横向位置,低段初始值指示当前循环移位单位阵的移位因子,之后 在每个时钟到来时对低段地址进行循环移位,每zCSEx个时钟重置整个地址就行。详细的 硬件实现将在下一章中给出。 第 35 页 第四章 基于二次扩展的 QC-LDPC 码构造及其编码算法 4.2.3 准循环移位阵乘向量 由3.2.1 的定义可知,准循环移位阵是由zPEx×zPEx个大小相同的循环移位阵拼接得到 的方阵。对于新编码算法来说,只有ϕ 是由准循环移位阵构成的,这是因为ϕ 是经过由 准循环移位单位阵构成的矩阵E、T-1、B、D加、减、乘运算的结果,即ϕ = −ET −1B + D 。 由于在4.1.1 构造时对基矩阵进行了微调,从而保证ϕ −1 是存在的,因此ϕ −1 也是由准循 环移位阵构成的,一般来说它不是稀疏的。矩阵ϕ −1 的大小同矩阵D一样,是由(dv-1)×(dv -1)个准循环移位阵构成的。 大小为3×3的循环移位阵 11 1 11 11 1 1 1 1 1 111 1 1 11 111 1 1 11 1 1 1 1 1 11 1 1 11 1 1 图4-6 zPEx = zCSEx = 3 的准循环移位阵示例 Fig.4-6 Example of Quasi-Cyclic-Matrix with zPEx = zCSEx = 3 图4-6给出了一个zPEx = zCSEx = 3的准循环移位阵的例子。由于在同一个校验矩阵中, 准循环移位单位阵和准循环移位阵的大小是相同的,为了保证高吞吐量编码器的实现, 需要它们有相同的计算速度,因此在准循环移位单位阵分块串行计算的基础上,准循环 移位阵的乘法需要采用分块并行计算,以弥补更多的非零循环移位阵的存在。这种分块 计算的最小单位其实就是循环移位阵乘向量的运算。 在Lin Shu[26]提出的基于生成矩阵的编码算法中,具体给出了两种循环移位阵乘向 量的实现方法。一种方法是将循环移位阵按行置入循环移位寄存器,将整个输入向量存 储在另一组寄存器中,每个时钟到来时,对两个寄存器组按位做一次与操作后再逐比特 异或,得到目标向量的一位,同时上述循环移位寄存器右移一位,相当于置入了循环移 第 36 页 第四章 基于二次扩展的 QC-LDPC 码构造及其编码算法 位阵的下一行,其具体结构如图4-7所示;另一种方法是将循环移位阵按列置入循环移 位寄存器,令输入向量逐比特进入,每个时钟到来时,令当前输入比特与循环移位寄存 器的每一位按位进行与操作,将所得结果向量与先前得到的中间结果向量再按位进行一 次异或操作后存入中间结果寄存器,其具体结构如图4-8所示。 长度为zCSEx的循环移位寄存器 …… x x1 x2 xzCSEx-1 1 2 …… xzCSEx zCSEx zCSEx位的异或 目标向量的一位 图4-7 按行置入的循环移位阵乘向量结构 Fig.4-7 Structure of QC matrix multiplied by vector through rows xi 1 XOR 长度为zCSEx的循环移位寄存器A …… 2 …… zCSEx XOR …… XOR XOR …… 长度为zCSEx的寄存器B 图4-8 按列置入的循环移位阵乘向量结构 Fig.4-8 Structure of QC matrix multiplied by vector through columns 第 37 页 第四章 基于二次扩展的 QC-LDPC 码构造及其编码算法 无论是按行置入还是按列置入的循环移位阵乘向量运算,需要的硬件资源和所能实 现的吞吐量都是一致的。具体说来,如果大小为zCSEx×zCSEx的循环移位阵与长度为zCSEx 的向量相乘,无论采用上述哪种方法都能够在zCSEx个时钟周期内得到目标向量,都需要 一组长度为zCSEx的循环移位寄存器以及另一组长度为zCSEx的寄存器,以及zCSEx×zCSEx次按 位与操作和zCSEx×zCSEx次异或操作。由于使用了zPEx组这样的计算模块并行计算,因此准 循环移位阵乘向量运算可以在zPEx×zCSEx个时钟周期内完成,这和相同大小准循环移位单 位阵乘向量运算有着一样快的速度。 由于上述两种处理方式在资源消耗和吞吐量上是无差别的,因此实际中在考虑使用 哪种方法时,只需要知道前级计算模块是如何给出输入向量的。在新编码算法中,准循 环移位阵乘向量的前级运算是向量加法,其中参与加法的向量 (−ET −1A + C)sT 是通过准 循环移位单位阵乘向量并行实现的。从4.2.2 的描述中我们知道,准循环移位单位阵乘 向量的结果是逐比特输出的,因此实际中我们采用按列置入的结构进行循环移位阵乘向 量的运算。 综上所述,新编码方案结合了RU算法和基于生成矩阵编码算法的优点,由于矩阵 ϕ −1 是由准循环移位阵组成的,因此可以采用基于生成矩阵的编码算法将RU算法中这一 块非稀疏矩阵乘向量算法替换掉,从而去除了限制吞吐量的一大瓶颈。同时,由于新编 码算法仅针对矩阵ϕ −1 部分采用了基于生成矩阵的编码算法,有利于控制总的ROM和寄 存器资源消耗,由于一般ϕ −1 的大小不会随着码率的增加而增加,因此这样的做法在吞 吐量和复杂度之间作了一个很好的折中。 4.2.4 对于码长、码率的自适应 基于二次扩展的QC-LDPC码的码率R、码长N与列重dv、乱序扩展因子zPEx、循环移 位扩展因子zCSEx之间的关系可以用下式表示: N (1 − R) = dv × zPEx × zCSEx (4-5) 仿真证明,1/2码率的LDPC码列重取dv = 3是最合适的,因此实际中我们也是这样做 的。另外考虑到译码器的实现复杂度和循环移位扩展因子zCSEx成正比,因此实际中固定 zCSEx = 32不变。从4.2.2 可知,对准循环移位单位阵来说,固定循环移位扩展因子zCSEx 意味着生成的读地址只需要随着乱序扩展因子zPEx的增大而增加高位的位宽;从4.2.3 可 第 38 页 第四章 基于二次扩展的 QC-LDPC 码构造及其编码算法 知,固定循环移位扩展因子zCSEx意味着循环移位阵乘向量运算本身不需要作任何改变, 只需要随着乱序扩展因子zPEx的增加添加相应数量的并行计算模块即可。由于上述两种 运算是新编码算法的核心运算,因此它们只需要分别为最大乱序扩展因子zPEx预留足够 的读地址位宽或者并行计算单元,这样的编码器完全能够支持所有较小的乱序扩展因子 zPEx。因此,除了4.1.2 给出的参数以外,新编码算法还可以在几乎只增加ROM资源的前 提下实现诸如R = 6/7、5/6、4/5、2/3的不同码率,以及各种其他码长。 可见,在流水级被重新安排后,新编码算法已经和基于生成矩阵的算法一样,可以 支持原RU算法不能支持的多码长、多码率自适应编码,而相比RU算法牺牲的代价仅仅 是对矩阵ϕ −1 部分采用类似基于生成矩阵的编码算法。关于这部分更详细的讨论,请见 下一章的相关部分。 4.3 本章小结 本 章 在 基 于 单 次 扩 展 的 QC-LDPC 码 构 造 的 基 础 上 , 提 出 了 基 于 二 次 扩 展 的 QC-LDPC码构造,通过对基矩阵施加更多的约束,以达到简化编码的目的。4.1.2 给出 了实际构造的不同码长、不同码率的QC-LDPC码的误码性能,证明了使校验矩阵中非零 元素的分布更均匀的构造方法不会对码字的误码性能构成很大的影响。 在具体实施二次扩展过程中,可以通过固定循环移位扩展因子zCSEx,方便译码器实 现;通过改变母矩阵以及乱序扩展因子zPEx,可以实现不同码长、不同码率的QC-LDPC 码构造。 对于上述码构造方法,本章提出了一种结合RU算法和基于生成矩阵编码算法的改 进算法,通过对QC-LDPC码的校验矩阵H引入RU算法中的分割,并将子矩阵T限制成一 个准循环移位单位阵,彻底移除了RU算法中前向替换的模块;通过对矩阵ϕ −1 乘向量部 分采用基于生成矩阵的编码算法,大大提高了该部分的计算并行度。在改进了上述两大 限制RU算法吞吐量的环节后,实现了相对高吞吐量的编码算法。与此同时,新编码算 法的流水级也由RU算法的6级降到了4级,进一步降低了编码时延。 由于新编码算法的核心——准循环移位单位阵乘向量运算以及准循环移位阵乘向 量运算分别为最大的乱序扩展因子zPEx保留了大位宽的读地址和相应数量的并行计算模 块,因此码字在线切换时,只需要配置地址位宽和这些冗余的计算模块使之处于运行或 者等待状态即可。 新编码算法在RU算法基础上提高了吞吐量,并且实现了多码长、多码率的自适应 第 39 页 第四章 基于二次扩展的 QC-LDPC 码构造及其编码算法 编码,牺牲的代价仅仅是对矩阵ϕ −1 部分采用类似基于生成矩阵的编码算法,因而它既 具有相对基于生成矩阵编码算法低资源消耗的特点,又具有相对RU算法高吞吐量、自 适应的优势,是一种对上述两种算法的很好的折中。 下一章将对新编码算法在FPGA上的实现进行详细的介绍,并将其性能参数与RU算 法、基于生成矩阵的编码算法进行比较。 第 40 页 第五章 高吞吐量 LDPC 码编码器的 FPGA 实现 第五章 高吞吐量 LDPC 码编码器的 FPGA 实现 上一章给出了基于二次扩展的QC-LDPC构造方法以及相应的新编码算法。本章将会 详细介绍新编码算法在FPGA上的实现细节,包括主要控制模块、功能模块以及存储模 块的设计。由于实现高吞吐量的主要基础是更平衡的流水线分级以及以准循环移位阵为 基本运算单位的并行运算,因此本章的重点在于描述硬件上如何进行并行计算,包括准 循环移位单位阵乘向量、准循环移位阵乘向量的并行计算,以及如何将每一个流水级消 耗的时钟数控制在zPEx×zCSEx。 本文实现的编码器支持的码字集合已在4.1.2 中给出,码字之间可以在线切换,即 在当前帧处理完毕后就能够从一种工作码字切换到另一种工作码字,从而确保不需要重 复多次配置 FPGA。 尽管本编码器可以在几乎只增加 ROM 资源的情况下进一步支持 2/3、4/5、5/6、6/7 等不同码率、不同码长的 LDPC 码,在这里给出支持 1/2、3/4、7/8 码率以及 2304、4608 码长的版本,这样的码长码率配置已经可以应用在多种通信系统中。 本章最后会给出新编码方法与RU算法以及基于生成矩阵的编码算法硬件实现的比 较,用实际结果证明在资源有限的情况下,本文提出的新编码方法是实现高吞吐量的有 效方法。 5.1 新编码器的 FPGA 硬件实现 5.1.1 编码器流水线分级细节 在传统的 RU 算法中,对编码器进行流水线分级的思想已经形成,然而由于 RU 算 法在很多地方不能轻易实现并行计算,因此图 3-2所示的流水线结构仍有着许多不足之 处。流水线分级的主要目的是提高处理事件的速度,通过将有明显先后顺序的几个事件 放在不同的流水级上先后处理,达到流水线连续运转的目的。然而,流水线并非分得越 细,效率越高,原因在于流水线之间一般需要引入存储模块,在存储的数据量较大的情 况下应该谨慎控制流水线级数。流水线处理事件的速度取决于流水级的瓶颈,也就是需 要最长时钟数完成的一级流水线。 图 4-4给出了新编码算法的流程图,大致对流水线进行了划分,这里给出更具体的 第 41 页 第五章 高吞吐量 LDPC 码编码器的 FPGA 实现 流水线结构图,见图 5-1。我们对主要的流水级进行了命名,分别是输入缓存、第一处 理缓存流水级、第二处理流水级、第三缓存流水级、第四处理缓存流水级和输出级。根 据上一章对主要功能模块的描述,可以先行对每一级流水线所需要的时钟数进行估计。 输入 缓存 缓存S 第一处 理缓存 流水级 第二处 理流水 级 第三缓 存流水 级 第四处 理缓存 流水级 输出级 信息帧 缓存S C CSIMV 缓存Cs Φ-1 VA ET-1AsCs CSDMV T-1A CSIMV 缓存 T-1As E CSIMV ET-1As 缓存p1 缓存p1 T-1B CSIMV T-1Bp1 VA 缓存p2 编码后码字 CWG 图5-1 新编码器详细流水线结构图 Fig.5-1 Detailed pipeline flow chart of new encoder implementation 首先考察输入缓存。由于新编码器的主要模块均以准循环移位阵为基本单位进行并 行计算,而第一处理缓存流水级中的矩阵 T-1A、C 分别由 dc-dv 个和 2×(dc-dv)个准循环 移位单位阵构成,因此要求信息比特一次输入 dc-dv 个,以满足 dc-dv 个准循环移位单位 阵乘向量模块并行计算的要求。鉴于第一处理缓存流水级对输入缓存的输出要求,为方 便起见,输入缓存对信息帧也有着相同的要求,由式(4-5)可知,输入缓存可以在 zPEx×zCSEx 个时钟周期内拿到一帧完整的数据。 考察第一处理缓存流水级。由4.2.2 可知,一个准循环移位单位阵乘向量的运算可 以在 zPEx×zCSEx 个时钟周期内完成,而这些组成矩阵 T-1A、C 的准循环移位单位阵之间 是并行计算的,因此,涉及矩阵 T-1A、C 与信息比特 s 的乘法可以在 zPEx×zCSEx 个时钟 周期内全部完成。注意到单个准循环移位单位阵乘向量的结果是通过 zPEx×zCSEx 个时钟 周期逐比特连续且立即输出的,因此此处采用位宽为 1,深度为 zPEx×zCSEx 的乒乓 RAM 缓存模块可以在上述 zPEx×zCSEx 个时钟周期内完成对所有结果的缓存,即第一处理缓存 流水级可以在 zPEx×zCSEx 个时钟周期内处理完毕。 考察第二处理流水级。同第一处理缓存流水级一样,涉及矩阵 E 的准循环移位单位 第 42 页 第五章 高吞吐量 LDPC 码编码器的 FPGA 实现 阵乘向量运算在 zPEx×zCSEx 个时钟周期内逐比特连续给出数据,经向量加法模块后在上 述 zPEx×zCSEx 个时钟周期内连续输出作为准循环移位阵乘向量运算的输入。由4.2.3 可知, 单个准循环移位阵乘向量运算可以在 zPEx×zCSEx 个时钟周期内完成,而组成矩阵ϕ −1 的准 循环移位阵之间是并行计算的,因此第二处理流水级可以在 zPEx×zCSEx 个时钟周期内处 理完毕。 考察第三缓存流水级。由于是为了第四处理缓存流水级和输出级作缓存,因此其存 储格式需要满足这两级对计算的要求。由于第四处理缓存流水级中矩阵 T-1B 是由两个 准循环移位单位阵组成的,并且校验比特 p1 的长度对应的准循环移位单位阵也是 2 块, 因此这里可以要求第二处理流水级在 zPEx×zCSEx 个时钟周期内并行逐比特输出 p1,从而 第三缓存流水级可以在上述的 zPEx×zCSEx 个时钟周期内缓存完毕。 考察第四处理缓存流水级。其前半部分与第二处理流水级的前半部分类似,之后只 需将向量加法模块逐比特输出,在 zPEx×zCSEx 个时钟周期内存入缓存即可,因此第四处 理缓存流水级可以在 zPEx×zCSEx 个时钟周期内处理完毕。 考察输出级。输出级是一个组帧的过程,由以上描述可知,信息比特 s、校验比特 p1 和 p2 的位宽分别为 dc-dv、2、1。由于在码字构造中固定 dv = 3,因此组帧后每个时钟 可以输出 dc 个比特,由式(4-5)可知,这样输出级可以在 zPEx×zCSEx 个时钟周期内输出完 毕。 因此,在新编码器中,每一级流水线所需的基本处理时间相等,为 zPEx×zCSEx 个时 钟周期,这样的流水线结构是非常理想的,编码延时仅约为 6×zPEx×zCSEx。 5.1.2 准循环移位单位阵乘向量模块 在4.2.2 中,已经简单介绍了准循环移位单位阵乘向量的计算方法,然而由于在实 际的计算中,所有参与该运算的矩阵都是由至少两块准循环移位单位阵组成,只是所有 的准循环移位单位阵之间都是并行计算而已,因此这一节将围绕准循环移位单位阵之间 如何在硬件上并行计算展开。 举例矩阵 T-1B 与向量 p1 相乘的例子。由基于二次扩展的 QC-LDPC 码构造可知, 由于限制校验矩阵的列重 dv = 3,因此矩阵 T-1B 是由两个准循环移位单位阵构成的,如 图 5-2所示。在与输入向量 p1 做乘法时,这两个准循环移位单位阵之间是并行计算的, 在这两个准循环移位单位阵内部是串行分块计算的。具体结构如图 5-3 所示。 第 43 页 第五章 高吞吐量 LDPC 码编码器的 FPGA 实现 b1 b5 b3 b6 b2 b4 图5-2 zPEx = 3 时矩阵 T-1B 示例 Fig.5-2 An example of matrix T-1B with zPEx = 3 存储T-1B信息 p11 ROM p12 p13 地址生成 p21 p22 p23 AND 图5-3 矩阵 T-1B 与向量 p1 相乘的硬件流程 Fig.5-3 Hardware flow chart of T-1B multiplied by p1 这里的输入向量 p1 在第四缓存流水级中由两对乒乓 RAM 进行存储,每一对乒乓 RAM 的深度是 zPEx×zCSEx,位宽为 1,负责存储长度为 zPEx×zCSEx 的 p1 的前后两部分向量。 当 T-1B 与向量 p1 的乘法使能时,首先计算循环移位单位阵 b1 和 b5 与 p1 的两个长度为 zCSEx 的子向量的乘法,它们分别是 p11 和 p22。由前述理论可知,循环移位单位阵乘向量 就是对向量进行循环上移。因此,通过从存储矩阵 T-1B 信息的 ROM 中读取第一个地址 数据,它包含两个地址,分别对应循环移位单位阵 b1 和 b5,每个地址包括高 log2(zPEx) 位(这里是“00”和“01”)表示 b1 和 b5 在准循环移位单位阵中的横向位置,低 log2(zCSEx) 位表示 b1 和 b5 的移位因子。以这两个地址作为初始地址分别读取向量 p11 和 p22 的 1 比 特,进行异或运算后就能够输出给后续的向量加法模块了。在之后的时钟到来时,上述 两个地址的低 log2(zCSEx)位按照模 zCSEx 循环加 1 计数,逐比特输出向量 p11 和 p22 的剩余 第 44 页 第五章 高吞吐量 LDPC 码编码器的 FPGA 实现 (zCSEx-1)比特,分别进行异或运算后输出给后续的向量加法模块,直到第 zCSEx 个时钟 到来时,循环移位单位阵 b1 和 b5 与向量 p11 和 p22 的乘法完成。在第(zCSEx+1)个时钟到 来时,从存储矩阵 T-1B 信息的 ROM 中读取第二个地址数据(它同样包含两个地址,分 别对应循环移位单位阵 b3 和 b6),以这两个地址作为初始地址分别读取向量 p13 和 p23 的 1 比特,进行异或运算后输出给后续的向量加法模块。在之后的时钟到来时,上述两个 地址的低 log2(zCSEx)位按照模 zCSEx 循环加 1 计数,逐比特输出向量 p13 和 p23 的剩余(zCSEx -1)比特,分别进行异或运算后输出给后续的向量加法模块,直到第(2×zCSEx)个时钟到 来时,循环移位单位阵 b3 和 b6 与向量 p13 和 p23 的乘法完成。在第(2×zCSEx+1)个时钟到 来时,从存储矩阵 T-1B 信息的 ROM 中读取第三个地址数据(它也包含两个地址,分别 对应循环移位单位阵 b2 和 b4),以这两个地址作为初始地址分别读取向量 p12 和 p21 的 1 比特,进行异或运算后输出给后续的向量加法模块。在之后的时钟到来时,上述两个地 址的低 log2(zCSEx)位按照模 zCSEx 循环加 1 计数,逐比特输出向量 p12 和 p21 的剩余(zCSEx -1)比特,分别进行异或运算后输出给后续的向量加法模块,直到第 zPEx×zCSEx 个时钟到 来时,循环移位单位阵 b2 和 b4 与向量 p12 和 p21 的乘法完成。于是矩阵 T-1B 与向量 p1 的乘法在 zPEx×zCSEx 个时钟周期内完成。 从上述结合硬件流程图的描述可见,基于二次扩展的构造方法带来的准循环移位单 位阵的结构是很有优势的。由于它的行重、列重均为 1,因此可以保证在每一个时刻中, 每个准循环移位单位阵中有且只有一个循环移位单位阵参与和向量的运算。这样在 zPEx×zCSEx 个时钟周期内,zPEx 个循环移位单位阵可以串行完成与相应部分向量的乘法, 且保证每个时钟每个准循环移位单位阵只输出一个比特,将所有同一行上并行运算的准 循环移位单位阵输出的这一个比特作异或就能够获得目标向量的一位。由于我们总可以 控制目标向量长度保持在 zPEx×zCSEx,(否则可以将目标向量分为长度为 zPEx×zCSEx 的几段 分开并行计算),因此涉及矩阵 T-1A、T-1B、C、E 的所有准循环移位单位阵乘向量运算 都能够在 zPEx×zCSEx 个时钟周期内完成,并且这些操作所需要的硬件资源只是几个读地 址、异或门、基本是可以忽略不计的。 当码字在线切换时,只需要从存储矩阵 T-1B 信息的 ROM 中不同地址读取相应码字 对应的初始地址即可。 5.1.3 准循环移位阵乘向量模块 在4.2.3 中,简单说明了准循环移位阵乘向量运算可以分块运算,即分解成循环移 位阵乘向量运算,然而并没有具体讲述分块计算之间是如何协调的。在实际的计算中, 第 45 页 第五章 高吞吐量 LDPC 码编码器的 FPGA 实现 ϕ −1 至少由 4 块准循环移位阵组成,所有的准循环移位阵之间仍然采用并行计算,由于 每一个准循环移位阵内部所有的循环移位阵都需要参与与向量的乘法运算,比准循环移 位单位阵中参与乘法运算的循环移位单位阵的数量要大 zPEx 倍,因此为了能够和准循环 移位单位阵有相同的计算速度,需要 zPEx 倍更多的计算单元并行计算。这一节将围绕准 循环移位阵内部与相互之间如何在硬件上实现并行计算展开。 举 例 矩 阵 ϕ −1 与 向 量 (−ET −1A + C)sT 相 乘 的 例 子 , 为 说 明 简 单 起 见 , 将 向 量 (−ET −1A + C)sT 记作向量 x。由基于二次扩展的 QC-LDPC 码构造可知,限制校验矩阵的 列重 dv = 3,因此矩阵ϕ −1 是由 2×2 个准循环移位阵构成的,如图 5-4所示。在与长度为 2×zCSEx 的输入向量 x 做乘法时,这四个准循环移位阵之间是并行计算的,在这四个准循 环移位阵内部结合了串、并行的分块计算。 再次考察图 4-7、图 4-8给出的按行置入和按列置入的循环移位阵乘向量实现模块 图。硬件实现上选择按列置入主要有以下两个原因:其一,上一个运算步骤向量加法的 运算结果是逐比特输出的,如果按行置入的话需要级联一个缓存;其二,在一个时钟内 完成 zCSEx 个比特的模 2 加法不如只完成一次模 2 加法运算简单。图 5-5给出了按列置入 的循环移位阵乘向量硬件结构图。 矩阵ϕ −1 a11 a12 a13 c11 c12 c13 a21 a22 a23 c21 c22 c23 a31 a32 a33 c31 c32 c33 b11 b12 b13 d11 d12 d13 b21 b22 b23 d21 d22 d23 b31 b32 b33 d31 d32 d33 向量x x1 x2 图5-4 zPEx = 3 时矩阵ϕ −1 示例 Fig.5-4 An example of matrix ϕ −1 with zPEx = 3 第 46 页 第五章 高吞吐量 LDPC 码编码器的 FPGA 实现 xi 1 XOR 长度为zCSEx的循环移位寄存器A …… 2 …… zCSEx XOR …… XOR XOR …… 长度为zCSEx的寄存器B 图5-5 按列置入的循环移位阵乘向量硬件结构 Fig.5-5 Structure of QC matrix multiplied by vector through columns 由于之前的向量加法模块是按照准循环移位阵的大小并行化的,因此事实上有两个 加法器同时在处理长度为 zPEx×zCSEx 的逐比特输入的向量,因此这里的输入向量 x 可以 被分为长度为 zPEx×zCSEx 的前后两段,记作 x1,x2。硬件初始化时,将所有如图 5-5所示 的计算单元中寄存器 B 复位。当ϕ −1 与输入向量 x 的乘法使能时,首先将循环移位阵 a11、 a21、a31,b11、b21、b31,c11、c21、c31,d11、d21、d31 的第一列分别置入 12 个计算单元的 循环移位寄存器 A 中,此时向量 x1、x2 的第一个比特从向量加法模块中同时输出,它 们分别逐个与先前存入 12 个循环移位寄存器 A 的所有比特逐个相与后,再将结果与 12 个寄存器 B 分别相异或,(注意到此时寄存器 B 中的所有寄存器值均为 0),将得到的结 果分别存入 12 个寄存器 B。在之后的时钟到来时,12 个循环移位寄存器 A 逐比特循环 右移,向量 x1、x2 逐比特从向量加法模块中输出,它们分别逐个与 12 个循环移位寄存 器 A 的所有比特逐个相与后,再将结果与 12 个寄存器 B 分别相异或,将得到的中间结 果分别存入 12 个寄存器 B 中。直到第 zCSEx 个时钟到来时,涉及循环移位阵 a11、a21、 a31,b11、b21、b31,c11、c21、c31,d11、d21、d31 的乘法完成,将循环移位阵 a12、a22、a32, b12、b22、b32,c12、c22、c32,d12、d22、d32 的第一列分别置入上述 12 个计算单元的循环 移位寄存器 A 中,重复上述过程。直到第 2×zCSEx 个时钟到来时,涉及循环移位阵 a12、 第 47 页 第五章 高吞吐量 LDPC 码编码器的 FPGA 实现 a22、a32,b12、b22、b32,c12、c22、c32,d12、d22、d32 的乘法完成,将循环移位阵 a13、a23、 a33,b13、b23、b33,c13、c23、c33,d13、d23、d33 的第一列分别置入上述 12 个计算单元的 循环移位寄存器 A 中,重复上述过程,直到第 zPEx×zCSEx 个时钟到来时,涉及矩阵ϕ −1 的 乘法完成,此时将上述 6 个对应 a、b 的计算单元中寄存器 B 的值与另外 6 个对应 c、d 的计算单元中寄存器 B 的值逐比特异或后拼接起来就得到目标向量 p1。 从 上 述 算 法 描 述 可 见 , 完 成 整 个 矩 阵 ϕ −1 与 向 量 (−ET −1A + C)sT 的 乘 法 只 需 要 zPEx×zCSEx 个时钟数,这对于编码器的吞吐量是有着积极影响的。由于基于生成矩阵的编 码算法是非常灵活的,可以采用串行、并行乃至全并行的结构,这里为了保持和准循环 移位单位阵乘向量有着相同的计算速度,采用并行的结构,比起串行结构而言牺牲了一 定的硬件资源,对吞吐量有相比串行结构有着 zPEx 倍的提升,因此这种折中是可以接受 的。这里需要指出的是,由于准循环移位阵乘向量运算消耗了整个编码器所需的大多数 ROM 和寄存器资源,如果矩阵ϕ −1 可以人为地确定成单位阵或者某种规则的结构(如由 准循环移位单位阵构成),那将大大降低整个编码器对 ROM 和寄存器资源的需求。 5.1.4 向量缓存模块 图 5-1中有很多存储信息比特、校验比特以及其他中间向量的存储器,这些存储器 一般是通过乒乓 RAM 实现的。由于编码算法中所有的计算都是以循环移位阵的大小为 单位并行进行的,因此一般要求向量缓存模块也将向量分成长度为 zPEx×zCSEx 的段进行 存储,直接传给输出级的缓存除外。 因此,这里的缓存可以分为两种,一种仅由两块 RAM 乒乓而成,另一种是对应输 出级的缓存,通常称为循环缓存,它与一般乒乓 RAM 唯一不同的地方是参与“乒乓” 的 RAM 数量大于 2。 上述两种 RAM 分别存在于输入缓存中,其中 6 块深度为 zPEx×zCSEx,位宽为(dc-dv) 的循环缓存对信息比特 s 进行帧一级的 FIFO 操作,以确保它与相应的校验比特 p1、p2 同时传递给输出级。另外输入缓存将信息比特 s 按照长度 zPEx×zCSEx 进行分割,分别存储 在 zPEx 个深度为 zCSEx、位宽为 1 的乒乓 RAM 中,每(dc-dv)对这样的乒乓 RAM 联合存 储一份信息比特 s。根据流水级需要,一共有(dv+1)份信息比特 s 被存储在输入缓存中。 第一处理缓存流水级中,将向量 T-1AsT 按照长度 zPEx×zCSEx 进行分割,分别存储在 zPEx 个深度为 zCSEx、位宽为 1 的乒乓 RAM 中,将 CsT 按照长度 zPEx×zCSEx 进行分割,分 第 48 页 第五章 高吞吐量 LDPC 码编码器的 FPGA 实现 别存储在(dv-1)对深度为 zPEx×zCSEx、位宽为 1 的乒乓 RAM 中,另外使用 4 块深度为 zPEx×zCSEx、位宽为 1 的 RAM 对向量 T-1AsT 进行帧意义上的 FIFO 操作以确保 T-1AsT 与 相应的校验比特 p1 同步传递给第四处理缓存流水级。 第三缓存流水级中,使用 3 块深度为 zPEx×zCSEx、位宽为 2 的 RAM 对校验比特 p1 进行帧意义上的 FIFO 操作以确保校验比特 p1 与相应的信息比特 s、校验比特 p2 同步传 递给输出级,另外还将校验比特 p1 按照长度 zPEx×zCSEx 进行分割,分别存储在 zPEx 个深 度为 zCSEx、位宽为 1 的乒乓 RAM 中。这样一共有 2 份校验比特 p1 被存储在第三缓存流 水级中。 第四处理缓存流水级中,使用一对深度为 zPEx×zCSEx、位宽为 1 的乒乓 RAM 存储校 验比特 p2。 5.1.5 码字生成模块 这里的码字生成模块不同于 RU 算法相应的模块,RU 算法由于在预处理中对校验 矩阵 H 进行了列交换,相当于对编码后的码字 c 作了一次列交换,因此需要在码字生成 模块将码字 c 交换回去,以使译码器正确译码。然而基于二次扩展的 QC-LDPC 构造方 法在构造时已经加入了足够的约束,使得编译码过程中使用的是相同的校验矩阵,从而 无需对码字 c 进行列交换。这里的码字生成模块只需要将信息比特 s、校验比特 p1 和 p2 组装起来即可。如果后续模块有需要的话,也可以在这里对输出接口进行定义。 5.1.6 支持不同码长和码率的灵活性 在4.2.4 中,说明了本次实现固定循环移位扩展因子 zCSEx = 32 不变,再由5.1.2 和 5.1.3 可知,最基本的循环移位单位阵乘向量和循环移位阵乘向量的硬件结构基本只和 循环移位扩展因子 zCSEx 有关,因此在通过变动母矩阵或者乱序扩展因子 zPEx 改变码长、 码率时,所需要的只是更宽的读地址(准循环移位单位阵乘向量)或者更多的并行计算 单元,以满足更多的并行计算即可。 在码率不变的情况下(母矩阵不变),可以通过改变乱序扩展因子 zPEx 改变码长。 此时准循环移位(单位)阵的数量并没有变化,仍然为 dv×dc 个。对于准循环移位单位 阵乘向量来说,只需要将读地址高位位宽相应增加到 log2(zPEx)即可,一般随着 zPEx 增加 一倍,位宽只需要增加 1 位即可。对于准循环移位阵乘向量,由于准循环移位阵的数量 没有改变,因此只是在内部增加了 zPEx 倍的如图 5-5所示的计算单元。 在码长不变的情况下,可以通过改变母矩阵和乱序扩展因子 zPEx 来改变码率,只要 第 49 页 第五章 高吞吐量 LDPC 码编码器的 FPGA 实现 符合式(4-5)的约束就行。此时准循环移位(单位)阵的数量随着 dv×dc 的增加而增加。 对于准循环移位单位阵乘向量来说,需要增加相应的计算单元,但是相应增加的资源消 耗是几乎可以忽略不计的。对于准循环移位阵乘向量,由于准循环移位阵的数量没有改 变,因此只是在内部增加了 zPEx 倍的如图 5-5所示的计算单元。 事实上,一般的二次扩展方法是,先利用母矩阵确定码率,再利用乱序扩展因子 zPEx 确定码长。因此,在为最大的 zPEx 预留最大的读地址,以及为最高的码率预留最多的并 行计算单元,就能够支持表 4-1中所有其他的码长、码率。 从5.1.4 来看,在硬件实现上,向量缓存模块只需要为最大的乱序扩展因子 zPEx 预 留足够的空间即可。 5.1.7 编码器的封装与接口 为了使编码器内部也有比较标准的模块和接口,需要对5.1.1 所述的六级流水线进 行封装,为了方便起见,输入级的循环缓存可以自成一级,独立于上述六级流水线之外。 分析这几级流水线各自的特点,可以发现它们从功能上大致可以分为计算和存储两种, 因此先统一最大输入输出接口的集合,然后再根据每一级的情况从中选择接口应该是切 实可行的方法。 图 5-6给出了流水线的标准输入输出接口集,以下每一级流水线不允许引入另外的 接口定义。表 5-1给出了输入输出接口的详细定义,由于位宽随不同流水线而有所差异, 因此这里没有给出具体位宽。 Clk Reset iBlkEn iCodeSel iData oRdAddr oRdSel Stage n oOutputEn oData iRdAddr iRdSel 图5-6 新编码器流水线标准输入输出接口集 Fig.5-6 Standard I/O interface of pipeline stages of proposed encoder algorithm 第 50 页 第五章 高吞吐量 LDPC 码编码器的 FPGA 实现 表5-1 新编码器流水线标准输入输出接口定义 前级互连 后级互连 信号名称 Clk Reset iBlkEn iCodeSel iData oOutputEn oRdAddr oRdSel iRdAddr iRdSel oData 功能定义 时钟信号 复位信号 使能信号 码字选择信号 数据输入信号 输出使能信号 输出地址信号 输出片选信号 输入地址信号 输入片选信号 输出数据信号 输入/输出 输入 输入 输入 输入 输入 输出 输出 输出 输入 输入 输出 新编码器所有流水级间的互连如图 5-7所示。整个编码器封装后的接口如图 5-8所 示。更具体的硬件细节这里就不再展开了。 第 51 页 第五章 高吞吐量 LDPC 码编码器的 FPGA 实现 Clk Reset iBlkEnS iCodeSel iDataS oDataS iRdAddrS iRdSelS Stage S Clk Reset iBlkEn5 oOutputEn5 iCodeSel iData5 oRdAddr5 oRdSel5 oData5 iRdAddr5 iRdSel5 Stage 5 Clk Reset iBlkEn6 iCodeSel iData6 oRdAddr6 oRdSel6 oData6 Stage 6 Clk Reset iBlkEn3 oOutputEn3 iCodeSel iData3 oRdAddr3 oRdSel3 oData3 Stage 3 Clk Reset iBlkEn4 oOutputEn4 iCodeSel iData4 oData4 iRdAddr4 iRdSel4 Stage 4 Clk Reset iBlkEn1 oOutputEn1 Clk Reset iBlkEn2 oOutputEn2 iCodeSel iData1 oData1 iRdAddr1 iRdSel1 Stage 1 iCodeSel iData2 oRdAddr2 oRdSel2 oData2 iRdAddr2 iRdSel2 Stage 2 图5-7 新编码器流水线级间互连示意图 Fig.5-7 Illustration of interconnection between pipeline stages 第 52 页 第五章 高吞吐量 LDPC 码编码器的 FPGA 实现 Clk Reset iBlkEn iCodeSel iData oOutputEn oData 图5-8 新编码器的对外接口 Fig.5-8 Interface of the proposed encoder 5.2 新编码器的综合评估 5.2.1 资源消耗 本文提出的新编码器所支持的码字集合如表 4-1所示,该码字集合包括两种码长和 各自分别对应的三种码率。由于考虑到译码器的可实现性,我们固定循环移位扩展因子 zCSEx = 32 不变,通过调节乱序扩展因子 zPEx 来实现对码长码率的控制。而从5.1.2 和5.1.3 中可知,这样做的代价就是在增加码率或者 zPEx 时相应增加计算模块。由于此次编码器 实现支持的 zPEx 从 3 到 24 不等,码率跨度也非常大,因此所有的计算单元都是为了 zPEx = 24 或 7/8 码率预留的。尽管在 zPEx = 3 或者 1/2 码率时有足够多的计算模块可供调配, 但是也会有部分资源空闲,因此从某些意义上来讲,并非每个时刻所有模块都在全力工 作的。 除了5.1.2 和5.1.3 涉及的计算模块外,其他的资源主要包括 ROM 和5.1.4 所述的 RAM。从5.1.4 的叙述中可知,很多 RAM 的深度和 zPEx×zCSEx 成正比,因此这些 RAM 的最大深度需要为 zPEx = 24 预留。ROM 资源主要用在存储矩阵ϕ −1 上,由于ϕ −1 总是由 四个准循环移位阵组成的,因此 ROM 资源的大小和 zPEx×zCSEx 相关,zPEx = 24 对应的那 个码使用的 ROM 资源几乎占到所有 ROM 资源的一半。 在 Xilinx Virtex II pro 70 上的实现结果表明,单个编码器使用了 25%的 slice 和 44% 的 Block RAM,因此一块这样的 FPGA 完全可以放得下两个编码器。 第 53 页 第五章 高吞吐量 LDPC 码编码器的 FPGA 实现 5.2.2 性能指标 基于二次扩展的 QC-LDPC 码编码器的各项性能指标如表 5-2所示,衡量编码器的 主要性能指标有编码延时、净吞吐量等。由于工作频率高低会影响上书性能指标,因此 这里将编码器工作频率 f(MHz)作为参数使用。 表5-2 基于二次扩展的 QC-LDPC 码编码器的性能指标 码长 码率 行重 列重 乱序扩展因子 循环移位因子 编码延时 吞吐量 N R dv dc zPEx 2304 7/8 24 3 3 zCSEx Clock Mbps 32 576 21f 2304 3/4 12 3 6 2304 1/2 6 3 12 32 1152 9f 32 2304 3f 4608 7/8 24 3 6 4608 3/4 12 3 12 32 1152 21f 32 2304 9f 4608 1/2 6 3 24 32 4608 3f 5.3 与现有编码算法的比较 由于新的编码算法是结合了 RU 算法以及基于生成矩阵的编码算法,因此我们可以 和这两种编码算法稍作一下对比。但是,即使是对相同的码字进行编码,也很难保证对 比的结果有意义,这是因为每一种编码方法都是和校验矩阵的构造密切相关的,一种校 验矩阵一般只能适合一种编码方法。另外,考虑到某些编码器结构尽管可能稍显复杂, 但是在支持码长、码率的灵活性上可能更胜一筹,因此我们一般很难准确定量地描述各 种编码方法的优缺点。在此我们仅在最大码长、最低码率相同的情况下,对三种编码算 法在 Xilinx Vertex II pro 70 FPGA 上的资源消耗和性能进行比较,结果如表 5-3所示。其 中 FPGA 工作时钟为 100Mbps。 第 54 页 第五章 高吞吐量 LDPC 码编码器的 FPGA 实现 表5-3 新编码算法与现有算法的比较 算法 资源消耗 Block RAM Slice 支持码字 编码延时 净吞吐量 支持码率 (时钟数) (Mbps) RU 算法 26% 22% ( 4608, 2304 ) 1/2 36072 46 ( 2304, 1152 ) 1/2 1152 300 ( 4608, 2304 ) 1/2 2304 300 G 矩阵乘 18% ( 2304, 1728 ) 3/4 70% 576 900 ( 4608, 3456 ) 3/4 1152 900 ( 2304, 2016 ) 7/8 288 2100 ( 4608, 4032 ) 7/8 576 2100 ( 2304, 1152 ) 1/2 2304 300 ( 4608, 2304 ) 1/2 4608 300 新算法 ( 2304, 1728 ) 3/4 44% 25% 1152 900 ( 4608, 3456 ) 3/4 2304 900 ( 2304, 2016 ) 7/8 576 2100 ( 4608, 4032 ) 7/8 1152 2100 从上表我们可以对这三种算法有一个进一步的认识。 RU 算法很难支持自适应 LDPC 编码,因此即使已经支持了某种最长码长、最低码 率的码,在此基础上要进一步支持短码长、高码率的码其实和新做一个编码器的资源消 耗相差不多。另外由于 RU 算法的流水级过多且分配不均衡,因此吞吐量较低、编码延 时较长。 基于生成矩阵的编码算法和新编码算法可以作一个较好的比较,因为它同样能够支 持和新算法完全一样的码字集合。然而,基于生成矩阵的算法不仅消耗的 slice 资源和 Block RAM 资源严重不平衡,并且很难用 Block RAM 来代替那些 slice,原因在于基于 生成矩阵的算法需要使用的大量寄存器本身不能够用 Block RAM 代替。因此,在需要 更高吞吐量的场合就不能够使用这种编码算法。 新编码算法只有 4 个准循环移位阵是通过类似基于生成矩阵的编码算法实现的,相 比基于生成矩阵的编码算法的 9 个可以节省至少一半的 slice 资源,ROM 资源消耗的情 况也是类似的,至少省下了一半的 ROM,但是从表 5-3来看,Block RAM 的资源消耗反 而增加了,这是因为实现时很多可以用 slice 的地方都用 Block RAM 代替了,为的是省 下 slice 方便布局布线以及提高时钟频率。如果将这些 Block RAM 用 slice 来取代的话, 新编码器的资源消耗应该是 25%的 Block RAM 和 35%的 slice。新编码算法相对于基于 第 55 页 第五章 高吞吐量 LDPC 码编码器的 FPGA 实现 生成矩阵的编码算法最大的不足之处在于增加了一些编码延时,但是相比 RU 算法的编 码延时几乎是可以忽略不计的。 综上所述,在需要很高吞吐量的场合,新编码算法有着很强的竞争力。 5.4 本章小结 本章详细介绍了基于二次扩展的 QC-LDPC 码的编码实现,之后给出了它与基于其 它算法的编码器之间的比较。 这里首先介绍了编码器的详细框架,在此基础上描述了其中两种最主要的计算—— 准循环移位单位阵乘向量、准循环移位阵乘向量的具体实现,之后对于同样比较重要的 向量缓存模块和码字生成模块作了简单的介绍,最后给出了编码器流水级间的封装以及 对外的接口。 由于编码器是在具体硬件 FPGA 上实现的,因此这里给出了编码器的资源消耗和实 现的具体性能参数。在此基础上,为了研究新编码方法相对 RU 算法和基于生成矩阵编 码算法的定量优势,又在相同的 FPGA 上使用基于生成矩阵的编码算法,实现了相同码 字的编码,发现新编码方法通过用 4 块准循环移位阵代替原先的 9 块准循环移位阵大量 地节省了寄存器和 ROM 的硬件资源,因此是对基于生成矩阵编码算法的显著改进。由 于 RU 算法本身不适合支持可变码长、可变码率,因此仅在相同的 FPGA 上实现了最长 码长、最低码率的 RU 编码器,证实了 RU 算法编码延时大、吞吐量低的缺点。因此在 需要实现高吞吐量编译码器的情况下,新编码算法是一种理想的选择。 第 56 页 第六章 全文总结 第六章 全文总结 6.1 主要创新点 本文在结合了 RU 算法和基于生成矩阵的编码算法以后,在一种基于二次扩展的 QC-LDPC 构造基础上,给出了一种新的编码器结构,以实现高吞吐量的 LDPC 编译码。 新编码器的主要结构仍然基于 RU 算法,但是它通过在校验矩阵引入循环移位结构 后将 RU 算法大大简化,彻底抛弃了 RU 算法中串行的前向替换模块。新编码器不但将 流水线级数从 RU 算法的 6 级降到了现在的 4 级,并且将所有流水级所消耗的时钟数控 制在几乎相等的范围内,进一步减少了编码时延,提高了吞吐量。其中在涉及准循环移 位阵乘向量的部分引入了基于生成矩阵的编码方法,大大提高了计算并行度,从而解决 了 RU 算法限制吞吐量的两大障碍。 新编码器在对码长、码率的自适应能力上可以和基于生成矩阵的编码算法媲美,然 而它可以通过将准循环移位阵的数量从 9 个降到 4 个,使 ROM 和寄存器资源的使用降 低了一半以上,由于它不再依赖于大量的寄存器结构,因此可以在一块 FPGA 上实现两 个编码器并行工作。相比 RU 算法,不但提升了吞吐量,缩短了编编码延时,更重要的 是灵活地实现了可变码长、可变码率的自适应编码。 本文最后给出了在 FPGA 上实现该编码器的详细流程。从性能仿真的结果来看,这 种基于二次扩展的 QC-LDPC 码具有较高的实用价值。 6.2 进一步研究的方向 本文提出的基于二次扩展的 QC-LDPC 构造方法和基于此的新编码器结构能够实现 高吞吐量的 LDPC 码编译码要求,硬件复杂度相对 RU 算法和基于生成矩阵的算法较低, 但是相对于某些基于单次扩展的重复累积码编码方法来说就比较高了。因此,如何进一 步降低本编码器的实现复杂度可以是一个研究方向。这一点主要可以从ϕ −1 的简化上去 考虑,理想情况下的ϕ −1 应该是单位阵。 基于单次扩展的重复累积码编译码器都比较容易实现,但是码的性能不能够保证, 第 57 页 第六章 全文总结 原因在于校验矩阵中存在过多的列重为 2 的节点。因此为了提升这类码的性能,近来有 学者提出将基矩阵中的双对角线结构改为三对角线结构,此时的译码算法不会有较大的 改变。因此上述两类码的性能与编码复杂度之间的折中也是人们比较关心的问题。 信源、信道乃至考虑到调制的联合编解码一直是人们热衷研究的对象,如果可以将 两次编解码过程合并在一次进行,就能够大大降低整体系统中硬件资源的消耗。但是由 于信源、信道编码的出发点不同,因此如何将两者协调起来是一个需要进一步研究的课 题。 在解决了上述问题后,相信 LDPC 码的未来会越来越光明,它一定能够在现实生活 中得到进一步的应用。 第 58 页 参考文献 参考文献 [1] C. Berrou, A. Glavieux, and P. Thitimajshima, “Near shannon limit error-correcting coding and decoding: Turbocodes”, in Proc. of ICC’93, pp. 1064–1070, Geneve, Switzerland, May 1993. [2] C. Berrou and A. Glavieux, "Near-optimum error-correcting coding and decoding: Turbo Codes," IEEE Trans. Commun., vol. 44, pp. 1261-1271, Oct, 1996. [3] P. H. Siegel, D. Divsalar, E. Eleftheriou, J. Hagenauer, D. Rowitch, and W. H. Tranter, “The turbo principle: From theory to practice,” IEEE J. Select. Areas Commun. , vol. 19, pp. 793–799, May 2001. [4] R. G. Gallager, Low-Density Parity-Check Codes. Cambridge, MA: MIT Press, 1963. Available at http://justice.mit.edu/people/gallager.html [5] R. G. Gallager, “Low-density parity-check codes”, IRE Transactions on Information Theory, vol. IT-8, pp. 21–28,Jan. 1962. [6] G. A. Margulis, “Explicit construction of graphs without short cycles and low density codes,” Combinatorica, vol. 2, no. 1, pp. 71–78, 1982. [7] R. Tanner, “Arecursive approach to low complexity codes,” IEEE Trans. Inform. Theory, vol. IT-27, pp. 533–547, Sept. 1981. [8] V. Zyablov and M. Pinsker, “Estimation of the error-correction complexity of Gallager low-density codes,” Probl. Pered. Inform. , vol. 11,pp. 23–26, Jan. 1975. [9] D. J. C. MacKay, “Good error-correcting codes based on very sparse matrices”, IEEE Transactions on Information Theory, vol. 45, pp. 399–431, Mar. 1999. [10] D. J. C. MacKay and R. M. Neal, “Near Shannon limit performance of low density parity check codes”, Electronics Letters, vol. 32, pp. 1645–1646, Aug. 1996. [11] N. Wiberg, “Codes and decoding on general graphs”, Ph.D. Dissertation, Linkoping University, Sweden, 1996. Available at http://www.essrl.wustl.edu/˜jao/itrg2000/. [12] M. Luby, M. Mitzenmacher, A. Shokrollahi, D. Spielman, and V. Stemann, “Practical loss-resilient codes,” in Proc. 29th Annual ACM Symp. Theory of Computing, 1997, pp. 150–159. [13] M. Luby, M. Mitzenmacher, A. Shokrollahi, and D. Spielman, “Analysis of low density 第 59 页 参考文献 codes and improved designs using irregular graphs,” in Proc. 30th Annu. ACM Symp. Theory of Computing, 1998, pp. 249–258. [14] Jilei Hou; Siegel, P.H.; Milstein, L.B., “Performance analysis and code optimization of low density parity-check codes on Rayleigh fading channels,”, Selected Areas in Communications, IEEE Journal on , Volume: 19 Issue: 5 , May 2001 Page(s): 924 -934. [15] Futaki, H.; Ohtsuki, T. “Performance of low-density parity-check (LDPC) coded OFDM systems,” Communications, 2002. ICC 2002. IEEE International Conference on , Volume: 3 , 2002 .Page(s): 1696 -1700 vol.3 [16] Futaki, H.; Ohtsuki, T. “Low-density parity-check (LDPC) coded OFDM systems,” Vehicular Technology Conference, 2001. VTC 2001 Fall. IEEE VTS 54th, Volume: 1, 2001 .Page(s): 82 -86 vol.1 [29] Futaki, H.; Ohtsuki, T. “Low-density parity-check (LDPC) coded OFDM systems with M-PSK,” Vehicular Technology Conference, 2002. VTC Spring 2002. IEEE 55th , Volume: 2 , 2002 .Page(s): 1035 -1039 vol.2 [17] T. Richardson, A. Shokrollahi, and R. Urbanke, “Design of capacity-approaching low-density parity check codes,” IEEE Trans. Inform. Theory, vol. 47, pp. 619–637, Feb. 2001. [18] Y. Kou, S. Lin, and M. Fossorier, “Construction of low density parity check code: a geometric approach”, in Proceedings of the 2nd International Symposium on Turbo Codes and Related Topics, pp. 137–140, Brest, France,Sept. 2000. [19] J. Lafferty and D. Rockmore, “Codes and iterative decoding on algebraic expander graphs”, in International Symposium on Information Theory and its Application, Honolulu, Hawaii, 2000. Availabel at http://www.cs.cmu.edu/˜lafferty/. [20] Y. Mao and A. Banihashemi, “Design of good LDPC codes using girth distribution”, in IEEE International Symposium on Information Theory, Italy, June 2000. [21] E. Boutillon, J. Castura, and F. R. Kschischang, “Decoder-first code design”, in Proceedings of the 2nd International Symposium on Turbo Codes and Related Topics,pp.459–462,Brest,France,Sept.2000. Available at http://lester.univ-ubs.fr:8080 /˜boutillon/publications.html. [22] D.Divsalar, Hui Jin, R.McEliece. “Coding theorems for Turbo-like codes”, in Proceedings of the 1998 Allerton Conference, 1998: pp. 201-210 [23] Hui Jin, A.Khandekar, R.McEliece. “Irregular repeat-accumulate codes”, Proc. 2nd International Symposium on Turbo Codes, 2000: pp. 1-8. 第 60 页 参考文献 [24] Richardson, T.J.; Urbanke, R.L., “Efficient encoding of low-density parity-check codes”, IEEE Transactions on Information Theory, Volume: 47 Issue: 2 , Feb 2001 Page(s): 638 -656. [25] D. J. C. MacKay, S. T. Wilson, and M. C. Davey, “Comparison of constructions of irregular Gallager codes,” in Proc. 36th Allerton Conf. Communication, Control, and Computing, Sept. 1998. [26] Zongwang Li, Lei Chen and Shu Lin, “Efficient Encoding of Quasi-Cyclic Low-Density Parity-Check Codes”, IEEE Transanctions on Communications, Volume: 54 No. 1 pp. 71-81, Jan, 2006 [27] Mohamed Shaqfeh, Norbert Goertz, “Systematic Modification of Parity-Check Matrices for Efficient Encoding of LDPC Codes”, ICC 2007 [28] Y. Kou, S. Lin, and M. P. C. Fossorier, “Low-density parity-check codes based on finite geometries: A rediscovery and new results,” IEEE Trans. Inform. Theory, vol. 47, pp. 2711–2736, Nov. 2001. [29] Ahmed Nouh,and Amir H.Banihashemi, “Bootstrap decoding of low-density parity-check codes,” IEEE COMMUNICATIONS LETTERS,vol.6,NO.9,Sep 2002. [30] C. Howland and A. Blanksby, “Parallel decoding architectures for low density parity check codes”, in Proc. of 2001 IEEE Int. Symp. on Circuits and Systems, Sydney, May 2001. [31] Levine, B.; Reed Taylor, R.; Schmit, H., “Implementation of near Shannon limit error-correcting codes using reconfigurable hardware,”, Field-Programmable Custom Computing Machines, 2000 IEEE Symposium on , 17-19 April 2000 Page(s): 217 -226 [32] T. Zhang, Z. Wang, and K. K. Parhi, “On finite precision implementation of low-density parity-check codes decoder”, in Proc. of 2001 IEEE Int. Symp. on Circuits and Systems, Sydney, May 2001. Available at http://www.ece.umn.edu/groups/ddp/turbo/. 第 61 页 附录一 英语缩略语对照表 英语缩略语 AWGN BEC BER BPA BPSK BSC CSDMV CSEx CSI CSIMV CSM CWG DE DEx DVB-S2 FER FPGA FS IEEE LDGM LDPC LLR LMMSA MPA 附录一 英语缩略语对照表 英语全称 Additive White Gaussion Noise Binary Erasure Channel Bit Error Rate Belief Proporgation Algorithm Binary Phase Shift Keying Binary Symmetry Channel Cyclic Shift Dense Matrix Vector ( Multiplication ) Cyclic Shift Expansion Cyclic Shift Identity Cyclic Shift Identity Matrix Vector ( Multiplication ) Cyclic Shift Matrix Code Word Generation Density Evolution Duplex Expansion Digital Video Broadcasting-Satellite 2 Frame Error Rate Field Programmable Gate Array Forward Substitution Institute of Electrical and Electronics Engineers Low Density Generation Matrix Low Density Parity Check (Code) Log-Likelihood Ratio Layered Minimum-Sum Algorithm Message Passing Algorithm 中文对照 加性高斯白噪声 二进制擦除信道 误比特率 置信传播算法 二进制相移键控 二进制对称信道 准循环移位阵乘向量 循环移位扩展 循环移位单位阵 准循环移位单位阵乘向量 循环移位阵 码字生成 密度演化 二次扩展 欧洲第二代卫星数字视频广 播标准 误帧率 现场可编程门阵列 前向替换 电气电子工程师协会 低密度生成矩阵 低密度奇偶校验(码) 对数似然比 分层的最小和算法 信息传递(译码)算法 第 62 页 MSA MMSA PEG PEx RA SS QC QCI QCM QC-LDPC SNR TPC VA 附录一 英语缩略语对照表 Minimum-Sum Algorithm Modified Minimum-Sum Algorithm Progressive Edge Growth Permutation Expansion Repeat Accumulate (Code) Stopping Set Quasi Cyclic Quasi Cyclic Identity Quasi Cyclic Matrix Quasi Cyclic LDPC (Code) Signal Noise Ratio Turbo Product Code Vector Addition 最小和算法 改进的最小和算法 边增长(算法) 乱序扩展 重复累积(码) 停止集 准循环 准循环移位单位阵 准循环移位阵 基于准循环结构的 LDPC (码) 信噪比 Turbo 乘积码 向量加法 第 63 页 符号名称 dc dv G H/H*/H~/H# HB HM M m N n R zCSEx zPEx 附录二 符号说明 附录二 符号说明 代表含义 校验矩阵的行重 校验矩阵的列重 LDPC 码的生成矩阵 LDPC 码的校验矩阵及其变型 LDPC 码的基矩阵 基于二次扩展的 QC-LDPC 码的母矩阵 校验矩阵 H 的行数 校验矩阵 H 基矩阵的行数 LDPC 码码长 校验矩阵 H 基矩阵的列数 LDPC 码码率 循环移位扩展因子 乱序扩展因子 第 64 页 致谢 致谢 本文能够在今天顺利完成,是离不开生活中各个方面对我的关心和帮 助的。如果没有你们的支持,难以想象我能够在两年半的研究生生活中坚 持下来。 首先我要感谢我的父母,是他们在家里无微不至的照顾使我免去了后 顾之忧,得以将全部精力投入到科研和论文的撰写过程中去,他们的关怀 是我此次写作的原动力所在。 其次,我要感谢我的导师徐友云老师,在我两年半的硕士学习生涯中, 他给了我许多学术上的指导,导引我进入了无线通信的领域中。无论是在 学术还是项目上,都对我提出了严格的要求,让我在任何时刻都不至于懈 怠,始终保持着对科学的无限探求。 然后,我要感谢我的指导教师俞晖老师,从我的本科毕业设计开始, 他就对我进行学术科研上各个方面的指导,掌握着我学术研究进展的第一 手信息,在本文的写作过程中也给我提了许多宝贵的建议。我还要感谢无 线通信研究所的全体教师,不但为我的学习和研究提供了良好的氛围,更 在平时成为了我的良师益友。他们是:张海滨老师、钱良老师、甘小莺老 师、王新兵老师、刘静老师、刘炜老师等。 这里还需要提到的是我们 LDPC 组的所有新老成员,他们是和我一届 的倪俊枫、沈进旗同学,在平时科研、项目中给了我很多启发;潘宇、施 惠丰、王大伟师兄,他们为我所做的研究做了很多基础工作;以及夏皛、 华颖、丁洁等师弟师妹们,他们为我进行 FPGA 仿真验证提供了很大的帮 助。 如果没有这些家人、老师、朋友、同学的支持和鼓励,我的论文不会 进行得这么顺利,在此谨向大家表示我最真实的敬意,感谢你们为我所做 的这一切! 第 65 页 攻读硕士学位期间已发表或录用的论文 攻读硕士学位期间已录用的论文和申请的专利 [1] 张晨,徐友云,俞晖,《低复杂度的基于迭代译码的 LDPC 编码方法》,已于 2007 年 9 月 27 日被《信息技术》录用 [2] 张晨,徐友云,俞晖,甘小莺,《分层准循环扩展构造的 LDPC 码的编码器》,已于 2007 年 9 月 7 日申请专利 第 66 页 高吞吐量LDPC码编码构造及其FPGA实现 作者: 学位授予单位: 张晨 上海交通大学 相似文献(2条) 1.期刊论文 基于PEG算法的准循环LDPC码的编码构造方法 -数据采集与处理2009,24(z1) 为了将渐进添边(Progressive edge-growth,PEG)算法应用于准循环低密度校验码(Low density paritycheck codes,LDPC codes)的构造,本文从最小化环长和减少短环周期的角 度,提出一种新颖的准循环LDPC码的编码构造方法.利用该方法构造出一个码率为1/2的LDPC码,并通过计算机仿真得到其误帧率曲线,其性能优于3GPP中相同码长码率的Turbo码.该 LDPC码不仅性能优异,而且编译码方法简单、复杂度低,能够节省存储空间,适用于未来移动通信以及深空通信. 2.学位论文 杨曙辉 一种用模拟LSI实现的新型软判决译码器的设计方法研究 2003 随着电子信息技术的迅速发展,人们对调整、低功耗的数据通信系统的需求越来越大.目前,以手机为代表的移动通信用户已可以实现声音、图象和数据的传输,正朝着更高速的方 向发展.在通信系统中,速度与可靠性是一对矛盾,随着速率的提高,势必要求在信道中引入更为复杂的编码方案和解码算法,用以保护数据在高速传输过程中引起的误码.例如在第三代 移动通信中,已部分采用了目前性能最好的Turbo码编码方案.采用这些新型信道编、解码方法的目的,是为了在传输时能够接近理论上的信道容易限制,更好地利用信号功率和信道带 宽.但是对于Turbo码和低密度校验码等高性能码进行解码时一般采用迭代算法,需要很大的计算功率,计算的复杂性使得在给定功率情况下,很难用传统的数字电路设计方法实现.因此 需要研究新型的信道解码器的设计方法.该文利用信息论中的因子图概念,在系统级和行为级对信道编码构造了行为和概率组合模型.在算法级采用因子图中的和积算法,计算接收信息 序列中有效信息的后验概率分布,通过比较后验概率的大小,完成对信道编码的软判决译码.在电路级利用CMOS工艺,通过晶体管级的模拟电路设计,以(5,2,3)网格码为例,构造了完整 的模拟解码器电路.解码器主要由具有二级流水线结构的模拟输入接口电路,概率计算解码算网络电路,输出接口电路等组成.该文以模拟电路型乘法器为基础,利用和积算法和概率门 函数的定义,设计了一组与数字逻辑门电路对应的模拟概率门电路.通过对模拟概率门电路的有效级联,构成解码时所需的概率计算网络,完成后验概率解码算法.虽然在单元电路中采 用的是精度比较低的晶体管器件,但是通过高度的互连,以及实质是利用电路比值的关系来解码,使得模拟计算网络可以在系统级达到很高的准确性.用模拟LSI实现数字通信的信道解 码,是充分利用而不是排斥晶体管器件固有的非线性物理特性,体现了集成电路设计时对事物认识全面考虑的思想.与相应的数字电路实现相比,模拟解码器在速度或功耗上,至少提高 了两个数量级,而且芯片面积和结构的复杂性都降低了很多.模拟概率门电路也可形成模块电路,便于整体电路设计时的调用,减少了模拟电路设计时的工作量.这种设计方法适用于构 造可用因子图描述的网络码、Turbo码、低密度校验码等的模拟解码器. 本文链接:http://d.g.wanfangdata.com.cn/Thesis_D060004.aspx 授权使用:北京理工大学(北京理工大学),授权号:9fea7086-553c-4079-b1a7-9e2e001793ac 下载时间:2010年11月14日
更多简介内容

评论

下载专区


TI最新应用解决方案

工业电子 汽车电子 个人电子
$(function(){ var appid = $(".select li a").data("channel"); $(".select li a").click(function(){ var appid = $(this).data("channel"); $('.select dt').html($(this).html()); $('#channel').val(appid); }) })