信息論與編碼技術(shù)：第六章 信道編碼

1、1 第六章 信 道 編 碼 6.1 信道編碼的概念 6.2 線性分組碼 6.3 循環(huán)碼 6.4 卷積碼2 信源的輸出經(jīng)過信源編碼后可用較少的符號來表達信源消息，這些符號剩余度很小，效率很高，因此提高了通信系統(tǒng)信息傳輸?shù)挠行?，但對噪聲干擾的抵抗能力很弱。 信息傳輸要通過各種物理信道，由于干擾、設(shè)備故障等影響，被傳送的信源符號可能會發(fā)生失真，使有用信息遭受損壞，對接收的信號造成誤判。 在接收端錯誤地確定所接收的信號叫做差錯。 為了提高信息傳輸?shù)臏蚀_性，使其具有較好的抵抗信道中噪聲干擾的能力，在通信系統(tǒng)中需要采用專門的檢錯、糾錯方法，即差錯控制。 差錯控制的任務(wù)是發(fā)現(xiàn)所產(chǎn)生的錯誤，并指出發(fā)生錯誤的

2、信號或者校正錯誤。 采用可靠、有效的信道編碼方法可以實現(xiàn)差錯控制。 信道編碼器要對信源編碼輸出的符號進行變換，使其盡量少受噪聲干擾的影響，減少傳輸差錯，提高通信可靠性。 本章要討論的問題是在信源編碼符號受到噪聲干擾的影響后，如何從接收到的信號中恢復出原送入信道的信號、確定差錯概率是多少等。本章重點內(nèi)容： 信道編碼的基本概念和分類，在此基礎(chǔ)上再討論線性分組碼、循環(huán)碼與卷積碼的信道編碼、譯碼方法。 36.1 信道編碼的概念 進行信道編碼是為了提高信號傳輸?shù)目煽啃?，改善通信系統(tǒng)的傳輸質(zhì)量。 研究信道編碼的目標是尋找具體構(gòu)造編碼的理論與方法。 香農(nóng)第二定理已從理論上指出，只要實際信息傳輸率Rt)。48

3、 這里說的“同時”是指在譯碼過程中，若錯誤個數(shù)t，則能糾正；若錯誤個數(shù)t，但e (et)，則能檢測這些錯誤，但不能糾正，或者說能檢測e+t個錯誤，其中t個錯誤可以糾正。其直觀的關(guān)系如下圖所示。 49 圖6.1.9(c)中，粗線球面(圓)是糾正t個錯誤的球面，細線球面(圓)代表檢出e個錯誤的球面。當接收碼字 中不包含錯誤或錯誤t， 將落在粗線球內(nèi)或球上，因而可把 糾正為原發(fā)送的碼字，當接收碼字 包含t個而e個錯誤時， 不會落在任何碼字的糾錯球內(nèi)，但此時代表糾錯范圍的粗線球面與另一碼字的代表檢錯范圍的細線球面沒有相交或相切，于是可將糾錯和檢錯區(qū)分開來。 例如，當碼的最小碼距為2時，不能糾錯(只能檢

4、測出1位錯)。 當碼的最小碼距為3或4時，可以糾正所有1位錯。 當碼的最小碼距為5時，可以糾正所有2位錯。 當碼的最小碼距為n時，可以糾正所有 位錯。 50 定理6.1.1說明，碼的最小距離dmin越大，碼的糾(檢)錯的能力越強。但是，隨著冗余碼元的增多，信息傳輸速率會降低得越多。 通常用 來表示碼字中信息碼元所占的比例，稱為編碼效率，簡稱碼率，它是衡量碼性能的又一個重要參數(shù)。碼率越高，信息傳輸率就越高，但此時糾錯能力要降低，若=1時就沒有糾錯能力了?？梢?，碼率與糾錯能力之間是有矛盾的。 51對糾錯編碼的基本要求： 糾錯和檢錯能力盡量強，編碼效率盡量高，碼長盡量短，編碼規(guī)律盡量簡單。 在實際系

5、統(tǒng)中，根據(jù)具體指標要求，保證有一定的糾錯能力和編碼效率，且易于實現(xiàn)和節(jié)省費用。 大多數(shù)信道編碼的性能都很難同時兼顧上述要求，因此，目前信道編碼的主要目的是以可靠性為主，即在保證抗干擾能力盡量強的基礎(chǔ)上，適當兼顧有效性，尋求和構(gòu)造最小距離dmin比較大的碼。526.2 線性分組碼 線性分組碼是糾錯碼中非常重要的一類碼，雖然對于同樣碼長的非線性碼來說線性碼可用碼字較少，但由于線性碼的編碼和譯碼容易實現(xiàn)，而且是討論其他各類碼的基礎(chǔ)，至今仍是廣泛應(yīng)用的一類碼。6.2.1 線性分組碼的基本概念 通常在信源編碼器之后加上一級信道編碼器(又稱糾錯編碼器)，它對信源編碼器輸出的D進制序列進行分組，并對每一分組

6、進行變換，變換后的碼組具有抗信道干擾的能力。若這種變換是線性變換，則稱變換后的碼組為線性分組碼；若變換為非線性變換，則稱變換后的碼組為非線性分組碼。實際中常用線性分組碼。 53定義6.2.1 對信源編碼器輸出的D進制序列進行分組，設(shè)分組長度為k，相應(yīng)的分組信息序列表示為：其中每個碼元mi(1ik)都是D進制的，顯然這樣的序列共有Dk個。信道編碼(糾錯編碼)的目的是將各信息序列 進行變換，使其成為以下形式： 其中，nk，ci(1in)為D進制數(shù)，顯然這樣的碼字共有Dn個。我們稱全體碼字 的集合為D元分組碼。若由 到 之間的變換為線性變換，則稱全體碼字 的集合為D元線性分組碼，常用(n,k)線性分

7、組碼C來表示全體碼字 的集合。 54 線性分組碼中的線性是指編碼規(guī)律即碼元之間的約束關(guān)系是線性的，而分組則是對編碼方法而言，即編碼是將每k位信息分為一組獨立處理，編成長度為n位(nk)的D進制碼組。 若信道中傳輸?shù)氖嵌蛄?，則(n,k)線性分組碼的編碼是在信道輸入端的2n個n長的二元序列中找一組2k個碼字，使碼字的r=n-k個檢驗元與其k個信息元之間滿足一定的線性關(guān)系，并使碼書中碼字間最小距離為最大。55例6.2.1 設(shè)將信源編碼器輸出的二進制序列進行分組，分組長度k=1，相應(yīng)的碼字表示為這里m1是二進制的，即D=2。這樣的碼字共有兩個，即“1”和“0”?，F(xiàn)將 進行變換，變換規(guī)則為： 因此，

