通信原理II第4次課課件

1、10.3 線性分組碼10.3.1 線性分組碼的基本概念1.線性分組碼的概念(1) 分組碼線性分組碼中的分組是對(duì)信息序列的處理方法而言，即編碼時(shí)將信息序列每位分為一組，編碼器對(duì)每組的位信息按一定的規(guī)律產(chǎn)生個(gè)監(jiān)督碼，輸出長度為的碼組（碼字）。對(duì)于分組碼，每一碼組的(即)個(gè)監(jiān)督碼僅與本碼組的個(gè)信息碼有關(guān)，與其他碼組的信息無關(guān)。(2) 線性碼 線性分組碼中的線性是指碼組中監(jiān)督碼與信息碼的關(guān)系，線性碼碼組中任一碼元都是信息碼元的線性組合。 2.線性分組碼的性質(zhì)下面通過舉例來認(rèn)識(shí)和了解線性分組碼及其性質(zhì)。例10.3.1 (7,4)二進(jìn)制線性分組碼的輸入信息組（又稱信息段）是m,編碼輸出A，已知碼組到信息間

2、的映射關(guān)系為求輸出碼組集合（這里，“+”指模二加）。 解：將由線性方程組描述的輸入輸出碼元之間的線性變換關(guān)系改寫成矩陣形式：A （模2加）= mG 碼長的碼組有種組合，而4位的信息組只有種組合，對(duì)應(yīng)16個(gè)碼組?？梢姡?7,4)線性分組碼僅有16個(gè)許用碼組。分別令信息組為（0000），（0001），（1111），代入上面的矩陣算式，不難算得各信息組對(duì)應(yīng)的碼組，列于表10.3.1 。 表10.3.1 (7,4)線性分組碼碼組集合信息位監(jiān)督位信息位監(jiān)督位0000000100100011010001010110011100001110111011010101100010001001101010111

3、100110111101111111100010001001010100111表10.3.1 反映出線性分組碼所具備的基本性質(zhì)： (1) 一個(gè)線性分組碼共有個(gè)（許用）碼組；(2) 對(duì)加法滿足封閉性，即線性分組碼中任意兩個(gè)碼組之和（模2加）仍是分組碼中的一個(gè)碼組；(3) 全零碼是線性分組碼中的一個(gè)碼組；(4) 線性分組碼各碼組之間的最小碼距，等于除全零碼外的碼組的最小重量。10.3.2 生成矩陣及其特性在例10.3.1的編碼過程中，核心的因素是矩陣G，它決定了變換規(guī)則，也決定了碼組集合和性質(zhì)。不失一般性，令是一組（個(gè)）二進(jìn)制信息碼元，它可看成是一個(gè)的矩陣m，或 m。編碼后，輸出碼組長度增大到,通

4、常將碼組寫成通式A。則線性分組碼的編碼運(yùn)算通常用矩陣形式表示為：A = mG （10.3.1）式中，G稱為該碼的生成矩陣，是（行列）階矩陣： G （10.3.2）其中，系數(shù)，；表示第個(gè)信息元對(duì)第個(gè)碼元的影響。 如例10.3.1中的生成矩陣G是階矩陣；G中系數(shù)為1表示信息元對(duì)碼元會(huì)產(chǎn)生影響，系數(shù)為0表示無影響。如G中的第5列是，表示對(duì)產(chǎn)生影響，而對(duì)無影響。歸納起來，生成矩陣G具有以下特性：(1) 線性分組碼的每個(gè)碼組都是生成矩陣G各行矢量的線性組合。因?yàn)榘捶謮K矩陣運(yùn)算法則將式（10.3.2）展開，可得 A （10.3.3）或 （10.3.4）在例10.3.1中，有 A(2) 生成矩陣G的各行本身

