線性分組碼(免費(fèi))

1、線性分組碼       8.3.1 基本概念    分組碼是一組固定長度的碼組，可表示為（n , k），通常它用于前向糾錯(cuò)。在分組碼中，監(jiān)督位被加到信息位之后，形成新的碼。在編碼時(shí)，k個(gè)信息位被編為n位碼組長度，而n-k個(gè)監(jiān)督位的作用就是實(shí)現(xiàn)檢錯(cuò)與糾錯(cuò)。當(dāng)分組碼的信息碼元與監(jiān)督碼元之間的關(guān)系為線性關(guān)系時(shí)，這種分組碼就稱為線性分組碼。    對(duì)于長度為n的二進(jìn)制線性分組碼，它有種可能的碼組，從種碼組中，可以選擇M=個(gè)碼組（k&l

2、t;n）組成一種碼。這樣，一個(gè)k比特信息的線性分組碼可以映射到一個(gè)長度為n碼組上，該碼組是從M=個(gè)碼組構(gòu)成的碼集中選出來的，這樣剩下的碼組就可以對(duì)這個(gè)分組碼進(jìn)行檢錯(cuò)或糾錯(cuò)。    線性分組碼是建立在代數(shù)群論基礎(chǔ)之上的，各許用碼的集合構(gòu)成了代數(shù)學(xué)中的群，它們的主要性質(zhì)如下：    （1）任意兩許用碼之和（對(duì)于二進(jìn)制碼這個(gè)和的含義是模二和）仍為一許用碼，也就是說，線性分組碼具有封閉性；    （2）碼組間的最小碼距等于非零碼的最小碼重。   

3、0;在8.2.1節(jié)中介紹的奇偶監(jiān)督碼，就是一種最簡單的線性分組碼，由于只有一位監(jiān)督位通常可以表示為（n,n-1），式（8-5）表示采用偶校驗(yàn)時(shí)的監(jiān)督關(guān)系。在接收端解碼時(shí)，實(shí)際上就是在計(jì)算：                                （8-6） 

4、60;   其中，   表示接收到的信息位，表示接收到的監(jiān)督位，若S0，就認(rèn)為無錯(cuò)；若S1就認(rèn)為有錯(cuò)。式（8-6）被稱為監(jiān)督關(guān)系式，S是校正子。由于校正子S的取值只有“0”和“1”兩種狀態(tài)，因此，它只能表示有錯(cuò)和無錯(cuò)這兩種信息，而不能指出錯(cuò)碼的位置。    設(shè)想如果監(jiān)督位增加一位，即變成兩位，則能增加一個(gè)類似于式（8-6）的監(jiān)督關(guān)系式，計(jì)算出兩個(gè)校正子和， 而共有4種組合：00，01，10，11，可以表示4種不同的信息。除了用00表示無錯(cuò)以外，其余3種狀態(tài)就可用于指示3種不同的誤碼圖樣

5、。    同理，由r個(gè)監(jiān)督方程式計(jì)算得到的校正子有r位，可以用來指示-1種誤碼圖樣。對(duì)于一位誤碼來說，就可以指示-1個(gè)誤碼位置。對(duì)于碼組長度為n、信息碼元為k位、監(jiān)督碼元為rn - k位的分組碼（常記作（n，k）碼），如果希望用r個(gè)監(jiān)督位構(gòu)造出r個(gè)監(jiān)督關(guān)系式來指示一位錯(cuò)碼的n種可能，則要求：                      &#

6、160;          （8-7)     下面通過一個(gè)例子來說明線性分組碼是如何構(gòu)造的。設(shè)分組碼（n , k）中k = 4，為了能夠糾正一位錯(cuò)誤，由式（8-7）可以看到，要求r  3，若取r = 3，則n = k+r = 7。因此，可以用表示這7個(gè)碼元，用、表示利用三個(gè)監(jiān)督方程，通過計(jì)算得到的校正子，并且假設(shè)、三位校正字碼組與誤碼位置的關(guān)系如表8-4（當(dāng)然，也可以規(guī)定成另

