??? 摘? 要: 提出一種有效的計算級聯(lián)Z形碼最小距離的方法。該方法將多維的級聯(lián)Z形碼并行地分成兩個低維數(shù)的分量碼，其中有一個分量碼的維數(shù)固定為2，然后找出所有能在該二維分量碼中產(chǎn)生低于某個已知的最小距離上限的輸入序列，再驗證這些序列在整個碼中產(chǎn)生的距離，從而找出最小距離。從最后數(shù)字結(jié)果來看，使用普通的個人計算機，該方法能夠在111小時內(nèi)為碼率為1/2的級聯(lián)Z形碼找出最小距離20，而在38小時內(nèi)為碼率為1/3的級聯(lián)Z形碼找到最小距離26。?

??? 關(guān)鍵詞：? Z形碼； 最小距離； 環(huán)； 聯(lián)合界

?

??? 近來隨著迭代譯碼技術(shù)的發(fā)展，許多具有非常優(yōu)秀性能的碼相繼被發(fā)現(xiàn)^[1-2]。其中級聯(lián)Z形碼(Concatenated Zigzag Codes)就是一種非常優(yōu)異而且編譯碼都簡單的碼，參考文獻[3]中給出的一個碼的性能離香農(nóng)限僅0.9dB。?

??? 通常計算一個碼的最小距離是一件非常困難的事。參考文獻[3]中給出一種在一致交織器假設(shè)下計算級聯(lián)Z形碼的距離譜的算法。但該算法不適用于確定性交織器場合。錯誤脈沖法是非常有效的計算用迭代譯碼的碼的最小距離的方法，如turbo碼^[4]、LDPC碼^[5]，但其缺點是不能保證計算結(jié)果的正確性。在參考文獻[6]中，作者提出一種能夠計算turbo碼的真實最小距離的算法，參考文獻[7]改進該算法，以增大計算的距離。本文提出一種利用環(huán)搜索來計算級聯(lián)Z形碼最小距離的有效方法。?

1 級聯(lián)Z形碼?

1.1? Z形碼?

??? 圖1描述Z形碼的編碼過程。首先信息序列被分成I段，每一段由J個比特組成。然后每一段做奇偶校驗，產(chǎn)生一個奇偶比特，這個過程就是簡單奇偶校驗碼(SPC)編碼過程。然后這I個奇偶比特被送入一個只有兩個狀態(tài)的卷積編碼器，進行卷積運算。使用d(i,j)i=1,2,…,I, j=1,2,…,J,來代表信息矩陣，則奇偶序列p(i)i=1,2,…,I可以用如下的公式來產(chǎn)生：?

?????

?

?

1.2 級聯(lián)Z形碼?

??? 一個K維的級聯(lián)Z形碼由并行的K個Z形碼和K個交織器組成，見圖2。其稀疏奇偶校驗矩陣可以用如下式來表示：?

?????

?

?

??? 這里H^p是一個I×I的雙對角矩陣，O是一個I×I的全零矩陣，是一個I×IJ的稀疏矩陣, 該矩陣中“1” 的位置是由第i個交織器決定的。?

2? 一個有效的計算最小距離算法?

??? 為了方便，將該算法分成當級聯(lián)Z形碼維數(shù)為2維和大于2維的兩種情況。?

2.1? 二維級聯(lián)Z形碼?

??? 對于一個二維的級聯(lián)Z形碼，假設(shè)輸入重量為2w，根據(jù)Z形碼編碼原理，如圖3所示，按順序每兩個“1”之間(用虛線表示)在每一個分量碼中所跨過奇偶重量之和就是該輸入序列產(chǎn)生奇偶校驗總重量p。即:?

?????

