差错控制编码课件

*

差錯控制編碼

*5.1引言數字信號在傳輸過程中受到干擾的影響，使信號波形變壞，發生誤碼，可以採用一些方法解決。

有效性——信源編碼可靠性——通道編碼*0、復習

模擬信源：在無線廣播中，信源一般是一個語音源（話音或音樂）；在電視廣播中，信源主要是活動圖像的視頻信號源。這些信源的輸出都是模擬信號，所以稱之為模擬源。

信源編碼：將模擬資訊源的輸出轉化為數字信號，即A/D轉換。

信源編碼目的：提高通信有效性，減少原消息的冗餘度。5.1引言*差錯出現原因外界雜訊傳輸中碼間串擾解決方法合理地設計基帶信號，選擇調製、解調方式，採用均衡技術，發送功率等因素，使誤比特率降低。差錯控制措施了。5.1引言*

差錯控制編碼屬通道編碼，要求在滿足有效性前提下，盡可能提高數字通信的可靠性。

差錯控制編碼是在資訊序列上附加上一些監督碼元，利用這些冗餘的碼元，使原來不規律的或規律性不強的原始數字信號變為有規律的數字信號。例如奇偶校驗。差錯控制解碼則利用這些規律性來鑒別傳輸過程是否發生錯誤，或進而糾正錯誤。5.1引言*

按功能分：檢錯碼和糾錯碼按監督碼元與資訊碼元關係分：線性碼與非線性碼按資訊碼元與監督碼元之間的約束關係不同分：分組碼與卷積碼按資訊碼元在編碼後是否保持原來的信號形式分：系統碼與非系統碼按糾正差錯的類型分：糾正隨機錯誤的碼與糾正突發錯誤的碼按碼元的取值分：二進位碼與多進制碼001、差錯控制編碼分類5.1引言*2、誤碼類型

隨機誤碼

突發誤碼錯碼出現是隨機的、錯碼之間統計獨立。由隨機雜訊引起存在隨機誤碼的通道稱為隨機通道／無記憶通道差錯在短時間成串出現，而在其間又存在較長的無差錯區間，且差錯之間相關例如：脈衝雜訊，存儲系統中磁帶的缺陷或讀寫頭接觸不良引起，再例如用手機過涵洞，且無發射天線存在這種差錯的通道稱為突發通道／有記憶通道5.1引言3、錯誤圖樣例如：設發送數據序列為：00000000001111111111接收數據序列為：01101001001111001001錯誤圖樣（差錯序列）：發送數據序列與接收序列對應碼位的模２和則差錯序列為：01101001000000110110可見發生了兩個長度分別為７和５的突發差錯，其錯誤圖樣分別為1101001和11011突發長度：指突發差錯首位與末位之間的長度（中間可能有沒錯的碼位）*說明差錯序列或錯誤圖樣中的“０”表示對應碼位沒錯，而“１”表示有錯實際通道很複雜，所出現的差錯並不是單一的，往往是隨機和突發差錯並存，只不過以某種錯誤為主一般說來，糾正隨機差錯的編譯碼方法和設備比較簡單，成本較低，效果較顯著；而糾正突發差錯的編譯碼方法和設備比較複雜，成本較高，效果也不如前者顯著5.1引言*4、通道類型

隨機通道

突發通道

混合通道5.1引言*5、差錯控制方法檢錯重發（ARQ）停發等候重發返回重發選擇重發前向糾錯（FEC）回饋校驗（IRQ）混合方式（HEC）5.1引言*（1）檢錯重發法（ARQ）

AutomaticRepeatreQuest