7、一種對(duì)應(yīng)關(guān)系，這并不影響討論的一般性）：         由表中規(guī)定可已看到，僅當(dāng)一錯(cuò)碼位置在時(shí)，校正子為1；否則為0。這就意味著四個(gè)碼元構(gòu)成偶數(shù)監(jiān)督關(guān)系：                    (8-8a）    同理，構(gòu)成偶數(shù)監(jiān)督關(guān)系：  

8、60;              （8-8b） 表8-4校正字與誤碼位置S1S2S3誤碼位置S1S2S3誤碼位置001010100011a0a1a2a3101110111000a4a5a6無錯(cuò)     以及構(gòu)成有數(shù)監(jiān)督關(guān)系：               

9、60;              （8-8c）     在發(fā)送端編碼時(shí)是信息碼元，它們的值取決于輸入信號(hào)，因此是隨機(jī)的。是監(jiān)督碼元，它們的取值由監(jiān)督關(guān)系來確定，即監(jiān)督位應(yīng)使式（8-8）的三個(gè)表達(dá)式中的、和的值為零（表示編成的碼組中應(yīng)無錯(cuò)碼），這樣式（8-8）的三個(gè)表達(dá)式可以表示成下面的方程組形式：         &#

10、160;                          （8-9）     由上式經(jīng)移項(xiàng)運(yùn)算，接出監(jiān)督位               &

11、#160;                     （8-10）     根據(jù)上面兩個(gè)線性關(guān)系，可以得到16個(gè)許用碼組如表8-5所示： 表8-5許用碼組信息位監(jiān)督位信息位監(jiān)督位信息位監(jiān)督位信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0a6a5a4a3a2a1a0a6a5a4a3a2a1a0000000010

12、0100011000011101110010001010100011111010101100010001001101010111111000100011100110111001111001010100111     接收端收到每個(gè)碼組后，計(jì)算出、和，如不全為0，則可按表8-4確定誤碼的位置，然后予以糾正。例如，接收碼組為0000011，可算出011，由表8-4可知在位置上有一誤碼。    不難看出，上述（7，4）碼的最小碼距，因此，它能糾正一個(gè)誤碼或檢測兩個(gè)誤碼。如超出糾錯(cuò)能力，則反而會(huì)因“亂糾”而增加新

13、的誤碼。      8.3.2 監(jiān)督矩陣H和生成矩陣G    式（8-9）所述（7，4）碼的三個(gè)監(jiān)督方程式可以重新改寫為如下形式：                     （8-11）     對(duì)于式（8-11）可以用矩陣形式來表示：

14、60;             （8-12）     上式可以記作：或，其中                     （8-13a）      

15、60;                  （8-13b）                              &#

16、160;   （8-13c）     通常H稱為監(jiān)督矩陣，A稱為信道編碼得到的碼字。在這個(gè)例子中H為r×n階矩陣，P為r×k階矩陣，Ir為r×r階單位矩陣，具有這種特性的H矩陣稱為典型監(jiān)督矩陣，這是一種較為簡單的信道編譯碼方式。典型形式的監(jiān)督矩陣各行是線性無關(guān)的，非典型形式的監(jiān)督矩陣可以經(jīng)過行或列的運(yùn)算化為典型形式。    對(duì)于式（8-10）也可以用矩陣形式來表示：       

17、;或者              （8-14）     比較式（8-13a）和式（8-14）可以看到，如果在Q矩陣的左邊在加上一個(gè)k×k的單位矩陣，就形成了一個(gè)新矩陣G：                   &

18、#160;   （8-15）     這里G稱為生成矩陣，利用它可以產(chǎn)生整個(gè)碼組                          （8-16）     由式（8-15）表示的生成矩陣形式稱為典型生成矩陣，利用

19、式（8-16）產(chǎn)生的分組碼必為系統(tǒng)碼，也就是信息碼元保持不變，監(jiān)督碼元附加在其后。      8.3.3 校驗(yàn)子S    在發(fā)送端信息碼元M利用式（8-16），實(shí)現(xiàn)信道編碼，產(chǎn)生線性分組碼A；在傳輸過程中有可能出現(xiàn)誤碼，設(shè)接收到的碼組為B。則收發(fā)碼組之差為：               （8-17）    &

20、#160;這里，表示i位有錯(cuò)，表示i位無錯(cuò)?；谶@樣的原則接收端利用接收到的碼組B計(jì)算校正子：                   （8-18）     因此，校正子僅與E有關(guān)，即錯(cuò)誤圖樣與校正子之間有確定的關(guān)系。    對(duì)于上述（7，4）碼，校正子S與錯(cuò)誤圖樣的對(duì)應(yīng)關(guān)系可由式（8-18）求得，其計(jì)算結(jié)果見表8-6所示

21、。在接收端的譯碼器中有專門的校正子計(jì)算電路，從而實(shí)現(xiàn)檢錯(cuò)和糾錯(cuò)。 表8-6（7，4）碼校正子與錯(cuò)誤圖樣的對(duì)應(yīng)關(guān)系序號(hào)錯(cuò)誤碼位ESe6 e5 e4 e3 e2 e1 e0S3 S2 S101234567/b0b1b2b3b4b5b60  0  0  0  0  0  00  0  0  0  0 &#

22、160;0  10  0  0  0  0  1  00  0  0  0  1  0  00  0  0  1  0  0  00  0  1  0  0  0  00  1  0  0  0  0  01  0  0  0  0  0  00  0  00