自适应Viterbi译码器技术.doc

自适应Viterbi译码器技术摘 要：随着现代通信技术的迅速发展，高速和高可靠性成为衡量信息传输质量的关键指标。信道编码技术能够对信道差错进行控制，降低误码率，实现可靠性通信，具有重要的军事和民事意义。Viterbi译码算法及其实现技术是信道编码技术的一个重要组成部分，但是其存在自身的缺陷或不足。Viterbi译码算法的译码性能将会随着码的相关长度增加而提高，但其实现的复杂度将以的比例增长。本文提出了一种自适应Viterbi译码算法IAVA(Improved Adaptive Viterbi Algorithm)。该算法利用信噪比评估模块自适应地调整门限值的高低，并利用复杂度评估模块自适应地改变译码器的基状态数，从而合理利用硬件资源。当译码器工作于低信噪比环境中时门限被自动调高，保证译码性能的同时适当减少了译码器的复杂度；当工作于高信噪比环境中时门限被自动调低，此时译码器复杂度得到锐减，译码模式将切换到基-4模式从而提高了译码速度，因此在大动态信噪比环境下该算法具有优越的性能。关键词：信道编码；自适应Viterbi译码；Viterbi译码；卷积码The Technology of Adaptive Viterbi DecodingYIN Qinghong，XU Xin，LI Nan，SUN Zhao Lin(College of Electronic Science and Engineering, National University of Defense and Technology, Changsha 410073, China )Abstract: With the development of modern communication technology, high speed and high stability have come into being two key factors when measuring the quality of information tansmission. The technology of channel encoding, which can control the channel errors, reduce the code error rate, and ensure the stable communication, has a deep meaning in military affairs and civil applicaton. The Viterbi decoding algorithm and the methd of its implementation are important parts of the channel encoding. However, they have their own limitation as well. In the algorithm of Viterbi decoding, while the performance of decoding is improved with the increasing of length of the convolutional encoding , the complexity to implement it increases at the rate of . A modified Viterbi decoding arithm IAVA is put forward. In the algorithm, while a SNR evaluating module is utilized to automatically adjust the gate-vaule, a complexity evaluating module is used to automatically adjust the decoders radix mode, through which, the resource is reasonably used. When working at the condition of low SNR, the gate-vaule is increased automatically. This way, reduces the decoding complexity while ensuring the good performance at the same time. When working at the condition of high SNR, the gata-vaule is decreased automatically to reduce the decoding complexity. In this working condition, the decoding mode is changed to radix-4 mode, which resultes in a rapid improvement in the decoding speed, thus the algorithm has a good performance in the condition of wide dynamic SNR.Key words: channel encoding, adaptive Viterbi decoding, Viterbi decoding, convolutional encoding 1.引 言在高斯白噪声通道通信中，对于卷积译码Vterbi译码算法是一种最优的解码算法。但是其复杂度会随着其状态数成2的指数增长，其指数K就是卷积码的相关长度。有两种经典的方法可以减少译码器的状态数，即M1,2算法和t算法3,4。M算法只保留在每次译码时的最好的状态，其中。对于M算法来说，其中的状态排序对于硬件实现来说比较复杂，误码率会随着M的减小而增加，然而硬件复杂度也会随着M的增加而增加。对于t算法来说，在每个译码时刻首先确定最优路径度量然后将其他度量路径大于的状态删除掉，其中是一个固定的值。用这种方法可以避免M算法中的状态排序问题，但是采用这种算在每个时刻的法状态数会将发生变化。总之，采用此算法状态数会随着信噪比(SNR)的大小而变化，当信噪比(SNR)大时所需的状态数较少，当信噪比(SNR)小时所需的状态数较多。因此，t算法在一定意义上可以说是一种自适应Vterbi译码器。但是在自适应滤波器中如何实现门限的选择将是问题的关键所在，本文提出了根据估计误码率的大小来判断信噪比的大小从而确定值的大小的横向自适应过程，以及通过评估复杂度来确定是否采用基-4译码器。本文的主要工作将在第二节对整个自适应算法的结构进行描述，第三节将主要介绍判决门限的自适应算法，第四节完成基-4自适应算法的描述，第五节将对整个自适应算法进行总结。2.总体方案设计图 1描述了传统Viterbi自适应算法的结构，与标准Viterbi算法相比较它增加了获取最优路径和幸存路径的舍取两个功能模块5。在第时刻ACS模块输出每种状态的其最优度量后，获取最优路径模块将找出所有状态中的最佳路径度量并令其为，然后幸存路径的舍取模块将根据各个状态的最优度量是否大于来确定该状态的最优度量是否被舍去。若则该状态的最优度量将舍去，反之则保留，其中是确定的正整数。是幸存路径舍取模块的判决极限，它将是由获取最优路径模块和共同决定的，而最优路径模块将找出所有状态中的最佳路径度量将随着时间不停的发生变化，值将决定所有状态路径度量值的动态范围。由于值是一个固定不变的值，因此在各种条件下其动态范围图 1经典自适应Viterbi译码算法结构都不会发生变化，因此就有可能出现当信噪比大时，只需要小动态范围就能满足要求但动态范围相对过大，而当信噪比较小时，需要打动态范围时但动态范围相对过小。因此需要寻找一种方法使其能在不同情况下自动调整值。本文采用一种新的自适应方式来确定值，如图 2所示。采用信噪比评估的方法可以根据信噪比的大小不同调节值的大小，从而可以更大的增加自适应Viterbi译码的灵活性。当信噪比评估模块判决出信噪比较高时，可以将值设置较小的值，当判决出信噪比较低时就将值设置较大的值。图 2改进后自适应Viterbi译码算法结构改进后的自适应Viterbi译码算法虽然具有具有根据信噪比大小的变化调制门限值的能力，但可以得知在高信噪比时门限降低而且各个状态的最优路径度量离最优度量较近的分布较小，因此在这种状态下所需状态数比较少，且误码率也很低，同理当信噪比较小时门限将会不断增大，且各个状态的最优路径度量分布也将逐渐均匀，因此会状态数会不断增加并接近标准Viterbi译码算法。从以上分析可知在高信噪比时所需资源急剧下降，而在低信噪比时资源没有发生改变。因此为了使资源得到合理有效的利用，可以在所需状态少的时候采用基-4模式来提高译码的速度，而在所需状态比较多的情况下才用基-2模式。因此在信噪比较高时采用基-4模式，而信噪比较低时采用基-2模式。因此在译码模式的选择上也可以实现自适应的过程，其具体设计框图如图 2所示。采用者种结构后，当评估出具有较高信噪比时分支度量、加-比-选、以及幸存路径的舍取都将转换为基-4模式。在基-4模式下，译码器的分支度量将直接度量两步的值，同样加-比-选也是对双步进行操作，其具体实现将在第四节进行描述。通过对模式进行自适应，译码器可以通过信噪比评估自主的实现资源的配置和译码速度的自适应，在保证误码率的前提下提高了资源的利用率，实现了资源的有效配置。3判决门限的自适应算法由图 2可知判决门限自适应的自适应Viterbi译码器算的门限值可以根据评估的信噪比大小而改变，因此我们可以设定不同的门限值来对译码过程进行比较。选择一个的二进制卷积编码序列，其中，如果输入的信号序列，则输出的卷积序列v=(11,01,01,00,10,11,00)。若接收机接收到的序列，其中第五位由于信道噪声而发生了改变。现在选择不当的值对译码过程进行比较，假设=1、2和3，其译码算法的网格图如图 3所示，图 3(a)是当时的网格图，由图可知在2T时刻只剩下状态其余三种状态均不能满足要求，在3T时刻状态和只能由状态和生成，由图可知状态和已被舍去，故其度量值应为，在5T和6T时刻状态、和度量值均超过门限值而舍去，因此在(a) 时的网格图(b) 时的网格图(c) 时的网格图图 3自适应译码器算法的网格图整个译码过程中状态数急剧减少，图中的黑色加粗路径为序列的真实路径；图 3(b)是当时的网格图，该图只有在2T和3T时刻有2个和1个状态被舍去，被舍去的状态数相对应图 3(a)有所减少，但译码复杂度有所增加；图 3(c)是当时的网格图，该图和标准Vterbi译码器结构完全相同，状态数没有任何变化。因此在信噪比较好时，若值设置过大，那么状态数就显得过多，译码过程变得复杂，而在信噪比较差时，若值设置过小就会使误码率加大。使用门限自适应译码器可以根据信噪比大小调节门限，从而解决上述的问题。因此门限自适应算法必须根据所计算的个状态的最优路径信息评估出信噪比的优劣，只有这样才能对门限值进行自适应。但需要如何评估信噪比的优劣将成为该模块的难点，通过仿真可以得知，当信噪比较大时，所以状态的最优度量值的最小度量值较小且所以状态的度量值分布不均匀，而当信噪比较小时，所有状态的最优度量值的最小度量值比较大且所有状态的度量值分布均匀。因此可以根据所有状态的最优度量值确定其信噪比的大小。4基-4模式自适应算法编码状态寄存器每移动一位后转换为新的状态，每一个新状态都对应着两个前导状态。如图 4所示，在进行从第i步到第步的译码时，前一级相差个状态的两个状态经过0和1路径，汇合到下一级奇偶相邻的两个状态，即状态和转移得到后一时刻的状态和。图中，实线为输入为0时的路径，虚线为输入为1时的路径。如当前状态为“001001”，假设数据由右端进入，那么到达这个新状态的前导状态则包括“000100”和“100100。加-比-选单元通过累加比较后存储两个前导状态中到达当前状态时状态度量值较小的一个。由于前导状态只有两个，因此可以用0和1作为区分这一节点的标志，这一节点标志就是幸存路径信息。这种每次状态寄存器仅移动一位的算法称为基二算法。基二算法每次运算仅产生一位幸存路径信息。图 4基-2算法示意图基四算法是对基二算法的合并。将一个状态数为的网格图可分解为个子网格图，每一个子网格图由个状态数为的网格图组成，通过将每一个状态的子网格图应用ACS循环更新的阶预测方法，合并为基的网格图。当时即为基四算法，如图 5所示，基四算法将基二算法中的两步合并为一步，这种算法使前一状态可能到达后一状态的数目比基二算法增加一倍。合并后的网格图并不影响译码性能，因为在被改变的网格图中的最优路径与原来基二的网格图之间有着一一对应的关系，由于幸存路径信息的表示方法由原来的一位增长为两位，在译码过程中每一步将产生两位译码结果，因此理论上基四算法要比基二算法的译码速率快一倍，但由于在基四算法额外增加的硬件会带来相应的延时，因此实际速率达不到理论值8。图 5基-2算法到基-4算法的转换示意图从图中可以看出在基-2算法中每个状态的前导状态为2，而在基-4算法中每个状态的前导状态为4，因此在在加-比-选时必须对四个度量值进行比较和选择，增加了译码算法的复杂度。5结束语可以看出，采用新的门限自适应Viterbi算法以后，译码性能并没有下降，而随着信噪比的改善，采用基-4算法，译码速度可以大大提高，同时随着卷积码状态数的增加，译码时间的减少也越显著。当然本算法并不能使译码性能得到提高。而在信噪比接近译码性能极限时，T值比较大，而使得与一般Viterbi算法没有什么区别。因此，本算法适用于信噪比变化范围较大的信道环境，可以在一种编译码方案下有效解决译码性能与译码速度的矛盾。参考文献1 F. Jeline and J.B. Anderson,Instrument- able Tree Encoding of Information SourcesJ, IEEE Trans. Inform. Theory, vol. IT-17, pp. 118-119,June 1971.2 J.B. Anderson and Elke Offer,Reduced- State Sequence Detection with Convolutional CodesJ, IEEE Trans. Inform. Theory, vol. 40, pp. 965-972,May 1994.3 J.B. Anderson,Limited Search Trellis Decoding of Convolutional CodesJ, IEEE Trans. Inform.Theory, vol. 35, pp. 944-955, Sep. 19894 Stanley J. Simmons,Breadth-First Trellis Decoding with Adaptive EffortJ, IEEE Trans.Com., vol. 38, pp. 3-12, Jan. 19905 S. J. Simmons, “Brea