收端在接收到的信碼中發現錯碼時，就通知發端重發，直到正確接收為止。例如奇偶校驗。檢錯重發方式只用於檢測誤碼，能夠在接收單元中發現錯誤，但不一定知道該錯誤碼的具體位置。需具備雙向通道。5.1引言發收能夠發現錯誤的碼圖5.1-1（a)檢錯重發（ARQ)應答信號圖5.1-1（b)檢錯重發（ARQ)信源編碼器和緩沖記憶體重發控制雙向信道解碼器指令產生器輸出緩衝記憶體收信者正確時輸出錯誤時刪除判斷有無錯誤*①停發等候重發2發送端：接收端：133123ACKACKNAK發現錯誤TITw停頓時間圖5.1-2停發等候重發5.1引言*發端在Tw時間內送出一個碼組；收端收到後檢查。如果未發現錯誤，則發回一個認可信號（ACK）給發送端，發送端收到ACK信號再發下一個碼組若檢測到錯誤，則發回一個否認信號（NAK），發送端收到NAK信號後重發前一碼組，並再次等候ACK信號或NAK信號發送兩個碼組之間有停頓時間TI，影響了傳輸效率5.1引言*②返回重發圖5-2(b)返回重發其發送端不停地送出一個個連續碼組，不再等候收端返回的ACK信號一旦收端發現錯誤並返回NAK信號，則發端從下一碼組開始重發前面的N個碼組N的大小取決於信號傳遞及處理所帶來的延時5.1引言*發送端：接收端：1234562341234562345678956789發現錯誤NAK從碼組2開始重發5.1引言圖5.1-3返回重發*③選擇重發也是連續不斷地發送碼組，收端檢測到錯誤後發回NAK信號。與返回重發不同的是，發端並不重發錯誤碼組後的所有碼組，而只重發有錯的那個碼組5.1引言*發送端：接收端：12345627812345627899發現錯誤NAK重發碼組2圖5.1-4選擇重發5.1引言*三者比較選擇重發傳輸效率最高，但成本最貴：控制機制複雜，發端和收端都要有數據緩衝器；返回重發、選擇重發需要全雙工資料鏈路，而停發等候重發只要求半雙工的資料鏈路。5.1引言*（2）前向糾錯法（FEC）

ForwardErrorCorrection發收能夠糾正錯誤的碼圖5.1-5前向糾錯（FEC)信源編碼器單向通道糾錯解碼器輸出緩衝記憶體收信者+5.1引言*發送端將資訊序列編碼成能夠糾正錯誤的碼，接收端根據編碼規則進行檢查，如果有錯自動糾正不需要回饋通道，特別適合只能提供單向通道場合自動糾錯，不要求檢錯重發，延時小，即時性好糾錯碼必須與通道的錯誤特性密切配合若糾錯較多，則編、解碼設備複雜，傳輸效率低5.1引言*（3）資訊回饋校驗法（IRQ）

InformationRepeatreQuest接收端將接收到的信碼原封不動地轉發回發端，並與原發送信碼相比較，若發現錯誤，發端再重發。數據資訊發收圖5.1-6資訊回饋法數據資訊5.1引言*收端把收到的數據序列全部經反向通道送回發端，發端比較發出和送回的數據序列，從而發現有否錯誤，如果有錯誤，發端將數據序列再次傳送，直到發端沒有發現錯誤。不需要糾錯、檢錯的編、解碼器，設備簡單。需要和正向通道相同的反向通道，即時性差發端需要一定容量的記憶體以存儲發送碼組僅適應於傳輸速率較低，通道差錯率較低，具有雙向傳輸線路及控制簡單的系統5.1引言*（4）混合糾錯檢錯（HEC）

HybridErrorCorrectionFEC與ARQ的結合發端發出同時具有檢錯和糾錯能力的碼，收端收到後，檢查錯誤情況：如果錯誤在糾錯能力之內，則自動糾正；若超出糾錯能力，但在檢錯能力之內，則經反向通道要求重發。在即時性和解碼複雜性方面是FEC和ARQ的折衷。5.1引言*發收能夠發現和糾正錯誤的碼圖5.1-7混合糾錯檢錯（HEC)應答信號5.1引言*核心問題

發現錯誤糾正錯誤5.1引言*5.2差錯控制編碼的基本原理

在資訊碼序列中加監督碼就稱為差錯控制編碼，也叫糾錯編碼。不同的編碼方法，有不同的檢錯和糾錯能力，增加監督碼元越多，檢（糾）錯能力越強。差錯控制編碼原則上是降低編碼效率來換取可靠性提高。（即誤碼率更小）。

*理論依據：Shannon通道編碼定理。定理指出：對於一給定的有干擾通道，若其通道容量為C，只要發送端以低於C的速率R發送資訊，則一定存在一種編碼方法，使編碼錯誤概率P隨著碼長n的增加，按指數下降到任意小的值。1、糾錯編碼的理論依據5.2差錯控制編碼的基本原理*E(R)nCC1C2圖5.2-1誤差指數曲線5.2差錯控制編碼的基本原理*2、糾錯編碼的基本思想5.2差錯控制編碼的基本原理

