應用疊代式複數步驟多數決解碼之循環碼研究

Abstract

本論文重點在研究複數步驟多數決循環碼之解碼，發展高效能的演算法及降低儲存需求。在演算法的部分，我們提出的演算法都具有部份平行解碼(partial parallel decoding)的特性。過去研究複數步驟多數決循環碼的解碼，僅能使用序列式解(serial decoding)或是全平行解碼(fully parallel decoding)。若考慮硬體實作，序列式解碼速度慢但硬體複雜度低; 全平行式解碼速度快但硬體複雜度高。部份平行解碼能在解碼速度及硬體複雜度間取得平衡。在我們探討的解碼演算法中，針對三步驟多數決循環碼，我們提出了對應的疊代式三步驟總和乘積演算法(iterative three-step sum-product algorithm)；針對非二進位兩步驟多數決循環碼，我們提出了疊代式兩步驟擴展式最小值總合演算法(iterative two-step extended min-sum algorithm)；並且，我們將疊代式可靠度多數決演算法(iterative reliability majority-logic decoding)應用到兩步驟多數決循環碼，探討二進位及非二進位的循環碼解碼。另一方面，本篇論文探討的循環碼皆建構在有限幾何中(finite geometry)，此類循環碼其奇偶檢查矩陣(parity-check matrix)具有正交的特性。在過去的文獻中，複數步驟循環碼解碼尚未有使用正交特性做奇偶檢查矩陣分解(parity-check matrix decomposition)。我們利用複數步驟多數決循環碼奇偶檢查矩陣具有正交的特性，分解成兩個以上的奇偶檢查矩陣；這些被分解過後的矩陣具有循環(cyclic)或是半循環(quasi-cyclic)結構的特性，因而大幅減少奇偶檢查矩陣資訊儲存的需求。 我們將總和乘積演算法應用到三步驟多數決循環碼。先前的文獻，僅有兩步驟多數決循環碼解碼的研究，但該研究無法解碼三步驟多數決循環碼。在本論文中，我們發現三步驟多數決循環碼的奇偶檢查矩陣可以利用其正交特性分解成三個具有循環及半循環特性的子矩陣(sub-matrix)；我們所提出的疊代式三步驟總和乘積演算法便能操作在這三個子矩陣完成運算。 對於二進位兩步驟多數決循環碼，我們提出了加權式疊代可靠度多數決演算法。在過去的研究中，對於二進位兩步驟多數決循環碼的解碼，僅有疊代式兩步驟總和乘積演算法(iterative two-step sum-product algorithm)及疊代式兩步驟最小值總和演算法(iterative min-sum algorithm)被討論過。上述兩演算法因為使用了實數的運算，因此運算複雜度過高。為了降低兩步驟多數決循環碼演算法的運算複雜度，我們提出的加權疊代式兩步驟可靠度多數決演算法，僅使用整數及二進位運算，並且進一步利用在解碼過程中第二層產生的軟資訊 (soft information)當作第一層解碼資訊的權重，模擬結果顯示將軟資訊加入解碼的過程有效的改善疊代式可靠度多數決演算法的效能。另外，與過去使用實數運算的演算法相比，大幅降低了運算複雜度。 針對非二進位兩步驟多數決循環碼，我們提出了兩種解碼演算法分別是疊代式兩步驟擴展式最小值總和演算法(iterative two-step extended min-sum algorithm)和疊代式可靠度兩步驟多數決演算法(iterative reliability two-step majority logic decoding algorithm)。非二進位兩步驟多數決循環碼在文獻中尚未被討論過；此外，兩步驟多數決循環碼中有很多短迴圈長度為4(short cycles of length 4)，在過去的研究中短迴圈將會使得大部份低密度奇偶檢查碼(Low-Density Parity-Check code)的碼字不容易收斂(converge)。然而，建構在有限幾何的複數步驟循環碼其奇偶檢查矩陣具有正交結構的特性，以及大量的冗餘檢查和(redundant check-sum)，若搭配合適的演算法解碼，仍有可能達到良好的解碼效能。本研究利用複數步驟多數決循環碼在有限幾何中正交的性質，設計出兩種演算法，分別具有高效能及低複雜度的特性，皆可減少短迴圈對於降低該循環碼解碼效能的影響。 整體而言，本文著重於複數步多數決循環碼的疊代式解碼研究，並且利用建構在有限幾何的複數步驟循環碼其奇偶檢查矩陣具有正交結構的特性，分解矩陣成數個子矩陣，大幅減少儲存的需求，同時也達成部份平行演算的目的，能在解碼速度及硬體複雜度間取得平衡。我們以程式語言在加成性白高斯雜訊(additive white Gaussian noise)的通道環境下模擬。對於三步驟多數決循環碼，我們所提出的疊代式三步驟總和乘積演算法，與BCH代數碼的硬資訊解碼相比最多可達到1.9 dB的編碼增益(coding gain)；在儲存需求的部份，使用奇偶矩陣的分解跟原始矩陣相比，僅需要2/n的儲存量(其中n為碼字長度)。對於二進位兩步驟多數決循環碼，使用我們提出的加權式疊代可靠度多數決演算法，利用整數及二進位運算替換了原本實數加法的運算，與BCH代數碼的硬資訊解碼相比最多可達到1.2 dB的編碼增益。對於非二進位兩步驟多數決循環碼，我們提出的疊代式兩步驟擴展式最小值總和演算法，與理德索羅門代數碼使用代數軟資訊解碼相比最多可以達到2.5 dB的編碼增益。若以計算複雜度為考量，我們所提出的疊代式可靠度兩步驟多數決演算法跟疊代式兩步驟擴展式最小值總和演算法相比，最多可以減少99%的運算複雜度而僅有0.5 dB的編碼損耗。

