臺灣博碩士論文加值系統

本論文主要是研究如何將第二代數位電視解碼系統之演算法，目的是在降低位元錯誤率(Bit error rate)。其整體系統包括外編碼BCH(Bose, Chaudhuri, and Hocquenghem)碼，目的是為了要對抗突發性的位元錯誤、內編碼LDPC(low-density parity-check)碼，目的是為了要增加編碼增益、位元交錯(bit interleaver)，目的是要打散其資料位元，以避免資料產生連續性的錯誤、經過瑞雷通道(Rayleigh channel)，到接收端的部分分別為用解列扭交錯(column twist deinterleaver)與解奇偶交錯(parity deinterleaver)的方式來做解位元交錯器(bit deinterleaver)、內解碼的部分則是使用最小和積演算法(Min-Sum Algorithm)降低接收端所產生的迭代與錯誤率、外解碼的部分則是使用Berlekamp-Massey演算法尋找錯誤位址方程式，最後再使用秦式搜尋(Chien Search)加快找出錯誤位址。
經由模擬的結果顯示，在Nc(Number of column)分別為8、12跟16的規範中與各種碼率分別為1/2、3/5、2/3、3/4、4/5、5/6，在迭代次數減少後，也能降低錯誤率，增加其編碼增益。

The major goal of this thesis is to reduce the number of iterations required by the algorithm in DVB-T2 decoding systems. The overall system is composed of several parts: the outer BCH (Bose, Chaudhuri, and Hocquenghem) code, which can be used for overcoming bursty errors; the inner LDPC (low-density parity-check) code, whose purpose is to increase coding gains; the bit interleaver, which scrambles data bits so that the original message will not suffer too much on bursty channels. After message signals are transmitted through Rayleigh channels, received bits are deinterleaved by using a column twist deinterleaver followed by a parity deinterleaver. Min-Sum Algorithm is used in the inner decoder, which can effectively reduce number of iterations and error rates. Berlekamp-Massey algorithm is then applied in the outer decoder to construct the error location equation. Finally, Chien Search algorithm is used to efficiently locate the locations of errors.
Simulation results show that, under all of the specifications for the numbers of column Nc being 8, 12, and 16, and for various code rates (i.e, 1/2, 3/5, 2/3, 3/4, 4/5 and 5/6), the error performance and coding gains can be effectively improved even when the iteration numbers are reduced.

中文摘要……………………………………………………………………………i
英文摘要……………………………………………………………………………ii
誌謝…………………………………………………………………………………iii
目錄…………………………………………………………………………………iv
表目錄………………………………………………………………………………vi
圖目錄………………………………………………………………………………vii
第一章、 緒論……………………………………………………………… 1
1.1 前言………………………………………………………………………1
1.2 論文目的…………………………………………………………………1
1.3研究方法與內容………………………………………………………… 2
第二章、DVB-T2通道編碼系統………………………………………………3
2.1外部編碼BCH encoding………………………………………………… 5
2.1.1 BCH code的簡介………………………………………………………5
2.1.2 BCH code編碼…………………………………………………………6
2.2內編碼LDPC encoding……………………………………………………9
2.2.1低密度奇偶校驗碼 (LDPC) 之概述………………………………… 9
2.2.2低密度奇偶校驗碼之結構…………………………………………… 9
2.2.3內編碼的過程………………………………………………………… 9
2.3 位元交錯(Bit interleaver)…………………………………………12
2.4通道………………………………………………………………………15
2.4.1路徑損失………………………………………………………………17
2.4.2遮蔽效應………………………………………………………………17
2.4.3 多重路徑衰減……………………………………………………… 17
2.4.4行動通訊系統之瑞雷衰退效應………………………………………18
第三章、DVB-T2通道解碼系統…………………………………………… 19
3.1解碼系統之簡介…………………………………………………………19
3.2解位元交錯器(bit deinterleaver) …………………………………19
3.3內解碼(LDPC decoder) ……………………………………………… 24
3.3.1 Tanner Graph……………………………………………………… 24
3.3.2 對數領域的和積演算法(Log-SPA(Sum-Product Algorithm))… 25
3.3.3最小和積演算法(Min-Sum Algorithm, MSA)………………………29
3.3.4 修正最小和積演算法(Modified MSA) ……………………………29
3.4 外解碼 (Outer decoder)…………………………………………… 31
3.4.1 徵狀值計算………………………………………………………… 31
3.4.2尋找錯誤位置多項式 Berlekamp-Massey algorithm…………… 32
3.4.3 尋找錯誤位置電路— Chien Search………………………………35
第四章、DVB-T2通道解碼模擬…………………………………………… 36
4.1模擬………………………………………………………………………36
4.2模擬分析…………………………………………………………………55
4.2.1碼率……………………………………………………………………55
4.2.2格雷映射………………………………………………………………55
4.2.3模擬後發現的缺點……………………………………………………56
第五章 結論與未來展望……………………………………………………57
參考文獻…………………………………………………………………… 58
附錄………………………………………………………………………… 60