發送端按照某種規則在資訊序列上附加監督碼元，接收端則按照同一規則檢查兩者間關係……

以犧牲通信的有效性（資訊傳輸速率）來提高可靠性

碼的檢錯和糾錯能力是用資訊量的冗餘來換取的。一般說來，添加的冗餘越多，碼的檢錯、糾錯能力越強，但通道的傳輸效率下降也越多。*

碼長：碼字中碼元的數目。碼距：兩個等長碼字中對應碼位上不同二進位碼元的位數定義兩碼字的距離，簡稱碼距（d）。對於二進位稱作這兩個碼字的漢明距離。如兩碼字“10011”與“11010”間碼距為2。3、碼距與檢錯和糾錯能力的關係5.2差錯控制編碼的基本原理（1）幾個概念*

最小碼距：在一個碼字集合中，任意兩個碼字間距離的最小值，即碼字集合中任意兩元素間的最小距離，記為dmin或d0

碼重：碼字中非零碼元的數目定義為該碼字的重量，簡稱碼重。如“10011”碼字的碼重為3。糾錯碼的抗干擾能力完全取決於許用碼字之間的距離，碼的最小距離越大，說明碼字間的最小差別越大，抗干擾能力就越強。5.2差錯控制編碼的基本原理*舉例說明：假如要傳送A、B兩個消息編碼一：消息A----“0”；消息B----“1”最小碼距1若傳輸中產生錯碼（“0”錯成“1”或“1”錯成“0”）收端無法發現，該編碼無檢錯糾錯能力。5.2差錯控制編碼的基本原理*編碼二：消息A----“00”；消息B----“11”最小碼距2若傳輸中產生一位錯碼，則變成“01”或“10”，收端判決為有錯（因“01”“10”為禁用碼組），但無法確定錯碼位置，不能糾正，該編碼具有檢出一位錯碼的能力。這表明增加一位冗餘碼元後碼具有檢出一位錯碼的能力5.2差錯控制編碼的基本原理編碼三：消息A----“000”；消息B----“111”最小碼距3傳輸中產生一位即使兩位錯碼，都將變成禁用碼組，收端判決傳輸有錯。該編碼具有檢出兩位錯碼的能力。在產生一位錯碼（錯1位概率遠遠大於錯2位、3位概率）情況下，收端可根據“大數”法則進行正確判決，能夠糾正這一位錯碼。該編碼具有糾正一位錯碼的能力。例如收到110，認為是111。這表明增加兩位冗餘碼元後碼具有檢出兩位錯碼及糾正一位錯碼的能力。*一個碼能檢測e個錯碼，則要求其最小碼dmin≥e+1一個碼能糾正t個錯碼，則要求其最小dmin≥2t+1一個碼能糾正t個錯碼，同時能檢測e個錯碼，則要求其最小碼距

dmin≥e+t+1(e>t)（2）最小碼距與檢錯和糾錯能力的關係5.2差錯控制編碼的基本原理*(a)檢e個錯圖5.2-2(a)碼距與檢錯糾錯能力的關係Ae1dminBA、B都為許用碼；A發生e個錯；B不能靠在球面上，否則收到B無法判斷是否為錯碼；dmin≥e+15.2差錯控制編碼的基本原理*1tABtdmin(b)糾正t個錯碼圖5.2-2(b)碼距與檢錯糾錯能力的關係A、B都為許用碼；A、B都發生t個錯；dmin≥2t+15.2差錯控制編碼的基本原理*ABtedmint(c)糾正t個錯碼，檢測e個錯碼圖5.2-2(c)碼距與檢錯糾錯能力的關係A、B都為許用碼；A發生e個錯；B發生t個錯；

dmin≥e+t+15.2差錯控制編碼的基本原理*當碼長n=7,P=10-3時，則有假設隨機通道中發送“0”碼與發送“1”碼傳錯概率相等都為P,且P<<1,則在碼長為n的碼組中發生r個錯誤的概率為：4、誤碼率大概率事件5.2差錯控制編碼的基本原理*設n=k+r指一個碼組中資訊位所占比重，用η表示η=k/n=k/(k+r)，其中k為資訊碼元的數目，n為碼長5、編碼效率η一次課5.2差錯控制編碼的基本原理*

