1第6章信道編碼6.1信道編碼的概念

6.2信道編碼定理

6.3線性分組碼2第6章信道編碼

信道編碼是以信息在信道上的正確傳輸為目標的編碼，可分為兩個層次上的問題：如何正確接收載有信息的信號 －－線路編碼如何避免少量差錯信號對信息內容的影響 －－糾錯編碼36.1信道編碼的概念進行信道編碼是為了提高信號傳輸的可靠性，改善通信系統的傳輸質量，研究信道編碼的目標是尋找具體構造編碼的理論與方法。從原理上看，構造信道碼的基本思路是根據一定的規律在待發送的信息碼元中人為地加入一定的多余碼元(稱為監督碼)，以引入最小的多余度為代價來換取最好的抗干擾性能。

46.1.1信道編碼的分類

對不同的信道需要設計不同類型的信道編碼方案，按照信道特性進行劃分，信道編碼可分為：以糾獨立隨機差錯為主的信道編碼、以糾突發差錯為主的信道編碼和糾混合差錯的信道編碼。從功能上看，信道編碼可分為檢錯(可以發現錯誤)碼與糾錯(不僅能發現而且能自動糾正)碼兩類，糾錯碼一定能檢錯，檢錯碼不一定能糾錯，平常所說的糾錯碼是兩者的統稱。

56.1.1信道編碼的分類根據信息碼元與監督碼元之間的關系，糾錯碼分為線性碼和非線性碼。

線性碼——信息碼元與監督碼元之間呈線性關系，它們的關系可用一組線性代數方程聯系起來。非線性碼——信息碼元與監督校元之間不存在線性關系。

66.1.1信道編碼的分類按照對信息碼元處理的方法的不同，糾錯碼分為分組碼和卷積碼。

分組碼----把信息序列以每k個碼元分組，然后把每組k個信息元按一定規律產生r個多余的監督碼元，輸出序列每組長為n=k+r，則每一碼字的r個校驗元只與本碼字的k個信息位有關，與別的碼字的信息位無關，通常記分組碼為(n,k)。

76.1.1信道編碼的分類其中分組碼又可分循環碼和非循環碼：對循環碼而言，其碼書的特點是，若將其全部碼字分成若干組，則每組中任一碼字中碼元循環移位后仍是這組的碼字；對非循環碼來說，任一碼字中的碼元循環移位后不一定再是該碼書中的碼字。86.1.1信道編碼的分類

卷積碼----把信息序列以每k0(通常較小)個碼元分段，編碼器輸出該段的監督碼元r=n-k0

不但與本段的k0個信息元有關，而且還與其前面L段的信息碼元有關，故記卷積碼為(n,k0,L)。按照每個碼元的取值來分，可有二元碼和多元碼。由于目前的傳輸或存儲系統大都采用二進制的數字系統，所以一般提到的糾錯碼都是指二元碼。

96.1.1信道編碼的分類106.1.2與糾錯編碼有關的基本概念

在通信系統的接收端，若接收到的消息序列R和發送的碼符號序列C不一樣，例如R=(11000)，而C=(10001)，R與C中有兩位不同，即出現兩個錯誤，這種錯誤是由信道中的噪聲干擾所引起的。116.1.2與糾錯編碼有關的基本概念1.碼長、碼重和碼距碼字中碼元的個數稱為碼字的長度，簡稱碼長，用n表示。碼字中非“0”碼元的個數稱為碼字的漢明重量(簡稱碼重，記作W)。對二進制碼來說，碼重W就是碼字中所含碼元“1”的數目，例如碼字“110000”，其碼長n=6，碼重W=2。兩個等長碼字之間對應碼元不相同的數目稱為這兩個碼組的漢明距離(簡稱碼距)。例如碼字“110000”與“100001”，它們的漢明距離D=2。

126.1.2與糾錯編碼有關的基本概念在某一碼集C中，任意兩個碼字之間漢明距離的最小值稱為該碼的最小距離dmin，即：例如：碼組C={0111100，1011011，1101001}的最小碼距dmin=3。從避免碼字受干擾而出錯的角度出發，總是希望碼字間有盡可能大的距離，因為最小碼距代表著一個碼組中最不利的情況。

136.1.2與糾錯編碼有關的基本概念2.錯誤圖樣為了定量地描述信號的差錯，定義收、發碼之“差”為差錯圖樣。差錯圖樣E＝發碼C-

收碼R

（模M）。例：8進制(M=8)碼元，若發碼 ：C=（0,2,5,4,7,5,2）收碼變為：R=（0,1,5,4,7,5,4）差錯圖樣 E=C-R=（0,1,0,0,0,0,6）（模8）二進制碼：E=CR或

C=RE。

146.1.3錯誤的種類1、隨機錯誤：由隨機干擾引起。(前后位置無關，時間無關，差錯以等概率發生)特點：因為干擾是隨機的，所以各碼元是否發生錯誤是相互獨立的，不會成片出錯。2、突發錯誤：由突發干擾引起（前后相關，成堆出現）。特點：因為突發干擾是突然出現的，且能持續一段時間，同時相對功率較大，所以錯誤往往成片出現。常見錯誤有兩種：隨機錯誤和突發錯誤

（在一個突發錯誤持續長度內，開頭和末尾的碼元總是錯的，中間一些碼元不一定都錯，但錯的碼元數較多）如閃電和開關瞬態往往引起突發錯誤。156.1.2與糾錯編碼有關的基本概念3.重復碼和奇偶校驗碼

1)重復碼構成重復碼的方法是當發送某個信源符號ai時，不是只發一個，而是連續重發多個，連續重發的個數越多，重復碼的抗干擾能力就越強，當然效率也越低。

166.1.2與糾錯編碼有關的基本概念不重復時為(1，1)重復碼，如圖所示：重復一次時為(2，1)重復碼，如圖所示：

176.1.2與糾錯編碼有關的基本概念重復二次時為(3，1)重復碼，如圖所示：

186.1.2與糾錯編碼有關的基本概念

