許大山臺灣大學：電信工程學研究所吳宇鵬Wu, Yu-PengYu-PengWu2007-11-272018-07-052007-11-272018-07-052007http://ntur.lib.ntu.edu.tw//handle/246246/58702自從1948年Shannon發表一篇卓越的論文後 [13]，大量的研究便不斷投注在如何構建好的碼和發展相對應的解碼演算法上面。直到現在，很多好的碼和相對應的解碼演算法已經被提出來。對於短的碼長而言 (數百或更少個位元)，一些針對特定長度好的碼已經被發現，例如格雷 (Golay)碼。對於長的碼長而言 (數千或更多個位元)，渦輪 (turbo)碼和低密度位元檢查 (LDPC)碼也展現出它們卓越的更錯能力。但是對於短的碼長而言，還沒有一個效能好且碼長是可調的碼和相對應實際的解碼方法被提出來 (渦輪碼和低密度位元檢查碼在此碼長下效能不好)。基於以上的原因，我們的目標就擺在找一個效能好且碼長是可調的短長度碼和相對應實際的解碼方法。 在本篇論文中，我們提出一個方法去找一個連結碼 (concatenated code)的家族。這個連結碼家族是由循環檢測碼 (CRC) 和摺積碼 (convolutional code)所組成的。這方法是以“摺積碼輸入端空間的分解”和“否定輸入”這兩個概念為基礎所構成。這種連結碼具有非常簡單的編碼方式。另外在這種連結碼的架構下，我們也去搜尋最好的碼 (從擁有最大的最小距離觀點)在某些給定的條件下。我們的結果顯示我們設計的連結碼 (接近碼率0.4)最大概似解碼效能可以接近球體裝填極限效能從0.55 dB 到 0.75 dB 對於碼長從272位元到528位元而言 (對於封包錯誤率為10^-4狀況下)。 此外，我們也針對文中的連結碼提出兩個解碼器，“循環檢測碼錯誤更正跟隨列舉維特比演算法解碼器”和“循環檢測碼限制嵌入列舉維特比演算法解碼器”。這兩個解碼器利用了循環檢測碼的錯誤更正能力而不是錯誤偵測能力和列舉解碼的概念。根據我們的模擬結果顯示，“循環檢測碼限制嵌入列舉維特比演算法解碼器”對於接近碼率0.4的碼在碼長度最大到528位元時皆可以達到最佳的解碼效果。這是到目前為止對於碼長度從200到500位元這區間最好的解碼效能報告。 關鍵詞 ─ 連結碼、循環檢測碼、摺積碼、摺積碼輸入端空間的分解、否定輸入、循環檢測碼錯誤更正跟隨列舉維特比演算法解碼器、循環檢測碼限制嵌入列舉維特比演算法解碼器After the publication of Shannon's paper in 1948 [13], a large amount of research was led to the construction of specific codes with good error-correcting capabilities and development of efficient decoding algorithms for these codes. Until now, many good codes and corresponding decoding algorithms have been proposed. For short or very short codeword lengths (hundreds of or less bits), several good codes (for example, the Golay code) for specific block size have been found. For moderate or large codeword lengths (thousands of or more bits), turbo code and low density parity check (LDPC) code also show their excellent error correcting capability. But for short or very short codeword lengths, there are no adjustable block sizes and high performance short codes with practical decoding (turbo or LDPC codes don't perform well in this codeword lengths). Based on this reason, we aim to discover alternative high performance short codes with practical decoding and adjustable block sizes. In this thesis, we provide a method, based on concepts of "decomposition of the input error space of convolutional code" and "denial of input", to find a family of good codes consisted of concatenated Cyclic redundancy code (CRC) and convolutional code. This concatenated code own very simple encoding form. On the framework of this concatenated code, we also search the best code (from the viewpoint of having the largest minimal distance) on some given conditions. Our result indicates that maximum likelihood (ML) decoding performance of this concatenated code with close to rate-0.4 can achieve near-SPB performance for codeword lengths ranging from 272 bits to 528 bits with 0.55 dB to 0.75 dB for a word error probability of 10^-4. Furthermore, we also propose two decoders, "LVA followed by CRC correction decoder" and "LVA with built-in CRC constraint decoder", for this concatenated code. The decoders take advantage of the error correction capability rather than the error detection capability of CRC and the concept of list decoding. Under our result, it shows that "LVA with built-in CRC constraint decoder" can achieve optimal decoding of close to rate-0.4 codes of lengths up to 528 bits. This is the best reported decoding performance so far for codeword lengths from 200 to 500 bits. Keywords ─ concatenated code, CRC, convolutional code, decomposition of the input error space of convolutional code, denial of input, LVA followed by CRC correction decoder, LVA with built-in CRC constraint decoder1 Introduction 1 2 Background 5 2.1 Sphere packing bound(SPB) . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Cyclic redundancy codes (CRCs) . . . . . . . . . . . . . . . . . . . . 7 2.3 Convolutional code . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 Construction of Concatenated CRC and Convolutional Codes 11 3.1 Decomposition of the input error space of convolutional code . . . . . 11 3.2 Concept of "denial of input" . . . . . . . . . . . . . . . . . . . . . . . 13 3.3 Construction of concatenated CRC and convolutional codes . . . . . . 14 3.3.1 "2dfree" case . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.3.2 "3dfree" case . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.3.3 Analysis of coding gain . . . . . . . . . . . . . . . . . . . . . . 18 4 Results for ML Decoding Performance of Our Designed Codes 20 4.1 Number of "terminated errorlets" for the specific convolutional codes 20 4.2 Results for parameters of CRCs based on the specific convolutional codes 22 4.3 Results for ML decoding performance of our designed codes . . . . . 25 4.4 Optimization pays . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5 Decoding of Concatenated CRC and Convolutional Codes 32 5.1 Interpretation of "LVA followed by CRC correction decoder" . . . . . 33 5.2 Interpretation of "LVA with built-in CRC constraint decoder" . . . . 34 5.3 Performance comparison among three decoding schemes . . . . . . . . 39 6 Conclusions 43 Bibliography 45404751 bytesapplication/pdfen-US連結碼循環檢測碼摺積碼摺積碼輸入端空間的分解否定輸入循環檢測碼錯誤更正跟隨列舉維特比演算法解碼器循環檢測碼限制嵌入列舉維特比演算法解碼器concatenated codeCRCconvolutional codedecomposition of the input error space of convolutional codedenial of inputLVA followed by CRC correction decoderLVA with built-in CRC constraint decoderthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/58702/1/ntu-96-R94942095-1.pdf