奇偶監督碼二維奇偶監督碼恒比碼正反碼5.3常用的簡單編碼

*1、奇偶監督碼5.3常用的簡單編碼

奇偶監督碼：在資訊碼元後附加一位監督位，使得碼組中奇偶監督碼“1”的個數為偶數或奇數。*

最小碼距dmin=2

只能檢測出單個或奇數個錯誤，不能糾錯應用：以隨機錯誤為主的電腦通信系統，難於對付突發錯誤編碼效率=k/n=k/(k+1)5.3常用的簡單編碼

*

將經過奇偶監督編碼的碼元序列按行排成方陣，每行為一組奇偶監督碼，但發送時按列的順序傳輸接收端將碼元排成發送時的方陣形式，再按行進行奇偶校驗能夠發現某行上所有奇數個錯誤以及突發長度不大於方陣行數的突發錯誤編碼效率2、水準奇偶監督碼5.3常用的簡單編碼

表5-1水準奇偶監督碼111011100110000......0110110101第一個碼元第二個碼元第三個碼元第十個碼元監督碼元表5-2水準奇偶監督碼接收端出現突發誤碼示例1101×××結論：能夠發現突發長度不大於方陣行數的突發錯誤*

又稱為方陣碼、行列監督碼、二維奇偶監督碼。將水準奇偶監督碼推廣到二維。即在水準監督基礎上再對方陣中每一列進行奇偶校驗，發送時按列的順序傳輸接收端將碼元排成發送時的方陣形式，再分別按行、按列進行奇偶校驗3、水準垂直奇偶監督碼5.3常用的簡單編碼

*

能夠發現某行、某列上所有奇數個錯誤以及突發長度不大於方陣行數或列數的突發錯誤；有可能檢測出偶數個錯誤（在行上檢測不出，但有可能在列上檢測出），但當偶數個錯誤剛好構成矩形時，則檢測不出可糾正一些錯誤

5.3常用的簡單編碼

表5-3水準垂直奇偶監督碼發送順序表5-4水準垂直奇偶監督碼接收端糾錯示例011例如：當碼組中僅在一行有奇數個錯誤時，能夠確定錯誤位置，並糾正它。√√√√√√√√√√√√√××××表5-5水準垂直奇偶監督碼接收端檢錯示例011構成矩形的偶數個誤碼檢測不出。√√√√√√√√√√√√√00√√√√表5-6水準垂直奇偶監督碼接收端檢錯示例01有可能檢測出偶數個誤碼。√√√√√√√√√√√00√√1√√××*4、恒比碼

每個碼組中含“1”和“0”的個數的比例恒定，又稱等重碼能檢測出所有1個和奇數個錯誤，並能部分檢測出偶數個錯誤（成對交換錯則檢測不出）簡單，適應於對字母或符號進行編碼5.3常用的簡單編碼

表5-7我國五單位保護電碼表（是一種五中取三碼）數字電碼數字電碼001101500111101011610101211001711100310110801110411010910011*5、正反碼

監督位數目與資訊位數目相同，且監督碼元與資訊碼元或者相同或者相反，取決於資訊序列中“1”的個數。電報通信用的正反碼的碼長n=10。資訊位k=5，監督位r=5。5.3常用的簡單編碼

*

碼組中資訊位有奇數個“1”，監督碼元與資訊碼元相同；碼組中資訊位有偶數個“1”，監督碼元與資訊碼元相反。5.3常用的簡單編碼

（1）正反碼編碼規則*

將接收碼組中資訊位與監督位按位模2加，得到合成碼組產生校驗碼組：接收碼組中資訊碼元有奇數個“1”，則校驗碼組=合成碼組，否則校驗碼組=合成碼組的反碼按照校驗碼組中“1”的個數進行判決及糾錯（表5-8）5.3常用的簡單編碼

（2）接收端解碼規則校驗碼組組成誤碼情況全為0無誤碼4個“1”，1個“0”資訊碼有一個錯碼，位置對應校驗碼組中“0”的位置1個“1”，4個“0”監督碼有一個錯碼，位置對應校驗碼組中“1”的位置其他錯碼多於1個表5-8正反碼檢錯糾錯判決規則*(1)若接收碼組為1100111001合成碼組為1100111001=00000因碼組中資訊碼元有奇數個“1”，校驗碼=00000判決為無錯傳輸(2)若接收碼組為1000111001

