信息論與編碼原理-第8章-線性分組碼

信息論與編碼原理_第8章_線性分組碼第一頁(yè)，共125頁(yè)。第8章線性分組碼8.1一般概念8.2一致監(jiān)督方程和一致監(jiān)督矩陣8.3線性分組碼的生成矩陣8.4線性分組碼的編碼8.5線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力8.6線性分組碼的譯碼8.7線性分組碼的性能8.8漢明碼8.9由已知碼構(gòu)造新碼的方法8.10GSM的信道編碼總體方案8.11線性分組碼的碼限第二頁(yè)，共125頁(yè)。8.1一般概念(1)線性分組碼的編碼：編碼過程分為兩步：把信息序列按一定長(zhǎng)度分成若干信息碼組,每組由k位組成;編碼器按照預(yù)定的線性規(guī)則（可由線性方程組規(guī)定），把信息碼組變換成n重（n>k）碼字，其中(n－k)個(gè)附加碼元是由信息碼元的線性運(yùn)算產(chǎn)生的。(2)線性分組碼的碼字?jǐn)?shù)：信息碼組長(zhǎng)k位，有2k個(gè)不同的信息碼組，有2k個(gè)碼字與它們一一對(duì)應(yīng)。第三頁(yè)，共125頁(yè)。8.1一般概念(3)術(shù)語(yǔ)線性分組碼：通過預(yù)定的線性運(yùn)算將長(zhǎng)為k位的信息碼組變換成n重的碼字(n>k)。由2k個(gè)信息碼組所編成的2k個(gè)碼字集合，稱為線性分組碼。碼矢：一個(gè)n重的碼字可以用矢量來表示：C=(cn－1,cn－1,…,c1,c0)(n,k)線性碼：信息位長(zhǎng)為k，碼長(zhǎng)為n的線性碼。編碼效率/編碼速率/碼率/傳信率：R=k/n。它說明了信道的利用效率，R是衡量碼性能的一個(gè)重要參數(shù)。返回目錄第四頁(yè)，共125頁(yè)。8.2一致監(jiān)督方程和一致監(jiān)督矩陣(1)一致監(jiān)督方程(2)舉例(3)一致監(jiān)督矩陣(4)一致監(jiān)督矩陣特性第五頁(yè)，共125頁(yè)。8.2一致監(jiān)督方程和一致監(jiān)督矩陣(1)一致監(jiān)督方程構(gòu)成碼字的方法：編碼是給已知信息碼組按預(yù)定規(guī)則添加監(jiān)督碼元，構(gòu)成碼字。在k個(gè)信息碼元之后附加r(r=n－k)個(gè)監(jiān)督碼元，使每個(gè)監(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)督元，每個(gè)碼元取“0”或“1”監(jiān)督元按下面方程組計(jì)算：第六頁(yè)，共125頁(yè)。8.2一致監(jiān)督方程和一致監(jiān)督矩陣(1)一致監(jiān)督方程一致監(jiān)督方程/一致校驗(yàn)方程：確定信息元得到監(jiān)督元規(guī)則的一組方程稱為監(jiān)督方程/校驗(yàn)方程。由于所有碼字都按同一規(guī)則確定，又稱為一致監(jiān)督方程/一致校驗(yàn)方程。為什么叫線性分組碼？由于一致監(jiān)督方程是線性的，即監(jiān)督元和信息元之間是線性運(yùn)算關(guān)系，所以由線性監(jiān)督方程所確定的分組碼是線性分組碼。返回目錄第七頁(yè)，共125頁(yè)。8.2一致監(jiān)督方程和一致監(jiān)督矩陣(2)舉例信息碼組(101)，即c6=1,c5=0,c4=1代入(7.2.1)得：c3=0,c2=0,c1=1,c0=1由信息碼組(101)編出的碼字為(1010011)。其它7個(gè)碼字如表8.2.1。返回目錄第八頁(yè)，共125頁(yè)。8.2一致監(jiān)督方程和一致監(jiān)督矩陣(3)一致監(jiān)督矩陣為了運(yùn)算方便，將式(7.2.1)監(jiān)督方程寫成矩陣形式，得：將式(8.2.2)可寫成：H

·CT=0T

或

C·HT=0CT、HT、0T分別表示C、H、0的轉(zhuǎn)置矩陣。第九頁(yè)，共125頁(yè)。8.2一致監(jiān)督方程和一致監(jiān)督矩陣(3)一致監(jiān)督矩陣系數(shù)矩陣H的后四列組成一個(gè)(4×4)階單位子陣，用I4表示，H的其余部分用P表示：第十頁(yè)，共125頁(yè)。8.2一致監(jiān)督方程和一致監(jiān)督矩陣(3)一致監(jiān)督矩陣推廣到一般情況：對(duì)(n,k)線性分組碼，每個(gè)碼字中的r(r=n－k)個(gè)監(jiān)督元與信息元之間的關(guān)系可由下面的線性方程組確定：返回第十一頁(yè)，共125頁(yè)。8.2一致監(jiān)督方程和一致監(jiān)督矩陣(3)一致監(jiān)督矩陣令上式的系數(shù)矩陣為H，碼字行陣列為C：返回目錄第十二頁(yè)，共125頁(yè)。(4)一致監(jiān)督矩陣特性對(duì)H各行實(shí)行初等變換，將后面r列化為單位子陣，得到下面矩陣，行變換所得方程組與原方程組同解。監(jiān)督矩陣H的標(biāo)準(zhǔn)形式：后面r列是一單位子陣的監(jiān)督矩陣H。8.2一致監(jiān)督方程和一致監(jiān)督矩陣第十三頁(yè)，共125頁(yè)。(4)一致監(jiān)督矩陣特性

H標(biāo)準(zhǔn)形式的特性H陣的每一行都代表一個(gè)監(jiān)督方程，它表示與該行中“1”相對(duì)應(yīng)的碼元的模2和為0。

H的標(biāo)準(zhǔn)形式表明了相應(yīng)的監(jiān)督元是由哪些信息元決定的。例如(7,3)碼的H陣的第一行為(1011000)，說明第一個(gè)監(jiān)督元等于第一個(gè)和第三個(gè)信息元的模2和，依此類推。

H陣的r行代表了r個(gè)監(jiān)督方程，由H所確定的碼字有r個(gè)監(jiān)督元。為了得到確定的碼，r個(gè)監(jiān)督方程（或H陣的r行）必須是線性獨(dú)立的，這要求H陣的秩為r。若把H陣化成標(biāo)準(zhǔn)形式，只要檢查單位子陣的秩，就能方便地確定H陣本身的秩。8.2一致監(jiān)督方程和一致監(jiān)督矩陣參見方程返回目錄第十四頁(yè)，共125頁(yè)。8.3線性分組碼的生成矩陣(1)線性碼的封閉性(2)線性分組碼的生成矩陣(3)生成矩陣與一致監(jiān)督矩陣的關(guān)系(4)對(duì)偶碼第十五頁(yè)，共125頁(yè)。(1)線性碼的封閉性