8、形成的糾錯碼具有以下形式 由于m1只取0或l，所以 的全體碼字只有兩個：長為n 的全0或全l序列，即經(jīng)過上述變換，得到了(n,1)重復碼。 56例6.2.2 設(shè)信源編碼器輸出的信息序列為 ，其中mi(1ik)是二進制數(shù)。信道編碼器輸出的碼字為 ，其中ci(1in, nk)也是二進制數(shù)。若從 到 的變換規(guī)則為：由于從 到 的變換是一種線性變換，所以全體 的集合構(gòu)成了一種(n,n-1)線性分組碼。 57 由本例可以看出，變換后碼字集合中每一個碼字的所有碼元之和為問題：這樣的和意味著什么？ 因為假設(shè)了碼為二進制碼，上述碼元的和是模2和。因此，變換后將每一個碼字的碼元全部加起來，它的模2和為0，即每一

9、個碼字中1的個數(shù)為偶數(shù)個，所以這種碼為偶校驗碼。 58例6.2.3 (7,3)線性分組碼，按以下的規(guī)則(校驗方程)可得到四個校驗元c4,c3,c2,c1。 式中m3,m2,m1是三個信息碼元，方程中的加運算均為模2加。由此可得到(7,3)分組碼的8個碼字。8個信源序列與8個碼字的對應(yīng)關(guān)系列于表6.2.1中。由校驗方程看到，信息碼元與校驗碼元滿足線性關(guān)系，因此該(7,3)碼是線性碼。 59表6.2.1 例6.2.3編出的(7,3)線性碼的碼字與信息碼元的對應(yīng)關(guān)系 60信息碼元碼 字m3 m2 m1c7 c6 c5 c4 c3 c2 c10 0 00 0 0 0 0 0 00 0 10 0 1 1

10、 1 0 10 1 00 1 0 0 1 1 10 1 10 1 1 1 0 1 01 0 01 0 0 1 1 1 01 0 11 0 1 0 0 1 11 1 01 1 0 1 0 0 11 1 11 1 1 0 1 0 06.2.2 生成矩陣和一致校驗矩陣 從矢量空間的角度來看，形形色色的編碼方法實質(zhì)上是采用了不同的基底選擇方法及矢量映射規(guī)則而形成的。基底的選擇與映射規(guī)則均可用矩陣來表示，因此在線性分組碼的討論中就有了生成矩陣和一致校驗矩陣的概念。1. 生成矩陣 在討論生成矩陣之前，我們再看例6.2.3的(7,3)線性分組碼。該碼所滿足的校驗方程可寫成矩陣形式：6162 上式可表為 。

11、其中G稱為線性分組碼的生成矩陣。 分析 可知：二進制碼取值于0,1,7位二進制數(shù)有27=128種不同的排列，而3個信息碼元構(gòu)成的信息位只有8種排列，這8種排列與例6.2.3(7,3)分組碼的8個碼字一一對應(yīng)?？梢姡纠€性分組碼的碼書是選取了128種排列之中的8種。當分別令m3,m2,m1為(000),(001),(111)時，代入 ，即得表6.2.1所示的各信息碼元組對應(yīng)的碼字。 在例6.2.3(7,3)分組碼的編碼過程中，核心因素是生成矩陣G, 它決定了校驗元的生成規(guī)則與最終的碼書。該生成矩陣G由3個行矢量組成，這3個行矢量本身就是碼書中的3個碼字，可以證明這3個行矢量是線性無關(guān)的，即可以

12、選擇碼書中的3個線性無關(guān)的碼字來構(gòu)成生成矩陣G的行矢量。63 上例的啟示： 碼書其實是一個子空間，只要找到一組合適的基底，它們的線性組合就能產(chǎn)生整個碼書C。 由線性代數(shù)可知，基底不是唯一的。在基底的線性組合產(chǎn)生的矢量中，任意選出k個矢量，只要它們滿足線性無關(guān)的條件，都可以作為由k位信息碼元生成(n,k)線性分組碼的生成矩陣。反映到矩陣運算上，只要保證矩陣的秩是k，就可以通過行初等變換改變生成矩陣的形式而不改變碼書。 因此，任何生成矩陣都可通過運算轉(zhuǎn)化成如下的系統(tǒng)形式定義6.2.2 若信息組以不變的形式在碼字的任意k位中出現(xiàn)，則該碼稱為系統(tǒng)碼。否則，稱為非系統(tǒng)碼。 目前常用的有兩種形式的系統(tǒng)碼：

13、 一種是把信息組排在碼字(cn,c2,c1)的最左邊k位cn,cn-k+1, 生成矩陣的系統(tǒng)形式屬于這種形式。除非特別說明，后面提到的系統(tǒng)碼均指這種形式。 另一種是把信息組安置在碼字(cn,c2,c1)的最右邊k位ck,c2,c1。 64 能夠產(chǎn)生系統(tǒng)碼的生成矩陣為典型矩陣(或稱標準陣)。 典型矩陣的最大優(yōu)勢是便于檢查生成矩陣G的各行是否是線性無關(guān)。 如果G不具有標準型，雖能產(chǎn)生線性碼，但碼字不具備系統(tǒng)碼的結(jié)構(gòu)，因而存在難以區(qū)分碼字中信息碼元和監(jiān)督碼元的缺點。 由于系統(tǒng)碼的編碼與譯碼較非系統(tǒng)碼簡單，而且對分組碼來說，系統(tǒng)碼與非系統(tǒng)碼的抗干擾能力是等價的，故若無特別聲明，僅討論系統(tǒng)碼。 如果生成

14、矩陣G為非標準型的，可經(jīng)過行初等變換變成標準型。652 一致校驗矩陣 從前面的討論可知，編碼問題就是在給定的dmin下如何從已知的k個信息碼元求得r=n-k個校驗碼元。 例6.2.3(7,3)分組線性碼的4個檢驗碼元可由式(6.2.1)中的后4個線性方程組決定。為進一步說明信息碼元與校驗碼元之間的關(guān)系，將式 中后4個線性方程進行變換 66 其矩陣形式表示為 一般可寫成： 上式表明， 中各碼元是滿足由矩陣H所確定的r個線性方程的解，故 是碼書C中的一個碼字，由 的全體就構(gòu)成了碼書C。 反之，若某碼元序列滿足由H所確定的r個線性方程，則該碼元序列一定是碼書C中的一個碼字。 67 因此， H一定，便

