藏族风情

•

Turbo编码器提升毫微微蜂窝DSP的效率

2010年11月11日11:40:16 来源:大比特资讯 作者：ADI公司 Hazarathaiah Malepati, Yosi Stein

• Html文件格式可能无法显示特殊符号及公式，阅读全文，请点击下面按钮以Pdf文件格式浏览阅读

如未安装Pdf阅读器点击下面按钮下载安装

最近，小型毫微微蜂窝基站概念在移动应用中越来越受欢迎。与传统宏蜂窝相比，毫微微蜂窝在覆盖范围、兼容性和成本方面都具有优势。

由于成本和性能的制约，毫微微蜂窝设计必须具有与宏蜂窝大致相同的模块化水平和复杂度，并且与个人而非社群的经济承受能力相适应。

但是，为了实现至少与传统宏蜂窝系统相同的信号强度，毫微微蜂窝必须采用支持高达14.4 Mbps比特率的多通道设计。因此，设计人员面临着严峻挑战：利用系统的数字信号处理(DSP)引擎编码多通道比特流，同时为系统的其它关键操作提供足够的计算裕量。

本文介绍如何实现基于Turbo编码的高效算法以支持基于Blackfin的14.4 Mbps 3G毫微微蜂窝设计，该设计仅消耗Blackfin可提供的600 MIPS计算能力中的100 MIPS，从而为系统的其它必要操作留下了充沛的资源。

Turbo码性能卓越，因此自1993年推出以来，便在业界和学术界引起了极大的关注。Turbo码的工作效率几乎达到了香农所确定的信道容量极限，信噪比(SNR)间隔小于或等于0.7dB。

Turbo码最初由Berrou、Glavieux和Thitimajshima提出1，它是利用两个并行级联的卷积编码器构建而成。在Turbo编码方案中，同一信息序列的不同交织版本上产生两个分量码。在解码器端，使用两个最大后验概率(MAP)解码器以迭代方式解码判决结果。MAP解码算法使用接收到的数据和奇偶校验符号（对应于根据真实和交织形式的数据位计算而来的奇偶校验位）及其它解码器软输出（外部）的信息，产生更可靠的判决结果。

关于Turbo码的高效解码，学术界已提出了许多算法和实现技术，但有关如何高效实现Turbo编码器以支持高比特率应用的技术则不多见。在基站等应用中，一次须传输多个数据流。因此，必须高效实现Turbo编码器，使之能以较少的处理能力编码多个比特流。

毫微微蜂窝的服务对象是个体而非群体，因此用户将拥有专属的无线基础设施，能够为其所有移动设备提供良好的信号强度。就数据处理而言，宏蜂窝与毫微微蜂窝的模块和复杂度大致相同。但是，毫微微蜂窝设计的目标用户是个人而非群体，所以应做到价格低廉。因此，在毫微微蜂窝设计中使用多个昂贵的处理器件并不现实。本文并未阐述毫微微蜂窝完整架构的细节，

但在讨论用于无线网络纠错功能的3G标准2 Turbo编码时，已特别注意了毫微微蜂窝设计的预算要求。

3G Turbo编码器的实现

Turbo编码器主要包括两个成分编码器，一个交织器将二者隔开。3G Turbo递归系统码(RSC)编码器的原理框图如图1所示。每个RSC编码器均包括一个传递函数为(1+D+D3)的正向通道和一个传递函数为(1+D2+D3)的反馈通道。每个输入的交织地址产生过程参见3GPP的论文2。利用双MAC（乘法累加器）DSP（如Blackfin等）无法即时计算交织地址，除非我们有许多计算单元。

通常是预先计算交织地址，并将其存储在存储器中。存储的交织地址可以用于Turbo编码和解码。如果码字很大，则预计算的交织地址存储在L3存储器中，否则存储在L1存储器中。对于更大的码字，我们使用窗口方法编码或解码各位，并使用直接存储器访问方法根据需要从L3传输数据（如输入和交织地址等）。

由图1可知，对于每个输入，我们输出一个系统位Xi和两个奇偶校验位Yi和Zi。这里，奇偶校验位Zi并不直接取决于实际输入位bi，而是取决于交织缓冲器中索引为i的位b'i。给定N位的输入消息块B时，我们或者执行地址计算，从块B获得各输入位索引的交织位b'i，或者立即执行整个块B的交织，并存储为交织块B'，然后用索引i线性访问b'i。请注意，根据3G标准计算交织位地址并非易事，因此，我们倾向于在开始编码多个消息数据块之前，预先计算所有N位的地址，并将其一次性存储在存储器中。这样，我们就能忽略Turbo编码产生交织地址的复杂性。

