跳到主要內容

臺灣博碩士論文加值系統

(18.97.14.86) 您好!臺灣時間:2025/02/08 01:26
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:江佳陽
研究生(外文):Chia-yang Chiang
論文名稱:低密度同位元檢測碼與密度進化
論文名稱(外文):Low Density Parity Check Code and Density Evolution
指導教授:陸曉峯
指導教授(外文):Hsiao-feng Lu
學位類別:碩士
校院名稱:國立中正大學
系所名稱:通訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:英文
論文頁數:73
中文關鍵詞:低密度同位元檢測碼密度進化
外文關鍵詞:ldpcdensity evolutionlow density parity check code
相關次數:
  • 被引用被引用:0
  • 點閱點閱:298
  • 評分評分:
  • 下載下載:35
  • 收藏至我的研究室書目清單書目收藏:0
本篇論文中闡述了兩個在編碼領論中重要的發明,一個是「低密度同位元檢測碼」(Low Density Parity Check Code)一個是「密度進化」(Density Evolution)。

低密度同位元檢測碼是線性區碼的一種,可以提供接近 Shannon Capacity的效能以及可以實作出的編解碼架構。低密度同位元檢測碼是由 Gallager 在他博士論文中首次被提出來,然而在之後的35年間甚少受到重視。在 Tanner、 Mackay、 Luby 與 Urbanke 等人在低密度同位元檢測碼中所做的一些重要的研究之後,近年來低密度同位元檢測碼變的更有名氣了。低密度同位元檢測碼的編碼技術在IEEE 802.11n 與 DVB-H 或者甚至未來的 4G 科技中都是重要的技術。在一些良好設計下,碼率為0.5的低密度同位元檢測碼在 binary-input AWGN 通道下可以與 Shannon limit 只有0.0045 dB的差距,或在 multilevel AWGN 通道下與 Shannon limit只有0.0063dB 的差距。

密度進化是一個非常有效也直接的方法,用來分析低密度同位元檢測碼與解碼演算法搭配下,可以在多麼惡劣的通道下達到傳送可靠資料。整個方式是基於三個假設,以及我們利用電腦模擬來找出在binary-input memoryless 通道下的近似閥值(threshold) ,這些通道有binary symmetry channel 與 binary input additive white Gaussian noise 通道。我們重現了當年 Gallager 所發現的閥值現象(threshold phenomenon)並且計算出在不同通道下以及不同碼率下,個別的閥值會是多少。藉由使用密度進化,我們可以得知我們所設計的低密度同位元檢測碼的效能好壞與否,並且進一步藉由密度進化我們可以去設計出更好的低密度同位元檢測碼以期能在當碼長度為無窮大時,我們的效能能達到 Shannon limit。
The LDPC code is a class of linear block codes which provide near capacity
performance and implementable coding scheme. The LDPC code was first
invented by Gallager in his thesis but was scarcely considered in the
following 35 years. After Tanner, Mackay, Luby and Urbanke et al.
with all their great works the LDPC code became renowned in recent years.
The LDPC coding becomes the important technique for IEEE 802.11n, DVB-H or
even in future 4G technologies. In some well designed degree distribution,
the 1/2 rate LDPC code can approach Shannon limit within 0.0045dB for
binary-input AWGN channels or approach Shannon limit within 0.0063dB for
multilevel AWGN channels.

