認(rèn)識編碼學(xué)CodingTheory編碼學(xué)簡介誕生:C.Shannon

1948

年的文章“AMathematicalTheoryofCommunication”

載于BellSyst.Tech.J.27,379-423&623-656

目標(biāo):找出有效率的編碼方法,

使信息能在有噪聲

的通道上可靠地

傳送.

應(yīng)用:將宇宙飛船玤所拍攝的相片傳回地球,

注冊碼(證件號/ISBN)的設(shè)計,數(shù)位資料儲存,…參考書及主題參考書:Hill(1986),AFirstCourseinCodingTheoryLing&Xing(2004),CodingTheory:AFirstCourse

主題:用以修正隨機(jī)錯誤

的分組碼(塊碼)

blockcodes

forcorrectingrandomerrors

兩大問題:尋找“最好”的碼有效率地譯碼內(nèi)容(基礎(chǔ)部分)錯誤修正碼介紹編碼學(xué)的主要問題有限域簡介有限域上的矢量空間線性碼介紹線性碼的編碼與譯碼對偶碼,奇偶檢驗矩陣,伴隨式譯碼Hamming碼1.錯誤修正碼介紹IntroductiontoError-CorrectingCodes錯誤修正碼信息在有噪聲的通道上傳送時,可能會產(chǎn)生錯誤.

錯誤修正碼用于修正這種錯誤.要求:整個過程越快且越可靠(準(zhǔn)確)

越好.做法:加入“多余”的部分,[例:重要的事要講三次]使得當(dāng)收到的信息有(不太多)錯誤時,仍然可以還原出本來的信息.通訊流程(以下是例子)發(fā)信者

信息編碼器

碼文信息通道

噪聲

收到的碼文譯碼器

譯碼后的信息收信者

注記額外的符碼不能保證100%準(zhǔn)確

傳達(dá),只能提高正確傳達(dá)的概率.在編碼前,發(fā)信者通常會把信息加密,<<

密碼學(xué)以避免通道上其他人竊看信息;

相應(yīng)地,收信者在讀信前也要先解密.前例是一個binary

repetition

codeoflength5

二元重覆碼,長度5

例子集合{00000,11111}是一個碼,

它的元素00000和11111都是這個碼的碼文.

這個碼是一個二元碼,它的字母集是{0,1}.英文單詞的集合是一個26元碼,它的字母集為{A,B,C,…,Z}.(忽略大小寫分別)英文路名(不含數(shù)字)的集合則是27元碼.分組碼/塊碼blockcodes

例子:電話號碼英國的10位電話號碼,可視作長度為10的10元碼.可以設(shè)計出一套電話號碼,它滿足以下要求:

(1)有超過82,000,000個碼文(足夠當(dāng)時英國用);

(2)即使撥錯任何單一個數(shù)字,仍能正確撥通電話.將會在第7章會建構(gòu)出這種碼.例子:東南西北的二元編碼

例子:東南西北的二元編碼(續(xù))

Hamming距離

例子及注記:距離

最近鄰譯碼

nearestneighbordecoding

最近鄰譯碼的最大似然性

詞出錯概率

worderrorprobability

注記/“線性碼”

碼的最小距離

定理

(最小距離與偵錯及修正)

[證]最小距離與偵錯及修正的位數(shù)偵錯位數(shù)修正位數(shù)100210321431