多進(jìn)制線性分組碼的線性規(guī)劃譯碼算法研究.pdf

1、糾錯(cuò)碼理論理論提出60多年來，在理論和工程應(yīng)用中均取得了豐碩的成果，線性規(guī)劃(Linear Programming，LP)譯碼就是其中之一。本文提出了一種新的多項(xiàng)式時(shí)間復(fù)雜度的LP譯碼算法，通過理論及實(shí)驗(yàn)仿真驗(yàn)證了該方法在一定條件下滿足“ML特性”和“碼字獨(dú)立性”，同時(shí)結(jié)果表明該算法比Flanagan提出的LP譯碼算法執(zhí)行效率更高。主要內(nèi)容和研究成果如下：
　　1.首先介紹了線性分組碼的基本概念及其Tanner圖表示形式，并引入了

2、線性規(guī)劃的基本概念。由于線性規(guī)劃最優(yōu)值總在可行域組成的多面體頂點(diǎn)處取得，結(jié)合這個(gè)性質(zhì)，F(xiàn)eldman等人創(chuàng)造性地提出了LP譯碼理論。其次討論了Feldman的LP譯碼算法，并針對(duì)二進(jìn)制線性分組碼設(shè)計(jì)了基于奇偶校驗(yàn)多面體的 LP譯碼算法。最后通過仿真實(shí)驗(yàn)驗(yàn)證該方法與Feldman LP譯碼算法性能相當(dāng)。
　　2.本文針對(duì)多進(jìn)制線性分組碼譯碼展開了深入的研究。首先結(jié)合多進(jìn)制線性分組碼的校驗(yàn)矩陣和Tanner圖表示形式闡述了置信傳播(B

3、elief Propagation，BP)譯碼算法的流程。其次從最大似然(Maximum Likelihood，ML)譯碼算法出發(fā)，詳細(xì)地介紹了 Flanagan LP譯碼方法的原理及其數(shù)學(xué)優(yōu)化模型。通過分析發(fā)現(xiàn)Flanagan LP譯碼算法的復(fù)雜度隨著校驗(yàn)矩陣行重呈指數(shù)增長，在工程中難于實(shí)現(xiàn)，同時(shí)通過仿真實(shí)驗(yàn)驗(yàn)證了Flanagan LP譯碼模型復(fù)雜度過高這一問題。
　　3.線性規(guī)劃多面體結(jié)構(gòu)的研究也是本文的一個(gè)重點(diǎn)。主要討論了描

4、述多元奇偶校驗(yàn)多面體的基本方法，并且構(gòu)造了一種新的2q元奇偶校驗(yàn)多面體，同時(shí)給出了該多面體的幾種重要特性，最后對(duì)這些理論進(jìn)行分析并給予證明。
　　4.本文主要討論了多進(jìn)制線性分組碼的 LP譯碼問題，并提出了一種新的多進(jìn)制線性分組碼的多項(xiàng)式時(shí)間復(fù)雜度的LP譯碼算法。對(duì)于多進(jìn)制線性分組碼，我們采用奇偶校驗(yàn)多面體將ML譯碼松弛為一種新的LP譯碼，該線性規(guī)劃模型只含有多項(xiàng)式復(fù)雜度的輔助變量和約束條件。最后不僅證明了，如果多進(jìn)制碼字的等價(jià)二