差错控制编码课件

*

差錯控制編碼

*9.1引言差錯控制編碼的基本方法在發送端被傳輸的資訊序列上附加一些監督碼元,這些多餘碼元與資訊碼元之間以某種確定的規則相互關聯(約束),接收端按照既定的規則檢驗資訊碼元與監督碼元之間的關係.*常用差錯控制方法檢錯重發前向糾錯發收檢錯碼應答信號發收糾錯碼*混合糾錯發收糾檢錯應答信號常用檢錯重發系統:停發等候重發,返回重發和選擇重發*停發等候重發12331TI23發接收ACKNAK發現錯誤這是一種半雙工的通信方式,原理簡單,效率低.*返回重發12345623456789…12345623456789…發接收發現錯誤NAK從碼組2開始重發(傳輸效率最高,需複雜的控制,收、發數據緩存)選擇重發789101112重發碼組2*9.2糾錯編碼的基本原理分類按差錯控制編碼的功能：檢錯碼、糾錯碼、糾刪碼。按資訊碼元和附加的監督碼元之間的檢驗關系：線性碼、非線性碼。按資訊碼元和監督碼元之間的約束方式：分組碼、卷積碼。*例：3位二進位數構成的碼組表示天氣全用用4種用2種全用用4種用2種000晴晴晴100雪001雲101霜陰010陰110霧雨011雨雲111雹雨*如不要檢（糾）錯，傳輸4種不同的資訊，用兩位碼組就夠了，這兩位碼代表所傳資訊，稱為資訊位，多增加的稱為監督位。將資訊碼分組，為每組信碼附加若干監督碼的編碼，稱為分組碼。在分組碼中，監督碼元僅監督本碼組的中的資訊碼元。分組碼用（n，k）表示，n—碼組長度，k—

資訊位數，n–k=r監督位數。1的數目稱為碼組的重量，兩個碼組對應位上數字不同的位數稱為碼組距離（漢明距離）。各碼組間距離的最小值為最小碼距d0

*d0的大小直接關係著編碼的檢，糾錯能力。為檢測e個錯碼，要求d0≥e+1為糾正t個錯碼，要求d0≥2t+1為糾正t個錯碼，同時檢測e個錯碼，要求

d0≥e+t+1Bd0BA12BA12BB345d0*AB1te若隨機通道中，發送“0”和發送“1”時的錯誤概率相等，為P，且P<<1,則碼長為n的碼組恰好發生r個錯碼的概率為:*當n=7P=10-3時P(1)≈7×10-3P(2)≈2.1×10-5

P(3)≈3.5×10-8

可見,採用差錯控制編碼,即使僅能糾正這種碼組中的1~2個錯誤,也可以使誤碼率下降幾個數量級.*9.3常用的簡單編碼奇偶監督碼無論資訊位有多少,監督位只有一位,使碼組中“1”的數目為偶(或奇)數.接收端這種碼能夠檢測奇數個錯碼,適用檢測隨機錯誤*二維奇偶監督碼把上述奇偶監督碼的若干碼組排列成矩陣,每一碼組寫成一行,然後,再按列的方向增加第二維監督位*恒比碼每個碼組均含有相同數目的“1”(和“0”).由於“1”的數目與“0”的數目之比保持恒定,故得此名.正反碼是一種簡單的能夠糾正錯碼的編碼,監督位數目與資訊位數目相同,監督位與資訊位相同或相反,由資訊碼中的“1”的個數而定.

*9.4線性分組碼線性分組碼中資訊碼元和監督碼元是用線性方程聯繫起來的.線性碼建立在代數學群論基礎上,線性碼各許用碼組的集合構成代數學中的群,因此,又稱群碼.主要性質任意兩許用碼組之和(模2和)仍為一許用碼組.(封閉性)碼的最小距離等於非零碼的最小重量*奇偶監督碼是一種最簡單的線性碼,偶校驗時S稱為校正子,又稱伴隨式.S=0無錯,S=1有錯.一般,由r個監督方程式計算得r個校正子,可以用來指示2r-1種錯誤,對於一位誤碼來說,就可以指示2r-1個誤碼位置.對於(n,k)碼,如果滿足2r-1≥n則可能構造出糾正一位或一位以上錯誤的線性碼.*設分組碼(n,k)中k=4,為糾正一位錯碼,要求r≥3,則n=k+r=7S1S2S3錯碼位置S1S2S3錯碼位置001a0101a4010a1110a5100a2111a6011a3000無錯*計算監督位判斷錯碼位置按上述方法構造的糾正單個錯誤的線性分組碼稱為漢明碼。碼長n=2r–1資訊位k=2r–1–r監督位r（1）（2）*編碼速率=（1）改寫為表示成矩陣形式=PIr*簡記為或H稱為監督矩陣，H確定，則編碼時監督位和資訊位的關係就完全確定了。

P為r×k階Ir為r×r階單位方陣具有[PIr]形式的H矩陣稱為典型陣。（2）改寫為：=*或Q生成矩陣GAG*具有形式的生成矩陣稱為典型生成矩陣。由典型生成矩陣得出的碼組A中，資訊位不變，監督位附加其後，這種碼稱為系統碼。*發送碼組A在傳輸過程中可能發生誤碼，設接收到的碼組為B=[bn-1bn-2…b0]則B–A=EE=[en-1en-2…e0]錯誤圖樣也可寫作B=A+E*接收端計算校正子為錯誤圖樣與校正子之間有確定的關係*例設且有3

