一般概念一致監(jiān)督方程和一致監(jiān)督矩陣線性分組碼市公開課一等獎百校聯(lián)賽特等獎?wù)n件

5.1普通概念5.2一致監(jiān)督方程和一致監(jiān)督矩陣5.3線性分組碼生成矩陣5.4線性分組碼編碼5.5線性分組碼最小距離、檢錯和糾錯能力5.6線性分組碼譯碼5.7線性分組碼性能5.8漢明碼5.9由已知碼結(jié)構(gòu)新碼方法5.10線性分組碼碼限第5章線性分組碼1第1頁線性分組碼編碼：線性分組碼編碼過程分為兩步：把信息序列按一定長度分成若干信息碼組，每組由k位組成；編碼器按照預(yù)定線性規(guī)則(可由線性方程組要求)，把信息碼組變換成n重(n>k)碼字，其中(n－k)個附加碼元是由信息碼元線性運算產(chǎn)生。信息碼組長k位，有2k個不一樣信息碼組，則有2k個碼字與它們一一對應(yīng)。5.1普通概念2第2頁名詞解釋線性分組碼：經(jīng)過預(yù)定線性運算將長為k位信息碼組變換成n重碼字(n>k)。由2k個信息碼組所編成2k個碼字集合，稱為線性分組碼。碼矢：一個n重碼字能夠用矢量來表示C=(Cn－1,Cn－1,…,C1,C0)所以碼字又稱為碼矢。(n,k)線性碼：信息位長為k，碼長為n線性碼。編碼效率/編碼速率/碼率/傳信率：R=k/n。它說明了信道利用效率，R是衡量碼性能一個主要參數(shù)。5.1普通概念3第3頁(1)一致監(jiān)督方程編碼就是給已知信息碼組按預(yù)定規(guī)則添加監(jiān)督碼元，以組成碼字。在k個信息碼元之后附加r(r=n－k)個監(jiān)督碼元，使每個監(jiān)督元是其中一些信息元模2和。舉例：k=3,r=4，組成(7,3)線性分組碼。設(shè)碼字為(C6,C5,C4,C3,C2,C1,C0)C6,C5,C4為信息元，C3,C2,C1,C0為監(jiān)督元，每個碼元取“0”或“1”監(jiān)督元可按下面方程組計算5.2一致監(jiān)督方程和一致監(jiān)督矩陣4第4頁一致監(jiān)督方程/一致校驗方程：確定信息元得到監(jiān)督元規(guī)則一組方程稱為監(jiān)督方程/校驗方程。因為全部碼字都按同一規(guī)則確定，又稱為一致監(jiān)督方程/一致校驗方程。因為一致監(jiān)督方程是線性，即監(jiān)督元和信息元之間是線性運算關(guān)系，所以由線性監(jiān)督方程所確定分組碼是線性分組碼。5.2一致監(jiān)督方程和一致監(jiān)督矩陣5第5頁(2)舉例信息碼組(101)，即C6=1,C5=0,C4=1代入(5.1)得：C3=0,C2=0,C1=1,C0=1由信息碼組(101)編出碼字為(1010011)。其它7個碼字如表5.1。6.2一致監(jiān)督方程和一致監(jiān)督矩陣6第6頁(3)一致監(jiān)督矩陣為了運算方便，將式(5.1)監(jiān)督方程寫成矩陣形式，得式(5.2)可寫成H

CT=0T或

C

