格雷碼的編碼和譯碼算法

格雷碼(Golay Code)的編碼和譯碼算法

格雷碼在通信中應用廣泛。例如早在1980年俄羅斯航天儀表碼研究所為了提高“星一地”、“地一星”鏈路數字指控信息的可靠性，研制和實現了格雷碼的編碼器和譯碼器，該設備在某型號飛行任務中成功地進行了試驗。試驗表明，使用格雷碼，通信系統的誤碼率與未編碼通信系統相比減少了1-3個數量級。格雷碼通常是指線性分組(23,12)碼，最小距離dmin=7,糾錯能力 t=3。由于223-12=2048=1+ ，所以格雷碼是完備碼，其碼重分布見下面表1。碼重0781112151623碼個數1253506128812885062531表1 格雷碼的碼重分布

格雷碼Golay (23，12)是循環碼。對于漢明碼、格雷碼、二次剩余碼、BCH碼和R-S碼等循環碼的解碼有很多方法，如梅杰特解碼(Meggit, 1961)、大數邏輯解碼(Reed，1954)、門限解碼(Massey, 1961)、信息組解碼(Prange, 1962)。最經典的方法當屬梅杰特解碼，它充分利用了循環碼的循環特征。

格雷碼的編碼算法輸入：信源消息u(消息分組u)輸出：碼字v1、處理：信源輸出為一系列二進制數字0和1。在分組碼中，這些二進制信息序列分成固定長度的消息分組(message blocks)。每個消息分組記為u，由k個信息位組成。因此共有2k種不同的消息。編碼器按照一定的規則將輸入的消息u轉換為二進制n維向量v，這里n >k。此n維向量v就叫做消息u的碼字(codeword)、碼字矢量或碼向量(code vector)。 因此，對應于2k種不同的消息，也有2k種碼字。這2k個碼字的集合就叫一個分組碼(block code)。若一個分組碼可用，2k個碼字必須各不相同。因此，消息u和碼字v存在一一對應關系。由于n符號輸出碼字只取決于對應的k比特輸入消息，即每個消息是獨立編碼的，從而編碼器是無記憶的，且可用組合邏輯電路來實現。定義：一個長度為n，有2k個碼字的分組碼，當且僅當其2k個碼字構成域GF(2)上所有n維向量組成的向量空間的一個K維子空間時被稱為線性(linear)(n, k)碼。格雷碼Golay(n,k)就是線性分組(n, k)碼的一種。其編碼算法即為使用生成矩陣G：v = u·G 。例1-1 格雷碼Golay (20,8,7) 的生成矩陣G為：G= [ Ik P ]k×n = ，v = u·G ，處理完畢。其他線性分組(n, k)碼都可以照此辦理即可。線性分組(n, k)碼的校正子(伴隨式)有2n-k個，設該碼的糾錯能力為t，那么重量小于或者等于t的所有錯誤模式(圖樣)都要有唯一的校正子(伴隨式)與之對應，因而，對于二進制(n, k)碼，有漢明限：2n-k≥ ，當2n-k=時，(n, k)碼稱為完備碼(Perfect Code)。完備碼的校正子(伴隨式)得到了充分的利用，不存在解碼不唯一的問題，然而完備碼不一定是糾錯能力強的碼，因為它的最小距離dmin未必最大。完備碼也是稀少的，已知的二進制完備碼有t=1的漢明碼(Hamming Code)和t=3的格雷碼(Golay Code)，以及n為奇數的簡單重復(n,1)碼。三進制完備碼有t=2的(11,6,5)格雷碼。糾錯能力t=1的完備碼統稱為漢明碼。由定義可知，(n, k)漢明碼應當滿足下列條件：2n-k=1+n ，令校驗位長m=n-k，那么容易知道：n=2m-1, k=2m-1-m, dmin=3漢明碼的校驗矩陣H具有特殊的性質：它的m維列向量正好是除零向量以外的所有可能的向量組合，共有2m-1個，恰好構成了H矩陣的列數n。格雷碼通常是指線性分組(23,12)碼，最小距離dmin=7，糾錯能力 t=3。由于223-12=2048=1+ ，所以格雷碼是完備碼，其碼重(碼的重量)分布見下面表0-1。

表1 格雷碼的碼重分布碼重0781112151623碼個數1253506128812885062531

備注：1、格雷碼Golay (20,8,7) 的生成矩陣G為：G= [ Ik P ]k×n = 。2、除了分組碼之外，還有卷積碼。卷積碼編碼器同樣接受k比特分組的信息序列u，并產生n符號組的編碼序列(碼序列)v(卷積碼編碼中，符號u和v用來表示分組的序列而非單個分組)。但是，每一個編碼分組不僅取決于當前單位時間對應的k比特消息組，而且與前m個消息組有關。此時，編碼器的存儲級數(memory order)為m。編碼器所產生的所有可能的輸出編碼序列的集合構成了一個碼。比值R=k/n稱為碼率(code rate)。由于編碼器有存儲單元

總結

以上是生活随笔為你收集整理的4位格雷码的顺序编码_格雷码的编码和译码算法.doc的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。