15、可由信息碼元求出校驗碼元，編碼問題就迎刃而解；或者說，要解決編碼問題，只要找到H即可。由于(n,k)碼的所有碼字均按H所確定的規(guī)則求出，故稱H為其一致校驗矩陣。 一般(n,k)線性分組碼有r=n-k個校驗碼元，故必須有r個獨立的線性方程。所以(n,k)線性分組碼的一致檢驗矩陣H由r行和n列組成，可表示為 由H矩陣可建立r個線性方程68 綜上所述，可將H矩陣的特點歸納如下： H矩陣的每一行代表一個線性方程中的有關(guān)系數(shù)，它對 應(yīng)求一 個校驗碼元的線性方程。 H矩陣每一列代表此碼元與哪幾個校驗方程有關(guān)。 由該H矩陣得到的(n,k)分組碼的每一碼字 都必須滿足 由H矩陣的行所確定的線性方程，即 (*)

16、或(*)。 (n,k)碼需有r個校驗碼元，故需有r個獨立的線性方程。 因此，H矩陣必須有r 行，且各行之間線性無關(guān)，即H矩 陣的秩為r。69 由于生成矩陣G中的每一行及其線性組合都是(n,k)碼中 的一個碼字，故有 或 。 這說明H矩陣的每一行與由G矩陣行生成的分組碼中每 一個碼字內(nèi)積均為0，因此G和H彼此正交。 由例6.2.3不難看出，(7,3)碼的H矩陣右邊為一個4階單位矩陣。通常，系統(tǒng)型(n,k)線性分組碼的H矩陣右邊r列組成一個單位矩陣Ir，故有 Hrn=QrkIr 稱這種形式的H矩陣為典型矩陣(或標準矩陣)，同樣，采用典型矩陣形式的H矩陣更易于檢查各行是否線性無關(guān)。70 由 易得：

17、由此關(guān)系可知 這說明，P的第一行就是Q的第一列，P的第二行就是Q 的第二列，因此，H矩陣一旦確定，則G矩陣也就確定，反之亦然(?)。 7172因此得 因而線性系統(tǒng)碼的監(jiān)督矩陣H和生成矩陣G之間可以相互直接轉(zhuǎn)換。 如已知(7,4)線性系統(tǒng)碼的監(jiān)督矩陣 關(guān)于線性分組碼的兩個定理：定理一 設(shè)兩元線性分組碼C由監(jiān)督矩陣H所定義，若 為其中任意兩個碼字，則 也一定是C中的一個碼字。證 是C中兩個碼字，故有即 滿足監(jiān)督(校驗)方程，所以 必是一個碼字。 該定理表明，線性分組碼的任兩個碼字之和仍是一個碼字，這一性質(zhì)稱為線性分組碼的封閉性。 73定理二 一個(n,k)線性分組碼中非零碼字的最小重量等于該碼的最

18、小距離dmin。 證 設(shè)有任意兩個碼字 。根據(jù)線性分組碼的封閉性性知 ，而 74 由例6.2.3(7,3)線性碼的8個碼字可見，除全零碼字外，其余7個碼字最小重量Wmin=4，所以該(7,3)線性碼的最小距離dmin=4 。 75信息碼元碼 字m3 m2 m1c7 c6 c5 c4 c3 c2 c10 0 00 0 0 0 0 0 00 0 10 0 1 1 1 0 10 1 00 1 0 0 1 1 10 1 10 1 1 1 0 1 01 0 01 0 0 1 1 1 01 0 11 0 1 0 0 1 11 1 01 1 0 1 0 0 11 1 11 1 1 0 1 0 03 線性分組

19、碼的編碼 (n,k)線性分組碼的編碼就是根據(jù)一致校驗矩陣H或生成矩陣G將長度為k的信息碼元變換成長度為n的碼字。 這里以(7,3)線性分組碼為例來說明構(gòu)造編碼電路的方法。例6.2.4 設(shè)二元碼字為 ，碼的一致校驗矩陣H為由 ，即76 (a) 并行編碼電路 (b) 串行編碼電路圖6.2.1 線性分組碼編碼電路原理圖 77 按照該線性方程組，可直接畫出(7,3)線性分組碼的并行編碼電路和串行編碼電路，如圖6.2.1所示。78例6.25 考慮一個(7,4)線性分組碼，其生成矩陣為(1) 對于信息序列 ，編出的碼字是什么？(2) 畫出該(7,4)分組線性碼編碼器的原理圖。(3) 若接收到一個碼元序列

20、，檢驗它是否為碼字。解 設(shè)輸入信息組 , 編碼后的碼字屬于碼書C。(1) 由 可知，將 和G代入，可得對應(yīng)碼字為(1011000)。由于本例是系統(tǒng)碼， 前4位不必計算，后面3個校驗位可以根據(jù)生成矩陣G中的分塊矩陣P列出線性方程組：79 將m4=1, m3=0, m2=1, m1=1代入方程組，得c3=0, c2=0,c1=0，因此得碼字 。(2) 按照校驗位生成的線性方程組，可直接畫出該(7,4)分組線性碼串行編碼器原理圖：80 編碼器的工作構(gòu)過程為：首先將信息位m4，m3，m2，m1依次順序輸入。編碼后，開關(guān)在輸出前4位時向上撥，將m4 ，m3，m2，m1依次順序輸出；輸出后3位時，開關(guān)向下

21、撥，將c3, c2，c1，順序移位輸出。(3) 根據(jù) ，如果接收到的碼元序列屬于碼集C，則必然可由接收到的碼元序列的前4位生成后3位。由于接收到的碼元序列 ，將m4 =1，m3=0，m2=0，m1=1代入 ，得c3=m4+m3+m2=1，c2=m3+m2+m1=1，c1= m4+m3+m1=0，因此正確的碼字應(yīng)為 ，所以接收到的碼元序列 不是碼字。4 對偶碼和縮短碼 我們已經(jīng)討論了(n,k)線性分組碼的生成矩陣G與其對應(yīng)的一致校驗矩陣H，如果把(n,k)碼的一致校驗矩陣“看成”是(n,r)碼的生成矩陣，將(n,k)碼的生成矩陣“看成”是(n,r)碼的一致校驗矩陣，則稱這兩種碼互為對偶碼。 為了

22、使由原碼的一致檢驗矩陣和生成矩陣交換后所得的對偶碼的一致檢驗矩陣和生成矩陣具有標準形式，需在交換后對矩陣做列初等變換，此變換可通過將單位矩陣由前移到后或由后移到前實現(xiàn)，無需繁瑣的運算。8182例6.2.6 求例6.2.3所述 (7,3)碼的對偶碼。 顯然，(7,3)碼的對偶碼應(yīng)是(7,4)碼。由對偶碼的定義得，(7,4)碼的G矩陣就是(7,3)碼的H矩陣，將其化成標準形式。 將H(7,3)轉(zhuǎn)化成G(7,4)后，可按 得到(7,3)碼的對偶碼(7,4)碼，如表6.2.2所示。 表6.2.2 (例6.2.3) (7,3)線性碼的對偶碼(7,4)碼83信息碼元碼 字信息碼元碼 字m4 m3 m2 m

