OFDM系统中Turbo编码混合ARQ技术的研究和实现 答辩人：刘伟峰 指导老师：朱杰

背景概述 Bell Joint Lab

课题背景 高频短波通信 抗毁能力极强 覆盖范围广 运行成本低 机动灵活 战争、自然灾害、边远地区的主要通信方式 Bell Joint Lab

研究重点 Turbo码的原理、仿真和设计 Turbo编码混合自动重复请求方案 系统模块的DSP实现与优化 Matlab建模仿真 矩阵推导MAP算法 短帧Turbo码的设计方法 Turbo编码混合自动重复请求方案 现有方案的分析比较 提出新颖的“分而治之Turbo编码HARQ”方案 系统模块的DSP实现与优化 循环冗余校验码的快速实现 Max-Log-MAP算法的实现与优化 Bell Joint Lab

OFDM——抗多径衰落的尖兵 频谱划分成窄的平坦衰落子信道 串并变换后，每个子信道上的符号速率下降，可以很好的对抗时延扩展 把频率和时间选择性衰落的影响随机化，有利于纠错码工作 一个频率选择性信道→多个非频率选择性信道 Bell Joint Lab

OFDM的Matlab实现 Bell Joint Lab

Turbo码的原理、仿真和设计 Bell Joint Lab

Turbo码——接近Shannon限的好码 编码器由两个递归系统卷积码通过交织器级联的方式结合而成，以较小的编译码复杂度，生成码重分布优良的长码 译码器采用迭代的方式，两个分量译码器互相帮助，充分利用码子的约束信息 在短约束长度、长分组以及10到20次迭代的情况下，Turbo码在误码率（BER）10e-5处距离Shannon限0.5dB左右 Bell Joint Lab

Turbo编码器 并行级联卷积编码器 串行级联卷积编码器 Bell Joint Lab

Turbo解码器 并行级联卷积译码器 Bell Joint Lab

软输入软输出分量译码器 对数似然比（LLR） Y是观测，uk 是估计值 符号表示0，1比特，幅度表示可靠程度 Bell Joint Lab

MAP算法 想法 计算 特点（相比维特比算法） 把比特的概率估计转化为状态转移的概率估计 把状态转移的概率估计以递推形式计算 三种度量，两次递推，一步到位 特点（相比维特比算法） 复杂度大（乘法，除法，指数，对数计算） 卷积译码无优势 可以输出译码软信息 Bell Joint Lab

MAP算法 前向度量 后向度量 分支度量 前向递推 后向递推 后验概率LLR Bell Joint Lab

MAP算法的计算流程 计算分支度量 前向递推计算前向度量 后向递推计算前向度量 综合计算后验概率LLR Bell Joint Lab

MAP算法的矩阵表示 前向度量 后向度量 分支度量矩阵 前向递推 后向递推 Bell Joint Lab

MAP算法的矩阵表示 Bell Joint Lab

MAP的简化算法——Max-Log-MAP 指数运算和乘法运算的噩梦 变换到对数域中 利用近似公式 Bell Joint Lab

Max-Log-MAP算法 简化前向递推 简化后向递推 支路度量计算 后验概率计算 Bell Joint Lab

Log-MAP算法 近似导致性能损失 引入纠正项 Bell Joint Lab

串行级联卷积码系统Matlab实现 Bell Joint Lab

并行级联卷积码系统Matlab实现1 Bell Joint Lab

并行级联卷积码系统Matlab实现2 Bell Joint Lab

Turbo码仿真1之译码器结构——迭代次数 Bell Joint Lab

Turbo码仿真1之译码器结构——误码率 Bell Joint Lab

短帧Turbo码的设计要点1 译码器结构的选择：PCCC结构的误码平层大约为1e-5，而SCCC结构能够提供更低的误码平层（大约1e-7），SCCC需要更多的迭代次数达到误码平层，本身的译码复杂度也是远远高于PCCC（内编码器是4进制输入，8进制输出，格形图上有16个状态，每个状态出发有4条路径，每个状态有4条路径交汇）。在本系统中，我们选择PCCC结构。 Bell Joint Lab

