《数学新浪潮.ppt》由会员分享，可在线阅读，更多相关《数学新浪潮.ppt（23页珍藏版）》请在三一文库上搜索。
1、數學新浪潮,編碼理論,簡介,介紹編碼理論的歷史 描述編碼理論的內容 談談一些好碼,歷史,1950 年漢明（Hamming）首先提出漢明碼 50至60年代發展成BCH碼 70年代高帕（Goppa）提出高帕碼 80年代謝伐斯曼（Tsfasman）將高帕碼推廣成一般的代數幾何碼,信息傳遞,信源,編碼,調諧器,信道,調諧器,譯碼,信息,傳送,編碼初階：對應,編碼就是把字符（letters）轉變成數碼例如,編碼初階：信息率,對編碼的要求是效率高，準確 上述編碼效率非常高，其信息率為,信息率為的碼在資源發揮的觀點上是完美的，沒有浪費一個位元,編碼初階：準確性,信息傳遞並非完美技術，可能發生錯誤 如 信息率
2、為的編碼無法檢查錯誤，如接收到的信息是，則可能是B，也可能是C（即）錯了一位元，同樣可能是R（即）錯了一位元,檢錯方法,衹用部份數碼組作碼字，長度為的數碼組有組 我們衹用及來編碼，如果接收到或我們就知道傳送出了錯誤,檢錯的代價,上述編碼的信息率為 信息率的意思是每個位元碼組衹有個位元的信息另個位元沒帶信息，可以說是多餘的 檢錯的代價就是信息率下降,再談檢錯碼,我們可以用奇偶校驗位元來進行檢錯，這樣做能提高信息率如,這組碼的信息率是,上述例子說明我們可以提高檢錯碼的信息率,知錯能改,在上述C編碼中，如果接收到的數碼組是我們知道出了錯誤，但是信源究竟是或我們無法知道 怎樣編碼才會既能夠檢錯又能夠改
3、錯？具這樣能力的編碼，我們稱之為糾錯碼 要明白如何製作糾錯碼，我們要由如何譯碼談起,譯碼初階,極大似然譯碼准則：設收到的數碼組為 r 而所有碼字為 則 為假設信源是 而收到 r 的條件概率 r 就被譯作令 最大的 ,譯碼初階,二元對稱信道 漢明重量數碼組中的總數，例如的重量是 兩數碼組，的漢明距離（）的重量,q,q,p,p,例如，之間的距離是 設 為數碼組與碼字 之間的距離，則 容易看出當 最小時 最大因此我們得出另一譯碼方案：最小距離譯碼准則,一個簡單的譯碼例,考慮二元 碼 其中,也可以說這個碼由生成矩陣,所生成,這個碼衹有四個碼字,根據上述譯碼原則，我們有,我們將每一行均譯成該行最上的碼字
4、,糾錯碼入門,重覆碼是最簡單的糾錯碼，其編碼方法是 這編碼能糾正不多於N個錯誤譯 碼方法是當收到 時，如果的個數多於N時就將譯作，否則譯作這編碼的信息率是,糾錯碼原理,讓我們仔細看看重覆碼當 時，我們可以把所有長度的數碼組分為兩組：,每組衹包含一個碼字如果收到的 屬於 就將 譯為，如果收到的 屬於 就將 譯為注意此時 而且,抽象一點說， 是以 為球心半徑為的球；而 是以 為球心半徑為的球,000,010,001,100,111,110,011,101,將這概念推廣至維二元線性空間就得到線性糾錯碼漢明 碼就是最早發現的線性糾錯碼這個碼的信息率為 是所有能傳送四位元信息的糾錯碼中最高,漢明碼,漢明 碼的編碼方法：設 為一碼字，則 為信息位元並,我們亦可以利用向量和矩陣來編碼，將信息表達成向量 再乘以生成矩陣G就得到碼字,漢明碼的全部碼字為,譯碼方法也十分簡單，衹須將收到的數碼組 乘上校驗矩陣 再將 與 的列比較，其中,例如 並非碼字，一定是出了錯誤，譯碼時先計算,此時 是 的第五列，因此 的第五位元錯了所以 被譯成 ，注意 是碼字如果 是碼字，有,因此設 則,而這就是 的第 列,