23、1c7 c6 c5 c4 c3 c2 c1m4 m3 m2 m1c7 c6 c5 c4 c3 c2 c10 0 0 00 0 0 0 0 0 01 0 0 01 0 0 0 1 0 10 0 0 10 0 0 1 0 1 11 0 0 11 0 0 1 1 1 00 0 1 00 0 1 0 1 1 01 0 1 01 0 1 0 0 1 10 0 1 10 0 1 1 1 0 11 0 1 11 0 1 1 0 0 00 1 0 00 1 0 0 1 1 11 1 0 01 1 0 0 0 1 00 1 0 10 1 0 1 1 0 01 1 0 11 1 0 1 0 0 10 1 1 00

24、 1 1 0 0 0 11 1 1 01 1 1 0 1 0 00 1 1 10 1 1 1 0 1 01 1 1 11 1 1 1 1 1 1 在有些情況下，如果對某一給定長度的信息碼元找不到合適碼長的碼，則可將某一(n,k)碼縮短以滿足要求。 例如，在(7,3)線性分組碼的碼字集合中將最左邊一位為0的消息和對應(yīng)的碼字選出來，并把消息中最左邊的0去掉，則可構(gòu)成(6,2)線性分組碼，這種碼稱為縮短碼。如表6.2.3所示。 表6.2.3 例6.2.3線性碼的(6,2)縮短碼 84信息碼元碼字m2 m1 c6 c5 c4 c3 c2 c10 00 0 0 0 0 00 10 1 1 1 0 11

25、01 0 0 1 1 11 11 1 1 0 1 0 縮短碼的G矩陣與H矩陣也可由原(n,k)碼的G和H推導而來。 (n-i,k-i)碼的生成矩陣是將(n,k)碼的生成矩陣去掉前i行和前i列即可，而H矩陣則只要去掉前i列即可。 (7,3)碼對應(yīng)的(6,2)縮短碼的G矩陣與H矩陣為 可按箭頭所指方向，從一個已知矩陣求出另一個矩陣。由此，一個(n,k)線性分組碼可以縮短成(n-i,k-i)線性分組碼。 對偶碼和縮短碼的糾錯能力沒有改變，即它們與原碼的糾錯性能相同。856.2.3 線性分組碼的譯碼 只要找到G矩陣或H矩陣，便解決了編碼問題。經(jīng)編碼后發(fā)送的碼字，由于信道干擾可能出錯，接收方怎樣發(fā)現(xiàn)或糾

26、正錯誤呢？這就是譯碼要解決的問題。 設(shè)發(fā)送的碼字為 ，信道產(chǎn)生的錯誤圖樣為 ，接收序列為 ，那么 ，即有ri=ci+ei(i=1,2,n)。譯碼的任務(wù)就是要從 中求出 ，從而得到碼字的估計值 。 由于(n,k)碼的任何一個碼字 均滿足 ，可將接收序列 用上式進行檢驗。若 即接收序列 滿足校驗關(guān)系， 是一個碼字，否則 有錯。86定義6.2.3 設(shè)(n,k)碼的一致校驗矩陣為H， 是發(fā)送碼字為 時的接收序列，則稱為接收序列 的伴隨式或校正子。 顯然，若錯誤圖樣 ，則 ，這時，接收序列 就是發(fā)送的碼字 ；若 ，則 ，說明 在傳輸過程中出錯，如能從 得到 ,則可從 恢復發(fā)送的碼字 。 若將(n,k)碼

27、的一致檢驗矩陣H寫成向量形式： 87式中 對應(yīng)H矩陣的某一列，它是一個r維的列向量。則伴隨式 上式說明，伴隨式 是一致校驗矩陣H各列的線性組合。如果錯誤圖樣 中有一些分量不為0，則在 中正好就是 中不為0的那幾列對應(yīng)的 組合而成。 由于 是r維列向量，所以伴隨式 也是一個r維列向量。 88結(jié)論： 由 可知伴隨式 僅與錯誤圖樣 有關(guān)，它充分反映了信道受干擾的情況，而與發(fā)送的是什么碼字無關(guān)。 伴隨式 是碼字是否有錯的判別式，若 ，則判 沒有出錯；若 ，則判有錯。 不同的錯誤圖樣具有不同的伴隨式，它們是一一對應(yīng)的，對二元碼來說，伴隨式 即為一致檢驗矩陣H中與錯誤圖樣對應(yīng)的各列之和。 注意(伴隨式檢錯

28、時的例外): 如果錯誤圖樣 本身就是一個碼字，即 碼，那么計算伴隨式 得到的結(jié)果必為 ，此時的錯誤不能發(fā)現(xiàn)(?)，也無法糾正，因而這樣的錯誤圖樣稱為不可檢錯誤圖樣。 89例6.2.7 計算例6.2.3所述(7,3)碼接收 時的伴隨式。 解 (7,3)碼的一致校驗矩陣為 當接收 時，接收端譯碼器根據(jù)接收序列計算的伴隨式 為90 因此，譯碼器判別接收序列無錯，即傳輸中未發(fā)生錯誤。 當接收 時，接收端譯碼器根據(jù)接收序列計算的伴隨式為: 由于 ，所以譯碼器判別接收序列 有錯，即傳輸中有錯誤發(fā)生。由于(7,3)碼是糾正單個錯誤的碼，經(jīng)觀察知 為H的第二列，因此可判定接收序列 的第二位發(fā)生了錯誤。由于接收

29、序列中錯誤個數(shù)與碼的糾錯能力相符，所以可正確譯碼，即發(fā)送碼字應(yīng)為 。 91 當接收 時，接收端譯碼器根據(jù)接收序列計算的伴隨式 為 ，但與H的任何一列都不相同，無法判別錯誤發(fā)生在哪些位上，此時只能發(fā)現(xiàn)有錯。 92 伴隨式 的計算可用電路來實現(xiàn)，如前所述的(7,3)碼，設(shè)接收序列 ，則伴隨式為 根據(jù)上式，可畫出(7,3)碼伴隨式 的計算電路，如圖6.2.3所示。 936.2.4 線性分組碼的糾錯能力 由前面的介紹可知，線性分組碼的糾錯能力t和碼字的最小距離dmin有關(guān)，一般t是在設(shè)計通信系統(tǒng)時提出的，那么尋找滿足糾正t個錯誤碼元的碼字就是編碼技術(shù)的任務(wù)，為此我們還需進一步研究dmin和碼字結(jié)構(gòu)的關(guān)

