6.3.1一般概念6.3.2線性分組碼的監(jiān)督方程和監(jiān)督矩陣6.3.3線性分組碼的生成矩陣6.3.4線性分組碼的編碼6.3.5線性分組碼的譯碼6.3.6漢明碼6.3線性分組碼8/14/202316.3.1一般概念6.3線性分組碼8/1/一、名詞解釋線性分組碼：通過預(yù)定的線性運(yùn)算將長為k位的信息碼組變換成n長的碼字(n>k)。由2k個(gè)信息碼組所編成的2k個(gè)碼字集合，稱為線性分組碼。碼矢：一個(gè)n長的碼字可以用矢量來表示C=(Cn－1,Cn－2,…,C1,C0)所以碼字又稱為碼矢。(n,k)線性碼：信息位長為k，碼長為n的線性碼。編碼效率/編碼速率/碼率：R=k/n。它說明了信道的利用效率，R是衡量碼性能的一個(gè)重要參數(shù)。6.3.1一般概念8/14/20232一、名詞解釋6.3.1一般概念8/1/20232線性分組碼的編碼：線性分組碼的編碼過程分為兩步：把信息序列按一定長度分成若干信息碼組，每組由k位組成；編碼器按照預(yù)定的線性規(guī)則(可由線性方程組規(guī)定)，把信息碼組變換成n長(n>k)碼字，其中(n－k)個(gè)附加碼元是由信息碼元的線性運(yùn)算產(chǎn)生的。信息碼組長為k位，若有2k個(gè)不同的信息碼組，則有2k個(gè)碼字與它們一一對應(yīng)。8/14/20233線性分組碼的編碼：線性分組碼的編碼過程分為兩步：8/1/20線性分組碼是前向糾錯(cuò)碼，它可以在無需重發(fā)的情況下檢測出有限個(gè)錯(cuò)碼，并加以糾正。當(dāng)其他改善手段（如增加發(fā)射功率或使用復(fù)雜的解調(diào)器）不切實(shí)際時(shí)，分組碼可以用來改善通信系統(tǒng)的性能。在分組編碼器中，k個(gè)信息位被編成n位，從而對k個(gè)信息位增加了n-k個(gè)冗余位，而冗余位的作用是檢測和糾正錯(cuò)碼。8/14/20234線性分組碼是前向糾錯(cuò)碼，它可以在無需重發(fā)(1)監(jiān)督方程編碼就是給已知信息碼組按預(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ì)算6.3.2線性分組碼的監(jiān)督方程和監(jiān)督矩陣8/14/20235(1)監(jiān)督方程6.3.2線性分組碼的監(jiān)督方程和監(jiān)督矩監(jiān)督方程的一般定義：通過已知的信息元得到監(jiān)督元規(guī)則的一組方程稱為監(jiān)督方程。由于所有碼字都按同一規(guī)則確定，又稱為一致監(jiān)督方程。由于監(jiān)督方程是線性的，即監(jiān)督元和信息元之間是線性運(yùn)算關(guān)系，所以由線性監(jiān)督方程所確定的分組碼是線性分組碼。[參見以下(7,3)分組碼的例子]6.3.2線性分組碼的監(jiān)督方程和監(jiān)督矩陣8/14/20236監(jiān)督方程的一般定義：6.3.2線性分組碼的監(jiān)督方程和監(jiān)(2)舉例若已知信息碼組為(101)，即C6=1,C5=0,C4=1代入方程(5.1)得：C3=0,C2=0,C1=1,C0=1由信息碼組(101)編出的碼字為(1010011)。其它7個(gè)碼字如表5.1。6.3.2線性分組碼的監(jiān)督方程和監(jiān)督矩陣8/14/20237(2)舉例6.3.2線性分組碼的監(jiān)督方程和監(jiān)督矩陣8(3)監(jiān)督矩陣為了運(yùn)算方便，將式(5.1)監(jiān)督方程寫成矩陣形式，得式(5.2)可寫成H