Turbo码仿真2之分量码——递归 Bell Joint Lab

Turbo码仿真2之分量码——生成多项式 Bell Joint Lab

Turbo码仿真2之分量码——约束长度 Bell Joint Lab

短帧Turbo码的设计要点2 分量码的选择：分量码必须是递归形式的，递归形式的分量码对于Turbo码减少低码重码子起着十分重要的作用，分量码的生成多项式也起着十分重要的作用，必须优化设计，分量码的约束长度对于Turbo码的作用十分有限，增大分量码的约束长度导致译码器复杂度的增加。在本系统中，我们推荐使用poly2trellis(3, [7 5],7)分量码。 Bell Joint Lab

Turbo码仿真3之帧长 Bell Joint Lab

短帧Turbo码的设计要点3 帧长：对于Turbo码的性能而言，希望帧长越长越好，虽然帧长度的增加不会增加单位比特译码的复杂度，但是帧长直接决定了系统传输的时间延迟和译码存储空间，所以帧长度的选择必须折中考虑。一般的对于语音系统，帧长为200比特左右，对于视频系统，帧长为1000比特左右。本系统中，我们使用256比特作为帧的长度。 Bell Joint Lab

Turbo码仿真4之交织器——SCCC Bell Joint Lab

Turbo码仿真4之交织器——PCCC Bell Joint Lab

Turbo码仿真4之交织器——奇偶分离 Bell Joint Lab

短帧Turbo码的设计要点4 交织器：交织器在Turbo码系统中也是一个十分重要的组件，相比较差的交织器，良好的交织器可以提供大约0.2dB到1dB左右的增益，大量的试验证明，一般的随机交织可以取得良好的性能，代数交织和随机交织的性能相当，但是随着帧长的变小，随机交织的优越性会消失，直至我们必须“刻意”的设计交织器，才能使Turbo码正常工作。随机交织对于帧长度没有约束，代数交织器一般对于帧长有着特殊的要求，矩阵交织器同样要求帧长能够分解成两个相近数的乘积。所有的交织器都可以通过查表的方式完成。本系统中，我们推荐使用随机交织。 Bell Joint Lab

Turbo码仿真5之译码算法——简化 Bell Joint Lab

Turbo码仿真5之译码算法——量化比特数 Bell Joint Lab

短帧Turbo码的设计要点5 译码算法：Log-MAP算法和MAP算法相当，Max-Log-MAP有大约0.5dB的性能损失，MAP算法复杂度最大，Log-MAP和Max-Log-MAP计算量相近，但是Max-Log-MAP算法在结构上最接近维特比算法，容易在DSP上快速实现。3比特的量化足够，但是在高信噪比区，推荐6比特量化。在本系统中，我们使用Max-Log-MAP算法，6比特量化。 Bell Joint Lab

Turbo码仿真6之打孔 Bell Joint Lab

短帧Turbo码的设计要点6 打孔：打孔可以提高码率，但是会带来误码率方面的性能损失，打孔的选择应该基于系统设计要求的考虑，没有孰优孰劣的问题。本系统中，我们使用1/2码率的Turbo码，打孔方式取经典方案。 Bell Joint Lab

Turbo码仿真7之结尾 Bell Joint Lab

短帧Turbo码的设计要点7 结尾策略：对于帧长大约1000比特的系统，无需考虑迫零处理，当帧长小于50比特，我们采用方案4迫零处理。 Bell Joint Lab

Turbo码混合ARQ系统 Bell Joint Lab

Turbo编码混合ARQ系统 Bell Joint Lab