Density Evolution is a useful and straightforward method to analyze the LDPC
codes and decoding algorithm's performance and how worst a channel can be
for a designed LDPC code to reliably transmit data. The whole method is
based upon three symmetry assumptions and we use computer simulation to find
the asymptotical thresholds for some binary-input memoryless channels such
as binary symmetry channel and binary input additive white Gaussian noise
channel. We demonstrate the threshold phenomenon which Gallager first found
and also calculate the thresholds for different rates using different
channel models. By using density evolution, we could know the LDPC code that
we designed performs well or not, and then find the good degree distribution
for LDPC code via density evolution to achieve the Shannon limit
asymptotically as the block length tends to infinity become possible.
1 Introduction
1.1 Reliable Transmission
1.2 Low-Density Parity-Check Codes
1.3 Thesis Organization
2 Low-Density Parity-Check Codes
2.1 Representation
2.1.1 Matrix Representation
2.1.2 Graphical Representation
2.2 Regular Low-Density Parity-Check Codes
2.3 Irregular Low-Density Parity-Check Codes
2.4 Degree distribution polynomials
2.5 LDPC Encoding
2.5.1 Regular LDPC Codes
2.5.2 Irregular LDPC Codes
3 LDPC Decoding Algorithm
3.1 Hard Decision Decoding
3.1.1 Gallager's first decoding algorithm
3.1.2 Gallager's second decoding algorithm
3.2 Soft Decision Decoding
3.2.1 Sum-Product Algorithm
3.2.2 Min-Sum Algorithm
4 Density Evolution
4.1 Symmetric Assumption
4.1.1 Binary Symmetry Channel (BSC)
4.1.2 Binary Input Additive White Gaussian Channel (BIAWGNC)
4.2 Threshold Effects
4.2.1 Channel models and Capacity
4.3 Gallager's decoding algorithm on BSC
4.3.1 Gallager's first decoding algorithm
4.3.2 Gallager's second decoding algorithm
4.4 Belief Propagation (BP) Algorithm
5 Computer Simulation Results
5.1 BSC using Gallager's first decoding algorithm
5.2 BSC using Gallager's second decoding algorithm
5.3 BSC using BP algorithm
5.4 BIAWGNC using BP algorithm
5.5 Irregular LDPC codes
6 Conclusions
C. E. Shannon, "A mathematical theory of
communication," Bell System Technical Journal, vol. 27, pp.
379-423, 1948.

R. G. Gallager. Low-Density Parity-Check Codes.
IRE Trans. Inform. Theory, pp. 21-28, Jan. 1962.

R. G. Gallager. Low-Density Parity-Check Codes. MIT
Press, Cambridge, MA, 1963.

M. R. Tanner, "A recursive approach to low
complexity codes," IEEE Trans. Inform. Theory, vol. 27, pp.
533-547, 1981.

J. Pearl, Probabilistic Reasoning in Intelligent Systems:
Networks of Plausible Inference. Morgan Kaufmann Publishers, Inc., 1988.

T. M. Cover and J. A. Thomas, Elements of
Information Theory. New York: Wiley, 1991.

D. MacKay and R. Neal, "Good codes based on very
sparse matrices," in Cryptography and Coding, 5thIMA
Conf., C. Boyd, Ed., Lecture Notes in Computer Science,
pp. 100-111, Berlin, Germany: Springer, 1995.

M. Luby, M. Mitzenmacher, and A. Shokrollahi, " Analysis of
random processes via and-or tree evaluation," in Proceedings of the
9th Annual ACM-SIAM Symposium on discrete Algorithms, pp. 364-373, 1998.

Michael G. Luby, Michael Mitzenmacher, M. Amin Shokrollahi,
Daniel A. Spielman. "Analysis of low-density parity-check codes and
improved designs using irregular graphs." 30th ACM STOC, May 23-26 1998.

V. Sorokine, F. R. Kschischang, and S. Pasupathy, "
Gallager codes for CDMA applications: Part I}," IEEE Trans. Comm,
pp. 1660-1668, Oct. 2000.

V. Sorokine, F. R. Kschischang, and S. Pasupathy,"
Gallager codes for CDMA applications: Part II}," IEEE Trans. Comm,
pp. 1818-1828, Nov. 2000.

Michael G. Luby, Michael Mitzenmacher, M. Amin Shokrollahi,
and Daniel A. Spielman. "Improved low-density parity-check codes
using irregular graphs," IEEE Trans. Inform. Theory, vol. 47, pp.
585-598, Feb. 2001.

N. Wiberg, Codes and decoding on general graphs
," Ph.D. dissertation, Dept. Elec. Eng., Univ. Linkoping, Sweden, Apr.
1996.

T. Richardson and R. Urbanke,
"The capacity of low-density parity-check codes under message-passing decoding},"
IEEE Trans. Inform. Theory}, vol. 47, pp. 599-618, Feb. 2001.

T. Richardson, A. Shokrollahi, and R. Urbanke,
"Design of capacity approaching low-density parity-check codes},"
IEEE Trans. Inform. Theory, vol. 47, pp. 619-637, Feb. 2001.

T. Richardson, R. Urbanke,
"Efficient encoding of low-density parity-check codes," IEEE Trans. Inform. Theory, vol.
47, pp. 638-656, Feb. 2001.

S.-Y. Chung, D. Forney, T. Richardson, and R. Urbanke,
"On the design of low-density parity-check codes within 0.0045 dB of
the Shannon limit," IEEE Commun. Letter., vol. 5, pp.58-60, Feb.
2001.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top