合成碼組1000111001=01000

因碼組中資訊碼元有偶數個“1”，則校驗碼組為10111；說明資訊碼元中第二位錯碼，給以糾正為1100111001[例5-1]

假設發送碼組為1100111001，分析各種正反碼判決糾錯情況。5.3常用的簡單編碼

(3)若接收碼組為1100101001：合成碼組10000；因碼組中資訊碼元有奇數個“1”，則校驗碼組為10000說明監督碼元中第一位錯碼(4)若接收碼組為1001111001：合成碼組01010；因碼組中資訊碼元有奇數個“1”，則校驗碼組為01010，說明錯碼多於1個碼長為10的正反碼能夠糾正1位差錯，並能檢測所有2位及以下的錯碼。*6、ISBN國際圖書統一編號InternationalStandardBookNumberISBN7-118-02481-3中國出版公司書名編號校驗位無誤碼，若不能被11整除，有誤碼5.3常用的簡單編碼

*7118024813891717192331323571524415877100131163198（模11）=05.3常用的簡單編碼

能被11整除，無誤碼。*5.4線性分組碼（重點）(1)分組碼：先將資訊碼分組，然後給每組信碼附加若干監督碼的編碼稱為分組碼，用符號(n,k)表示，k是資訊碼的位數，n是編碼組總位數，又稱為碼長，r=n-k為監督位數。(2)代數碼：建立在代數學基礎上的編碼稱為代數碼。例如奇偶校驗碼。

1、基本概念*(3)線性碼：線性碼中資訊位和監督位是按一組線性方程構成的。線性碼是一種代數碼。奇偶監督碼是最簡單的線性碼。(4)線性分組碼：資訊碼分組後，附加的監督碼和資訊碼由一些線性代數方程聯繫著的編碼稱為線性分組碼。5.4線性分組碼*2、線性分組碼的性質任意兩個許用碼組之和（逐位模2和）仍為一許用碼組，即具有封閉性。最小碼距=非零碼的最小碼重（1的個數）。5.4線性分組碼*以漢明碼為例來說明編碼原理。漢明碼是一種設計用來糾正一位錯碼且編碼效率較高的線性分組碼。（7，4）漢明碼的編碼效率為：

3、線性分組碼的編碼原理5.4線性分組碼*

發送端編碼：將一位監督碼元附加在資訊碼元後，使得碼元中“1”碼元個數為偶數。接收端解碼：計數接收碼組中“1”碼元個數是否為偶數，即計算：S=an-1+an-2+……+a0（模2加）（5.4-1）S=0認為沒錯，S=1認為有錯。（5.4-1）式稱為監督方程/監督關係式，S稱為校正子/校驗子/伴隨式（1）回憶奇偶監督偶校驗碼5.4線性分組碼*

監督位增加到2位：有兩個監督方程，兩個伴隨式；兩個伴隨式組合有四種（00表示無錯，01、10、11表示一位錯碼的三種可能位置）監督位增加到r位：可指示一位錯碼的（2r-1）個可能位置對於（n，k)分組碼，若希望用r=n-k個監督位構造出的r個監督關係式來指示一位錯碼的n種可能位置，則要求：

可以這樣來考慮2r-1≥n即2r≥k+r+1（5.4-2）5.4線性分組碼*欲糾正一位錯碼，由（5.4-2）式知r≥3。取r=3，則n=k+r=7設7位碼元為：a6a5

……a0；三個伴隨式：S1、S2、S3；可規定S1S2S3的八種組合與一位錯碼的對應關係（也可規定為另一種對應關係）：構造一（n，k)分組碼，k=4並能糾正一位錯碼(2)漢明碼的構造5.4線性分組碼*表5-9S1S2S3的八種組合與一位錯碼的對應關係5.4線性分組碼S1S2S3錯碼位置000無錯碼001a0010a1100a2011a3101a4110a5111a6資訊碼監督碼a6a5a4a3a2a1a0S1=a2+a4+a5+a6S2=a1+a3+a5+a6S3=a0+a3+a4+a6(5.4-3)監督方程:*（3）發端編碼的原則：

資訊碼元a6

、a5

、a4、a3來源於待編碼的資訊序列；

監督碼元a2

、a1、

a0的取值應根據資訊碼元按監督關係式來決定，即使前面三式中的S1、