30、系。 線性分組碼碼字的結(jié)構(gòu)是由生成矩陣G(或一致校驗矩陣H)決定的，若已知H矩陣，該碼的結(jié)構(gòu)也就知道了，實際上所謂校驗就是利用H矩陣去鑒別接收矢量 的結(jié)構(gòu)。那么從研究碼的糾錯能力角度來看dmin與H有什么關(guān)系呢？ 94 利用伴隨式對碼字譯碼例 6.2.8 已知(7,3)線性分組碼的一致檢驗矩陣為對以下兩個碼字譯碼： 。解 假設(shè)有4種傳輸模式：(1) 發(fā)送的碼字在傳輸時沒有發(fā)生錯誤，即 ， 此時伴隨式為則 95(2)傳送中發(fā)生一個錯誤。若 ，根據(jù)接收序列分別計算伴隨式設(shè)接收碼字為96 這說明 的確僅與 有關(guān)，而與發(fā)送碼字無關(guān)。 對于該(7,3)線性分組碼，若發(fā)生一個錯誤，計算得到的正好與H中的某

31、一列向量相同。如果 正好與H的第i列相同，就說明接收序列的第i位出錯，即ei=1。本例的第一對接收序列， 均為H矩陣第一列，因此有 而第二對接收序列， 均為H矩陣的第二列，故 校正后的第一組接收碼字 。 校正后的第二組接收碼字 。 因此，分別有9798(3) 傳送中發(fā)生兩個錯誤。仍發(fā)送前述 ，即 計算伴隨式可得 由于 說明傳送的碼字有錯，但 與H矩陣中任何一列均不相同說明是不可糾正的錯誤，即無法由 得到 。這兩個碼字各自兩位錯的位置不同。 實際上 而分析 的結(jié)果可知是H矩陣中第1列與第2列之和，而 是H矩陣中第3列與第4列之和。這不但說明 與 有關(guān)，而且說明前述“ 是H中相應(yīng)于 不等于 的那些

32、列向量的線性組合”的結(jié)論是正確的。99(4) 傳送中發(fā)生三位錯。如發(fā)送前述 而接收 ，由 ，可知 通過計算伴隨式為 ，說明有錯。雖此時 與H矩陣第5列相等，但并不能說明 的第5位出錯。根據(jù)定理6.1.1所述最小碼距與檢錯、糾錯能力的關(guān)系可知，該(7,3)碼的dmin=4，其抗干擾能力為糾1檢2。若不用于糾錯，則該碼可檢出3位錯誤。所以本例能檢出3位錯誤，但不能糾正錯誤(?)。100 綜上所述，一個(n,k)碼要能糾正所有單個錯誤，則由所有單個錯誤的錯誤圖樣確定的 均不相同，且不等于 。 而一個(n,k)碼要能糾正t個錯誤，就必須要求t錯誤的所有可能組合的錯誤圖樣都必須有不同的伴隨式與之對應(yīng)。因

33、此若有 101 這說明(n,k)碼要能糾正t個錯誤，其H矩陣中任意2t列必須線性無關(guān)。這與定理6.1.1所述“若要糾正t個獨立差錯，則要求dmin2t+1”是一致的，即H矩陣中要求任意dmin-1列線性無關(guān)。定理6.2.1 (n,k)線性分組碼最小碼距等于dmin的充要條件是一致檢驗矩陣H矩陣中任意dmin-1列線性無關(guān)。 上述定理是構(gòu)造任何類型線性分組碼的基礎(chǔ)，由定理可得出以下三個結(jié)論： 為了構(gòu)造最小距離dmine+1(可檢測e個錯誤)或dmin2t+1(可糾正t個錯誤)的線性分組碼，其充要條件是要求H矩陣中任意dmin-1列線性無關(guān)。102 例如，要構(gòu)造最小距離為3的碼，則要求H矩陣中任意

34、2列線性無關(guān)。對于二元碼，即要求H矩陣滿足無相同的列和無全0的列，就可糾正所有單個錯誤(?)。 因為交換H矩陣的各列不會影響碼的最小距離，因此列向量相同但排列位置不同的所有H矩陣所對應(yīng)的分組碼，其糾錯能力和碼率是等價的。 任一線性分組碼的最小距離dmin(或最小重量Wmin)均滿足 dminn-k+1 。 滿足dmin=n-k+1的線性分組碼稱為極大最小距離碼。在同樣的n, k之下，由于dmin最大，因此糾錯能力更強。設(shè)計這種碼，是編碼工作中人們感興趣的一個課題。 根據(jù)定理6.2.1，可由H矩陣的列的相關(guān)性直接知道碼的糾錯、檢錯能力。103 在已知信息位k的條件下，如何去確定監(jiān)督位r=n-k

35、的位數(shù)(或確定碼長)，才能滿足對糾錯能力t的要求？對此有下述結(jié)論： 若C是(n,k)二元碼，當已知k時，要使C能糾正t個錯，則必須有不少于r個校驗位，并且使r滿足：式中的 為n中取i的組合。 (*)又稱為漢明不等式。 104105證 糾一個錯的(n,k)線性分組碼必須能糾正 個錯誤圖樣，因此式中右邊加1是由于考慮了無錯的情況。 而糾兩個錯的(n,k) 線性分組碼必須能糾正 個錯誤圖樣，所以有依此類推，一個糾t個錯誤的(n,k)線性分組碼必須滿足106 上式不僅表示了(n,k) 線性分組碼的糾錯能力t與錯誤圖樣數(shù)2r之間的關(guān)系，也說明了監(jiān)督碼元數(shù)r=n-k與糾錯能力t之間的關(guān)系。 當 時，稱該碼

36、為完備碼，這時由碼的糾錯能力所確定的伴隨式數(shù)恰好等于可糾的錯誤圖樣數(shù)，所以完備碼的r個監(jiān)督碼元得到了充分利用。 6.2.5 漢明碼 漢明碼是漢明 (Hamming)于1950年提出的能糾正一位錯的特殊的線性分組碼。漢明碼有許多很好的性質(zhì)，是一種完備碼，它可以用一種簡潔有效的方法進行譯碼。由于它的編、譯碼較簡單，且較容易實現(xiàn)，因此被廣泛采用，尤其是在計算機存儲與運算系統(tǒng)中被廣泛應(yīng)用。 漢明碼的參數(shù) 對于任意正整數(shù)m3，存在具有下列參數(shù)的二進制漢明碼： 碼長： n=2m-1 信息位數(shù)：k=2m-m-1 監(jiān)督位數(shù)：r=n-k 最小碼距：dmin=3107 給定m后，即可構(gòu)造出具體的(n,k)漢明碼，

37、這可以從建立一致校驗矩陣H入手。由于H矩陣的列數(shù)就是碼長n，行數(shù)等于r。例如m=3，可得出n=7, k=4，因而是(7,4)線性碼。其 H矩陣正是用2r-1個非零三維列向量構(gòu)成的, 如 此時，H矩陣的列所對應(yīng)的十進制數(shù)正好是17，對于糾一位差錯來說，其伴隨式的值就等于對應(yīng)的H矩陣的列矢量，即錯誤位置。所以，這種形式的H矩陣構(gòu)成的碼很便于糾錯，但這是非系統(tǒng)的(7,4)漢明碼的一致校驗矩陣。如果要得到系統(tǒng)碼，可調(diào)整各列次序來實現(xiàn)： 108有了H0，就可得到系統(tǒng)碼的校驗位，其相應(yīng)的生成矩陣為： 設(shè)碼字 ，根據(jù)H0及關(guān)系式 ，得校驗關(guān)系 109 (7,4)漢明碼的并行編碼電路原理圖如圖6.2.4所示。

