線性分組碼譯碼算法的快速性能分析

摘 要：為了分析高斯白噪信道中線性分組碼的譯碼性能，提出了采用低信噪比時數值仿真和高信噪比時理論估算相結合的方法來計算誤碼率，從而快速準確地獲取整個信噪比范圍內的譯碼性能曲線。試驗結果表明，該方法得到的誤碼率與實際誤碼率一致。

關鍵詞：線性分組碼；BCH；譯碼性能；誤碼率

中圖分類號：TN919.3 文獻標識碼：B

文章編號：1004373X(2008)0303102

Fast Analysis of Algorithm Performance for Decoding Linear Block Codes

HUANG Long，XU Xiaoyong，SUN Guangfu

(Satellite Navigation RD Center，School of Electronic Science and Engineering，National University.of Defense Technology，Changsha，410073，China)

Abstract：In order to analyze the decoding performance of linear block codes，a new method is proposed in this paper.The decoding performance plot can be gotten quickly and precisely within a wide SNR range by using computer emulation when SNR is low and theoretical estimation when SNR is high.Simulation results show advantage of the proposed method over conventional methods is much faster speed with little difference of the real decoding performance.

Keywords：linear block codes;BCH;decoding performance;error rate

1 引 言

衡量一種糾錯碼譯碼方法性能好壞的主要標準是其誤碼率指標。而要評估該譯碼方法在指定誤碼率下所需的輸入信噪比，就需要獲取較寬信噪比范圍內的誤碼率曲線。目前對誤碼率的評估均是通過計算機數值仿真得出，由蒙特卡羅仿真原理，通常需要測得100個誤碼才能確保統計得到的誤碼率有足夠好的置信度。比如某應用系統要求誤碼率指標低于10-5，則仿真樣本至少為107，如此大量的數據仿真耗費的計算機資源和計算時間是相當驚人的，甚至是不可實現的。

然而，高信噪比條件下的高斯白噪信道中，信道傳輸出現大量錯誤的概率是非常小的，因此可以只考慮在每個碼字中出現很少幾位錯誤的情況，而忽略發生概率極小的出現多位錯誤的情況。基于這種認識，本文提出了一種數值仿真和理論估算相結合的方法：在信噪比低于閾值時，用傳統的數值仿真技術得出其誤碼率；當信噪比高于閾值時，用理論估算得出其誤碼率，把兩段誤碼率曲線拼接起來即可得到整個信噪比范圍內的誤碼率曲線。采用該方法可以在普通的計算機配置和可接受的仿真時間內，準確地獲取整個信噪比范圍的誤碼率曲線。

2 線性分組碼的硬譯碼性能分析

2.1 譯碼方法

線性分組碼是目前研究最多也是應用最廣的一種糾錯碼，因此本文以線性分組碼的硬譯碼性能為研究對象進行討論。

在以下討論中，約定以C表示發送碼字，E表示高斯白噪信道產生的錯誤圖樣，E′表示譯碼器得出的錯誤圖樣，R表示接收矢量的硬判決結果，S表示接收矢量的伴隨式，表示譯碼結果，H表示線性分組碼的一致校驗矩陣。

對線性分組碼的硬譯碼分以下幾步完成[1]：

(1) 對接收信號進行硬判決，R=C+E；

若ri<0，則Ri=1;若ri≥0，則Ri=0

(2) 由R得到接收矢量的伴隨式，S=R#8226;HT=(C+E)#8226;HT=E#8226;HT；

(3) 根據伴隨式S確定錯誤圖樣E′；

(4) 得出譯碼結果，=R+E′=C+E+E′。

2.2 理論分析

對于最多可糾正t位錯的(n，k，t)線性分組碼，由糾錯碼理論可知，其一致校驗矩陣H中任意2t列均線性無關[1]，即：

其中，hip，hjq，(1≤ip≤n，1≤jq≤n)是H矩陣的列向量，且hip≠hjq。

假設對發送碼字C，信道產生的錯誤圖樣E的重量W(E)=t+1時， 則接收矢量R的伴隨式為：

由式(1)得:

即S不可能寫成H中任何t－1個列向量之和，這說明譯碼器得到的錯誤圖樣E′的重量W(E′)>t－1。又因為(n，k，t)線性分組碼錯誤圖樣的重量W(E′)≤t，由此得到W(E′)=t。因此，式(2)可寫為:

即該接收矢量的伴隨式S既可以用H中的t+1個列向量來表示，也可以用H中的t個列向量來表示。

只要式(4)中第二個等號兩邊的2t+1項有一項相同，則余下2t－1項線性相關，這與(n，k，t)碼H矩陣任意2t列均線性無關矛盾。因此式(4)中所有2t+1項均不相同，即譯碼器得出的錯誤圖樣E′與信道本身產生的錯誤圖樣E在非零碼元位置上完全不重合。因此糾錯譯碼將在硬判決t+1位誤碼的基礎上，再增加t位誤碼，導致該碼字最終結果有2t+1位發生誤碼。