简单编码。在简单编码中，我们逐位编码。对于每个输入位，我们输出三位。模拟RSC编码器的一段C代码样例如表1所示。通常，输入数据位以8位字节的形式从存储器存取，因为处理器可以从存储器存取的最小数据为一个字节（或一个8位量）。获得一个字节的数据后，为了逐位进行编码，必须拆包各位，每位需要大约1.125周期（总共9个周期：使用Blackfin rot指令，第一位拆包需要2个周期，其余各位需要1个周期）。然后，编码此位又需要7个周期，因为编码仅涉及到序列化操作。完成编码后，必须将编码位封包，并存储在存储器中，以便进行其它处理和传输。数据封包所需的周期数与拆包相同，即每位1.125周期。因此，编码1位数据并输出1个奇偶校验位总共需要10个周期（包括开销）。

计算复杂度。由于我们使用查找表来检索交织地址，而不是即时计算，因此只有访问查找表需要一些周期（可能不涉及计算操作）。交织一个数据位需要大约三个周期（一个周期用于加载偏移，两个周期用于计算绝对地址）。Turbo编码涉及到两个RSC编码器和一个交织操作，因此编码一个数据位总

共需要25个周期（包括开销）。对于14.4 Mbps比特率的毫微微蜂窝应用，我们需要大约360 MIPS，即约60%的Blackfin处理器MIPS。

Turbo码的处理

如前所述，如果实现不当，更高比特率的Turbo编码器将是一个昂贵的模块。接下来，我们将讨论高效实现Turbo编码器的技术。我们将Turbo编码器分为两部分：第一部分是来处理位的编码，第二部分是处理数据位的交织。

使用查找表进行编码。如前所述，使用两个RSC编码器进行Turbo编码时，每个输入位需要大约20个周期。下面我们将介绍一种不同的使用查找表方法，每个输入位只需2.5个周期（用于两个编码器）。为了存储查找表数据，需要256个字节的额外存储器。考虑到RSC编码器的目前状态，使用查找表一次可以编码多个位。通过预先计算长度L的输入位的所有可能组合和状态位的所有三种组合的查找表，我们一次可以编码L位。在这种编码中，我们使用的查找表含有2L+3项。随着L值增大，查找表也会增大。L=4时（换言之，一次编码4位），查找表含有27或12，如图2所示。各项包含4个编码位和3位更新状态信息。换言之，一个字节（或8位）足以代表查找表的各项。

深入研究8位查找表设计可以发现，为了从4个输入位（假设位于寄存器r0）和3个当前状态位（假设位于寄存器r1）计算12查找表的7位偏移，我们必须从输入字节（或从r0）提取（1个周期）4个数据位（假设存入寄存器r2），从前一编码的查找表输出（或从r1）提取（1个周期）当前状态（假设存入寄存器r3），将3个状态位移动（1个周期）4位(r3=r3<<4)，以及对提取的4个输入数据位至状态位求“或”（1个周期；即r4=r2|r3）。只要正确设计查找表，我们就能避免状态位的提取和移位操作。如果我们对各查找表项使用两个字节，并将状态位置于移位位置，如图3所示，我们就能省掉两个偏移计算周期（节约50%）。

完成编码位的计算之后，我们必须将编码位封包。我们一次编码4位，并且一次输出一个编码的4位半字节，因此将半字节封包成字节是很容易的事。我们用两个周期将两个半字节封包成一个字节，一个周期用于左移，另一个周期用于“或”或“和”运算。对于双编码器输出封包，Blackfin需要四个周期。利用乘法累加器(MAC)，我们可以在两个周期内完成两个编码器的封包工作，因为Blackfin有两个MAC单元。对于单迭代循环，用于Turbo编码器编码和封包的Blackfin ASM代码如表2所示。该ASM代码包括两个RSC编码器的编码和封包。ASM代码清楚地显示，一个字节的Turbo编码需要20个周期，或者说每个位需要2.5个周期。

在表2中，借助此ASM代码，我们可一次实现两个编码器的4位数据编码。但实际上，第二个编码器并不直接从输入比特流字节中获得数据。传送

