一種基于碼譜數(shù)值算法的改進算法

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

關(guān)鍵詞： 分布式算術(shù)碼； 碼譜； 數(shù)值算法； 迭代計算

中圖分類號： 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 引 言

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

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

1 算術(shù)碼碼譜

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

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

5 結(jié) 語

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

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

參考文獻

[1] 陳運.信息論與編碼[M].2版.北京：電子工業(yè)出版社，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.