CT=0T或

C

HT=0CT、HT、0T分別表示C、H、0的轉(zhuǎn)置矩陣。6.3.2線性分組碼的監(jiān)督方程和監(jiān)督矩陣8/14/20238(3)監(jiān)督矩陣6.3.2線性分組碼的監(jiān)督方程和監(jiān)督矩系數(shù)矩陣H的后四列組成一個(gè)(4×4)階單位子陣，用I4表示，H的其余部分用P表示6.3.2線性分組碼的監(jiān)督方程和監(jiān)督矩陣8/14/20239系數(shù)矩陣H的后四列組成一個(gè)(4×4)階單位子陣，用推廣到一般情況：對(n,k)線性分組碼，每個(gè)碼字中的r(r=n－k)個(gè)監(jiān)督元與信息元之間的關(guān)系可由下面的線性方程組確定6.3.2線性分組碼的監(jiān)督方程和監(jiān)督矩陣8/14/202310推廣到一般情況：對(n,k)線性分組碼，每個(gè)碼字中的r令上式的系數(shù)矩陣為H，碼字矩陣（行陣列）為C6.3.2線性分組碼的監(jiān)督方程和監(jiān)督矩陣8/14/202311令上式的系數(shù)矩陣為H，碼字矩陣（行陣列）為C6.3.2(4)監(jiān)督矩陣特性對H各行實(shí)行初等變換，將后面r列化為單位子陣，于是得到下面矩陣，行變換后所得方程組與原方程組同解。監(jiān)督矩陣H的標(biāo)準(zhǔn)形式：后面r列是一單位子陣的監(jiān)督矩陣H。H陣的每一行都代表一個(gè)監(jiān)督方程，即H陣的r行代表了r個(gè)監(jiān)督方程，也表示由H所確定的碼字有r個(gè)監(jiān)督元。6.3.2線性分組碼的監(jiān)督方程和監(jiān)督矩陣8/14/202312(4)監(jiān)督矩陣特性6.3.2線性分組碼的監(jiān)督方程和監(jiān)H的標(biāo)準(zhǔn)形式還說明了相應(yīng)的監(jiān)督元是由哪些信息元決定的。例如(7,3)碼的H陣的第一行為(1011000)，說明此碼的第一個(gè)監(jiān)督元等于第一個(gè)和第三個(gè)信息元的模2和，依此類推。

6.3.2線性分組碼的監(jiān)督方程和監(jiān)督矩陣8/14/202313H的標(biāo)準(zhǔn)形式還說明了相應(yīng)的監(jiān)督元是由哪些信息元決定的。6.(1)線性碼的封閉性線性碼的封閉性：線性碼任意兩個(gè)碼字之和仍是一個(gè)碼字。定理：設(shè)二元線性分組碼CI(CI表示碼字集合)是由監(jiān)督矩陣H所定義的，若U和V為其中的任意兩個(gè)碼字，則U+V也是CI中的一個(gè)碼字。[證明]：由于U和V是碼CI中的兩個(gè)碼字，故有HUT=0T，HVT=0T那么H(U+V)T=H(UT+VT)=HUT+HVT=0T即U+V滿足監(jiān)督方程，所以U+V一定是碼字集合CI中的一個(gè)碼字。6.3.3線性分組碼的生成矩陣8/14/202314(1)線性碼的封閉性6.3.3線性分組碼的生成矩陣8/1(2)線性分組碼的生成矩陣的由來：在由(n,k)線性碼構(gòu)成的線性空間Vn的k維子空間中，一定存在k個(gè)線性獨(dú)立的碼字：g1,g2,…,gk,。碼字集合CI中，其它任何碼字C都可以用這k個(gè)碼字的某種線性組合來表示，即6.3.3線性分組碼的生成矩陣8/14/202315(2)線性分組碼的生成矩陣的由來：6.3.3線性分組碼G中每一行g(shù)i=(gi1,gi2,…,gin)都是一個(gè)碼字；對每一個(gè)信息碼元m來說，都可以通過矩陣G求得其對應(yīng)的碼字。生成矩陣的定義：由于矩陣G

