信息科學第五章2課件

差錯率：差錯率是衡量傳輸質(zhì)量的重要指標之一，它有以下幾種不同的定義。碼元差錯率：指在傳輸?shù)拇a元總數(shù)中發(fā)生差錯的碼元數(shù)所占的比例（平均值），簡稱誤碼率。比特差錯率

/比特誤碼率：指在傳輸?shù)谋忍乜倲?shù)中發(fā)生差錯的比特數(shù)所占的比例（平均值）。在二進制傳輸系統(tǒng)中，碼元差錯率就是比特差錯率。碼組差錯率：指在傳輸?shù)拇a組總數(shù)中發(fā)生差錯的碼組數(shù)所占的比例（平均值）。第五節(jié)糾錯編碼的基本思想根據(jù)不同的應(yīng)用場合對差錯率有不同的要求。在電報傳送時，允許的比特差錯率約為10－4～10－5；計算機數(shù)據(jù)傳輸，一般要求比特差錯率小于10－8～10－9；在遙控指令和武器系統(tǒng)的指令系統(tǒng)中，要求有更小的誤比特率或碼組差錯率。采用信道編碼的數(shù)字通信系統(tǒng)在某些情況下，信道的改善可能較困難或者不經(jīng)濟，這就要求采用信道編碼，以便滿足系統(tǒng)差錯率的技術(shù)指標要求。信道編碼為系統(tǒng)設(shè)計者提供了一個降低系統(tǒng)差錯率的措施。采用信道編碼后的數(shù)字通信系統(tǒng)可用圖6.1.2所示。二進制編碼信道模型：

R=C+E

(mod2)E：隨機變量；差錯圖案：隨機序列(Ei)；稱E=(E0,E1,…,En-1)中Ei=1為第i位上的一個隨機錯誤；第i至第j位之間有很多錯誤時，稱為一個j－i+1長的突發(fā)錯誤。(2)信道編碼的基本思想信道編碼的對象：是信源編碼器輸出的信息序列m。通常是二元符號1、0組成的序列。信道編碼的基本思想按一定規(guī)則給數(shù)字序列m增加一些多余的碼元，使不具有規(guī)律性的信息序列m變換為具有某種規(guī)律性的數(shù)碼序列C；碼序列中的信息序列碼元與多余碼元之間是相關(guān)的；信道譯碼器利用這種預(yù)知的編碼規(guī)則譯碼。檢驗接收到的數(shù)字序列R是否符合既定的規(guī)則，從而發(fā)現(xiàn)R中是否有錯，或者糾正其中的差錯；碼元的組成及其它們之間的關(guān)系信息碼組：數(shù)字序列m總是以k個碼元為一組傳輸，稱這k個碼元的碼組為信息碼組。例如遙控系統(tǒng)中的每個指令字，計算機中的每個字節(jié)。碼組/碼字：信道編碼器按一定的規(guī)則對每個信息碼組附加一些多余的碼元，構(gòu)成了n個碼元的碼組。監(jiān)督碼元/監(jiān)督元：附加的(n－k)

個碼元稱為該碼組的監(jiān)督碼元或監(jiān)督元。是否可用線性方程組來表示線性碼：編碼規(guī)則可以用線性方程表示；非線性碼：編碼規(guī)則不能用線性方程表示；按碼字的結(jié)構(gòu)分系統(tǒng)碼：前k個碼元與信息碼組一致；非系統(tǒng)碼：沒有系統(tǒng)碼的特性。按糾正差錯的類型可分為糾正隨機錯誤的碼和糾正突發(fā)錯誤的碼；按碼字中每個碼元的取值可分為二進制碼和多進制碼。(1)偶（或奇）校驗方法p為偶校驗位m0+m1+m2+…+mk－1+p=0(mod2)則C=(m0,m1,m2,…,mk－1,p)為一個偶校驗碼字。C中一定有偶數(shù)個“1”當差錯圖案E中有奇數(shù)個“1”，即R

