当前位置:首页 >> 信息与通信 >>

LDPC编译码技术的研究与实现_图文

电 子 科 技 大 学
UNIVERSITY OF ELECTRONIC SCIENCE AND TECHNOLOGY OF CHINA

硕士学位论文
MASTER THESIS

论文题目

LDPC 编译码技术的研究与实现

学科专业 学 号

通信与信息系统 201221010415 孔宪章 阎 波 教授

作者姓名 指导教师

分类号 UDC 注 1

密级









LDPC 编译码技术的研究与实现
(题名和副题名)

孔宪章
(作者姓名)

指导教师





教 成

授 都

电子科技大学

(姓名、职称、单位名称)

申请学位级别 提交论文日期

硕士 2015.03.26

学科专业 论文答辩日期

通信与信息系统 2015.05.19 2015 年 6 月

学位授予单位和日期 答辩委员会主席 评阅人

电子科技大学

注 1:注明《国际十进分类法 UDC》的类号。

RESEARCH AND IMPLEMENTATION OF THE LDPC TECHNOLOGY OF ENCODING AND DECODING

A Master Thesis Submitted to University of Electronic Science and Technology of China

Major: Author: Advisor: School:

Communication and Information System Xianzhang Kong Prof. Bo Yan
School of Communication and Information Engineering

独创性声明
本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知,除了文中特别加以标注和致谢的地方 外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 作者签名: 日期: 年 月 日

论文使用授权
本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定,有权保留并向国家有关部门或机构送交论文的复印件和磁盘, 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 (保密的学位论文在解密后应遵守此规定) 作者签名: 导师签名: 日期: 年 月 日

摘 要

摘 要
当今时代,移动通信发展迅速,已经进入到人们生活的各个方面,给人们的 工作和生活带来极大的便利。纠错编码技术的应用对移动通信技术的实现起到了 关键的作用。LDPC(Low Density Parity Check code)码是纠错编码技术中一种能 够逼近香农极限的“好码” 。 本文基于 802.16e 协议实现了一个多码长多码率的高速 QC-LDPC 编码器和译 码器。首先,分别通过对编码和译码算法进行了研究。LDPC 编码算法主要有高斯 消元法、Efficient 算法等,本文选择了适合 802.16e 协议中准双对角线校验矩阵的 简化 Efficient 编码算法。在编码的硬件实现过程中,采用了流水线和部分并行结 构,实现了高速编码器。 LDPC 译码算法主要研究了基于概率测度的 BP 译码算法、 基于 LLR 的 BP 译 码算法、归一化最小和译码算法等算法。最终的实现选择了适合 FPGA 硬件实现 的归一化最小和译码算法。在实现结构方面,对 TPMP 和 TDMP 两种实现结构进 行了仿真对比,最终选择了收敛速度快、迭代次数少的 TDMP 实现结构,即水平 分层迭代结构。最终实现的译码器可以信噪比为 2.5dB 时,BER 可以达到 10-6。另 外,为了实现高速译码器的目标,译码器的实现过程中采用了乒乓操作、流水线 结构、四个码字同时译码等结构来提高译码器的吞吐率。 本文利用 Xilinx 公司的 XC705 开发板实现了多码长多码率的 QC-LDPC 高速 编码器和译码器,码长最大支持 2304,码率支持 1/2、2/3、3/4 和 5/6。编码器的 时钟频率为 250MHz, 吞吐率为 13.7Gbps。 译码器实现了最大时钟频率为 250MHz、 最大吞吐率为 1.65Gbps 的高速译码器。 关键词:QC-LDPC,TDMP,Efficient 算法,归一化最小和译码算法,FPGA

I

ABSTRACT

ABSTRACT
Nowadays, mobile communication develops rapidly and it has made a great effect on every aspect of people’s life and has brought much convenience to them. The applica -tion of Error Correction of Coding plays a key role in mobile communication technolo -gy. LDPC (Low Density Parity Check) code is one kind of Error Correction of Coding which is a good code because of its near Shannon limit performance in the high code rate range. This thesis has completed a QC-LDPC coder and decoder which is suited for multi code length and multi code rate based on 802.16e. The algorithm of coding and decoding has been studied. The coding algorithm is mainly Gaussian elimination method and Efficient Coding Algorithm. We choosed the Efficient Algorithm which is suited for the structure of quasi-double diagonal in 802.16e. In order to complete the high speed LDPC coder, we make full use of the pipeline and partial-parallel structure. This thesis made a description of the LDPC decoding algorithm such as belief propagation decoding algorithm and normalized min-sum decoding algorithm. Finally, we choosed the later one. We focused on two kinds of implementation structures—TDMP and TPMP. The iterations of TDMP structure is less 50% than TPMP structure. After the comparison, we used the TDMP structure in decoding. The BER of the system can achieve 10-6 when SNR is 2.5dB. Besides, the implementation of LDPC decoding also used the Ping-Pong operating and pipeline technology to improve the performance of the decoders. The thesis has made a complementation of a QC-LDPC coder and decoder on XC705 board of Xilinx which is multi code length and code rate. The maximum code length is 2304 and the code rate is 1/2, 2/3, 3/4 and 5/6. The maximum frequency of the system is 250MHz and the throughput of coder and decoder is 13.7Gbps and 1.65Gbps. Keywords: QC-LDPC, TDMP, Efficient Algorithm, Normalized MSA, FPGA

II

目 录

目 录
第一章 绪论 ............................................................................................................. 1 1.1 数字通信系统与信道编码....................................................................... 1 1.2 LDPC 码的发展历史与研究现状 ........................................................... 3 1.3 论文内容安排........................................................................................... 4 第二章 LDPC 码基础理论 ...................................................................................... 6 2.1 LDPC 码的基本概念 ............................................................................... 6 2.1.1 校验矩阵表示法............................................................................. 6 2.1.2 Tanner 图表示法............................................................................. 7 2.2 LDPC 码关键性能参数 ........................................................................... 8 2.2.1 度分布序列 .................................................................................... 8 2.2.2 环 .................................................................................................... 9 2.3 LDPC 码的构造方法 ............................................................................... 9 2.3.1 随机构造法..................................................................................... 9 2.3.2 结构化构造方法............................................................................11 2.4 QC-LDPC 码的基本概念 ...................................................................... 12 2.4.1 QC-LDPC 码的基本概念和特点 ................................................ 12 2.4.2 IEEE802.16e 协议中 QC-LDPC 码的应用 ................................. 12 2.5 本章小结................................................................................................. 13 第三章 LDPC 编码算法研究及硬件实现设计 .................................................... 15 3.1 LDPC 码的编码算法 ............................................................................. 15 3.1.1 生成矩阵算法............................................................................... 15 3.1.2 高斯消元法编码算法................................................................... 15 3.1.3 Efficient 编码算法 ........................................................................ 16 3.1.4 适用于 802.16e 的简化 Efficient 编码算法 ................................ 18 3.2 LDPC 码编码器的硬件实现 ................................................................. 20 3.2.1 LDPC 编码器硬件实现结构分析 ............................................... 20 3.2.2 LDPC 编码器硬件实现仿真 ....................................................... 22 3.3 本章小结................................................................................................. 23 第四章 LDPC 译码算法研究及硬件实现设计 .................................................... 24 4.1 LDPC 译码算法分析 ............................................................................. 24 4.1.1 比特翻转译码算法....................................................................... 24
III

目 录

4.1.2 基于概率测度的 BP 译码算法 .................................................... 26 4.1.3 基于对数似然比的 BP 译码算法 ................................................ 28 4.1.4 最小和译码算法........................................................................... 30 4.1.5 译码算法性能比较....................................................................... 31 4.2 LDPC 译码器关键参数的仿真 ............................................................. 32 4.2.1 量化范围及量化位宽的确定....................................................... 32 4.2.2 归一化因子的确定....................................................................... 35 4.2.2 最大迭代次数的确定................................................................... 37 4.3 硬件实现结构分析................................................................................. 38 4.3.1 串行、全并行与部分并行实现结构........................................... 38 4.3.2 TPMP 结构和 TDMP 结构及性能对比 ...................................... 38 4.3.3 LDPC 译码器 FPGA 实现结构图 ............................................... 41 4.4 译码器仿真结果..................................................................................... 53 4.5 本章小结................................................................................................. 55 第五章 LDPC 编译码器的验证与测试 ................................................................ 57 5.1 LDPC 编译码器的验证方案 ................................................................. 57 5.2 LDPC 编译码器的验证平台 ................................................................. 59 5.3 LDPC 编码器和译码器的板级验证 ..................................................... 62 5.1.1 LDPC 编码器的板级验证 ........................................................... 62 5.1.2 LDPC 译码器的板级验证 ........................................................... 64 5.4 LDPC 编译码器的性能分析 ................................................................. 65 5.5.1 LDPC 编码器的性能分析 ........................................................... 65 5.5.2 LDPC 译码器的性能分析 ........................................................... 67 5.5 本章小结................................................................................................. 68 第六章 总结与展望 ............................................................................................... 69 6.1 总结......................................................................................................... 69 6.2 展望......................................................................................................... 70 致 谢 ................................................................................................................ 71 参考文献 ................................................................................................................ 72 个人简历及攻读硕士学位期间的研究成果 ........................................................ 75

IV

图目录

图目录
图 1-1 数字通信系统框图 ....................................................................................... 1 图 2-1 校验矩阵 H(12,3,6)的 Tanner 图 ................................................................ 7 图 2-2 四环 .............................................................................................................. 9 图 2-3 Gallager 法构造的校验矩阵 ...................................................................... 10 图 3-1 校验矩阵经过高斯消元法后的矩阵 ........................................................ 16 图 3-2 校验矩阵转化后得到的近似下三角矩阵 ................................................ 16 图 3-3 编码硬件实现框图 .................................................................................... 20 图 3-4 循环移位模块输入输出 ............................................................................ 21 图 3-5 add_unit 模块输入输出 .............................................................................. 21 图 3-6 编码器输入格式 ........................................................................................ 22 图 3-7 编码器中关键信号的仿真波形 ................................................................ 22 图 4-1 Tanner 图中译码迭代数据流(1) ........................................................... 27 图 4-2 Tanner 图中译码迭代数据流(2) ........................................................... 28 图 4-3 三种译码算法的性能及实现复杂度比较 ................................................ 31 图 4-4 信噪比为 0 时接收到 y 的概率分布 ........................................................ 33 图 4-5 不同 SNR 下的量化范围边界 .................................................................. 34 图 4-6 不同量化比特的性能比较 ........................................................................ 35 图 4-7 不同归一化因子取值下译码器的性能比较 ............................................ 36 图 4-8 译码器不同迭代次数的译码性能对比 .................................................... 37 图 4-9 TDMP 结构下的 LDPC 不同信噪比的误比特率仿真图......................... 40 图 4-10 TPMP 结构下的 LDPC 不同信噪比的误比特率仿真图 ....................... 41 图 4-11 QC-LDPC 译码器的硬件实现整体架构 ................................................. 42 图 4-12 译码器设计文件列表 .............................................................................. 44 图 4-13 译码器输入输出示意图 .......................................................................... 45 图 4-14 将两个码字绑定在一起译码 .................................................................. 45 图 4-15 Channel_ram 的结构图 ............................................................................ 46 图 4-16 Channel_ram 接口示意图 ........................................................................ 46 图 4-17 Shift_array 的接口示意图 ........................................................................ 47 图 4-18 Sub_array 输入输出接口示意图 ............................................................. 48 图 4-19 Sub_unit 输入输出示意图 ....................................................................... 49
V

图目录

图 4-20 FIFO 模块输入输出接口示意图 ............................................................. 50 图 4-21 CNU_array 输入输出接口示意图 ........................................................... 50 图 4-22 min_info 的格式 ....................................................................................... 51 图 4-23 cnu_unit 输入输出接口示意图 ................................................................ 51 图 4-24 Min_ram 输入输出接口示意图 ............................................................... 52 图 4-25 Sign_ram 输入输出接口示意图 .............................................................. 52 图 4-26 Add_array 模块输入输出接口示意图 ..................................................... 53 图 4-27 加法器小单元 add_unit 输入输出接口图 ............................................... 53 图 4-28 LDPC 译码器数据输入模块仿真............................................................ 54 图 4-29 译码器数据输出格式 .............................................................................. 54 图 4-30 译码器输出结果(一) .......................................................................... 55 图 4-31 译码器输出结果(二) .......................................................................... 55 图 5-1 LDPC 编译码系统模型.............................................................................. 57 图 5-2 matlab 加噪处理过程 ................................................................................. 58 图 5-3 验证平台及数据流 .................................................................................... 58 图 5-4 Xinlinx 公司 KC705 开发板 ...................................................................... 59 图 5-5 FPGA 一般设计流程.................................................................................. 61 图 5-6 板级验证连接图 ........................................................................................ 63 图 5-7 编码器板级验证仿真图(一) ................................................................ 63 图 5-8 编码器板级验证仿真图(二) ................................................................ 64 图 5-9 译码器板级验证仿真图(一) ................................................................ 64 图 5-10 译码器板级验证仿真图(二) .............................................................. 65 图 5-11 译码器板级验证仿真图(三) .............................................................. 65 图 5-12 对时钟信号进行约束 .............................................................................. 66 图 5-13 编码器的时钟约束报告 .......................................................................... 67 图 5-14 QC-LDPC 译码器时钟约束报告 ............................................................. 68

VI

表目录

表目录
表 2-1 三种码长和四种码率下信息比特和码长的对应关系 ............................ 13 表 2-2 802.16e 协议中码率为 1/2,码长为 2304 的基矩阵 ............................... 13 表 4-1 译码器状态控制器 .................................................................................... 44 表 4-2 Shift_array 对初始数据进行初始化位移量 .............................................. 48 表 5-1 XC7K325T 芯片资源统计表 ..................................................................... 60 表 5-2 编码器的硬件资源消耗表 ........................................................................ 66 表 5-3 QC-LDPC 译码器的资源消耗表 ............................................................... 67 表 5-4 QC-LDPC 译码器吞吐率计算 ................................................................... 68

VII

缩略词表

缩略词表
英文缩写 LDPC QC-LDPC BPSK CNU VNU FPGA SNR BER TPMP TDMP BP NMS ASIC LLR LTE DVB AWGN WiMax WCDMA 英文全称 Low Density Parity Check Code Quasi-LDPC Binary Phase Shift Keying Check Node Update Variable Node Update Field Programmable Gate Array Signal Noise Radio Bit Error Rate Two Phase Message-Passing Turbo Decoding Message-Passing Belief Propagation Algorithm Normalized Minimum Sum Application Specific Integrated Circuit Log Likelihood Ratio Long Term Evolution Digital Video Broadcasting Additive White Gaussian Noise Worldwide Interoperability for Microwave Access Wideband Code Division Multiple Access 中文注释 低密度奇偶校验码 准循环低密度奇偶校验码 二进制相移键控 校验节点更新单元 变量节点更新单元 现场可编程门阵列 信噪比 误比特率 两相消息传递法 Turbo 译码类消息传递法 置信传播算法 归一化最小和译码算法 专用集成电路 对数似然比 第四代移动通信技术 数字视频广播 加性高斯白噪声 全球微波互联技术 宽带码分多址移动通信系统

VIII

第一章 绪论

第一章

绪论

绪论部分主要综述数字通信系统与信道编码技术等基本原理,其次着重研究 信道编码中的 LDPC 码的历史、研究现状与 LDPC 码在未来移动通信中的应用价 值并与 LTE 标准采用的 Turbo 码进行了对比。在本章的最后一节中,简要分析了 本论文的后续章节的概要。

1.1 数字通信系统与信道编码
在当今社会,通信系统影响着我们生活的方方面面,它可以可靠并及时地把 信息(如声音、图像等)传递到接收方。数字通信有着抗干扰性能强、差错可控 等优点,应用非常广泛。数字通信系统包括手机、数字电视、因特网接入以及计 算机之间的数据传输。这些系统功能差异很大,然后他们几乎都有着一个通用的 数字通信系统模型[1](如图 1-1) 。

信源

信源编码

加密

信道编码

调制器

噪声

信道

信宿

信源解码

解密

信道解码

解调器

图 1-1 数字通信系统框图

在数字通信系统中,信息序列(如声音、图片等)首先被采样,量化成数字 信号。然后通过信源编码器,经过数据压缩,去除冗余信息。通过加密增加数据 的安全性能。接下来通过信道编码,保证信息在通信系统中的可靠性,在这个过 程中增加了冗余信息。信道编码通常包括差错校验码、纠错码等。接收方通过差 错校验码可以知道接受到的信息是否正确并且根据差错校验码的结果可以确定是 否需要重传。而接收方通过纠错码则可以将一定范围的错误比特纠正过来。LDPC 码、Turbo 码就是两种应用广泛的纠错码。 经过信道编码后需要调制成可以再信道中传输的符号,根据信道的不同可以 采用不同的调制方式(如 BPSK、QPSK、16QAM、64QAM 等) 。信道是指信息传 输的具体的物理媒介,比如天线、网线、光纤、真空等。在信道中,信息的传输
1

电子科技大学硕士学位论文

会引入噪声,噪声对信息的干扰可以使信息比特发生错误。不同的信道可以引入 不同程度的误码率。 接收方收到信道信息后,经过解调将传输的信号符号还原为调制之前的数字 比特序列,由于信道的噪声的加入,收到的比特序列和之前发送的比特序列会发 生误码现象。通过信道译码器,利用接收到比特中的冗余信息来检查和纠正发生 的误码错误,提高信息传输的安全性。通过信道译码器后再经过解密、信源解码 到达信宿,即最终的接受者。 在数字通信系统中,可靠性是需要解决的基本问题之一。信宿接收到信息然 后进行评判,去伪存真的能力也就是可靠性。一般情况下可靠性是用误比特率、 误码率来表示。减小误比特率、误码率的方法就是充分利用信道编码技术。 在数字信号的传输过程中,信道会不可避免的加入干扰和噪声,从而使码元 受到破坏。对于普遍存在的加性噪声来看,主要有这些方法:采用适当的调制技 术、增加发送功率、采用差错控制等。纠错编码技术通过增加一些冗余的校验位 可以使接收端能够发现或纠正错误,这样可以高效的保证数字的传输可靠性。同 时也可以大大提高通信各项指标,如降低误比特率,降低天线功率等。 信道编码技术包含很多分类,按照其功能进行分类,可以分为纠删码、纠错 码和检错码;按照对信息比特的处理方法的不同可以分为分组码和卷机码;此外, 根据校验比特和信息比特之间的关系可以分为线性码和非线性码;根据进制可以 分为二进制码和多进制码。 1948 年,香农提出了有名的信道编码定理[2],也被称为抗干扰的信道编码定 理:设信道共有 D 个符号输入,S 个符号输出,信道容量为 C,传送的消息码长 是 N,信息传输速率用 R 表示。当 R<C 时,只要 N 有足够长,则一定会在输入的 集合中找到 M 个码字,分别表示 M 个可能性相同的消息,组成一种编码,选择对 应的译码方式,可以是译码后的最小平均错误概率 P 值达到任意小。 这个定理也是香农第二定理,这个定理可以得到:在有噪声的信道中,只要 信道编码的码长足够长,总能找到一种编码方式,使得传输的数据发生错误的概 率达到任意小的值,同时此信道的传输速率能够无限制地接近香农极限。香农第 二定理的证明中用了三个理想的条件: (1)随机编码方式; (2)码长 N 趋于无限 长; (3)译码采用最好的最大似然比译码。 Turbo 码和 LDPC 码就是两种能够逼近香农极限的编码方式, 他们都引入了随 机编码的思想,Turbo 码采用交织器件来引入随机性,而 LDPC 码则采用将随机性 转化为稀疏校验矩阵的随机性。他们码长都可以很长,译码方式也采用了非常接 近最大后验概率的译码的迭代译码算法。

2

第一章 绪论

