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

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

但是，为了实现至少与传统宏蜂窝系统相同的信号强度，毫微微蜂窝必须采用支持高达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或128项，如图2所示。各项包含4个编码位和3位更新状态信息。换言之，一个字节（或8位）足以代表查找表的各项。
深入研究8位查找表设计可以发现，为了从4个输入位（假设位于寄存器r0）和3个当前状态位（假设位于寄存器r1）计算128项查找表的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.1064-1070， 1993.
2. 3GPP: 3rd Generation Partnership Project， "Technical Specification Group Radio Access Network， Multiplexing and Channel Coding，" V8.0.0， 2007.