2)奇偶檢驗碼奇偶校驗是一種最基本的校驗方法。構成奇偶檢驗碼的方法是在每k個二進制信息位后加上一個奇(偶)監督位(或稱校驗位)，使碼長n=k+r，同時使碼中“1”的個數恒為奇數(或偶數)，如圖所示。在奇偶校驗碼中，監督位r=1，它是一種碼重W為奇數(或偶數)的系統分組碼。

196.1.2與糾錯編碼有關的基本概念206.1.2與糾錯編碼有關的基本概念

奇校驗----如果信息碼元中“1”值的個數為奇數個，則校驗碼元值為“0”；如果信息碼元中“1”值的個數為偶數個，則校驗碼元值為“1”。即所有信息碼元與校驗碼元的模二和等于“1”。偶校驗----如果信息碼元中“1”值的個數為偶數個，則校驗碼元值為“0”；如果信息碼元中“1”值的個數為奇數個，則校驗碼元值為“1”。即所有信息碼元與校驗碼元的模二和等于“0”。

216.1.3檢錯與糾錯原理

要糾正傳輸差錯，首先必須檢測出錯誤。而要檢測出錯誤，常用的方法是將發送端要傳送的信息序列(常為二進制序列)中截取出長度相等的碼元進行分組，每組長度為k，組成k位碼元信息序列M，并根據某種編碼算法以一定的規則在每個信息組的后面產生r個冗余碼元，由冗余碼元和信息碼元一起形成“n位編碼序列”，即信號碼字C，n位的碼字比信息碼長(有n=k+r個碼元)，因而糾錯編碼是冗余編碼。226.1.3檢錯與糾錯原理譯碼就是利用校驗關系進行檢錯、糾錯的，在接收端收到的位碼字中，信息碼元與冗余碼元之間也應符合上述編碼規則，并根據這一規則進行檢驗，從而確定是否有錯誤。這就是差錯控制的基本思想。

236.1.3檢錯與糾錯原理分組碼一般用符號(n,k)表示，其中k是每組二進制信息碼元的數目，n是編碼組的長度(簡稱碼長)，即編碼組的總位數，n-k=r為每碼組中的校驗碼元(或稱監督位)數目。通常，將分組碼規定為具有如圖所示的結構。圖中前面k位為信息位，后面附加r個校驗位。

24奇偶校驗方法。增加偶(或奇)校驗位使得對消息序列而言校驗方程成立，當校驗位數增加時，可以檢測到差錯圖樣的種類數也增加，但同時碼率減小。n重復碼方法。重復消息位使之可以檢測出任意小于n個差錯的錯誤圖樣。等重碼方法。設計碼字中的非“0”符號個數(若是二進制碼則為“1”的個數)恒為常數，使碼集C由全體重量恒等的n長矢量組成。6.1.3檢錯與糾錯原理256.1.3檢錯與糾錯原理表所示為一種用于表示數字“0”到“9”的五中取三等重碼(所有碼字的碼重都等于“3”)的例子。

123456789001011110011011011010001111010111100011101001101101266.1.4檢錯與糾錯方式和能力

1.檢錯與糾錯方式自動請求重發方式----用于檢錯的糾錯碼在譯碼器輸出端給出當前碼字傳輸是否可能出錯的指示，當有錯時按某種協議通過一個反向信道請求發送端重傳已發送的全部或部分碼字，這種糾錯碼的應用方式稱為自動請求重發方式(ARQ，Automatic-Repeat-reQuest)。27前向糾錯方式----用于糾錯的糾錯碼在譯碼器輸出端總要輸出一個碼字或是否出錯的標志，這種糾錯碼的應用方式稱為前向糾錯方式(FEC，Forward-errorcontrol)。另外用于檢錯與糾錯的方式還有混合糾錯(HEC，HybridErrorCorrection)。如圖所示為上述幾種檢錯與糾錯方式示意圖，圖中有斜線的方框表示在該端檢出錯誤。6.1.4檢錯與糾錯方式和能力286.1.4檢錯與糾錯方式和能力29ARQ方式：發送端用編碼器對發送數據進行差錯編碼，通過正向信道送到接收端，而接收端經譯碼器處理后只是檢測有無差錯，不作自動糾正。如檢測到差錯，則利用反向信道反饋信號，請求發送端重發有錯的數據單元，直到接收端檢測不到差錯為止。

6.1.4檢錯與糾錯方式和能力30FEC方式：發送端用編碼器對發送數據進行差錯編碼，在接收端用譯碼器對接收到的數據進行譯碼后檢測有無差錯，通過按預定規則的運算，如檢測到差錯，則確定差錯的具體位置和性質，自動加以糾正，故稱為“前向糾錯”。6.1.4檢錯與糾錯方式和能力31HEC方式：是檢錯重發和前向糾錯兩種方式的混合。發送端用編碼器對發送數據進行便于檢錯和糾錯的編碼，通過正向信道送到接收端，接收端對少量的接收差錯進行自動前向糾正，而對超出糾正能力的差錯則通過反饋重發方式加以糾正，所以是一種糾檢結合的混合方式。6.1.4檢錯與糾錯方式和能力32

2.檢錯與糾錯能力一個糾錯碼的每個碼字都可以形成一個漢明球，因此要能夠糾正所有不多于t位的差錯，糾錯碼的所有漢明球均應不相交，判定糾錯碼的檢、糾錯能力可根據任意兩個漢明球不相交的要求，由碼的最小距離dmin來決定。

6.1.4檢錯與糾錯方式和能力33定理1若糾錯碼的最小距離為dmin，那么如下三個結論的任何一個結論獨立成立：①若要發現e個獨立差錯，則要求最小碼距

②若要糾正t個獨立差錯，則要求最小碼距

③若要求發現e個同時又糾正t個獨立差錯，則6.1.4檢錯與糾錯方式和能力34