This dissertation presents efficient iterative decoding algorithms and a parity-check decomposition scheme for multi-step majority-logic decodable cyclic codes. These codes are constructed based on finite geometries. The orthogonal structure of the parity-check matrices of the codes leads to the development of a decomposition scheme. The decomposition breaks the parity-check matrices of the codes into several submatrices, which allows the development of partial parallel decoding. The proposed iterative partial parallel decoding algorithms strike a reasonable balance between decoding speed and storage requirement. An iterative multi-step decoding algorithm is proposed for a class of multi-step majority-logic (MS-MLG) decodable cyclic codes. The proposed algorithm is capable of efficient decoding the MS-MLG decodable cyclic codes with large number of short cycles of length 4. In addition, we decompose the parity-check matrices into several submatrices by utilizing the orthogonal structure of the codes. Simulation results demonstrate that the MS-MLG decodable cyclic codes decoded with the proposed algorithm achieve as much as 1.9 dB coding gain over BCH codes with similar lengths and rates decoded with the hard-decision algorithm. An iterative weighted reliability two-step majority logic decoding (IWRTS-MLGD) algorithm for two-step majority-logic (TS-MLG)-decodable cyclic codes is presented. In contrast to other message passing decoding algorithms that utilize real number operations, our proposed decoding algorithm requires only logical operations and integer additions. Therefore, large computational complexities can be reduced. For moderate-length TS-MLG-decodable cyclic codes, the proposed algorithm aided with soft information and a scaling factor outperforms the hard-decision TS-MLGD algorithm and hard-decision BCH codes with similar length by 1.2 and 1.0 dB, respectively. Two iterative decoding algorithms are proposed for a class of non-binary two-step majority-logic (NB-TS-MLG) decodable cyclic codes. A partial parallel decoding scheme is also introduced to provide a balanced trade-off between decoding speed and storage requirements. Unlike non-binary one-step MLG decodable cyclic codes, the Tanner graphs of which are 4-cycle-free, NB-TS-MLG decodable cyclic codes contain a large number of short cycles of length 4, which tend to degrade decoding performance. The proposed algorithms utilize the orthogonal structure of the parity-check matrices of the codes to resolve the degrading effects of the short cycles of length 4. Simulation results demonstrate that the NB-TS-MLG decodable cyclic codes decoded with the proposed algorithms offer coding gains as much as 2.5 dB over Reed-Solomon codes of the same lengths and rates decoded with either hard-decision or algebraic soft decision decoding.