38、 漢明碼的譯碼，可以采用計算伴隨式，然后確定錯誤圖樣并加以糾正的方法。圖6.2.5所示為(7,4)漢明碼的譯碼電路原理圖。 110 需要注意的是(7,4)漢明碼的H矩陣并非只有以上兩種。原則上講，(n,k)漢明碼的H矩陣有r行n列，這n列由除了全0以外的r位碼組構(gòu)成，每個碼組只在某列中出現(xiàn)一次，H矩陣各列的次序可任意改變。 111 另外，由完備碼的定義 知，(7,4)漢明碼的r=3，最小碼距dmin=3，故其t=1，滿足上式。 所以(7,4)漢明碼實際上是t=1時的完備碼。6.3 循環(huán)碼 循環(huán)碼是一種特殊的線性分組碼，屬于線性分組碼的一個重要子類，也是目前研究最為透徹的一類碼，大多數(shù)有實用價值

39、的糾錯碼都是循環(huán)碼。 循環(huán)碼比一般的線性分組碼具有優(yōu)點：循環(huán)碼的編碼及譯碼易于用簡單的具有反饋連接的移位寄存器來實現(xiàn)。 定義6.3.1 設(shè)有(n,k)線性分組碼C，如果它的任意一個碼字的每一次循環(huán)移位仍然是C中的一個碼字，則稱C為循環(huán)碼。也即，如果 是循環(huán)碼C的一個碼字，那么 也都是C的碼字時，所有這些具有循環(huán)特性的碼字的全體構(gòu)成了循環(huán)碼。 112 例如在例6.2.3中的(7,3)線性分組碼就是循環(huán)碼，該碼如表6.3.1所示。由表可以看到，在右邊的碼字欄內(nèi)，任一個碼字將其循環(huán)移位后，其結(jié)果仍是該欄內(nèi)的一個碼字。例如將第二行的碼字循環(huán)右移一位后可得到第四行的碼字，第四行的碼字循環(huán)右移一位后得到第

40、八行的碼字等。循環(huán)右移和左移具有同樣的效果。 113信息碼元碼字m3 m2 m1c7 c6 c5 c4 c3 c2 c10 0 00 0 0 0 0 0 00 0 10 0 1 1 1 0 10 1 00 1 0 0 1 1 10 1 10 1 1 1 0 1 01 0 01 0 0 1 1 1 01 0 11 0 1 0 0 1 11 1 01 1 0 1 0 0 11 1 11 1 1 0 1 0 0表6.3.1循環(huán)碼舉例循環(huán)碼的主要特點： 理論成熟：可利用成熟的代數(shù)結(jié)構(gòu)深入探討其性質(zhì)。 實現(xiàn)簡單：可利用循環(huán)移位特性在工程上進行編、譯碼。 循環(huán)碼的描述方式有很多，但在工程上最有用的是多項式

41、描述方法。 由于循環(huán)碼的以上特點，可以將其用多項式來表示，從而可以借助代數(shù)的工具對循環(huán)碼進行分析，這也是循環(huán)碼能被廣泛應(yīng)用的原因之一。 1146.3.1 循環(huán)碼的多項式描述 設(shè)有循環(huán)碼字 ， 則可以用一個次數(shù)不超過n-1的多項式惟一確定，其相應(yīng)的多項式可表示為 C(x)=cnxn-1+cn-1xn-2+c2x+c1 (6.3.1) 即碼字 與碼多項式C(x)一一對應(yīng)。 由循環(huán)碼的特性可知，若 是循環(huán)碼C的一個碼字，則 也是該循環(huán)碼C的一個碼字，它的碼多項式為： C(1)(x)=cn-1xn-1+cn-2xn-2+c1x+cn (6.3.2) 115 比較式(6.3.1)和式(6.3.2)，得：

42、 該式說明，碼字循環(huán)一次的碼多項式C(1)(x)是原碼多項式C(x)乘x后再除以xn+1所得的余式，即 C(1)(x)=xC(x)mod(xn+1) 由此可以推知，C(x)的i次循環(huán)移位C(i)(x)是原碼多項式 C(x)乘xi后再除以xn+1所得的余式，即 C(i)(x)=xiC(x)mod(xn+1) (6.3.3) 式(6.3.3)揭示了(n,k)線性碼中碼多項式與碼字循環(huán)移位之間的關(guān)系，它對循環(huán)碼的研究起著重要的作用。 116循環(huán)次數(shù)碼字碼 多 項 式 0 0 0 0 0 0 000 0 1 1 1 0 1x4+x3+x2+110 1 1 1 0 1 0 x(x4+x3+x2+1)mo

43、d(x7+1)=x5+x4+x3+x21 1 1 0 1 0 0 x2(x4+x3+x2+1)mod(x7+1)=x6+x5+x4+x231 1 0 1 0 0 1x3(x4+x3+x2+1)mod(x7+1)=x6+x5+x3+141 0 1 0 0 1 1x4(x4+x3+x2+1)mod(x7+1)=x6+x4+x+150 1 0 0 1 1 1x5(x4+x3+x2+1)mod(x7+1)=x5+x2+x+161 0 0 1 1 1 0 x6(x4+x3+x2+1)mod(x7+1)=x6+x3+x2+x 例如，前述(7,3)循環(huán)碼可由任一碼字(如0011101)經(jīng)循環(huán)移位后得到其他6

44、個碼字；也可由相應(yīng)的碼多項式x4+x3+x2+1乘以xi(i=1,2,6)后，再取x7+1的模得到其他6個非零碼多項式。(7,3)循環(huán)碼的循環(huán)移位過程及相應(yīng)多項式如表6.3.2所示。 表6.3.2 (7,3)循環(huán)碼的循環(huán)移位1176.3.2 循環(huán)碼的生成矩陣 根據(jù)循環(huán)碼的循環(huán)特性，可由一個碼字的循環(huán)移位得到其他非0碼字。 (n,k)循環(huán)碼的碼多項式中每一個能整除xn+1的(n-k)次首一多項式(其最高次項系數(shù)為l)都是該碼的生成多項式，記為g(x)。 將g(x)經(jīng)過(k-1)次循環(huán)移位，共得到k個碼多項式：g(x) 、xg(x) 、xk-1g(x) 。這k個碼多項式顯然是相互獨立的，可作為碼生

