《错误更正码简介》由会员分享，可在线阅读，更多相关《错误更正码简介（15页珍藏版）》请在金锄头文库上搜索。
1、錯誤更正碼簡介趙啟超演講李啟鈴記錄今天很高興來跟大家介紹 錯誤更正碼, ErrorCorrecting Codes, 通常縮寫成 ECC。 在日常生活中, 我們經常可以遇到 ECC 的應用, 譬如在買電腦的時候, 老闆說他的 RAM 是 ECC RAM, 也就是說他的 RAM 有錯誤更正碼在裡面。 這錯誤更正碼到底是做什麼用? 通常是應用在通訊的過程中, 實際上通訊分很多種, 平常想像到的是在空間中做通訊, 譬如從地球的某一點傳資料到地球的另外一點。 另外還有一種通訊的情況, 就是在時間上做通訊, 像平常看到電腦裡的磁帶 (magnetic tape)、 磁碟(magnetic disk);
2、又譬如雷射唱片 (com-pact disk, CD) 也是, 它在製造的時候把音樂寫進去, 然後再把它放到雷射唱盤 (CDplayer) 讀出來, 這也是一個在時間上做通訊的例子。 通常我們可以把通訊過程變成下面這個模型 (model) (如圖1)。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3、. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4、. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .datachannelnoisy data圖 1就是說有一些資料 (data) 經過一個東西叫做通道 (channel), 因為通道會有許多干擾或雜訊, 比方說你把音樂寫在 CD
5、 片上, 不小心刮了一塊, 讀出來的時候那地方就錯了,所以, 經過通道之後, 就會變成有雜訊的資料(noisy data), 而基本上錯誤更正碼就是要對付雜訊或干擾, 把錯誤改正回來。一. 錯誤更正碼的由來為什麼會想到利用錯誤更正碼?1948年以前, 大家在做通訊系統的時候, 都只想到要如何使訊號接收得比較好, 比如把天線加大, 或者把訊號傳遞的功率加大, 但這些都是在物理上做改進。 直到1948年 ClaudeShannon 寫了一篇論文叫做 A mathemat-ical theory of communications, 他說事實上我們不必這樣做, 很多情形只要在資料上做手腳, 只要傳資
6、料的速率小於每個通道特有的量, 術語叫做通道容量 (channel capac-ity), 就一定有辦法讓資料錯誤的機率很小,要多小都可以, 而要達到這樣的碼 (code) 一12數學傳播十八卷四期民83年12月定會存在, 但是他並沒有說用什麼樣的碼, 只證明了一定會有。 不過, 因為他提出了這件事, 後來造成了整個領域的發展, 這個領域叫做訊息理論 (information theory), 其中有很重要的一部分就是 ECC 的理論。 從1948年到現在40幾年來, 這整個領域的發展就是因為 Shannon 那時候的貢獻。基本上, Shannon 說什麼呢?原來我們是從資料到通道這樣直接過來
7、, 現在我們讓資料在傳出前先經過一個編碼器 (en-coder)(如圖2)。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8、. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9、. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10、. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11、. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12、. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13、. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .dataEncoderChanneldata redundancynoisy data noisy redundancyDecodergood data圖 2經過編碼器之後, 傳出來的東西除了原始的資料之外, 又加了一些多餘的資料 (redun-dant bits), 使得裡面有一個數學的結構存在, 當經過通道以後不論是原始的資料或多餘的資料都可能有錯, 可是因為它裡面有數學結構, 就可以經由解碼器 (decoder), 依原有的數學結構把錯誤的
14、東西改回來, 這就是錯誤更正碼的基本構想。二.SingleError Correct- ing(SEC) Codes我們現在先來看一個簡單的例子, 有三個集合 (sets) A、B、C 兩兩相交 (如圖3.1)。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15、. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16、. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