个接收码组驗證3個接收碼組是否發生差錯？若在某碼組中有錯碼，錯碼的校正子是什麼？然後再指出發生錯碼的碼字中，哪位有錯？*解：1）若無錯，則錯誤圖樣為0，S為0

B1無錯B2錯B3錯2）∵S2=H第1列∴E=[100000]第1位錯同理S3=H第3列∴E=[001000]第3位錯*線性碼的重要性質封閉性任意許用兩個碼組之和仍為許用碼組兩個碼組之間的距離必是另一碼組的重量,故最小碼距即碼的最小重量(除全0碼外)*9.5迴圈碼

9.5.1迴圈碼原理迴圈碼是一種重要的線性分組碼,易於實現,性能較好.迴圈碼除具有線性碼的一般性質外,還具有迴圈性,即迴圈碼中任一碼組迴圈一位以後,仍為該碼中的一個碼組.一長為n的碼組可表示成碼多項式*碼多項式的按模運算

若F(x)=N(x)Q(x)+R(x)則F(x)≡R(x)(模N(x))

例*在迴圈碼中,若T(x)是一個長為n的許用碼組,則xiT(x)在按模xn+1運算下,也是一個許用碼組.即若則T′(x)也是一個許用碼組*在迴圈碼中，一個（n，k）碼有2k個不同碼組假設用g（x）表示一個前k-1位皆為0（第k位不為0）的碼組則

在迴圈碼中，除全0碼外，再沒有連續k位均為“0”的碼組，即連“0”的長度最多只能k-1位。因此g（x）必須是一個常數項不為“0”的n-k次多項式生成多項式*g(x),xg(x),x2g(x),…xk-1g(x)都是碼組,且線性無關,故迴圈碼的生成矩陣G可寫成假如輸入資訊碼元mk-1mk-2…m0則*所有碼多項式T(x)都可被g(x)整除,而且,任一次數不大於k-1的多項式乘g(x)都是碼多項式.生成多項式g(X)的確定∵T(x)=h(x)g(x)又g(x)為一個碼組,故xkg(x)在模xn+1運算下也為一碼組,故可寫成=1*故g(x)是xn+1的一個n–k次因式,此即尋找g(x)的方法.例都可作為(7,3)迴圈碼的生成多項式*9.5.2迴圈碼的編、解碼方法

編碼步驟根據給定的（n,k)選定生成多項式g(x),即從xn+1的因數中選一n-k次多項式作為g(x).所有碼多項式T(x)都可被g(x)整除,據此對給定的資訊位m(x)進行編碼.資訊碼後附加n-k個0

*監督位資訊位例(7,3)迴圈碼m(x)=x2+x,g(x)=x4+x2+

x+1解r(x)*a+b+cd+輸入m輸出feS（7，3）碼編碼器mabcdef00000001111011110011101010100010100000101100001000000011f=mf=e*迴圈碼的解碼將接收碼組R(x)用g(x)去除,若未發生錯誤,R(x)能被g(x)整除,發生錯誤則有餘項.*9.6卷積碼

在編碼器複雜性相同的情況下,卷積碼的性能優於分組碼.卷積碼把k個資訊位編n位,k和n通常很小,特別適宜於串行形式傳輸,延時小.n個碼元與當前段的k個資訊位有關,而且與前N-1段的資訊有關,編碼過程相互關聯的碼元為Nn個.N或nN稱為卷積碼的約束長度,常把卷積碼記作(n,k,N)*654321+輸入bici輸出bici卷積碼編碼器k=1,n=2,N=6*

b6b5b4b3b2b1+一級移存+S6S5S4S3S2S1+門限電路(2,1,6)卷積碼門限解碼器輸入bici重算ci輸出校正子“1”的個數≥3?*假定b1以前各碼元均未發生錯誤,則(1)*(1)式經線性變換這是一組正交於E(b1)的正交校驗方程,在所考察的12個碼元(b1~b6,c1~c6)中錯誤不多於2個的條件下,僅當E(b1)=1,(2)式才有可能有3個或3個以上方程等於1.門限電路門限設為3,此時,門限電路輸出“1”,糾正b1錯誤,同時送到受E(b1)影響的各級校正子移存器糾正其中錯誤.(2)*監督矩陣H

假定b1進入編碼器之前，各級移存器處於“0”狀態則即*

H1用矩陣表示為11001100001110000011101000001110101000001100101010000011

…nn-k*H1：截短監督矩陣

自第7行起，每行結構相同，只是每行的起始比上一行多兩個“0”。一般，卷積碼的截短監督矩陣形式為：*In-k

—n-k階單位方陣

Pi

—（n-k）×k矩陣

0—

n-k階全零方陣基本監督矩陣h=[PN0PN-10PN-20…P1In-k]只要給定h，H1隨之確定。*生成矩陣G

基本生成矩陣g

g=[IKQ10Q20Q3

…0QN]截短生成矩陣Ik

—k階單位方陣

Qi=PiT

—k×（n-k）矩陣

0—

k階全零方陣*卷積碼的圖解表示（3，1，3）卷積碼編碼器a狀態m1m2為00，b狀態m1m2為01，c狀態m1m2為10，d狀態m1m2為11。

M3M2M1++輸入序列

mjmjy1，jY2，j*（3，1，