传统HARQ分类 Type I HARQ：数据被加以CRC并用FEC编码，重传时，错误分组被丢弃，重传分组与前一次相同。 Type II HARQ：考虑无线信道的时变特性，在首次传输数据块时没有或带有较少的冗余，如果传输失败，重传的数据块不是首次所传数据块的复制，而是增加了其中的冗余部分。在接收端将两次收到的数据块进行合并，编码速率下降而提高编码增益。 Type III HARQ：与第二类HARQ不同的是重传码字具有自解码能力，因此接收端可以直接从重传码字当中解码恢复数据，也可以将出错重传码字与已有缓存的码字进行合并后解码。 Bell Joint Lab

Turbo码HARQ I型 我们用ARQ I型广义的表示发送端在重发数据分组时，不生成新的码子，与传统定义不同的是，接收端不一定丢弃首发分组，完全可以利用首发的信息，增加系统的通过率。 这种ARQ机制的优点是系统充分利用了硬件资源，编译码器的结构和控制都比较简单，有利于系统降低复杂性和减少功耗。 Bell Joint Lab

Turbo码HARQ I型 接力棒式Turbo码HARQ 在发方，首先将欲传信息经Turbo编码器编码后发送出去，接收端经过Turbo译码，如果通过CRC检错校验，反馈ACK信号回发送端，如果不能通过CRC检错校验，则反馈NACK信号到发送端； 发送端收到重发指令，则将该信息的原先的码子重新发送； 在收方，对于重发帧的译码，可将上一帧的译码结果用作先验信息，并用于Turbo译码器进行译码。如果译码结果通过CRC检错校验，反馈ACK，否则反馈NACK； 重复第2、第3步，直到发送端收到ACK信号，或者达到最大的重发次数，放弃此次通信。 Bell Joint Lab

Turbo码HARQ II型 我们用ARQ II型表示发送端在重发数据分组时，生成新的校验信息，即所谓的增量冗余信息，但是新的分组没有自解码性质。 ARQ I型：简单的“重复码”，其最小码距是原来的L倍；实际上，通过L次重发可以构成纠错能力更强的纠错码。 这种ARQ机制的优点是能够充分利用重发的分组资源，纠错能力比I型更强，但是系统的编译码硬件设计必须以最低码率的纠错码设计，而系统一般运行在较高的码率水平上，所以不能充分利用硬件资源，编译码器的结构和控制相对复杂。 Bell Joint Lab

Turbo码HARQ II型 速率兼容打孔Turbo码HARQ 发送端生成L*N比特长度的Turbo码，经过打孔形成N比特长度分组，发送到信道，并且保存被删除的其他校验比特； 接收端接收到分组，经过Turbo译码，如果通过了CRC检错，发送ACK信号，否则，发送NACK信号； 发送端收到NACK信号，并累计重发次数，发送剩余的相应的N比特校验比特； 接收端接收到重发分组后，与首发分组组成新的码子，经过Turbo译码，如果通过了CRC检错，发送ACK信号，否则，发送NACK信号； 发送端收到NACK信号，并累加重发次数，发送剩余的相应的N比特校验比特； 接收端接收到重发分组后，与前两次的分组组成新码子，经过Turbo译码，如果通过CRC检错，发送ACK信号，否则，发送NACK信号； 重复上述过程，直到发送端收到ACK信号，或者重发次数达到最大的L次，放弃本次通信。 Bell Joint Lab

Turbo码HARQ II型 Turbo码分而治之HARQ 基本思想是：假设系统是1/2码率的Turbo码，我们的编译码硬件设计也是按照基本的1/2码率的Turbo码来设计，当发送端被要求重发时，我们可以把信息序列分成奇数位和偶数位两类，奇数位的信息比特保持不变，但是偶数位的信息比特用已知的“01”序列代替，然后经过编码器生成码子，实际上，新生成的码子的有效信息比特只有原来的一半，同时，码率也下降了一半，这也就意味着码子有着更强的纠错能力，在接收端，译码器首先对重发分组进行译码，运用相应的先验信息，得到关于信息序列奇数位比特的可靠信息，然后把这些信息反馈到第一个分组的译码器，通过奇数位比特的可靠信息来获得的正确译码。如果这时候，译码输出仍然没有通过CRC校验，那么在发送端可以把偶数位比特信息序列按奇偶分成2段，只传输其中1/4的信息比特，其他位置用已知序列填充，以此类推，最终获得正确译码。 Bell Joint Lab