6.1.4檢錯與糾錯方式和能力35定理說明，碼的最小距離dmin越大，碼的糾(檢)錯誤的能力越強。但是，隨著多余碼元的增多，信息傳輸速率會降低得越多。通常用=k/n來表示碼字中信息碼元所占的比例，稱為編碼效率，它是衡量碼性能的又一個重要參數。碼率越高，信息傳輸率就越高，但此時糾錯能力要降低，若=1時就沒有糾錯能力了。可見，碼率與糾錯能力之間是有矛盾。6.1.4檢錯與糾錯方式和能力366.1.5矢量空間與碼空間F表示碼元所在的數域，對于二進制碼，F代表二元域{0,1}。設n重有序元素的集合V={Vi

},若滿足條件：V中矢量元素在矢量加運算下構成加群；V中矢量元素與數域F元素的標乘封閉在V中；分配律、結合律成立，則稱集合V是數域F上的n維矢量空間，或稱n維線性空間，n維矢量又稱n重(n-tuples)。376.1.5矢量空間與碼空間對于域F上的若干矢量

線性組合：

線性相關：其中任一矢量可表示為其它矢量的線性組合

線性無關或線性獨立：一組矢量中的任意一個都不可能用其它矢量的線性組合來代替。386.1.5矢量空間與碼空間一組線性無關的矢量，線性組合的集合就構成了一個矢量空間V，這組矢量就是這個矢量空間的基底。n維矢量空間應包含n個基底基底不是唯一的，例：線性無關的兩個矢量（1,0）和（0,1）以及（-1,0）和（0,-1）可張成同一個兩維空間。396.1.5矢量空間與碼空間以（100）為基底可張成一維三重子空間V1，含21=2個元素，即以(010)(001)為基底可張成二維三重子空間V2，含22=4個元素，即以(100)(010)(001)為基底可張成三維三重空間V,含23=8個元素，V1和V2都是V的子空間。406.1.5矢量空間與碼空間每個矢量空間或子空間中必然包含零矢量兩個矢量正交：V1V2＝0兩個矢量空間正交：某矢量空間中的任意元素與另一矢量空間中的任意元素正交正交的兩個子空間V1、V2互為對偶空間(DualSpace)，其中一個空間是另一個空間的零空間（nullspace，也稱零化空間）。416.1.5矢量空間與碼空間碼空間通常qn>>qk，分組編碼的任務是要在n維n重矢量空間的qn種可能組合中選擇其中的qk個構成一個碼空間，其元素就是許用碼的碼集。

消息k長 (n,k)碼字n長

qk

種分組編碼器qn種

k維k重矢量n維n重矢量426.1.5矢量空間與碼空間分組編碼的任務：

①選擇一個ｋ維n重子空間作為碼空間。

②確定由k維k重信息空間到ｋ維n重碼空間的映射方法。碼空間的不同選擇方法，以及信息組與碼組的不同映射算法，就構成了不同的分組碼。436.1.6隨機編碼運用概率統計方法在特定信道條件下對編碼信號的性能作出統計分析，求出差錯概率的上下限邊界，其中最優碼所能達到的差錯概率上界稱作隨機碼界。用這種方法不能得知最優碼是如何具體編出來的，卻能得知最優碼可以好到什么程度，并進而推導出有擾離散信道的編碼定理，對指導編碼技術具有特別重要的理論價值。446.1.6隨機編碼在(N,K)分組編碼器中隨機選定的碼集有qNM種，第m個碼集(記作{c}m)被隨機選中的概率是：設與這種選擇相對應的條件差錯概率是Pe({c}m)，那么全部碼集的平均差錯概率是：456.1.6隨機編碼必定存在某些碼集某些碼集若，就必然存在一批碼集即差錯概率趨于零的好碼一定存在466.1.6隨機編碼碼集點數M=qK占N維矢量空間總點數qN的比例是F=qK/qN

=q-(N-K)

。當K和N的差值拉大即冗余的空間點數增加時，平均而言碼字的分布將變得稀疏，碼字間的平均距離將變大，平均差錯概率將變小。當F0即(N-K)時，能否讓平均差錯概率？Gallager在1965年推導了的上邊界，并證明這個上邊界是按指數規律收斂的。47

E(R)為可靠性函數，也叫誤差指數。碼率：R=(lbM)

/N

，

M是可能的信息組合數，M=qK，N是每碼字的碼元數，R表示每碼元攜帶的信息量，單位是每符號比特（bit/symbol）。R在[0,R0]區間時E(R)~R曲線是斜率為-1（-45）的直線，E(R)反比于R；而當R=C時E(R)=0即可靠性為零。

6.1.7信道編碼定理486.1.7信道編碼定理49

正定理：只要傳信率R小于信道容量C，總存在一種信道碼（及解碼器），可以以所要求的任意小的差錯概率實現可靠的通信。逆定理：信道容量C是可靠通信系統傳信率R的上邊界，如果R>C，就不可能有任何一種編碼能使差錯概率任意小。6.1.7信道編碼定理506.2糾錯編譯碼的基本原理與分析

R不變，信道容量大者其可靠性函數E(R)也大；C不變，碼率減小時其可靠性函數E(R)增大E(R) R0R1<R2C1

<C2

增大E(R)的途徑516.2.1糾錯編碼的基本思路對于同樣的碼率，信道容量大者其可靠性函數E(R)也大；對于同樣的信道容量，碼率減小時其可靠性函數E(R)增大。可采取以下措施減小差錯概率。(1)增大信道容量C增大E(R)的途徑①擴展帶寬。②加大功率。③降低噪聲。52(2)減小碼率R①q，N不變而減小K，這意味著降低信息源速率，每秒少傳一些信息。②q，K不變而增大N，這意味著提高符號速率（波特率），占用更大帶寬。③N，K不變而減小q，這意味著減小信道的輸入、輸出符號集，在發送功率固定時提高信號間的區分度，從而提高可靠性。6.2.1糾錯編碼的基本思路53(3)增加碼長N隨著N增大，矢量空間以指數量級增大，從統計角度而言碼字間距離也將加大，從而可靠性提高。另外，碼長N越大，其實際差錯概率就越能符合統計規律。6.2.1糾錯編碼的基本思路54糾錯能力的獲取

