论文部分内容阅读
摘 要： 维特比算法是卷积码的一种最大似然译码，其幸存路径和幸存路径度量的存储均有不同的实现方法，设计的通用维特比译码器，采用同址存储方法来实现幸存路径及其度量的存储，并用Matlab仿真该结构的译码器，结果表明该结构的译码器可正确实现译码，并且控制相对简单、译码延时较小。
关键词： 同址存储；维特比译码器；幸存路径；路径度量；FPGA
中图分类号：TN929 文献标识码：A 文章编号：1671－7597（2011）1210137－02
0 引言
维特比算法是卷积码的一种最佳概率译码方法[1]。实际中对某一种码型的维特比译码进行研究的较多，而有时需要不同码型的维特比译码，即通用的。
维特比译码中，需要将各个状态的幸存路径及其度量进行存储。路径度量的存储通常采用两种结构：乒乓结构和同址存储。幸存路径的存储有两种传统的实现方法：寄存器交换法[2]和回溯法[3]。本文设计的通用维特比译码器采用同址存储法[4]来实现幸存路径及其度量的存储，其控制相对简单、译码延时较小。
1 同址存储方法
在维特比译码器中，幸存路径或其度量的存储，就是记录下译码器每组输入时，各个状态对应的幸存路径或其度量。同址存储就是将前一时刻某个状态的幸存路径或其度量的信息，从一个地址读出，当经过加-比-选（ACS）单元处理后，把新状态的幸存路径或其度量又存储到该地址中。
以（2，1，3）卷积码为例，来介绍同址存储方法的原理，其ACS采用基2蝶形运算（见图1，图中转移分支上为该分支对应的判决比特）。
图1 基2蝶形运算图
图1中， 表示在n-1时刻0X状态。第n时刻，转移到状态X0的路径有21条，即从n-1时刻的0X状态转移过来的路径①，和从n-1时刻的1X状态转移过来的路径②。同样，在n时刻，转移到状态X1的路径也有21条，即路径③和④。但转移到各个状态的幸存路径只有一条，同时，在n时刻的其余状态的幸存路径都不会经由0X或1X状态转移过来，这样就可以实现幸存路径或其度量的同址存储。同址存储时，存储器按照状态个数分成相应的存储单元，里面存储的是相应状态的幸存路径或其度量。
图2 与图1对应的幸存路径存储器的信息
若此时译码深度为8，n时刻经过ACS的计算，确定状态X0和X1的幸存路径分别为第①条和第④条。此时，在幸存路径存储器里面，存储的是n-1时刻各个状态对应的幸存路径，见图2。则n时刻，状态X0的幸存路径可由前一状态0X所对应的幸存路径，加上状态X0的判决比特构成。通过对寄存器的读操作，从A中读出0X状态的幸存路径00001100，左移一位后，在该路径的后面添加一比特0，最后X0状态对应的幸存路径00011000，再将其存储到存储器的A地址里；同理，n时刻的X1状态对应的幸存路径为01001001，在存储X0状态的幸存路径的同时，将01001001存储于B地址中，这样就实现了幸存路径的同址存储。幸存路径度量的存储与此原理类似。
对于（n，k，N）卷积码（其中k 表示编码输入数据的位数，n表示编码输出数据位数，N表示约束长度），基2k蝶形运算如图3所示。输入的2k个状态的幸存路径及其度量，只与输出的2k个状态的幸存路径及其度量有关，并且输出的2k个状态的幸存路径及其度量的确定只与输入的2k个状态的幸存路径及其度量有关，所以可以用同址存储法实现幸存路径的存储。
由于幸存路径及其度量均采用同址存储，那么这两部分的控制就相同。同址存储方法中，如果存储是幸存路径，即译码后的序列，当达到译码深度后，就可以直接进行输出，不需要回溯，相应的译码延时就小；且采用的幸存路径存储部分是RAM（寄存器交换法采用寄存器和多路选择器），则会占用较少的资源。
图3 （n，k，N）卷积编码的一个基2k蝶形运算图
2 Matlab仿真
为了检验采用同址存储的通用维特比译码器的功能，本文采用Matlab进行仿真。
如果已知卷积码的n、k、N及其子生成元的系数 或 （其中K＝0，1，……，k-1，l＝0，1，……，N-1，j＝0，1，……，n-1），就可以确定其结构（见图4），根据此结构就可在Matlab中实现任意卷积码的编码。
（N，k，N）的维特比译码，共有2k（N-1）个状态，对应每组译码器的输入，基本的译码步骤为：
1）计算出一个基2k蝶形运算中每个输出状态的2k个分支度量。
2）读出该蝶形运算需要的2k个输入状态的幸存路径路径及其度量。
3）对蝶形结构的输出2k状态均进行ACS运算，确定每个输出状态的幸存路径及其度量。
4）将输出的2k个状态的新幸存路径及其度量进行存储。此时幸存路径或其度量采用同址存储法：2k个输出状态的幸存路径或其度量信息，存储到原来存储2k个输入状态的存储地址中，完成幸存路径或其度量的同址存储。
5）完成所有2k（N-1）状态的ACS计算，即2k（N-2）个基2k的蝶形运算，计算过程见1）-4）。
6）若达到译码深度，则选择具有最大度量幸存路径进行译码输出，每次输出k比特；若输入码元组数小于译码深度，则等所有输入均完成译码后，再选择具有最大度量的幸存路径进行译码输出。
用Matlab完成上述的卷积码的编译码过程，再将两者连接到一起进行验证。给定任意一组编码输入序列、k、n、N和相应的子生成元的系数，通过编、译码器后，观察译码的输出码元和编码的输入码元是否一致。如果一致，说明能正常译码，即采用同址存储的幸存路径及其度量存储是可行的。本程序对码率分别为1/2、1/3、1/4、2/3、3/4的适用于维特比译码算法的码[1]进行了验证：当给定一组卷积码的结构和随机的一组编码输入，将编码器的输出序列再作为维特比译码器的输入，发现译码器的输出序列与编码输入一致。图5是k=3、n=4、N=4、g11=40、g12=14、g13=34、g14=60、g21=04、g22=64、g23=20、g24=70、g31=34、g32=00、g33=60、g34=64
码型的卷积码的编码输入和译码输出的波形，其输入与输出完全一致。
3 结论
幸存路径及其度量是维特比译码器中的主要存储内容，如这两部分的结构合适，就可以大大减小译码器的硬件资源，并简化控制。传统的寄存器存储，需要寄存器和MUX，而同址存储用RAM进行存储，需要的硬件资源相对会少；传统的回溯法，存储的幸存路径在达到译码深度之后要进行回溯操作，而回溯时间需要一定的时间，但同址存储法由于存储的就是译码的信息，所以在达到译码深度后就可以直接进行输出，无需回溯。幸存路径度量的乒乓结构需要两组路径度量存储单元；而同址存储只需要一组存储单元，硬件资源会少。当幸存路径及其度量均采用同址存储时，这两部分的控制也相同，简化了控制的实现。在今后的设计中值得推广应用。
图5 （4，3，4）卷积码编、译码的各个序列
基金项目：福建省教育厅B类科技项目（JB09009）
参考文献：
[1]王新梅、肖国镇，纠错码——原理与方法，西安：西安电子科技大学出版社，2001.
[2]D.A.El-Dib,M.I.Elmasry.Modified register-exchange Viterbi dec
oder for low-power wireless communications.IEEE Transactions on Circuits and Systems,2004,51(2):371-378.
[3]Mario Traber.A Low Power Survivor Memory Unit For Sequential Viterbi Decoders.The 2001 IEEE International Symposium on,Circuits and Systems,2001.ISCAS 2001.Volume: 4:6-9 May 2001:214-217.
[4]张红、陈新、张国成，维特比译码器中幸存路径存储器的一种新的实现方法，应用科技，2007，34（3）：19-22.
作者简介：
张红（1978-），女，讲师，福州大学物理与信息工程学院。
关键词： 同址存储；维特比译码器；幸存路径；路径度量；FPGA
中图分类号：TN929 文献标识码：A 文章编号：1671－7597（2011）1210137－02
0 引言
维特比算法是卷积码的一种最佳概率译码方法[1]。实际中对某一种码型的维特比译码进行研究的较多，而有时需要不同码型的维特比译码，即通用的。
维特比译码中，需要将各个状态的幸存路径及其度量进行存储。路径度量的存储通常采用两种结构：乒乓结构和同址存储。幸存路径的存储有两种传统的实现方法：寄存器交换法[2]和回溯法[3]。本文设计的通用维特比译码器采用同址存储法[4]来实现幸存路径及其度量的存储，其控制相对简单、译码延时较小。
1 同址存储方法
在维特比译码器中，幸存路径或其度量的存储，就是记录下译码器每组输入时，各个状态对应的幸存路径或其度量。同址存储就是将前一时刻某个状态的幸存路径或其度量的信息，从一个地址读出，当经过加-比-选（ACS）单元处理后，把新状态的幸存路径或其度量又存储到该地址中。
以（2，1，3）卷积码为例，来介绍同址存储方法的原理，其ACS采用基2蝶形运算（见图1，图中转移分支上为该分支对应的判决比特）。
图1 基2蝶形运算图
图1中， 表示在n-1时刻0X状态。第n时刻，转移到状态X0的路径有21条，即从n-1时刻的0X状态转移过来的路径①，和从n-1时刻的1X状态转移过来的路径②。同样，在n时刻，转移到状态X1的路径也有21条，即路径③和④。但转移到各个状态的幸存路径只有一条，同时，在n时刻的其余状态的幸存路径都不会经由0X或1X状态转移过来，这样就可以实现幸存路径或其度量的同址存储。同址存储时，存储器按照状态个数分成相应的存储单元，里面存储的是相应状态的幸存路径或其度量。
图2 与图1对应的幸存路径存储器的信息
若此时译码深度为8，n时刻经过ACS的计算，确定状态X0和X1的幸存路径分别为第①条和第④条。此时，在幸存路径存储器里面，存储的是n-1时刻各个状态对应的幸存路径，见图2。则n时刻，状态X0的幸存路径可由前一状态0X所对应的幸存路径，加上状态X0的判决比特构成。通过对寄存器的读操作，从A中读出0X状态的幸存路径00001100，左移一位后，在该路径的后面添加一比特0，最后X0状态对应的幸存路径00011000，再将其存储到存储器的A地址里；同理，n时刻的X1状态对应的幸存路径为01001001，在存储X0状态的幸存路径的同时，将01001001存储于B地址中，这样就实现了幸存路径的同址存储。幸存路径度量的存储与此原理类似。
对于（n，k，N）卷积码（其中k 表示编码输入数据的位数，n表示编码输出数据位数，N表示约束长度），基2k蝶形运算如图3所示。输入的2k个状态的幸存路径及其度量，只与输出的2k个状态的幸存路径及其度量有关，并且输出的2k个状态的幸存路径及其度量的确定只与输入的2k个状态的幸存路径及其度量有关，所以可以用同址存储法实现幸存路径的存储。
由于幸存路径及其度量均采用同址存储，那么这两部分的控制就相同。同址存储方法中，如果存储是幸存路径，即译码后的序列，当达到译码深度后，就可以直接进行输出，不需要回溯，相应的译码延时就小；且采用的幸存路径存储部分是RAM（寄存器交换法采用寄存器和多路选择器），则会占用较少的资源。
图3 （n，k，N）卷积编码的一个基2k蝶形运算图
2 Matlab仿真
为了检验采用同址存储的通用维特比译码器的功能，本文采用Matlab进行仿真。
如果已知卷积码的n、k、N及其子生成元的系数 或 （其中K＝0，1，……，k-1，l＝0，1，……，N-1，j＝0，1，……，n-1），就可以确定其结构（见图4），根据此结构就可在Matlab中实现任意卷积码的编码。
（N，k，N）的维特比译码，共有2k（N-1）个状态，对应每组译码器的输入，基本的译码步骤为：
1）计算出一个基2k蝶形运算中每个输出状态的2k个分支度量。
2）读出该蝶形运算需要的2k个输入状态的幸存路径路径及其度量。
3）对蝶形结构的输出2k状态均进行ACS运算，确定每个输出状态的幸存路径及其度量。
4）将输出的2k个状态的新幸存路径及其度量进行存储。此时幸存路径或其度量采用同址存储法：2k个输出状态的幸存路径或其度量信息，存储到原来存储2k个输入状态的存储地址中，完成幸存路径或其度量的同址存储。
5）完成所有2k（N-1）状态的ACS计算，即2k（N-2）个基2k的蝶形运算，计算过程见1）-4）。
6）若达到译码深度，则选择具有最大度量幸存路径进行译码输出，每次输出k比特；若输入码元组数小于译码深度，则等所有输入均完成译码后，再选择具有最大度量的幸存路径进行译码输出。
用Matlab完成上述的卷积码的编译码过程，再将两者连接到一起进行验证。给定任意一组编码输入序列、k、n、N和相应的子生成元的系数，通过编、译码器后，观察译码的输出码元和编码的输入码元是否一致。如果一致，说明能正常译码，即采用同址存储的幸存路径及其度量存储是可行的。本程序对码率分别为1/2、1/3、1/4、2/3、3/4的适用于维特比译码算法的码[1]进行了验证：当给定一组卷积码的结构和随机的一组编码输入，将编码器的输出序列再作为维特比译码器的输入，发现译码器的输出序列与编码输入一致。图5是k=3、n=4、N=4、g11=40、g12=14、g13=34、g14=60、g21=04、g22=64、g23=20、g24=70、g31=34、g32=00、g33=60、g34=64
码型的卷积码的编码输入和译码输出的波形，其输入与输出完全一致。
3 结论
幸存路径及其度量是维特比译码器中的主要存储内容，如这两部分的结构合适，就可以大大减小译码器的硬件资源，并简化控制。传统的寄存器存储，需要寄存器和MUX，而同址存储用RAM进行存储，需要的硬件资源相对会少；传统的回溯法，存储的幸存路径在达到译码深度之后要进行回溯操作，而回溯时间需要一定的时间，但同址存储法由于存储的就是译码的信息，所以在达到译码深度后就可以直接进行输出，无需回溯。幸存路径度量的乒乓结构需要两组路径度量存储单元；而同址存储只需要一组存储单元，硬件资源会少。当幸存路径及其度量均采用同址存储时，这两部分的控制也相同，简化了控制的实现。在今后的设计中值得推广应用。
图5 （4，3，4）卷积码编、译码的各个序列
基金项目：福建省教育厅B类科技项目（JB09009）
参考文献：
[1]王新梅、肖国镇，纠错码——原理与方法，西安：西安电子科技大学出版社，2001.
[2]D.A.El-Dib,M.I.Elmasry.Modified register-exchange Viterbi dec
oder for low-power wireless communications.IEEE Transactions on Circuits and Systems,2004,51(2):371-378.
[3]Mario Traber.A Low Power Survivor Memory Unit For Sequential Viterbi Decoders.The 2001 IEEE International Symposium on,Circuits and Systems,2001.ISCAS 2001.Volume: 4:6-9 May 2001:214-217.
[4]张红、陈新、张国成，维特比译码器中幸存路径存储器的一种新的实现方法，应用科技，2007，34（3）：19-22.
作者简介：
张红（1978-），女，讲师，福州大学物理与信息工程学院。