[1]DVB Document A122, 2008,Frame structure channel coding and modulation for a second generation digital terrestrial television broadcasting system (DVB-T2), June
[2]2008，社團法人台灣數位電視協會制訂”第二代地面數位電視接收機技術需求”技術規範
[3]Simon Haykin，2001年，通訊系統(communication systems)，第四版，翁萬德、江松茶，全華科技圖書股份有限公司 印行。第5.3、8.6~8.7節， 09月16日。
[4]Shu Lin, Daniel J. Costello.,1983,Error control coding fundamentals and applications, (Prentice-Hall Computer Applications in Electrical Engineering Series) ,Chapter 6,
[5]劉適程，民國93年，”以BCH 編碼為基礎之倒頻譜聲音浮水印技術”，國立東華大學資訊工程碩士在職專班，第三章12~14頁， 7月
[6]R. G. Gallager, 1962,“Low-density parity-check code,” IRE Trans. Inform. Theory, vol. IT-8, pp. 21-28, Jan..
[7]William E. Ryan, 2003,“An introduction to LDPC codes*”, Department of electrical and computer Engineering, The university of Arizona, August 19
[8]R. M. Tanner et. Al. ,2004., “ LDPC Block and Convolutional Codes Based on Circulant Matrices,” IEEE Trans. Information Theory, VOL. 50, NO. 12, pp. 2966-2984, Dec.
[9]D. J. C. MacKay, 1999. “Good error-correcting codes based on very sparse matrices,” IEEE Trans. Inform. Theory, vol. 45, pp.399-431, Mar.
[10]Takashi Yokokawa, Makiko Kan, Satoshi Okada, Lui Sakai, 2008, “Parity and Column Twist Bit Interleaver for DVB-T2 LDPC Codes”, 5th International Symposium on Turbo Codes and Related Topics.
[11]桂銘緯，2005， “應用於行動通訊之雷瑞衰退通道之適應性灰色預測模型”，大葉大學電信工程研究所碩士班，第三章。
[12]R. M. Tanner, 1981, “ A recursive approach to low complexity codes.” IEEE Tras. Inform.Theory, vol. IT-27, no. 5, pp.399-431, Sept.
[13]N. Wiberg, 1996 ,“Codes and decoding on general graphs,” Ph.D. dissertation, Linkoping University, Sweden, Chapter 3.
[14]M. P. C. Fossorier, M. Mihaljevic, and H. Imai, 1999, “Reduced complexity iterative decoding of low density parity check codes based on belief propagation,” IEEE Trans. Commun.,May.
[15]X.-Y. Hu, E. Eleftheriou, D.-M. Amold, and A. Dholakia, 2001, “Efficient implementation of the sum-product algorithm for decoding LDPC codes,” GLOBECOM.
[16]W. W. Peterson, 1960, “Encoding and error-correction procedures for the Bose-Chaudhuri codes,” IRE Trans. Inf. Theory, IT-6, pp. 459-470, Sep.
[17]D. Gorenstein and N. Zierler,1961,“A class of cyclic linear error-correcting codes in pm symbols,” pp. 107-214, June.
[18]E. R. Berlekamp, 1968, Algebraic Coding Theory, McGraw-Hill, New York,.
[19]J. L. Massey, 1969 ,“Shift register synthesis and BCH coding,” IEEE Trans. Info. Theory, vol. 15, pp. 122-127, Jan..
[20]Shayan, Y.R. ; Le-Ngoc, Tho ; Bhargava, V.K. , 1987,”Binary-decision approach to fast Chien search for software decoding of BCH codes”, October.