線性碼的封閉性：線性碼任意兩個(gè)碼字之和仍是一個(gè)碼字。定理7.3.1：設(shè)二元線性分組碼CI(CI表示碼字集合)是由監(jiān)督矩陣H所定義的，若U和V為其中的任意兩個(gè)碼字，則U+V也是CI中的一個(gè)碼字.[證明]：由于U和V是碼CI中的兩個(gè)碼字，故有：HUT=0THVT=0T，那么H(U+V)T=H(UT+VT)=HUT+HVT=0T即U+V滿足監(jiān)督方程，所以U+V一定是一個(gè)碼字。一個(gè)長(zhǎng)為n的二元序列可以看作是GF(2)(二元域)上的n維線性空間中的一點(diǎn)。所有2n個(gè)矢量集合構(gòu)成了GF(2)上的n維線性空間Vn。把線性碼放入線性空間中進(jìn)行研究，將使許多問題簡(jiǎn)化而比較容易解決。(n,k)線性碼是n維線性空間Vn中的一個(gè)k維子空間Vk。8.3線性分組碼的生成矩陣返回目錄第十六頁(yè)，共125頁(yè)。(2)線性分組碼的生成矩陣生成矩陣的來由：在由(n,k)線性碼構(gòu)成的線性空間Vn的k維子空間中，一定存在k個(gè)線性獨(dú)立的碼字：g1,g2,…,gk。碼CI中其它任何碼字C都可以表為這k個(gè)碼字的一種線性組合，即：8.3線性分組碼的生成矩陣第十七頁(yè)，共125頁(yè)。(2)線性分組碼的生成矩陣生成矩陣定義：由于矩陣G生成了(n,k)線性碼，稱矩陣G為(n,k)線性碼的生成矩陣。8.3線性分組碼的生成矩陣第十八頁(yè)，共125頁(yè)。(2)線性分組碼的生成矩陣

生成矩陣G的特性G中每一行g(shù)i=(gi1,gi2,…,gin)都是一個(gè)碼字；對(duì)每一個(gè)信息組m，由矩陣G都可以求得(n,k)線性碼對(duì)應(yīng)的碼字。(n,k)線性碼的每一個(gè)碼字都是生成矩陣G的行矢量的線性組合，所以它的2k個(gè)碼字構(gòu)成了由G的行張成的n維空間的一個(gè)k維子空間Vk。8.3線性分組碼的生成矩陣第十九頁(yè)，共125頁(yè)。(2)線性分組碼的生成矩陣

線性系統(tǒng)分組碼

線性系統(tǒng)分組碼的構(gòu)成：通過行初等變換，將G化為前k列是單位子陣的標(biāo)準(zhǔn)形式。8.3線性分組碼的生成矩陣第二十頁(yè)，共125頁(yè)。(2)線性分組碼的生成矩陣

線性系統(tǒng)分組碼

線性系統(tǒng)分組碼定義：用標(biāo)準(zhǔn)生成矩陣Gk×n

編成的碼字，前面k位為信息位，后面r=n－k位為校驗(yàn)位，這種信息位在前校驗(yàn)位在后的線性分組碼稱為線性系統(tǒng)分組碼。當(dāng)生成矩陣G確定之后，(n,k)線性碼也就完全被確定了，只要找到碼的生成矩陣，編碼問題也同樣被解決了。8.3線性分組碼的生成矩陣第二十一頁(yè)，共125頁(yè)。(2)線性分組碼的生成矩陣舉例：(7,4)線性碼的生成矩陣為：8.3線性分組碼的生成矩陣返回目錄第二十二頁(yè)，共125頁(yè)。(3)生成矩陣與一致監(jiān)督矩陣的關(guān)系由于生成矩陣G的每一行都是一個(gè)碼字，所以G的每行都滿足：Hr×n(C1×n)T=(01×r)T，則有：Hr×n(Gk×n)T=(0k×r)T

或Gk×n(Hr×n)T=0k×r線性系統(tǒng)碼的監(jiān)督矩陣H和生成矩陣G之間可以直接互換。8.3線性分組碼的生成矩陣第二十三頁(yè)，共125頁(yè)。(3)生成矩陣與一致監(jiān)督矩陣的關(guān)系由于生成矩陣G的每一行都是一個(gè)碼字，所以G的每行都滿足：Hr×n(C1×n)T=(01×r)T，則有：Hr×n(Gk×n)T=(0k×r)T

或Gk×n(Hr×n)T=0k×r線性系統(tǒng)碼的監(jiān)督矩陣H和生成矩陣G之間可以直接互換。8.3線性分組碼的生成矩陣第二十四頁(yè)，共125頁(yè)。(3)生成矩陣與一致監(jiān)督矩陣的關(guān)系舉例：已知(7,4)線性系統(tǒng)碼的監(jiān)督矩陣為：8.3線性分組碼的生成矩陣QQT返回目錄第二十五頁(yè)，共125頁(yè)。(4)對(duì)偶碼

對(duì)偶碼：對(duì)一個(gè)(n,k)線性碼CI，由于Hr×n(Gk×n)T=(0k×r)T，如果以G作監(jiān)督矩陣，而以H作生成矩陣，可構(gòu)造另一個(gè)碼CId，CId是一個(gè)(n,n－k)線性碼，稱碼CId為原碼的對(duì)偶碼.

例如：(7,4)線性碼的對(duì)偶碼是(7,3)碼：(7,3)碼的生成矩陣G(7,3)是(7,4)碼監(jiān)督矩陣H(7,4)

8.3線性分組碼的生成矩陣返回目錄第二十六頁(yè)，共125頁(yè)。

(n,k)線性碼的編碼：根據(jù)線性碼的監(jiān)督矩陣或生成矩陣將長(zhǎng)為k的信息組變換成長(zhǎng)為n(n>k)的碼字。利用監(jiān)督矩陣構(gòu)造(7,3)線性分組碼的編碼電路設(shè)碼字為：C=(c6c5c4c3c2c1c0)碼的監(jiān)督矩陣為：8.4線性分組碼的編碼第二十七頁(yè)，共125頁(yè)。利用監(jiān)督矩陣構(gòu)造(7,3)線性分組碼的編碼電路：根據(jù)上面方程組可直接畫出(7,3)碼的并行編碼電路和串行編碼電路:8.4線性分組碼的編碼返回目錄第二十八頁(yè)，共125頁(yè)。8.5線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力(1)漢明距離、漢明重量和漢明球(2)最小距離與檢、糾錯(cuò)能力(3)線性碼的最小距離與監(jiān)督矩陣的關(guān)系第二十九頁(yè)，共125頁(yè)。(1)漢明距離、漢明重量和漢明球

漢明距離（距離）：在(n,k)線性碼中，兩個(gè)碼字U、V之間對(duì)應(yīng)碼元位上符號(hào)取值不同的個(gè)數(shù)，稱為碼字U、V之間的漢明距離。線性分組碼的一個(gè)碼字對(duì)應(yīng)于n維線性空間中的一點(diǎn)，碼字間的距離即為空間中兩對(duì)應(yīng)點(diǎn)的距離。因此，碼字間的距離滿足一般距離公理：8.5線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力第三十頁(yè)，共125頁(yè)。(1)漢明距離、漢明重量和漢明球