45、成矩陣的k行，將上述碼多項式按行降序排列，得到循環(huán)碼的生成矩陣G(x)： 118 碼的生成矩陣一旦確定，碼也就確定了。這說明(n,k)循環(huán)碼可由它的一個n-k次首一多項式g(x)來確定，因此可以說由g(x)生成了(n,k)循環(huán)碼。因此稱g(x)為碼的生成多項式，即 g(x)=gn-kxn-k+g1x+g0 若碼C具有生成多項式g(x)，則該碼一定是循環(huán)碼。 碼的生成多項式g(x)的性質(zhì)： 在(n,k)循環(huán)碼中，(n-k)次碼多項式是最低次的碼多項式。 在(n,k)循環(huán)碼中，g(x)是惟一的(n-k)次多項式。 在(n,k)循環(huán)碼中，每個碼多項式C(x)都是g(x)的倍式。 任意(n,k)循環(huán)碼

46、的生成多項式g(x)一定整除xn+1。119120證明 (n,k)循環(huán)碼的生成多項式g(x)是xn+1的因式，即 xn+1 = g(x)h(x) (g(x)一定整除xn+1| h(x)=(xn+1)/g(x)|(xn+1)modg(x)=0) 。 由于xkg(x)是n次多項式，可表示為 xkg(x)=(xn+1)+g(k)(x) (*)其中g(shù)(k)(x)= xkg(x) mod (xn+1)。由循環(huán)碼的循環(huán)移位關(guān)系知，xkg(x)是g(x)循環(huán)移位k次所得的碼多項式，故g(k)(x)是g(x)的倍式。設(shè) g(k)(x)= m(x)g(x)代入(*)，得 xn+1=xk +m(x)g(x)上式表

47、明g(x)是xn+1的因式。例6.3.1 求二進制(7,4)循環(huán)碼的生成矩陣。解 為求生成矩陣，需先求生成多項式。由定義知，對于(7,4)循環(huán)碼，只需找到一個能夠整除x7+1的三次首一多項式(?)。為此，將x7+1分解因式，有 x7+1=(x+1)(x3+x+1)(x3+x2+1) 上式中滿足三次首一多項式要求的有兩個因式，可從中任選一個作為生成多項式，如選擇 g(x)=x3+x+1 為得出生成矩陣，先寫出生成矩陣各行的系數(shù)，即 xg(x)=x4+x2+x x2g(x)=x5+x3+x2 x3g(x)=x6+x4+x3121為什么只進行 3 次循環(huán)移位? 因此，按照生成矩陣的定義有 故對應(yīng)(7

48、,4)循環(huán)碼的生成矩陣為122例6.3.2 求二進制(7,3)循環(huán)碼的生成多項式。解 分解多項式x7+1，取其四次首一多項式作為生成多項式(?) x7+1=(x+1)(x3+x+1)(x3+x2+1) 可將一次和任一三次多項式的乘積作為生成多項式： g1(x)=(x+1)(x3+x+1) = x4+x3+x2+1或 g2(x)=(x+1)(x3+x2+1) =x4+x2+x+1(如何用g1(x)或g2(x)生成(7,3)循環(huán)碼? ) 由于(n,k)線性碼的G矩陣與H矩陣滿足關(guān)系 GHT=0 而循環(huán)碼也是線性碼，如果設(shè)g(x)為(n,k)循環(huán)碼的生成多項式，它必為x7+1的因式，則有 xn+1=

49、g(x)h(x) (6.3.6) 123 g(x)是n-k次多項式，以g(x)為生成多項式，生成一個(n,k)循環(huán)碼。 h(x)是k次多項式，以h(x)為生成多項式，生成一個(n,n-k)循環(huán)碼，這兩個循環(huán)碼互為對偶碼。稱h(x)為循環(huán)碼的校驗多項式，且 h(x)=hkxk+h1x+h0 (6.3.7) 顯然，循環(huán)碼也可由其校驗多項式完全確定，(n,k)循環(huán)碼的一致校驗矩陣H為 (6.3.8) 124n-k-1個0上式中h*(x)為h(x)的反多項式 h*(x)=h0 xk+h1xk-1+hk-1x+hk例6.3.3 以二進制碼(7,3)碼為例，說明(n,k)循環(huán)碼可由生成多項式g(x)或校驗

50、多項式h(x)完全確定。解 由多項式的因式分解知 x7+1=(x3+x+1)(x4+x2+x+1) 其四次多項式為生成多項式g(x)(?) g(x)=x4+x2+x+1=g4x4+g3x3+g2x2+g1x+g0 (其中g(shù)3=0) 125r行n-k-1個0 其三次多項式為校驗多項式h(x)(?) h(x)= x3+x+1=h3x3+h2x2+h1x+h0 (其中h2=0) 由等式x7+1=g(x)h(x)，兩端的同次系數(shù)應(yīng)相等，得 x3的系數(shù) g3h0+g2h1+g1h2+g0h3=0 x4的系數(shù) g4h0+g3h1+g2h2+g1h3=0 x5的系數(shù) g4h1+g3h2+g2h3=0 x6的

51、系數(shù) g4h2+g3h3=0 將上述方程組寫成矩陣形式：126 上式中列矩陣(列向量)的元素就是生成多項式g(x)的系數(shù)，它本身是一個碼字，那么第一個矩陣即為(7,3)循環(huán)碼的一致校驗矩陣，即 可見，一致校驗矩陣的第一行是碼的校驗多項式h(x) 的系數(shù)的反序排列(h(x)的反多項式)，而第二、三、四行分別是第一行的逐次左移位，由此得到用校驗多項式的系數(shù)構(gòu)成的一致校驗矩陣： 127結(jié)論： 給定了(n,k)循環(huán)碼的生成多項式g(x)，可以求得相應(yīng)的生成矩陣G，由g(x)又可以確定校驗多項式h(x)，并可由h(x)確定循環(huán)碼的一致校驗矩陣H。 生成多項式g(x)與生成矩陣G的含義是相同的，g(x)對

52、應(yīng)于循環(huán)碼的多項式表示方式，而G矩陣對應(yīng)于循環(huán)碼的矩陣表示方式，兩者之間可以相互轉(zhuǎn)換。校驗多項式h(x)與一致校驗矩陣H的關(guān)系同上。128稱為生成多項式定理：在一個(n,k)循環(huán)碼中，有唯一的一個n-k次多項式g(x)= xn-k+ gn-k-1xn-k-1 + + g2x2+ g1x+ 1，每個為g(x)倍式的小于等于n-1次的多項式一定是碼多項式。反之，每一個碼多項式C(x)是g(x)的倍式。定理：(n,k)循環(huán)碼的生成多項式g(x)是xn+1的因式，反之，若g(x)是xn+1的一個n-k次因式，則g(x)生成(n,k)循環(huán)碼。概括地說，要生成一個(n,k)循環(huán)碼，就是要找到一個能除盡xn

