??? 摘? 要: 提出一種有效的計算級聯Z形碼最小距離的方法。該方法將多維的級聯Z形碼并行地分成兩個低維數的分量碼，其中有一個分量碼的維數固定為2，然后找出所有能在該二維分量碼中產生低于某個已知的最小距離上限的輸入序列，再驗證這些序列在整個碼中產生的距離，從而找出最小距離。從最后數字結果來看，使用普通的個人計算機，該方法能夠在111小時內為碼率為1/2的級聯Z形碼找出最小距離20，而在38小時內為碼率為1/3的級聯Z形碼找到最小距離26。?
??? 關鍵詞：? Z形碼； 最小距離； 環； 聯合界
?
??? 近來隨著迭代譯碼技術的發展，許多具有非常優秀性能的碼相繼被發現[1-2]。其中級聯Z形碼(Concatenated Zigzag Codes)就是一種非常優異而且編譯碼都簡單的碼，參考文獻[3]中給出的一個碼的性能離香農限僅0.9dB。?
??? 通常計算一個碼的最小距離是一件非常困難的事。參考文獻[3]中給出一種在一致交織器假設下計算級聯Z形碼的距離譜的算法。但該算法不適用于確定性交織器場合。錯誤脈沖法是非常有效的計算用迭代譯碼的碼的最小距離的方法，如turbo碼[4]、LDPC碼[5]，但其缺點是不能保證計算結果的正確性。在參考文獻[6]中，作者提出一種能夠計算turbo碼的真實最小距離的算法，參考文獻[7]改進該算法，以增大計算的距離。本文提出一種利用環搜索來計算級聯Z形碼最小距離的有效方法。?
1 級聯Z形碼?
1.1? Z形碼?
??? 圖1描述Z形碼的編碼過程。首先信息序列被分成I段，每一段由J個比特組成。然后每一段做奇偶校驗，產生一個奇偶比特，這個過程就是簡單奇偶校驗碼(SPC)編碼過程。然后這I個奇偶比特被送入一個只有兩個狀態的卷積編碼器，進行卷積運算。使用d(i,j)i=1,2,…,I, j=1,2,…,J,來代表信息矩陣，則奇偶序列p(i)i=1,2,…,I可以用如下的公式來產生：?
????
?
?
?
1.2 級聯Z形碼?
??? 一個K維的級聯Z形碼由并行的K個Z形碼和K個交織器組成，見圖2。其稀疏奇偶校驗矩陣可以用如下式來表示：?
????
?
?
?
??? 這里Hp是一個I×I的雙對角矩陣，O是一個I×I的全零矩陣，
是一個I×IJ的稀疏矩陣, 該矩陣中“1” 的位置是由第i個交織器決定的。?
2? 一個有效的計算最小距離算法?
??? 為了方便，將該算法分成當級聯Z形碼維數為2維和大于2維的兩種情況。?
2.1? 二維級聯Z形碼?
??? 對于一個二維的級聯Z形碼，假設輸入重量為2w，根據Z形碼編碼原理，如圖3所示，按順序每兩個“1”之間(用虛線表示)在每一個分量碼中所跨過奇偶重量之和就是該輸入序列產生奇偶校驗總重量p。即:?
????
?
??? 這時產生的碼字的總重量就是2w+p。值得注意的是，根據Z形碼的編碼規則，輸入重量為奇數的序列產生的奇偶校驗序列，相當于在輸入序列最后插入一個“1”，因而輸入重量為奇數的序列可以轉換為輸入重量為偶數的序列來考慮。另一方面，當級聯碼的維數只有2維時，圖中虛線和實線(代表交織關系)將沿著箭頭所指的方向形成一個閉環(圖3(a)），或多個閉環(圖3(b)）。?
?
?
??? 一個簡單的搜索單閉環的方法如圖3(a)所示。首先在第一個Z形碼中選擇一個起始點s00，然后再在這個分量碼中選另一個點s10，使得該點與s00之間的奇偶重量為一個確定的值p00，顯然如果p00不為零，滿足這個條件的點s10有2J種；而如果p00為零，就只有J-1種。然后s10被唯一地交織到另一個分量碼上一個位置s01。然后再在這個分量碼中選一個點s11，使得該點與s01之間的奇偶重量為p01。接著s11又被唯一地逆交織到第一個分量碼中的一個新位置s20。這樣過程不斷進行下去直到最后一個點s31被確定。如果最后s31逆交織到第一個分量碼的點剛好是s00，則形成了一個閉環，該環中總的奇偶重量就為p。對于多環，如圖3(b)所示，可用同樣的方法得到每一個環，他們的總的奇偶重量就是p。?
??? 這樣計算最小距離的過程如下：?
??? 假設已知最小距離的一個上限為d*。就要找出所有能夠滿足d*≥2w+p的w和p，而對于每一個p，還要找出所有滿足(3)式的pit，然后根據前面介紹的方法搜索單環和多環。?
??? 這樣就能找出所有能產生小于和等于d*的輸入序列，因而就能找出最小距離dm。值得注意的是，所有搜索到輸入序列產生的距離都是一個最小距離的上限，因而都可以作為d*，所以如果起初不知道d*，可以設一個很大的值，比如N，然后再在搜索過程中利用搜索到輸入序列中產生的最小距離作為d*，使d*不斷地逼進dm。?
??? 下面分析尋找一個輸入重量為2w而奇偶重量為p的環所需要的計算量。?
2.2? 尋找一個環長為p的單環的復雜度分析?
??? 我們知道，給定一個值p，能滿足(3)式的pit的數目共有:?
????
?
??? 
而對應(3)式中，如果有λ(λ≤min(2w,p)個非零的pit，則在Np中，滿足這種情況的組合數為:?
????
?
??? 而另一方面，對于每一個確定的pit的分布，如果pit中非零的數有λ個，這種情況下，搜索一個環的復雜度為(2J)λ(J-1)2w-λ。這樣當給定w和p后，對于每一個確定的起始點，搜索所有的單環復雜度為:?
????
?
??? 從這個結果來看，該算法能夠非常有效地降低計算最小距離的復雜度。?
2.3? K-維級聯Z形碼(K>2)?
??? 當級聯Z形碼的維數K超過2時，將這K維碼分成兩個分量碼，其維數分別為2維和K-2維。為了方便討論，把2維的分量碼叫做基本分量碼，而把K-2維的分量碼稱為導出分量碼。其方法是先在基本分量碼中找出所有能產生距離小于或等于d*的輸入序列，然后再檢查這些輸入序列在整個K維的級聯Z形碼產生的總距離，這樣即可找到所有能產生小于和等于dm的輸入序列。?
??? 注意，如果計算時間不受約束，該算法一定能找出真實的最小距離和所有產生該最小距離的輸入序列；而如果計算時間有限，則該算法只能找到最小距離的一個上限d*。?
3 數字結果?
??? 下面對三個碼來計算其真實最小距離。這三個碼的碼長分別為504、1 008和480，前兩個碼的碼率為1/2，最后一個碼率為1/3。最終計算出的最小距離被列在表1中。其中第一個碼的最小距離由輸入重量為4、12、14三種序列產生，第二個碼的最小距離由輸入重量16的序列產生，而第三個碼最小距離由輸入重量為4的序列產生的。表1還給出了找出每一個碼最小距離所需要的時間。所用的計算機為普通奔騰4個人計算機，主頻為2GHz。?
?
?
??? 圖4給出了這三個碼的BER性能仿真結果以及近似的聯合界結果。該仿真采用的譯碼器為參考文獻[8]中給出的APP算法，最大迭代次數為100。而近似聯合界計算由(8)式給出[6]:?
????
?
?
?
??? 其中R為碼率，Eb/N0為每一個比特的信噪比。從圖4中可看出，隨著信噪比的增加，近似聯合界越來越接近仿真結果，它們都能很好地反映一個碼在高信噪比時的誤碼率性能。?
??? 本文提出一種有效的計算級聯Z形碼最小距離的方法。從其中的數字結果來看，使用普通的個人計算機，該方法能夠在111小時內為碼率為1/2的級聯Z形碼找出最小距離20，而在38小時內為碼率為1/3的級聯Z形碼找到最小距離26。最后利用最小距離來計算近似聯合界，通過與誤碼率的仿真結果對比，近似聯合界很好地反映了碼在高信噪比時的性能，從而為評估碼的性能提供一種有效的手段。?
參考文獻?
[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.