最小距離dmin：在(n,k)線性碼的碼字集合中，任意兩個(gè)碼字間距離最小值，叫做碼的最小距離。若C(i)和C(j)是任意兩個(gè)碼字，則碼的最小距離表示為：碼的最小距離是衡量碼的抗干擾能力（檢、糾錯(cuò)能力）的重要參數(shù)。碼的最小距離越大，碼的抗干擾能力就越強(qiáng)。8.5線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力第三十一頁(yè)，共125頁(yè)。(1)漢明距離、漢明重量和漢明球漢明球：以碼字C為中心，半徑為t的漢明球是與C的漢明距離≤t的向量全體SC(t)：任意兩個(gè)漢明球不相交最大程度取決于任意兩個(gè)碼字之間的最小漢明距離dmin。8.5線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力第三十二頁(yè)，共125頁(yè)。(1)漢明距離、漢明重量和漢明球漢明球：8.5線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力返回第三十三頁(yè)，共125頁(yè)。(1)漢明距離、漢明重量和漢明球漢明重量（碼字重量）W：碼字中非0碼元符號(hào)的個(gè)數(shù)，稱為該碼字的漢明重量。在二元線性碼中，碼字重量就是碼字中含“1”的個(gè)數(shù)。最小重量Wmin

：線性分組碼CI中，非0碼字重量最小值，叫做碼CI的最小重量：Wmin=min{W(V),V∈CI,V≠0}8.5線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力第三十四頁(yè)，共125頁(yè)。(1)漢明距離、漢明重量和漢明球

最小距離與最小重量的關(guān)系：線性分組碼的最小距離等于它的最小重量。[證明]：設(shè)線性碼CI，且U∈CI,V∈CI又設(shè)U－V=Z由線性碼的封閉性知，Z∈CI

因此，d(U,V)=W(Z)由此可推知，線性分組碼的最小距離必等于非0碼字的最小重量。8.5線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力返回目錄第三十五頁(yè)，共125頁(yè)。(2)最小距離與檢、糾錯(cuò)能力檢錯(cuò)能力：如果一個(gè)線性碼能檢出長(zhǎng)度≤l個(gè)碼元的任何錯(cuò)誤圖樣，稱碼的檢錯(cuò)能力為l。糾錯(cuò)能力：如果線性碼能糾正長(zhǎng)度≤t個(gè)碼元的任意錯(cuò)誤圖樣，稱碼的糾錯(cuò)能力為t。最小距離與檢糾錯(cuò)能力的關(guān)系：線性碼的最小距離越大，意味著任意碼字間的差別越大，則碼的檢、糾錯(cuò)能力越強(qiáng)。8.5線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力第三十六頁(yè)，共125頁(yè)。(2)最小距離與檢、糾錯(cuò)能力最小距離與糾錯(cuò)能力：(n,k)線性碼能糾t個(gè)錯(cuò)誤的充要條件是碼的最小距離為：dmin≥2t+1(8.5.1)[證明]：設(shè)發(fā)送的碼字為V；接收的碼字為R；U為任意其它碼字則矢量V、R、U間滿足距離的三角不等式：d(R,V)+d(R,U)≥d(U,V)(8.5.2)設(shè)信道干擾使碼字中碼元發(fā)生錯(cuò)誤的實(shí)際個(gè)數(shù)為t'，且t'≤td(R,V)＝t'≤t(8.5.3)8.5線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力第三十七頁(yè)，共125頁(yè)。(2)最小距離與檢、糾錯(cuò)能力最小距離與糾錯(cuò)能力：(n,k)線性碼能糾t個(gè)錯(cuò)誤的充要條件是碼的最小距離為：dmin≥2t+1(8.5.1)[證明]：由于d(U,V)≥dmin=2t+1，代入式(7.5.2)得：

d(R,U)≥d(U,V)－d(R,V)=2t+1－t'>t

(8.5.4)

含義：如果接收字R中錯(cuò)誤個(gè)數(shù)t'≤t，接收字R和發(fā)送字V間距離≤t，而與其它任何碼字間距離都大于t，按最小距離譯碼把R譯為V。此時(shí)譯碼正確，碼字中的錯(cuò)誤被糾正。幾何意義：8.5線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力參見圖示第三十八頁(yè)，共125頁(yè)。(2)最小距離與檢、糾錯(cuò)能力最小距離與檢錯(cuò)能力：(n,k)線性碼能夠發(fā)現(xiàn)l個(gè)錯(cuò)誤的充要條件是碼的最小距離為：dmin≥l+1(8.5.5)[證明]：設(shè)發(fā)送的碼字為V；接收的碼字為R；U為任意其它碼字則矢量V、R、U間滿足距離的三角不等式：d(R,V)+d(R,U)≥d(U,V)(8.5.2)設(shè)信道干擾使碼字中碼元發(fā)生錯(cuò)誤的實(shí)際個(gè)數(shù)為l'，且l'≤ld(R,V)＝l'≤l(8.5.6)8.5線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力第三十九頁(yè)，共125頁(yè)。(2)最小距離與檢、糾錯(cuò)能力最小距離與檢錯(cuò)能力：(n,k)線性碼能夠發(fā)現(xiàn)l個(gè)錯(cuò)誤的充要條件是碼的最小距離為：dmin≥l+1(8.5.5)[證明]：由于d(U,V)≥dmin=l+1，代入式(7.5.2)得：d(R,U)≥d(U,V)－d(R,V)=l+1－l'>0

(8.5.7)

含義：由于接收字R與其它任何碼字U

的距離都大于0，說明接收字R

不會(huì)因發(fā)生l'個(gè)錯(cuò)誤變?yōu)槠渌a字，因而必能發(fā)現(xiàn)錯(cuò)誤。8.5線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力第四十頁(yè)，共125頁(yè)。(2)最小距離與檢、糾錯(cuò)能力最小距離與檢錯(cuò)能力：

幾何意義：8.5線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力第四十一頁(yè)，共125頁(yè)。(2)最小距離與檢、糾錯(cuò)能力最小距離與檢、糾錯(cuò)能力：(n,k)線性碼能糾t個(gè)錯(cuò)誤，并能發(fā)現(xiàn)l個(gè)錯(cuò)誤(l>t)的充要條件是碼的最小距離為：Dmin≥t+l+1(8.5.8)[證明]：因?yàn)閐min>2t+1，根據(jù)最小距離與糾錯(cuò)能力定理，該碼可糾t個(gè)錯(cuò)誤。因?yàn)閐min>l+1，根據(jù)最小距離與檢錯(cuò)能力定理,該碼有檢l個(gè)錯(cuò)誤的能力。糾錯(cuò)和檢錯(cuò)不會(huì)發(fā)生混淆：設(shè)發(fā)送碼字為V，接收字為R，實(shí)際錯(cuò)誤數(shù)為l'，且t<l'≤l。這時(shí)R與其它任何碼字U的距離：d(R,U)≥d(U,V)－d(R,V)=t+l+1－l'≥t+1>t