给第二编码器之前，我们必须对输入比特流进行交织处理。我们已经讨论了第二个编码器的交织，交织位存储在交织缓冲器中。我们假设，通过将交织位存储在可寻址的边界内（换言之，存储一位必须使用最小的字节），所存储的交织位可以直接从缓冲器存取进行编码。由于我们是利用查找表方法以半字节形式进行编码，因此必须先将交织位封包成字节，再将其存储在交织缓冲器中。

交织器设计。由于上述基于查找表的编码方法需要字节形式的交织位，因此必须将交织位封包成字节。这样，为了以正确的顺序将这些位送入第二个编码器，必须执行以下三个步骤：拆包、交织、封包。我们以字节表示数据，封包是将位多路复用为字节，拆包是将字节解多路复用为位。将位封包成字节需要所有交织位，我们首先必须完成交织处理。对于这两种操作（拆包和交织），每位大约需要3个周期，如表3所示。表3中的ASM代码对一个字节的输入数据执行拆包和交织处理。带进位的循环移位指令rot r by -1可提供从结尾最高有效位(MSB)开始的拆包数据位。

下一步是将交织数据位封包成字节。封包操作与表3所示的拆包操作完全相反。但是，如果我们使用进位循环指令rot r by 1进行封包，则每位需要2个周期，其中一个周期用于将寄存器中的数据位移入cc。因此，我们不使用循环，而使用比较和选择指令vit_max进行封包。vit_max指令将两个寄存器中存在的两个最低有效位(LSB)字与同一寄存器的两个MSB字相比较，从而一次封包两位。vit_max指令的比较结果输出标志保存于累加器中，经过四次迭代后，我们从累加器中提取封包的字节。由于我们无法在一个周期内从同一缓冲器加载两位数据提供给vit_max指令，因此必须再花一个周期来加载数据位。这样，封包两位需要两个周期，或者一位一个周期，如表4所示。

计算复杂度评估

无论是依据每位周期数来评估，还是依据执行任务所需的存储空间来评估，这种Turbo码算法实现方法的计算负荷都是相对适中的。

周期估算。如表3和表4所示，对交织数据执行拆包、交织和封包处理，每位需要4个周期。在表2所示的数据编码中，每位需要2.5个周期。这样，Turbo编码器总的周期成本为每位6.5个周期。请注意，这一估算没有考虑周期开销。假设每位的开销为1个周期，则执行Turbo编码，每位需要大约7.5个周期。借助这一高效的实现方法，我们在14.4 Mbps比特率时只需使用Blackfin处理器的108 MIPS，或者约18%的处理器MIPS。相比之下，简单编码方法则需要使用60%的处理器MIPS。由于Turbo编码器只消耗18%的MIPS，还剩下约82%的处理器MIPS，因此我们有充足的裕量来应对毫微微蜂窝基站的其它模块。

存储空间估算。利用查找表方法实现Turbo编码时，我们需要256字节的数据存储空间来存储预计算的编码信息。采用高效方法时，我们将各位封包成字节，因而存储交织数据所需的数据存储空间更小（仅1/8）。即时计算交织地址的方法非常昂贵，所以两种方法均需要数据存储器来存储交织地址。

利用预先计算的查找表，我们可以仅使用18%的处理器MIPS来执行Turbo编码；否则，使用简单方法则要消耗约60%的MIPS。这种高效方法使用256字节的存储器来存储查找表，所用的总存储空间少于简单方法所需的存储空间。

Hazarathaiah Malepati于2003年加入ADI公司，目前从事Blackfin系列处理器的嵌入式算法软件开发工作。2000年至2003年，他担任印度班加罗尔HIRP（HFCL-IISc研究计划）的研发工程师。他拥有印度KREC Surathkal工业电子硕士学位。

Yosi Stein担任DSP首席系统架构师兼高级技术经理，在数字媒体技术中心工作，负责为ADI公司定点DSP系列开发宽带通信和图像压缩增强指令集。他拥有以色列理工学院电气工程学士学位。

尾注：

1. Berrou C, A Glavieux, and P. Thitimajshima,, \"Near Shannon Limit Error-Correcting Coding: Turbo Codes,\" Proc IEEE Int. Conf. Commun., Geneva, Switzerland, pp.10-1070, 1993. 2. 3GPP: 3rd Generation Partnership Project, \"Technical

Specification Group Radio Access Network, Multiplexing and Channel Coding,\" V8.0.0, 2007.

基于WCDMA的Turbo Codes交织器的设计与实现