生成了(n,k)線性碼中的任何一個(gè)碼字，稱矩陣G為(n,k)線性碼的生成矩陣。(n,k)線性碼的每一個(gè)碼字都是生成矩陣G的行的線性組合。6.3.3線性分組碼的生成矩陣8/14/202316G中每一行g(shù)i=(gi1,gi2,…標(biāo)準(zhǔn)生成矩陣：通過行初等變換，將G化為前k行和k列是單位子陣的標(biāo)準(zhǔn)形式6.3.3線性分組碼的生成矩陣8/14/202317標(biāo)準(zhǔn)生成矩陣：6.3.3線性分組碼的生成矩陣8/1/202線性系統(tǒng)分組碼：用標(biāo)準(zhǔn)生成矩陣Gk×n

編成的碼字，前面k位為信息數(shù)字，后面r=n－k位為校驗(yàn)字，這種信息數(shù)字在前校驗(yàn)數(shù)字在后的線性分組碼稱為線性系統(tǒng)分組碼。當(dāng)生成矩陣G確定之后，(n,k)線性碼也就完全被確定了，只要找到碼的生成矩陣，編碼問題也同樣被解決了。[參見下面有關(guān)（7，4）線性碼例子]6.3.3線性分組碼的生成矩陣8/14/202318線性系統(tǒng)分組碼：用標(biāo)準(zhǔn)生成矩陣Gk×n編成的碼字，前面(3)舉例：

已知一個(gè)(7,4)線性碼的生成矩陣G如下圖示，當(dāng)輸入信息碼元為1010時(shí)，試求輸出的碼字。6.3.3線性分組碼的生成矩陣由矩陣乘法規(guī)則可知：

C

=

m

G的結(jié)果，就是矩陣G中，與m中為“1”的元素相對應(yīng)的行按位模2加的結(jié)果。8/14/202319(3)舉例：6.3.3線性分組碼的生成矩陣由矩陣乘法規(guī)則6.3.3線性分組碼的生成矩陣練習(xí)：已知某線性分組碼的生成矩陣為試問：（1）n=?k=?,該碼組集合中的碼字有多少？（2）若信息碼元m分別是1100和1111時(shí),寫出其對應(yīng)的輸出碼字。8/14/2023206.3.3線性分組碼的生成矩陣練習(xí)：試問：8/1/20236.3.3線性分組碼的生成矩陣（1）n=7,k=4,共有16個(gè)碼字。8/14/2023216.3.3線性分組碼的生成矩陣（1）n=7,k(4)生成矩陣與監(jiān)督矩陣的關(guān)系由于生成矩陣G的每一行都是一個(gè)碼字，所以G的每行都滿足HCT=0T，則有HGT=0T

或GHT=0結(jié)論：線性系統(tǒng)碼的監(jiān)督矩陣H和生成矩陣G之間可以直接轉(zhuǎn)換。6.3.3線性分組碼的生成矩陣8/14/202322(4)生成矩陣與監(jiān)督矩陣的關(guān)系6.3.3線性分組碼的生舉例：1、已知線性系統(tǒng)碼的監(jiān)督矩陣，寫出其生成矩陣。6.3.3線性分組碼的生成矩陣8/14/202323舉例：6.3.3線性分組碼的生成矩陣8/1/2023236.3.3線性分組碼的生成矩陣舉例：2、已知線性系統(tǒng)碼的生成矩陣，寫出其監(jiān)督矩陣。8/14/2023246.3.3線性分組碼的生成矩陣舉例：8/1/2023246.3.3線性分組碼的生成矩陣練習(xí)題：

已知(7,3)線性分組碼,其碼字表示為:

C

=

(C6,C5,C4,C3,C2,C1,C0)C6,C5,C4為三位信息元，C3,C2,C1,C0為四位監(jiān)督元，可由下列方法產(chǎn)生:試求：（1）生成矩陣G和監(jiān)督矩陣H；（2）寫出其全部的碼字，碼字間的最小距離dmin是多少？8/14/2023256.3.3線性分組碼的生成矩陣練習(xí)題：試求：8/1碼字最小距離為:4根據(jù)產(chǎn)生監(jiān)督碼的方法，寫出監(jiān)督方程為：6.3.3線性分組碼的生成矩陣8/14/202326碼字最小距離為:4根據(jù)產(chǎn)生監(jiān)督碼的方法，寫出監(jiān)督方程為：1：已知(8,4)系統(tǒng)線性碼的監(jiān)督方程為課堂作業(yè)式中：C7,C6,C5,C4為信息碼元，

C3,C2,C1,C0為監(jiān)督碼元，求該碼的監(jiān)督矩陣和生成矩陣。8/14/2023271：已知(8,4)系統(tǒng)線性碼的監(jiān)督方程為課堂作業(yè)式中：2、某（n,k）系統(tǒng)線性分組碼的全部碼字如下：00000010111011011101求：（1）n=?,k=?（2）碼的生成矩陣G和監(jiān)督矩陣H。8/14/2023282、某（n,k）系統(tǒng)線性分組碼的全部碼字如下：8/1/2022、解：（1）已知M=2K

=4，故k=2；又知碼長n=5，那么r=n-k=3該碼是（5，2）線性碼。

（2）8/14/2023292、解：8/1/2023293、某（5，2）線性分組碼的H矩陣為：求：（1）該碼的G矩陣；（2）寫出該碼的全部碼字。8/14/2023303、某（5，2）線性分組碼的H矩陣為：8/1/202330(n,k)線性碼的編碼就是根據(jù)線性碼的監(jiān)督矩陣或生成矩陣將長為k的信息組變換成長為n(n>k)的碼字。舉例：用監(jiān)督矩陣構(gòu)造(7,3)線性分組碼的編碼電路：設(shè)碼字矢量為C=(C6C5C4C3C2C1C0)碼的監(jiān)督矩陣為6.3.4線性分組碼的編碼8/14/202331(n,k)線性碼的編碼就是根據(jù)線性碼的監(jiān)督矩陣或生成矩陣將根據(jù)方程組可直接畫出(7,3)碼的并行編碼電路和串行編碼電路，如圖。6.3.4線性分組碼的編碼8/14/202332根據(jù)方程組可直接畫出(7,3)碼的并行編碼電路和串行編碼舉例：一個(gè)(6,3)線性分組碼，其生成矩陣是

求：（1）將生成矩陣G轉(zhuǎn)化為標(biāo)準(zhǔn)生成矩陣GS后，計(jì)算系統(tǒng)碼碼集，列出映射關(guān)系。（2）寫出監(jiān)督矩陣HS，畫出編碼器原理圖。6.3.4線性分組碼的編碼8/14/202333舉例：一個(gè)(6,3)線性分組碼，其生成矩陣是6.3解：（1）根據(jù)矩陣的初等變換規(guī)則，對G作行運(yùn)算：原第1行+第3行作為第一行，原第1行+第2行+第3行作為第二行，原第1行+第2行作為第三行；得到系統(tǒng)化后的生成矩陣GS，于是系統(tǒng)碼C=m2[100111]+m1[010110]+m0[001011],得碼集和映射關(guān)系如下表。8/14/202334解：8/1/202334（2）根據(jù)標(biāo)準(zhǔn)監(jiān)督矩陣與生成矩陣之間的關(guān)系，可得：根據(jù)監(jiān)督矩陣可得到監(jiān)督方程組：8/14/202335（2）根據(jù)標(biāo)準(zhǔn)監(jiān)督矩陣與生成矩陣之間的關(guān)系，可得：8/1/2一、接收碼字的伴隨式和錯(cuò)誤檢測的概念：①用監(jiān)督矩陣編碼，也用監(jiān)督矩陣譯碼：當(dāng)接收到一個(gè)碼字R后，校驗(yàn)H

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

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

HT或ST=H

RT。③如何糾錯(cuò)？設(shè)發(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。6.6線性分組碼的譯碼8/14/202336一、接收碼字的伴隨式和錯(cuò)誤檢測的概念：6.6線性分組碼的譯④伴隨式與錯(cuò)誤圖樣之間的關(guān)系：伴隨式僅與錯(cuò)誤圖樣有關(guān)，而與發(fā)送的具體碼字無關(guān)，即伴隨式僅由錯(cuò)誤圖樣決定；伴隨式是錯(cuò)誤的判別式：若S=0，則判為沒有出錯(cuò)，接收字是一個(gè)碼字；若S≠0，則判為有錯(cuò)。不同的錯(cuò)誤圖樣具有不同的伴隨式，它們是一一對應(yīng)的。對二元碼，伴隨式是H陣中與錯(cuò)誤碼元對應(yīng)列之和；特別地，當(dāng)只發(fā)生一個(gè)錯(cuò)誤時(shí)，求出的伴隨式一定對應(yīng)于H陣中的某一列，那么，與接收碼字對應(yīng)的某一位就發(fā)生了錯(cuò)誤。也就是說：伴隨式的二進(jìn)制數(shù)值就是錯(cuò)誤位置號。6.6線性分組碼的譯碼8/14/202337④伴隨式與錯(cuò)誤圖樣之間的關(guān)系：6.6線性分組碼的譯碼8/⑤伴隨式譯碼舉例：某(7,3)線性系統(tǒng)碼設(shè)發(fā)送碼字C=1010011，接收碼字R＝1010011，R與C相同。6.6線性分組碼的譯碼8/14/202338⑤伴隨式譯碼舉例：6.6線性分組碼的譯碼8/1/20233若接收碼字中有一位錯(cuò)誤6.6線性分組碼的譯碼8/14/202339若接收碼字中有一位錯(cuò)誤6.6線性分組碼的譯碼8/1/202當(dāng)碼元錯(cuò)誤多于1個(gè)時(shí)6.6線性分組碼的譯碼8/14/202340當(dāng)碼元錯(cuò)誤多于1個(gè)時(shí)6.6線性分組碼的譯碼8/1/2023練習(xí)：已知(7,4)線性分組碼的生成矩陣如下。求：(1)該碼集的全部碼字16個(gè)碼字以及監(jiān)督矩陣H。(2)若接收碼字R分別為1101101和1001001時(shí)，根據(jù)伴隨式來判斷收的碼字有無錯(cuò)誤。若有錯(cuò)，寫出糾錯(cuò)后的碼字。6.6線性分組碼的譯碼8/14/202341練習(xí)：6.6線性分組碼的譯碼8/1/202341當(dāng)R=（1101101）時(shí)，說明：第7位發(fā)生錯(cuò)誤。E

=0000001糾正：C’=R+E=1101101+0000001=1101100S=0，接收碼字正確。8/14/202342當(dāng)R=（1101101）時(shí)，說明：第7位發(fā)生錯(cuò)誤。E=⑥伴隨式計(jì)算電路：伴隨式的計(jì)算可用電路來實(shí)現(xiàn)。以(7,3)碼為例：設(shè)接收字為R=(R6R5R4R3R2R1R0)，伴隨式為6.6線性分組碼的譯碼8/14/202343⑥伴隨式計(jì)算電路：6.6線性分組碼的譯碼8/1/2023根據(jù)上式可畫出伴隨式計(jì)算電路，如圖所示。6.6線性分組碼的譯碼8/14/202344根據(jù)上式可畫出伴隨式計(jì)算電路，如圖所示。6.6線性分組碼的二、結(jié)論：由于碼的可