??? 這時產(chǎn)生的碼字的總重量就是2w+p。值得注意的是，根據(jù)Z形碼的編碼規(guī)則，輸入重量為奇數(shù)的序列產(chǎn)生的奇偶校驗序列，相當于在輸入序列最后插入一個“1”，因而輸入重量為奇數(shù)的序列可以轉(zhuǎn)換為輸入重量為偶數(shù)的序列來考慮。另一方面，當級聯(lián)碼的維數(shù)只有2維時，圖中虛線和實線(代表交織關(guān)系)將沿著箭頭所指的方向形成一個閉環(huán)(圖3(a)），或多個閉環(huán)(圖3(b)）。?

?

?

??? 一個簡單的搜索單閉環(huán)的方法如圖3(a)所示。首先在第一個Z形碼中選擇一個起始點s₀⁰，然后再在這個分量碼中選另一個點s₁⁰，使得該點與s₀⁰之間的奇偶重量為一個確定的值p₀⁰，顯然如果p₀⁰不為零，滿足這個條件的點s₁⁰有2J種；而如果p₀⁰為零，就只有J-1種。然后s₁⁰被唯一地交織到另一個分量碼上一個位置s₀¹。然后再在這個分量碼中選一個點s₁¹，使得該點與s₀¹之間的奇偶重量為p₀¹。接著s₁¹又被唯一地逆交織到第一個分量碼中的一個新位置s₂⁰。這樣過程不斷進行下去直到最后一個點s₃¹被確定。如果最后s₃¹逆交織到第一個分量碼的點剛好是s₀⁰，則形成了一個閉環(huán)，該環(huán)中總的奇偶重量就為p。對于多環(huán)，如圖3(b)所示，可用同樣的方法得到每一個環(huán)，他們的總的奇偶重量就是p。?

??? 這樣計算最小距離的過程如下：?

??? 假設(shè)已知最小距離的一個上限為d^*。就要找出所有能夠滿足d^*≥2w+p的w和p，而對于每一個p，還要找出所有滿足(3)式的p_i^t，然后根據(jù)前面介紹的方法搜索單環(huán)和多環(huán)。?

??? 這樣就能找出所有能產(chǎn)生小于和等于d^*的輸入序列，因而就能找出最小距離d_m。值得注意的是，所有搜索到輸入序列產(chǎn)生的距離都是一個最小距離的上限，因而都可以作為d^*，所以如果起初不知道d^*，可以設(shè)一個很大的值，比如N，然后再在搜索過程中利用搜索到輸入序列中產(chǎn)生的最小距離作為d^*，使d^*不斷地逼進d_m。?

??? 下面分析尋找一個輸入重量為2w而奇偶重量為p的環(huán)所需要的計算量。?

2.2? 尋找一個環(huán)長為p的單環(huán)的復雜度分析?

??? 我們知道，給定一個值p，能滿足(3)式的p_i^t的數(shù)目共有:?

?????

??? 而對應(yīng)(3)式中，如果有λ(λ≤min(2w,p)個非零的p_i^t，則在N_p中，滿足這種情況的組合數(shù)為:?

?????

??? 而另一方面，對于每一個確定的p_i^t的分布，如果p_i^t中非零的數(shù)有λ個，這種情況下，搜索一個環(huán)的復雜度為(2J)^λ(J-1)2^w-λ。這樣當給定w和p后，對于每一個確定的起始點，搜索所有的單環(huán)復雜度為:?

?????

??? 從這個結(jié)果來看，該算法能夠非常有效地降低計算最小距離的復雜度。?

2.3? K-維級聯(lián)Z形碼(K>2)?

??? 當級聯(lián)Z形碼的維數(shù)K超過2時，將這K維碼分成兩個分量碼，其維數(shù)分別為2維和K-2維。為了方便討論，把2維的分量碼叫做基本分量碼，而把K-2維的分量碼稱為導出分量碼。其方法是先在基本分量碼中找出所有能產(chǎn)生距離小于或等于d^*的輸入序列，然后再檢查這些輸入序列在整個K維的級聯(lián)Z形碼產(chǎn)生的總距離，這樣即可找到所有能產(chǎn)生小于和等于d_m的輸入序列。?

??? 注意，如果計算時間不受約束，該算法一定能找出真實的最小距離和所有產(chǎn)生該最小距離的輸入序列；而如果計算時間有限，則該算法只能找到最小距離的一個上限d^*。?

3 數(shù)字結(jié)果?

??? 下面對三個碼來計算其真實最小距離。這三個碼的碼長分別為504、1 008和480，前兩個碼的碼率為1/2，最后一個碼率為1/3。最終計算出的最小距離被列在表1中。其中第一個碼的最小距離由輸入重量為4、12、14三種序列產(chǎn)生，第二個碼的最小距離由輸入重量16的序列產(chǎn)生，而第三個碼最小距離由輸入重量為4的序列產(chǎn)生的。表1還給出了找出每一個碼最小距離所需要的時間。所用的計算機為普通奔騰4個人計算機，主頻為2GHz。?

?

?

??? 圖4給出了這三個碼的BER性能仿真結(jié)果以及近似的聯(lián)合界結(jié)果。該仿真采用的譯碼器為參考文獻[8]中給出的APP算法，最大迭代次數(shù)為100。而近似聯(lián)合界計算由(8)式給出^[6]:?

?????

?

?

??? 其中R為碼率，E_b/N₀為每一個比特的信噪比。從圖4中可看出，隨著信噪比的增加，近似聯(lián)合界越來越接近仿真結(jié)果，它們都能很好地反映一個碼在高信噪比時的誤碼率性能。?

??? 本文提出一種有效的計算級聯(lián)Z形碼最小距離的方法。從其中的數(shù)字結(jié)果來看，使用普通的個人計算機，該方法能夠在111小時內(nèi)為碼率為1/2的級聯(lián)Z形碼找出最小距離20，而在38小時內(nèi)為碼率為1/3的級聯(lián)Z形碼找到最小距離26。最后利用最小距離來計算近似聯(lián)合界，通過與誤碼率的仿真結(jié)果對比，近似聯(lián)合界很好地反映了碼在高信噪比時的性能，從而為評估碼的性能提供一種有效的手段。?

參考文獻?

[1] BERROU C, GLAVIEUX A, THITIMAJSHIMA P. Near shannon limit error-correcting coding and decoding:?turbo codes [C]// Proc IEEE Int Conf Communications.Geneve, Switzerland: IEEE Press. 1993: 1064-1070.?

[2] MACKAY D J C, NEAL R M. Near shannon limit?performance of low density parity check codes [J]. IEE lectron Lett, 1996,32(18):1645-1646.?

[3]?LI P, HUANG X L, PHAMDO N. Zigzag codes and?concatenated zigzag codes[J]. IEEE Trans Inform Theory,?2001,47(2):800-807.?

[4] BERROU C, VATON S, JEZEQUEL M, et al. Computing the minimum distance of linear codes by the error?impulse method[C]// Proc IEEE Global Telecommunications Conference. Taipei, Taiwan: IEEE Press, 2002:1017-1020.?

[5] HU X Y, FOSSORIER M P C, EELFTHEROU E. On?the computation of the minimum distance of low-density?parity-check codes [C]// Proc. 2004 IEEE Int Conf??Communications. Paris, France: IEEE Press, 2004:?767-771.?

[6] GARELLO R, PIERLEONI P, BENEDETTO S. Computing?the free distance of turbo codes and serially concatenated codes with Interleavers: algorithms and applications[J]. IEEE Journal on Selected Areas in Communications, 2001,19(5):800-812.?

[7] Ould-Cheikh-Mouhamedou Y,CROZIER S, KABAL P.Efficient distance measurement method for turbo codes?that use structured interleavers[J]. IEEE Commun. Lett,2006,10(6):477-479.?

[8] LI P. Modified turbo codes with low decoding complexity[J].IEE Electron. Lett., 1998,34(23):2228-2229.