1.2 LDPC 码的发展历史与研究现状
LDPC 是一种线性纠错码。 Gallager 在 1962 年他的博士论文 《Low Density Parity Check Codes》[3]中详细提出了 LDPC 码(Low Density Parity Check Code),在他的 论文中,论述了校验矩阵的构造方式和编码方法,同时也提出了基于概率的迭代 译码算法。给出了在二进制对称信道、加性高斯白噪声信道下的仿真结果。性能 可以超越当时几乎所有的编码方式。然而,由于其复杂的技术水平和译码理论方 面的不足,导致接下来的三十多年里,LDPC 码一直被研究人员所遗忘。 1981 年 Tanner 提出了基于图模型的码,引入了 Tanner 图[4](又叫二部图) 。 Tanner 认为采用 Tanner 图构造而成的 LDPC 码在经过译码后能够明显地降低译码 过程的复杂度。同时他提出了和积译码算法(SUM-PRODUCT ALGORITHM)和 最小和译码算法(MIN-SUM ALGORITHM) 。Tanner 为后来的 LDPC 再次被世人 关注奠定了坚实的研究基础。 上世纪 90 年代,C.Berrou 提出了 Turbo 码,达到了近似香农极限的性能。其 译码结构采用了并行级联的方式,编码简单,译码采用了迭代译码算法,复杂度 比较低,并被广泛地应用在了第三代移动通信标准 WCDMA 和 CDMA2000 中[5]。 Turbo 码的迭代思想为 LDPC 码的译码提供了新的思路。此时,研究人员重新对 LDPC 码提出了研究兴趣。 1996 年,Neal 和 MacKay 在研究过程中提出 Gallager 发明的 LDPC 码也是以 一种“好”码,并且在长码时,性能甚至超过了 Turbo 码。这项发现标志着 LDPC 重 新回到研究人员的视野。 M. G. Luby 等提出了非规则的 LDPC 码, 这种码的性能超过了规则码的性能[6]。 Chung 提出码率为 1/2 的 LDPC 码,其性能距离香农极限仅有 0.0045dB 之内[7]。 2004 年 Marc P.C 提出了 QC-LDPC 码[8],实现了低复杂度的编码,译码可以采用 部分并行的结构。 目前, LDPC 码已经在很多方便被应用, 如 DVB-S2、 CCSDS 标准、 GB20600、 以及 WiMax(802.16e)中。 近年来,LDPC 码的研究主要在以下几个方面:构造校验矩阵方法、编译码算 法的优化、误码率分析比较以及 LDPC 码在实际应用中的实现。 目前,移动通信发展日新月异,第四代移动通信技术 LTE 发展如日中天。而 LTE 在信道编码中用的是 Turbo 码。 随着下一代无线通信对更高速率、 更高吞吐率 的要求,Turbo 和 LDPC 码成为了两个非常重要的候选方案。这两种码都能够逼近 香农极限,两种码各有优势。 Turbo 码的性能稍微优于 LDPC,但是却要付出巨大的代价。吉华芳的研究[9]
3

电子科技大学硕士学位论文

表明将 LDPC 码迭代 20 次的性能与 Turbo 码迭代 6 次的性能比较后,虽然 Turbo 码的性能比 LDPC 码优 0.5dB,然后 LDPC 的复杂度却只有 Turbo 的 5/656。 LDPC 码比 Turbo 码译码复杂度较低,每 bit 译码需要少量的计算,可以完全 实现并行操作, 实现高速译码。 而 Turbo 码随着码长的增加, 译码的时间急剧增加。 因为对于 Turbo 码来说,是由卷积码级联而成,当分组的长度比较长时,译码复杂 度并不是简单线性增加。但是,对于 LDPC 码来说就不是这样,因为 LDPC 码是 采用的并行的方式,只需要增加扩展因子就可以,这样不会增加译码需要的时间。 另外,LDPC 码的校验矩阵具有稀疏的特性,码长很长的时候,距离比较远的 信息比特是一起参与校验过程,突发差错对于译码的影响不大。因此 LDPC 码本 身就具有了纠正突发差错的特性。但是,对于 Turbo 码来说,加入随机性需要引入 交织器。而交织器必然会造成一定的延迟。因此,Turbo 码会因为交织器的存在而 产生较大的延时。总之,LDPC 码本身就具有自交织性能,即伪随机性。 对于 LDPC 码,可以根据资源来选择实现的结构,可以在串行、并行和部分 并行之间选择, 不同的结构意味着不同的资源和不同的吞吐率。 而 Turbo 码则没有 这样的优点。另外,LDPC 码不仅仅适用于二进制的对称信道,同样也适用于任何 最佳输入是对称分布的信道,所以几乎在任何信道上是“好码”。 目 前 为 止 , Turbo 码 已 经 应 用 在 了 第 三 代 移 动 通 信 标 准 CDMA2000 和 WCDMA、以及第四代移动通信标准 LTE 中。LDPC 应用同样广泛,比如 DVB、 WiMAX 等标准中。由于上文中提到的 LDPC 码的种种优点,笔者认为在下一代移 动通信中, LDPC 码有着很大的可能性来代替 Turbo 码。因此,继续研究 LDPC 编译码技术以及其在 FPGA 上的实现有着很重要的研究意义。

1.3 论文内容安排
本文的主要工作之一就是 LDPC 编译码算法的研究,通过分析比较现有的 LDPC 编 译 码 算 法 并 对 之 进 行 对 比 。 主 要 采 用 了 适 合 采 用 部 分 并 行 算 法 的 QC-LDPC 码,QC-LDPC 码将 LDPC 码分为小的模块适合对各个模块进行并行计 算。本文将 LDPC 码的编译码算法的实现基于 802.16e 标准实现。采用乒乓操作、 流水线、部分并行等设计思想完成了编译码算法在 FPGA 上的实现。实现的特色 在于多码率多码长的实现以及比较高的吞吐率。以下部分对本文的行文安排做一 个简单分析: 本文第二章主要研究 LDPC 码的基本定义、基本理论等基础理论。研究了 LDPC 码的概念、QC-LDPC 码、校验矩阵、Tanner 图的特点。 第三章主要内容是关于 LDPC 编码算法的研究以及实现。编码算法主要采用
4

第一章 绪论

适合 802.16e 的校验矩阵特征的 Efficient 编码算法, 对 QC-LDPC 编码进行了 FPGA 的硬件实现设计,对硬件实现的结构进行了分析和研究。 第四章主要内容是对 QC-LDPC 码的译码算法进行研究、对比以及硬件实现。 通过研究基于概率测度的 BP 译码算法、基于对数似然比的 BP 译码算法和最小和 译码算法以及对比,选择了适合 FPGA 实现的归一化最小和译码算法。随后研究 了算法仿真的各项参数,如最大译码迭代次数、归一化最小和因子、定点范围和 位宽等参数。然后对硬件实现结构的特点进行了研究,如采用了部分并行、流水 线等结构。最后,将 QC-LDPC 在 Modelsim 上的硬件实现仿真情况展现出来。 第五章主要内容是 QC-LDPC 码的译码的板级测试部分。对 QC-LDPC 编码器 和译码器的测试平台和测试方案进行了详细分析。并对其实现的性能参数进行了 研究。 第六章主要内容是对本文的总结和对未来的展望。

Equation Chapter (Next) Section 1 Equation Chapter (Next) Section 1

5

电子科技大学硕士学位论文

第二章
2.1 LDPC 码的基本概念

LDPC 码基础理论

LDPC 码是一种线性分组纠错码,于 1962 年被 Gallager[3]提出,因此又称为 Gallager 码。LDPC 码可以用 (n, k ) 表示,其中 n 表示码长,k 表示信息比特的长度, 那么 (n ? k ) 表示校验比特的长度。而码率则被定义为:
R? k n

(2-1)

s ? ? s0 , s 1, s
关系:

设 一 个 码 长 为 n 的 LDPC 码 为 c ? ?c0 , c1 , c2…cn?1 ? , 对 应 的 信 息 位 为
2

sk ?

?1

, 那么一定存在一个 n 维的线性向量组合 G ,使得 c 和 s 存在如下

c ? s ?G
其中 G 是由 k 个 n 维向量组成:
? g0 ? ? g ? ? 1 ? G ? ? g2 ? ? ? ? ? ? g ? k ?1 ? ?

(2-2)

(2-3)

上式中, g0 , g1 , g2

gk ?1 都是行向量。G 称为 LDPC 码的生成矩阵。生成矩阵

可以用作 LDPC 码的编码使用。最早的 LDPC 编码就是用生成矩阵来实现的。除 了生成矩阵之外,还有一种重要的矩阵叫做校验矩阵,将在下面进行分析。

2.1.1

校验矩阵表示法

通常 LDPC 码可以由校验矩阵和二分图来唯一确定[10]。校验矩阵 H 的维度为
(n ? k ) ? n 。 H 矩阵是一个稀疏矩阵,也就是 H 矩阵中的“1”非常少,所以 LDPC

码也可以称为“低密度奇偶校验码”。假设编码后的 LDPC 码用 c 表示,那么校验矩 阵和 c 的关系是: H ? cT ? 0 。 H 是一个维度为 ? n ? k ? ? n 的矩阵。

6

第二章 LDPC 码基础理论

? h0 ? ? h ? H= ? 1 ? ? ? ? ? ? hn ? k ?1 ?

(2-4)

根据 H 与 c 的关系可以用作编码和译码。行重是指校验矩阵 H 的一行中“1”的 个数,同理,一列中“1”的个数就是列重。稀疏校验矩阵中的行或列中“1”的个数不 固定的校验矩阵称为不规则码。每一行的行重都相等,每一行的列重都相等,那 么这样的 LDPC 码叫做规则码。规则 LDPC 码可以用 H ? n, p, q ? 来表示,其中 n 为 码长, p 和 q 分别表示规则码的校验矩阵的行重和列重,例如下面的校验矩阵对应 的 LDPC 码就是一个规则码,可以用 H ?12,6,3? 来表示:

?1 ?1 ? ?0 H = ? ?1 ?0 ? ?0

1 1 0 0 1 0

1 1 0 0 0 1

0 1 0 1 1 0

0 1 0 0 1 1

1 0 1 0 0 1

1 0 1 0 1 0

0 0 1 1 1 0

0 0 0 1 1 1

0 0 1 1 0 1

1 0 1 0 0 1

0? 1? ? 1? ? 1? 0? ? 0?

(2-5)

2.1.2

Tanner 图表示法

由上节可知,校验矩阵和 LDPC 码是一一对应的关系,除此之外,Tanner 图 也可以唯一定义 LDPC 码[11]。Tanner 图由三个部分构成,分别是变量节点、校验 节点以及连接校验节点和变量节点的边。Tanner 是一个双向图,把校验矩阵中的 变量节点和校验几点之间的关系形象地表示成图模型。变量节点用圆圈表示,而 校验节点则用正方形表示,如果 H (i, j ) 为“1”,那么在第 i 个校验节点和第 j 个变
校验节点 C1 C2 C3 C4 C5 C6

V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V11 V12 变量节点

图 2-1 校验矩阵 H(12,3,6)的 Tanner 图

7

电子科技大学硕士学位论文

量节点连接,否则不连接。这样校验矩阵就和 Tanner 图一一对应起来。和某一个 节点直接相连的节点的个数定义为此点的度。从一个节点出发,从另一条边回到 原点走过的边形成一个“环”,其中距离最短的循环距离叫做“围长”。 前面已经讲过如何把校验矩阵转化为 Tanner 图的方法,即图 2-1 为上一节中 的公式(2-5)转化为的 Tanner 图。从图 2-1 中的 Tanner 图可以看出,其所对应的校 验矩阵共有 12 个变量节点,变量节点的度为 3,校验节点的度为 6。

2.2 LDPC 码关键性能参数
LDPC 码的性能与校验矩阵和 Tanner 图有着很强的联系。这些关键的参数将 会在本节中讨论。

2.2.1 度分布序列
稀疏校验矩阵中行重或列重不固定的 LDPC 码称为不规则码。与节点相连的 节点的个数称为这个节点的度。不规则 LDPC 码的每个节点的度一般不相同,可 以用度分布序列[12]来表示。度分布对用 ? ? , ? ? 来表示,度分布中 ? 和 ? 的定义如下 所示:
d i ?1 zkq 20151125 ? ? x? ? ??x
v

i ?2

i

(2-6) (2-7)

? ? x ? ? ? ? j x j ?1
j ?2

dc

上式中 ? ? x ? 和 ? ? x ? 分别是变量节点和校验节点的度分布。当 x ? 1 时,

? ?1? ? 1 且 ? ?1? ? 1 。其中 ? i 表示的是全部与度为 i 的变量节点相连边数在总边数中
所占的比例。 ? j 表示全部的度为 j 的校验节点相连的变数在总变数中所占的比例。 另外, d v 和 d c 分别表示 Tanner 图中变量节点和校验节点的最大的度。规则 LDPC 码就是不规则 LDPC 码的一个特例,比如 (2, 4) LDPC 规则码之度分布对为 ( x, x3 ) 。 不规则码和规则 LDPC 码的 Tanner 图构造方式相同,只不过不规则码的校验节点 和变量节点的度一般不均匀、不相同。 当变量节点的度数越大时,变量节点就可以从更多的校验节点上获得更多的 信息,这样从而可以更容易准确判断它的值[12]。另外,当校验节点所连接的变量 节点越多,也就是校验节点度越大,这个校验节点对应的校验方程从变量节点上 引入的误差越大,校验方程不满足的概率更大。因此,从这个角度来说,应该减 小校验节点的度。这样出现了一对矛盾。不规则码和规则码相比各有优劣。不规 则 LDPC 码的出现就可以让这两种矛盾达到一个平衡,因为通过合理的构造不规
8

第二章 LDPC 码基础理论

则 LDPC 码可以使得构造的不规则 LDPC 码比规则 LDPC 码有着更好的性能[13], 并且具有较低的错误平层[14]。 本文实现的 LDPC 码就是一种不规则 LDPC 码。

2.2.2 环
LDPC 码所对应的环是指 Tanner 图中从一个节点出发,在变量节点和校验节 点之间经过,走若干步后回到起点,形成一个回路,这个回路就是环[15]。可以得 出,环的长度只能是大于等于 4 的偶数。 环的存在可以使译码器不能快速收敛,或者根本不能收敛[16]。因此,我们要 尽量避免短环的存在,至少不能存在四环(如图 2-2) 。当无环时,用和积译码算 法可以得到最佳译码的结果,否则,那么由和积译码算法得到的概率并非真正的 后验概率。可见,环的存在会使得译码的性能无法得到满足。但是,一般情况下, 码长是固定的,码字无环是不可能的,因此,我们要尽量减小短环,也就是增加 最小的环的长度,即增加围长。
m1 m2

zkq
m3

20151125
m4

图 2-2 四环

2.3 LDPC 码的构造方法
在 LDPC 码的性能中,除了码长、译码方法之外,其构造方式也是影响 LDPC 码性能的重要因素。在 Tanner 图中能够直观地表示出的对 LDPC 码性能重要的影 响因素就是环的长度。因此,在构造 LDPC 码的过程中,需要利用一定的方式来 构造 LDPC 码的校验矩阵。目前,构造 LDPC 码的方法一般分为两大类,结构化 构造法和随机构造法。下面对着两种 LDPC 码的构造方法进行分析和对比。

2.3.1

随机构造法

LDPC 码的校验矩阵的随机构造法是指先对校验矩阵的基本参数进行设定, 例 如节点的度分布序列、环长等,然后再利用计算机搜索的方法进行随机生成校验 矩阵。随机构造法一般包括以下几种方法:Gallager 法、Mackay 构造法、比特填 充与扩展比特填充方法等。
9

电子科技大学硕士学位论文

(1) Gallager 法 Gallager[3]利用 (n, j, k ) 表示一个规则的 LDPC 码, n 表示码长, j 表示行重, 即校验矩阵中每行中“1”元素的个数, k 表示列重,即校验矩阵中每列中“1”元素的 个数。Gallager 采用的构造方法为: (1)首先将校验矩阵按行分成 j 个子矩阵,保 证每个子矩阵中,每一列只有一个“1”。 (2)让子矩阵中,“1”元素呈现逐行下降的 形状排列,保证第 i 行中的 k 个“1”从第 (i ? 1)k ? 1 开始到 i ? k 为止。 (3)剩下的子矩 阵按照第一个诞生的子矩阵进行列随机变换。下图展示按照 Gallager 法构造的一 个规则 LDPC 校验矩阵。 如图 2-3 为利用 Gallager 法构造的一个(20,3,4)的 LDPC 码的校验矩阵。 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 zkq 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 20151125 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0

图 2-3 Gallager 法构造的校验矩阵

由 Gallager 法构造的矩阵有一些限制条件,如对于列重和行重的限制。这样 导致这种方法构造的校验矩阵的性能不理想,构造复杂度太大。 (2) Mackay 构造法 Mackay 构造的校验矩阵的特点是校验矩阵对应的 Tanner 图中的环数目最少, 同时加入列重为“2”的列[17]。Mackay 发明了四中方法来构造 LDPC 校验矩阵,这 样的结果是得到的矩阵没有“四环” 。四种方法如下: 方法一:对于 M ? N 的校验矩阵 H ,列重固定,行重在每行中均匀分布,并 且保证两列之间没有“四环” 。 方法二:校验矩阵 H 中,前 M / 2 的列列重为 2,这些列重为 2 的列由两个维 度为 (M/ 2) ? (M/ 2) 单位矩阵叠放而成。
10

第二章 LDPC 码基础理论

方法三:删除掉方法一和方法二中构造的矩阵的一部分列,使得校验矩阵对 应的 Tanner 图中没有周长为一个固定长度的短环(如六环) 。 (3) 比特填充与扩展比特填充法 比特填充法解决了两大问题,一是要求给定变量节点数 n 、变量节点度 a 、围 长 g 使得校验节点数尽可能地少;二是给定校验节点数 m 、变量节点数 n 、变量节 点度 a 、校验节点度 b ,并且保证 mb ? na 成立,要求尽可能使围长 g 值越大越好。 这种算法的具体步骤为: 假如已经有一个校验矩阵 H ,列重小于行重,即 a ? b ,围长为 g ;现在在校 验矩阵的基础上再增加一列作为 H 的第 (n ? 1) 列,其大小为 a ,初始为一个空的集 合 X 1 ,其实 {1, 2,…, m} 的一个子集。进一步循环操作,知道得到一个完整的校验 矩阵。 扩展比特填充法与比特填充法很类似,都是保证固定的 g ,用“1”来填充校验 矩阵。唯一不同的是整个操作的过程中,围长是保证不变。在最初算法执行的时 候,其围长为最大值 g max ,当列不能再加时,即不能继续填充比特时,减小最大 围长为 g max ? 2 ,然后继续进行算法。如此循环反复。另外,必然有一个围长变化 的最小值 g min ,当围长小于最小值的时候,算法停止。

2.3.2

结构化构造方法

zkq

20151125

随机构造矩阵方法由于随机特性的存在,所以没有固定的结构,导致编码的 复杂度急剧增加。结构化构造方法具有确定的结构,循环长度增加,具有循环码 结构或者准循环码结构,编码的具体实现比较简单。结构化构造校验矩阵方法具 体包括这几种方法: (1) 有限几何构造法 利用有限几何的知识,利用点和线来构造。例如有投影几何和欧式几何。几 何 X 具有 a 个点和 B 条线,满足以下条件: (a) 每一条线包含 c 个点; (b) 两点之间只有一条线; (c) 点只能落在 d 条直线上面; (d) 两条线或平行,或相交且仅有一个交点。 以上就是有限几何的方法构造了一个几何 X ,其与二元域上 B ? a 维校验矩阵

H i , j 相对应。矩阵中的行和列分别对应几何 X 中的线和点。如果第 i 条线包含 j 个
点,那么校验矩阵中的对应的位置 hi , j ? 1 ,否则 hi , j ? 0 。校验矩阵的行重为 c ,列 重为 d 。Yu Kou[18]等已经利用此方法构造出没有四环的循环码或者准循环码。

11

电子科技大学硕士学位论文

(2) 组合设计法 组合设计法可以用来构造没有四环的校验矩阵。首先定义一个参数为
(v, k , ? , r , b) 的数对 ( X , A) ,X 由 v 个元素组成一个集合,X 同时也被分为 b 个子集。

分的方法为:每个子集中定义包含 k 个点, X 中任取两点组成一个点对,不同点 对的数量就是 ? 。从 X 中任取一点都包含在 r 个不同的块中,从而得出 bk ? nr 并 且 ? (v ?1) ? r (k ?1) 。所以可以容易地得出, (v, k , ? , r , b) 中,只有 3 个参数相互独 立,一般使用前三个参数。 在校验矩阵中,若任意两行对应的连个位置出现了“1”,意味着出现了一个四 环。由于组合设计法得到的校验矩阵当 ? ? 1 时, X 中的每一个点只出现在 A 的一 个块中,因此,这种方法构造的校验矩阵不存在四环。

2.4 QC-LDPC 码的基本概念 2.4.1 QC-LDPC 码的基本概念和特点
LDPC 码在构造过程中的不同分为结构型码和随机型码,随机型码是指在 LDPC 码的校验矩阵中的“1”是随机生成的,其特点是码的性能比较好,但是编码 和译码比较复杂,不能实现简单编码和简单译码。而结构型 LDPC 码如 QC-LDPC 通过几何代数等方法构成[18],就可以实现部分并行编译码,大大减小了编译码的 复杂度,并且还可以有效避免短环的存在。 QC-LDPC 码的生成矩阵和校验矩阵都有着循环移位特性,编译码技术实现相 对比较简单。QC-LDPC 码的校验矩阵是由其对应的基矩阵表示,每个位置的值表 示的是单位矩阵循环移位的数量,这样可以减小校验矩阵的存储空间。

