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

信息論與編碼原理（第八章）

──────────────

線性分組碼12/22/20221DepartmentofElectronicsandInformation,NCUTSongPeng信息論與編碼原理（第八章）

──────────────

線第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線性分組碼的碼限12/22/20222DepartmentofElectronicsandInformation,NCUTSongPeng第8章線性分組碼8.1一般概念12/16/208.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)。12/22/20223DepartmentofElectronicsandInformation,NCUTSongPeng8.1一般概念(1)線性分組碼的編碼：編碼過程分為兩8.1一般概念(3)術(shù)語線性分組碼：通過預(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ù)。返回目錄12/22/20224DepartmentofElectronicsandInformation,NCUTSongPeng8.1一般概念(3)術(shù)語返回目錄12/16/20228.2一致監(jiān)督方程和一致監(jiān)督矩陣(1)一致監(jiān)督方程(2)舉例(3)一致監(jiān)督矩陣(4)一致監(jiān)督矩陣特性12/22/20225DepartmentofElectronicsandInformation,NCUTSongPeng8.2一致監(jiān)督方程和一致監(jiān)督矩陣(1)一致監(jiān)督方程(2)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ì)算：12/22/20226DepartmentofElectronicsandInformation,NCUTSongPeng8.2一致監(jiān)督方程和一致監(jiān)督矩陣(1)一致監(jiān)督方程128.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)督方程所確定的分組碼是線性分組碼。返回目錄12/22/20227DepartmentofElectronicsandInformation,NCUTSongPeng8.2一致監(jiān)督方程和一致監(jiān)督矩陣(1)一致監(jiān)督方程返回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。返回目錄12/22/20228DepartmentofElectronicsandInformation,NCUTSongPeng8.2一致監(jiān)督方程和一致監(jiān)督矩陣(2)舉例返回目錄128.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)置矩陣。12/22/20229DepartmentofElectronicsandInformation,NCUTSongPeng8.2一致監(jiān)督方程和一致監(jiān)督矩陣(3)一致監(jiān)督矩陣將式8.2一致監(jiān)督方程和一致監(jiān)督矩陣(3)一致監(jiān)督矩陣系數(shù)矩陣H的后四列組成一個(gè)(4×4)階單位子陣，用I4表示，H的其余部分用P表示：12/22/202210DepartmentofElectronicsandInformation,NCUTSongPeng8.2一致監(jiān)督方程和一致監(jiān)督矩陣(3)一致監(jiān)督矩陣128.2一致監(jiān)督方程和一致監(jiān)督矩陣(3)一致監(jiān)督矩陣推廣到一般情況：對(duì)(n,k)線性分組碼，每個(gè)碼字中的r(r=n－k)個(gè)監(jiān)督元與信息元之間的關(guān)系可由下面的線性方程組確定：返回12/22/202211DepartmentofElectronicsandInformation,NCUTSongPeng8.2一致監(jiān)督方程和一致監(jiān)督矩陣(3)一致監(jiān)督矩陣返回8.2一致監(jiān)督方程和一致監(jiān)督矩陣(3)一致監(jiān)督矩陣令上式的系數(shù)矩陣為H，碼字行陣列為C：返回目錄12/22/202212DepartmentofElectronicsandInformation,NCUTSongPeng8.2一致監(jiān)督方程和一致監(jiān)督矩陣(3)一致監(jiān)督矩陣返回(4)一致監(jiān)督矩陣特性對(duì)H各行實(shí)行初等變換，將后面r列化為單位子陣，得到下面矩陣，行變換所得方程組與原方程組同解。監(jiān)督矩陣H的標(biāo)準(zhǔn)形式：后面r列是一單位子陣的監(jiān)督矩陣H。8.2一致監(jiān)督方程和一致監(jiān)督矩陣12/22/202213DepartmentofElectronicsandInformation,NCUTSongPeng(4)一致監(jiān)督矩陣特性8.2一致監(jiān)督方程和一致監(jiān)督矩陣(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)督矩陣參見方程返回目錄12/22/202214DepartmentofElectronicsandInformation,NCUTSongPeng(4)一致監(jiān)督矩陣特性8.2一致監(jiān)督方程和一致監(jiān)督矩陣8.3線性分組碼的生成矩陣(1)線性碼的封閉性(2)線性分組碼的生成矩陣(3)生成矩陣與一致監(jiān)督矩陣的關(guān)系(4)對(duì)偶碼12/22/202215DepartmentofElectronicsandInformation,NCUTSongPeng8.3線性分組碼的生成矩陣(1)線性碼的封(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線性分組碼的生成矩陣返回目錄12/22/202216DepartmentofElectronicsandInformation,NCUTSongPeng(1)線性碼的封閉性8.3線性分組碼的生成矩陣返回目錄(2)線性分組碼的生成矩陣生成矩陣的來由：在由(n,k)線性碼構(gòu)成的線性空間Vn的k維子空間中，一定存在k個(gè)線性獨(dú)立的碼字：g1,g2,…,gk。碼CI中其它任何碼字C都可以表為這k個(gè)碼字的一種線性組合，即：8.3線性分組碼的生成矩陣12/22/202217DepartmentofElectronicsandInformation,NCUTSongPeng(2)線性分組碼的生成矩陣8.3線性分組碼的生成矩陣1(2)線性分組碼的生成矩陣生成矩陣定義：由于矩陣G生成了(n,k)線性碼，稱矩陣G為(n,k)線性碼的生成矩陣。8.3線性分組碼的生成矩陣12/22/202218DepartmentofElectronicsandInformation,NCUTSongPeng(2)線性分組碼的生成矩陣8.3線性分組碼的生成矩陣1(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線性分組碼的生成矩陣12/22/202219DepartmentofElectronicsandInformation,NCUTSongPeng(2)線性分組碼的生成矩陣8.3線性分組碼的生成矩陣1(2)線性分組碼的生成矩陣

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

線性系統(tǒng)分組碼的構(gòu)成：通過行初等變換，將G化為前k列是單位子陣的標(biāo)準(zhǔn)形式。8.3線性分組碼的生成矩陣12/22/202220DepartmentofElectronicsandInformation,NCUTSongPeng(2)線性分組碼的生成矩陣8.3線性分組碼的生成矩陣1(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線性分組碼的生成矩陣12/22/202221DepartmentofElectronicsandInformation,NCUTSongPeng(2)線性分組碼的生成矩陣8.3線性分組碼的生成矩陣1(2)線性分組碼的生成矩陣舉例：(7,4)線性碼的生成矩陣為：8.3線性分組碼的生成矩陣返回目錄12/22/202222DepartmentofElectronicsandInformation,NCUTSongPeng(2)線性分組碼的生成矩陣8.3線性分組碼的生成矩陣返(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線性分組碼的生成矩陣12/22/202223DepartmentofElectronicsandInformation,NCUTSongPeng(3)生成矩陣與一致監(jiān)督矩陣的關(guān)系8.3線性分組碼的生(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線性分組碼的生成矩陣12/22/202224DepartmentofElectronicsandInformation,NCUTSongPeng(3)生成矩陣與一致監(jiān)督矩陣的關(guān)系8.3線性分組碼的生(3)生成矩陣與一致監(jiān)督矩陣的關(guān)系舉例：已知(7,4)線性系統(tǒng)碼的監(jiān)督矩陣為：8.3線性分組碼的生成矩陣QQT返回目錄12/22/202225DepartmentofElectronicsandInformation,NCUTSongPeng(3)生成矩陣與一致監(jiān)督矩陣的關(guān)系8.3線性分組碼的生(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線性分組碼的生成矩陣返回目錄12/22/202226DepartmentofElectronicsandInformation,NCUTSongPeng(4)對(duì)偶碼8.3線性分組碼的生成矩陣返回目錄12/1

(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線性分組碼的編碼12/22/202227DepartmentofElectronicsandInformation,NCUTSongPeng(n,k)線性碼的編碼：根據(jù)線性碼的監(jiān)督矩陣或生成矩陣將利用監(jiān)督矩陣構(gòu)造(7,3)線性分組碼的編碼電路：根據(jù)上面方程組可直接畫出(7,3)碼的并行編碼電路和串行編碼電路:8.4線性分組碼的編碼返回目錄12/22/202228DepartmentofElectronicsandInformation,NCUTSongPeng利用監(jiān)督矩陣構(gòu)造(7,3)線性分組碼的編碼電路：8.48.5線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力(1)漢明距離、漢明重量和漢明球(2)最小距離與檢、糾錯(cuò)能力(3)線性碼的最小距離與監(jiān)督矩陣的關(guān)系12/22/202229DepartmentofElectronicsandInformation,NCUTSongPeng8.5線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力(1)漢明距離(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ò)能力12/22/202230DepartmentofElectronicsandInformation,NCUTSongPeng(1)漢明距離、漢明重量和漢明球8.5線性分組碼的最小距(1)漢明距離、漢明重量和漢明球

最小距離dmin：在(n,k)線性碼的碼字集合中，任意兩個(gè)碼字間距離最小值，叫做碼的最小距離。若C(i)和C(j)是任意兩個(gè)碼字，則碼的最小距離表示為：碼的最小距離是衡量碼的抗干擾能力（檢、糾錯(cuò)能力）的重要參數(shù)。碼的最小距離越大，碼的抗干擾能力就越強(qiáng)。8.5線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力12/22/202231DepartmentofElectronicsandInformation,NCUTSongPeng(1)漢明距離、漢明重量和漢明球8.5線性分組碼的最小距(1)漢明距離、漢明重量和漢明球漢明球：以碼字C為中心，半徑為t的漢明球是與C的漢明距離≤t的向量全體SC(t)：任意兩個(gè)漢明球不相交最大程度取決于任意兩個(gè)碼字之間的最小漢明距離dmin。8.5線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力12/22/202232DepartmentofElectronicsandInformation,NCUTSongPeng(1)漢明距離、漢明重量和漢明球8.5線性分組碼的最小距(1)漢明距離、漢明重量和漢明球漢明球：8.5線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力返回12/22/202233DepartmentofElectronicsandInformation,NCUTSongPeng(1)漢明距離、漢明重量和漢明球8.5線性分組碼的最小距(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ò)能力12/22/202234DepartmentofElectronicsandInformation,NCUTSongPeng(1)漢明距離、漢明重量和漢明球8.5線性分組碼的最小距(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ò)能力返回目錄12/22/202235DepartmentofElectronicsandInformation,NCUTSongPeng(1)漢明距離、漢明重量和漢明球8.5線性分組碼的最小距(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ò)能力12/22/202236DepartmentofElectronicsandInformation,NCUTSongPeng(2)最小距離與檢、糾錯(cuò)能力8.5線性分組碼的最小距離、(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ò)能力12/22/202237DepartmentofElectronicsandInformation,NCUTSongPeng(2)最小距離與檢、糾錯(cuò)能力8.5線性分組碼的最小距離、(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ò)能力參見圖示12/22/202238DepartmentofElectronicsandInformation,NCUTSongPeng(2)最小距離與檢、糾錯(cuò)能力8.5線性分組碼的最小距離、(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ò)能力12/22/202239DepartmentofElectronicsandInformation,NCUTSongPeng(2)最小距離與檢、糾錯(cuò)能力8.5線性分組碼的最小距離、(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ò)能力12/22/202240DepartmentofElectronicsandInformation,NCUTSongPeng(2)最小距離與檢、糾錯(cuò)能力8.5線性分組碼的最小距離、(2)最小距離與檢、糾錯(cuò)能力最小距離與檢錯(cuò)能力：

幾何意義：8.5線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力12/22/202241DepartmentofElectronicsandInformation,NCUTSongPeng(2)最小距離與檢、糾錯(cuò)能力8.5線性分組碼的最小距離、(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ò)能力12/22/202242DepartmentofElectronicsandInformation,NCUTSongPeng(2)最小距離與檢、糾錯(cuò)能力8.5線性分組碼的最小距離、(2)最小距離與檢、糾錯(cuò)能力最小距離與檢、糾錯(cuò)能力：幾何意義：8.5線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力12/22/202243DepartmentofElectronicsandInformation,NCUTSongPeng(2)最小距離與檢、糾錯(cuò)能力8.5線性分組碼的最小距離、(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ò)誤。返回目錄12/22/202244DepartmentofElectronicsandInformation,NCUTSongPeng(2)最小距離與檢、糾錯(cuò)能力8.5線性分組碼的最小距離、(3)線性碼的最小距離與監(jiān)督矩陣的關(guān)系定理8.5.1：設(shè)H為(n,k)線性碼的一致監(jiān)督矩陣，若H中任意S列線性無關(guān)，而H中存在(S+1)列線性相關(guān)，則碼的最小距離為(S+1)。定理8.5.2：若碼的最小距離為(S+1)，則該碼的監(jiān)督矩陣的任意S列線性無關(guān)，而必存在有相關(guān)的(S+1)列。定理8.5.3：在二元線性碼的監(jiān)督矩陣H中，如果任一列都不是全“0”，且任兩列都不相等，則該碼能糾一個(gè)錯(cuò)誤。（S=2，dmin=3）8.5線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力12/22/202245DepartmentofElectronicsandInformation,NCUTSongPeng(3)線性碼的最小距離與監(jiān)督矩陣的關(guān)系8.5線性分組碼的8.6線性分組碼的譯碼8.6.1伴隨式和錯(cuò)誤檢測(cè)8.6.2糾錯(cuò)譯碼12/22/202246DepartmentofElectronicsandInformation,NCUTSongPeng8.6線性分組碼的譯碼8.6.1伴隨式和錯(cuò)誤檢測(cè)8.68.6.1伴隨式和錯(cuò)誤檢測(cè)(1)如何譯碼？(2)伴隨式(3)伴隨式的計(jì)算(4)伴隨式的特性(5)舉例(6)伴隨式計(jì)算電路8.6線性分組碼的譯碼12/22/202247DepartmentofElectronicsandInformation,NCUTSongPeng8.6.1伴隨式和錯(cuò)誤檢測(cè)(1)如何譯碼？8.612/18.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線性分組碼的譯碼12/22/202248DepartmentofElectronicsandInformation,NCUTSongPeng8.6.1伴隨式和錯(cuò)誤檢測(cè)(1)如何譯碼？返回目錄8.68.6.1伴隨式和錯(cuò)誤檢測(cè)(3)伴隨式的計(jì)算

發(fā)送碼字：C=(cn－1,cn－2,…,c0)信道錯(cuò)誤圖樣：E=(en－1,en－2,…,e0)ei=0，表示第i位無錯(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線性分組碼的譯碼12/22/202249DepartmentofElectronicsandInformation,NCUTSongPeng8.6.1伴隨式和錯(cuò)誤檢測(cè)(3)伴隨式的計(jì)算返回目錄8.8.6.1伴隨式和錯(cuò)誤檢測(cè)(4)伴隨式的特性伴隨式僅與錯(cuò)誤圖樣有關(guān)，而與發(fā)送的具體碼字無關(guān)，即伴隨式僅由錯(cuò)誤圖樣決定；伴隨式是錯(cuò)誤的判別式：若S=0，則判為沒有出錯(cuò)，接收字是一個(gè)碼字；若S≠0，則判為有錯(cuò)。不同的錯(cuò)誤圖樣具有不同的伴隨式，它們是一一對(duì)應(yīng)的。對(duì)二元碼，伴隨式是H陣中與錯(cuò)誤碼元對(duì)應(yīng)列之和。返回目錄8.6線性分組碼的譯碼12/22/202250DepartmentofElectronicsandInformation,NCUTSongPeng8.6.1伴隨式和錯(cuò)誤檢測(cè)(4)伴隨式的特性返回目錄8.(5)舉例：(7,3)碼接收字R的伴隨式計(jì)算若接收字中沒有錯(cuò)誤：設(shè)發(fā)送碼字C=1010011，接收碼字R＝1010011，R與C相同：但接收端譯碼器并不知道就是發(fā)送的碼字根據(jù)接收字R計(jì)算伴隨式：ST=HRT=0T因此，譯碼器判接收字無錯(cuò)8.6.1伴隨式和錯(cuò)誤檢測(cè)8.6線性分組碼的譯碼12/22/202251DepartmentofElectronicsandInformation,NCUTSongPeng(5)舉例：(7,3)碼接收字R的伴隨式計(jì)算8.(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線性分組碼的譯碼12/22/202252DepartmentofElectronicsandInformation,NCUTSongPeng(5)舉例：(7,3)碼接收矢量R的伴隨式計(jì)算88.6.1伴隨式和錯(cuò)誤檢測(cè)(5)舉例：(7,3)碼接收矢量R的伴隨式計(jì)算當(dāng)碼元錯(cuò)誤多于1個(gè)時(shí)：發(fā)送碼字C=1010011，接收碼字R=0011011，伴隨式為：由于ST是第一列和第四列之和，不等于0；但ST與H陣中任何一列都不相同無法判定錯(cuò)誤出在哪些位上，只是發(fā)現(xiàn)有錯(cuò)。返回目錄8.6線性分組碼的譯碼12/22/202253DepartmentofElectronicsandInformation,NCUTSongPeng8.6.1伴隨式和錯(cuò)誤檢測(cè)(5)舉例：(7,3)碼8.6.1伴隨式和錯(cuò)誤檢測(cè)(6)伴隨式計(jì)算電路伴隨式的計(jì)算可用電路來實(shí)現(xiàn)。(7,3)碼為例：接收字R=(r6r5r4r3r2r1r0)，伴隨式：8.6線性分組碼的譯碼12/22/202254DepartmentofElectronicsandInformation,NCUTSongPeng8.6.1伴隨式和錯(cuò)誤檢測(cè)(6)伴隨式計(jì)算電路8.6128.6.1伴隨式和錯(cuò)誤檢測(cè)(6)伴隨式計(jì)算電路伴隨式計(jì)算電路：返回目錄8.6線性分組碼的譯碼12/22/202255DepartmentofElectronicsandInformation,NCUTSongPeng8.6.1伴隨式和錯(cuò)誤檢測(cè)(6)伴隨式計(jì)算電路返回目錄88.6.2糾錯(cuò)譯碼(1)最佳譯碼準(zhǔn)則（最大似然譯碼）(2)查表譯碼法(3)標(biāo)準(zhǔn)陣列(4)舉例(5)結(jié)論8.6線性分組碼的譯碼12/22/202256DepartmentofElectronicsandInformation,NCUTSongPeng8.6.2糾錯(cuò)譯碼(1)最佳譯碼準(zhǔn)則（最大似然譯碼）8.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線性分組碼的譯碼12/22/202257DepartmentofElectronicsandInformation,NCUTSongPeng8.6.2糾錯(cuò)譯碼(1)最佳譯碼準(zhǔn)則（最大似然譯碼）8.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線性分組碼的譯碼12/22/202258DepartmentofElectronicsandInformation,NCUTSongPeng8.6.2糾錯(cuò)譯碼(1)最佳譯碼準(zhǔn)則（最大似然譯碼）返回8.6.2糾錯(cuò)譯碼(2)查表譯碼法按最小距離譯碼，對(duì)有2k個(gè)碼字的(n,k)線性碼，為了找到與接收字R有最小距離的碼字，需將R分別和2k個(gè)碼字比較，以求出最小距離。其中利用“標(biāo)準(zhǔn)陣列”譯碼是最典型的方法。返回目錄8.6線性分組碼的譯碼12/22/202259DepartmentofElectronicsandInformation,NCUTSongPeng8.6.2糾錯(cuò)譯碼(2)查表譯碼法返回目錄8.612/18.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線性分組碼的譯碼12/22/202260DepartmentofElectronicsandInformation,NCUTSongPeng8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列8.612/16/2028.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線性分組碼的譯碼12/22/202261DepartmentofElectronicsandInformation,NCUTSongPeng8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列8.612/16/2028.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列③標(biāo)準(zhǔn)陣列構(gòu)造方法返回8.6線性分組碼的譯碼12/22/202262DepartmentofElectronicsandInformation,NCUTSongPeng8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列返回8.612/16/28.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線性分組碼的譯碼12/22/202263DepartmentofElectronicsandInformation,NCUTSongPeng8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列8.612/16/202(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線性分組碼的譯碼12/22/202264DepartmentofElectronicsandInformation,NCUTSongPeng(3)標(biāo)準(zhǔn)陣列8.6.2糾錯(cuò)譯碼假定某一n重X出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)，即把無錯(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線性分組碼的譯碼12/22/202265DepartmentofElectronicsandInformation,NCUTSongPeng8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列8.612/16/202(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線性分組碼的譯碼12/22/202266DepartmentofElectronicsandInformation,NCUTSongPeng(3)標(biāo)準(zhǔn)陣列8.6.2糾錯(cuò)譯碼見表8.612/16/28.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í)，譯碼才是正確的。可糾正的錯(cuò)誤圖樣：這2n－k個(gè)陪集首稱為可糾正的錯(cuò)誤圖樣。見表8.6線性分組碼的譯碼12/22/202267DepartmentofElectronicsandInformation,NCUTSongPeng8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列見表8.612/16/28.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線性分組碼的譯碼12/22/202268DepartmentofElectronicsandInformation,NCUTSongPeng8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列8.612/16/2028.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線性分組碼的譯碼12/22/202269DepartmentofElectronicsandInformation,NCUTSongPeng8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列8.612/16/2028.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線性分組碼的譯碼12/22/202270DepartmentofElectronicsandInformation,NCUTSongPeng8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列8.612/16/2028.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線性分組碼的譯碼12/22/202271DepartmentofElectronicsandInformation,NCUTSongPeng8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列8.612/16/2028.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線性分組碼的譯碼12/22/202272DepartmentofElectronicsandInformation,NCUTSongPeng8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列8.612/16/2028.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線性分組碼的譯碼12/22/202273DepartmentofElectronicsandInformation,NCUTSongPeng8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列8.612/16/2028.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線性分組碼的譯碼12/22/202274DepartmentofElectronicsandInformation,NCUTSongPeng8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列完備碼特性：圍繞2k8.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線性分組碼的譯碼12/22/202275DepartmentofElectronicsandInformation,NCUTSongPeng8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列8.612/16/2028.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線性分組碼的譯碼12/22/202276DepartmentofElectronicsandInformation,NCUTSongPeng8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列8.612/16/2028.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線性分組碼的譯碼12/22/202277DepartmentofElectronicsandInformation,NCUTSongPeng8.6.2糾錯(cuò)譯碼(3)標(biāo)準(zhǔn)陣列返回目錄8.612/168.6.2糾錯(cuò)譯碼(4)舉例：(6,3)碼的標(biāo)準(zhǔn)陣列返回返回目錄8.6線性分組碼的譯碼12/22/202278DepartmentofElectronicsandInformation,NCUTSongPeng8.6.2糾錯(cuò)譯碼(4)舉例：(6,3)碼的標(biāo)準(zhǔn)陣列返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線性分組碼的譯碼12/22/202279DepartmentofElectronicsandInformation,NCUTSongPeng8.6.2糾錯(cuò)譯碼(5)結(jié)論見表8.612/16/2028.6.2糾錯(cuò)譯碼(5)結(jié)論線性分組碼一般譯碼器（伴隨式譯碼法/查表譯碼法）譯碼器如下圖。這種查表譯碼法具有最小的譯碼延遲和最小的譯碼錯(cuò)誤概率，原則上可用于任何(n,k)線性碼。8.6線性分組碼的譯碼12/22/202280DepartmentofElectronicsandInformation,NCUTSongPeng8.6.2糾錯(cuò)譯碼(5)結(jié)論8.612/16/202288.6.2糾錯(cuò)譯碼(5)結(jié)論舉例：求(7,4)漢明碼的編碼電路和譯碼電路。其系統(tǒng)碼形式：8.6線性分組碼的譯碼12/22/202281DepartmentofElectronicsandInformation,NCUTSongPeng8.6.2糾錯(cuò)譯碼(5)結(jié)論8.612/16/202288.6.2糾錯(cuò)譯碼(5)結(jié)論舉例：求(7,4)漢明碼的編碼電路和譯碼電路。編碼電路：8.6線性分組碼的譯碼12/22/202282DepartmentofElectronicsandInformation,NCUTSongPeng8.6.2糾錯(cuò)譯碼(5)結(jié)論8.612/16/202288.6.2糾錯(cuò)譯碼(5)結(jié)論舉例：求(7,4)漢明碼的編碼電路和譯碼電路。編碼電路：8.6線性分組碼的譯碼12/22/202283DepartmentofElectronicsandInformation,NCUTSongPeng8.6.2糾錯(cuò)譯碼(5)結(jié)論8.612/16/202288.6.2糾錯(cuò)譯碼(5)結(jié)論舉例：求(7,4)漢明碼的編碼電路和譯碼電路。譯碼電路：8.6線性分組碼的譯碼12/22/202284DepartmentofElectronicsandInformation,NCUTSongPeng8.6.2糾錯(cuò)譯碼(5)結(jié)論8.612/16/202288.6.2糾錯(cuò)譯碼(5)結(jié)論舉例：求(7,4)漢明碼的編碼電路和譯碼電路。譯碼電路：8.6線性分組碼的譯碼12/22/202285DepartmentofElectronicsandInformation,NCUTSongPeng8.6.2糾錯(cuò)譯碼(5)結(jié)論8.612/16/202288.7線性分組碼的性能在通信中檢、糾錯(cuò)碼的實(shí)際性能是在統(tǒng)計(jì)上體現(xiàn)出來的。錯(cuò)誤概率：不可檢錯(cuò)誤概率：pud譯碼錯(cuò)誤概率：pwe譯碼失敗概率：pwf比特誤碼率：Pbd差錯(cuò)概率的原因：碼的結(jié)構(gòu)信道特性分析均以BSC信道為模型。12/22/202286DepartmentofElectronicsandInformation,NCUTSongPeng8.7線性分組碼的性能在通信中檢、糾錯(cuò)碼的實(shí)際性能是在統(tǒng)8.7線性分組碼的性能(1)不可檢錯(cuò)誤概率(2)譯碼錯(cuò)誤概率(3)譯碼失敗概率(4)比特誤碼率12/22/202287DepartmentofElectronicsandInformation,NCUTSongPeng8.7線性分組碼的性能(1)不可檢錯(cuò)誤概率(2)譯碼錯(cuò)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－812/22/202288DepartmentofElectronicsandInformation,NCUTSongPeng8.7線性分組碼的性能(1)不可檢錯(cuò)誤概率pud12/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ì)偶碼的重量枚舉式。12/22/202289DepartmentofElectronicsandInformation,NCUTSongPeng8.7線性分組碼的