分而治之方案的性能——误帧率 Bell Joint Lab

分而治之方案的性能——通过率 Bell Joint Lab

Turbo码HARQ III型 ARQ III型表示发送端在重发数据分组时，生成新的校验信息，同时新的分组具有自解码性质。 纠错能力和译码复杂度都介于I型和II型之间。与II型类似的是系统不能充分利用硬件资源，编译码器的结构和控制相对复杂。 Bell Joint Lab

Turbo码HARQ III型 多维Turbo码HARQ Turbo码本身就可以构成一种很好的ARQ机制，首先，利用分量码1生成码子1，发送到信道，如果接收端能正确接收，那么继续发送下一帧数据，如果不能，那么经过交织的信息序列利用分量码2，生成码子2，发送到信道，译码器先对码子2进行译码（可以利用第一次译码的结果作为先验信息），如果译码成功，就反馈ACK信号，如果失败，那么联合码子1和码子2进行Turbo迭代译码，如果译码成功那么就反馈ACK，如果到了预定的迭代次数，仍然没有通过CRC校验，那么反馈NACK信号，发送端可以进一步利用新的交织器和新的分量码，生成码子3，在接收端，译码器先利用前次译码结果作为先验信息，对码子3进行译码，如果成功就反馈ACK信号，如果失败，那么就把3个码子构成一个3维的Turbo码，进行译码，以此类推，直到译码成功 。 Bell Joint Lab

Turbo/HARQ系统DSP实现 Bell Joint Lab

BLACKFIN DSP介绍 高度并行的计算单元 高性能地址产生器 分层结构的内存 数据总线和程序总线分离的哈佛结构 流水线技术 独立多个乘加器单元 高性能地址产生器 循环缓冲 嵌套零开销循环 传输过程中饱和和限幅 分层结构的内存 较少的延迟 缩短的处理空载时间 Bell Joint Lab

BLACKFIN DSP程序优化 特殊指令的使用 并行指令的使用 DSP硬件资源的合理使用 数据在内存中的优化配置 流水线冲突 Bell Joint Lab

CRC算法原理 k位二进制数据序列 r位二进制校验码 n位二进制序列 生成多项式 满足 Bell Joint Lab

字节序列求余的递推算法 M字节的序列 Bell Joint Lab

CRC算法在BLACKFIN DSP上的实现 三字节序列算法 为形如[Da 0 0 ]的三字节构造一个余数表。对于M字节序列N，读取前3个字节数据构成最初的三字节序列[Da Db Di]，此时i=3，然后进入如下的循环： 根据Da查表求得[Da 0 0 ]的余数[Rh Rl]； 计算Db+Rh和Di+Rl，得到新的Da和Db； 判断i是否等于M，如果相等则循环结束，得到余数，否则，读取序列N中的下个数据字节Di+1，得到新的三字节序列，跳到2。 3次总线读，2次异或，1次加法，1次移位和1次寄存器赋值 Bell Joint Lab