zkq

20151125

2.4.2

IEEE802.16e 协议中 QC-LDPC 码的应用

WiMax 是全球微波互联接入, 是一种宽带无线接入方式, 也叫 IEEE802.16e[19]。 此标准中 QC-LDPC 码的校验矩阵由基矩阵 H b 来表示,H b 是一个维度为 mb ? nb 的 矩阵(2-8),每一个元素 Pi , j 表示由一个维度为 z ? z 的单位矩阵向右移 Pi , j 个单位生 成的矩阵。

? P0,0 ? 1,0 ? P ? H b ? P2,0 ? ? ? ? ? Pmb ?1,0

P0,1 P 1,1 P2,1 Pmb ?1,1

P0,2 P 1,2 P2,2 Pmb ?1,2

P0,n b ?2 P 1,n b ? 2 P2,n b ?2 Pmb ?1,nb ?2

P0,n b ?1 ? ? P 1,n b ?1 ? P2,n b ?1 ? ? P Hb ? ? ? Pmb ?1,nb ?1 ? ?

(2-8)

12

第二章 LDPC 码基础理论

QC-LDPC 码的校验矩阵都是有基矩阵 H b 扩展成维度为 m ? n 的校验矩阵,其 中 m ? mb ? z, n ? nb ? z , z 指扩展因子。802.16e 中 H b 的列数都是 24,即 nb ? 24 。 码长为 n ,扩展因子 z ? n / 24 。那么每个 Pi , j 所表示的矩阵都是 z ? z 的单位阵 经过循环右移生成的,Pi , j 是有从 ?1 到 (z? 1) 之间的一个值, 除了 ?1 表示零矩阵外, 其他值都表示向右循环移位的值。802.16e 采用了用了四种码率,对于每一种码率 有 19 种码长。如表 2-1 中是三种码长和四种码率的信息比特的对应关系:
表 2-1 三种码长和四种码率下信息比特和码长的对应关系 n(bit) 576 1056 2304 z 24 44 96 k(byte) R=1/2 36 66 144 R=2/3 48 88 192 R=3/4 54 99 216 R=5/6 60 110 240

IEEE802.16e 协议中的校验矩阵都有着准双对角的结构,具有这种结构的 LDPC 码可以直接根据校验矩阵来编码,不需要将校验矩阵转化为生成矩阵[20]。
表 2-2 802.16e 协议中码率为 1/2,码长为 2304 的基矩阵
-1 -1 -1 61 -1 -1 -1 -1 12 -1 -1 43 94 27 -1 -1 -1 -1 -1 11 -1 -1 -1 -1 73 -1 -1 47 39 -1 95 73 -1 -1 7 -1 -1 -1 24 -1 -1 -1 53 -1 -1 -1 65 -1 -1 -1 22 -1 -1 46 -1 -1 83 -1 -1 -1 -1 22 81 -1 -1 40 -1 -1 24 94 -1 66 -1 79 -1 -1 84 -1 -1 2 -1 -1 -1 -1 -1 9 33 -1 -1 82 -1 -1 43 59 -1 41 55 -1 -1 65 -1 -1 -1 -1 -1 -1 39 -1 83 -1 -1 25 41 -1 14 47 -1 -1 49 -1

zkq -1
-1 -1 -1 72 -1 18 -1 -1 70 -1 -1

-1 0 -1 -1

20151125 7 0 -1
-1 -1 -1 -1 0 -1 -1 -1 -1 -1 7 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1

-1 -1 0 0 -1 -1 -1 -1 -1 -1 -1 -1

-1 -1 -1 0 0 -1 -1 -1 -1 -1 -1 -1

-1 -1 -1 -1 0 0 -1 -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 0 0 -1 -1 -1 -1 -1

-1 -1 -1 -1 -1 -1 0 0 -1 -1 -1 -1

-1 -1 -1 -1 -1 -1 -1 0 0 -1 -1 -1

-1 -1 -1 -1 -1 -1 -1 -1 0 0 -1 -1

-1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 -1

-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0

12

79 -1 -1 51 72 -1 26

如表 2-2 就是一个码率为 1/2 时的基矩阵,最后 12 列除了第一列外,后面 11 列是一个双对角线结构,因此称这个矩阵为准双对角线结构(矩阵中的“0”指单位 矩阵,“-1”指零矩阵) 。

2.5 本章小结
本章对 LDPC 的基本定义和概念进行了基本的分析,随后研究了几个关键概 念,如码率、校验矩阵、生成矩阵、度、行重和列重等概念,并简单对规则 LDPC
13

电子科技大学硕士学位论文

码和不规则 LDPC 码进行了性能等方面的比较。另外, 引出 QC-LDPC 的概念和特 性以及其优点,随后研究了 802.16e 协议下的 QC-LDPC 码的基矩阵的准双对角线 的特性。本章为后续章节的 LDPC 编码和译码奠定了基础。

Equation Chapter (Next) Section 1

14

第三章 LDPC 编码算法研究及硬件实现设计

第三章

LDPC 编码算法研究及硬件实现设计

3.1 LDPC 码的编码算法
LDPC 是一种线性分组码,其编码算法与线性分组码的编码算法基本相似。基 本上可以分为三种:生成矩阵法、高斯消去法和专门针对近似下三角矩阵的简化 Efficient 编码算法。 这几种算法各有优劣。 在实现的过程中, 主要根据所选的 LDPC 码型来确定选择编码算法。下面对这几种算法进行简要分析。

3.1.1

生成矩阵算法

LDPC 码是一种线性分组码,因此可以用线性分组码通用的方法来编码,可以 根据校验矩阵 H 求出生成矩阵 G 。 比如信息比特用 m 来表示, 编码后的码字用 c 来 表示。则根据 c ? m ? G 就可以很容易进行编码。因此,生成矩阵算法的难点就在 于求生成矩阵 G 。 生成矩阵可以通过对校验矩阵进行高斯消去法来进行矩阵的初等变换来求 出,设校验矩阵可以分为两部分: H ? [ H1 | H 2 ] ,设 n 是码长, k 是信息位的位数,

m ? n ? k 是校验位的位数。其中 H 2 是一个维度是 m ? m 的矩阵。将矩阵 H 进行初
等变换,则可以将该矩阵变为形式为 H ? [ X , I m ] 的矩阵,其中 I m 为 m 维的单位矩 阵。 根据校验矩阵 H 和生成矩阵 G 的定义 H ? cT ? 0 和 c ? m ? G 可以得出:

H ?G ? 0

(3-1)

因此,显然根据 H ? [ X , I m ] 可以求出生成矩阵的值为 G ? [ I k , X T ] 。这是矩阵

H 2 是满秩的情况,当不是满秩的时候就需要进行矩阵在二元域下的行初等变换或
列初等变换,这样就可以求出生成矩阵。 这种算法进行编码时,只需要求一次生成矩阵,比较简单,但是这种算法得 到的生成矩阵一般不是稀疏矩阵[21]。 另外这种算法对于 QC-LDPC 码来说计算也比 较复杂,不如直接用校验矩阵进行编码。

3.1.2

高斯消元法编码算法

根据 LDPC 码的校验矩阵 H 来求出生成矩阵 G 的方法来编码比较复杂,一般 常用的算法包括高斯消元法和专门针对准双对角线结构的校验矩阵的 Efficient 算 法。

15

电子科技大学硕士学位论文

高斯消元法就是将校验矩阵经过行初等变换将校验矩阵中产生一个如图 3-1 的下三角矩阵[22]。

k

m

m

图 3-1 校验矩阵经过高斯消元法后的矩阵

利用高斯消元法对校验矩阵 H 经过变换出一个下三角矩阵后为 H ? ,由于编码 后的 LDPC 码 c 满足: H ? cT ? 0 。设编码前为 s ,经过编码后 c ? [s, p] ,其中

p ? [ p0 , p1

pm? 1 ]。因此,求 p 只需要按照下面的算法来求:

首先,将信息比特直接赋给向量 s ,以便下面代入方程。 然后,对于 H 矩阵第 i 行满足方程:

H i? ? ?s, p ? ? ? s j ? H i?, j ? ? p j ? H i?, j ?k ? 0
j ?0 j ?0

k ?1

i

(3-2)

从 i ? 1 开始, 可以根据上式求出 p0 , 然后 i ? i ? 1 , 继续代入(3-2)即可求出 pi ?1 , 不断循环直到求出最后一个 P 的值 pm?1 。这样就求出了所有的校验位的值。 这种算法可以比较简单地求出校验位,但是利用高斯消元法使得原先的校验 矩阵中的“1”位置发生了变化,这样使得原先校验矩阵的随机性发生了变化,即 稀疏性发生变化。

3.1.3

Efficient 编码算法

Efficient 编码算法可以对任何类型的 LDPC 码进行编码, 这种算法使得校验矩 阵转化为具有特殊结构的校验矩阵,然后再进行编码。首先将校验矩阵进过简单 的行初等变换,使矩阵右上角出现一个下三角矩阵(如图 3-2) 。

A

B

T

C

D

E

图 3-2 校验矩阵转化后得到的近似下三角矩阵

16

第三章 LDPC 编码算法研究及硬件实现设计

在上式中, 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 ? 。
校验矩阵 H 进过初等变换后为 H ? 。

?A B T ? H? ? ? ? ?C D E ?
首先,将 H ? 左乘以以下矩阵:

(3-3)

0? ? I X ?? ?1 I? ? ? ET ?
得到:

(3-4)

A B T? ? XH ? ? ? ? ?1 -1 ? ? ET A ? C ? ET B ? D 0 ?
的 g 位, p1 对应校验位的 m ? g 位。那么编码后的码字为 c ? ? m, p0 , p1 ? 。 根据校验矩阵和码的关系:
H ? cT ? 0

(3-5)

码字的信息位用 m 表示,校验位用 p = ? p0 , p1 ? 来表示,其中 p0 中包含校验位

(3-6)

可以得到:

H?? c ? 0 XH ? ? c ? 0
代入可以得到:
T T A ? sT ? B ? p0 ? T ? p1 ?0

(3-7) (3-8)

(3-9) (3-10)

? ?ET

?1

T A ? C ? ? sT ? ? ? ET ?1B ? D ? ? p0 ?0

根据(3-10)可以求出:
T p0 ? ? ? ? ET ?1B ? D ? ? ? ? ET ?1 A ? C ? ? sT ?1

(3-11)

最后将求出的 p0 代入(3-9)则可以求出 p1 的值。 最后就得到了所要的码字:

T

c ? ? s, p0 , p1 ?

(3-12)

17

电子科技大学硕士学位论文

3.1.4

适用于 802.16e 的简化 Efficient 编码算法

IEEE802.16e 标准下的 LDPC 码有着特殊的结构, 其校验矩阵是一个准双对角 线结构(如表 2-2) ,用上节提到的 Efficient 算法也可比较简答的求出。下面研究 一种简化的更便捷的编码方式[23]。编码步骤如下: IEEE802.16e 标准下校验矩阵的特殊结构如下(码率为 0.5) :
? P0,0 ? 1,0 ? P ? P ? 2,0 Hb ? ? ? ? ?P ? mb ?1,0 ? ? Pmb ,0 P0,1 P 1,1 P2,1 P0,kb ?1 P 1,k b ?1 P2,k b ?1 P0,k b P 1,k b 0 0 ?1 0 0 ?1 ?1 ?1? ? ?1 ?1 ?1? ?1 ?1 ?1? ? ?1? ? 0 0 ?1? ?1 0 0 ? ? ?1 ?1 0 ? ?

P2,k b ?1 | |

(3-13)

?1 ?1 Pmb ,1 Pmb ,1 Pmb ,kb ?1 Pmb ,k b ?1 ?1 ?1 ?1 P P
mb ,k b ?1 mb ,k b

上述矩阵为基矩阵, 每一个 Pi , j 都表示将维度是 z ? z 的单位阵向右循环移位的 单位数,将其简化为
Hb ? ? ? H bI | Hbp ? ??? ? HbI | Hbp1 | Hbp 2 ? ?

(3-14)

将基矩阵转化为校验矩阵:
H ?? ? H I | H p1 | H p 2 ? ? Q0,1 Q0,kb ?1 Q0,k b ? Q0,0 ? Q1,1 Q1,kb ?1 Q1,k b ? Q1,0 ? Q Q2,1 Q2,k b ?1 Q2,k b ? 2,0 ?? | ? ? ?Q Qmb ,1 Qmb ,kb ?1 Qmb ,kb ? mb ?1,0 ? Qmb ,kb ?1 Qmb ,kb ? Qmb ,0 Qmb ,1

I 0 I I 0 I | 0 0 0 0 0 0

0 0 0? ? 0 0 0? 0 0 0? ? 0? ? I I 0? 0 I I? ? 0 0 I? ?

(3-15)

上式中 Qi , j 表示将维度为 z ? z 的单位阵向右循环移位 Pi , j 个单位生成的矩阵。
I 表示单位阵,其他为零矩阵。

编码后的 LDPC 码为:

c ? ? s, P 1, P 2?
s?? ? s0 , s1 skb ?1 ? ?

(3-16) (3-17) (3-18)

P 1 ? ? p0 ?
18

第三章 LDPC 编码算法研究及硬件实现设计

P2 ? ? ? p1 , p2

pmb ?1 ? ?

(3-19)

根据校验矩阵和编码后码字的关系 H ? c ? 0 可以得出:

H I ? s ? H p1 ? P 1 ? H p2 ? P 2 ?0
化简为方程组为:
kb ?1 j ?0 kb ?1 j ?0

(3-20)

? Q0, j ? s j ? Q0,kb ? p0 ? p1 ? 0

(3-21) (3-22)

? Q1, j ? s j ? Q1,kb ? p0 ? p1 ? p2 ? 0

kb ?1 j ?0

? Qi , j ? s j ? Qi ,kb ? p0 ? pi ?1 ? p2 ? 0

(3-23)

kb ?1 j ?0

? Qmb ?1, j ? s j ? Qmb ?1,kb ? p0 ? pmb ?1 ? 0

(3-24)

将方程(3-21)到方程(3-24)全部在二元域上相加,可以得到:
mb ?1 kb ?1

? mb ?1 ? ? ? Qi , j ? s j ? ? ? Qi ,kb ? ? p0 ? 0 i ?0 j ?0 ? i ?0 ?

(3-25)

根据式(3-25)可以求出 p0 :
mb ?1 kb ?1

p0 ? ?

i ?0 j ?0

? ? Qi , j ? s j ? mb ?1 Q ? ? ? i ,kb ? ? i ?0 ?

(3-26)

将 p0 的值代入公式(3-22)可以求出 p1 的值。依此类推,通过第 i 个方程可以求 出 pi 的值,将 pi 的值代入第 ? i ? 1? 个方程可以求出 pi ?1 。这样可以求出所有的校验 位的值 P1 和 P2 。 以上就是适合 IEEE802.16e 协议的校验方程结构的 Efficient 算法。 这种算法的 优势在于不需要进行高斯消元,校验矩阵的稀疏特性得以保证,不会被破坏,这 样 LDPC 码的性能也不会受编码的影响。

19

电子科技大学硕士学位论文

3.2 LDPC 码编码器的硬件实现 3.2.1 LDPC 编码器硬件实现结构分析

本设计使用的是 802.16e 协议中的 LDPC 码进行设计,实现了四种码率(1/2、 2/3、3/4、5/6) ,最大码长为 2304 的 LDPC 编码。 从上一节可以看出,QC-LDPC 的编码算法主要包括循环移位,模二加等。设 计框图如图 3-3,整个设计采用了流水线的思想。 所谓流水线技术,就是如同生产过程中的转配流水线一样,将复杂的工序分 成很多工作量相当的小模块,每个小模块都协同工作,这样的结果是整个系统的 工作速度只取决于流水线的输入速度,这样以来,理想的流水线操作运行效率可 以大大提高。在硬件设计中利用流水线技术可以将复杂的运算分成很多个模块来 实现,这样就把复杂的运算分配到多个时钟周期内,减轻每个时钟周期可以执行 的任务减少。因此,利用流水线技术可以提高编码的时钟周期。 下图是整个编码的设计框图:
s p1 Cycle_shift Register xor Cycle_shift xor p2

Cycle_shift Data_in Buffer

Register

xor

p3
M U X

Data_out

Cycle_shift

Register

xor

p4

Cycle_shift

Register

xor

p5

????

图 3-3 编码硬件实现框图

下面对编码设计框图中的各个模块做一个研究, 研究的过程中以码长为 2304、 码率为 1/2 为例: (1)BUFFER 模块

20

第三章 LDPC 编码算法研究及硬件实现设计

BUFFER 模块对进入编码器的数据进行一个缓存,数据 data_in 指进入编码器 待编码的数据,由于是 QC-LDPC 编码,扩展因子为 z ? 96 。因此,进入系统的数 据格式设定为每个时钟进入 96 比特,对于码长为 2304 的编码,输入一帧数据需 要 12 个时钟周期将一个码字输入完毕。data_in_flag 是开始输入数据标志,和第一 个数据一起进入编码器。之所以每个时钟只输入 z ? 96 个数据,是考虑到译码需要 用到的时间。如果,如果增加 data_in 的位宽,就会出现第一帧码字还没有编码完 成,第二帧数据就来的结果。因此,将输入位宽定义成 96 比特是必须的。 BUFFER 在对进入编码器的数据进行缓存的同时,将一路数据变为 12 路,分 别对应校验矩阵的 12 行,12 行同时进行计算累加。这里用了全并行的思想,当多 路数据互不影响,相互独立,可以在同一个时间进行运算时,就可以用全并行的 思想,由于本算法运算复杂度不高,因此,这里的全并行并不会对资源消耗产生 过大的影响。 (2)cycle_shift 模块 在 QC-LDPC 中,编码时需要将 96 比特为一组的数据以 z ? 96 为单位向右循 环移位。具体设计框图如图 3-4。

clk_main rst data_need_shift[95:0]
shift_num[6:0] Cycle_shift Data_after_shift[95:0]

图 3-4 循环移位模块输入输出

(3)加法模块 根据 Efficient 算法中的公式(3-25)可以知道校验矩阵的每一行都对应一个加法 器,为了求得 ? ? Qi , j ? s j ,必须求所有行的值, ? Qi , j ? s j 表示第 i 行对应的值。
i ?0 j ?0 j ?0 mb ?1 kb ?1 kb ?1

如图 3-5 为 add_unit 的模块输入输出:
clk_main
rst data_in[95:0]

Add_unit

Data_after_shift[95:0]

H_value[7:0]
data_in_flag

图 3-5 add_unit 模块输入输出

21

电子科技大学硕士学位论文

如图 3-5 所示,除了时钟 clk_main、复位信号 rst、数据输入外,还需要输入 校验矩阵每一行的值 H_value,作为循环移位的位移量。12 路 add_unit 全部计算 完之后将这 12 路值全部加起来得到 ? ? Qi , j ? s j ,这样就可以根据式(3-25)求出
i ?0 j ?0 mb ?1 kb ?1

p0 的值。将此值代入第二行就可以求出 p1 的值。如此类推就可以求出所有的校验
位的值,这些校验值通过 MUX 的控制下依次输出。就可以得到编码后的码字,如 图 3-3。

3.2.2

LDPC 编码器硬件实现仿真

上一小节主要讲述了 LDPC 编码器的结构设计,本节主要对编码的设计进行 仿真及其测试。综合主要用了 Xilinx 公司的 ISE 软件,仿真用了 Altera 公司的 Modelsim 软件。如图 3-6 为利用 Modelsim 软件仿真得出的编码器输入数据格式, 从下图中可以看出经过 12 个时钟周期,第一帧码字输入完毕,于此同时,在每一 帧的开始第一个时钟周期内,数据输入标志 data_in_flag 高有效。

图 3-6 编码器输入格式

仿真测试方式:用 matlab 产生编码前的随机序列,编码后将正确的编码后的 值输出到文本文件中,在 Modelsim 的 textbench 文件中添加代码将文本文件中 的数据读入 Modelsim,将正确的编码结果和仿真出的结果做一个差,如果结果全 是零,则说明仿真结果是正确的。如图 3-7 是整个译码器关键数据的仿真图,译码 器中的每一个重要的数据都在下面的仿真图里正确地显示。

图 3-7 编码器中关键信号的仿真波形

22

第三章 LDPC 编码算法研究及硬件实现设计

3.3 本章小结
本章首先对 QC-LDPC 编码算法进行了研究,如生成矩阵算法、高斯消元编码 算法、Efficient 编码算法等。对各个算法进行了研究对比,然后根据 802.16e 的校 验矩阵特点选择了适用的简化 Efficient 算法。最后,对编码器硬件实现仿真结果 进行了分析和研究。实现了一个多码率 LDPC 编码器,码率分别为 1/2,2/3,3/4, 5/6。码长为 2304。