S2

、S3均為0：5.4線性分組碼*a2=a4+a5+a6a1=a3+a5+a6a0=a3+a4+a6

給定資訊位後，根據上式算出各監督位，該編碼的所有碼組如表5-10：(5.4-4)a6+a5+a4+a2=0a6+a5+a3+a1=0a6+a4+a3+a0=0(5.4-5)5.4線性分組碼表5-10許用碼組*該漢明碼的編碼效率較高

R=k/n=4/7≈57%該碼的最小碼距為3，能糾正一個錯碼或檢測兩個錯碼設收到碼組0000011，按監督方程計算可得：S1=0，S2=1，S3=1；再根據校正子組合與一位錯碼位置的對應關係，可知錯碼發生在a3位，並加以糾正。00010115.4線性分組碼*（4）監督矩陣沿（7，4）漢明碼出發，式（5.4-4）可改寫成：1·a6+1·a5+1·a4+0·a3+1·a2+0·a1+0·a0=01·a6+1·a5+0·a4+1·a3+0·a2+1·a1+0·a0=01·a6+0·a5+1·a4+1·a3+0·a2+0·a1+1·a0=0寫成矩陣形式：(5.4-6)5.4線性分組碼*H稱為線性碼監督矩陣可化簡為：H·AT=0T

或A·HT=05.4線性分組碼*r×n階矩陣監督矩陣H確定了編碼時監督碼元與資訊碼元的關係把具有[P·Ir]形式的H矩陣稱為典型形式的監督矩陣，其中P為r×k階矩陣,Ir為r×r階單位方陣

H矩陣的各行應線性無關。矩陣若能寫成典型形式，則其各行一定線性無關監督矩陣H特點5.4線性分組碼*上式右部前面矩陣就是監督矩陣H中的P矩陣。(5)生成矩陣（5.4-5）式也可寫成矩陣形式，即(5.4-7)5.4線性分組碼*其中Q=PT可見，Q為k×r階矩陣。或寫成5.4線性分組碼*生成矩陣G：在Q矩陣的左邊加上一個k×k階矩陣，即5.4線性分組碼*k×n階矩陣編碼方法完全由生成矩陣G確定把具有[Ik·Q]形式的G矩陣稱為典型形式的生成矩陣，其中，Ik為k×k階單位方陣，Q為k×r階矩陣由典型生成矩陣產生的分組碼一定是系統碼G矩陣的各行應線性無關，每行均為許用碼組生成矩陣G特點5.4線性分組碼*[例5-2]已知（6，3）漢明碼的生成矩陣如下，(1)列出所有許用碼組;(2)最小碼距d0;(3)檢錯糾錯能力(4)編碼效率5.4線性分組碼（1）資訊碼編碼碼字碼重00000000000010011103010010011301101110141001001013101101011411011011041111110003（3）（4）（2）*設（7,4）線性碼的生成矩陣G為：當資訊位為0001時，（1）試求其後的監督位。（2）監督矩陣H5.4線性分組碼*解：（1）*（2）監督矩陣H根據生成矩陣和監督矩陣的關係：

G=[Ik·Q]，H=[P·Ir]其中P=QT，可得監督矩陣H為：*錯誤矩陣/錯誤圖樣E：設發送碼組為A，接收碼組為B，(6)校正子與檢錯則錯誤矩陣5.4線性分組碼*接收端計算校正子S，即S=BHT=(A+E)HT=AHT+EHT=0+EHT=EHT

可見校正子只與E有關，即錯誤圖樣與校正子之間有確定的關係，所以可從錯誤圖樣與校正子的關係表中確定錯碼位置，加以糾正。5.4線性分組碼*以（7，4）漢明碼為例設發送碼組A=（0001011）接收碼組B=（0000011）則收端解碼過程如下：①計算校正子②查表得a3為錯誤位置，即可糾正（0001011）5.4線性分組碼*5.4線性分組碼4、（7，4）漢明碼編譯碼仿真漢明碼編譯碼仿真*設A1和

A2為碼中任意兩許用碼組，則有 A1·HT=0 A2·HT=0 於是A1·HT+

A2·HT=（A1+

A2）·HT=0即（A1+

A2）必是該碼中一許用碼組[例5-3]

