无线通信系统-FFT与信道译码VLSI设计 课件第5章 Turbo码并行译码器VLSI结构设计

第5章Turbo码并行译码器VLSI结构设计5.1Turbo码的并行译码方法5.2Turbo码子块并行译码器VLSI结构设计5.3Turbo码并行译码QPP交织器VLSI结构设计5.4并行QPP交织器的硬件设计5.5理论分析与硬件测试本章小结

5.1Turbo码的并行译码方法

LTE系统turbo码编译码器的原理框图如图5.1所示，在发送端，turbo码编码器由两个卷积码编码单元和一个交织器组成。包含K个信息比特的数据块xk,k=0,1,L,K-1，输入turbo码编码器后一方面作为输出系统比特（SystematicBits），另一方面通过编码单元来产生相应的校验比特（ParityBits）。

图5.1Turbo码编译码器原理框图

卷积码编码单元1接收正常次序的信息比特序列{xk}并输出相应的校验比特序列

，类似地编码单元2接收交织次序的信息比特序列

并输出

，其中

表示交织函数。编码后的turbo码具有固定的

码率，可以通过打孔等操作来实现码率变换。经过符号映射、调制并通过无线信道传输后，接收端利用软检测器来得到

的对数似然比（Log-LikelihoodRatio，LLR），它们分别记作

与

。以

为例，其具体形式为

它代表了相应的比特取1或

的概率大小，故LLR也被称为比特软信息。

5.1.1基于符号的MAP译码算法

为了便于讨论，我们将SISO译码单元输入的系统位与校验位软信息分别记作Lsk与Lpk，类似于卷积码的Viterbi译码算法，SISO译码单元运行的Log-MAP算法和max-log-MAP算法可以利用卷积码网格进行递归运算。令ak(s)和βk(s)

分别表示网格第k级状态

的前向状态度量与反向状态度量；定义

为连接网格第k-1级状态sʹ与第k级状态s的分支所对应的分支度量，其计算方式如下：

(5.1)

利用(5.1)-(5.6)，SISO译码单元实现了对系统位软信息

Lsk、校验位软信息Lpk以及先验信息LAk的处理来得到判决软信息LDk和外信息LEk。具体到turbo码译码器中，如图5.1所示，分量译码单元1利用Lsk，

以及先验信息

来计算判决软信息

和外信息

。类似地分量译码单元2利用

以及先验信息

来计算判决软信息

和外信息

。迭代译码操作表现为SISO译码单元之间的外信息交互，即

(5.7)

这里

表示解交织函数。

5.1.2子块并行译码与块交织流水线策略

子块并行译码方法将长度为

的turbo码码块划分为P个长度为S=K/P的子块并对每个子块进行独立处理，图5.2(a)以P=2为例对子块并行译码器结构进行说明。在执行子块并行译码算法时，需要对每个子块左侧边界的前向状态度量和右侧边界的反向状态度量进行有效估计。

图5.2子块并行译码结构与基于块交织流水线方式的SISO译码策略

图5.2子块并行译码结构与基于块交织流水线方式的SISO译码策略

5.1.3滑动窗译码与前后向交叉译码方式

在SISO译码过程中，状态度量和分支度量需要在计算判决软信息之前进行缓存。尽管子块并行译码方法以及块交织流水线策略的使用能够实现译码器吞吐量与计算资源使用效率的提升，每个子块内仍然需要存储全部状态度量与分支度量，从这一点来看译码器的数据存储开销并未减小。滑动窗译码和前后向交叉译码方法旨在对SISO译码算法的前向状态递推、反向状态递推以及软信息计算操作进行合理调度来避免译码过程中大量的数据缓存。

滑动窗译码方法将长度为S的子块进一步划分为L个长度为W=S/L的窗口，并按照图5.3所示的方式将不同SISO译码操作分布在不同的窗口上执行，这样每个子块内只需要对用于初始化反向状态度量的窗口存储分支度量以及对执行反向状态递推的窗口存储分支度量与状态度量。

图5.3基于滑动窗译码与前后向交叉译码方式的子块并行译码方法

前后向交叉译码在一定程度上克服了滑动窗译码所面临的计算与控制复杂度高的问题，它对SISO译码操作的调度方法在图5.3上半部分给出。不难发现前后向交叉译码不涉及到子块数据的分窗口操作，也不需要在子块并行译码执行前预估各子块边界处的度量值。不过以前后向交叉译码方式工作的SISO译码单元在存储开销的降低幅度上不及滑动窗译码方法，因为每个子块在处理中至少需要存储1/2个子块长度的状态度量和分支度量；另一方面，前后向交叉译码使得SISO译码单元不能以恒定速率向外输出判决软信息与外信息，这给外信息的存储和交织器设计带来一定挑战。