(1)利用冗余度冗余度：在信息流中插入冗余比特，這些冗余比特與信息比特之間存著特定的相關性。冗余的資源：時間，頻帶，功率，設備復雜度。

6.2.1糾錯編碼的基本思路556.2.1糾錯編碼的基本思路

(2)噪聲均化噪聲均化：讓差錯隨機化，以便更符合編碼定理的條件從而得到符合編碼定理的結果。基本思想：設法將危害較大的、較為集中的噪聲干擾分攤開來，使不可恢復的信息損傷最小。①增加碼長N②卷積③交錯（或稱交織）

566.2.2最優譯碼與最大似然譯碼譯碼器的任務是從受損的信息序列中盡可能正確地恢復出原信息。譯碼算法的已知條件是：①實際接收到的碼字序列{r},r=(rn,rn-1,…,r1)②發端所采用的編碼算法和該算法產生的碼集Xn,滿足③信道模型及信道參數。576.2.2最優譯碼與最大似然譯碼586.2.2最優譯碼與最大似然譯碼1.最佳譯碼(最大后驗概率譯碼)在已知r的條件下找出可能性最大的發碼作為譯碼估值，即令596.2.2最優譯碼與最大似然譯碼2.最大似然譯碼在已知r的條件下使先驗概率最大的譯碼算法

也叫似然函數。利用貝葉斯公司可以建立先驗概率和后驗概率之間的關系：606.2.2最優譯碼與最大似然譯碼如果①構成碼集的個碼字以相同概率發送，滿足。②對于任何r都有相同的值，滿足。則最大等效于的最大，在此前提下最佳譯碼等效于最大似然譯碼。616.2.2最優譯碼與最大似然譯碼對于無記憶信道，

例：BSC信道的最大似然譯碼可以簡化為最小漢明距離譯碼。漢明距離譯碼是一種硬判決譯碼。由于BSC信道是對稱的，只要發送的碼字獨立、等概，漢明距離譯碼也就是最佳譯碼。626.3線性分組碼m=(mk-1,…,m1,m0)c=(cn-1,…,c1,c0)碼字c消息m(n,k)分組編碼器

碼集C能否構成n維n重矢量空間的一個k維n重子空間？如何尋找最佳的碼空間？qk個信息元組以什么算法一一對應映射到碼空間。

碼率－－編碼效率：Rc

=k/n

636.3線性分組碼為了敘述方便，以下認為碼失、碼字、碼組是同義詞，對n重矢量、1n矩陣、行矢量等的數學表達式也不作嚴格區別。646.3線性分組碼設有等概出現的M組待傳信源消息，每組有k位，即。今加上r個多余位，使每組消息變成n=k+r位。而n位長的二進制序列共有2n個，但由于信息組只有2k個，故有2n-2k個n位序列不是碼字。設碼字的形式為：656.3.1生成矩陣和校驗矩陣

線性分組碼碼空間C是由k個線性無關的基底張成的k維n重子空間，碼空間的所有元素（即碼字）都可以寫成k個基底的線性組合，即這種線性組合特性正是線性分組碼名稱的來歷。顯然，研究線性分組碼的關鍵是研究基底、子空間和映射規則，如圖所示

666.3.1生成矩陣和校驗矩陣Hn-k維n重對偶空間Dk維k重信息組空間mk維n重碼空間cGn維n重空間Vn676.3.1生成矩陣和校驗矩陣用gi表示第i個基底并寫成矩陣再將k個基底排列成k行n列的G矩陣686.3.1生成矩陣和校驗矩陣碼空間的所有元素（即碼字）都可以寫成k個基底的線性組合。由于k個基底即G的k個行矢量線性無關，矩陣G的秩一定等于k。當信息元確定后，碼字僅由G矩陣決定，因此我們稱這k×n矩陣G為該(n,k)線性分組碼的生成矩陣。696.3.1生成矩陣和校驗矩陣1.生成矩陣G(k×n)的特點想要保證(n,k)線性分組碼能夠構成k維n重子空間，G

的k個行矢量gk-1,…,g1,g0必須是線性無關的，只有這樣才符合作為基底的條件。由于基底不是唯一的，所以G也就不是唯一的。不同的基底有可能生成同一碼集，但因編碼涉及碼集和映射兩個因素，碼集一樣而映射方法不同也不能說是同樣的碼。706.3.1生成矩陣和校驗矩陣2.系統形式的生成矩陣

(n,k)碼的任何生成矩陣都可以通過行運算（以及列置換）簡化成“系統形式”。

Ik是k×k單位矩陣，P是k×(n-k)矩陣。

716.3.1生成矩陣和校驗矩陣3.生成的碼字C

前k位由單位矩陣Ik決定，等于把信息組m原封不動搬到碼字的前k位；其余的n-k位叫冗余位或一致校驗位，是前k個信息位的線性組合。這樣生成的（n,k）碼叫做系統碼。若生成矩陣G不具備系統形式，則生成的碼叫做非系統碼。系統化不改變碼集，只是改變了映射規則。726.3.1生成矩陣和校驗矩陣4.系統碼若通過行運算和列置換能將兩個生成矩陣G互等，則稱這兩個G等效。非系統碼的G可通過運算轉變為系統碼的G。等效的兩個G生成的兩個(n,k)線性碼也是等效的。因此，每個(n,k)線性碼都可以和一個系統的(n,k)線性碼等效。736.3.1生成矩陣和校驗矩陣5.空間構成n維n重空間有相互正交的n個基底，選擇k個基底構成碼空間C，選擇另外的(n-k)個基底構成空間H，C和H是對偶的CHT＝0,GHT=0。746.3.1生成矩陣和校驗矩陣6.校驗矩陣將H空間的n-k個基底排列起來可構成一個(n-k)×n矩陣，稱為校驗矩陣H。用來校驗接收到的碼字是否是正確的；G是(n,k)碼的生成矩陣，H是它的校驗矩陣；H是(n,n-k)對偶碼的生成矩陣，它的每一行是一個基底。G則是它的校驗矩陣。756.3.1生成矩陣和校驗矩陣以(7,3)線性分組碼為例。信息位k=3，則校驗元個數為r=n-k，設碼字為：,其中為信息元；為校驗元。每個碼元取值為“0”或“1”。設某(7,3)線性分組碼各碼字的校驗元與信息元之間的關系由下述方程決定：766.3.1生成矩陣和校驗矩陣