HT=0CT、HT、0T分別表示C、H、0轉(zhuǎn)置矩陣。5.2一致監(jiān)督方程和一致監(jiān)督矩陣7第7頁系數(shù)矩陣H后四列組成一個(4×4)階單位子陣，用I4表示，H其余部分用P表示5.2一致監(jiān)督方程和一致監(jiān)督矩陣8第8頁推廣到普通情況：對(n,k)線性分組碼，每個碼字中r(r=n－k)個監(jiān)督元與信息元之間關(guān)系可由下面線性方程組確定5.2一致監(jiān)督方程和一致監(jiān)督矩陣9第9頁令上式系數(shù)矩陣為H，碼字行陣列為C5.2一致監(jiān)督方程和一致監(jiān)督矩陣10第10頁(4)一致監(jiān)督矩陣特征對H各行實施初等變換，將后面r列化為單位子陣，于是得到下面矩陣，行變換所得方程組與原方程組同解。監(jiān)督矩陣H標準形式：后面r列是一單位子陣監(jiān)督矩陣H。H陣每一行都代表一個監(jiān)督方程，它表示與該行中“1”相對應(yīng)碼元模2和為0。5.2一致監(jiān)督方程和一致監(jiān)督矩陣11第11頁H標準形式還說明了對應(yīng)監(jiān)督元是由哪些信息元決定。比如(7,3)碼H陣第一行為(1011000)，說明此碼第一個監(jiān)督元等于第一個和第三個信息元模2和，依這類推。

H陣r行代表了r個監(jiān)督方程，也表示由H所確定碼字有r個監(jiān)督元。為了得到確定碼，r個監(jiān)督方程（或H陣r行）必須是線性獨立，這要求H陣秩為r。若把H陣化成標準形式，只要檢驗單位子陣秩，就能方便地確定H陣本身秩。5.2一致監(jiān)督方程和一致監(jiān)督矩陣12第12頁(1)線性碼封閉性線性碼封閉性：線性碼任意兩個碼字之和仍是一個碼字。定理5.1：設(shè)二元線性分組碼CI(CI表示碼字集合)是由監(jiān)督矩陣H所定義，若U和V為其中任意兩個碼字，則U+V也是CI中一個碼字。[證實]：因為U和V是碼CI中兩個碼字，故有HUT=0T，HVT=0T那么H(U+V)T=H(UT+VT)=HUT+HVT=0T即U+V滿足監(jiān)督方程，所以U+V一定是一個碼字。一個長為n二元序列能夠看作是GF(2)(二元域)上n維線性空間中一點。長為n全部2n個矢量集合組成了GF(2)上n維線性空間Vn。把線性碼放入線性空間中進行研究，將使許多問題簡化而比較輕易處理。(n,k)線性碼是n維線性空間Vn中一個k維子空間Vk。5.3線性分組碼生成矩陣13第13頁(2)線性分組碼生成矩陣在由(n,k)線性碼組成線性空間Vn

k維子空間中，一定存在k個線性獨立碼字：g1,g2,…,gk,。碼CI中其它任何碼字C都能夠表為這k個碼字一個線性組合，即5.3線性分組碼生成矩陣14第14頁G中每一行g(shù)i=(gi1,gi2,…,gin)都是一個碼字；對每一個信息組m，由矩陣G都能夠求得(n,k)線性碼對應(yīng)碼字。生成矩陣：因為矩陣G生成了(n,k)線性碼，稱矩陣G為(n,k)線性碼生成矩陣。(n,k)線性碼每一個碼字都是生成矩陣G行矢量線性組合，所以它2k個碼字組成了由G行張成n維空間一個k維子空間Vk。5.3線性分組碼生成矩陣15第15頁線性系統(tǒng)分組碼經(jīng)過行初等變換，將G化為前k列是單位子陣標準形式

5.3線性分組碼生成矩陣16第16頁線性系統(tǒng)分組碼：用標準生成矩陣Gk×n