Equation Chapter (Next) Section 1

23

电子科技大学硕士学位论文

第四章

LDPC 译码算法研究及硬件实现设计

本章主要根据 LDPC 译码的发展历程研究了三种 LDPC 译码算法:基于概率 测度的 BP(Belief Propagation)译码算法、基于 LLR 的 BP 译码算法、最小和译码算 法。并将这三种算法做了对比,最终选用了适合硬件实现的最小和译码算法。为 了进一步提高译码器的性能,本文采用修正的最小和译码算法。 另外,本章也主要研究了最小和译码算法的两种不同实现结构:TDMP 译码 实现和 TPMP 译码实现。 将这两种结构进行了仿真对比, 最终选用的是基于 TDMP 结构的水平分层迭代译码算法。最后,详细研究了硬件实现的结构特点和具体的 参数。

4.1 LDPC 译码算法分析
LDPC 译码算法主要是分为两大类:硬判决算法和软判决算法。自从 1962 年 LDPC 码被 Gallager 提出时, Gallager 同时给出了一种译码算法, 即 BF (Bit Flipping) 译码算法 ,也就是比特翻转译码算法[24]。硬判决算法的优势在于只需要做判断和 加法运算,不仅运算量小,而且复杂度也比较低,比较实用。其缺点是性能比较 低,并且译码时长不确定。而对于软判决来说,可以比较更加充分地利用信道信 息,通过迭代译码算法,使得其译码性能无限接近香农极限。这两种算法都是基 于消息传递算法(Message Passing Algorithms) ,在译码过程中,每个节点的消息 在 Tanner 图中不断传递,区别在于量化的比特数的区别,硬判决是将受到的信息 判决为 0 或 1,而软判决算法是将受到的信息量化为多比特,使得受到的信息更加 细化。 对于软判决算法主要包括基于概率测度的 BP 译码算法、基于 LLR 的译码算 法、最小和译码算法以及简化的最小和译码算法。下面将对这几种译码算法做一 个研究。

4.1.1

比特翻转译码算法

比特翻转译码算法(Bit Flipping)由 Gallager 在 60 年代提出,当传输结果发 生错误时, 接受到的信息经过校验得到校验向量 S ? ? s0 , s1 ,…,sM ?1 ? 来表示,S 可以 反映出校验信息失败的比特。 当接受到的信息序列 Z 发生错误时,S 中的某些比特 就会发生错误,校验向量 S 发生改变,这就是 BF 算法的基本原理。 BF 算法首先统计不满足的校验结果,找出使得校验方程不成立的个数超过门
24

第四章 LDPC 译码算法研究及硬件实现设计

限值(Threshold)的比特,然后将这些点进行翻转,这样完成了一次迭代,继续 不断重复迭代,知道所有的比特都满足校验方程。或者设置一个最大迭代次数门 限值 ? ,当迭代次数达到 ? 后,不论迭代有没有得到正确的结果,都立即停止,视 为译码失败。 比特译码算法的具体步骤如下: (1) 接收序列为 Z ,迭代次数为 k ? 1 ; (2) 利用校验矩阵计算相对应的校验方程。如果所有对应的校验方程都满 足( S k ? 0 ) ,则停止译码,结果为正确的值。否则进入下一步; (3) 计算每一个比特所对应的不成立的校验的方程的数目,将此作为是否 翻转的依据, fi k , ? i ? 0,…,N ? 1? ,上式中 fi k ? ?i?C (j) s k j ; (4) 从序列 fi k , ? i ? 0,…, N ? 1? 中找出最大值对应的信息比特所在的位置
?;
k (5) 翻转位置为 ? 的比特的值 Z ? ;将 0 变为 1,将 1 变为 0;

(6) 如果已经达到了最大迭代次数,那么停止译码,译码失败;否则,迭 代次数 k 加 1,进入步骤(2)开始下一次迭代。 从上述译码步骤中可以看出,BF 算法比较简单,只有模二加运算。 另一种改进的 BF 译码算法 Iterate F-BF 译码算法是对上述算法的修改,修改 过后的算法可以将迭代得到的判断依据同时引入到下一次的迭代过程。比如第 k
k k 次的迭代依据是 fi k ? 0, ? i ? 0,…,N ? 1? ,译码得到结果 Z k ? ? z0 , z1k ,…,zN ?1 ? 。在

k 次迭代结束之前,修改并保存 fi k ,其规则为:在第 k 次迭代过程中被翻转的比 特 Z ? 对应的判断依据 f ? 设置成最不可能被翻转的值。 改进的比特翻转算法流程为: (1) 接收序列为 Z ,迭代次数为 k ? 1 ; (2) 利 用 校 验 矩 阵 计 算 出 所 对 应 的 校 验 方 程 。 如 果 校 验 方 程 都 满 足 ( Sk ? 0) ,就可以停止译码,结果为正确的值。否则进入下一步; (3) 计算每一个比特对应的不成立的校验的方程的数目,将此作为是否翻 转的依据, fi k , ? i ? 0,…,N ? 1? ,上式中 fi k ? ?i?C (j) s k j ;
k ? fi k ?1 ? w ,系数 w 可以再 0 ? 1 之间设 (4) 计算第 k ? 1 次的迭代判据 fi k ? f zi

置。 (5) 查找 fi k , ? i ? 0,…,N ? 1? 中最大比特所在的位置 ? ;
k (6) 翻转位置为 ? 的比特的值 Z ? ;将 0 变为 1,将 1 变为 0;

(7) 如果已经达到了最大迭代次数,那么停止译码,译码失败;否则,迭 代次数 k 加 1,进入步骤(2)开始下一次迭代。
25

电子科技大学硕士学位论文

以上就是 BF 算法、改进的 BF 算法的详细流程。BF 算法虽然算法复杂低,消 耗资源也比较少,但是由于其性能不高,现在应用此方法来译码的情况也很少见。

4.1.2

基于概率测度的 BP 译码算法

当发送的消息序列经过编码、调制后,经过信道到达接收端,由于信道中噪 声的存在会使得错误发生,在译码之前,我们可以根据信道信息、接收到的值来 求出初始信道概率信息。初始信道信息也叫先验概率,定义如下。 下面都以调制方式为 BPSK、信道为 AWGN 信道下的定义:

fi 0 ? P{x ? ?1| yi } ?

P{ yi | xi ? ?1} 1 ? P{ yi | xi ? ?1} ? P{ yi | xi ? ?1} 1 ? exp(2 yi / ? 2 )

(4-1) (4-2)

fi1 ? P{x ? ?1| yi } ? 1 ? fi (0) ?
下面对算法中用到的符号进行定义:

1 1 ? exp(?2 yi / ? 2 )

fi a : 接收端接收到的信号的第 i 个符号 xi ? a 的先验概率, 计算方式为如式(4-1)
和式(4-2);
N ( j ) :表示与第 j 个校验节点所相连的变量节点的集合; N ( j ) \ i :表示与第 j 个校验节点所相连的变量节点的集合中去掉相连的第 i 个

变量节点;
M (i) :表示与第 i 个变量节点所相连的校验节点的集合;

表示与第 i 个变量节点所相连的校验节点的集合中除掉相连的第 j 个 M (i) \ j : 校验节点;
( k ), a qij :表示第 k 次迭代中的,从第 j 个变量节点传递到第 i 个校验节点的信息

xn 被判断为 a 的概率,其中 a ? 0,1 ;
rij( k ),a :表示第 k 次迭代中的,从第 i 个校验节点的信息传递到第 j 个变量节点
的信息 xn 被判决为 a 的概率,其中 a ? 0,1 ;

q (jk ),a :表示经过第 k 次迭代译码后得到的变量节点 j 的值满足 x j ? a 的后验概
率。 下面是基于概率测度算法的译码算法的步骤: 首先是进行初始化,根据公式(4-1)和(4-2)求出先验概率的值 fi a 并且把它赋值
(0), a 给 qij ,另外将 rij( k ),a 初始化为 0:
(0), a qij ? fi a

(4-3) (4-4)

rij( k ),a ? 0

26

第四章 LDPC 译码算法研究及硬件实现设计

初始化后进入迭代过程,初始化迭代次数为 1,进入以下三个步骤: (1)水平迭代过程: 水平迭代的处理单元叫做 CNU(Check Nodes Update),水平迭代即变量节点对 校验节点的更新,计算公式如下:

? ( k ),0 1 1 (k ?1),0 ?1),1 ? qi(k ) ?j ?rij ? 2 ? 2 ? (qi?j i ?? N ( j )\ i ? ? ?1),1 ?1),0 ? r ( k ),1 ? 1 ? 1 (qi(k ? qi(k ) ?j ?j ? ij ? 2 2 i?? N ( j )\i ?

(4-5)

上式中 k 表示迭代次数。下图为 Tanner 图中的一个局部图,显示出了 CNU 模 块前后的数据流。其中 V1、V2、V3 表示三个变量节点,表示水平迭代前后的数 据来源,其中 1,2 表示前面一个步骤中校验节点从变量节点获得的信息,而 3 代表 的实线部分表示当前步骤的数据流。
V1 2 CNU 1 V2

3 V3
图 4-1 Tanner 图中译码迭代数据流(1)
a 图 4-1 中的虚线 1 表示第 k 次迭代中来自变量节点 1 的数据 q (k), 2 表示第 k 次 j ,1 ,

a 迭代中来自变量 2 的数据 q (k), j ,2 。

(2)垂直迭代过程: 垂直迭代的处理单元叫做 VNU(Value Nodes Update),垂直迭代当变量节点更 新完校验节点后,校验节点对变量节点的更新,计算公式如下:
( k ),0 ?qij ? Kij ? fi 0 ? ? (rij(?k ),0 ) ? j ?? M ( i )\ j ? ( k ),1 1 ( k ),1 ? qij ? Kij ? fi ? ? (rij? ) j ?? M ( i )\ j ?

(4-6)

( k ),0 ( k ),1 ? qij ? 1 成立。垂直迭代 在(4-6)中 K ij 表示修正系数,这个系数可以使得 qij

过程的数据流图 4-2 可以知道 C1、C2、C3 和 C4 表示四个校验节点,虚线表示上
27

电子科技大学硕士学位论文

一个步骤校验节点处理的数据给到 VNU 单元,实现表示当前处理的过程。这就是 垂直迭代过程的主要运算。
C1 C2 2 3 VNU 4 C4
图 4-2 Tanner 图中译码迭代数据流(2)

C1 1 Vi

C3

(3)校验部分 经过水平迭代和垂直迭代后的译码完成了一次迭代,每次迭代完都需要进行 校验,来判断是否校验成功。变量节点完成更新后获得更新后的先验信息:

?q (jk ),0 ? Kij ? fi 0 ? ? (rij('k ),0 ) ? j' ? M (i ) ? ( k ),1 1 ( k ),1 ? q j ? Kij ? fi ? '? (rij ' ) j ? M (i ) ?

(4-7)

将获得的信息序列 c 参与校验 H ? cT ? 0 ,如果满足所有的校验方程,那么说 明此次译码成功,否则若达到最大迭代次数,译码失败,否则进入步骤(1)开始 下一次迭代。

4.1.3

基于对数似然比的 BP 译码算法

基于概率测度的 BP 译码算法有很多缺陷:比如不适合量化、算法实现复杂度 较高等。因此,在硬件实现的时候,一般不会采用基于概率测度的译码算法。基 于对数似然比(LLR)的译码算法,不仅适合量化,实现复杂度还比较低。 在研究此算法之前,首先对一些必要的符号进行定义:

Qv0 :信道信息初始化后传递给变量节点的初始值;

Qck,v :表示第 k 次迭代中,从变量节点 v 传递给校验节点 c 的信息;

Rck,v :表示第 k 次迭代中,从校验节点 c 传递给变量节点 v 的信息;
Qvk :表示经过 k 次迭代后,变量节点的 LLR 值。
首先,获得信道传输来的信息后要进行初始化信道信息。将信道信息转化为 对数似然比 LLR。对于对数似然比 L( x) 的值得定义为:

28

第四章 LDPC 译码算法研究及硬件实现设计

L( x) ? ln

P( x ? 0 | yi ) f0 ? ln i 1 P( x ? 1| yi ) fi

(4-8)

当信道为 AWGN 信道,调制方式为 BPSK 的情况下,将式(4-1)和式(4-2)代入 上式可以求得:

L(x) ? ln

fi 0 1 ? exp(2 yi / ? 2 ) ? ln f i1 1 ? exp(?2 yi / ? 2 )
(4-9)

? 1 ? exp(?2 yi / ? 2 ) ? ? exp(2 yi / ? 2 ) ? ? ? ln 1 ? exp(?2 yi / ? 2 )
2 ? ln ? ?exp(2 yi / ? ) ? ?

? 2 yi / ? 2
当初始信息被更新后,就开始以下的迭代过程。 (1) 校验节点的更新(水平方向迭代) 根据上一次迭代得到的变量节点的信息求出本次迭代的校验节点的信息:

Rck,v ? ? ?1 (

n?N ( c )\ v

?

1 ?(Qck,? n ))

(4-10)

上式中, ?( x) 表示双曲正切函数:

1 ex ?1 ?( x) ? tanh( x) ? x 2 e ?1
? ?1 ( x) ? ln 1? x 1? x

(4-11) (4-12)

(2) 变量节点的更新(垂直方向迭代) 根据本次迭代校验节点得到的值进行运算可以对变量节点进行更新。计算公 式为:
1 Qck,v ? Qck,? v ? m?M ( v )\ c

?

k Rm ,v

(4-13)

经过更新后,变量节点处的后验信息也发生了变化:

Qvk ? Qvk ?1 ?
(3) 译码判决模块

m?M ( v )

?

k Rm ,v

(4-14)

通过将各个不同变量节点的后验信息结合校验矩阵进行判决,首先先根据每 个变量节点的后验概率值的符号位判断其二进制取值:

29

电子科技大学硕士学位论文

?0, Qvk ? 0 xi ? ? k ?1, Qv ? 0

(4-15)

然后就可以得到译码的结果序列 c ? ? x0 , x1 ,…,xn ? ,再利用其编码所用的校验 方程来进行验证:
H ? cT ? 0

(4-16)

如果译码结果可以满足式(4-16),那么说明此次译码已经成功,停止译码,译 码结束。否则如果达到译码器初始化时设定的最大迭代次数,那么译码结果失败 且译码过程结束。如果既没有译码成功,同时也没有达到最大的设定好的迭代次 数,那么就可以继续下一次迭代,从第(2)步继续译码,如此循环。

4.1.4

最小和译码算法

从以上算法中可以看出,基于概率测度和基于 LLR 的 BP 译码算法都含有比 较复杂的算法,不适合硬件实现,比如基于对数似然比的 BP 算法中的校验节点更 新模块包含有双曲正切函数。 因此, 要想使得译码算法适合硬件实现, 必须将以上算法进行简化, Fossorier[25] 根据双曲正切函数的特点,将基于对数似然比的 BP 译码算法进行简化,从而得到 了最小和译码算法。 由于 tanh(x) 和 tanh ?1 (x) 是奇函数,因此,我们可以得到:
tanh(x) ? sgn(x) ? tanh(| x |)

(4-17) (4-18)

tanh ?1 (x) ? sgn(x) ? tanh ?1 (| x |)
根据式(4-17)和式(4-18)可以做如下简化:
Rck,v ? 2 tanh ?1 ( ? 2 tanh ?1[ ?2 1 1 tanh( Qck,? n )) 2 n?N ( c )\ v

?

n?N ( c )\ v

?

1 sgn(Qck,? n )?

1 1 tanh( | Qck,? n |)] 2 n?N ( c )\ v

?

(4-19)

n?N ( c )\ v

?

1 ?1 sgn(Qck,? n ) ? tanh [

1 1 tanh( | Qck,? n |)] 2 n?N ( c )\ v

?

根据 tanh(| x |) 在 0-1 之间为单调递增函数的性质可以得到:
1 1 k ?1 1 1 1 tanh( | Qck,? min | Qck,? n |) ? min tanh( | Qc , n |) ? tanh( n |) n?N ( c )\ v n?N ( c )\ v 2 2 2 n?N ( c )\ v

?

(4-20)

这样,经过简化,可以把式(4-10)简化为:

30

第四章 LDPC 译码算法研究及硬件实现设计

Rck,v ?

n?N ( c )\ v

?

1 k ?1 sgn(Qck,? n ) ? min (| Qc , n |) n?N ( c )\ v

(4-21)

由于简化的误差,通过上式得到的值比和积译码算法得到的值要偏大,因此, 我们需要对式(4-21)所求得的值进行修正,对 Rck,v 有以下两种修正方式: (1) 归一化最小和译码算法(Normalized Min-Sum Algorithm) 本算法将校验节点所求得的 Rck,v 乘以一个修正因子 ? :

Rck,v ? ? ?

n?N ( c )\ v

?

1 k ?1 sgn(Qck,? n ) ? min (| Qc , n |) n?N ( c )\ v

(4-22)

? 的取值范围是 0 ? 1 。
(2)偏移量最小和译码算法(Offset Min-Sum Algorithm) 本算法将校验节点所求得到的 Rck,v 减去一个值,以此来达到减小校验 节点值得目的。

Rck,v ? ? ?

n?N ( c )\ v

?

1 k ?1 sgn(Qck,? 0} n ) ? max{ min (| Qc , n |)-?, n?N ( c )\ v

(4-23)

如果校验节点值大于 ? ,那么修正后的值就是原来值减去 ? 的差,否则,校验 节点的值就是零。 总之, 最小和译码算法包括两种修正方式, 在这两种方式中, 修正系数和 LDPC 译码器的译码性能息息相关。 如果 ? 或者 ? 的值选择不当, 则有可能加剧译码误差, 使得译码性能急剧下降,因此,选择 ? 或者 ? 的值尤其重要。 在实现的过程中,我们通常用仿真工具来对不同的修正系数下 LDPC 译码器 的译码性能进行仿真,通过根据仿真结果来选择适当的修正因子值[26]。

4.1.5

译码算法性能比较

前面研究了两大类 LDPC 译码算法:硬判决算法和软判决算法。硬判决累算 法由于其译码性能比较差,所以在实践中很少使用。软判决算法包括基于概率测 度的 BP 译码算法、基于对数似然比的 BP 译码算法、最小和译码算法以及修正的
译码性能 对比 实现复杂 度对比

基于概率测 度的BP译码 算法

> <

基于LLR的 BP译码算法

> <

最小和译码 算法

图 4-3 三种译码算法的性能及实现复杂度比较

最小和译码算法。这几种软判决算法中,算法复杂度依次降低,意味着硬件实现
31

电子科技大学硕士学位论文

的复杂度也依次降低。 虽然修正最小和译码算法在硬件实现上具有复杂度低、占用硬件资源较少等 优点,但是同时这些算法的性能也是依次降低的[27](如图 4-3) 。 通过仿真及综合考虑,目前 LDPC 译码器的硬件实现几乎都采用的是最小和 译码算法。虽然性能有所损失,但是综合考虑,硬件实现复杂度降低带来的好处 远远超过了性能损失带来的坏处。

4.2 LDPC 译码器关键参数的仿真
前面两节完成了对 LDPC 译码器的算法分析和仿真。本节承上启下,连接算 法与硬件实现。对于硬件实现所必须的一些参数进行仿真并确定,为后续的硬件 实现做铺垫。比如量化范围、定点位宽、最大迭代次数、归一化最小和的系数等 信息。下面将对这些参数的确定进行必要的仿真。 仿真的条件为:BPSK 调制、噪声信道为 AWGN 信道、码长为 2304、码率以 1/2 为例进行仿真。

4.2.1

量化范围及量化位宽的确定
??1, s ? 0 x?? ? ?1, s ? 1

在编码之前,数据都是有 0 和 1 构成,经过 BPSK 调制后发送的数据为: (4-24)

调制后得到的符号 ?1 在传递的过程中会加入噪声。 AWGN 信道( Additive White Gaussian Noise)是加性高斯白噪声信道。加性体现在噪声是直接加到发送 的符号上的,比如发送的符号是 x ,噪声为 n ,接收到的符号是 y ,那么存在如下 关系:

y ? x?n
高斯的含义是指噪声的幅度服从高斯分布:
? ? x ? ? ?2 ? f (x) ? exp ? ? ? 2 ? ? 2?? 2 ? ? ? 1

(4-25)

(4-26)

服从高斯分布又叫服从正太分布, 用 X ~ N ? ? , ? 2 ? 表示 X 服从正太分布。 ?表 示正太分布的对称轴, ? 2 表示噪声的功率。 图 4-4 表示出了加到符号 ?1 上的噪声的概率。如下图为接收到的 y 值得分布 的概率。

32

第四章 LDPC 译码算法研究及硬件实现设计

0.2 0.18 0.16
接 受 到 的 值 为 y 的 概 率 f(y)

0.14 0.12 0.1 0.08 0.06 0.04 0.02 0 -6

-4

-2

0 y

2

4

6

图 4-4 信噪比为 0 时接收到 y 的概率分布

信噪比 SNR 表示的是信号和噪声的相对功率强度,将信号功率和噪声功率之 比取对数再乘以 10 的结果:
SNR ? 10 lg( P ) N

(4-27)

一只信号功率和 SNR 的情况下,可以求得噪声的功率,如式(4-28)

N ? P ?10

?

SNR 10

(4-28)

由于 N ? ? 2 ,即当信号功率归一化为 1 时,噪声的功率为:

? ? 10
2

?

SNR 10

(4-29)

从上式中求得了噪声的功率值。由于信噪比不同,则噪声功率不同, ? 2 也不 同,则高斯分布的范围也会相应的发生变化。我们将信号的功率进行归一化,因 此我们将量化的范围置信度取为 0.99。即使得接收到的值 99%落在量化范围内。 下面对不同信噪比下的满足 99%的数据落在量化范围的边界值。 从图 4-5 中可以看出, 当信噪比范围取值为-1 到 9 时, 量化范围的边界值的大 小出现逐渐变小的趋势。通过观察可以得出当边界取 3.2 时,基本可以保证信噪比 在大于-1 时,99%的接收到的值的取值会在量化范围[-3.2,3.2]内。因此,量化范围 确定为[-3.2, 3.2]。
33

电子科技大学硕士学位论文

3.5

3

2.5
量化范围边界

2

1.5

1

0.5

0 -1

0

1

2

3

4 SNR/dB

5

6

7

8

9

图 4-5 不同 SNR 下的量化范围边界

量化一般可以分为非均匀量化和均匀量化,在均匀量化中,可以将信号的取 值平均分配成间隔相同的小区间,量化的区间大小是由量化位宽和量化范围决定 的。而对于非均匀量化来说,其对于信号量化区间大小不同,并且所处的区间也 不同。所取的值密度较大时,量化间隔大,否则量化间隔小。和均匀量化相比, 非均匀量化优势很明显。但是对于我们的 LDPC 译码的硬件实现来说,均匀量化 要比非均匀量化实现简单的多。非均匀量化比较耗资源,因此,选择了均匀量化。 如分别对 TDMP 算法下面的译码进行了定点量化,量化比特分别为 5、6、7、 8 进行了仿真对比,经过对比可以得出,量化比特增加的时候,译码器的性增加并 不明显,在信噪比达到 3dB 的时候,所有的量化比特的情况误比特率并不明显, 资源消耗却增加。因此,选择量化比特为 6 比特。

34

第四章 LDPC 译码算法研究及硬件实现设计

10

0

10

-1

量化比特5 量化比特6 量化比特7 量化比特8

10

-2

10

-3

BER

10

-4

10

-5

10

-6

10

-7

10

-8

0.5

1

1.5 SNR(dB)

2

2.5

3

图 4-6 不同量化比特的性能比较

4.2.2

归一化因子的确定

归一化最小和算法中,由于对和积译码算法进行了简化,因此,简化过程在 减小运算复杂度的过程中必然降低了运算的精确度,即这种简化必然引入了一定 的误差。 为了减小这种误差,可以在校验节点更新模块中引入了归一化因子来调整最 小和算法的译码误差。归一化因子 ? 的取值范围是 0 ~ 1 。利用归一化因子与求得 的用于更新变量节点的值相乘就可以减小误差[28]。 在 FPGA 硬件实现中,数据是以二进制保存着的。和加法相比,FPGA 中乘法 的实现必然带来更大的资源消耗。用加法的话比较节省资源。 因此 ? 的取值最好是最多两位三进制比特可以表示,如果不是的话,则会引 入乘法器导致译码算法复杂,资源消耗急剧上升。因此,对几种比较适合硬件实 现的因子的取值进行了仿真,如 0.125,0.25,0.5,0.625,0.75,0.875,1。取这些特别的值 可以使得方便硬件实现。将乘法简便地转化成了加法来实现。
35

电子科技大学硕士学位论文

下面是对归一化因子的大小进行仿真的图:

10

0

10

-1

10

-2

10

-3

BER
10
-4

10

-5

10

-6

归 一 化 因 子 0.125 归 一 化 因 子 0.25 归 一 化 因 子 0.375 归 一 化 因 子 0.5 归 一 化 因 子 0.625 归 一 化 因 子 0.75 归 一 化 因 子 0.875 归一化因子1 -1 0 1 SNR(dB) 2 3 4 5

10

-7

-2

图 4-7 不同归一化因子取值下译码器的性能比较

从图 4-7 中可以看出, 归一化因子为 0.75 或者 0.875 的情况下,译码器收敛的 速度最快,在 SNR ? 3 的时候信噪比可以达到 10?6 量级。虽然这两个值得性能都差 不多。但是在硬件实现上,0.75 写成二进制的形式是 (0.75)10 ? (0.11)2 ,0.875 写成 二进制形式为:(0.875)10 ? (0.111)2 。 FPGA 中乘法的是实现可以用移位和加法相结 合的形式来实现,这两个参数相比较,可以得出采用归一化因子为 0.75 可以减小 一次移位和一次加法运算。而且译码器性能和 0.875 的情况相差不多。因此最终归 一化因子选择用 0.75。

36

第四章 LDPC 译码算法研究及硬件实现设计

4.2.2

最大迭代次数的确定

本文在译码实现仿真过程中,需要用仿真实验的方法来确定 LDPC 译码器的 最大迭代次数。译码算法采用的是归一化最小和译码算法。在仿真中,考虑信噪 比 SNR 的范围为 ?2 ~ 7 。 迭代次数分别是 1 到 9。 如图 4-8 所示为仿真得到的结果。 从图 4-8 中不同迭代次数译码器的性能可以得出, 当迭代次数从 1 不断增加时, 译码器收敛的速度越来越快,到迭代次数为 8 或 9 时,译码器在信噪比为 3dB 时, 误比特率 BER 可以达到 10?6 以下。

10

0

10

-1

10

-2

10
BER

-3

10

-4

10

-5

10

-6

10

-7

TDMP迭 代 1次 TDMP迭 代 2次 TDMP迭 代 3次 TDMP迭 代 4次 TDMP迭 代 5次 TDMP迭 代 6次 TDMP迭 代 7次 TDMP迭 代 8次 TDMP迭 代 9次 -1 0 1 2 3 SNR(dB) 4 5 6 7

-2

图 4-8 译码器不同迭代次数的译码性能对比

当迭代次数达到 8、9 次时,对译码器性能的改善已经不是很明显,而由于本 译码器采用了流水线的结构,除了控制部分外的资源消耗是和流水线的级数成正 比,即和迭代次数成正比。所有节约一个迭代次数就可以减小将近 10%的资源消 耗。因此最终的最大迭代次数定为 8。

37

电子科技大学硕士学位论文

4.3 硬件实现结构分析 4.3.1 串行、全并行与部分并行实现结构

LDPC 译码器在实现过程中,可以采取不同的结构,目前主要有三类实现 结构:全并行、串行和部分并行。设码长为 n ,信息比特为 k ,那么全并行结构是 指译码器包括 k 个 VNU 节点和 (n ? k ) 个 CNU 节点, 这种结构的特点是所有的 CNU 和 VNU 分别同时运行,这样可以大大降低译码所用的时间,最大程度地提高了译 码器的吞吐率。但是与此同时,弊端就是资源利用率也大大增加。尤其在硬件实 现中当码长比较长的时候会消耗资源太大而未被广泛使用。 串行结构是指 LDPC 译码器实现中只有一个 CNU 单元和一个 VNU 单元,这 种实现结构恰好是全并行结构的另一个极端,消耗资源明显已经达到最小,然而 与此同时带来的是译码时间的增加,码长比较长的时候,迭代时间线性增加。吞 吐率会受到影响,因此对于对吞吐率要求比较高的系统,不适合采取这种结构。 部分并行结构就是对串行结构和全并行结构的一个折中,这样不经避免了全 并行结构消耗资源大和串行结构吞吐率低的缺陷,而且使得吞吐率和资源消耗做 了一个平衡。 因此,在本文中,依然采取的是部分并行结构。在部分并行结构中,LDPC 译 码器根据更新 CNU 和 VNU 节点的顺序衍生出两种实现结构——TPMP 和 TDMP 结构,在接下来的两节中分别对着两种不同的结构进行研究。

4.3.2

TPMP 结构和 TDMP 结构及性能对比

这两种结构都是基于消息传递(Message Passing)的实现方式。2004 年之前, 译码算法大多基于 TPMP(Two Phase Massage-Passing),发展到最适合逻辑实现的 算法是基于 TPMP 的基于对数似然比的修正最小和译码算法[29]。随后,具有低编 码复杂度的 QC-LDPC 码被提出。 2006 年, Mansour 、 Shanbhag 提出了基于 TDMP(Turbo Decoding Message-Passing)的分层迭代结构,提高了译码收敛的速度。 TPMP 算法指更新先将校验节点依次更新完之后, 再返回来更新变量节点, 具 体算法以归一化最小和算法为例:

Rck,v ?

n?N ( c )\ v

?

1 k ?1 sgn(Qck,? n ) ? min (| Qc , n |) n?N ( c )\ v

(4-30) (4-31) (4-32)

1 Qck,v ? Qck,? v ?

m?M ( v )\ c

?

k Rm ,v

Qvk ? Qvk ?1 ?

m?M ( v )

?

k Rm ,v

38

第四章 LDPC 译码算法研究及硬件实现设计

式(4-30)表示校验节点的更新,将所有的校验节点都用此公式更新以后,开始 执行(4-31)来更新变量节点,同时用式(4-32)更新变量节点对应的后验概率信息。 迭代过程就是这三个方程不断循环。 而对于 TDMP(Turbo Decoding Message-Passing)结构就有所不同,TDMP 结 构又叫水平分层译码结构。与 TPMP 结构不同,TDMP 的迭代是分层的,校验矩 阵的行对应着层。译码开始后,首先更新第一组校验节点,然后用更新过的校验 节点的信息来更新所有与之相关的变量节点。完成更新后,利用更新过的变量节 点的信息开始第二层(即第二组校验节点)的更新。如此循环直到完成最后一层 的迭代之后,就算完成一次译码迭代过程。 可以看出 TDMP 与 TPMP 的区别在于,TDMP 更新完一组校验节点后马上把 校验节点更新过后的信息返回更新变量节点。这样让变量节点和校验节点之间的 更新更加及时。下面研究一下 TDMP 结构下 LDPC 译码算法[30]。 本算法利用归一化最小和译码算法: (1) 变量节点的更新 如果是第一次更新,那么变量节点需要利用初始信息来赋初值:
1,1 Qc ,v ? L( xv )

(4-33)

如果不是第一次迭代那么变量节点的更新为:
1,t Qck,,vt ? Qck,,vt ?1 ? Rck,? v

(4-34)

,t 上式中, Qck,v 表示第 k 次迭代中对第 t 层中,校验节点 c 对变量节点 v 的更新。

(2) 校验节点的更新

Rck,,vt ?

n?N ( c )\ v

?

sgn(Qck,,nt ) ? min (| Qck,,nt |)
n?N ( c )\ v

(4-35)

,t 与上一步类似,Rck,v 表示第 k 次迭代中对第 t 层的迭代,变量节点 v 更新校验节

点c。 (3) 后验概率的更新

Qvk ? Qck,,vt ? Rck,,vt
式(4-36)表示将本次校验节点的更新值加到后验概率中。

(4-36)

从上述公式中,可以看出,步骤(1)和步骤(3)的公式属于 LDPC 译码中 的 VNU 模块,而步骤(2)属于 CNU 模块。原来算法中每次迭代完后需要保存两 部分信息: VNU 产生的用于下一次更新校验节点的信息和更新后的后验概率信息,
k 研究(4-31)和(4-32)可以发现,两部分只存在着一个差值: Rm , v 。因此,只需要保存

39

电子科技大学硕士学位论文
k Qvk 的值和 Rm , v 的值就可以,下一层的迭代开始时,只需要将这两者的值做一个减

法如式(4-34)就可以求得下一层的迭代需要的 Qck,,vt 的值。这样做最大的好处是可以 大大缩小存储空间,节约硬件资源[31]。 通过以上公式可以看出,分层译码算法可以将校验节点的信息及时地传送给 变量节点,这样就使得基于 TDMP 的分层迭代算法迭代次数大大减小,加快了收 敛的速度。这样可以大约节约一半的迭代次数[32]。 下面对这两种算法进行仿真对比,所选的参数为:码长 2304,码率 1/2。算法 TDMP 和 TPMP 的算法,对不同迭代次数的结果进行对比,下面分别为 TDMP 迭 代次数为:1,3,5,7,8,9 和 TPMP 迭代次数为 3,7,11,15,19 的情况下的性能图:
10
0

10

-1

10

-2

TDMP迭 代 1次 TDMP迭 代 3次 TDMP迭 代 5次 TDMP迭 代 7次 TDMP迭 代 8次 TDMP迭 代 9次

10
BER

-3

10

-4

10

-5

10

-6

10

-7

-2

-1

0

1

2 3 SNR(dB)

4

5

6

7

图 4-9 TDMP 结构下的 LDPC 不同信噪比的误比特率仿真图

图 4-9 横轴为信噪比(SNR) ,竖轴表示不同信噪比下的误比特率(BER) 。从 图中可以看出,同一个迭代次数的性能在信噪比(SNR),不断上升的情况下越来 越小,如迭代次数为 1 的线在 SNR=6dB 时,达到 10?4 数量级。随着迭代次数的不 断增加,译码器收敛的速度越来越快,当迭代次数为 8 次和迭代次数为 9 次的时 候,误比特率已经几乎相同,在 3dB 左右,BER 可以达到 10?6 以下。 下面是 TPMP 算法下的译码器不同迭代次数的性能仿真。译码器迭代次数分 别为 3,7,11,15,19。从下图中可以看出,其整体的收敛特性和 TDMP 下的性能仿真
40

第四章 LDPC 译码算法研究及硬件实现设计

很相似。当迭代次数为 19 时,译码器的性能在 SNR=2dB 时达到 10?6 以下。 将图 4-9 和图 4-10 进行对比可以发现, 当 TPMP 和 TDMP 性能接近时, TPMP 的迭代次数将近是 TDMP 的迭代次数的两倍。TDMP 结构在迭代次数为 9 次时, SNR=1.5dB 时性能达到 10?6 以下,而 TPMP 结构在迭代次数为 19 次时,SNR=2dB 时才能达到 10?6 以下,所以可以看出 TPMP 迭代次数大约为 TDMP 两倍时,性能 比 TDMP 还要差 0.5dB。因此,TDMP 结构和 TPMP 相比,有着明显的优势。 当然,由于 TDMP 迭代过程比 TPMP 复杂度要高,因此 TDMP 的硬件实现逻 辑控制复杂度要高于 TPMP。本文的实现结构就是采用的 TDMP 结构。
10
0

10

-1

10

-2

TPMP迭 代 1次 TPMP迭 代 3次 TPMP迭 代 7次 TPMP迭 代 11次 TPMP迭 代 15次 TPMP迭 代 19次

10
BER

-3

10

-4

10

-5

10

-6

10

-7

0

1

2

3 4 SNR(dB)

5

6

7

图 4-10 TPMP 结构下的 LDPC 不同信噪比的误比特率仿真图

4.3.3

LDPC 译码器 FPGA 实现结构图

在上一小节中已经研究了 TPMP 和 TDMP 两种实现结构的优劣,并对二者的 性能进行了仿真,最后得出结论:TDMP 迭代次数比 TPMP 小一半时,性能仍然 优于 TPMP 结构。因此本文的 QC-LDPC 译码器的设计采用了 TDMP 的设计,也 就是采用了水平分层迭代译码算法。下面对译码器的实现结构特点以及实现框图 进行详细研究。 在硬件设计中必须考虑两个关键指标: 一是资源消耗, 而是速度。 在 QC-LDPC 译码实现结构的选择中,出发点都是这两个关键指标。
41

电子科技大学硕士学位论文

首先,本文选择了部分并行结构,根据 4.2.1 对各种结构的对比可以得出部分 并行的结构不仅避免了全并行的资源消耗过多和串行的吞吐率过低的缺陷,而且 同时在实现速度和资源消耗之间达到了一个平衡。此外部分并行结构也是一种非 常适合本文的 QC-LDPC 的实现的重要的考虑方面。 其次,本设计选择了流水线结构,使用流水线结构可以减小一个时钟周期内 的组合逻辑复杂度,提高时钟频率,进而提高吞吐率。另外,流水线可以让所有 的模块每一个时刻都在运行,不会出现有一个时刻是有模块不在工作的时刻。充 分利用了 QC-LDPC 的算法的特点,使用了乒乓操作,使得 CNU(Check Node Update)和 VNU(Variable Node Update)同时在工作,避免了硬件资源的浪费, 提高资源利用率。 再次,使用了乒乓操作,使得两组码字同时译码,和流水线的特点相配合, 一起使得每一个时刻所有的模块都在工作,提高了处理数据的速率,从而提高了 吞吐率。乒乓操作是现代硬件设计常用的一种设计方法,这种方法还有另外一个 好处,即可以充当缓冲器的作用,使得数据可以连续进行处理,而不需要额外的 缓冲器。最后,在使用乒乓操作的基础上,两组码字每一组由两帧码字构成。这 样利用了 QC-LDPC 的部分并行的特性,将 QC-LDPC 的并行度进行了扩展,原来 的 QC-LDPC 的并行度为扩展因子 z ? 96 ,而经过扩展后,将两个码字看成一个扩 展因子为 z ? 96 ? 2 ? 192 的码字。
Out_check Data_in rom

Channel_RA M

Shift_Array

Add_array

Sign_RAM Min_RAM

Sub_array

CNU FIFO

图 4-11 QC-LDPC 译码器的硬件实现整体架构

42

第四章 LDPC 译码算法研究及硬件实现设计

这样做相当于在没有增加控制逻辑的情况下,将两个译码器合并,减小了一 组控制逻辑的资源消耗。同时,也提高了一倍的数据处理能力,吞吐率变为原来 的两倍。 如图 4-11 为 QC-LDPC 译码器的硬件实现整体架构图。经过上面将译码器的 优势的分析,下面具体分析译码器的整体结构和各个模块的具体设计。在研究中, 会将上述优点相结合的方式来分析。 首先对整体实现架构中的数据流进行简要分析: 先将待测试的数据存入 Data_in rom 中来模拟上级数据的到来,由于此译码器 是 4 帧码字数据同时进行译码的,所以此 rom 中保存有的数据为 4 的整数倍。虚 线表示数据开始进入译码器时的数据流。当 4 帧码字经过虚线进入到 Channel_RAM 中保存时,虚线部分暂停,其他实线部分开始译码,直到译码结束 下一个组译码开始时,新数据才会再次通过虚线部分进入系统。 译码过程开始后,第一层数据从 Channel_RAM 中串行读出,进入 Shift_Array 进行循环移位,循环移位的作用是将每组 2 ? z ? 192 个数据一一对应。接下来第一 层数据依次来到 Sub_Array 进行做减法,此处的减法属于变量节点更新 VNU 如式 (4-34)的范畴,除第一次迭代减数为零外,其余迭代减数为上一次迭代产生的最小
1,t k ,t 值或者次小值 Rck,? v 。减法的结果为 Qc , v 。做完减法后,数据来到了校验节点处理

模块和 FIFO 模块,CNU 模块就是求这一层数据的绝对值的最小值 min、次小值 min_next 和最小值的位置索引 index。 求得这些数据后将这些数据保存到 Min_RAM 中用于作为减数参与下一次译码迭代的减法。FIFO 是将减法的结果保存起来,等 数据做完 CNU 后就可以一起参与下一步骤的加法。等到这一层的数据 CNU 更新 完毕后,FIFO 也开始同步输出数据,共同进入加法器阵列 Add_array 参与加法 (4-36),此处的加法属于 LDPC 译码过程中的校验节点更新 VNU 部分,此处的加 法的结果就是变量节点处的更新后参与校验的后验概率值。加法结束后将加法得 到的和保存回到 Channel_ram。至此,第一层数据更新完毕。由于是乒乓操作,当 第一组数据的第一层保存到 Channel_ram 中时, 第二组数据的第一层开始往外读出 数据。反之,当第二组的数据开始往 Channel_ram 中存储数据时,第一组的数据开 始从 Channel_ram 中往外读数据。如此交替,实现了 CNU 和 VNU 所有的时刻都 是在工作着的。如此不断迭代,当完成最后一层的迭代后意味着第一次迭代结束。 继续不断迭代,当迭代次数达到最大迭代次数时,数据从 Channel_RAM 中读 出到 Out_check 中进行校验,加入校验成功,那么译码成功;如果校验失败,那么 此次校验失败。 以上部分就是译码器的数据流研究,下面对译码器整体架构中的每个模块进

43

电子科技大学硕士学位论文

行详细研究。 4.3.3.1 LDPC_TOP LDPC_TOP 是 LDPC 译码器的顶层文件,用来对 LDPC 译码器的各个模块进 行总体调控。比如译码过程的开始,结束等都是由此文件控制。另外在本 LDPC 译码器的设计中, 采用了将各个模块的控制器进行了“分布式”处理, 即将各个模块 的控制信息由各个模块自己独立产生,对于上一级没有过分依赖,上一级仅仅需 要将开始的使能信号传递下去就可以,这样做的好处是提高了代码的移植性,同 时也提高了可读性,对于其他开发人员,他不需要了解整体算法或者其他模块就 可以对某个模块进行一定的了解。与“分布式”控制相对的就是“集中式”处理, 在集中式处理中,设计者通常将设计的各个模块的控制器集中到一个文件下。这 样对每一个单独的模块的可移植性进行了一定的破坏,不利于与快速开发。因此 本文选择了“分布式”开发思想。 在 LDPC_TOP 中,仅仅对最高层的控制进行了设计并对各个模块进行了例化 和连接(如图 4-12) 。

图 4-12 译码器设计文件列表

在译码器的总体控制中译码器的迭代次数 iter_num 控制着译码迭代的始末。 对译码器总体控制的信号为译码器的状态 decoder_states。其有三种状态:
表 4-1 译码器状态控制器 译码器的状态(decoder_states) 0 1 2 意义 数据进入译码器存入 Channel_ram 阶段 译码过程 译码结束,OUT_RAM 输出译码结果

最初的译码器状态值为零,在这个阶段,数据从外部分分为 6 路进入译码器, 每一路为 96bit。由于本文设计的译码器是四个码字同时译码,因此,输入阶段需 要输入四个码字,当四个码字都输入完毕后,数据保存到 channel_ram 中,保存完
44

第四章 LDPC 译码算法研究及硬件实现设计

毕后开始译码,译码器的状态值变为 1,开始译码。当译码成功或者最大译码迭代 次数后结束译码, 译码器状态值变为 2, 停止译码, 在这个阶段将保存到 OUT_RAM 中的译码结果输出译码器。如图 4-13 为译码器的输入输出接口。
clk_main rst code_rate[1:0] data_in_0[95:0]
data_out_flag LDPC_TOP data_out_a[95:0] data_out_b[95:0]
图 4-13 译码器输入输出示意图

?? data_in_5[95:0]
data_in_flag

4.3.3.2 Channel_RAM 前面已经研究过 Channel_RAM 的结构, 译码器采用了乒乓操作和对 QC-LDPC 扩展因子扩展的方法。乒乓操作就是讲数据流等时分配到两个数据缓冲区,比较 常见的是利用一个双口 RAM(DPRAM) 、FIFO 等实现。通过控制逻辑对输入数 据和输出数据进行按照节拍,相互配合来切换位置,这样可以使得进入的数据没 有停顿地与 RAM 交换数据,因此这种结构非常适合流水线式的运算处理,完成数 据的无缝缓冲和处理。是面积与速度互换的原则的很好的体现。 除了采用乒乓操作外,还将扩展因子进行扩展为原来的两倍,即将两个码字 合并为一个码字,绑定到一起,这样可以节约一套控制逻辑。
2304 bit = 24 × 96bit Code_1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 +

Code_2

1

2

3

4

5

6

7

8

9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

Code_1&Code_2

1

1

2

2

3

3

?? ??

22 22 23 23 24 24

图 4-14 将两个码字绑定在一起译码

如图 4-14 可以看出, 码长为 2304 的码字由 24 个 96bit 的小码块组合而成, 将 两个码字的每一个小码块分别意义对应粘连到一起,这样生成一个码长为 4608 的 大码,由 24 个大小为 192bit 的小码块构成。 在 Channel_RAM 实现的过程当中,在保存时没有将两个码字在物理上进行粘 连,而是将他们保存在不同的 RAM 中,译码的时候再同时进行读取,然后再粘连 后进行其他译码的过程。因此,Channel_RAM 采用了两个双口 RAM 来存储信息。

45

电子科技大学硕士学位论文

对于 Channel_RAM 用到的两个双口 RAM, 由两个双口 RAM 组成, 每个双口 RAM 存放两个码字, 每个双口 RAM 都是一个乒乓操作, 双口 RAM_A 和 RAM_B 是相互独立,对应的位置的操作相似的(图 4-15) 。每个双口 RAM 的深度为 64, 位宽为 960bit,即其大小为 64 ? 960bit 。图中每个剪头都表示分层迭代译码的每一 层的数据流,如图可以看出,两个双口 RAM 在左侧数据保存的时候,右侧的数据 部分正在读出。如此反复,不间断地交换数据,实现了乒乓操作。同时用两个双 口 RAM 进行乒乓操作,提高了数据处理能力,也提高了译码器的吞吐率。

DPRAM A

Code1

Code3

Code2

Code4

DPRAM B

图 4-15 Channel_ram 的结构图

如图 4-15 为 Channnel_ram 输入输出接口图,从顶层到 Channel_ram 模块的接 口中,除了时钟、复位信号、码率外,有分层迭代译码的层数,读数据的层数 write_layer 和 read_layer 以及数据接口,channel_ram_in 表示进入 Channel_ram 中 的数据, channel_ram_back 表示每次经过译码后返回到 Channel_ram 中的数据接口。 输出方面 shift_num_location 是给下一个模块 Shift_array 读取 shift_num 的指示信 号,channel_ram_read 信号表示读出 Channel_ram 的数据接口。
clk_main rst code_rate[1:0] channel_ram_in_0[191:0] channel_ram_in_9[191:0] channel_ram_in_ena channel_ram_back_0[191:0] shift_num_location

??

channel_ram_read_0[191:0]
Channel_ram

??

??
chanel_ram_read_9[191:0]

channel_ram_back_9[191:0] channel_ram_back_ena read_layer write_layer

图 4-16 Channel_ram 接口示意图

由于采用了乒乓操作,因此,译码开始时,先与校验矩阵第一层对应位置的 Code1 和 Code3 进行译码,等 Code1 和 Code3 循环回到 Channel_ram,开始往 Channel_ram 中存储时,开始读取与校验矩阵第一层对应位置的 Code2 和 Code4,

46

第四章 LDPC 译码算法研究及硬件实现设计

等 Code2 和 Code4 循环回到 Channe_ram 时,校验矩阵第二层对应位置的 Code1 和 Code3 开始读取,如此循环往复。 4.3.3.3 Shift_array 由于 QC-LDPC 的特性,校验矩阵的表现形式通常是基矩阵。前面章节已经 研究过,每一个基矩阵的元素都是一个数字,每一个数字 x 在校验矩阵中表示将一 个 z ? z 的单位阵向右平移 x 个单位生成的矩阵。 这样, 每一层的校验矩阵和每一个 大小为 z 的码块就不是一一对应的。而算法中 CNU 模块要求所有的比特必须一一 对应才能求出正确的最小值、次小值。也是部分并行的要求。因此,需要一个 Shift_array 模块来将平移后的码块向左循环移位使得所有的码块相应的位置都对 齐,方便后面的操作。 这里的 Shift_array 除了在译码的时候会用到之外,当最初的数据进入时也会 首先先进行一个移位,每个数据移位的量为基矩阵里每一列的从下面数第一个非 零的数字, 即为初始化需要进行一个移位, 初始化移位后, 译码前从 Channel_RAM 中读出的数据本身带着一个偏移量。因此,译码的移位量是在初始化移位的基础 上添加一个相对移位使得码块的移位达到绝对位移值(绝对位移值就是指基矩阵 中的值)如表 4-2 中黑底的数字表示的就是初始化的位移量。这样做的好处是,只 需(4-37)要进行一个初始化,可以保证每一次迭代的时候读出的数据进行移位的值 是一样的,使得硬件设计更加简便。在译码过程中,所有的位移量是存在 ROM 中 保存着的。此外,Shift_array 采用了并行操作对 10 位位宽的数据进行循环移位, 并行度为 Channel_RAM 中的数据的位宽 10。
clk_main rst code_rate[1:0] shift_in_0[191:0]
shift_in_9[191:0] shfit_in_ena shift_num_location[9:0]
图 4-17 Shift_array 的接口示意图

??

Shift_array

sub_begin_flag shift_out_0[191:0]

??
shift_out_9[191:0]

如图 4-17 是 Shift_array 模块中的输入输出接口示意图。 输入包括时钟、复位、 码率以及数据输入 shift_in,数据输入每一路为 192bit,对 192bit 整体进行移位。 sub_begin_flag 作为下一级减法器阵列的激励。 在 Shift_array 中,采用了 10 路 Shift_unit 模块来分别对 10 路位宽为 192 比特 的数据进行循环移位。移位量保存在 ROM 中,按照数据进入的顺序依次读出。

47

电子科技大学硕士学位论文 表 4-2 Shift_array 对初始数据进行初始化位移量
-1 -1 -1 61 -1 -1 -1 -1 12 -1 -1 43 94 27 -1 -1 -1 -1 -1 11 -1 -1 -1 -1 73 -1 -1 47 39 -1 95 73 -1 -1 7 -1 -1 -1 24 -1 -1 -1 53 -1 -1 -1 65 -1 -1 -1 22 -1 -1 46 -1 -1 83 -1 -1 -1 -1 22 81 -1 -1 40 -1 -1 24 94 -1 66 -1 79 -1 -1 84 -1 -1 2 -1 -1 -1 -1 -1 9 33 -1 -1 82 -1 -1 43 59 -1 41 55 -1 -1 65 -1 -1 -1 -1 -1 -1 39 -1 83 -1 -1 25 41 -1 14 47 -1 -1 49 -1 -1 -1 -1 -1 72 -1 18 -1 -1 70 -1 -1 -1 12 0 -1 -1 79 -1 -1 51 72 -1 26 7 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 7 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0

4.3.3.4 Sub_array Sub_array 是变量节点更新 VNU 的一部分,利用经过循环移位后的值和保存 在 Min_ram 和 Sign_ram 中的最小值、 次小值来求本次迭代需要的变量节点的信息。 用于产生下一次迭代的更新校验节点信息的值。第一次迭代的减数为 0,从第二次
1,t 迭代开始,每次迭代的减数为上一次迭代产生的最小值或者次小值 Rck,? v 。同样是

并行操作,并行度为 192。在做减法之前涉及到串并转换。
clk_main rst code_rate[1:0] sub_in_0[191:0] sub_in_9[191:0]

??

sub_out_0[191:0] Sub_array

?? min_ram_out_16[191:0]
sn_ram_out[191:0] sub_in_flag

min_ram_out_0[191:0]

??
sub_out_191[191:0]

图 4-18 Sub_array 输入输出接口示意图

如图 4-18 为整体的 Sub_array 的输入输出接口示意图。输入包括时钟、复位、 以及循环移位器到减法模块的输入 sub_in。min_ram_out 表示上一次译码迭代求出 的最小值、次小值和最小值的位置。sub_in_0 到 sub_in_9 共 10 路,每一路 192bit。 min_ram_out_0 到 min_ram_out_16 共 17 路, 每一路 192bit。 数据进入 Subarray 后, 首先进行串并转换,将 sub_in 转化成 192 路 10bit,将 min_ram_out 转化为 192 路 17bit。 进行串并转换完毕后,前面的 192 路数据和 Sub_unit 模块对应,下面对减法

48

第四章 LDPC 译码算法研究及硬件实现设计

器阵列中的减法器小单元进行研究。如下图为减法器小模块的接口示意图。
clk_main rst code_rate[1:0] num_of_layer_b[4:0] layer_b[3:0] sub_in_b[9:0] min_in_b[5:0] min_n_in_b[5:0] index_in_b[4:0] sign_in_b

Sub_unit

sub_out[9:0]

图 4-19 Sub_unit 输入输出示意图

如图 4-19 为 Sub_unit 的输入输出接口示意图,输入包括时钟、复位信号、码 率、减数、减数在本译码层中的位置、层数、最小值、次小值、最小值的位置、 最小值的符号输入。输出为 sub_out,位宽为 10bit。 4.3.3.5 FIFO FIFO (First In First Out) 是用来缓存数据,等减法的结果在参与 CNU 结束后, CNU 求出的值还需要和 FIFO 中保存着的数据进行做加法操作。 和 Channel_ram 一 样,也是采用了双口 RAM。 由于在译码过程中,与 FIFO 大小息息相关的参数就是校验矩阵每行的行重。 四种码率对应的校验矩阵中,1/2、2/3、3/4、5/6 对应的校验矩阵的最大行重分别 为 7、10、15、20。因此,FIFO 的设计采用最大行重 20 来设计,位宽为 192 比特, 因为减法的结果为 192 路位宽为 10 比特的数据, 因此需要 10 个 RAM 来保存数据。 由于本文采用的算法为水平分层迭代算法,因此计算是一层一层计算的。一 般的水平分层算法 FIFO 中保存的值为一层的数据。由于本文采用了乒乓操作,同 时对两个码字进行译码,由于 FIFO 在译码过程中是同时读取,因此,FIFO 需要 两个大小为最大行重 20 的部分来进行保存数据,因此存储器深度为 40,考虑地址 是二进制,因此深度取 64,两个 20 个值分别存在前后两个 32 大小的空间中。因 此 FIFO 的设计中共需要 10 个双口 RAM,每个 RAM 的位宽为 192 比特,深度为 64。 如图 4-20 为 FIFO 的输入输出接口示意图,输入有时钟、复位信号、码率、 译码器状态、 fifo_flag 为 fifo 开始工作指示信号, cun_in_0 到 cnu_in_191 为输入信 号,输出信号为 fifo_out_0 到 fifo_out_191。

49

电子科技大学硕士学位论文

clk_main rst code_rate[1:0] decoder_states[2:0] fifo_flag cnu_in_0[9:0]

fifo_out_0[9:0]
FIFO_array

??
fifo_out_191[9:0]

??
cnu_in_191[9:0]
图 4-20 FIFO 模块输入输出接口示意图

4.3.3.6 CNU 模块 CNU(Check Node Update)是指校验节点的更新,将每一层的数据求出最小 值 min、 次小值 min_next 和最小值的位置索引 index。 CNU 部分采用的结构是部分 并行,即串行和并行相结合。同 Sub_array 模块类似,共 192 路并行,每一路串行 求最小值等。译码过程中的每一层数据经过 CNU 后会得出一个最小值、次小值、 和最小值的位置 index。 除了需要计算最小值等之外,在 CNU 模块中还需要对每一层的对应的数据进 行一个模二加的操作,求得其符号之和。这样求的目的是为了求得最小值的符号。 在上一节中的求最小值的公式中表示, ? sgn(Qck,,nt ) 为最小值和次小值的符号,
n?N ( c )\v

本文求最小值符号的方法是,在 CNU 模块中求出每一层对应数据的符号位之和, 在 Add_array 模块中再利用求得的符号和来与加数的符号模二加, 从而用两步求出 了最小值、次小值的符号。下面对 CNU 的输入输出接口进行分析。
clk_main rst code_rate[1:0] decoder_states[2:0] cnu_flag cnu_in_0[9:0]

cnu_sign_out[191:0]

CNU_array

min_info_0[191:0]

??
min_info_16[191:0]

??
cnu_in_191[9:0]

图 4-21 CNU_array 输入输出接口示意图

如图 4-21 为 CNU_array 的输入输出接口,输入接口包括时钟、复位信号、码 率、译码器状态、CNU_array 输入使能 cnu_flag 和数据 cnu_in_0 到 cnu_in_191。 输出为 min_info_0 到 min_info_16。

50

第四章 LDPC 译码算法研究及硬件实现设计

对于输出 17 组 min_info,每一路都是 192 比特。接下来对 min_info 的结构进 行分析:

最小值 min

min_info_0 192bit
??

min_info_5 192bit
次小值 min_n

min_info_6 192bit
??

min_info_11 192bit
最小值 位置 index

min_info_12 192bit
??

min_info_16 192bit
图 4-22 min_info 的格式

如图 4-22 为 CNU_array 的输出 min_info 的格式, 第 16 位到 12 位表示最小值 位置的 index,第 11 位到第 6 位表示次小值 min_n,第 5 位到第 0 位表示最小值 min。 在 CNU_array 中,有 192 路 cnu_unit 并行计算,下面对 cnu_unit 的输入输出 进行分析。如图 4-23 是 cnu_unit 的输入和输出接口示意图。

clk_main rst code_rate[1:0] decoder_states[2:0] cnu_flag cnu_in[9:0]

min_info[16:0] Cnu_unit cnu_out_flag sgn_out

图 4-23 cnu_unit 输入输出接口示意图

4.3.3.7 Min_ram 和 Sign_ram Min_ram 用来保存 CNU 产生的最小值、次小值和最小值的位置。保存到 Min_ram 中,下次迭代的时候需要读出这些值用来计算下一次迭代的减数。 每一层的迭代结束后,都会产生一个最小值、次小值和最小值的位置,这些 值被存在 Min_ram 中,四种码率的结构中,码率为 1/2 的校验矩阵的行数最多, 即每次迭代 1/2 码率产生的值为 12 组。由于乒乓操作的技术的应用,Min_ram 需 要 24 组的空间,最终采用深度为 32 的 RAM,前后两个 12 组分别存储于前后两

51

电子科技大学硕士学位论文

个 16 的空间。 最终, 本文采用了 17 个双口 RAM, 每一个双口 RAM 的位宽为 192bit, 深度为 32。如图 4-24 为 Min_ram 的接口图。

clk_main rst code_rate[1:0] cnu_out_flag min_info_0[191:0]
min_info_16[191:0]

min_ram_out_0[191:0]

Min_ram

??
min_ram_out_16[191:0]

??

图 4-24 Min_ram 输入输出接口示意图

另外,还有一个存储器保存最小值和次小值的符号值,这些符号是加法器模 块 Add_array 的结果。四种码率需要保存的值的空间大小分别为:84,80,90,80。 考虑乒乓操作,因此最终选择保存符号的空间深度为 256,位宽为 192。 下图 4-25 为存储符号的双口 RAM 的输入输出接口示意图。

clk_main rst code_rate[1:0] sign_in_flag sign_out_flag sign_in[191:0]

Sign_ram

sign_out[191:0]

图 4-25 Sign_ram 输入输出接口示意图

4.3.3.8 Add_array Add_array 模块的功能也是 VNU 功能的一部分,加法是为了求得经过校验节 点更新过后的变量节点对应的后验信息。 此模块通过将 FIFO 中保存着的将变量节 点更新后的值与 CNU 的校验节点信息相加。同减法模块 Sub_array 相同,也是并 行度为 192。 如下图 4-26 为加法器的输入输出接口示意图。

52

第四章 LDPC 译码算法研究及硬件实现设计

clk_main rst code_rate[1:0] min_info_0[191:0]

add_out_flag Add_array

??

min_info_16[191:0] fifo_out_0[9:0]

add_out_0[191:0]

??
add_out_9[191:0]

??

fifo_out_191[9:0] sign_in[191:0]
图 4-26 Add_array 模块输入输出接口示意图

与减法器相似,加法器也是采用了 192 路并行处理,一个加法器 Add_array 由 192 路加法器小单元 add_unit 并行处理。add_unit 的接口如图 4-27。
clk_main rst code_rate[1:0] add_flag add_num[9:0] index[4:0] min[5:0] min_n[5:0] sign_in

add_out[9:0]

Add_unit sign_to_ram

图 4-27 加法器小单元 add_unit 输入输出接口图

4.4 译码器仿真结果
上一节主要讲述了 QC-LDPC 译码器的分层译码实现结构, 并对这种结构的优 缺点进行了分析。另外,还对译码器的每一个模块的设计结构进行了分析。本节 将对译码器的仿真结果进行分析。 同编码器一样,译码器的仿真工具依然选择业界知名的 Modelsim 软件,下面 对译码器的关键数据进行了仿真展示。 首先, 对于数据的输入过程来说, 是通过 Matlab 产生编码后通过 AWGN 信道 后的数据,将此数据进行量化出处理后,生成二进制的比特文件 data_in.txt。译码 仿真时,利用仿真用到的 Textbench 文件 ldpc_decoder_tb.v 来将文件 data_in.txt 读 入仿真器,这样输入数据就进入到了仿真器中。 从仿真图中可以看出,每次译码开始进入到译码器中的数据有 4 帧码字。最
53

电子科技大学硕士学位论文

后分为两组,译码过程为了保证流水线结构采用了乒乓操作。

图 4-28 LDPC 译码器数据输入模块仿真

输出数据格式:上一节已经讲到数据的保存结构,利用了乒乓操作和两码字 合并的方式。因此,输出格式也可以两个码字同时输出。如下图:

数据输入格式:

Code_1

Code_2

Code_3

Code_4

数据输出格式:

data_out_a
data_out_b
图 4-29 译码器数据输出格式

Code_1
Code_2

Code_3
Code_4

数据输入后开始译码,译码最后的测试方式:将 Matlab 计算出的正确的译码 参考结果转化为二进制比特文件 data_out_a_ref.txt、data_out_b_ref.txt。然后利用 ISE 软件将此数据存到 ROM 中。 当译码器计算出结果 data_out_a、 data_out_b 的时 候,从 ROM 中读出参考值 data_out_a_ref、data_out_b_ref 并将计算结果值和参考 值做一个差值求得 data_out_a_diff、data_out_b_diff。如果这个差值结果为零,那么 说明译码器计算值是正确的。

54

第四章 LDPC 译码算法研究及硬件实现设计

图 4-30 译码器输出结果(一)

如图 4-30 是译码器的输出结果,当 data_out_flag 有效时,译码结果开始输出, 如图 4-31 中可以看出, data_out_a 和 data_out_a_ref 数据相同, 其差值 data_out_a_diff 为零,说明 data_out_a 和 data_out_a_ref 数值相同,译码结果是正确的。

图 4-31 译码器输出结果(二)

4.5 本章小结
本章主要内容为一个多码长多码率译码器的算法研究以及硬件实现。首先, 本章研究了基于概率测度的 BP 译码算法、基于对数似然比的 BP 译码算法、最小 和译码算法及归一化最小和译码算法等译码算法。并且对这几种算法进行了一个 对比,最终选择了归一化最小和译码算法。 随后对 QC-LDPC 译码器的两种主要实现结构 TPMP 和 TDMP 及性能进行了 对比,最后选择了性能比较突出的 TDMP 结构,即水平分层迭代译码结构。对硬 件实现需要的各个参数进行了一一仿真确定。然后对硬件实现的结构进行了详细 地研究。并且对仿真结果和实现的参数进行了研究和分析。 本章设计的 QC-LDPC 译码器为一个多码长多码率的译码器, 码长最大可以达 到 4608,此码长为 802.16e 协议中最大码长的两倍。由于采用了乒乓操作,对于

55

电子科技大学硕士学位论文

常规的 2304 的码长可以 4 个码字同时译码。四种码率分别为:1/2,2/3,3/4,5/6。 由于四种码率的实现译码器参数不同,本章还对吞吐率以及资源消耗进行了分析, 并与其他译码器设计进行了对比。

Equation Chapter (Next) Section 1

56

第五章 LDPC 编译码器的验证与测试

第五章

LDPC 编译码器的验证与测试

前两章分别对 LDPC 编码器和译码器的硬件实现结构进行了研究和说明。另 外,还利用 Modelsim 软件对设计进行了仿真。经过仿真,分析编译码器的一些参 数,如最高工作频率、资源消耗、吞吐率等参数。由于之前都是软件的仿真,具 体的实现情况还需要下板来验证。本章主要讲述 LDPC 编码器和译码器在 Xilinx KC705 开发板上进行板级验证的过程及结果。

5.1 LDPC 编译码器的验证方案
前面两章分别对多码率多码长的 LDPC 编码器和译码器完成了功能仿真,本 章主要分析对 LDPC 编码器模块和 LDPC 译码器模块进行测试和验证。 本章分别对第三章和第四章对 QC-LDPC 编码器和译码器的设计进行测试和 验证。验证的思路是:将通信系统中除了 QC-LDPC 编码器、译码器之外的其他模 块的功能利用 PC 实现,包括编码器之前的模块、调制、经过信道加噪声、解调等 模块。下图为通信系统中从编码器到译码器需要经过的模块示意图。
噪 声

数据 产生

QC-LDPC 编码器

调制

量化

QC-LDPC 译码器(解调)

译码 结果

数据比对

图 5-1 LDPC 编译码系统模型

图 5-1 展示了编译码系统的模型。在 QC-LDPC 编译码系统中,首先利用 PC 中的 Matlab 产生随机的固定长度的的二进制比特数据流,即产生 LDPC 码编码前 的信息比特,如当码长为 2304 比特,码率为 0.5 时,信息比特的长度就是 比特。 2304? 0.5 ? 1152 二进制比特数据流进入 QC-LDPC 编码器进行编码,生成长度为固定码长的 LDPC 码,如前面输入 1502 比特的信息比特,码率为 0.5 时,编码器将会产生另 外的 1502 比特的校验位,与输入的 1502 比特的信息位合并,形成码长 2304 的码
57

电子科技大学硕士学位论文

字。编码后校验比特读回 PC 进行比对其正确性。 编码后的码字在经过信道前,需要进行调制,本文采用的调制是 BPSK 调制, 这部分操作也是在 PC 上完成。调制后经过信道在传输的比特中加入噪声,这部分 工作是用 Matlab 模拟通过一个 AWGN 信道来实现的。在 Matlab 中有一个函数可 以实现模拟加噪声。

图 5-2 matlab 加噪处理过程

由于本文实现的是软解调,即在进入 QC-LDPC 译码器的信息为软信息,即直 接对接收到的浮点数进行译码,由于 FPGA 实现需要对数据进行定点操作,将接 收到的数据进行量化,将[-3.2, 3.2]区间内的值进行均匀量化为 6 比特的二进制数 值。这些值就是译码器开始译码的软信息。 将这些软信息导入开发板 KC705,在开发板上完成 QC-LDPC 译码。另外,在 QC-LDPC 译码的过程中已经完成了解调制过程。
产生 随机 序列

PC(1) (matlab)

(a)

(b) 比对编 码数据 调制、 加噪、 量化、

Xilinx KC705

QCLDPC 编码器

比对 数据

PC(2) (matlab)
(c)

(d)

Xilinx KC705

QCLDPC 译码器

PC(3) (matlab)

(a)产生随机信息比特序列 (b)编码器产生校验序列 (c)将量化后的比特进入译码器 (d)将译码结果传给PC

图 5-3 验证平台及数据流

根据译码的结果进行判断整个系统的正确性。在对译码器的结果判定上,是 通过 matlab 生成译码的结果来和 FPGA 仿真的结果进行对比, 当译码结果出现时, FPGA 内部读出事先存储在 ROM 中的正确数值,两者做一个减法,通过判断减法

58

第五章 LDPC 编译码器的验证与测试

的差是否为零来判定译码是否正确,最后利用 Chipscope 读出 FPGA 中的译码结 果与正确结果的差,根据这个差是否为零来判定译码器的正确性。 如图 5-3 描述了整个验证平台的数据流及验证方案。首先 PC(1)产生随机的 序列,经过 KC705 中的 QC-LDPC 编码器,产生 LDPC 码的校验位。编码完成后, 结果利用 Chipscope 读入 PC(2) ,对编码的结果进行比对。然后将数据进行调制、 加噪声、量化,然后将量化结果进入 KC705 中的 QC-LDPC 译码器,经过译码后, 再次利用 Chipscope 读入 PC(3) ,对译码的结果进行判定。

5.2 LDPC 编译码器的验证平台
在对 LDPC 编码器和译码器的验证中,使用了 Xilinx 的 KC705 芯片,这款开 发板搭载了 7 系列的 Kintex-7 系列的 XC7K325T 芯片。随着 FPGA 技术的发展目 前 Kintex-7 系列的芯片的特征尺寸已经达到 28nm。意味着更高的集成度和更高的 性能。 Kintex-7 系列是 Xilinx 公司具有较高性价比的 FPGA 之一。 如图 5-4 为 KC705 开发板。

图 5-4 Xinlinx 公司 KC705 开发板

此款开发板的应用领域也比较广泛,主要应用在航空电子、3D 电视、手持超 声设备、LTE 基带、视频网关、LED 背光的平板电视等。另外,这款芯片的逻辑 资源也比较丰富,非常适合实现并行度需求高的 LDPC 编译码的实现过程。 如表 5-1 为 XC7K325T 芯片的资源表。

59

电子科技大学硕士学位论文 表 5-1 XC7K325T 芯片资源统计表 资源类型 Slices Logic Cells CLB Flip-Flops Maximum Distributed RAM (Kb) Block RAM/FIFO (36 Kb each) Total Block RAM (Kb) CMTs (1 MMCM + 1 PLL) Maximum Single-Ended I/O Maximum Differential I/O Pairs DSP48 Slices Analog Mixed Signal (AMS) / XADC GTX Transceivers (12.5 Gb/s Max Rate) 资源数量 50,950 326,080 407,600 4,000 445 16,020 10 500 240 840 1 16

FPGA 于 20 世纪 80 年代出现, 备受现代数字系统设计等工程师们欢迎的一种 系统设计积木块。 工程师通常利用硬件描述语言 VHDL 或者 Verilog-HDL 对 FPGA 进行设计[33]。半导体技术经过了不同的发展历程。初期从小规模集成电路(Small Scale Integration)发展到了中规模集成电路(Medium Scale Integration) ,随后经过 多年的发展又实现了从大规模集成电路 (Large Scale Integration)发展到了超大规 模集成电路 (Very Large Scale Integration) 。半导体技术的不断演进,为 FPGA 技 术的不断发展奠定了坚实的基础。 FPGA 使得软件和硬件的边界更加模糊,硬件体现在逻辑门和寄存器等,而软 件则体现在微处理器执行的命令上。在微处理器方面,Xilinx 公司有 8 位处理器软 核 PicoBlaze,还有 32 位的 RSIC 架构的处理器软核 MicroBlaze。除此之外,还有 丰富的硬核处理器 Power-PC。在 IP(Intellectual Property)方面,Xilinx 提供了大 量丰富的可以用在不同领域的 IP 核。不仅如此,FPGA 还嵌入了大量的硬核,这 样就可以利用 FPGA 硬件机构中参数化的 IP 核将整个数字系统在一片 FPGA 内实 现。也就是通常意义上的可编程 SOC(System On Programmable Chip) 。Xilinx 的 7 系列产品中还多了一个全新的数字处理平台 ——EPP ( Extensible Processing Platform) 。总之,越来越多的功能模块被加入到了 FPGA 当中,让 FPGA 的应用 场合越来越广阔。 对于 FPGA 的设计来说,一般有特定的流程(如图 5-5) 。
60

第五章 LDPC 编译码器的验证与测试

需求分析

模块划分

代码设计

综合优化

功能仿真

时序验证

实现

板级调试

图 5-5 FPGA 一般设计流程

下面对 FPGA 的设计流程基本流程进行分析: (1)需求分析: 在这个阶段就是要对设计的系统进行一个整体的分析规划,这一阶段要完成 对功能的描述和设计、硬件资源的消耗、功耗、处理速度等。综合以上参数来选 择确定使用的硬件型号以及整体方案。是自顶而下设计方法的最顶端。 (2)模块划分 对于一个整体的系统来说,利用自顶而下的设计方法,将一个整个系统划分 为不同功能的子系统,将子系统继续划分。划分原则是同一层的模块功能相互独 立、没有相互交叉的部分。这个部分就是系统的功能不断细分的过程。 (3)代码设计 这一部分就是利用硬件描述语言 VHDL 或者 Verilog-HDL 来对每一个小系统 的功能进行描述。描述过程中利用硬件描述语言对状态机、总线功能、控制逻辑 进行细分的功能描述。这一部分的代码具有很强的移植性和可读性。初次之外还 有一种描述方法是原理图描述法,有着直观、形象化的特点,适合顶层设计。 (4)功能仿真
61

电子科技大学硕士学位论文

功能仿真就是利用专门的软件对上一步写的代码进行查找错误。另一方面, 要根据电路的特征判断所写的代码是否适合实现所需的功能。这一过程也叫做行 为仿真。有名的仿真工具一般有 Modelsim、VCS 等软件。 (5)综合优化 除了满足所要的功能外,还要考虑资源消耗、功耗、速度、成本等因素。这 些都是设计所要附加的约束条件。约束条件可以通过代码的形式添加,也可以通 过原理图的方式输入。这一过程就是对设计进行一个优化的过程。其结果就是生 成可以供布局布线使用的网表,这个网表包括了设计需要的器件及其之间的连接 关系。经过这一过程中计算机的计算优化,可以获得一个满足要求的电路的方案, 这一过程就叫做综合。 (6)实现 这一部分就是将综合得到的网表映射到 FPGA 器件中去。每个公司都会有自 己的软件,如 Xilinx 的软件是 ISE,Altera 的软件为 Quartus。ISE 中的实现包括三 个部分:Translate、Map 和 Place&Route。软件可以根据每个公司不同的硬件结构 生成不同的位流文件提供给时序仿真和 FPGA 配置需要。 (7)时序约束 在硬件实现中,必然存在着器件之间信号传输的延迟、连线延迟等情况都可 以造成时序问题。这些延迟足够大时,就会影响到系统的时序。通过时序验证就 可以检查是否存在时序未规定的情况。所以布局布线后的时序验证就显得很重要。 (8)板级调试 在实现和时序约束都通过后,可以将布局布线后形成的 bit 流文件配置下载到 FPGA 板子中去。完成下载后,就可以用外接的验证工具来对设计进行一些物理测 试。如果发生错误,那么需要回到代码设计那一步来重新检查错误,重新设计。 如果正确,那么说明系统的设计是成功的。

5.3 LDPC 编码器和译码器的板级验证 5.1.1 LDPC 编码器的板级验证

Chipscope 是 Xilinx 公司设计的一款在线逻辑分析仪,通过 Chipscope 可以实 时抓取 FPGA 内部信号的值,在电脑上生成波形,可以用来判断下板实现的详细 结果。FPGA 内部有专门用于验证用的 BlockRam,在触发条件达到时,按照采样 条件进行采集数据,并且将数据保存到 BlockRam 中。然后将采得的值通过 JTAG 线传到电脑上,电脑上绘制出波形(如图 5-6) 。

62

第五章 LDPC 编译码器的验证与测试

图 5-6 板级验证连接图

在板级验证之前,需要在设计中例化两种核:集成逻辑分析仪核( ILA , Integrated Logic Analyzer core)和集成控制器核 ICON(Integrated Controller core) 。 ILA 主要用来提供触发和跟踪捕获数据的功能; ICON 负责 ILA 核和边界扫描端口 通信的功能。设计时,只需要将这些核例化在设计代码中,然后进行综合优化、 布局布线、下载等步骤。就可以利用 Chipscope Pro Analyzer 设定触发条件并且观 察信号波形。 第三章已经研究过编码器的主要算法和硬件实现结构。本节主要分析编码器 的板级验证结果。如图 5-7 为编码器整体验证图,本测试图是在码长 2304、码率 为 1/2 下的测试图:

图 5-7 编码器板级验证仿真图(一)

从图 5-7 中可以看出编码器的输入是串行输入 96 比特。 由于码率为 1/2, 所以 LDPC 编码器的输入为 2304 ? 0.5=1152 bit,每个时钟周期输入 96 比特,所以需要 12 个时钟周期才将编码前的信息比特全部输入编码器。 下图为编码器的输出结果。本编码器输出结果只有校验位。由于编码器码率 为 1/2,所以,输出也是 1152 比特,每个时钟周期输出 96 比特,同样需要 12 个 时钟周期输出结束。对于结果的核对,是采用将下板的数据输出,用 matlab 来比

63

电子科技大学硕士学位论文

对完成核对。 图 5-8 中 展 示 出 编 码 器 输 出 的 详 细 结 果 。 encoder_out 为 编 码 输 出 , encoder_out_flag 是编码器输出指示,encoder_out_ref 是保存在 ROM 中的 Matlab 计算出的正确的编码值,encoder_out_diff 是编码结果的值与编码结果参考值的差。 从图中可以看出,encoder_out_diff 的值为零,从而验证了编码结果的正确性。

图 5-8 编码器板级验证仿真图(二)

5.1.2

LDPC 译码器的板级验证

第四章中已经对译码器的算法以及硬件实现结构进行了分析,对其硬件实现 也做了仿真,本节主要研究译码器的板级验证过程详情。本文实现的译码器是多 码长多码率的 QC-LDPC 译码器,使用的参数是基于 802.16e 协议,支持最大码长 为 802.16e 协议的两倍 4608。四种码率分别为:1/2,2/3,3/4,5/6。以下的验证 展现的是码长 2304,码率 1/2 下进行的测试。 如图 5-9 为译码器的板级验证的实现图:

图 5-9 译码器板级验证仿真图(一)

下板验证的参数采用码长 2304、码率为 1/2 为例。 从图中可以看出,译码器的输入数据是连续输入了四帧数据。由于译码器的 先验信息是量化为 6 比特,因此,数据输入是利用了 6 路并行的方式,每一路 96

64

第五章 LDPC 编译码器的验证与测试

比特。下面图 5-10 是译码器的输出模块的板级验证图:

图 5-10 译码器板级验证仿真图(二)

从图 5-10 中可以看出, 输出采用了两路 data_out_a、 data_out_b 两路同时输出, 经过 48 个时钟将四帧码字全部输出。每个码字输出时,data_out_flag 为高有效。 另外,data_out_a_ref、data_out_b_ref 为译码的参考信号,从图 5-11 中可以看出 data_out_a 与 data_out_a_ref 、 data_out_b 与 data_out_b_ref 都 相 等 , 其 差 data_out_a_diff 和 data_out_b_diff 也都为零,从而验证了译码的正确性。

图 5-11 译码器板级验证仿真图(三)

5.4 LDPC 编译码器的性能分析
前文对 QC-LDPC 编码器和译码器的算法仿真以及硬件实现进行了详细的研 究和分析。本节主要对 QC-LDPC 编码器和译码器的实现性能参数进行分析和研 究。 本文旨在实现一个高速的 LDPC 编码器和译码器,所以在本文的实现中,最 关键的性能指标就是吞吐率(Throughput) 。吞吐率是指单位时间内译码器处理数 据的能力。下面将对吞吐率分别在编码器和译码器中进行研究和分析。

5.5.1

LDPC 编码器的性能分析

用 ISE 软件综合得到的资源消耗, 所选的芯片是 Xilinx 的 K7 系列的 xc7k325t, 从表 5-2 中可以看出编码器的资源消耗并不大。
65

电子科技大学硕士学位论文 表 5-2 编码器的硬件资源消耗表 Device Utilization Summary Slice Logic Utilization Used Available Number of Slice Registers 4,532 407,600 Number of Slice LUTs 9,451 203,800 Number of occupied Slices 3,185 50,950 Utilization 1% 4% 6%

在编码器的硬件实现中,还有一些特别重要的指标,比如最大时钟频率和编 码器吞吐率。 对于最大时钟频率可以利用 ISE 自带的管教约束软件 Constraint Editor 来进行约束时钟频率(如图 5-12) 。

图 5-12 对时钟信号进行约束

经过约束后,重新综合,根据得到时钟的综合报告(如图 5-13)可以得到编 码器的最小时钟周期可以达到 3.986ns ,说明编码器的最大时钟频率可以达到 250MHz。根据这些参数就可以求出一些关键的参数,比如吞吐率。

66

第五章 LDPC 编译码器的验证与测试

图 5-13 编码器的时钟约束报告

另一个重要的参数就是编码器的吞吐率,根据吞吐率的定义[34]如式(5-1)
Throughput ? 码长 ? f max 一帧码字编码需要的时钟数

(5-1)

将我们编码的参数代入式(5-1),就可以求出编码器的吞吐率。一帧码字进入 编码器的比特数为 2304 ?1/ 2 ? 1152 ,从图 5-13 可以观察得出,第一个进入的码字 开始后经过 21 个时钟周期,输出端开始输出编码结果。最大时钟频率为 250MHz。 代入公式,可以求得编码器的吞吐率为 13.7Gbps。 由于不同码率、相同码长的码字对应的校验矩阵列数相同,即编码所需的时 钟周期数相同,所以不同码率的编码器的吞吐率都是 13.7Gbps。

5.5.2

LDPC 译码器的性能分析

同编码器相似,首先对译码器的资源消耗进行分析。如表 5-3 为 QC-LDPC 译 码器的资源消耗统计表。
表 5-3 QC-LDPC 译码器的资源消耗表 Device Utilization Summary Slice Logic Utilization Used Available Number of Slice Registers 19,833 407,600 Number of Slice LUTs 37,835 203,800 Number of Block RAM/FIFO 131 445 Number of fully used LUT-FF 10,877 46,791 pairs Utilization 1% 18% 29% 23%

在译码器的实现中中,吞吐率的定义为:
Throughput ? 码长 ? 4 ? f max 一次迭代的时钟周期数 ? 迭代次数

(5-2)

从吞吐率的定义可以看出,译码器的码长、迭代次数、每次迭代需要的时钟 周期数、最大时钟周期数有关。因此,在硬件设计实现中,必须想方设法减小时 钟周期数、迭代次数并且提高时钟周期。公式(5-2)分子上码长乘以 4 是因为本文 采用了 4 个码字同时译码的结果。
67

电子科技大学硕士学位论文

在减小时钟周期方面,我们采用了部分并行的方式。在资源消耗允许的情况 下尽可能地提高并行度,从而提高了单位时间译码器处理数据的能力。另外,本 文选择了收敛速度快的 TDMP 类的水平分层迭代译码结构,从而提高了吞吐率。 另外,还需要从 RTL 级代码上调试,来提高译码器的时钟频率。 下面将分析本文所实现的译码器的吞吐率。 为了求得最大的时钟频率,本文对设计进行了静态时序分析,以求得最大的 时钟频率,从图 5-14 中可以看到,本文的译码器的关键路径耗时为 3.892ns,从而 可以计算得出,最大时钟频率约为 250MHz。

图 5-14 QC-LDPC 译码器时钟约束报告

前面已经可以得知所有求吞吐率所需的变量。因此可以对本文实现的不同码 率的译码器进行计算吞吐率。接下来本文分别对码长为 2304,码率为 1/2、2/3、 3/4 和 5/6 四种情况下的吞吐率进行了研究和分析。
表 5-4 QC-LDPC 译码器吞吐率计算 码长 码率 1/2 2/3 3/4 5/6 最大 行重 7 10 15 20 行 数 12 8 6 4 总迭代周 期数 1459 1395 1555 1395 最大时 钟频率 吞吐率 1.58Gbps 1.65Gbps 1.48Gbps 1.65Gbps

2304

250MHz

从表 5-4 中可以看到,本文设计的译码器的吞吐率基本可以达到 1.5Gbps。最 大的吞吐率可以达到 1.65Gbps。

5.5 本章小结
本章对 FGPA 的硬件实现的原理及步骤做了简要研究, 并对 QC-LDPC 编码器 和译码器的验证方法进行了说明。 随后对本文中设计的多码长多码率 QC-LDPC 编 码器和译码器进行了板级验证, 对设计的准确性进行了验证。 另外分别对 QC-LDPC 编码器和译码器的性能进行了研究和分析。最后,系统的最大时钟频率达到 250MHz,编码器的吞吐率为 13.7Gbps,译码器的最大吞吐率为 1.65Gbps。

68

总结与展望

第六章
6.1 总结

总结与展望

本文对 LDPC 编码技术和译码技术进行了系统地分析。首先,第一章对信道 编码技术的重要性、LDPC 码的发展历史与现状进行了分析,并结合未来移动通信 的应用对 LDPC 码的前景进行了展望。另外对 FPGA 技术进行了研究。第二章对 LDPC 码的基本技术基础进行了研究,着重分析了可以充分利用部分并行结构的 QC-LDPC 编码技术。 然后,第三章和第四章分别对 LDPC 编码和译码进行了算法层面的分析和硬 件实现结构的分析。 对于 LDPC 编码, 主要研究了生成矩阵法、 高斯消元法、 Efficient 算法等算法。由于选择了 802.16e 协议中的参数,因此,选择适合 802.16e 实现的 Efficient 算法。并对此算法进行了硬件实现,实现结构采用了流水线结构,实现了 高速编码。 第四章主要对 LDPC 译码进行了分析和研究。算法方面,主要研究了基于概 率测度的 BP 译码算法、基于对数似然比的 BP 译码算法、归一化最小和算法等算 法。并对几种译码算法进行了初步比较。最后选择了适合硬件实现的归一化最小 和译码算法。在实现结构方面,主要有 TPMP 结构和 TDMP 结构两种实现结构。 本文对这两种结构进行了仿真对比,最后选择了 TDMP 结构并进行了硬件实现。 并且对译码器的硬件实现结构进行了详细的分析。译码结构采用了乒乓操作、流 水线、四码字同时译码等技术,用于提高译码器的性能。 第五章对 LDPC 编码器和译码器进行了板级验证。分别对验证方案和验证平 台进行了研究和分析,对板级验证进行了研究。 通过本文的研究,可以得出以下结论: (1)对于 LDPC 编码算法,Efficient 编码算法比较适合应用在具有准双对角 线结构的校验矩的 LDPC 编码中;尤其对于 QC-LDPC 码,可以充分利用其准循环 特性,提高编码效率,降低编码复杂度; (2)在 LDPC 译码算法中,归一化最小和译码算法或者偏移量最小和译码算 法是目前最适合 FPGA 实现的算法; (3)在 LDPC 译码实现中,QC-LDPC 译码可以充分利用部分并行结构、乒 乓操作、分层迭代结构来提高译码器的吞吐率; (4)本文最终实现了多码长多码率的 LDPC 编码器和译码器。编码器的吞吐 率为 13.7Gbps,译码器的吞吐率可以达到 1.65Gbps,已经达到了设计的目标,时
69

电子科技大学硕士学位论文

钟频率为 250MHz。

6.2 展望
目前,由于 LDPC 码编码和译码的高复杂度,其都是在 FPGA 上实现。本文 实现了吞吐率为 13.7Gbps 的多码长多码率 QC-LDPC 编码器和吞吐率为 1.65Gps 的多码长多码率 QC-LDPC 译码器。 未来 LDPC 的发展基本会有以下几个方向: (1) 性能算法方面提升。虽然目前 LDPC 编码和译码算法都比较成熟,基 于现有的 BP 译码算法, 继续探索新的译码性能更好的算法。 使得 LDPC 译码收敛速度更快,更容易接近香农极限。 (2) 译码实现结构方面,随着 FPGA 技术的发展,单个 FPGA 芯片上的逻 辑资源越来越丰富,这为 LDPC 译码器的实现提供了很好的发展契机。 LDPC 译码器的并行度可以进一步提升, 这样减少译码迭代所需的时钟 周期,从而进一步提升 LDPC 译码器的吞吐率。 (3) 随着 ASIC 技术的发展,其已经得到了广泛的关注。目前,LDPC 译码 器的硬件实现已经有很多人在 ASIC 上实现,ASIC 可以直接面向用户 的需求、运行速度快等优点,在大量投产的时候成本也比较低。因此, ASIC 成了未来 LDPC 译码器实现的另一个发展方向。

70

致 谢

致 谢
时光飞逝,依稀记得刚来到成电的青涩,迷茫,如今在成电学习已有七载, 马上就要离开,心中百般不舍。七年中,太多的人太多的事让我带来巨大的成长。 非常感谢成电遇到的每一位朋友,每一位老师。 非常感谢我的导师阎波教授,阎波老师不仅仅在学术上严谨认真、待人和蔼。 而且在生活中更像是一位姐姐,一位朋友。没有老师的威严,没有老师的严肃, 闪现在我脑海中只有一张灿烂的笑脸。对于同学们的不足,阎老师总是很耐心地 指导和教诲。不管是学术还是做人的方式,都值得我一辈子去学习。能拥有阎老 师这样一位导师,我感到非常骄傲。 非常感谢教研室的李广军老师、林水生老师、杨海芬老师、周亮老师、黄乐 天老师在科研道路上给我的指点迷经,尤其李广军老师对整个通信和 IC 行业的高 瞻远瞩,值得我们每位同学去学习。 非常感谢 LTE 项目组的每一位成员:丁宁、郑和、潘毓平、李杨波、刘雨非。 和你们在一起真的很幸福,很开心。很高心我们都能留到成都。 非常感谢在成都七年中遇到的每一个朋友。成都,真的是一座来了就不想离 开的城市,感谢成都的美食~ 再次非常感谢我的导师阎波教授对我毕业设计和论文的辛勤指导,感谢阎老 师耐心地督促,让我们在写论文的时候有着充分多的时间。 最后,非常感谢我的父母。非常感谢他们辛勤的培养,终于要走向社会,可 以报答他们的时候。 最后的最后,感谢我自己,感谢自己一步一步的选择,好不容易走到今天, 毕业以后才是人生真正的开始。生命不息,奋斗不止,祝福我自己~

71

电子科技大学硕士学位论文

参考文献
[1] 李晓峰, 周宁, 周亮, 等. 通信原理[M]. 北京:清华大学出版社, 2008, 23-24. [2] Shannon C E. A mathematical theory of communication[J]. ACM SIGMOBILE Mobile Computing and Communications Review, 2001, 5(1): 3-55. [3] Gallager R G. Low-density parity-check codes[J]. Information Theory, IRE Transactions on, 1962, 8(1): 21-28. [4] Tanner R M. A recursive approach to low complexity codes[J]. Information Theory, IEEE Transactions on, 1981, 27(5): 533-547. [5] Willenegger S. cdma2000 Physical layer: an overview[J]. Communications and Networks, Journal of, 2000, 2(1): 5-17. [6] Luby M G, Mitzenmacher M, Shokrollahi M A, et al. Improved low-density parity-check codes using irregular graphs[J]. Information Theory, IEEE Transactions on, 2001, 47(2): 585-598. [7] Chung S Y, Forney Jr G D, Richardson T J, et al. On the design of low-density parity-check codes within 0.0045 dB of the Shannon limit[J]. Communications Letters, IEEE, 2001, 5(2): 58-60. [8] Fossorier M P C. Quasicyclic low-density parity-check codes from circulant permutation matrices[J]. Information Theory, IEEE Transactions on, 2004, 50(8): 1788-1793. [9] 吉华芳, 毕光国, 张在琛. LDPC 码及其与 Turbo 码的比较[C], 第九届全国青年通信学术会 议论文集, 北京, 2004, 55-57. [10] Kschischang F R, Frey B J, Loeliger H A. Factor graphs and the sum-product algorithm[J]. Information Theory, IEEE Transactions on, 2001, 47(2): 498-519. [11] Darabiha A, Carusone A C, Kschischang F R. Block-interlaced LDPC decoders with reduced interconnect complexity[J]. Circuits and Systems II: Express Briefs, IEEE Transactions on, 2008, 55(1): 74-78. [12] Luby M, Mitzenmacher M, Shokrollah A, et al. Analysis of low density codes and improved designs using irregular graphs[C]. Proceedings of the thirtieth annual ACM symposium on Theory of computing(ACM), 1998: 249-258. [13] 王鹏. LDPC 码的编译码原理及编码设计[D]. 西安: 西安电子科技大学, 2003, 15-16. [14] Tian T, Jones C, Villasenor J D, et al. Construction of irregular LDPC codes with low error floors[C]. Communications, 2003. ICC'03. IEEE International Conference on. IEEE, 2003, 5: 3125-3129.

72

参考文献 [15] 贺鹤云. LDPC 码基础与应用[M]. 北京: 人民邮电出版社, 2009, 30-32. [16] 贺玉成. 基于图模型的低密度奇偶校验码理论及其应用研究[D]. 西安: 西安电子科技大 学, 2002, 21-22. [17] MacKay D J C. Good error-correcting codes based on very sparse matrices[J]. Information Theory, IEEE Transactions on, 1999, 45(2): 399-431. [18] Yu Kou, Shu Lin and Mare P C Fossorier. Low-density Parity-check Codes: Construction Based on Finite Geometrices[J]. Globecom 2000, 2000, 50-55. [19] IEEE. 802.16e. IEEE Standard for Local and metropolitan area networks. Part16: Air interface for fixed broadband wireless access systems[S], 2006. [20] 肖扬. Turbo 与 LDPC 编解码及其应用[M]. 北京: 人民邮电出版社, 2010, 112-113. [21] 董超科. 高速 LDPC 编译码硬件设计[D]. 哈尔滨: 哈尔滨工业大学, 2010, 4-6. [22] MacKay D J C, Wilson S T, Davey M C. Comparison of constructions of irregular Gallager codes[J]. Communications, IEEE Transactions on, 1999, 47(10): 1449-1454. [23] Richardson T J, Urbanke R L. Efficient encoding of low-density parity-check codes[J]. Information Theory, IEEE Transactions on, 2001, 47(2): 638-656. [24] 曹建林. LDPC 的硬判决译码研究[M]. 电子与封装. 2006, 6(12):31-33. [25] Fossorier M P C, Mihaljevic M, Imai H. Reduced complexity iterative decoding of low-density parity check codes based on belief propagation[J]. Communications, IEEE Transactions on, 1999, 47(5): 673-680. [26] Richardson T J, Urbanke R L. The capacity of low-density parity-check codes under message-passing decoding[J]. Information Theory, IEEE Transactions on, 2001, 47(2): 599-618. [27] Sham C W, Chen X, Tam W M, et al. A layered QC-LDPC decoder architecture for high speed communication system[C]. Circuits and Systems (APCCAS), 2012 IEEE Asia Pacific Conference on. IEEE, 2012: 475-478. [28] Cui Z, Wang Z, Zhang X. Reduced-complexity column-layered decoding and implementation for LDPC codes[J]. Communications, IET, 2011, 5(15): 2177-2186. [29] Wang Z, Cui Z. A memory efficient partially parallel decoder architecture for quasi-cyclic LDPC codes[J]. Very Large Scale Integration (VLSI) Systems, IEEE Transactions on, 2007, 15(4): 483-488. [30] Mansour M M. A turbo-decoding message-passing algorithm for sparse parity-check matrix codes[J]. Signal Processing, IEEE Transactions on, 2006, 54(11): 4376-4392.

73

电子科技大学硕士学位论文 [31] Zhao S, Zhou X, Ying F, et al. Memory size reduction for LDPC layered decoders[C]. Circuits and Systems (APCCAS), 2010 IEEE Asia Pacific Conference on. IEEE, 2010: 426-429. [32] Mansour M M, Shanbhag N R. High-throughput LDPC decoders[J]. Very Large Scale Integration (VLSI) Systems, IEEE Transactions on, 2003, 11(6): 976-996. [33] 夏宇闻. Verilog 数字系统设计教程[M]. 北京: 北京航空航天大学出版社, 2003, 3-5. [34] Heidari T, Jannesari A. Design of high-Throughput QC-LDPC Decoder for WiMAX standard[C]. Electrical Engineering (ICEE), 2013 21st Iranian Conference on. IEEE, 2013: 1-4.

74

个人简历及攻读硕士学位期间的研究成果

个人简历及攻读硕士学位期间的研究成果
个人简历: 孔宪章,男,汉族,籍贯山西省平遥县,1989 年 4 月 24 日生。 2008 年 9 月~2012 年 6 月,就读于电子科技大学微电子与固体电子学院电子科学 与技术专业,获工学学士学位。 2012 年 9 月~2015 年 6 月,就读于电子科技大学通信与信息工程学院通信与信息 系统专业,攻读硕士学位。 科研经历: 2013 年 2 月至 2015 年 3 月,LDPC 编译码算法及实现的研究; 2013 年 9 月至 2014 年 9 月, 面向 TD-LTE 及其演进技术的通用仿真与验证平台研 究与开发。 获奖情况: 2012 年 2013 年 研究生新生二等奖学金 研究生学业一等奖学金 校级优秀研究生 第四届《新创意?创意心》大赛 实物组银奖 创意组铜奖 2014 年 研究生学业二等奖学金 第十二届研究生电子设计大赛(EDA)上机组一等奖 第八届研究生烹饪大赛 二等奖 华为企业人俱乐部 优秀部员

75

LDPC编译码技术的研究与实现
作者: 学位授予单位: 孔宪章 电子科技大学

引用本文格式:孔宪章 LDPC编译码技术的研究与实现[学位论文]硕士 2015


相关文章:
LDPC编译码技术的研究与实现_图文.pdf
电子科技大学 UNIVERSITY OF ELECTRONIC SCIENCE AND TECHNOLOGY OF CHINA 硕士学位论文 MASTER THESIS 论文题目 LDPC 编译码技术的研究与实现 学科专业 学号 通信与...
LDPC译码方法研究及实现_图文.pdf
2007 年第 4 期 通信与广播电视 1 LDPC 译码方法研究实现万福 * 简伟摘 * * 吕一希要 * * * 本文主要研究了低密度校验码 ( LDPC 码 ) 的编译码方法...
LDPC码编译码器的原理及其硬件实现_图文.pdf
仿真硬件实现的方法,对 LDPC 码的编译码原理、算法进行了研究,设计了 LDPC ...随着 LDPC 码理论的日趋完善,实现方式的不断改善 LSI 技术的进步,LDPC 码...
LDPC编译码原理课件_图文.pdf
LDPC编译码原理课件_信息与通信_工程科技_专业资料。LDPC码 2011-4-19 1 目录...LDPC码编译码研究与实现 暂无评价 3页 1.50 【硕士论文】LDPC码的编......
LDPC编码的研究与硬件实现_图文.pdf
北京邮电大学 硕士学位论文 LDPC编码的研究与硬件实现 姓名:唐启荣 申请学位级别:...LDPC编译码技术的研究与... 暂无评价 88页 2下载券 LDPC码实现及并行级联...
LDPC码构造及编译码技术研究.pdf
LDPC码构造及编译码技术研究 - 专题聚焦 中文核心期刊 LDPC 码构造及编译码技术研究 黄戈, 余松煜, 管云峰, 潘宇 (上海交通大学 图像通信与信息处理研究所, ...
LDPC码的编译码算法研究.doc
LDPC码的编译码算法研究 - LDPC 码的编译码算法研究 通信技术发展十分迅
LDPC码及其译码实现.doc
LDPC码及其译码实现_信息与通信_工程科技_专业资料。LDPC,Gallager,BP算法,Log-...LDPC编译码技术的研究与... 暂无评价 88页 2下载券 LDPC的FPGA实现 暂无评价...
LDPC码的编译码方法研究.doc
LDPC 码的编译码方法研究低密度奇偶校验(Low-Density Parity-Check,LDPC)码作为一种逼近香农极 限的信道编码,具有描述简单、译码复杂度低、可以并行实现、错误平台...
星载多进制LDPC码编译码方法的研究_图文.pdf
星载多进制LDPC编译码方法的研究_信息与通信_工程科技_专业资料。本文描述了星载多进制LDPC编译码方法的研究方法,具体对现阶段国内外多进制LDPC的研究现状...
LDPC码的编译码算法研究本科毕业论文.doc
LDPC码的编译码算法研究本科毕业论文 - 毕业论文 题目: LDPC 码的编译码算法研究 II 摘 要 低密度奇偶校验码(Low Density Parity Check Cod...
(完整版)LDPC码的编译码算法研究本科毕业论文.doc
(完整版)LDPC码的编译码算法研究本科毕业论文 - 单片机论文,毕业设计,毕业论文,单片机设计,硕士论文,研究生论文,单片机研究论文,单片机设计论文
(最新版)LDPC码的编译码算法研究本科毕业论文.doc
(最新版)LDPC码的编译码算法研究本科毕业论文 - 毕业论文,单片机论文,毕业论文设计,毕业过关论文,毕业设计,课程设计,硕士论文,研究生论文
5G通信系统中LDPC编译码器的设计与实现.doc
5G通信系统中LDPC编译码器的设计与实现 - 5G 通信系统中 LDPC 编译码器的设计与实现 目前,移动通信系统研究已进入 5G 时代,信道编码作为关键技术之一,主要 用于...
LDPC编译码仿真.doc
除去了长为 4 的短循环,能提高译码的准 确度,利于译码的实现,但是也有可能...LDPC编译码技术的研究与... 暂无评价 88页 2下载券 LDPC码编译码原理及算法...
LDPC的FPGA实现_图文.pdf
LDPC的FPGA实现_信息与通信_工程科技_专业资料。 摘要 摘要 随着信息的高速增长...通常的研究中, 人们的注意力主要集中于如何构造好码以及更好的编译码算 法,而...
基于IEEE80216e协议的LDPC码编译码算法的研究_图文.pdf
西安电子科技大学 硕士学位论文 基于IEEE802.16e协议的LDPC编译码算法的研究 姓名:包秋艳 申请学位级别:硕士 专业:通信与信息系统 指导教师:李兵兵 20100601 摘要...
基于CCSDS标准的LDPC编译码应用技术研究.doc
基于CCSDS标准的LDPC编译码应用技术研究 - 龙源期刊网 http://www.qikan.com.cn 基于 CCSDS 标准的 LDPC 编译码应用技术 研究 作者:张庆林等 来源:...
IEEE802_11nLDPC译码的设计与实现_图文.pdf
IEEE802_11nLDPC译码的设计与实现 - 2 8卷第2期 201 1年
基于CCSDS标准的LDPC编译码应用技术研究_论文.pdf
基于CCSDS标准的LDPC编译码应用技术研究 - 软 件园 Industry focus 基于C CSDS 标准 的L DPC 编译码应用技术研究 张庆...