5.2Turbo码子块并行译码器VLSI结构设计

综合上一节讨论的并行译码方法，我们可以得到如图5.4(a)所示的turbo码子块并行译码器顶层框图，其中接收码块被划分为P个子块，译码器中配置了N=P/λ个SISO译码单元，这里假设第n个SISO译码单元采用块交织流水线策略来处理第P(n-1)/N+1至第pn/N个子块。每轮迭代译码通过两个半轮来完成，N个SISO译码单元在这两个半轮中分别作为分量译码器1和分量译码器2来处理译码输入。

在译码器中实现(5.7)所描述的外信息交互有两种方法：

非平衡式调度：如图5.4(b)所示，在前半轮迭代并行SISO译码单元以自然序读取先验信息和存储外信息；在后半轮迭代并行SISO译码单元以交织次序读取先验信息，并以解交织次序存储外信息；

平衡式调度：如图5.4(c)所示，在前半轮迭代并行SISO译码单元以自然序读取先验信息，并以解交织次序存储外信息；在后半轮迭代并行SISO译码单元以自然序读取先验信息，并以交织次序存储外信息。

图5.4Turbo码子块并行译码器顶层结构与迭代调度方案

图5.4Turbo码子块并行译码器顶层结构与迭代调度方案

基于块交织流水线策略的SISO译码单元VLSI实现结构如图5.5所示。图5.5基于块交织流水线策略的SISO译码单元设计方案

需要指出的是，

在turbo码译码器中块交织流水线因子为

的SISO译码单元并非仅能处理λ个子块，通过调整输入数据读取方式，可支持任意M个子块的分时处理，其中对各个子块数据的读取以max{M,λ}个时钟周期为单位循环执行：

如果M<λ，此时读取操作的循环周期为λ个时钟周期，并将其中第

时钟周期作为第i个子块的操作时隙。具体的数据读取方式为：在第1个时隙更新读地址并读取第1个子块的数据，在第2至第M个时隙内用同样的地址依次读取第2至第M个子块的数据，将第M+1个时隙至第4个时隙作为空闲时隙；

如果

，此时读取操作的循环周期为M个时钟周期，并将其中第

时钟周期分配给第i个子块作为操作时隙；此时的数据读取方式为：在第1个时隙更新读地址并对读取第1个子块的数据，在随后的M-1个时隙内用同样的地址依次读取第2至第M个子块的数据。

利用硬件电路实现状态度量递推时，考虑到状态度量值均采用了定点表示形式，为了避免数据的溢出，需要对每次递推得到的状态度量进行归一化处理。根据Max-log-MAP算法的原理，进行归一化之前首先应求出当前状态度量中的最大值，再从其他状态度量中减去这一最大值，即可实现状态度量的归一化。当采用radix-2v译码算法时，在(5.4)的基础上归一化过程可以表示为：

其中

和

分别表示归一化后的前向和反向状态度量。为了缩短状态度量的更新周期，可以将上述归一化方式改进为：利用前一组状态度量的最大值对当前的状态度量进行归一化，即：

基于以上延迟归一化方案，归一化因子的确定与新状态度量的计算可以并行执行，从而加速状态度量的更新周期。

表5.1以raidx-4译码算法中，第2k时刻的状态度量计算过程为例描述了各时钟周期下ACS单元在计算某一前向状态度量

的详细操作，其中的CLK#1、CLK#2、CLK#3和CLK#4用于指代译码过程中连续的4个时钟周期，状态度量总数假定为8个，且每一级的状态与前一级的4个状态相连接。

5.3Turbo码并行译码QPP交织器VLSI结构设计

5.3.1外信息存储模式与QPP交织器的数学表示

我们定义

的矩阵M来表示外信息LEk的存储模式，在物理上它对应于由多个存储器组成的存储阵列。参数ρ表示SISO译码单元在同一时刻输出的外信息或者读取的先验信息个数，则在滑动窗译码和前后向交叉译码方式下分别有ρ=v和ρ=2v

。将M中的相邻ρ行聚合为一个子矩阵，这样它可以重新表示为分块矩阵的形式，即

(5.8)

定理5.1：对于(5.10)所定义的QPP交织器，假设参数S满足S|K，那么对于

，

其中

表示下取整运算。

5.3.2支持无冲突访问的外信息存储模式

为了设计合理的外信息存储模式M以支持数据的无冲突存取，需要首先准确描述外信息送入存储阵列以及先验信息离开存储阵列的数据次序而这一点与SISO译码单元的工作方式密切相关。具体来讲，第n+1个执行radix-2v算法的译码单元在时刻t会处理网格中连续ρ级的译码数据，这些网格级数可以表示为

，其中对于以滑动窗译码方式工作的SISO译码单元，

具有如下的形式：

(5.11)

