【摘要】：糾錯碼理論理論提出60多年來,在理論和工程應(yīng)用中均取得了豐碩的成果,線性規(guī)劃(Linear Programming,LP)譯碼就是其中之一。本文提出了一種新的多項式時間復(fù)雜度的LP譯碼算法,通過理論及實驗仿真驗證了該方法在一定條件下滿足“ML特性”和“碼字獨立性”,同時結(jié)果表明該算法比Flanagan提出的LP譯碼算法執(zhí)行效率更高。主要內(nèi)容和研究成果如下:1.首先介紹了線性分組碼的基本概念及其Tanner圖表示形式,并引入了線性規(guī)劃的基本概念。由于線性規(guī)劃最優(yōu)值總在可行域組成的多面體頂點處取得,結(jié)合這個性質(zhì),Feldman等人創(chuàng)造性地提出了LP譯碼理論。其次討論了Feldman的LP譯碼算法,并針對二進(jìn)制線性分組碼設(shè)計了基于奇偶校驗多面體的LP譯碼算法。最后通過仿真實驗驗證該方法與Feldman LP譯碼算法性能相當(dāng)。2.本文針對多進(jìn)制線性分組碼譯碼展開了深入的研究。首先結(jié)合多進(jìn)制線性分組碼的校驗矩陣和Tanner圖表示形式闡述了置信傳播(Belief Propagation,BP)譯碼算法的流程。其次從最大似然(Maximum Likelihood,ML)譯碼算法出發(fā),詳細(xì)地介紹了Flanagan LP譯碼方法的原理及其數(shù)學(xué)優(yōu)化模型。通過分析發(fā)現(xiàn)Flanagan LP譯碼算法的復(fù)雜度隨著校驗矩陣行重呈指數(shù)增長,在工程中難于實現(xiàn),同時通過仿真實驗驗證了Flanagan LP譯碼模型復(fù)雜度過高這一問題。3.線性規(guī)劃多面體結(jié)構(gòu)的研究也是本文的一個重點。主要討論了描述多元奇偶校驗多面體的基本方法,并且構(gòu)造了一種新的2q元奇偶校驗多面體,同時給出了該多面體的幾種重要特性,最后對這些理論進(jìn)行分析并給予證明。4.本文主要討論了多進(jìn)制線性分組碼的LP譯碼問題,并提出了一種新的多進(jìn)制線性分組碼的多項式時間復(fù)雜度的LP譯碼算法。對于多進(jìn)制線性分組碼,我們采用奇偶校驗多面體將ML譯碼松弛為一種新的LP譯碼,該線性規(guī)劃模型只含有多項式復(fù)雜度的輔助變量和約束條件。最后不僅證明了,如果多進(jìn)制碼字的等價二進(jìn)制碼字能夠構(gòu)成基于GF(2)的子空間并且信道滿足對稱特性,本文提出LP譯碼算法就具有“ML特性”和“碼字獨立性”。同時,通過仿真實驗驗證了該LP譯碼算法不僅能很好地逼近ML譯碼算法,并能獲得與Flanagan LP譯碼算法相同的性能,而且在16QAM調(diào)制下其執(zhí)行效率比Flanagan LP譯碼算法高了近15倍。
[Abstract]:Since the error-correcting code theory was put forward more than 60 years ago, great achievements have been made in both theory and engineering application, among which Linear programming LP decoding is one of them. In this paper, a new LP decoding algorithm with polynomial time complexity is proposed. The theoretical and experimental results show that the method satisfies the requirements of "ML characteristics" and "codeword independence" under certain conditions. The results show that the algorithm is more efficient than LP decoding algorithm proposed by Flanagan. The main contents and research results are as follows: 1. This paper first introduces the basic concept of linear block code and its Tanner graph representation, and introduces the basic concept of linear programming. Since the optimal value of linear programming is always obtained at the vertex of polyhedron composed of feasible domains, Feldman and others creatively put forward LP decoding theory. Secondly, the LP decoding algorithm of Feldman is discussed, and the LP decoding algorithm based on parity check polyhedron is designed for binary linear block codes. Finally, the simulation results show that the performance of this method is equivalent to that of Feldman LP decoding algorithm. In this paper, the decoding of multiary linear block codes is studied. Firstly, the flow of Belief propagation BP decoding algorithm is described by combining the check matrix of multiary linear block codes and the representation of Tanner diagram. Secondly, the principle of Flanagan LP decoding method and its mathematical optimization model are introduced in detail from the Maximum LikelihoodML decoding algorithm. It is found that the complexity of the Flanagan LP decoding algorithm increases exponentially with the line repetition of the check matrix, and it is difficult to be implemented in engineering. At the same time, the problem of high complexity of the Flanagan LP decoding model is verified by simulation experiments. The study of linear programming polyhedron structure is also an important part of this paper. This paper mainly discusses the basic method of describing multivariate parity check polyhedron, constructs a new 2Q element parity check polyhedron, and gives several important properties of the polyhedron. At last, it analyzes these theories and proves them. In this paper, the problem of LP decoding for multiary linear block codes is discussed, and a new LP decoding algorithm with polynomial time complexity for multiary linear block codes is proposed. For multi-ary linear block codes, the parity-check polyhedron is used to relax ML decoding into a new LP decoding. The linear programming model contains only auxiliary variables and constraints of polynomial complexity. Finally, it is not only proved that if the equivalent binary codeword of the multiary codeword can form the subspace based on GF (2) and the channel satisfies the symmetry characteristic, the LP decoding algorithm has "ML characteristics" and "codeword independence". At the same time, the simulation results show that the LP decoding algorithm not only approximates ML decoding algorithm, but also achieves the same performance as Flanagan LP decoding algorithm, and its execution efficiency under 16QAM modulation is nearly 15 times higher than that of Flanagan LP decoding algorithm.
【學(xué)位授予單位】：西安電子科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：TN911.22

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 林楷,鄒盛唐,史治平,張雪竹;雙向監(jiān)督復(fù)轉(zhuǎn)碼的譯碼算法改進(jìn)[J];通信技術(shù);2003年04期