(8.5.9)∴不會(huì)把R誤糾為U。8.5線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力第四十二頁(yè)，共125頁(yè)。(2)最小距離與檢、糾錯(cuò)能力最小距離與檢、糾錯(cuò)能力：幾何意義：8.5線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力第四十三頁(yè)，共125頁(yè)。(2)最小距離與檢、糾錯(cuò)能力8.5線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力當(dāng)(n,k)線性碼的最小距離dmin給定后，可按實(shí)際需要靈活安排糾錯(cuò)的數(shù)目。例如：對(duì)dmin=8的碼，可用來糾3檢4錯(cuò)，或糾2檢5錯(cuò)，或糾1檢6錯(cuò)，或者只用于檢7個(gè)錯(cuò)誤。返回目錄第四十四頁(yè)，共125頁(yè)。(3)線性碼的最小距離與監(jiān)督矩陣的關(guān)系定理8.5.1：設(shè)H為(n,k)線性碼的一致監(jiān)督矩陣，若H中任意S列線性無(wú)關(guān)，而H中存在(S+1)列線性相關(guān)，則碼的最小距離為(S+1)。定理8.5.2：若碼的最小距離為(S+1)，則該碼的監(jiān)督矩陣的任意S列線性無(wú)關(guān)，而必存在有相關(guān)的(S+1)列。定理8.5.3：在二元線性碼的監(jiān)督矩陣H中，如果任一列都不是全“0”，且任兩列都不相等，則該碼能糾一個(gè)錯(cuò)誤。（S=2，dmin=3）8.5線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力第四十五頁(yè)，共125頁(yè)。8.6線性分組碼的譯碼8.6.1伴隨式和錯(cuò)誤檢測(cè)8.6.2糾錯(cuò)譯碼第四十六頁(yè)，共125頁(yè)。8.6.1伴隨式和錯(cuò)誤檢測(cè)(1)如何譯碼？(2)伴隨式(3)伴隨式的計(jì)算(4)伴隨式的特性(5)舉例(6)伴隨式計(jì)算電路8.6線性分組碼的譯碼第四十七頁(yè)，共125頁(yè)。8.6.1伴隨式和錯(cuò)誤檢測(cè)(1)如何譯碼？用監(jiān)督矩陣編碼，也用監(jiān)督矩陣譯碼：接收到一個(gè)字R后，校驗(yàn)HRT=0T是否成立：若關(guān)系成立，則認(rèn)為R是一個(gè)碼字；否則判為碼字在傳輸中發(fā)生了錯(cuò)誤；HRT的值是否為0是校驗(yàn)碼字出錯(cuò)與否的依據(jù)。(2)伴隨式/監(jiān)督子/校驗(yàn)子：S=RHT或ST=HRT返回目錄8.6線性分組碼的譯碼第四十八頁(yè)，共125頁(yè)。8.6.1伴隨式和錯(cuò)誤檢測(cè)(3)伴隨式的計(jì)算

發(fā)送碼字：C=(cn－1,cn－2,…,c0)信道錯(cuò)誤圖樣：E=(en－1,en－2,…,e0)ei=0，表示第i位無(wú)錯(cuò)；ei=1，表示第i位有錯(cuò)。i=n－1,n－2,…,0接收字：R=(rn－1,rn－2,…,r0)=C+E=(cn－1+en－1,cn－2+en－2,…,c0+e0)求接收字的伴隨式（接收字用監(jiān)督矩陣進(jìn)行檢驗(yàn)）ST=HRT=H(C+E)T=HCT+HET

(8.6.1)HCT=0T，所以ST=HET設(shè)H=(h1,h2,…,hn)，（hi表示H的列）。代入式(8.6.1)得：ST=h1en－1+h2en－2+…+hn

e0返回目錄8.6線性分組碼的譯碼第四十九頁(yè)，共125頁(yè)。8.6.1伴隨式和錯(cuò)誤檢測(cè)(4)伴隨式的特性伴隨式僅與錯(cuò)誤圖樣有關(guān)，而與發(fā)送的具體碼字無(wú)關(guān)，即伴隨式僅由錯(cuò)誤圖樣決定；伴隨式是錯(cuò)誤的判別式：若S=0，則判為沒有出錯(cuò)，接收字是一個(gè)碼字；若S≠0，則判為有錯(cuò)。不同的錯(cuò)誤圖樣具有不同的伴隨式，它們是一一對(duì)應(yīng)的。對(duì)二元碼，伴隨式是H陣中與錯(cuò)誤碼元對(duì)應(yīng)列之和。返回目錄8.6線性分組碼的譯碼第五十頁(yè)，共125頁(yè)。(5)舉例：(7,3)碼接收字R的伴隨式計(jì)算若接收字中沒有錯(cuò)誤：設(shè)發(fā)送碼字C=1010011，接收碼字R＝1010011，R與C相同：但接收端譯碼器并不知道就是發(fā)送的碼字根據(jù)接收字R計(jì)算伴隨式：ST=HRT=0T因此，譯碼器判接收字無(wú)錯(cuò)8.6.1伴隨式和錯(cuò)誤檢測(cè)8.6線性分組碼的譯碼第五十一頁(yè)，共125頁(yè)。(5)舉例：(7,3)碼接收矢量R的伴隨式計(jì)算若接收字中有1位錯(cuò)誤：發(fā)送碼字C=1010011，接收碼字R=1110011，伴隨式為：(7,3)碼是糾單個(gè)錯(cuò)誤的碼，且ST等于H的第二列，因此判定接收字R的第二位是錯(cuò)的。由于接收字R中錯(cuò)誤碼元數(shù)與碼的糾錯(cuò)能力相符，所以譯碼正確。8.6.1伴隨式和錯(cuò)誤檢測(cè)8.6線性分組碼的譯碼第五十二頁(yè)，共125頁(yè)。8.6.1伴隨式和錯(cuò)誤檢測(cè)(5)舉例：(7,3)碼接收矢量R的伴隨式計(jì)算當(dāng)碼元錯(cuò)誤多于1個(gè)時(shí)：發(fā)送碼字C=1010011，接收碼字R=0011011，伴隨式為：由于ST是第一列和第四列之和，不等于0；但ST與H陣中任何一列都不相同無(wú)法判定錯(cuò)誤出在哪些位上，只是發(fā)現(xiàn)有錯(cuò)。返回目錄8.6線性分組碼的譯碼第五十三頁(yè)，共125頁(yè)。8.6.1伴隨式和錯(cuò)誤檢測(cè)(6)伴隨式計(jì)算電路伴隨式的計(jì)算可用電路來實(shí)現(xiàn)。(7,3)碼為例：接收字R=(r6r5r4r3r2r1r0)，伴隨式：8.6線性分組碼的譯碼第五十四頁(yè)，共125頁(yè)。8.6.1伴隨式和錯(cuò)誤檢測(cè)(6)伴隨式計(jì)算電路伴隨式計(jì)算電路：返回目錄8.6線性分組碼的譯碼第五十五頁(yè)，共125頁(yè)。8.6.2糾錯(cuò)譯碼(1)最佳譯碼準(zhǔn)則（最大似然譯碼）(2)查表譯碼法(3)標(biāo)準(zhǔn)陣列(4)舉例(5)結(jié)論8.6線性分組碼的譯碼第五十六頁(yè)，共125頁(yè)。8.6.2糾錯(cuò)譯碼(1)最佳譯碼準(zhǔn)則（最大似然譯碼）通信是一個(gè)統(tǒng)計(jì)過程，糾、檢錯(cuò)能力最終要反映到差錯(cuò)概率上。對(duì)于FEC方式，采用糾錯(cuò)碼后的碼字差錯(cuò)概率為pwe：p(C)：發(fā)送碼字C的先驗(yàn)概率p(C/R)：后驗(yàn)概率8.6線性分組碼的譯碼第五十七頁(yè)，共125頁(yè)。8.6.2糾錯(cuò)譯碼(1)最佳譯碼準(zhǔn)則（最大似然譯碼）若碼字?jǐn)?shù)為2k，對(duì)充分隨機(jī)的消息源有p(C)=1/2k，所以最小化的pwe等價(jià)為最小化p(C‘≠C/R)，又等價(jià)為最大化：p(C'

=C/R)；對(duì)于BSC信道：最大化的p(C'

=C/R)等價(jià)于最大化的p(R/C)，最大化的p(R/C)又等價(jià)于最小化d(R,C)，所以使差錯(cuò)概率最小的譯碼是使接收向量R與輸出碼字C'距離最小的譯碼。返回目錄8.6線性分組碼的譯碼第五十八頁(yè)，共125頁(yè)。8.6.2糾錯(cuò)譯碼(2)查表譯碼法按最小距離譯碼，對(duì)有2k個(gè)碼字的(n,k)線性碼，為了找到與接收字R有最小距離的碼字，需將R分別和2k個(gè)碼字比較，以求出最小距離。其中利用“標(biāo)準(zhǔn)陣列”譯碼是最典型的方法。返回目錄8.6線性分組碼的譯碼第五十九頁(yè)，共125頁(yè)。8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列①碼字參數(shù)：發(fā)送碼字：取自于2k個(gè)碼字集合{C}；接收碼字：可以是2n個(gè)n重中任一個(gè)矢量。②譯碼方法把2n個(gè)n重矢量劃分為2k個(gè)互不相交的子集，使得在每個(gè)子集中僅含一個(gè)碼字；根據(jù)碼字和子集間一一對(duì)應(yīng)關(guān)系，若接收矢量Rl落在子集Dl中，就把Rl譯為子集Dl含有的碼字Cl；當(dāng)接收矢量R與實(shí)際發(fā)送碼字在同一子集中時(shí)，譯碼就是正確的。8.6線性分組碼的譯碼第六十頁(yè)，共125頁(yè)。8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列③標(biāo)準(zhǔn)陣列構(gòu)造方法先將2k個(gè)碼字排成一行，作為標(biāo)準(zhǔn)陣列的第一行，并將全0碼字C1=(00…0)放在最左面的位置上；然后在剩下的(2n－2k)