当SISO译码单元以前后向交叉译码方式工作时，wi(t)则应当写作：

类似于先验信息的逻辑读地址ai,n(t)，这里定义外信息的逻辑写地址为

ei,n(t)同样描述了外信息写入存储阵列的次序。

要避免发生数据访问冲突，应当保证写入存储阵列或者从存储阵列中读出的数据都对应于不同的存储器。也就是说，需要设计存储模式M以保证对于i=0,L,ρ-1以及n=0,L,N-1，Nρ

个逻辑读地址

与逻辑写地址

都能映射到M的不同的行上。下面我们首先在算法5.1中给出存储模式M的具体形式，然后在证明M能够支持无冲突的数据访问。

图5.6以K=16,f1=3,f2=8的QPP交织器为例给出了不同情形下存储模式M的形式。对于两个逻辑写地址

，由算法5.1可知它们对应的存储器组序号分别为n1和n2，而在各自存储器组内所对应的存储器标号分别为

与

。

图5.6不同turbo码译码器中存储模式

实例

图5.6不同turbo码译码器中存储模式

实例（QPP交织器参数K=16,f1=3,f2=8

）

引理5.1：设c1,c2是正整数，a,b为任意整数，那么.

与此同时，文献[33]对QPP函数参数

和

的数学性质进行了深入研究，并得出如下结论：

基于上述讨论和理论准备，我们给出如下定理：

定理5.2：对于采用QPP交织器的turbo码，如果码块长度

是4的倍数，即

，那么算法4.1定义的存储模式M能够支持先验信息无冲突访问的充要条件是

满足

(5.15)

5.4并行QPP交织器的硬件设计

5.4.1数据写入电路结构

其中

。可以看到(5.16)建立了SISO译码单元输出的外信息和存储器组内的v个存储器之间的对应关系。值得注意的是，由于

与参数t无关，故该对应关系是时不变的。另一方面，物理地址

可以写作

在前后向交叉译码模式下，数据存储的物理地址ζi表示为

可以发现SISO译码单元输出的2v个外信息在存储时，前一半数据和后一半数据将分别用到的不同的物理地址。以前后向交叉译码方式工作的子块并行译码器中数据写入电路的设计框图如图5.7b所示，和滑动窗译码情形下的设计相比，地址产生单元需要在同一时刻产生两个物理地址来分别完成每个SISO译码单元输出的前v个和后v个外信息的存储，并且在存储器组内部署了一个蝶形换向器来改变数据流与存储器的对应关系。蝶形换向器的控制逻辑

可以选取

与

的最后一个数据位经过同或运算得到。当c=0时，蝶形换向器不改变2v个外信息的次序；反之将前v个与后v个外信息进行对换。

图5.7Turbo码子块并行译码器的外信息写入电路设计框图

图5.7Turbo码子块并行译码器的外信息写入电路设计框图

5.4.2数据读取电路的读地址产生器

定理5.3：QPP交织地址

的v步递归计算方法如下：

其中

，参数v为正表示地址的前向递归生成，为负表示地址的反向递归生成。

当4|K时我们有f2mod2=0，此时QPP交织地址还满足

上式表明一旦确定出连续的K|4个交织地址，其余3K|4个地址可以通过非递归的方式来确定。

为了充分利用定理5.4的数学性质，我们将Nρ个逻辑读地址划分为ρ个地址组，并用

来表示第i=1个地址组。可以看到，

的N个地址具有相同的下标i且下标n遍历了

，因此它们满足定理5.4中描述的数学特性。为了从存储阵列中准确地读取数据，需要利用

ai,n(t)的余项εi,n来进一步确定存储器标号

和物理读地址

。对于地址组

内包含的N个逻辑地址，

(1)可以利用前N/2个逻辑地址来确定出全部的N个存储器组序号

，这是因为(5.24)和(5.25)表明同一地址组内的N个逻辑地址所对应的存储器组序号具有较强的相关性；

(2)存储器标号

和物理读地址

可以通过任一逻辑地址来得到，这是因为

且

，而(5.23)表明

内的N个逻辑地址具有相同的余项εi,n。基于这一点，在下面的讨论中我们略去εi,n的下标n来使数学表达式得到简化。

上述分析表明，通过每个地址组内的前N/2个地址将足以确定出该地址组内所有逻辑地址的存储器组序号、存储器标号以及物理读地址。读地址生成单元的顶层设计方案如图5.8(a)所示，进一步在图5.8(b)中，我们以配置两个SISO译码单元的radix-2前后向交叉译码turbo码译码器为例对读地址生成单元中各模块的功能进行说明，其中QPP交织器参数设置为K=16,f1=3,f2=8。一般地，读地址单元内需要配置ρ个逻辑地址产生单元，其中第i个单元负责产生地址组

