数学新浪潮专题培训市公开课一等奖百校联赛特等奖课件.pptx

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