稱此方程為該（7,3）線性分組碼的校驗方程，由于該碼系的所有碼字都按同一規則確定與校驗，故又稱為一致校驗方程。776.3.1生成矩陣和校驗矩陣如：信息組為101，即代入一致校驗方程得：所以由信息組101編出的可送給信道傳輸的、具有一定糾錯能力的碼字為：1010011。同理可求出與其他7個信息組相對應的碼字見下表：信息組對應碼字對應碼字信息組00000101001111111010110001110100100111001110100000001110100110100110100111001110786.3.1生成矩陣和校驗矩陣為了運算方便，可將一致校驗方程組寫成矩陣形式：796.3.1生成矩陣和校驗矩陣設則：或：（4×3）單位子陣806.3.1生成矩陣和校驗矩陣線性分組碼的一致生成矩陣與一致校驗矩陣之間有著非常密切的關系，這種關系非常重要。下面說明它們的關系：由于生成矩陣G的每一行都是一個碼字，而或者816.3.1生成矩陣和校驗矩陣更進一步：結論：(n,k)線性分組碼的一致生成矩陣G與一致校驗矩陣H之間可方便地相互轉換。或者826.3.1生成矩陣和校驗矩陣例6.1(6,3)線性分組碼，其生成矩陣是836.3.1生成矩陣和校驗矩陣求：(1)計算碼集，列出信息組與碼字的映射關系。(2)將該碼系統化處理后，計算系統碼碼集并列出映射關系。(3)計算系統碼的校驗矩陣H。若收碼r=[100110],檢驗它是否碼字？(4)根據系統碼生成矩陣畫出編碼器電原理圖。846.3.1生成矩陣和校驗矩陣解(1)由得

令得信息碼字系統碼字000000000000000001 011101 001011010 110001 010110011 101100 011101100 111010 100111101 100111 101100110 001011 110001111010110 111010856.3.1生成矩陣和校驗矩陣(2)對G作行運算，得系統化后的生成矩陣Gs

866.3.1生成矩陣和校驗矩陣(3)876.3.1生成矩陣和校驗矩陣(4)m0m1m2c0c1c2輸入輸出886.3.2線性分組碼的糾錯能力

N重碼矢可與N維矢量空間XN中的一個點對應，全體碼字所對應的點構成矢量空間里的一個子集。發碼一定在這個子集里，傳輸無誤時的收碼也一定位于該子集。當出現差錯時，接收的N重矢量有兩種可能：一種是對應到子集外空間某一點；另一種對應到該子集，卻對應到該子集的另一點上。

896.3.2線性分組碼的糾錯能力定理6.1任何最小距離dmin的線性分組碼，其檢錯能力為（dmin-1）,糾錯能力t為定理6.2線性分組碼的最小距離等于碼集中非零碼字的最小重量

dmin=min{w(Ci

)} CiC

及Ci

0906.3.2線性分組碼的糾錯能力

定理6.3(n,k)線性分組碼最小距離等于dmin的充要條件是：校驗矩陣H中有（dmin-1)列線性無關。

定理6.4(n,k)線性分組碼的最小距離必定小于等于(n-k+1)916.3.2線性分組碼的糾錯能力例：(7，4)線性碼

926.3.2線性分組碼的糾錯能力各列都不相同，任意2列之和不等于0，2列線性無關；任意2列之和一定等于矩陣中某一列，任意3列線性相關。所以該碼的最小距離為3，小于n-k+1=4。

(n,k)線性碼最小距離dmin的上邊界是n-k+1。如果我們設計的(n,k)線性碼的dmin達到了n-k+1，就是達到了設計性能的極點。因此，dmin=n-k+1的碼稱為極大最小距離碼

(MDC–MaximizedminimumDistanceCode)。936.3.3伴隨式與標準陣列譯碼

定義差錯圖案E

二進制碼中模2加與模2減是等同的，因此有E=R+C

及R=C+E

1.伴隨式S的定義因為CHT=0(碼字和校驗矩陣的正交性)所以RHT=(C+E)HT=CHT+EHT=EHT946.3.3伴隨式與標準陣列譯碼

1、如果收碼無誤：必有R=C即E=0，則EHT=0RHT=0。

2、如果收碼有誤：即E

0，則RHT

=EHT0。在HT固定的前提下，RHT僅僅與差錯圖案E有關，而與發送碼C無關。定義伴隨式S

S=(sn-k-1,…,s1,s0)=RHT=EHT

956.3.3伴隨式與標準陣列譯碼

2.伴隨式S的意義從物理意義上看，伴隨式S并不反映發送的碼字是什么，而只是反映信道對碼字造成怎樣的干擾。

差錯圖案E是n重矢量，共有2n個可能的組合，而伴隨式S是(n-k)重矢量，只有2n-k個可能的組合，因此不同的差錯圖案可能有相同的伴隨式。

接收端收到R后，因為已知HT，可求出S=RHT

；如果能知道對應的E，則通過C=R+E而求得C。966.3.3伴隨式與標準陣列譯碼

3.差錯圖案E的求解可以通過解線性方程求解E：

976.3.3伴隨式與標準陣列譯碼得到線性方程組：

sn-k-1=en-1h(n-k-1)(n-1)+…+e1h(n-k-1)1+e0h(n-k-1)0

s1=en-1h1(n-1)+…+e1h11+e0h10

s0=en-1h0(n-1)+…+e1h01+e0h00986.3.3伴隨式與標準陣列譯碼上述方程組中有n個未知數en-1,…e1,e0