内的前N/2个交织地址。当

时，逻辑地址产生单元具有图5.9所示的底层硬件结构，其中前N/4个地址按照定理5.3描述的递归方式产生，而另外N/2个地址则利用(5.22)描述的非递归方式获得。

图5.8读地址生成单元顶层结构框图及其工作方式说明

图5.9逻辑读地址产生单元的硬件结构

对于送入同一地址转换器的N/2个交织地址，QPP交织器所具有的最大无冲突特性使得它们具有不同的存储器组序号。不过在硬件实现中并不需要部署N/2条完整的q级流水线比较结构来独立处理各交织地址。从(5.24)和(5.25)可以看出在二元域内存储器组序号之间具有较强的相关性，从这一特性出发，我们只对前N/4条流水线装配第2级比较结构，对前N/8条流水线装配第3级比较结构并以此类推来构建出N/2条流水线。在上述分析的基础上，图5.10以N=8的情况为例给出了地址转换器的硬件设计方案。

图5.10地址转换器的硬件结构（N=8

）

图5.11物理地址提取与路由单元的硬件结构（ρ=8

）

5.4.3数据读取电路中数据路由单元

上面介绍的读地址产生单元将逻辑读地址逐步转化为存储器组序号、存储器标号以及物理地址来实现从存储阵列中获得所需的先验信息数据。在数据读取电路中，数据路由网络的作用是将所读取的先验信息正确分发至各SISO译码单元，为此需要将每个先验信息数据与其所对应的逻辑读地址关联起来。图5.12(a)给出了数据路由网络的顶层设计方案，进一步在图5.12(b)中，我们以配置两个SISO译码单元的radix-2前后向交叉译码器为例对数据路由网络中各模块的功能进行说明，其中QPP交织器参数为K=16,f1=3,f2=8。

图5.12数据路由网络顶层结构框图及其工作方式说明

图5.12数据路由网络顶层结构框图及其工作方式说明

在图5.13中，我们以ρ=4为例对数据组排序单元的结构进行描述。图5.13数据组排序单元的硬件结构（ρ=4

）

图5.14利用反转蝶形互联网络来实现数据组内先验信息的排序（N=4

）

5.5理论分析与硬件测试

5.5.1不同QPP交织器设计方案的复杂度分析

由图5.4(a)可以看出，交织器的数据读取电路可以划分为读地址产生单元和数据路由网络两部分且两者在一定程度上彼此关联：读地址产生单元在地址变换过程中要同时产生数据路由网络的控制信号，而数据路由网络的具体拓扑结构则同样影响着读地址产生单元的计算复杂度。

因此对于给定的存储模式M，数据路由网络拓扑结构的选择将同时影响其自身以及读地址产生单元的复杂度，进而决定整个数据读取电路的硬件资源开销。在硬件实现中，读地址产生单元需要利用到数据选择器和加法器，而数据路由网路则主要由数据选择器构成。表5.2对基于不同网络结构所设计的QPP交织器中数据读取电路占用的数据选择器和加法器数目进行估计，以此来衡量各方案的硬件复杂度。这里N表示子块并行译码器中SISO译码单元的数目，ρ代表每个SISO译码单元在同一时刻读取的先验信息个数，对于radix-2v滑动窗译码方式有ρ=v

，而对于前后向交叉译码方式有ρ=2v

。

进一步在图5.15和图5.16中，我们取定参数ρ来衡量在不同子块并行度下各类QPP交织器设计方案对数据选择器和加法器的消耗。

图5.15不同并行度下各QPP交织器设计方案对数据选择器的消耗对比

图5.16不同并行度下各QPP交织器设计方案对加法器的消耗对比

5.5.2QPP交织器的硬件实现与测试

对于交织器的数据读取电路而言，其消耗的数据选择器和加法器在FPGA内主要由sliceLUTs构成，因此我们首先关注QPP交织器的不同实现方案在这一指标上的表现。从表5.3和表5.4的统计数据来看，本章的设计方案所需的sliceLUTs资源与SISO译码单元数目N近似呈线性关系，这一趋势与表5.2的理论估计一致。另一方面在N=8的情况下通过比较滑动窗译码和前后向交叉译码方式下三种设计方案对slice单元总的消耗可以发现，本章提出的基于蝶形互联网络的交织器在ρ=4时所占用的硬件资源大约是ρ=2情形下的2倍，而基于交叉开关网络和主从Batcher网络的两种对比方案在ρ=2至ρ=4的变化过程中硬件资源消耗分别增加为原来的4倍和3倍左右。

进一步，将三种交织器的数据读取电路内各模块slice消耗情况以直方图的形式展现在图5.17中。由于本章的设计方案在同一时刻只产生和变换Nρ/2个交织地址，因而地址产生单元的硬