CRC算法在BLACKFIN DSP上的优化 四字节序列算法 为形如[Da 0 0 0]的四字节和[Db 0 0]的三字节构造余数表。对于M字节序列N，读取前4个字节数据构成最初的四字节序列[Da Db D2i-1 D2i]，此时i=2，然后进入如下的循环： 根据Da查表求得[Da 0 0 0]的余数[Rah Ral]； 根据Db查表求得[Db 0 0]的余数[Rbh Rbl]； 计算[D2i-1 D2i]+[Rah Ral]+[Rbh Rbl]，得到新的Da和Db； 判断i是否等于[M/2]，如果相等则跳到6，否则，读取序列N中的下一个16位数据[D2i+1 D2i+2]，得到新的四字节序列[Da Db D2i+1 D2i+2]，跳到2。 如果M是偶数，结束得到余数[Da Db]，否则对三字节序列[Da Db DM]求余得到结果。 3次总线读，2次异或，2次加法，2次移位和4次寄存器赋值。 Bell Joint Lab

CRC算法优化结果 四字节算法相比三字节算法，平均对每个字节的操作少了1.5次总线读，1次异或，但是多了一次寄存器数据搬移 测试表明：效率提高33% Bell Joint Lab

Max-Log-MAP算法 简化前向递推 简化后向递推 支路度量计算 后验概率计算 Bell Joint Lab

Max-Log-MAP在BLACKFIN DSP上实现 支路度量的计算用Add on Sign指令完成。 递推计算为“加比选”蝶形计算，用VIT_MAX指令完成，2次16位的比较和选择 Bell Joint Lab

蝶形计算在BLACKFIN DSP上实现 运算量占整个译码器的80% Bell Joint Lab

蝶形计算在BLACKFIN DSP上实现 前向递推： 读取BM值； 读取度量Ak-1(0)； 读取度量Ak-1(1)； 计算Ak-1(0)+BM,Ak-1(1)-BM,Ak-1(0)-BM,Ak-1(1)+BM； VIT_MAX指令比较选择得到Ak(0)和Ak(2)； 保存度量Ak(0)和Ak(2)。 Bell Joint Lab

蝶形计算在BLACKFIN DSP上实现 后向递推： 读取BM值； 读取度量Bk(0)； 读取度量Bk(2)； 计算Bk(0)+BM,Bk(2)-BM,Bk(0)-BM,Bk(2)+BM； VIT_MAX指令比较选择得到Bk-1(0)和Bk-1(1)； 保存度量Bk-1(0)和Bk-1(1) 。 Bell Joint Lab

蝶形计算在BLACKFIN DSP上的优化 如果不进行优化，整个蝶形运算需要10条指令 本文从以下几个方面对ACS进行了优化： 第一，BLACKFIN是双40位ALU结构，一个时钟周期内可以完成4次16位加法。 第二，总线32位宽，一次可以读取或保存两个16位操作数。 第三，BLACKFIN具有数据处理和数据存取的并行处理能力。 第四，两组可嵌套的零开销循环加上4组循环缓冲的数据指针。 第五，合理的分配数据可以避免STALL现象的发生。 第六，流水线冲突。 Bell Joint Lab

蝶形计算在BLACKFIN DSP上的优化 前向递推： 读取BM || 读取度量Ak-1(0)，Ak-1(1)； 计算Ak-1(0)+BM,Ak-1(1)-BM,Ak-1(0)-BM,Ak-1(1)+BM； VIT_MAX指令得到和Ak(0)和Ak(2) || 保存度量Ak(0) || 保存度量Ak(2) ； Bell Joint Lab

Max-Log-MAP算法优化结果 主频600M的BLACKFIN处理器，数据帧长为1024，译码器迭代6次 译码时间为0.5ms 数据吞吐量为2Mbps 相对于优化前，译码速度提高了50%以上 Bell Joint Lab

结束语——工作小结 Matlab建模、编程和仿真； 用矩阵形式表达MAP算法； 给出短帧Turbo码的设计要点； 提出“分而治之Turbo/HARQ”方案，给出仿真结果； 系统的阐述了BLACKFIN DSP的程序优化问题； 提出了CRC的“四字节序列求余”改进算法； 优化了Max-Log-MAP算法，提高了Turbo译码器的数据吞吐量。 Bell Joint Lab

谢谢大家！——Q&A Bell Joint Lab