證明線性分組碼的封閉性。（略）p319：9-6作業5.4線性分組碼*5.5迴圈碼迴圈碼是一種重要的線性分組碼。這種碼的編碼和解碼設備都不太複雜，且有較強的檢（糾）錯能力。共n位。通常前k位為資訊位，後r位為監督位。5.5.1迴圈碼的編碼原理*迴圈碼的特點：

封閉性；

迴圈性；即碼中任一碼組迴圈一位(將最右端的碼元移到左端或反之）以後，仍為該碼中的一個碼組。5.5.1迴圈碼的編碼原理*若(an-1,an-2……,a1,a0)是一(n,k)迴圈碼的碼組，則(an-2,an-3,……,a1,a0,an-1)(an-3,an-4,……,a0,an-1,an-2)…………(a0,an-1,an-2,an-3,……,a2,a1)也都是該迴圈碼的碼組。5.5.1迴圈碼的編碼原理*表5-10一種（7，3）迴圈碼的全部碼字序號碼字

序號碼字資訊位a6a5a4監督位a3a2a1a0資訊位a6a5a4監督位a3a2a1a010

0

00

0

0

051

0

01

0

1

120

0

10

1

1

161

0

11

1

0

030

1

01

1

1

071

1

00

1

0

140

1

11

0

0

181

1

10

0

1

0把碼長為n的碼組中的各碼元當作n-1次多項式的係數若碼組A=（an-1，an-2，……，a1，a0)，則其相應的碼多項式為：

T(x)=an-1xn-1+an-1xn-1+……+a1x+a0對於（7，3）迴圈碼的任意碼組可表示為：

T(x)=a6x6+a5x5+a4x4+a3x3+a2x2+a1x+a0如碼組（1100101）對應的碼多項式可表示為T7(x)=1·x6+1·x5+0·x4+0·x3+1·x2+0·x+1=x6+x5+x2+11、碼多項式T(x)*碼多項式與碼組的關係：本質上是一回事，僅是表示方法的不同而已。對於二進位碼組，多項式的每個係數不是0就是1，x僅是碼元位置的標誌。因此，這裏並不關心x的取值。0+0=00+1=11+0=11+1=00*0=00*1=01*1=15.5.1迴圈碼的編碼原理*若一個整數m可以表示為:則在模n運算下，有m≡p（模n），同樣對於多項式而言：則可以寫為：F(x)≡R(x)（模N(x)）。即一任意多項式F(x)被一個n次多項式N(x)除，得到商式Q(x)和一個次數小於n的餘式R(x)5.5.1迴圈碼的編碼原理*例如碼組（1100101）對應的碼多項式可為：T7(x)=x6+x5+x2+1其被x3+1除得x6+x5+x2+1≡1（模x3+1）5.5.1迴圈碼的編碼原理*在迴圈碼中，若T(x)是一個長為n的許用碼組，則xi·T(x)在按模xn+1運算下，也是一許用碼組。即若

xi·T(x)≡Ti(x)（模xn+1）則Ti(x)也是一許用碼組，且為A(x)碼組向左迴圈移位i次的結果。重要結論5.5.1迴圈碼的編碼原理*例如：其對應的碼組為0101110，它正是表5-10中第3碼字。結論：一個碼長為n的(n，k)迴圈碼，它必為按模xn+1運算的一個餘式。5.5.1迴圈碼的編碼原理*

迴圈碼完全由其碼組長度n和生成多項式g(x)所決定問題：尋找構成生成矩陣的k個線性無關的許用碼組2、迴圈碼的生成多項式與生成矩陣5.5.1迴圈碼的編碼原理*（n，k)迴圈碼中一定能找到這樣一個碼組：前面的k-1位都是0，而第k位及第n位為1，其他各位gi為0或1：（000…01gn-k-1gn-k-2…g2g11)其對應的碼多項式為g(x)，且g(x)一定是碼中唯一的一個n-k次多項式，這唯一的n-k次多項式g(x)稱為碼的生成多項式5.5.1迴圈碼的編碼原理*可以證明生成多項式g(x)具有以下特性：（1）g(x)是一個常數項為1的次多項式；（2）g(x)是的一個因式；（3）該迴圈碼中其他碼多項式都是g(x)的倍式。

g(x)，xg(x)

