数学新浪潮专题培训市公开课金奖市赛课一等奖课件

數學新浪潮編碼理論第1页第1页簡介介紹編碼理論歷史．描述編碼理論內容．談談一些好碼．第2页第2页歷史1950年漢明（Hamming）首先提出漢明碼．50至60年代發展成BCH碼．70年代高帕（Goppa）提出高帕碼．80年代謝伐斯曼（Tsfasman）將高帕碼推廣成普通代數幾何碼．第3页第3页信息傳遞信源編碼調諧器信道調諧器譯碼信息傳送第4页第4页編碼初階：對應編碼就是把字符（letters）轉變成數碼．比如第5页第5页編碼初階：信息率對編碼要求是效率高，準確．上述編碼效率非常高，其信息率為 信息率為１碼在資源發揮觀點上是完美，沒有浪費一個位元．第6页第6页編碼初階：準確性信息傳遞並非完美技術，也许發生錯誤．如信息率為１編碼無法檢查錯誤，如接受到信息是０００１０，則也许是B，也也许是C（即０００１１）錯了一位元，同樣也许是R（即１００１０）錯了一位元．第7页第7页檢錯办法衹用部份數碼組作碼字，長度為２數碼組有４組我們衹用００及１１來編碼，假如接受到０１或１０我們就知道傳送出了錯誤．１００００１１１第8页第8页檢錯代價上述編碼信息率為信息率＝０．５意思是每個２位元碼組衹有１個位元信息．另１個位元沒帶信息，能够說是多餘．檢錯代價就是信息率下降．第9页第9页再談檢錯碼我們能够用奇偶校驗位元來進行檢錯，這樣做能提升信息率．如這組碼信息率是上述例子說明我們能够提升檢錯碼信息率．第10页第10页知錯能改在上述C編碼中，假如接受到數碼組是０１０我們知道出了錯誤，但是信源终归是１１０或０１１我們無法知道．怎樣編碼才會既能夠檢錯又能夠改錯？具這樣能力編碼，我們稱之為糾錯碼．要明白如何製作糾錯碼，我們要由如何譯碼談起．第11页第11页譯碼初階極大似然譯碼准則：設收到數碼組為r

而所有碼字為則為假設信源是而收到r

條件概率．

r就被譯作令最大．第12页第12页譯碼初階二元對稱信道．漢明重量＝數碼組中１總數，比如１００１１０１重量是４．兩數碼組ｘ，ｙ漢明距離＝（ｘ－ｙ）重量．qqpp第13页第13页比如ｘ＝０１００１，ｙ＝１０１１１之間距離是４．設為數碼組ｒ與碼字之間距離，則容易看出當最小時最大．因此我們得出另一譯碼方案：最小距離譯碼准則．第14页第14页一個簡單譯碼例考慮二元碼其中也能够說這個碼由生成矩陣所生成．第15页第15页這個碼衹有四個碼字根據上述譯碼原則，我們有我們將每一行均譯成該行最上碼字．第16页第16页糾錯碼入門重覆碼是最簡單糾錯碼，其編碼办法是 這編碼能糾正不多於N個錯誤．譯 碼办法是當收到 時，假如１個數多於N時就將ｒ譯作１，否則譯作０．這編碼信息率是第17页第17页糾錯碼原理讓我們仔細看看重覆碼．當時，我們能够把所有長度３數碼組分為兩組：每組衹包括一個碼字．假如收到屬於就將譯為０，假如收到屬於就將譯為１．注意此時并且第18页第18页抽象一點說，是以為球心半徑為１球；而是以為球心半徑為１球．000010001100111110011101將這概念推廣至ｎ維二元線性空間就得到線性糾錯碼．漢明碼就是最早發現線性糾錯碼．這個碼信息率為是所有能傳送四位元信息糾錯碼中最高．第19页第19页漢明碼漢明碼編碼办法：設 為一碼字，則為信息位元並我們亦能够利用向量和矩陣來編碼，將信息表達成向量 再乘以生成矩陣G就得到碼字第20页第20页漢明碼所有碼字為第21页第21页譯碼办法也十分簡單，衹須將收到數碼組乘上校驗矩陣再將與列比較，其中第22页第22页比如並非碼