個(gè)n重中選取一個(gè)重量最輕的n重E2放在全0碼字C1下面，再將E2分別和碼字相加，放在對(duì)應(yīng)碼字下面構(gòu)成陣列第二行；在第二次剩下的n重中，選取重量最輕的n重E3，放在E2下面，并將E3分別加到第一行各碼字上，得到第三行；…，繼續(xù)這樣做下去，直到全部n重用完為止。得到表7.6.1所示的給定(n,k)線性碼的標(biāo)準(zhǔn)陣列。8.6線性分組碼的譯碼第六十一頁(yè)，共125頁(yè)。8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列③標(biāo)準(zhǔn)陣列構(gòu)造方法返回8.6線性分組碼的譯碼第六十二頁(yè)，共125頁(yè)。8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列④標(biāo)準(zhǔn)陣列的特性定理8.6.1：在標(biāo)準(zhǔn)陣列的同一行中沒有相同的矢量，而且2n個(gè)n重中任一個(gè)n重在陣列中出現(xiàn)一次且僅出現(xiàn)一次。[證明]：因?yàn)殛嚵兄腥我恍卸际怯伤x出某一n重矢量分別與2k個(gè)碼字相加構(gòu)成的，而2k個(gè)碼字互不相同，它們與所選矢量的和也不可能相同，所以在同一行中沒有相同的矢量；在構(gòu)造標(biāo)準(zhǔn)陣列時(shí)，是用完全部n重為止，因而每個(gè)n重必出現(xiàn)一次；每個(gè)n重只能出現(xiàn)一次：8.6線性分組碼的譯碼第六十三頁(yè)，共125頁(yè)。(3)標(biāo)準(zhǔn)陣列④標(biāo)準(zhǔn)陣列的特性定理8.6.1：在標(biāo)準(zhǔn)陣列的同一行中沒有相同的矢量，而且2n個(gè)n重中任一個(gè)n重在陣列中出現(xiàn)一次且僅出現(xiàn)一次。[證明]：8.6.2糾錯(cuò)譯碼假定某一n重

X

出現(xiàn)在第l行第i列，那么X=El+Ci；又假設(shè)X出現(xiàn)在第m行第j列，那么X=Em+Cj，l<m；因此El+Ci=Em+Cj，移項(xiàng)得Em

=El+Ci+Cj而Ci+Cj

也是一個(gè)碼字，設(shè)為Cs，于是Em

=El+Cs；這意味著Em

是第l行中的一個(gè)矢量，但Em是第m行(m>l)的第一個(gè)元素;按陣列構(gòu)造規(guī)則，后面行的第一個(gè)元素是前面行中未曾出現(xiàn)過的元素，這就和陣列構(gòu)造規(guī)則相矛盾。每個(gè)n重只能出現(xiàn)一次的原因8.6線性分組碼的譯碼第六十四頁(yè)，共125頁(yè)。8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列④標(biāo)準(zhǔn)陣列的特性定理8.6.2（線性碼糾錯(cuò)極限定理）：二元(n,k)線性碼能糾2n－k個(gè)錯(cuò)誤圖樣。這2n－k個(gè)可糾的錯(cuò)誤圖樣，包括0矢量在內(nèi)，即把無(wú)錯(cuò)的情況也看成一個(gè)可糾的錯(cuò)誤圖樣。[證明]：陪集：標(biāo)準(zhǔn)陣列的每一行叫做碼的一個(gè)陪集。陪集首：每個(gè)陪集的第一個(gè)元素叫做陪集首。(n,k)線性碼的標(biāo)準(zhǔn)陣列有2k列（和碼字?jǐn)?shù)量相等），2n/2k=2n－k行，且任何兩列和兩行都沒有相同的元素。8.6線性分組碼的譯碼第六十五頁(yè)，共125頁(yè)。(3)標(biāo)準(zhǔn)陣列④標(biāo)準(zhǔn)陣列的特性定理8.6.2（線性碼糾錯(cuò)極限定理）：[證明]：每一列包含2n－k個(gè)元素，最上面的是一個(gè)碼字，其它元素是陪集首和該碼字之和，例如第j列為：若發(fā)送碼字為Cj，信道干擾的錯(cuò)誤圖樣是陪集首，則接收矢量R必在Dj中；8.6.2糾錯(cuò)譯碼見表8.6線性分組碼的譯碼第六十六頁(yè)，共125頁(yè)。8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列④標(biāo)準(zhǔn)陣列的特性定理7.6.2(線性碼糾錯(cuò)極限定理)：