，卻只有n-k個方程，可知方程組有多解。在有理數或實數域中，少一個方程就可能導致無限多個解，而在二元域中，少一個方程導致兩個解，少兩個方程四個解，以此類推，少n-(n-k)=k個方程導致每個未知數有2k個解。到底取哪一個作為附加在收碼R上的差錯圖案E的估值呢？

996.3.3伴隨式與標準陣列譯碼概率譯碼：把所有2k個解的重量(差錯圖案E中1的個數)作比較，選擇其中最輕者作為E的估值。該方法概念上很簡單但計算效率不高。依據：若BSC信道的差錯概率是p，則長度n的碼中錯誤概率：1006.3.3伴隨式與標準陣列譯碼0個錯1個錯2個錯…n個錯

(1-p)n

p(1-p)n-1

p2(1-p)n-2

pn

>>>>>>…>>由于p<<1，出錯越少的情況，發生概率越大，E的重量越輕，所以該譯碼方法實際上體現了最小距離譯碼準則，即最大似然譯碼。依據：若BSC信道的差錯概率是p，則長度n的碼中錯誤概率：1016.3.3伴隨式與標準陣列譯碼

方法：(1)按最可能出現的2r個差錯圖案E，計算相應的伴隨式S，并構造伴隨式一差錯圖案表[(S,E)]。(2)對接收向量R計算伴隨式S。(3)查[(S,E)]表得E。(4)糾錯計算C=R-E。1026.3.3伴隨式與標準陣列譯碼例：設某（7,3）線性分組碼的一致校驗矩陣為：發送端發送的碼字為（注：接收端譯碼器并不知道發送碼字）。試討論下面三種接收情況下的判錯情形：1036.3.3伴隨式與標準陣列譯碼①接收端接收的碼字為②接收端接收的碼字為③接收端接收的碼字為解:①當接收端接收的碼字為時，故譯碼器判為沒錯。1046.3.3伴隨式與標準陣列譯碼②當接收端接收的碼字為時，又由其H陣知該(7,3)碼為能糾1個錯誤的碼型，且ST正好等于H陣中的第二列，因此可判定第二位有錯。1056.3.3伴隨式與標準陣列譯碼③當接收端接收的碼字為時，譯碼器判為有錯。又由于此時的伴隨式ST與H中任一列均不同，故一定出現了兩位或兩位以上的錯誤，譯碼器無法判定錯誤究竟出現在哪些位上。1066.3.3伴隨式與標準陣列譯碼伴隨式計算電路(以上例中的(7,3)碼為例)設接收字為1076.3.3伴隨式與標準陣列譯碼碼字輸入移位寄存器組半加器1086.3.3伴隨式與標準陣列譯碼伴隨式計算電路組合邏輯電路糾錯譯碼電路…………輸入（信道輸出）譯碼輸出1096.3.3伴隨式與標準陣列譯碼4.標準陣列譯碼表上述的概率譯碼，如每接收一個碼R就要解一次線性方程，那就太麻煩了。好在伴隨式S的數目是有限的2n-k個，如果n-k不太大，我們可以預先把不同S下的方程組解出來，把各種情況下的最大概率譯碼輸出列成一個碼表。這樣，在實時譯碼時就不必再去解方程，而只要象查字典那樣查一下碼表，這樣構造的表格叫做標準陣列譯碼表。1106.3.3伴隨式與標準陣列譯碼表中所列碼字是接收到的碼字R；將沒有任何差錯時的收碼R放在第一行，收碼等于發碼R=C(CCi,i=0,1,…2k-1),差錯圖案為全零E0=(0,0…0)，伴隨式為全零S0=(0,0…0)。由于有2k個碼字，碼表有2k列。

在第2到第n+1的n行中差錯圖案的所有重量為1(共n個)。1116.3.3伴隨式與標準陣列譯碼如果(1+n)<2n-k，再在下面行寫出全部帶有2個差錯的圖案(共個)。如果總行數(1+n+)仍然小于2n-k，再列出帶有3個差錯的圖案，以此類推，直到放滿2n-k行，每行一個Ej,對應一個不同的伴隨式Sj。這樣，表的行數2n-k正好等于伴隨式的數目。1126.3.3伴隨式與標準陣列譯碼S0E0S1E1

SjEj

E0+C0=0+0=0E0+C1=C1E0+Ci=CiE1+C0=E1

E1+CiEj+C0=EjEj+C1Ej+Ci

E1+C1

1136.3.3伴隨式與標準陣列譯碼譯碼表中有2n-k行，每行是一個陪集，每陪集的第一個元素(位于第一列)叫陪集首。同一陪集（同一行）中的所有元素對應共同的一個伴隨式。第一行陪集的陪集首是全零伴隨式S0所對應的全零差錯圖案E0(無差錯)，而第j行陪集的陪集首是伴隨式Sj所對應的重量最小的差錯圖案Ej(C0=0,Rj=Ej)。1146.3.3伴隨式與標準陣列譯碼譯碼表中有2k列，每列是一個子集，每子集的第一個元素(位于第一行)叫子集頭。同一子集（同一列）中的所有元素對應同一個碼字，第一列子集的子集頭是全零碼字C0，而第i列子集的子集頭是碼字Ci(E0=0,Ri=Ci)。1156.3.3伴隨式與標準陣列譯碼例6.3一個(5,2)系統線性碼的生成矩陣是G=設收碼R=(10101)，構造標準陣列譯碼表，譯出發碼的估值解：(1)構造標準陣列譯碼表。分別以信息組m=(00)、(01)、(10)、(11)及已知的G求得4個許用碼字為C1=(00000)、C2=(10111)、C3=(01101)、C4=(11010)。1166.3.3伴隨式與標準陣列譯碼求出校驗矩陣：1176.3.3伴隨式與標準陣列譯碼列出方程組：伴隨式有2n-k=23=8種組合，差錯圖案中代表無差錯的有一種，代表一個差錯的圖案有種，代表兩個差錯的圖案有種。只需挑選其中的兩個，挑選方法可有若干種，不是唯一的。1186.3.3伴隨式與標準陣列譯碼先將Ej=(00000)、(10000)、(01000)、(00100)、(00010)、(00001)代入上面的線性方程組，解得對應的Sj分別是(000)、(111)、(101)、(100)、(010)、(001)。剩下的伴隨式中，(011)所對應的差錯圖案是2k個即(00011)、(10100)、(01110)、(11001),其中(00011)和(10100)并列重量最輕，任選其中一個如(00011)。同樣可得伴隨式(110)所對應的最輕差錯圖案之一是(00110)。1196.3.3伴隨式與標準陣列譯碼S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=001101000101011111001206.3.3伴隨式與標準陣列譯碼將接收碼R＝10101譯碼可選以下三種方法之一譯碼：(1)直接搜索碼表，查得(10101)所在列的子集頭是(10111)，因此譯碼輸出取為(10111)。