2.3 誤碼率估計

在分析誤碼性能時，假設發送端發送全零碼字而不失一般性。經過加性高斯白噪信道傳輸，接收信號的每一位都服從均值為A(信號幅度)方差為σ2(噪聲功率)的正態分布，由此得接收矢量R每一位發生錯誤的概率[3]:

其中信噪比SNR=A2/(2σ2)。

由2.2節的分析可知，當信道傳輸出現t位以內的錯誤時，(n，k，t)線性分組碼可以完全糾正傳輸錯誤，誤碼為0。當信道傳輸出現t+1位錯誤時，糾錯譯碼后共有2t+1位誤碼。忽略信道傳輸出現大于t+1位錯誤的情況，得到對(n，k，t)線性分組碼在高信噪比時的誤碼率估計[2]：

若假設由伴隨式S確定的錯誤圖樣E′最大限度地不同于實際傳輸錯誤圖樣E，則誤碼率的上限可以由下式表示：

因此由式(6)得到的誤碼率估計與實際誤碼率相對誤差的上限為：

由式(8)得出最大相對估計誤差與信噪比的關系如圖1所示。

圖1 誤碼率估計相對誤差與信噪比的關系

圖1畫出了BCH(15，11，1)，BCH(15，7，2)和BCH(31，16，3)三種線性分組碼的誤碼率估計相對誤差與信噪比的關系。可以看出，當信噪比為6 dB時，最大相對誤差約10-2，并且相對誤差隨信噪比增大而迅速減小。這說明當信噪比大于6 dB時，式(6)的估計可以得到與實際誤碼率幾乎一致的結果，因此將BCH碼的信噪比閾值定為6 dB。

2.4 仿真結果

最終的試驗驗證以BCH(15，11，1)碼的硬譯碼誤碼率計算為例，在Matlab平臺上進行仿真。

圖2 BCH(15，11，1)碼實際硬譯碼與

理論估算誤碼率性能比較

由圖 2可知，當信噪比大于6 dB時，實際誤碼率與估計誤碼率的差別已經非常小，從而驗證了上述理論推導的結論。由圖2還可以看出，對應于仿真時間約9 h，只能得到7 dB以內的有效誤碼率曲線（仿真點數107，有效誤碼率為10-5量級）。若要得到更高信噪比下的誤碼性能，必須使仿真點數按指數增長，從而使得仿真時間迅速增加以致不可接受。

利用本文提出的方法可以很方便地得到BCH(15，11，1)碼譯碼算法在整個信噪比范圍內的誤碼率性能曲線。由圖 2的理論估算曲線可知，信噪比為6 dB時，誤碼率約10-4，因此仿真點數取106。此時在同樣的計算機配置下，只需大約80 min，大大節約了仿真時間。最后結果如圖3所示。

圖3 BCH(15，11，1)碼的誤碼率性能曲線

通過以上分析，得到譯碼算法的快速性能分析步驟如下：

(1) 由式(8)得到數值仿真和理論估算的信噪比閾值。

(2) 由式(6)計算信噪比閾值處的誤碼率，由此得到所需的仿真點數。

(3) 分別做計算機數值仿真和誤碼率理論估算。信噪比低于閾值部分誤碼率取自仿真數據，信噪比高于閾值部分誤碼率取自理論計算數據，將兩部分誤碼率拼接起來即可得到整個信噪比范圍內的誤碼率曲線。

3 結 語

本文提出的低信噪比下進行數值仿真與高信噪比下進行理論估算相結合的方法來獲取較寬信噪比范圍內的糾錯碼誤碼性能，可以大大節省仿真時間，并且有很高的準確度。通過仿真試驗，證實了該方法對線性分組碼是可行和有效的。并且在可以比較方便地估計出高信噪比條件下誤碼率時，該方法也可以推廣到其他糾錯碼的硬譯碼以及軟譯碼中。

參考文獻

[1]王新梅，肖國鎮.糾錯碼——原理與方法(修訂版)[M].西安：西安電子科技大學出版社，2001，

[2]張力軍，張宗橙，鄭寶玉.數字通信[M].4版.北京：電子工業出版社，2003.

[3]David Chase.A Class of Algorithms for Decoding Block Codes with Channel Measurement Information[J].IEEE Trans.on Information Theory，1972，IT—18(1):170—182.

作者簡介 黃 龍 男，1982年出生，國防科技大學電子科學與工程學院碩士生。研究方向為星基導航與定位技術。

許曉勇 男，1977年出生，國防科技大學電子科學與工程學院博士生。研究方向為星基導航與定位技術。

孫廣富 男，1970年出生，國防科技大學電子科學與工程學院副教授。研究方向為星基導航與定位技術。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。