中有奇數(shù)個位有錯時，可以通過校驗方程是否為0判斷有無可能傳輸差錯。(2)多個奇偶校驗位一個校驗位可以由信息位的部分或全部按校驗方程產(chǎn)生；例如C是一個對陣列消息進行垂直與水平校驗以及總校驗的碼字；其碼率為當校驗位數(shù)增加時，可以檢測到差錯圖案種類數(shù)也增加，同時碼率減小。(4)等重碼/定比碼設(shè)計碼字中的非0符號個數(shù)恒為常數(shù)，即C由全體重量恒等于m的n重向量組成。5中取3等重碼可以檢測出全部奇數(shù)位差錯，對某些碼字的傳輸則可以檢測出部分偶數(shù)位差錯。(1)差錯控制的基本方式前向糾錯(FEC)：發(fā)送端的信道編碼器將信息碼組編成具有一定糾錯能力的碼。接收端信道譯碼器對接收碼字進行譯碼，若傳輸中產(chǎn)生的差錯數(shù)目在碼的糾錯能力之內(nèi)時，譯碼器對差錯進行定位并加以糾正。自動請求重發(fā)(ARQ)：用于檢測的糾錯碼在譯碼器輸出端只給出當前碼字傳輸是否可能出錯的指示，當有錯時按某種協(xié)議通過一個反向信道請求發(fā)送端重傳已發(fā)送的碼字全部或部分?；旌霞m錯(HEC)：是FEC與ARQ方式的結(jié)合。發(fā)端發(fā)送同時具有自動糾錯和檢測能力的碼組，收端收到碼組后，檢查差錯情況，如果差錯在碼的糾錯能力以內(nèi)，則自動進行糾正。如果信道干擾很嚴重，錯誤很多，超過了碼的糾錯能力，但能檢測出來，則經(jīng)反饋信道請求發(fā)端重發(fā)這組數(shù)據(jù)。編碼增益實際的通信系統(tǒng)，信號的傳送需要一定的信噪比Eb/N0，它直接影響信道轉(zhuǎn)移概率的大小，誤碼率pbe與信噪比Eb/N0的關(guān)系如圖6.1.9所示，當采用糾錯碼之后，達到同樣的誤碼率需要的信噪比減小量稱為編碼增益。(1)一致監(jiān)督方程編碼就是給已知信息碼組按預(yù)定規(guī)則添加監(jiān)督碼元，以構(gòu)成碼字。在k個信息碼元之后附加r(r=n－k)個監(jiān)督碼元，使每個監(jiān)督元是其中某些信息元的模2和。舉例：k=3,r=4，構(gòu)成(7,3)線性分組碼。設(shè)碼字為(C6,C5,C4,C3,C2,C1,C0)C6,C5,C4為信息元，C3,C2,C1,C0為監(jiān)督元，每個碼元取“0”或“1”監(jiān)督元可按下面方程組計算一致監(jiān)督方程/一致校驗方程：確定信息元得到監(jiān)督元規(guī)則的一組方程稱為監(jiān)督方程/校驗方程。由于所有碼字都按同一規(guī)則確定，又稱為一致監(jiān)督方程/一致校驗方程。由于一致監(jiān)督方程是線性的，即監(jiān)督元和新信源之間是線性運算關(guān)系，所以由線性監(jiān)督方程所確定的分組碼是線性分組碼。(2)舉例信息碼組(101)，即C6=1,C5=0,C4=1代入監(jiān)督方程得：C3=0,C2=0,C1=1,C0=1由信息碼組(101)編出的碼字為(1010011)。其它7個碼字如表6.2.1。系數(shù)矩陣H的后四列組成一個(4×4)階單位子陣，用I4表示，H的其余部分用P表示推廣到一般情況：對(n,k)線性分組碼，每個碼字中的r(r=n－k)個監(jiān)督元與信息元之間的關(guān)系可由下面的線性方程組確定令上式的系數(shù)矩陣為H，碼字行陣列為CG中每一行g(shù)i=(gi1,gi2,…,gin)都是一個碼字；對每一個信息組m，由矩陣G都可以求得(n,k)線性碼對應(yīng)的碼字。(n,k)線性碼的每一個碼字都是生成矩陣G的行矢量的線性組合，所以它的2k個碼字構(gòu)成了由G的行張成的n維空間的一個k維子空間Vk。線性系統(tǒng)分組碼通過行初等變換，將G化為前k列是單位子陣的標準形式

(4)生成矩陣與一致監(jiān)督矩陣的關(guān)系由于生成矩陣G的每一行都是一個碼字，所以G的每行都滿足Hr×nCTn×1=0Tr×1，則有Hr×nGTn×k=0Tr×k