[證明]：若錯(cuò)誤圖樣不是陪集首，則接收矢量R不在Dj中，則譯成其它碼字，造成錯(cuò)誤譯碼；當(dāng)且僅當(dāng)錯(cuò)誤圖樣為陪集首時(shí)，譯碼才是正確的?？杉m正的錯(cuò)誤圖樣：這2n－k個(gè)陪集首稱為可糾正的錯(cuò)誤圖樣。見表8.6線性分組碼的譯碼第六十七頁(yè)，共125頁(yè)。8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列④標(biāo)準(zhǔn)陣列的特性線性碼糾錯(cuò)能力與監(jiān)督元數(shù)目的關(guān)系：一個(gè)可糾t個(gè)錯(cuò)誤的線性碼必須滿足：上式中等式成立時(shí)的線性碼稱為完備碼。即：8.6線性分組碼的譯碼第六十八頁(yè)，共125頁(yè)。8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列④標(biāo)準(zhǔn)陣列的特性線性碼糾錯(cuò)能力與監(jiān)督元數(shù)目的關(guān)系：[證明]：糾一個(gè)錯(cuò)誤的(n,k)線性碼，必須能糾正個(gè)錯(cuò)誤圖樣，因此：對(duì)糾兩個(gè)錯(cuò)誤的(n,k)線性碼，必須能糾個(gè)錯(cuò)誤圖樣，所以：8.6線性分組碼的譯碼第六十九頁(yè)，共125頁(yè)。8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列④標(biāo)準(zhǔn)陣列的特性線性碼糾錯(cuò)能力與監(jiān)督元數(shù)目的關(guān)系：[證明]：依此類推，一個(gè)糾t個(gè)錯(cuò)誤的(n,k)線性碼必須滿足：對(duì)于完備碼，由碼的糾錯(cuò)能力所確定的伴隨式數(shù)恰好等于可糾的錯(cuò)誤圖樣數(shù)，所以完備碼的(n－k)個(gè)監(jiān)督碼元得到了充分的利用。8.6線性分組碼的譯碼第七十頁(yè)，共125頁(yè)。8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列④標(biāo)準(zhǔn)陣列的特性完備譯碼：(n,k)線性碼的所有2n－k個(gè)伴隨式，在譯碼過程中都用來糾正所有小于等于個(gè)隨機(jī)錯(cuò)誤，以及部分大于t的錯(cuò)誤圖樣。限定距離譯碼：任一個(gè)(n,k)線性碼，能糾正個(gè)隨機(jī)錯(cuò)誤，如果在譯碼時(shí)僅糾正t'<t個(gè)錯(cuò)誤，而當(dāng)錯(cuò)誤個(gè)數(shù)大于t'時(shí)，譯碼器不進(jìn)行糾錯(cuò)而僅指出發(fā)生了錯(cuò)誤。8.6線性分組碼的譯碼第七十一頁(yè)，共125頁(yè)。8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列④標(biāo)準(zhǔn)陣列的特性從多維矢量空間的角度看完備碼假定圍繞每一個(gè)碼字Ci放置一個(gè)半徑為t的球，每個(gè)球內(nèi)包含了與該碼字漢明距離小于等于t的所有接收碼字R的集合；在半徑為的球內(nèi)的接收碼字?jǐn)?shù)是：因?yàn)橛?k個(gè)可能發(fā)送的碼字，也就有2k個(gè)不相重疊的半徑為t的球。包含在2k個(gè)球中的碼字總數(shù)不會(huì)超過2n個(gè)可能的接收碼字。8.6線性分組碼的譯碼第七十二頁(yè)，共125頁(yè)。8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列④標(biāo)準(zhǔn)陣列的特性從多維矢量空間的角度看完備碼于是一個(gè)糾t個(gè)差錯(cuò)的碼必然滿足不等式：如果上式中等號(hào)成立，表示所有的接收碼字都落在2k個(gè)球內(nèi)，而球外沒有一個(gè)碼，這就是完備碼。8.6線性分組碼的譯碼第七十三頁(yè)，共125頁(yè)。8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列④標(biāo)準(zhǔn)陣列的特性從多維矢量空間的角度看完備碼完備碼特性：圍繞2k

個(gè)碼字，漢明距離為t=INT[(dmin－1)/2]的所有球都是不相交的，每一個(gè)接收碼字都落在這些球中之一，因此接收碼與發(fā)送碼的距離至多為t，這時(shí)所有重量≤t的錯(cuò)誤圖樣都能用最佳（最小距離）譯碼器得到糾正，而所有重量≥t+1的錯(cuò)誤圖樣都不能糾正。8.6線性分組碼的譯碼第七十四頁(yè)，共125頁(yè)。8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列④標(biāo)準(zhǔn)陣列的特性從多維矢量空間的角度看完備碼舉例：對(duì)糾一個(gè)錯(cuò)誤的(7,4)漢明碼：(7,4)漢明碼是一個(gè)完備碼。所有漢明碼都是完備碼：（滿足2n－k=2r=n+1）。8.6線性分組碼的譯碼第七十五頁(yè)，共125頁(yè)。8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列④標(biāo)準(zhǔn)陣列的特性

標(biāo)準(zhǔn)陣列譯碼=最小距離譯碼=最佳譯碼陪集首是可糾正的錯(cuò)誤圖樣，為了使譯碼錯(cuò)誤概率最小，應(yīng)選取出現(xiàn)概率最大的錯(cuò)誤圖樣作陪集首；重量較輕的錯(cuò)誤圖樣出現(xiàn)概率較大，所以在構(gòu)造標(biāo)準(zhǔn)陣列時(shí)是選取重量最輕的n重作陪集首；當(dāng)錯(cuò)誤圖樣為陪集首時(shí)（可糾的錯(cuò)誤圖樣），接收矢量與原發(fā)送碼字間的距離（等于陪集首）最?。灰虼?，選擇重量最輕的元素作陪集首，按標(biāo)準(zhǔn)陣列譯碼就是按最小距離譯碼；所以標(biāo)準(zhǔn)陣列譯碼法也是最佳譯碼法。8.6線性分組碼的譯碼第七十六頁(yè)，共125頁(yè)。8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列④標(biāo)準(zhǔn)陣列的特性定理7.6.3：在標(biāo)準(zhǔn)陣列中，一個(gè)陪集的所有2k個(gè)n重有相同的伴隨式，不同的陪集伴隨式互不相同。[證明]：設(shè)H為給定(n,k)線性碼的監(jiān)督矩陣，在陪集首為El的陪集中的任意矢量為：R=El+Ci,i=1,2,…,2k其伴隨式為：S=RHT=(El+Ci)HT=ElHT+CiHT=ElHT上式表明：陪集中任意矢量的伴隨式等于陪集首的伴隨式。即同一陪集中所有伴隨式相同。不同陪集中，由于陪集首不同所以伴隨式不同。返回目錄8.6線性分組碼的譯碼第七十七頁(yè)，共125頁(yè)。8.6.2糾錯(cuò)譯碼(4)舉例：(6,3)碼的標(biāo)準(zhǔn)陣列返回返回目錄8.6線性分組碼的譯碼第七十八頁(yè)，共125頁(yè)。8.6.2糾錯(cuò)譯碼(5)結(jié)論任意n重的伴隨式?jīng)Q定于它在標(biāo)準(zhǔn)陣列中所在陪集的陪集首。標(biāo)準(zhǔn)陣列的陪集首和伴隨式是一一對(duì)應(yīng)的，因而碼的可糾錯(cuò)誤圖樣和伴隨式是一一對(duì)應(yīng)的，應(yīng)用此對(duì)應(yīng)關(guān)系可以構(gòu)成比標(biāo)準(zhǔn)陣列簡(jiǎn)單得多的譯碼表，從而得到(n,k)線性碼的一般譯碼步驟。