(2)先求伴隨式RHT=(10101)

HT=(010)=S4，確定S4所在行，再沿著行對碼表作一維搜索找到(10101),最后順著所在列向上找出碼字(10111)。1216.3.3伴隨式與標準陣列譯碼

(3)先求出伴隨式RHT=(010)=S4并確定S4所對應的陪集首（差錯圖案）E4=(00010)，再將陪集首與收碼相加得到碼字C=R+E4=(10101)+(00010)=(10111)。上述三種方法由上而下，查表的時間下降而所需計算量增大，實際使用時可針對不同情況選用。1226.3.3伴隨式與標準陣列譯碼對上例作進一步分析，還可以看到，該(5,2)碼的dmin=3,糾錯能力是t=INT[(3-1)/2]=1。因此，譯碼陣列中只有前6行具有唯一性、可靠性，真正體現了最大似然譯碼準則，而第7、8行的差錯圖案(00011)和(00110)中包含兩個“1”，已超出了t=1的糾錯能力，譯碼已不可靠。1236.3.3伴隨式與標準陣列譯碼比如，當收碼R＝(10100)時，根據碼表譯出的碼字是(10111)，與收碼R的漢明距離是2，然而收碼R與全零碼字(00000)的漢明距離也是2，為什么不能譯成(00000)呢？事實上，碼表的第7、8行本身就不是唯一的。注意在碼表計算過程中，伴隨式(011)所對應的4個差錯圖案中有兩個并列重量最輕，如果當時選的不是(00011)而是(10100)，那么碼表第7行就不是現在這樣了。1246.3.4完備碼(Perfectcode)任何一個二元(n,k)線性分組碼都有2n-k個伴隨式，假如該碼的糾錯能力是t，則對于任何一個重量小于等于t的差錯圖案，都應有一個伴隨式與之對應，也就是說，伴隨式的數目滿足條件上式稱作漢明限，任何一個糾t碼都應滿足上述條件。1256.3.4完備碼(Perfectcode)某二元(n,k)線性分組碼能使等式

成立，即該碼的伴隨式數目不多不少恰好和不大于t個差錯的圖案數目相等，相當于在標準譯碼陣列中能將所有重量不大于t的差錯圖案選作陪集首，而沒有一個陪集首的重量大于t，這時的校驗位得到最充分的利用。這樣的二元(n,k)線性分組碼稱為完備碼。

1266.3.4完備碼(Perfectcode)1.漢明碼(HammingCode)

漢明碼不是指一個碼，而是代表一類碼。漢明碼的糾錯能力t=1，既有二進制的，也有非二進制的。二進制時，漢明碼碼長n和信息位k服從以下規律：(n,k)=(2m-1,2m-1-m)

其中m=n-k，是正整數。當m＝3、4、5、6、7、8…時，有漢明碼(7,4)、(15,11)、(31,26)、(63,57)、(127,120)……。1276.3.4完備碼(Perfectcode)漢明碼是完備碼，因為它滿足上述等式。1286.3.4完備碼(Perfectcode)漢明碼的校驗矩陣H具有特殊的性質，能使構造方法簡化。一個(n,k)碼的校驗矩陣有n-k行和n列，二進制時n-k個碼元所能組成的列矢量總數是2n-k-1,恰好和校驗矩陣的列數n=2m-1相等。只要排列所有列，通過列置換將矩陣H轉換成系統形式，就可以進一步得到相應的生成矩陣G。1296.3.4完備碼(Perfectcode)例6.4構造一個m=3的二元(7，4)漢明碼。解：先利用漢明碼的特性構造一個(7，4)漢明碼的校驗矩陣H，再通過列置換將它變為系統形式：

0001111列置換1110100 H= 0110011 0111010=[PT

I3] 1010101 1101001再得生成矩陣G為

1000101 G=[I4

P]=0100111 0010110 0001011 1306.3.4完備碼(Perfectcode)

2.高萊（Golay）碼是二進制（23，12）線性碼，其最小距離dmin＝7，糾錯能力t=3。是完備碼，因為滿足等式

223-12=2048=在(23,12)碼上添加一位奇偶位即得二進制線性（24，12）擴展高萊碼，其最小距離dmin＝8。1316.3.5循環碼

1.循環碼的定義定義1：如將一個碼系的全部碼字分成若干組，則每組的所有碼字可由其中任一碼字的循環移位得到。如(7,3)循環碼分成兩個組

(0000000)

(0010111)(0101110)(1011100)(0111001)(1110010)(1100101)(1001011)1326.3.5循環碼又如：(7,4)循環碼分成四個組

(0000000)

(1111111)

(1000101)(0001011)(0010110)(0101100)(1011000)(0110001)(1100010)

(1001110)(0011101)(0111010)(1110100)(1101001)(1010011)(0100111)1336.3.5循環碼

定義2:一個(n,k)線性分組碼C，若它一個碼矢的每一循環移位都是C的一個碼字，則C是一個循環碼。