或Gk×nHTn×r=0k×r線性系統(tǒng)碼的監(jiān)督矩陣H和生成矩陣G之間可以直接互換。舉例已知(7,4)線性系統(tǒng)碼的監(jiān)督矩陣為(5)對偶碼對偶碼：對一個(n,k)線性碼CI，由于Hr×nGTn×k=0Tr×k，如果以G作監(jiān)督矩陣，而以H作生成矩陣，可構(gòu)造另一個碼CId，碼CId是一個(n,n－k)線性碼，稱碼CId為原碼的對偶碼。例如：(7,4)線性碼的對偶碼是(7,3)碼：(7,3)碼的監(jiān)督矩陣H(7,3)是(7,4)碼生成矩陣G(7,4)

(7,3)碼的生成矩陣G(7,3)是(7,4)碼監(jiān)督矩陣H(7,4)

(1)漢明重量和漢明球漢明距離/距離：在(n,k)線性碼中，兩個碼字U、V之間對應(yīng)碼元位上符號取值不同的個數(shù)，稱為碼字U、V之間的漢明距離。例如：(7,3)碼的兩個碼字U=0011101,V=0100111，它們之間第2、3、4和6位不同。因此，碼字U和V的距離為4。線性分組碼的一個碼字對應(yīng)于n維線性空間中的一點，碼字間的距離即為空間中兩對應(yīng)點的距離。漢明重量和漢明球漢明球：以碼字C為中心，半徑為t的漢明球是與C的漢明距離≤

t的向量全體SC(t)

線性分組碼的最小距離、檢錯和糾錯能力漢明重量/碼字重量/W：碼字中非0碼元符號的個數(shù)，稱為該碼字的漢明重量。在二元線性碼中，碼字重量就是碼字中含“1”的個數(shù)。最小重量/Wmin：線性分組碼CI中，非0碼字重量最小值，叫做碼CI的最小重量：Wmin=min{W(V),V∈CI,V≠0}最小距離與最小重量的關(guān)系：線性分組碼的最小距離等于它的最小重量。

(2)最小距離與檢、糾錯能力一般地說，線性碼的最小距離越大，意味著任意碼字間的差別越大，則碼的檢、糾錯能力越強。檢錯能力：如果一個線性碼能檢出長度≤l個碼元的任何錯誤圖樣，稱碼的檢錯能力為l。糾錯能力：如果線性碼能糾正長度≤t個碼元的任意錯誤圖樣，稱碼的糾錯能力為t。最小距離與糾錯能力：(n,k)線性碼能糾t個錯誤的充要條件是碼的最小距離為

幾何意義：最小距離與檢錯能力：(n,k)線性碼能夠發(fā)現(xiàn)l個錯誤的充要條件是碼的最小距離為dmin=l+1或l=dmin－1最小距離與檢、糾錯能力：(n,k)線性碼能糾t個錯誤，并能發(fā)現(xiàn)l個錯誤(l>t)的充要條件是碼的最小距離為dmin=t+l+1或t+l=dmin－1(1)伴隨式和錯誤檢測①用監(jiān)督矩陣編碼，也用監(jiān)督矩陣譯碼：接收到一個接收字R后，校驗HRT=0T是否成立：若關(guān)系成立，則認為R是一個碼字；否則判為碼字在傳輸中發(fā)生了錯誤；②伴隨式/監(jiān)督子/校驗子：S=RHT或ST=HRT。③如何糾錯？設(shè)發(fā)送碼矢C=(Cn－1,Cn－2,…,C0)信道錯誤圖樣為E=(En－1,En－2,…,E0)，其中Ei=0，表示第i位無錯；Ei=1，表示第i位有錯。i=n－1,n－2,…,0。接收字R為R=(Rn－1,Rn－2,…,R0)=C+E=(Cn－1+En－1,Cn－2+En－2,…,C0+E0)求接收字的伴隨式（接收字用監(jiān)督矩陣進行檢驗）ST=HRT=H(C+E)T=HCT+HET由于HCT=0T，所以ST=HET⑤舉例：(7,3)碼接收矢量R的伴隨式計算設(shè)發(fā)送碼矢C=1010011，接收碼字R＝1010011，R與C相同。若接收字中有一位錯誤當碼元錯誤多于1個時②標準陣列碼矢參數(shù)發(fā)送碼矢：取自于2k個碼字集合{C}；接收矢量：可以是2n個n重中任一個矢量。譯碼方法把2n個n重矢量劃分為2k個互不相交的子集，使得在每個子集中僅含一個碼矢；根據(jù)碼矢和子集間一一對應(yīng)關(guān)系，若接收矢量Rl落在子集Dl中，就把Rl譯為子集Dl含有的碼字Cl；當接收矢量R與實際發(fā)送碼矢在同一子集中時，譯碼就是正確的。標準陣列：是對給定的(n,k)線性碼，將2n個n重劃分為2k個子集的一種方法。標準陣列構(gòu)造方法先將2k個碼矢排成一行，作為標準陣列的第一行，并將全0碼矢C1=(00…0)放在最左面的位置上；然后在剩下的(2n－2k)