編成碼字，前面k位為信息數(shù)字，后面r=n－k位為校驗字，這種信息數(shù)字在前校驗數(shù)字在后線性分組碼稱為線性系統(tǒng)分組碼。當生成矩陣G確定之后，(n,k)線性碼也就完全被確定了，只要找到碼生成矩陣，編碼問題也一樣被處理了。5.3線性分組碼生成矩陣17第17頁(3)舉例(7,4)線性碼生成矩陣為5.3線性分組碼生成矩陣18第18頁(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之間能夠直接交換。5.3線性分組碼生成矩陣19第19頁舉例已知(7,4)線性系統(tǒng)碼監(jiān)督矩陣為5.3線性分組碼生成矩陣20第20頁(5)對偶碼對偶碼：對一個(n,k)線性碼CI，因為Hr×nGTn×k=0Tr×k，假如以G作監(jiān)督矩陣，而以H作生成矩陣，可結(jié)構(gòu)另一個碼CId，碼CId是一個(n,n－k)線性碼，稱碼CId為原碼對偶碼。比如：(7,4)線性碼對偶碼是(7,3)碼：(7,3)碼監(jiān)督矩陣H(7,3)是(7,4)碼生成矩陣G(7,4)

5.3線性分組碼生成矩陣21第21頁(7,3)碼生成矩陣G(7,3)是(7,4)碼監(jiān)督矩陣H(7,4)

5.3線性分組碼生成矩陣22第22頁(n,k)線性碼編碼就是依據(jù)線性碼監(jiān)督矩陣或生成矩陣將長為k信息組變換成長為n(n>k)碼字。利用監(jiān)督矩陣結(jié)構(gòu)(7,3)線性分組碼編碼電路：設(shè)碼字矢量為C=(C6C5C4C3C2C1C0)碼監(jiān)督矩陣為5.4線性分組碼編碼23第23頁依據(jù)方程組可直接畫出(7,3)碼并行編碼電路行串行編碼電路，如圖5.2。5.4線性分組碼編碼24第24頁(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)點距離。所以，碼字間距離滿足普通距離公理：5.5線性分組碼最小距離、檢錯和糾錯能力25第25頁最小距離/dmin：在(n,k)線性碼碼字集合中，任意兩個碼字間距離最小值，叫做碼最小距離。若C(i)和C(j)是任意兩個碼字，則碼最小距離表示為碼最小距離是衡量碼抗干擾能力（檢、糾錯能力）主要參數(shù)。碼最小距離越大，碼抗干擾能力就越強。漢明球：以碼字C為中心，半徑為t漢明球是與C漢明距離≤

t向量全體SC(t)

任意兩個漢明球不相交最大程度取決于任意兩個碼字之間最小漢明距離dmin。5.5線性分組碼最小距離、檢錯和糾錯能力26第26頁

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

[證實]：設(shè)線性碼CI，且U∈CI,V∈CI，又設(shè)U－V=Z，由線性碼封閉性知，Z∈CI。所以，d(U,V)=W(Z)，由此可推知，線性分組碼最小距離必等于非0碼字最小重量。5.5線性分組碼最小距離、檢錯和糾錯能力28第28頁(2)最小距離與檢、糾錯能力普通地說，線性碼最小距離越大，意味著任意碼字間差異越大，則碼檢、糾錯能力越強。檢錯能力：假如一個線性碼能檢出長度≤l個碼元任何錯誤圖樣，稱碼檢錯能力為l。糾錯能力：假如線性碼能糾正長度≤t個碼元任意錯誤圖樣，稱碼糾錯能力為t。5.5線性分組碼最小距離、檢錯和糾錯能力29第29頁最小距離與糾錯能力：(n,k)線性碼能糾t個錯誤充要條件是碼最小距離為

[證實]：設(shè)：發(fā)送碼字為V；接收碼字為R；U為任意其它碼字；則：矢量V、R、U間滿足距離三角不等式，

d(R,V)+d(R,U)≥d(U,V)(5.16)設(shè)：信道干擾使碼字中碼元發(fā)生錯誤實際個數(shù)為t’，且t’≤td(R,V)＝t’≤t(5.17)因為d(U,V)≥dmin=2t+1，代入式(5.16)得d(R,U)≥d(U,V)－d(R,V)=2t+1－t’>t(5.18)5.5線性分組碼最小距離、檢錯和糾錯能力30第30頁

上式表明：假如接收字R中錯誤個數(shù)t’≤t，那么接收字R和發(fā)送字V間距離≤t，而與其它任何碼字間距離都大于t，按最小距離譯碼把R譯為V。此時譯碼正確，碼字中錯誤被糾正。

幾何意義：5.5線性分組碼最小距離、檢錯和糾錯能力31第31頁最小距離與檢錯能力：(n,k)線性碼能夠發(fā)覺l個錯誤充要條件是碼最小距離為

dmin=l+1或l=dmin－1(5.19)[證實]：設(shè)：發(fā)送碼字為V；接收碼字為R；U為任意其它碼字；則：矢量V、R、U間滿足距離三角不等式，

d(R,V)+d(R,U)≥d(U,V)(5.20)設(shè)：信道干擾使碼字中碼元發(fā)生錯誤實際個數(shù)為l’，且l’≤ld(R,V)＝l’≤l(5.21)因為d(U,V)≥dmin=l+1，代入式(6.2.20)得d(R,U)≥d(U,V)－d(R,V)=l+1－l’>0

(5.22)5.5線性分組碼最小距離、檢錯和糾錯能力32第32頁

上式表明：因為接收字R與其它任何碼字U距離都大于0，則說明接收字R不會因發(fā)生l’個錯誤變?yōu)槠渌a字，因而必能發(fā)覺錯誤。