循環碼是一種線性碼，因此線性碼的一切特性均適合于循環碼；但它的特殊性是其循環性，碼字集合或者說碼組中任意一個碼字的循環移位得到的序列仍是該碼字集合中的碼字，即它對循環操作滿足封閉性。1346.3.5循環碼2.循環碼的多項式描述一般(n,k)線性分組碼的k個基底之間不存在規則的聯系，因此需用k個基底組成生成矩陣來表示一個碼的特征。而循環碼的k個基底可以是同一個基底循環k次得到，因此用一個基底就足以表示一個碼的特征。既然只有一個基底，就無需矩陣，只要用多項式作為數學工具就足夠了。1356.3.5循環碼3.循環碼的多項式定義把碼字C＝[cn-1cn-2

…c1c0]與一個不大于n-1次的碼多項式C(x)對應起來。

碼多項式C(x)定義為：

C(x)=cn-1xn-1+cn-2xn-2

+…+c1x+c0

對于二進制碼，ci{0,1},i=0,…，n-1。1366.3.5循環碼循環移一位：(cn-1cn-2

…c1c0)(cn-2

…c1c0cn-1)循環移一位：C0(x)=cn-1xn-1+cn-2xn-2+…+c1x+c0

C1(x)=

cn-2xn-1+cn-3xn-2+…+c0x+cn-1比較循環移位的前后，可用如下的多項式運算來表達循環移位

移1位：

C1(x)=xC0(x) mod(xn+1)

移2位：

C2(x)=xC1(x)=x2C0(x) mod(xn+1)

移n-1位：Cn-1(x)=xCn-2(x)=xn-1C0(x) mod(xn+1)1376.3.5循環碼4.碼字的組成根據碼空間封閉性，碼字的線性組合仍是碼字。C(x)=a0C0(x)+a1xC0(x)+a2x2C0(x)+…+an-1xn-1C0(x)=(a0+a1x

+a2x2+…+an-1xn-1)C0(x)=A(x)C0(x) mod(xn

+1) 其中C0(x)是一個碼多項式，而A(x)是次數不大于n-1的任意多項式。對于二進制碼，ai{0,1},i=0,…，n-1。1386.3.5循環碼5.生成多項式C(x)=m(x)g(x)碼多項式信息多項式生成多項式

生成多項式不是唯一的；

g(x)＝x

n-k

+gn-k-1x

n-k-1+…+g2x2+g1x+1

是(n-k)次的首一碼多項式，即(n-k)次項的系數為1。g(x)一定是(xn+1)的因子。1396.3.5循環碼

幾個關于生成多項式的定理

定理1：在(n,k)循環碼中，生成多項式g(x)是唯一的(n-k)次多項式，且次數是最低的。定理2：在(n,k)循環碼中，每個碼多項式C(x)都是生成多項式g(x)的倍式，而每個g(x)倍式的次數小于或等于(n-1)的多項式必為(n,k)循環碼的碼多項式。1406.3.5循環碼

定理3：(n,k)循環碼的生成多項式g(x)是xn+1的因式，即xn+1=h(x)g(x)定理4：若g(x)是一個(n-k)次多項式，且為xn+1的因式，則g(x)生成唯一一個(n-k)循環碼碼系。以上幾個定理說明：構建一個(n,k)循環碼時，只要分解多項式xn+1的因式，從中取出(n-k)次因式作生成多項式即可。1416.3.5循環碼6.校驗多項式多項式xn+1可因式分解為xn+1＝g(x)h(x)的形式；如果g(x)代表(n,k)循環碼的生成多項式，則h(x)代表該循環碼的一致校驗多項式，其階次為k。h(x)的校驗作用表現在：任何碼多項式C(x)與h(x)的模xn+1乘積一定等于0，而非碼字與h(x)的乘積必不為0。

C(x)h(x)=m(x)g(x)h(x)=m(x)(xn+1)=0mod(xn+1)1426.3.5循環碼例6.5研究一個長度n=7的循環碼的構成方法對(x7+1)作分解，找出n-k次因式。

x7+1＝(x+1)(x3+x2+1)(x3+x+1)，

n-k因式g(x)對偶式h(x) 循環碼

1(x+1) (x3+x2+1)(x3+x+1) (7,6)3(x3+x2+1)(x+1)(x3+x+1) (7,4)3(x3+x+1)(x+1)(x3+x2+1) (7,4)4(x+1)(x3+x2+1)(x3+x+1) (7,3)4(x+1)(x3+x+1)(x3+x2+1) (7,3)6(x3+x2+1)(x3+x+1)

(x+1) (7,1)1436.3.5循環碼構成(7,3)循環碼： 選g(x)=(x+1)(x3+x+1)=(x4+x3+x2+1)，則C(x)=m(x)g(x)=(m2x2+m1x+m0)(x4+x3+x2+1)。當輸入信息m=(011)時，m(x)=(x+1)，C(x)=(x+

1)(x4＋x3＋x2＋1)=x5+x2+x1+

1， 對應碼矢C=(0100111)。1446.3.5循環碼信息矢量m(m2m1m0)碼矢C(c6c5c4c3c2c1c0)000001010011100101110111000000000111010111010010011111101001101001100111010100111456.3.5循環碼6.系統循環碼碼字的前k位原封不動照搬信息位而后面(n-k)位為校驗位：C(x)=xn-km(x)+r(x)產生系統循環碼的方法：將信息多項式m(x)預乘xn-k，即右移(n-k)位；將xn-km(x)除以g(x)，得余式r(x)；得系統循環碼的碼多項式：C(x)=xn-km(x)+r(x)。1466.3.5循環碼例6.6(7,3)循環碼生成多項式是g(x)=x4+x3+x2+1，產生系統循環碼。解：先以輸入信息m=(011)即m(x)=(x+1)為例，①.xn-km(x)=x4(x+1)=x5+x4

②.(x5+x4)除以(x4+x3+x2+

1)，得余式(x3+x)③.C(x)=xn-km(x)

+r(x)＝(x5+x4)+(x3+x),