(n,k)線性碼的一般譯碼步驟計(jì)算接收矢量R的伴隨式ST=HRT；根據(jù)伴隨式和錯(cuò)誤圖樣一一對(duì)應(yīng)的關(guān)系，利用伴隨式譯碼表，由伴隨式譯出R的錯(cuò)誤圖樣E；將接收字減錯(cuò)誤圖樣，得發(fā)送碼字的估值：C'=R－E。見表8.6線性分組碼的譯碼第七十九頁(yè)，共125頁(yè)。8.6.2糾錯(cuò)譯碼(5)結(jié)論線性分組碼一般譯碼器（伴隨式譯碼法/查表譯碼法）譯碼器如下圖。這種查表譯碼法具有最小的譯碼延遲和最小的譯碼錯(cuò)誤概率，原則上可用于任何(n,k)線性碼。8.6線性分組碼的譯碼第八十頁(yè)，共125頁(yè)。8.6.2糾錯(cuò)譯碼(5)結(jié)論舉例：求(7,4)漢明碼的編碼電路和譯碼電路。其系統(tǒng)碼形式：8.6線性分組碼的譯碼第八十一頁(yè)，共125頁(yè)。8.6.2糾錯(cuò)譯碼(5)結(jié)論舉例：求(7,4)漢明碼的編碼電路和譯碼電路。編碼電路：8.6線性分組碼的譯碼第八十二頁(yè)，共125頁(yè)。8.6.2糾錯(cuò)譯碼(5)結(jié)論舉例：求(7,4)漢明碼的編碼電路和譯碼電路。編碼電路：8.6線性分組碼的譯碼第八十三頁(yè)，共125頁(yè)。8.6.2糾錯(cuò)譯碼(5)結(jié)論舉例：求(7,4)漢明碼的編碼電路和譯碼電路。譯碼電路：8.6線性分組碼的譯碼第八十四頁(yè)，共125頁(yè)。8.6.2糾錯(cuò)譯碼(5)結(jié)論舉例：求(7,4)漢明碼的編碼電路和譯碼電路。譯碼電路：8.6線性分組碼的譯碼第八十五頁(yè)，共125頁(yè)。8.7線性分組碼的性能在通信中檢、糾錯(cuò)碼的實(shí)際性能是在統(tǒng)計(jì)上體現(xiàn)出來的。錯(cuò)誤概率：不可檢錯(cuò)誤概率：pud譯碼錯(cuò)誤概率：pwe譯碼失敗概率：pwf比特誤碼率：Pbd差錯(cuò)概率的原因：碼的結(jié)構(gòu)信道特性分析均以BSC信道為模型。第八十六頁(yè)，共125頁(yè)。8.7線性分組碼的性能(1)不可檢錯(cuò)誤概率(2)譯碼錯(cuò)誤概率(3)譯碼失敗概率(4)比特誤碼率第八十七頁(yè)，共125頁(yè)。8.7線性分組碼的性能(1)不可檢錯(cuò)誤概率pud由(n,k)線性碼的重量分布求pud令A(yù)i為碼的重量分布，表示重量為i的碼字個(gè)數(shù)，i=0,1,2,…,n；

僅當(dāng)錯(cuò)誤圖樣與碼字集合中的非0碼字相同時(shí)，才不能檢出錯(cuò)誤，所以：舉例：(7,3)碼的重量分布是A0=1,A1=A2=A3=0,A4=7，其不可檢錯(cuò)誤概率為：

pud＝7×p4(1－p)3，若p=0.01，則：pud≈6.8×10－8第八十八頁(yè)，共125頁(yè)。8.7線性分組碼的性能(1)不可檢錯(cuò)誤概率pud利用(n,k)碼重量分布與其對(duì)偶碼的重量分布關(guān)系求pud設(shè)A0,A1,A2,…,An是(n,k)碼的重量分布；B0,B1,B2,…,Bn是它的對(duì)偶碼的重量分布；

對(duì)偶碼的重量枚舉式：下面的多項(xiàng)式稱為(n,k)碼和它的對(duì)偶碼的重量枚舉式。第八十九頁(yè)，共125頁(yè)。8.7線性分組碼的性能(1)不可檢錯(cuò)誤概率pud利用(n,k)碼重量分布與其對(duì)偶碼的重量分布關(guān)系求pud

MacWilliams恒等式：若已知線性碼的對(duì)偶碼的重量分布，就可確定該碼本身的重量分布：由式(7.7.1)得：第九十頁(yè)，共125頁(yè)。8.7線性分組碼的性能(1)不可檢錯(cuò)誤概率pud利用(n,k)碼重量分布與其對(duì)偶碼的重量分布關(guān)系求pud令：將這個(gè)恒等式代入式(8.7.4)得：第九十一頁(yè)，共125頁(yè)。(1)不可檢錯(cuò)誤概率pud利用(n,k)碼重量分布與其對(duì)偶碼的重量分布關(guān)系求pud將麥克威廉姆斯恒等式代入上式得：當(dāng)k<(n－k)時(shí)，用式(7.7.6)計(jì)算pud較簡(jiǎn)單；當(dāng)k>(n－k)時(shí)，用式(7.7.7)計(jì)算pud更容易。8.7線性分組碼的性能選字?jǐn)?shù)少的方式計(jì)算第九十二頁(yè)，共125頁(yè)。8.7線性分組碼的性能(1)不可檢錯(cuò)誤概率pud利用(n,k)碼重量分布與其對(duì)偶碼的重量分布關(guān)系求pud舉例：已知(7,4)碼的監(jiān)督矩陣H(7,4)，它等于其對(duì)偶碼的生成矩陣G(7,3)，即：由此生成矩陣的行的線性組合，可得到(7,3)碼的8個(gè)碼字：第九十三頁(yè)，共125頁(yè)。8.7線性分組碼的性能(1)不可檢錯(cuò)誤概率pud利用(n,k)碼重量分布與其對(duì)偶碼的重量分布關(guān)系求pud舉例：由此得到(7,4)對(duì)偶碼的重量枚舉式為：B(x)=1+7x4利用式(8.7.7)得：(7,4)碼的未檢出錯(cuò)誤概率為：

pud=2－3[1+7×(1－2p)4]－(1－p)7設(shè)p=0.01，則pud=6×10－6返回目錄第九十四頁(yè)，共125頁(yè)。8.7線性分組碼的性能(2)譯碼錯(cuò)誤概率pwe正確譯碼概率pwc：糾正小于等于t個(gè)差錯(cuò)的概率：第九十五頁(yè)，共125頁(yè)。8.7線性分組碼的性能(2)譯碼錯(cuò)誤概率pwe譯碼錯(cuò)誤概率pwe譯碼錯(cuò)誤發(fā)生在差錯(cuò)數(shù)目大于t，接收向量R與另一碼字C'的距離小于等于t的情況；

Di是重量i并譯為錯(cuò)誤碼字的可能的接收向量R的數(shù)目，即：譯碼錯(cuò)誤概率pwe為：返回目錄第九十六頁(yè)，共125頁(yè)。8.7線性分組碼的性能(3)譯碼失敗概率pwf由于仍存在不滿足式(8.7.8)的接收碼矢R，對(duì)于限定距離譯碼器來說就處于譯碼失敗狀態(tài)，即：pwf=1－pwc－pwe

圖中：RA—正確譯碼的接收矢量RB—譯碼錯(cuò)誤的接收矢量RC—譯碼失敗的接收矢量返回目錄第九十七頁(yè)，共125頁(yè)。8.7線性分組碼的性能(4)比特誤碼率pbc：信道的比特差錯(cuò)概率，對(duì)于BSC信道，pbc等于信道轉(zhuǎn)移概率p。pbd：譯碼錯(cuò)誤導(dǎo)致的碼字之間的比特差錯(cuò)率。pbm：消息源與消息接收終端之間的比特差錯(cuò)概率。

統(tǒng)計(jì)意義上認(rèn)為：消息和碼字之間的映射不改變碼字差錯(cuò)導(dǎo)致在整個(gè)碼長(zhǎng)內(nèi)比特差錯(cuò)的均勻分布特性，在統(tǒng)計(jì)意義上有pbm≈pbd第九十八頁(yè)，共125頁(yè)。8.7線性分組碼的性能(4)比特誤碼率

