在FPGA上实现咬尾卷积码的最优算法设计
引言
自1955年elias发明卷积码以来，卷积码作为一种高效的信道编码已被用在许多现代通信系统中。卷积码分为零比特卷积码(zero tail cc，简称ztcc)和咬尾卷积码(tail biting cc，简称tbcc)两种。ztcc是指在编码的时候，码字后面要另外加上k(k为约束长度)个0将编码寄存器的最后状态打出，而tbcc则是直接用码字的最后k个比特将编码寄存器初始化，从而提高编码率。现在的3g和4g通信标准中(比如wimax或lte)都采用了tbcc信道编码。关于tbcc的译码算法很多，其中比较经典的译码算法有循环维特比算法(cva)和bcjr算法。但上述算法由于解码时延不固定和复杂度的原因，均不便于硬件实现。为此，本文提出了一种便于硬件实现的次优解码算法。
1 tbcc译码算法
1．1 最优译码算法
tbcc的理论最优译码算法是，对于每一个可能的初始状态(3k)用维特比译码算法对所有可能的状态进行搜索，最后再根据最好的状态进行解码。但是，这种算法的复杂度太高，不利于硬件实现。
1．2 次最优译码算法
次最优译码算法的经典代表是cva算法，此外还有其改进的算法比如环绕维特比算法(wava)和双向维特比算法(bva)。它们的主要思路是利用圆形buffer将码字扩展成多个相同码块首尾相接的长码块进行译码。当检测到首尾状态相等或者满足自适应迭代的停止条件时，即完成译码；否则继续进行迭代。但该算法或其改进的wava和bva算法都存在这样一个问题。那就是解码的延迟不是固定的，而这非常不便于硬件实现。
所以，本文中提出固定延迟的译码算法，其基本思路是在码块的前lt个符号补在符号的后面，将码块的后lh个符号补在码字的前面，这样就构成一个长度为lt+n+lh的新码块(假设原码字长度为n)，图1所示是重构的码块示意图。该新码块可以按照ztcc解码一样去解码，然后从具有最小路径度量(path metric)的状态进行回溯。
图2所示是其译码算法流程图。其中lt和lh参数的选择应根据仿真来确定。这里采用典型值：lt=72，lh=96。
2 tbcc译码算法的实现
2．1 分支度量(branch metric)的计算
维特比译码算法采用ml准则，其分支度量可通过下式计算：
2．2 加-比较-选择器(acs)
图3所示是acs的状态转移蝶形图。实际上，卷积码的trellis图具有如下性质(lte中tbcc编码约束长度为7)：
对于每一个状态，其前面的状态为i<<1和(i1)％64和(i>>1+1)％64。
上述性质在硬件实现时非常好用。由上述性质可以给出路径度量的计算式：
从上面的公式可以看出。计算一个蝶形图需要4次加法和2次比较。图4所示是acs路径度量蝶形图。此外，操作时还可采用andries的简化方法来减小硬件开销，其公式如下：
计算出需要2次加法。对于lte中约束长度为7的tbcc来说，总共有64个状态，可以分别在两个蝶形图里面使用(符号会有所变化)，这样，加法器就减小为32，加上每个路径度量更新还需要一个加法器，这样共需要的加法器为32+64=96，比之前未简化的算法少用了32个加法器。
2．3 回溯
回溯的深度(trace back depth)必须大于编码深度(coding depth)，这是因为，经过回溯cd的长度，所有的幸存路径均会收敛。每次回溯时，所有幸存路径都需要从内存里面读出td个状态，同时将有td-cd个判断之后的比特送入lifo。回溯之后，会有td-cd的内存空间可写，另外在回溯时，还需要td-cd个内存空间来保存进来的数据，这样，内存空间就共需td+(td-cd)=2td-cd。在此可取典型值td=96，cd=72。
2．4 fpga的实现
本设计采用的fpga芯片为altera的stratixiiiep3sl340系列器件，其在quartusii9．0下综合出来的rtl视图如图5所示。其布线后所占用的资源如表l所列。
3 仿真验证
本文采用的开发流程是先在matlab下仿真出浮点算法的性能，然后根据系统要求用c实现定点模型，在和浮点的版本比较后，再采用ver-ilog实现。由于用verilog做性能仿真比较慢，本文采用的仿真和验证方法是在定点c下做性能仿真，然后将c版本的输入输出作为黄金参考数据，再用modelsim仿出vetilog版本的数据和参考数据做对比，如果数据完全一样，则验证通过，否则调试verilog语言并追踪错误。
验证选择的码长为1080，将tbcc解码器放在4×4 mimo接收机里，可得到如图6所示的snr曲线。
由图6可知，在snr很小的时候，tbcc解码器的性能反而较硬判决会下降，这是由于snr太小，tbcc已经无法从很少的已知信息中纠正其他的错误信息。而当snr较大时，tbcc解码器就可以从相对多的已知信息中纠正错误信息。由图6可见，在误码率为10-3以下时，tbcc能够获得约2l db的增益。
4 结束语
该解码器已经用在mimo接收机的fpga版本中。并且经过实验室测试，能够成功的解码出咬尾卷积编码，并具有较好的性能。另外，该解码器在实现上用的硬件资源很少，这可为整个系统的集成奠定基础。
超声波多普勒流速流量仪
TCL实力展现硬核音画质,全球首款最薄MiniLED电视
基于VL813芯片的USB3.0 HUB方案
商汤集团2021年实现营收47亿元
MODBUS RTU传输模式介绍
在FPGA上实现咬尾卷积码的最优算法设计
小米6X和红米6 Pro对比分析，看看两者之间到底有什么区别
国产“章鱼”第二版设计者说
通过触摸实现真实感的Piezo(压电)触觉反馈设备
TGV处理薄玻璃的处理方案
基于区块链技术去中心化的场外交易平台商币平台介绍
不止渲染已久的魅族Pro7首款双面屏手机，还有p25一款神秘新机！
Nordic使能跟踪网关设备新产品的介绍和应用说明
漫谈BTO 笔记本电脑DIY常识课
5G环境下国内光模块将有更大的机会向高端光模块市场发力
关于移动设备快充的方法的分析和应用
首创•中传 首届文创校友沙龙暨中国传媒大学校友创业联合会筹备会 互联网资讯
PLC程序解锁解码的详细介绍
晶振的基本性能及应用注意事项
京瓷推出008004尺寸微型MLCC
自1955年elias发明卷积码以来，卷积码作为一种高效的信道编码已被用在许多现代通信系统中。卷积码分为零比特卷积码(zero tail cc，简称ztcc)和咬尾卷积码(tail biting cc，简称tbcc)两种。ztcc是指在编码的时候，码字后面要另外加上k(k为约束长度)个0将编码寄存器的最后状态打出，而tbcc则是直接用码字的最后k个比特将编码寄存器初始化，从而提高编码率。现在的3g和4g通信标准中(比如wimax或lte)都采用了tbcc信道编码。关于tbcc的译码算法很多，其中比较经典的译码算法有循环维特比算法(cva)和bcjr算法。但上述算法由于解码时延不固定和复杂度的原因，均不便于硬件实现。为此，本文提出了一种便于硬件实现的次优解码算法。
1 tbcc译码算法
1．1 最优译码算法
tbcc的理论最优译码算法是，对于每一个可能的初始状态(3k)用维特比译码算法对所有可能的状态进行搜索，最后再根据最好的状态进行解码。但是，这种算法的复杂度太高，不利于硬件实现。
1．2 次最优译码算法
次最优译码算法的经典代表是cva算法，此外还有其改进的算法比如环绕维特比算法(wava)和双向维特比算法(bva)。它们的主要思路是利用圆形buffer将码字扩展成多个相同码块首尾相接的长码块进行译码。当检测到首尾状态相等或者满足自适应迭代的停止条件时，即完成译码；否则继续进行迭代。但该算法或其改进的wava和bva算法都存在这样一个问题。那就是解码的延迟不是固定的，而这非常不便于硬件实现。
所以，本文中提出固定延迟的译码算法，其基本思路是在码块的前lt个符号补在符号的后面，将码块的后lh个符号补在码字的前面，这样就构成一个长度为lt+n+lh的新码块(假设原码字长度为n)，图1所示是重构的码块示意图。该新码块可以按照ztcc解码一样去解码，然后从具有最小路径度量(path metric)的状态进行回溯。
图2所示是其译码算法流程图。其中lt和lh参数的选择应根据仿真来确定。这里采用典型值：lt=72，lh=96。
2 tbcc译码算法的实现
2．1 分支度量(branch metric)的计算
维特比译码算法采用ml准则，其分支度量可通过下式计算：
2．2 加-比较-选择器(acs)
图3所示是acs的状态转移蝶形图。实际上，卷积码的trellis图具有如下性质(lte中tbcc编码约束长度为7)：
对于每一个状态，其前面的状态为i<<1和(i1)％64和(i>>1+1)％64。
上述性质在硬件实现时非常好用。由上述性质可以给出路径度量的计算式：
从上面的公式可以看出。计算一个蝶形图需要4次加法和2次比较。图4所示是acs路径度量蝶形图。此外，操作时还可采用andries的简化方法来减小硬件开销，其公式如下：
计算出需要2次加法。对于lte中约束长度为7的tbcc来说，总共有64个状态，可以分别在两个蝶形图里面使用(符号会有所变化)，这样，加法器就减小为32，加上每个路径度量更新还需要一个加法器，这样共需要的加法器为32+64=96，比之前未简化的算法少用了32个加法器。
2．3 回溯
回溯的深度(trace back depth)必须大于编码深度(coding depth)，这是因为，经过回溯cd的长度，所有的幸存路径均会收敛。每次回溯时，所有幸存路径都需要从内存里面读出td个状态，同时将有td-cd个判断之后的比特送入lifo。回溯之后，会有td-cd的内存空间可写，另外在回溯时，还需要td-cd个内存空间来保存进来的数据，这样，内存空间就共需td+(td-cd)=2td-cd。在此可取典型值td=96，cd=72。
2．4 fpga的实现
本设计采用的fpga芯片为altera的stratixiiiep3sl340系列器件，其在quartusii9．0下综合出来的rtl视图如图5所示。其布线后所占用的资源如表l所列。
3 仿真验证
本文采用的开发流程是先在matlab下仿真出浮点算法的性能，然后根据系统要求用c实现定点模型，在和浮点的版本比较后，再采用ver-ilog实现。由于用verilog做性能仿真比较慢，本文采用的仿真和验证方法是在定点c下做性能仿真，然后将c版本的输入输出作为黄金参考数据，再用modelsim仿出vetilog版本的数据和参考数据做对比，如果数据完全一样，则验证通过，否则调试verilog语言并追踪错误。
验证选择的码长为1080，将tbcc解码器放在4×4 mimo接收机里，可得到如图6所示的snr曲线。
由图6可知，在snr很小的时候，tbcc解码器的性能反而较硬判决会下降，这是由于snr太小，tbcc已经无法从很少的已知信息中纠正其他的错误信息。而当snr较大时，tbcc解码器就可以从相对多的已知信息中纠正错误信息。由图6可见，在误码率为10-3以下时，tbcc能够获得约2l db的增益。
4 结束语
该解码器已经用在mimo接收机的fpga版本中。并且经过实验室测试，能够成功的解码出咬尾卷积编码，并具有较好的性能。另外，该解码器在实现上用的硬件资源很少，这可为整个系统的集成奠定基础。
超声波多普勒流速流量仪
TCL实力展现硬核音画质,全球首款最薄MiniLED电视
基于VL813芯片的USB3.0 HUB方案
商汤集团2021年实现营收47亿元
MODBUS RTU传输模式介绍
在FPGA上实现咬尾卷积码的最优算法设计
小米6X和红米6 Pro对比分析，看看两者之间到底有什么区别
国产“章鱼”第二版设计者说
通过触摸实现真实感的Piezo(压电)触觉反馈设备
TGV处理薄玻璃的处理方案
基于区块链技术去中心化的场外交易平台商币平台介绍
不止渲染已久的魅族Pro7首款双面屏手机，还有p25一款神秘新机！
Nordic使能跟踪网关设备新产品的介绍和应用说明
漫谈BTO 笔记本电脑DIY常识课
5G环境下国内光模块将有更大的机会向高端光模块市场发力
关于移动设备快充的方法的分析和应用
首创•中传 首届文创校友沙龙暨中国传媒大学校友创业联合会筹备会 互联网资讯
PLC程序解锁解码的详细介绍
晶振的基本性能及应用注意事项
京瓷推出008004尺寸微型MLCC