5、就是一個(gè)碼組，且它們是線性無關(guān)的。由特性(1)和(2)得到的啟示是：如果已有個(gè)線性無關(guān)的碼組，則它們的線性組合就能產(chǎn)生個(gè)碼組所構(gòu)成的集合。(3) 如果生成矩陣G具有的形式，其中為階單位方陣，Q是階矩陣，則稱G為典型生成矩陣。由典型生成矩陣得出的碼組稱為系統(tǒng)碼。在本章，系統(tǒng)碼的碼組中前個(gè)是信息位，后是監(jiān)督位，如圖10.1.3所示。如例10.3.1中，生成矩陣能分解成G (4) 非典型生成矩陣可以通過線性代數(shù)中的任何一種初等行變換和列交換，得到典型生成矩陣。10.3.3 監(jiān)督矩陣及其特性若將例10.3.1中的監(jiān)督位線性方程組表示成 （10.3.5）即 （10.3.6）寫成矩陣形式 （模2加） （1

6、0.3.7） 令則有 或 （10.3.8）我們將H稱為監(jiān)督矩陣（又稱校驗(yàn)矩陣）。推廣到維一般情況，H是一個(gè)階矩陣。監(jiān)督矩陣H的特性是：(1) 線性分組碼的任意碼組A正交于監(jiān)督矩陣H的任意一個(gè)行矢量，即 （10.3.9）(2) 監(jiān)督矩陣H的各行是線性無關(guān)的。(3) 若H，其中是階矩陣，為階單位方陣，則稱H矩陣為典型陣。(4)監(jiān)督矩陣H與生成矩陣G的關(guān)系對(duì)任何線性分組碼（系統(tǒng)碼或非系統(tǒng)碼），總是存在下列關(guān)系： 或 （10.3.10） 即監(jiān)督矩陣H的行與生成矩陣G的行正交。只有系統(tǒng)碼才有關(guān)系： 或 （10.3.11） 這時(shí)，生成矩陣G與監(jiān)督矩陣H可以互相轉(zhuǎn)換。10.3.4編碼和譯碼1. 系統(tǒng)碼編碼（

7、略）2. 譯碼線性分組碼的譯碼是以碼組為單位、通過檢測(cè)收發(fā)碼組之間的差異來發(fā)現(xiàn)或糾正錯(cuò)誤的。(1) 錯(cuò)誤圖樣設(shè)編碼器輸出碼組A，接收端的接收碼組B，則由信道干擾引起的收、發(fā)碼組之間的差異可表示成B = A + E （10.3.12）式中，E，當(dāng)時(shí)，表示該位接收碼元無錯(cuò)；若，則表示該位接收碼元有錯(cuò)。我們把這個(gè)錯(cuò)碼矢量稱為錯(cuò)誤圖樣。錯(cuò)誤圖樣表征了收發(fā)碼組之間的差異，因此，雖然事先并不知道發(fā)送碼組A，但是，如果譯碼器能推測(cè)出錯(cuò)誤圖樣是，那就可以給出譯碼結(jié)果為 （10.3.13）(2) 校正子與譯碼為找出，定義校正子（又稱伴隨式）S為 （10.3.14）將式（10.3.13）代入式（10.3.14）中

8、可得 （10.3.15）利用式（10.3.9）所示碼組與監(jiān)督矩陣的正交性，所以 （10.3.16）上式表明，校正子S的值只取決于錯(cuò)誤圖樣E，而與發(fā)送什么碼組A無關(guān)。如果想要推測(cè)出錯(cuò)誤圖樣是什么，可以從校正子入手，并且，當(dāng)給定S時(shí)，可能的錯(cuò)誤圖樣一定是方程（10.3.16）的解。(3) 譯碼過程譯碼過程可描述為： 利用式，計(jì)算校正子。如果，則表明接收碼組與監(jiān)督矩陣正交，即，可斷定接收碼組就是發(fā)送碼組；如果，轉(zhuǎn)入步驟。 由校正子S求錯(cuò)誤圖樣E若S與E之間一一對(duì)應(yīng)，則可能的錯(cuò)誤圖樣一定是方程的解。此時(shí)，校正子的組合數(shù)目不少于可糾正錯(cuò)誤圖樣的數(shù)目（參見例10.3.2）；若方程有多解，則可以運(yùn)用概率譯碼

