Chase-型譯碼算法搜索中心的選取方法的研究.pdf

1、本文主要研究采用BPSK信號(hào)的加性高斯白噪聲信道(AWGN)上的二元線性分組碼的軟判決譯碼算法。雖然最大似然譯碼算法使得譯碼的錯(cuò)誤概率最小，但是對(duì)于長(zhǎng)碼而言最大似然譯碼算法的計(jì)算復(fù)雜度太高。因此，文獻(xiàn)中有許多次最優(yōu)軟判決譯碼算法被提出，它們?cè)诩m錯(cuò)能力和譯碼復(fù)雜度之間達(dá)成折中，這對(duì)于理論研究和實(shí)際應(yīng)用都有很大的意義。
　　基于可靠性順序的譯碼算法(ROBDA)是目前廣泛應(yīng)用于各種實(shí)際通信系統(tǒng)的一種次最優(yōu)軟判決譯碼算法，當(dāng)它達(dá)到限界距

2、離(bounded-distance，BD)譯碼時(shí)，還是漸近最優(yōu)的。作為ROBDA的一種特例的Chase型譯碼算法在由代數(shù)譯碼器圍繞一些給定的搜索中心生成的一系列候選碼字中輸出一個(gè)最好的碼字作為輸出的譯碼算法，是Chase在[1]中提出的一類(lèi)迭代軟判決譯碼方法的推廣。Chase在[1]中提出的譯碼算法有三個(gè)，它們都是BD譯碼算法，搜索中心的個(gè)數(shù)分別是（Nd/2），2[d/2]和[d/2]+1，其中Chase-3算法的搜索中心的非零分量都

3、集中在可靠性較低的那些位置，N和d分別為碼長(zhǎng)和最小漢明距離。因?yàn)镃hase型譯碼算法的計(jì)算復(fù)雜性大致與搜索中心的個(gè)數(shù)成正比，設(shè)計(jì)以盡可能少的搜索中心達(dá)到BD譯碼的Chase型譯碼算法得到了很多編碼理論學(xué)者的關(guān)注。若設(shè)Δ(d)表示Chase-3型譯碼算法達(dá)到BD譯碼時(shí)搜索中心的最小數(shù)目。2003年，在[2]和[3]中分別證明了，Δ(d)≤[(d+2)/4]和Δ(d)≤[d/6]+1。當(dāng)漢明距離d趨近于無(wú)窮時(shí)，在[4]，[5]，[6]中則分

4、別得到了漸近上界Δ(d)≤O(d2/3)，Δ(d)≤O（d1/2+ε)），Δ(d)≤0(d√dlnd)。在[7]中，關(guān)于Δ(d)的漸近上界又進(jìn)一步改進(jìn)為:Δ(d)≤(ψ+o(1))d1/2，ψ≈2.414。
　　在本學(xué)位論文中，我們發(fā)現(xiàn)如果在Chase-3型譯碼算法原來(lái)的搜索中心中再添加一些其他類(lèi)型的向量，則可以用更少的搜索中心達(dá)到BD譯碼。我們證明了在Chase-3型譯碼算法中添加5個(gè)其他類(lèi)型的向量時(shí)可以用不超過(guò)(μ+ o(1)