個n重中選取一個重量最輕的n重E2放在全0碼矢C1下面，再將E2分別和碼矢相加，放在對應(yīng)碼矢下面構(gòu)成陣列第二行在第二次剩下的n重中，選取重量最輕的n重E3，放在E2下面，并將E3分別加到第一行各碼矢上，得到第三行；…，繼續(xù)這樣做下去，直到全部n重用完為止。得到(n,k)線性碼的標準陣列。定理6.2.6(線性碼糾錯極限定理)：二元(n,k)線性碼能糾2n－k個錯誤圖樣。這2n－k個可糾的錯誤圖樣，包括0矢量在內(nèi)，即把無錯的情況也看成一個可糾的錯誤圖樣。陪集：標準陣列的每一行叫做碼的一個陪集。陪集首：每個陪集的第一個元素叫做陪集首。每一列包含2n－k個元素，最上面的是一個碼矢，其它元素是陪集首和該碼矢之和，例如第j列為若發(fā)送碼矢為Cj，信道干擾的錯誤圖樣是陪集首，則接收矢量R必在Dj

中；若錯誤圖樣不是陪集首，則接收矢量R不在Dj

中，則譯成其它碼字，造成錯誤譯碼；當且僅當錯誤圖樣為陪集首時，譯碼才是正確的。可糾正的錯誤圖樣：這2n－k個陪集首稱為可糾正的錯誤圖樣。線性碼糾錯能力與監(jiān)督元數(shù)目的關(guān)系：一個可糾t個錯誤的線性碼必須滿足

上式中等式成立時的線性碼稱為完備碼。即

定義：(n,k)線性碼的所有2n－k個伴隨式，在譯碼過程中若都用來糾正所有小于等于個隨機錯誤，以及部分大于t的錯誤圖樣，則這種譯碼方法稱為完備譯碼。限定距離譯碼：任一個(n,k)線性碼，能糾正個隨機錯誤，如果在譯碼時僅糾正t’<t個錯誤，而當錯誤個數(shù)大于t’時，譯碼器不進行糾錯而僅指出發(fā)生了錯誤，稱這種方法為限定距離譯碼。標準陣列譯碼=最小距離譯碼法=最佳譯碼法陪集首是可糾正的錯誤圖樣，為了使譯碼錯誤概率最小，應(yīng)選取出現(xiàn)概率最大的錯誤圖樣作陪集首；重量較輕的錯誤圖樣出現(xiàn)概率較大，所以在構(gòu)造標準陣列時是選取重量最輕的n重作陪集首；這樣，當錯誤圖樣為陪集首時（可糾的錯誤圖樣），接收矢量與原發(fā)送碼矢間的距離（等于陪集首）最??；因此，選擇重量最輕的元素作陪集首，按標準陣列譯碼就是按最小距離譯碼；所以標準陣列譯碼法也是最佳譯碼法。定理6.2.7：在標準陣列中，一個陪集的所有2k個n重有相同的伴隨式，不同的陪集伴隨式互不相同。

(1)不可檢錯誤概率pud令A(yù)i為碼的重量分布，表示重量為i的碼字個數(shù)，由于僅當錯誤圖樣與碼矢集合中的非0碼矢相同時，才不能檢出錯誤，所以線性分組碼的性能(2)譯碼錯誤概率pwe正確譯碼概率pwc：糾正小于等于t個差錯的概率譯碼錯誤概率pwe為漢明碼是漢明于1950年提出的糾一個錯誤的線性碼，也是第一個糾錯碼。由于它編碼簡單，因而是在通信系統(tǒng)和數(shù)據(jù)存儲系統(tǒng)中得到廣泛應(yīng)用的一類線性碼。漢明碼的結(jié)構(gòu)參數(shù)：糾一個錯誤的線性碼，其最小距離dmin=3；監(jiān)督矩陣任意兩列線性無關(guān)/