譯碼錯(cuò)誤造成的誤碼率pbe

：設(shè)碼字是等概率發(fā)送，則：是發(fā)送全0碼字并錯(cuò)為j重碼字的概率Pbe

與pwe的關(guān)系字錯(cuò)必然有至少2t+1位碼字比特錯(cuò)；每個(gè)碼字平均有位消息比特錯(cuò)，所以pbe與pwe有如下漸進(jìn)關(guān)系：第九十九頁(yè)，共125頁(yè)。8.7線性分組碼的性能(4)比特誤碼率

譯碼失敗造成的誤碼率pbf

：

譯碼后總的誤碼率Pbd

：pbd=pbe+pbf返回目錄第一百頁(yè)，共125頁(yè)。8.8漢明碼

漢明碼的來由：漢明碼是漢明于1950年提出的糾一個(gè)錯(cuò)誤的線性碼，也是第一個(gè)糾錯(cuò)碼。由于它編碼簡(jiǎn)單，因而是在通信系統(tǒng)和數(shù)據(jù)存儲(chǔ)系統(tǒng)中得到廣泛應(yīng)用的一類線性碼。

漢明碼的結(jié)構(gòu)參數(shù)：糾一個(gè)錯(cuò)誤的線性碼，其最小距離dmin=3；監(jiān)督矩陣任意兩列線性無(wú)關(guān)／H的任兩列互不相同；沒有全0的列。監(jiān)督元個(gè)數(shù)r=n－k；H陣中每列有r個(gè)元素，至多可構(gòu)成2r－1種互不相同的非0列。對(duì)于任意正整數(shù)m≥3，漢明碼的結(jié)構(gòu)參數(shù)為：碼長(zhǎng)：

n=2m－1信息位數(shù)：

k=2m－m－1監(jiān)督位數(shù)：

n－k=m碼的最小距離：dmin=3(t=1)第一百零一頁(yè)，共125頁(yè)。8.8漢明碼漢明碼監(jiān)督矩陣構(gòu)成的兩種方式

H陣的標(biāo)準(zhǔn)形式：H=[QIr]，Ir為r階單位子陣，子陣Q是構(gòu)造Ir后剩下的列任意排列。用這種形式的H陣編出的漢明碼是系統(tǒng)碼。按r重表示的二進(jìn)制順序排列：按這種形式H陣編出的碼是非系統(tǒng)碼。當(dāng)發(fā)生可糾的單個(gè)錯(cuò)誤時(shí)，伴隨式為H陣中對(duì)應(yīng)的列，所以伴隨式的二進(jìn)制數(shù)值就是錯(cuò)誤位置號(hào)，有時(shí)這種碼譯碼比較方便。例如：第一百零二頁(yè)，共125頁(yè)。8.8漢明碼漢明碼監(jiān)督矩陣構(gòu)成的兩種方式

H陣的標(biāo)準(zhǔn)形式：H=[QIr]，Ir為r階單位子陣，子陣Q是構(gòu)造Ir后剩下的列任意排列。用這種形式的H陣編出的漢明碼是系統(tǒng)碼。按r重表示的二進(jìn)制順序排列：按這種形式H陣編出的碼是非系統(tǒng)碼。當(dāng)發(fā)生可糾的單個(gè)錯(cuò)誤時(shí)，伴隨式為H陣中對(duì)應(yīng)的列，所以伴隨式的二進(jìn)制數(shù)值就是錯(cuò)誤位置號(hào)，有時(shí)這種碼譯碼比較方便。由于漢明碼可糾的錯(cuò)誤圖樣數(shù)為：返回目錄第一百零三頁(yè)，共125頁(yè)。8.9由已知碼構(gòu)造新碼的方法(1)擴(kuò)展/Extending和打孔/Puncturing(2)增廣/Augmenting和刪信/Expunging/Expurgating(3)延長(zhǎng)/Lengthening和縮短/Sportening(4)乘積/Product(5)級(jí)聯(lián)/Concatenating(6)交織/Interleauing第一百零四頁(yè)，共125頁(yè)。8.9由已知碼構(gòu)造新碼的方法(1)擴(kuò)展/Extending和打孔/Puncturing擴(kuò)展：保持k不變，增加冗余位數(shù)以增加碼長(zhǎng)。打孔：保持k不變，減小冗余位。擴(kuò)展的逆過程。(2)增廣/Augmenting和刪信/Expunging/Expurgating增廣：保持n不變，增加碼字?jǐn)?shù)目k。刪信：保持n不變，減小k。(3)延長(zhǎng)/Lengthening和縮短/Sportening延長(zhǎng)：同時(shí)增加k和n。縮短：同時(shí)減小k和n。第一百零五頁(yè)，共125頁(yè)。8.9由已知碼構(gòu)造新碼的方法舉例：(2r－1,2r－1－r,3)漢明碼構(gòu)成各種新碼的6種方法返回目錄第一百零六頁(yè)，共125頁(yè)。8.9由已知碼構(gòu)造新碼的方法(4)乘積/Product消息作為陣列，分別進(jìn)行行列編碼。(5)級(jí)聯(lián)/Concatenating對(duì)消息編碼后的碼字再進(jìn)行一次編碼。級(jí)聯(lián)編碼的第一次所用碼稱外碼；第二次所用碼稱內(nèi)碼。級(jí)聯(lián)編碼常用于既有隨機(jī)差錯(cuò)又有突發(fā)差錯(cuò)的信道編碼。返回目錄第一百零七頁(yè)，共125頁(yè)。8.9由已知碼構(gòu)造新碼的方法(6)交織/Interleauing（《移動(dòng)通信中的關(guān)鍵技術(shù)》，北郵出版社，2001.8，P.102）交織編碼分為分組交織和卷積交織兩種。交織是一種信道改造技術(shù)，它通過信號(hào)設(shè)計(jì)將一個(gè)原來屬于突發(fā)差錯(cuò)的有記憶信道改造為基本上是獨(dú)立差錯(cuò)的隨機(jī)無(wú)記憶信道。交織碼的原理：第一百零八頁(yè)，共125頁(yè)。8.9由已知碼構(gòu)造新碼的方法(6)交織/Interleauing（《移動(dòng)通信中的關(guān)鍵技術(shù)》，北郵出版社，2001.8，P.102）舉例說明分組交織編碼器設(shè)計(jì)發(fā)送信息：X=(x1

x2

x3

x4…x23

x24

x25)交織器：按行寫入、按列取出的5×5陣列存儲(chǔ)器去交織器：完成與交織器相反的變換，按列寫入、按行取出，仍是一個(gè)5×5陣列存儲(chǔ)器，其差錯(cuò)規(guī)律變成了獨(dú)立差錯(cuò)。第一百零九頁(yè)，共125頁(yè)。8.9由已知碼構(gòu)造新碼的方法(6)交織/Interleauing

（《移動(dòng)通信中的關(guān)鍵技術(shù)》，北郵出版社，2001.8，P.102）舉例說明分組交織編碼器設(shè)計(jì)

交織矩陣對(duì)此矩陣按行寫入，按列讀出，得：X[1]=(x1x6x11x16x21

x2x7x12x17x22x3x8x13x18x23x4

x9x14x19x24x5x10x15x20x25)第一百一十頁(yè)，共125頁(yè)。8.9由已知碼構(gòu)造新碼的方法(6)交織/Interleauing

（《移動(dòng)通信中的關(guān)鍵技術(shù)》，北郵出版社，200