FPGA_ASIC-卷积码的Viterbi高速译码方案

投稿栏目：嵌入式与SOC——PLDCPLDFPGA应用卷积码的Viterbi高速译码方案AHigh-speedviterbi-decodingSchemeforConvolutionalCode（1.南京师范大学分析测试中心，2.南京师范大学物理科学与技术学院）刘国锦1王济生2时斌1朱晓舒1（1.AnalysisandTestingCenterofNanjingNormalUniversity,2.SchoolofPhysicsandTechnologyofNanjingNormalUniversity）LIUGuo-jin1WANGJi-sheng2摘要：本文探讨了无线通信中广泛涉及的差错控制问题，介绍了卷积码的编译码原理。提出了一种卷积码编码，及其高速Viterbi译码的实现方案，对译码的各个组成部分作了分析，并在FPGA中实现了该译码方案。仿真结果表明，在纠正能力范围内，能够正确纠错并译码，且具有高速译码的优点，达到了预期的效果，该设计方案可以非常容易地应用到很多差错控制的通信系统中。Abstract:Thispaperdiscussestheissueoferror-controlinvolvedwidelyinwirelesscommunications,andintroducesthecodingandendcodingprincipleofConvolutionalCode.AschemeofencodingofConvolutionalCodeanditshigh-speedviterbidecodingisproposed,andthecomponentsofdecodingareanalysed,thentheschemeisimplementedinFPGA.Thesimulationresultindicatesthatitcancorrecttheerrorbitsexactlywithintherangeofcapabilityerror-correcting,andithastheadvantageofhigh-speeddecoding.Prospectiveeffectisrealized.Thisdesignschemecanbeappliedeasilyinmanycommunicationsystemswitherror-control.关键词：差错控制；卷积码；Viterbi译码；寄存器交换Keywords:error-control;ConvolutionalCode;viterbidecoding;register-exchange中图分类号：TN492文献标识码：A0引言在无线通信过程中，由于信道中噪声干扰的存在，会不可避免地造成发送端的码元经过有噪信道到达接收端后，接受的码元中发生了差错，从而影响了无线数据通信的可靠性。为了提高数据传输的可靠性，通常在发送端对数据进行差错控制编码，也称为信道编码。在GSM及CDMA移动通信系统中，信道编码方案都广泛采用卷积码。在GSM系统的全速率业务信道（TCH/FS）中，采用1/2码率的（2，1，4）卷积编码。在CDMA系统中，正向信道和反向信道中分别采用（2，1，9）和（3，1，9）两种卷积编码方案，并结合块交织，进行信道的差错控制编码，以降低移动通信系统的误码率，保证数据传输的质量。卷积码的译码有两种方案，一种是寄存器交换法（RE），一种是回溯法（TB）。两种方案各有利弊，应基于不同的应用场合，合理选择译码方案。在低速通信场合，可以选择回溯法，但是在高速通信中，高数据速率必然要求有高的编译码速率。若采用回溯法，则要求回溯速率是译码输出速率的几十倍，显然如果输出速率很高，回溯速率必然更高，甚至无法实现，这时采用寄存器交换法便能更好适应高速译码的需要。本文主要讨论一种（2，1，4）卷积码的编译码原理，及其高速Viterbi译码的FPGA实现，并对结果做了分析。1、卷积码的编译码原理1.1卷积码的编码原理卷积码是爱里斯（Elias）在1955年提出的，它与分组码不同。卷积码编码器把k比特信息段编成n比特的码组，这个n比特的码组不仅同当前输入的k比特信息段有关，还与前面的（N-1）个信息段有关，N称为约束长度。卷积码可以用矩阵和多项式表示，编码器可以用移位寄存器和模2加法器实现。本文所讨论的（2，1，4）卷积码，k=1，n=2，码率为1/2，约束长度N=5（即存储长度m=4），多项式为G0=（23）=10011，G1=（35）=11101，图1是（2，1，4）卷积编码的结构图。图1(2,1,4)编码器结构图由编码结构图，可以得出编码输入输出码元之间的关系：034iiiiCmmm−−=⊕⊕1124iiiiiCmmmm−−−=⊕⊕⊕其中，im为输入码元，0iC、1iC为输出码元，可见本时刻的输出不仅取决于本时刻的输入，还取决于本时刻之前四个时刻的输入。此外，还可计算得，编码器共有24=16个状态。1.2卷积码的Viterbi译码原理卷积码最常用的译码算法是Viterbi译码，它是一种最大似然算法。它把接收序列与所有可能的发送序列相比较，选择具有最小码距的一个序列作为发送序列，并译出对应的信息序列。译码算法步骤如下：（1）从某一时间单位j=m开始，对进入每一状态的所有长为j段分支的部分路径，计算部分路径度量。对每一状态，挑选并存贮一条具有最大度量的部分路径及其部分度量值，此部分路径称为幸存路径。（2）j增加1，把此时刻进入每一状态的所有分支度量，同与这些分支相连的前一时刻的幸存路径的度量相加，得到了此时刻进入每一状态的幸存路径，加以存贮并删去其它所有路径，因此幸存路径延长了一个分支。（3）若jL+m（L为信息序列长度），则重复以上各步，否则停止，译码器得到了有最大路径度量的路径。实际中，当L很大时，经计算比较，得到完整的幸存路径后再做译码输出，译码器需存贮的幸存路径信息量太大，不太现实，而且译码输出的延时也较长。当幸存路径达到一定长度时，此时每个状态对应的幸存路径，它们前面的几个分支已经重合，因此只需要存储一定长度的幸存路径信息，即可进行信息序列的判决输出，而不会影响结果的正确性。这种方法称为截尾译码，截尾的路径长度，称为译码深度，记作τ，一般选择τ=(5~10)m。当处理完τ段幸存路径后，就开始判决输出，并且此后每处理一段就输出一段信息码元。2、Viterbi译码器的设计Viterbi译码器组成可分为，分支度量单元（BMU），加比选单元（ACS），路径度量存储单元（PMU），幸存路径存储和输出单元。译码电路按照ACS单元的组合方式，可以分为全并行方式，串行方式，串并结合方式。全并行结构，给每个状态分配一个ACS单元，同时进行各个状态的“加—比—选”运算，这种方式的电路设计相对简单一些，处理速度最快，但是需要的硬件开销也大。本文采用全并行方式，主要考虑其高速译码的优点。设计中取τ=5m=20，译码输出的等待时间为20个码段时钟周期。幸存路径存储有两种方法，一种是寄存器交换法（RE），一种是回溯法（TR），这里采用寄存器交换法。译码输出，采用最大路径度量法，在所有可能的幸存路径中，挑选一个具有最大路径度量的路径，以其对应的信息序列作为译码器的输出。（2，1，4）卷积码的Viterbi译码结构框图如图2所示。图2Viterbi译码结构框图2.1、分支度量（BMU）单元接收端的信号经过量化后，首先送到译码器的分支度量单元，计算相应的分支度量值。对于硬判决来说，度量值就是接收码字与该分支路径对应的的编码码字之间的汉明距离。（2，1，4）卷积码，共有16个状态，假设编码器的当前状态S=A4A3A2A1，则下一时刻的状态为S=A3A2A1X，“X”为下一时刻的输入编码器的信息元。由于“X”有两种可能值，0或者1，因此下一时刻所处的状态也有两种可能。相应的，前一时刻的每一状态可能转移到后一时刻的状态，有2条可能的路径，同时有2个可能的输出码字。BMU单元就是要根据当前的状态，分别计算接收码字与当前状态转移到下一时刻状态时输出的码字之间的汉明距离。由于（2，1，4）共有16个状态，对应的有32个分支，BMU单元需要分别计算32条分支的度量值，也即32个汉明距离。2.2加比选（ACS）和度量更新单元前后时刻之间新状态向老状态转移，对应的分支与连接老状态的部分路径，形成新状态的部分路径。（2，1，m）卷积码，前一时刻有两条分支到达当前时刻的每一状态。加比选单元是Viterbi译码的核心运算单元，主要任务是计算、比较到达当前时刻每一状态的两条部分路径的汉明距离，选择具有较小汉明距离的一条部分路径，作为到达该状态的幸存路径，并且更新该状态的度量值，以及输出判决比特。随着译码过程不断延伸，度量值也不断累积，为防止保存在寄存器中的度量值溢出，必须进行度量的控制。有关文献中，已指出解决方法，对于硬判决译码，在每次ACS运算之前，先选出当前所有状态度量中的最小度量值，再将各状态度量值与此最小度量值相减。然后进行ACS运算，只需要log2(2m)+1=4bit二进制数来表示每个新的状态度量值。图3“加比选”蝶形单元结构通常“加比选“运算采用蝶形单元的结构，如图3所示，前一时刻两个状态（is、8is+）和后一时刻两个状态（2is、21is+）组成一个蝶形单元，采用全并行结构，共需16/2=8个蝶形单元。例如当前状态为S12，它可能由前一时刻的状态S6或者S14转移而来。设前一时刻S6的度量值为4，S14的度量值为3，最小度量值为1，S6到达S12的分支（上分支）度量为0，S14到达S12的分支（下分支）度量为2，则沿上分支到达S12后，S12的新度量值为4-1+0=3，沿下分支到达，S12的新度量值为3-1+2=4，因此选择上分支作为到达S12的部分路径，并且更新S12的度量值为3，由于状态S12为“1100”，最低位为“0”，可以判断编码的输入信息元为“0”，译码判决的输出比特也应是“0”。2.3幸存路径存储和输出单元采用寄存器交换法存储幸存路径信息，ACS单元输出的幸存路径信息，就是对应该路径的译码输出比特。方案选择译码深度τ=20，每个状态分配20bit的存储单元，bit_0~bit_19，16个状态共需16x20=320bit。译码器每收到一个码字，经一系列处理后，ACS单元将输出16bit的译码比特，分别对应16个状态。如果当前状态S12由前一时刻的状态S6转移而来，则译码输出“0”，填入S12寄存器的bit_0位置，且S12状态将“继承”前一时刻S6状态的译码比特。采用RE法，将前一时刻S6状态对应的寄存器中的bit_19，作为当前时刻以状态S12结束的部分路径的译码输出，同时bit_18~bit_0拷贝到S12寄存器的bit_19~bit_1，这样便完成了状态S12的幸存路径的存储。依次方式，分别完成其它状态的幸存路径存储。当处理过的码字长度小于译码深度（τ=20）时，不输出译码，否则开始译码输出。译码产生，采用最大度量（最小汉明距离）选取法，即选择具有最小汉明距离的路径，将其路径寄存器中的最高位作为译码输出。3结果分析根据前面介绍的各模块的工作原理，就可以在FPGA中实现（2，1，4）卷积码的Viterbi译码。利在QuartusII软件，采用VHDL语言完成各功能模块的描述，在译码器设计的顶层实体中，用元件例化的方法，例化各模块实体，并进行元件的端口映射，完成一个完整的译码器设计。然后再用QuartusII软件完成系统的综合、仿真，进行分析验证。假设输入编码器的信息码元序列“01100，10001，00011，01111，00010，10000”，应输出码字为“03103，11210，22101，00302，20202，13113”，仿真波形图4所示。当输入编码器的码字有误码时，“02103，11210，32101，00302，10212，13113”，加下划线的表示该码字有误，经过Viterbi译码器后输出的译码波形如图5。比较仿真波形图5和图4，