万国春1, 陈 岚2 时间:2008年09月24日

字 体:

关键词:交织器核心噪比2M3GPP

摘 要: 介绍了Turbo码和交织技术以及交织技术在Turbo码中的重要作用，提出了一种交织器电

路的设计思路, 进行了信道的性能仿真,并比较了其性能。根据此设计思路,用Verilog HDL语言设计了交

织器电路,并给出了仿真结果,验证了设计的正确性。

关键词： WCDMA Turbo码 交织器 硬件描述语言

法国人C.Berrou等在1993年首先提出了Turbo码, 它是在综合过去几十年来的级联码、乘积码、最大后验概率译码与迭代译码等理论的基础上的一种创新。它在低信噪比下表现出了接近Shannon限的性能,超过了其他编码方法。因此,自Turbo码推出后便引起了各国研究者的极大兴趣。经过研究发现,Turbo

码不同于以往的其它编码,表现出了极佳的性能,其中一个重要原因就是采用了随机交织器。

Turbo码的基本原理是,通过编码器的巧妙构造,即多个子码通过交织器进行并行或串行级联(PCC/SCC),然后进行迭代译码,从而获得卓越的纠错性能。在Turbo码的编解码中,无论是编码还是解码,交织单元都是其中很重要的一环。图1所示为Turbo编译码的原理框图。在子译码器1与子译码器2之间的前向通路和反馈通道分别存在交织和解交织单元, 交织器在Turbo码的构造中是一个极其重要的因素。Turbo码中交织器的主要作用是减少校验比特间的相关性，进而在迭代译码过程中降低误比特率。C.Berrou等人在Turbo码提出伊始就给出了设计性能较好的交织器的特点和基本原则：(1)通过增加交织器的长度，可以使译码性能得到提高；(2)交织器应该使输入序列尽可能随机化，从而避免编码生成低重码字，导致Turbo码自由

距离减少。本文将就Turbo码中交织器参数的选择、性能和实现进行探讨。

[2]

[1]

WCDMA移动通信系统技术标准是由国际性第三代合作组织(3GPPwww.3gpp.org)支持并维护的。3GPP主要是由欧洲和日本的标准组织和公司组成。WCDMA技术规范充分考虑了与第二代GSM移动通信系统的互操作性和对GSM核心网的兼容性。它将GSM MAP作为上层核心网协议,与GSM核心网完全兼容。关于 WCDMA信道编码和映射的规范是 3G TS 25.212“Multinlexins and channel codns”(FDD)。图2为WCDMA系统

的系统框图。

1 数据交织算法

交织器是实现Turbo编码的一个重要环节。它的主要作用就是将原始数据序列打乱，使交织前后数据序列的相关性减弱。这样做的一个突出优点是大大降低了数据突发错误的影响，以进一步提高抗干扰性能。解交织器将交织器打乱的字节序列重新排列恢复原始码字。按交织方式可分为分组交织器和随机交织器两种。其实现基本类型又可分为行列式分组交织、螺旋式分组交织、线性转换式随机交织和读表式随机交织等。行列式分组交织是将信息码元序列视为 N×M矩阵，然后采取以行读和列写的方式实现码元交织，交织后码元的距离特性呈均匀分布；螺旋式分组交织则将码元序列视为 N×(N+1)矩阵，然后以对角方向读和行写的方式交织，交织后相临码元距离≥N。分组交织方式简单、对短序列交织效果较好，但交织后对码元的去相关不彻底。线性转换式随机交织就是设法找到一个可逆的比特位地址映射关系T，将长度为2M数据序列的每一比特从一个缓冲区送入另一缓冲区。即m′=mT。其中m=[aM-1,aM-2,...,a1,a0]为交织前比特位地址，T为M×M可逆矩阵，T=[t,Rt,...,Rt, Rt]，R为循环右移算子。这种交织器的优点是不需要专门的存储空间存放2个映射地址。但是，如此交织得到的码元序列仍然具有较强的相关性。图3、图4

分别是行列式分组交织和读表式随机交织算法示意图。

M

[3]

M-2

M-1

2 Turbo码交织器的优化设计方案

2.1 设计思想

为减少可编程逻辑器件FPGA的内部存储器需要，交织、反交织器设计采用地址翻译方式，也就是对交织、反交织器的读或写的地址进行变换。对于交织器，按行顺序写入交织矩阵，交织，带删除的按列输出。

对于反交织器，依据删除阵列按列顺序写入交织矩阵，反交织，带删除的按行输出。