幾何意義：5.5線性分組碼最小距離、檢錯和糾錯能力33第33頁最小距離與檢、糾錯能力：(n,k)線性碼能糾t個錯誤，并能發(fā)覺l個錯誤(l>t)充要條件是碼最小距離為

dmin=t+l+1或t+l=dmin－1(5.23)[證實]：因為dmin>2t+1，依據(jù)最小距離與糾錯能力定理，該碼可糾t個錯誤。因為dmin>l+1，依據(jù)最小距離與檢錯能力定理，該碼有檢l個錯誤能力。糾錯和檢錯不會發(fā)生混同：設(shè)發(fā)送碼字為V，接收字為R，實際錯誤數(shù)為l’，且t<l’≤l。這時R與其它任何碼字U距離

d(R,U)≥d(U,V)－d(R,V)=t+l+1－l’>t+1>t(5.24)因而不會把R誤糾為U。5.5線性分組碼最小距離、檢錯和糾錯能力34第34頁

幾何意義：5.5線性分組碼最小距離、檢錯和糾錯能力35第35頁5.5線性分組碼最小距離、檢錯和糾錯能力36第36頁當(n,k)線性碼最小距離dmin給定后，可按實際需要靈活安排糾錯數(shù)目。比如，對dmin=8碼，可用來糾3檢4錯，或糾2檢5錯，或糾1檢6錯，或者只用于檢7個錯誤。5.5線性分組碼最小距離、檢錯和糾錯能力37第37頁(3)線性碼最小距離與監(jiān)督矩陣關(guān)系定理5.2：設(shè)H為(n,k)線性碼一致監(jiān)督矩陣，若H中任意S列線性無關(guān)，而H中存在(S+1)列線性相關(guān)，則碼最小距離為(S+1)。（矩陣H秩為S）定理5.3：若碼最小距離為(S+1)，則該碼監(jiān)督矩陣任意S列線性無關(guān)，而必存在有相關(guān)(S+1)列。定理5.4：在二元線性碼監(jiān)督矩陣H中，假如任一列都不是全“0”，且任兩列都不相等，則該碼能糾一個錯誤。5.5線性分組碼最小距離、檢錯和糾錯能力38第38頁(1)伴隨式和錯誤檢測①用監(jiān)督矩陣編碼，也用監(jiān)督矩陣譯碼：接收到一個接收字R后，校驗H

RT=0T是否成立：若關(guān)系成立，則認為R是一個碼字；不然判為碼字在傳輸中發(fā)生了錯誤；H

RT值是否為0是校驗碼字犯錯是否依據(jù)。②伴隨式/監(jiān)督子/校驗子：S=R

HT或ST=H

RT。③怎樣糾錯？設(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。5.6線性分組碼譯碼39第39頁接收字R為R=(Rn－1,Rn－2,…,R0)=C+E=(Cn－1+En－1,Cn－2+En－2,…,C0+E0)求接收字伴隨式（接收字用監(jiān)督矩陣進行檢驗）ST=H

RT=H

(C+E)T=H

CT+H

ET

(5.25)因為H

CT=0T，所以ST=H

ET設(shè)H=(h1,h2,…,hn)，其中hi表示H列。代入式(5.25)得到5.6線性分組碼譯碼40第40頁④總結(jié)伴隨式僅與錯