…，xk-1g(x)5.5.1迴圈碼的編碼原理*g(x)，……，xk-1g(x)都是許用碼組，連同g(x)共k個許用碼組，構成碼的生成矩陣G(x)注：該生成矩陣並不是典型形式的，但可通過線性變換變換成典型的生成矩陣。5.5.1迴圈碼的編碼原理*一旦生成多項式g(x)確定以後，該迴圈碼的生成矩陣G(x)就可以確定，進而該迴圈碼的所有碼字就可以確定。生成矩陣G(x)的每一行都是一個碼組。5.5.1迴圈碼的編碼原理*[例5-4]試求（7，3）迴圈碼的生成多項式和生成矩陣。解1：對（7,3）迴圈碼，n=7，k=3,r=4由於g(x)是一個常數項為1的n-k次多項式，查表5-10知生成多項式為：g(x)=x4+x2+x+15.5.1迴圈碼的編碼原理*生成多項式g(x)是xn+1的一個因式，且g(x)是一個r次因式。因此，就可以先對xn+1進行因式分解，找到它的r次因式。下麵仍以（7，3）迴圈碼為例進行分析。5.5.1迴圈碼的編碼原理*解2：對（7,3）迴圈碼，n=7，k=3,r=4第一步：對x7+1進行因式分解得：x7+1=(x+1)(x3+x2+1)(x3+x+1).....(1)第二步：構造r次生成多項式g(x)。要從式（1）中找到r=n-k=4次的因數,這樣的因數有兩個：(x+1)(x3+x2+1)=x4+x2+x+1……………(a)(x+1)(x3+x+1)=x4+x3+x2+1……………(b)第三步：若按(a)構成生成多項式:生成多項式為：g(x)=x4+x2+x+1[例5-4]試求（7，3）迴圈碼的生成多項式和生成矩陣。將第1行與第3行模2加作為第1行，則有生成矩陣為：為典型生成矩陣若按(b)構成生成多項式:生成多項式為：g(x)=x4+x3+x2+1生成矩陣為：進行線性變換，得典型生成矩陣為：*已知（7，4）迴圈碼的全部碼組為：試寫出該迴圈碼的生成多項式g(x)和生成矩陣G，並將G化成典型矩陣。5.5.1迴圈碼的編碼原理*解：n=7，k=4，n-k=3上述碼組中的(n-k)=3次碼多項式為第2組，它所對應的碼多項式g(x)即為生成多項式：g(x)=x3+x+1。生成矩陣為：*3、迴圈碼的監督多項式與監督矩陣（略）其中

是

逆多項式1、方法1：5.5.1迴圈碼的編碼原理*[例5-5]試求（7，3）迴圈碼的監督多項式和監督矩陣。已知生成多項式g(x)=x4+x3+x2+1*方法2：根據生成矩陣和監督矩陣的關係求：

G=[Ik·Q]，H=[P·Ir]其中P=QT5.5.1迴圈碼的編碼原理*

首先從xn+1的因數中選一個（n-k）次多項式作為g(x)；然後，利用迴圈碼的編碼特點，即所有迴圈碼多項式T(x)都可以被g(x)整除，來定義生成多項式g(x)。5.5.2迴圈碼的編碼、解碼方法1、編碼方法（1）原理*設資訊位對應的多項式為m(x)用xn-k乘m(x)，相當於把資訊碼後附加上（n-k）個“0”（詳細解釋）用g(x)除xn-km(x)，得到餘式為r(x)編出碼組為：T(x)=xn-km(x)+r(x)(2)編碼步驟5.5.2迴圈碼的編碼、解碼方法*例如:資訊碼為110，它相當於m(x)＝x2+x。當n-k＝7-3＝4時，xn-k·m（x）＝x4·(x2+x)=x6+x5

，相當於1100000。而希望的到得系統迴圈碼多項式應當是T(x)=xn-k·m(x)+r(x)。5.5.2迴圈碼的編碼、解碼方法*即餘式r(x)=x2+1於是，對應碼組T(x)=xn-km(x)+r(x）=x6+x5+

x2+1編碼為1100101[例題]設（7，3）迴圈碼的生成多項式為g(x)=x4+x2+x+1，待編碼資訊位為110，求對應迴圈碼碼組。解：m(x)=x2+x，xn-km(x)=x4(x2+x)=x6+x55.5.2迴圈碼的編碼、解碼方法於是，以多項式形式表示的系統迴圈碼的生成矩陣為：其中