2.2 整体结构的设计

在交织深度相同时，交织器与反交织器重排控制参数相同，且在一个码块译码的多次循环迭代中均保持不变。所以同一模块在外部信号的控制下实现交织和反交织功能是一种比较节省资源的方法。图5示出

了这样的交织／反交织器结构设计。

交织参数计算和交织控制模块在输入交织深度block size后，计算对应交织图案。包括交织矩阵行数R、列数C、行间重排模式T(j)，在存储p、v数值的ROM表中查取并计算对应p、v数值，从而确定行内重排基准s(i)、行内重排因子q(j)。交织参数更新发生在交织长度改变、码块同步信号到来的时刻。交织和反交织功能模块从参数寄存器中获取相同的当前比特重排参数，根据所得到的参数计算输入比特顺序号对应的输出比特顺序号。交织或反交织功能模块受控于交织控制工作与否。输出控制以对应输出比特顺序号

将交织比特输出并写入外部DP－RAM中。

2.3 交织器的性能仿真

为了比较几种交织方式性能的优劣,选取生成多项式为g=(15,17)OCTAL的RSC,选取交织器的大小均为1024的情况,仿真出分组交织、对角线交织、螺旋交织、PN交织、S-随机交织等五种不同交织方式对译码性能的影响。仿真结果如图6所示,从几条曲线的比较可以看出,S-随机交织器的性能较之其他方式性能最好,在10-6附近,它与分组交织之间有大约0.5dB的增益。基于以上讨论,笔者选择S-随机交织方式,在译码迭代次数为10的译码条件下,选择迭代结构,对不同交织规模N的误码性能进行了仿真,结果如图7所示,分别给出了交织规模N为160、320、0、5120时,误码率随信噪比变化而变化的曲线。显然,在信噪比较低,SISO模块迭代次数均为10的情况下,交织单元的规模越大,其交织的一致性越好,如图7所示。当

N=5120时,误码率在信噪比略有增大时就有剧烈的衰减,表现出了良好的提高译码性能的能力。

[4]

3 基于WCDMA的144kbps交织、反交织器的具体实现

依据上述设计方案和性能仿真结果,采用硬件描述语言可以很方便地实现上述算法的交织。本设计基于ALTREA公司的Quartus环境,采用Verilog HDL语言编程,经过FPGA验证。在不同性能要求下,可以选择参

数来满足不同的要求。

由于数据速率已经确定，根据3GPP协议：对子一个20ms的数据帧，经过CRC－16校验后，帧长为26。

实现框图如图8。

图8中，qj表、pattern表、s(i)表用片内ROM就可以直接实现。计算(i*qj)mod(p-1)的模块用乘法器和除法器搭建。它最大的好处是，在数据速率改变时，只需要相应改变qj表、pattern表、s(i)表。 为了克服时延大的缺点，可以将先行算出的交织图案写到外部的EPROM中，但在寻址交织矩阵时，还需对地址进行处理。这种方法的优点就是速度较快，对FPGA芯片内部的资源占用减少。交织算法关键环节

的 HDL描述如下：

//地址计数器(用于串行输入、输出数据)：

module addr( ); endmodule

//索引表地址发生器(用于产生随机交织地址):

2

module addr_index( );

endmodule //交织器状态机： module interleaver_state( );

always @(state)

begin case (state)

…… endcase end

always @(posedge clk)

begin …… end endmodule

图9就是一个交织深度为43的交织器的部分工作时序图，这个交织器的设计方案即采用片内ROM存储

交织矩阵和删除矩阵。

参考文献

1 Berrou C,Galavieux A,Thitimajshima P.Near Shannon limit error-correcting coding and decoding: Turbo-codes:Turbo-codes.IEEE International Conference on Communication，1993；10～1070 2 K.Andrews, C.Heegard， D.Kozen.A theory of interleavers.Tech.Rep.97-1634.June 1997 3 O.Y.Takeshita，D.J.Costello Jr.New deterministric interleaver design for turbo codes.IEEE Trans.

Inform.Theory.2000;46(9):1998~2006

4 Jinhong Yuan,Branka Vucetic and Wen Feng.Combined Turbo Codes and Interleaver Design[J].IEEE

Trans.on Communications.1999;47(4)：484~487

5 张中培, 靳蕃. 从相关分析Turbo码交织器的设计[J]. 成都：电子科技大学学报,2000;29(1)：25～28