一種基于碼譜數值算法的改進算法

摘 要： 碼譜是一種分析分布式算術碼的編碼性能和解碼復雜度的工具，能有效提高編碼性能。碼譜的計算一般采用數值算法，該方法是一個迭代計算的過程，時間復雜度很高。針對時間復雜度高這個問題，通過去掉多余的函數精簡數值算法，提出一種基于碼譜數值算法的改進算法，進而降低時間復雜度。從理論上證明改進數值算法的正確性，實驗結果表明，改進后的數值算法能有效提高碼譜的計算效率，拓寬碼譜的實際應用范圍。

關鍵詞： 分布式算術碼； 碼譜； 數值算法； 迭代計算

中圖分類號： TN911?34； TN911.2 文獻標識碼： A 文章編號： 1004?373X（2016）18?0001?03

Abstract： Code spectrum is a tool of analyzing the encoding performance and decoding complexity of distributed arithmetic coding， which can effectively improve the encoding performance. The numerical algorithm is usually used in code spectrum calculation， but it is an iterative calculation process， in which the time complexity is very high. To solve this problem， an improved algorithm based on code spectrum numerical algorithm is proposed， which simplifies the numerical algorithm by removing the unnecessary functions. The correctness of the improved numerical algorithm is verified theoretically in the paper. The experimental results show that the improved numerical algorithm can effectively improve the computational efficiency of code spectrum， and broaden the practical application range of code spectrum.

Keywords： distributed arithmetic code； code spectrum； numerical algorithm； iterative calculation

0 引 言

隨著信息技術的不斷發展，海量的數據不斷產生，數據存儲的需求越來越大，編碼技術在其中起著越來越重要的作用[1?2]。分布式算術碼以其接近香農極限的優良性能得到廣泛應用[3?7]。其中算術碼碼譜能改進分布式算術碼的編解碼過程，降低實際解碼錯誤率[8?10]，對分布式算術碼的實際應用有重要作用[11]。碼譜的計算一般采用數值計算的方法。該方法是一個迭代計算的過程，主要分四步：離散化、初始化、迭代和歸一化。迭代過程是將區間劃分為三部分，[clip]函數將區間內參數范圍限制到[0，N-1]，是整個迭代過程最耗時的部分。而該數值算法的主要計算集中在迭代過程，隨著迭代次數的增加，算法的效率會大幅度降低[7?8]。

針對數值算法計算復雜度高、效率低的問題，簡化現有的數值算法，提出一種改進算法。理論證明劃分后的區間在不需要clip函數的情況下，參數也能保證在區間[0，N-1]內，進而提出一種去clip函數的改進算法。本文在理論上證明改進算法的正確性，實驗結果表明改進算法能夠有效提高計算效率。

1 算術碼碼譜

表1取8組實驗數據，由于計算過程有隨機性，每組結果取5 000次實驗后的平均值。實驗結果如表1所示，表中第一列表示參數[q]，第二列表示改進前數值算法的運行時間，第三列表示改進后數值算法的運行時間，第四列表示改進后數值算法的加速比。由表1可以看出，改進后的數值算法的運行速度相比改進前的數值算法得到了1.1～1.3倍的加速比。實驗結果充分證明了改進后的數值算法的有效性和可行性。圖2是對表1中8組不同參數設置下兩種數值算法速度對比效果圖，其中灰色是改進后的運行時間。

去掉clip函數后，可以簡化計算過程，從時間復雜度來看改進前數值算法的時間復雜度為[O（3N+KN）]，簡化后的算法去掉了clip函數，算法的時間復雜度為[O（N+KN）]，K表示迭代次數，實驗表明K的值并不是很大。比較時間復雜度可知，該改進后的算法在效率上有一定的提升。由以上實驗結果可知，改進后的數值算法不僅保證計算結果的正確性，而且有效提高計算效率，大大提升碼譜的實用性。

5 結 語

通過分析經典碼譜數值方法的迭代過程，提出一種去[clip]函數的基于碼譜數值算法的改進算法。不僅在理論上證明了該方法的正確性，而且實驗結果表明，相比經典的碼譜數值算法，提出的改進算法在效率上有1.1～1.3倍的提升，一定程度上緩解了經典碼譜數值算法效率低的問題。碼譜計算的難點在于數值計算，解決了這個問題，以后工作的重點是將碼譜推廣到一般信源。

注：本文通訊作者為來智勇。

參考文獻

[1] 陳運.信息論與編碼[M].2版.北京：電子工業出版社，2011：49?52.

[2] RISSANEN J J. Generalized Kraft inequality and arithmetic coding [J]. IBM journal of research development， 1976， 20（3）： 198?203.

[3] GRANGETTO M， MAGLI E， OLMO G. Distributed arithmetic coding [J]. IEEE communication letters， 2007， 11（11）： 883?885.

[4] GRANGETTO M， MAGLI E， TRON R， et al. Rate?compatible distributed arithmetic coding [J]. IEEE communication letters， 2008， 12（8）： 575?577.

[5] GRANGETTO M， MAGLI E， OLMO G. Distributed joint source?channel arithmetic coding [C]// Proceedings of IEEE ICIP. [S.l.]： IEEE， 2007： 3717?3720.

[6] GRANGETTO M， MAGLI E， TRON R， et al. Distributed arithmetic coding for the Slepian?Wolf problem [J]. IEEE transactions on signal process， 2009， 57（6）：2245?2257.

[7] FANG Yong. DAC spectrum of binary sources with equally?likely symbols [J]. IEEE transactions on communication， 2013， 61（4）： 1584?1594.

[8] FANG Yong. Distribution of distributed arithmetic codewords for equiprobable binary sources [J]. IEEE signal processing letters， 2009， 16（12）： 1079?1082.

[9] FANG Yong. Asymmetric Slepian?Wolf coding of nonstationarily?correlated M?ary sources with sliding?window belief propagation [J]. IEEE transactions on communication， 2013， 61（12）：5114?5124.

[10] LIU Yayun， FANG Yong. Codebook cardinality spectrum of distributed arithmetic codes for nonuniform binary sources [J]. Communications in computer and information science， 2015， 547： 458?467.

[11] FANG Yong， CHEN Liang. Improved binary DAC codec with spectrum for equiprobable sources [J]. IEEE transactions on communication， 2014， 62（1）：256?268.