9、的處理方法選擇錯(cuò)誤圖樣的估值。 利用關(guān)系式，由錯(cuò)誤圖樣估值求發(fā)送碼組估值。上述譯碼過程的框圖如圖10.3.2所示。圖10.3.1 譯碼過程示意圖(4) 概率譯碼注意，方程組（10.3.16）中有個(gè)未知數(shù)，卻只有個(gè)方程，可知方程的解E是不唯一。式（10.3.16）的解一共有個(gè)，記其為，由此帶來的后果是，由確定S后，可能的譯碼結(jié)果也是個(gè)，它們是，。那么究竟取哪一個(gè)作為錯(cuò)誤圖樣E的解呢？這里，介紹一種叫做概率譯碼的處理方法，它是把所有個(gè)解的重量（錯(cuò)誤圖樣E中1的個(gè)數(shù)）做比較，選擇最輕者作為E的估值。這種算法的理論根據(jù)是：若二進(jìn)制對(duì)稱信道（BSC）的差錯(cuò)概率是，則長度為的碼中錯(cuò)1位（對(duì)應(yīng)于E中有一個(gè)1

10、或E的重量為1）的概率是，錯(cuò)2位的概率是以此類推。由于，必有 （10.3.17） 所以，在E的個(gè)解中取重量最小的E時(shí)，譯碼正確的概率最大。由于E=B+A即收、發(fā)碼之間的漢明距離，E重量最小，就是B和A的距離最小，所以概率譯碼實(shí)際上體現(xiàn)了最小距離譯碼法則。10.3.5 漢明碼漢明碼是一類能糾正單個(gè)隨機(jī)錯(cuò)誤的線性分組碼，其最小碼距。漢明碼具有如下特性：(1) 二進(jìn)制漢明碼應(yīng)滿足條件： （10.3.18）式（10.3.18）的左邊為校正子的組合數(shù)目，右邊是無錯(cuò)傳輸（毫無疑問僅一種情形）與可糾正錯(cuò)誤圖樣數(shù)目（因漢明碼糾錯(cuò)能力，所以）之和。因此，漢明碼的校正子和可糾正錯(cuò)誤圖樣是一一對(duì)應(yīng)的，即式中的S與E

11、之間一一對(duì)應(yīng)。(2) 令，則利用關(guān)系式（10.3.18），漢明碼碼長和信息位可表示成：，于是當(dāng)時(shí)，分別有（7，4），（15，11），（31，26），（63，57），（127，120），（255，247），是漢明碼。(3) 漢明碼的編碼效率，當(dāng)碼長很大時(shí)，接近于1，所以漢明碼是一類高效率的糾錯(cuò)碼。(4) 個(gè)單個(gè)錯(cuò)誤的校正子就是監(jiān)督矩陣H矩陣的每一列。H矩陣所具有的這種特殊性質(zhì)，使得能以相對(duì)簡單的方法來構(gòu)造漢明碼。例10.3.2 已知(7,4)漢明碼的監(jiān)督矩陣為H=1) 試求校正子的組合數(shù)目、可糾正錯(cuò)誤圖樣數(shù)目。2) 驗(yàn)證該(7,4)碼符合由校正子來指示一位錯(cuò)碼位置的要求，并列出校正子與可糾正錯(cuò)誤

12、圖樣的對(duì)應(yīng)關(guān)系。3) 若接收碼組是(1100100)，寫出校正子，同時(shí)指出發(fā)生一位錯(cuò)碼的位置。解：1) ，。校正子的組合數(shù)目是，可糾正錯(cuò)誤圖樣數(shù)目為。2) 一般來說，如果希望用維校正子矢量來指示一位錯(cuò)碼的種可能位置，則要求：或?qū)τ诖a長的編碼，為了糾正一位錯(cuò)碼，則；或者若取值為3，則，顯然本例符合由校正子來指示一位錯(cuò)碼位置的要求。利用關(guān)系式，不難求得校正子與可糾正錯(cuò)誤圖樣的對(duì)應(yīng)關(guān)系，列表如下：校正子S可糾正錯(cuò)誤圖樣E111110101011100010001 1000000 0100000 0010000 0001000 0000100 0000010 0000001不難看出，將除全零外的其余校正子組合排列起來就是監(jiān)督矩陣。且排列順序不同，所得矩陣也就不同，說明H矩陣不是唯一的，也不一定是