2 王冬梅;王秀芳;路敬yN;浦曉威;;LLR-BP算法的簡化譯碼算法研究[J];科學(xué)技術(shù)與工程;2010年12期

3 曹艷;王紅星;;基于維特比算法的VMSK/2譯碼方式研究[J];遙測遙控;2010年06期

4 唐元元;張德民;劉哲哲;李小文;;TD-LTE系統(tǒng)中軟輸出球形譯碼檢測算法研究[J];電子技術(shù)應(yīng)用;2012年11期

5 周曉邁,王新梅;用譯碼算法優(yōu)化一類{1,-1}~n上的二次函數(shù)[J];通信學(xué)報;1992年04期

6 劉光亮,胡正名;一種新的軟輸出譯碼算法[J];電子科學(xué)學(xué)刊;1998年04期

7 白玉潔;呂吉賀;白鳳山;;一種Nonbinary-Turbo-DFH方案及譯碼算法[J];通信技術(shù);2013年09期

8 岳珍梅;藺俊杰;杜少波;;一種改進(jìn)的球形譯碼算法性能分析[J];蘭州理工大學(xué)學(xué)報;2013年06期

9 龐臣;徐家品;;多進(jìn)制低密度奇偶校驗碼的擴(kuò)展最小和譯碼算法研究[J];微型機(jī)與應(yīng)用;2014年05期

10 付永慶,劉雅琴,杜海明;一種短時延的Turbo碼并行譯碼算法[J];信號處理;2004年04期

相關(guān)會議論文 前10條

1 肖海勇;畢光國;;聯(lián)合檢測的均衡譯碼算法[A];通信理論與信號處理新進(jìn)展——2005年通信理論與信號處理年會論文集[C];2005年

2 劉海濤;程型清;李道本;;低復(fù)雜度復(fù)球譯碼檢測算法[A];通信理論與信號處理新進(jìn)展——2005年通信理論與信號處理年會論文集[C];2005年

3 梁棟;李冬霞;;一種改進(jìn)的Turbo碼Log-MAP譯碼算法[A];2006通信理論與技術(shù)新進(jìn)展——第十一屆全國青年通信學(xué)術(shù)會議論文集[C];2006年

4 張穎;岳殿武;;幾何Goppa碼的譯碼[A];第一屆中國高校通信類院系學(xué)術(shù)研討會論文集[C];2007年

5 周朝霞;王大勇;;一種高速并行的Turbo碼譯碼算法[A];2007通信理論與技術(shù)新發(fā)展——第十二屆全國青年通信學(xué)術(shù)會議論文集（下冊）[C];2007年

6 童勝;王鵬;王單;王新梅;;LDPC碼量化和積譯碼的高效實現(xiàn)[A];現(xiàn)代通信理論與信號處理進(jìn)展——2003年通信理論與信號處理年會論文集[C];2003年

7 盧而輝;賴信q;謝德望;李肇嚴(yán);;可運用于線性區(qū)塊碼之新式軟式判定譯碼算法[A];2005年海峽兩岸三地?zé)o線科技學(xué)術(shù)會論文集[C];2005年

8 路成業(yè);孫蓉;王新梅;;Turbo碼幾種譯碼算法中的量化分析[A];開創(chuàng)新世紀(jì)的通信技術(shù)——第七屆全國青年通信學(xué)術(shù)會議論文集[C];2001年

9 朱敏;孟慶民;高西奇;;球形譯碼在MIMO-OFDM系統(tǒng)中的應(yīng)用[A];第九屆全國青年通信學(xué)術(shù)會議論文集[C];2004年

10 劉釗;李會勇;何子述;劉本永;;VBLAST的一種新的非線性譯碼算法[A];2006通信理論與技術(shù)新進(jìn)展——第十一屆全國青年通信學(xué)術(shù)會議論文集[C];2006年

相關(guān)博士學(xué)位論文 前10條

1 林偉;多元LDPC碼：設(shè)計、構(gòu)造與譯碼[D];西安電子科技大學(xué);2012年

2 崔俊云;LDPC碼的構(gòu)造及其譯碼算法研究[D];西安電子科技大學(xué);2012年

3 黃海藝;低密度奇偶校驗（LDPC）碼改進(jìn)譯碼算法研究[D];華南理工大學(xué);2013年

4 羅天放;通信系統(tǒng)中的Turbo碼及Turbo均衡問題研究[D];哈爾濱工程大學(xué);2003年

5 王單;LDPC碼編譯碼算法研究[D];西安電子科技大學(xué);2006年

6 陳曉剛;現(xiàn)代編碼的性能分析與簡化譯碼算法[D];北京郵電大學(xué);2010年

7 劉原華;LDPC碼的代數(shù)構(gòu)造及譯碼算法研究[D];西安電子科技大學(xué);2009年

8 胡樹楷;LDPC碼構(gòu)造及低復(fù)雜度譯碼算法研究[D];西安電子科技大學(xué);2012年

9 徐朝軍;RS碼譯碼算法及其實現(xiàn)的研究[D];西安電子科技大學(xué);2006年

10 趙傳鋼;LDPC碼及迭代接收系統(tǒng)研究[D];北京郵電大學(xué);2006年

，

本文編號：2144328