53、+1的r=n-k次首生成多項式g(x),由g(x)來生成各個碼多項式后，找出與碼多項式相對應(yīng)的循環(huán)碼字。例子例GF(2)上多項式構(gòu)造一個（7，3）循環(huán)碼。碼多項式碼 字（0010111）（0101110）（1011100）（0111001）（1110010）（1100101）（1001011）（0000000）只要知道了xn+1的因式分解，用它的各個因式的乘積，便能得到很多個不同的循環(huán)碼。定理：在一個(n,k)循環(huán)碼中，有唯一的一個n-k次多項式g(x)= xn-k+ gn-k-1xn-k-1 + + g2x2+ g1x+ 1，每個為g(x)倍式的小于等于n-1次的多項式一定是碼多項式。反之，

54、每一個碼多項式C(x)是g(x)的倍式。證：令r=n-k，由于g(x)= xr+ gr-1xr-1 + + g2x2+ g1x+ 1是(n,k)循環(huán)碼中次數(shù)最低的一個非零首多項式。由于碼的循環(huán)特性，xg(x), x2g(x), xn-1-rg(x)也必為碼多項式，從而它們的線性組合 (mn-1-rxn-1-r + + m2x2+ m1x+ m0 )g(x)=M(x) g(x)也必在循環(huán)碼中，故每一個次數(shù)等于或小于n-1次的g(x)的倍式是碼多項式。定理：(n,k)循環(huán)碼的生成多項式g(x)是xn+1的因式，反之， 若g(x)是xn+1的一個n-k次因式，則g(x)生成(n,k)循環(huán)碼。證：因g

55、(x)為n-k次，則xk g(x)為n次多項式，用xn+1除之， 由6-5式可得： xkg(x)xn+1+Ck(x)其中Ck(x)為碼多項式，總可以寫為g(x)的倍式形式， 即Ck(x)m(x)g(x)由此可以得出xn+1 (xk+m(x)g(x)即g(x)是xn+1的一個因式。反之，當g(x)為n-k次，則它的倍式的線性組合(m0 + m1x + m2x2 + mk-1xk-1) g(x)也是碼多項式， 系數(shù)m0 、 m1、 m2、 mk-1 共有2k種不同組合，正好 構(gòu)成(n,k)碼中k個信息元所形成的2k個碼多項式。C(x)=mk-1, m1,m0 = MG(x)式中G(x)為循環(huán)碼的生

56、成矩陣，其k行分別由g(x)循環(huán)移位而成。生成矩陣和一致校驗矩陣校驗矩陣校驗矩陣n-k-1個0上式中h*(x)為h(x)的反多項式 h*(x)=h0 xk+h1xk-1+hk-1x+hk例6.3.3 以二進制碼(7,3)碼為例，說明(n,k)循環(huán)碼可由生成多項式g(x)或校驗多項式h(x)完全確定。解 由多項式的因式分解知 x7+1=(x3+x+1)(x4+x2+x+1) 其四次多項式為生成多項式g(x)(?) g(x)=x4+x2+x+1=g4x4+g3x3+g2x2+g1x+g0 (其中g(shù)3=0) 136r行n-k-1個0其四次多項式為生成多項式g(x)(?) g(x)=x4+x2+x+1

57、=g4x4+g3x3+g2x2+g1x+g0 (其中g(shù)3=0) 其三次多項式為校驗多項式h(x) h(x)= x3+x+1=h3x3+h2x2+h1x+h0 (其中h2=0) 137但是這樣編成的循環(huán)碼不是系統(tǒng)碼。如要編成前k位是信息元，后r=n-k位是監(jiān)督元的n位系統(tǒng)碼，可以先用xn-k乘消息多項式M(x)，再用g(x)去除，即其中q(x)是商式，r(x)是次數(shù)小于n-k的余式。于是是g(x)的倍式，因而是由g(x)生成(n,k)循環(huán)碼的碼多項式。系統(tǒng)碼情況得碼字C(x)= m(x) xn-k + r(x) = m(x) xn-k + m(x) xn-k modg(x) 設(shè)從信源輸入編碼器的

58、k位信息組多項式為： m(x)=mk-1xk-1+m1x+m0 如果要編出系統(tǒng)碼的碼字，則： C(x)=m(x)xn-k+r(x) (C(x)=0 mod g(x) r(x)=m(x)xn-k mod g(x) (6.3.9) 從式(6.3.9)知，系統(tǒng)碼的編碼器就是將信息組m(x)乘上xn-k，然后與該乘積被生成多項式g(x)相除所得余式r(x)相加的電路。 系統(tǒng)循環(huán)碼的編碼步驟如下： 以xn-k 乘以m(x)； 以xn-k m(x)除以g(x) ，得到余式r(x)； 連接xn-k m(x)與r(x) ，得碼字C(x)= xn-k m(x) + r(x) ， 或C(x)= xn-k m(x)

59、 + xn-k m(x) mod g(x)1406.3.3 系統(tǒng)循環(huán)碼 前面介紹的生成矩陣所產(chǎn)生的循環(huán)碼不是系統(tǒng)碼。可以通過矩陣的行初等運算，得到系統(tǒng)循環(huán)碼的生成矩陣，使之具有 G=IkP的形式。 生成矩陣的行初等運算實質(zhì)上就是碼字間k個基底間進行線性組合運算。 由系統(tǒng)循環(huán)碼的生成矩陣所得的一致校驗矩陣是H=PTIn-k。例6.3.4 以g(x)=x3+x+1為生成多項式生成一個循環(huán)碼，要求生成的(7,4)循環(huán)碼是系統(tǒng)碼。 解 由例6.3.1得對應(yīng)給定g(x)的(7,4)循環(huán)碼的一般生成矩陣為： 141 對矩陣G進行行初等變換，將第、行相加后作為第1行，第、行相加后作為第2行，得 對應(yīng)的 這樣

60、，就得到系統(tǒng)循環(huán)碼的生成矩陣G0和一致校驗矩陣H0。 1426.3.4 多項式運算電路 由于多項式g(x)=gnxn+g1x+g0表示的是時間序列g(shù)=(gng1g0)，因而多項式的運算表現(xiàn)為對時間序列的操作。 設(shè)有多項式g(x)和h(x)，則 g(x)與h(x)的相加電路如圖6.3.1所示。若h(x)的階數(shù)m小于g(x)的階數(shù)n，則將h(x)也擴充為n次多項式，其擴充的冪次項系數(shù)為0。 圖6.3.1 多項式相加 143 多項式g(x)乘以x等價為時間序列g(shù)延遲一位，因為 g(x)h(x)= g(x)(h1(x)+h2(x)= g(x)h1(x)+ g(x)h2(x) 故多項式g(x)與h(x)