第9章信道糾錯編碼(ok)

第9章信道糾錯編碼(ok)第一頁，共69頁。9.1概述1、概述信道分類：從差錯控制角度看隨機信道：錯碼的出現(xiàn)是隨機的。突發(fā)信道：錯碼是成串集中出現(xiàn)的?；旌闲诺溃杭却嬖陔S機錯碼又存在突發(fā)錯碼。差錯控制技術(shù)的種類檢錯重發(fā)前向糾錯混合糾錯差錯控制編碼：常稱為糾錯編碼，不同的編碼方法，有不同的檢錯或糾錯能力。

第二頁，共69頁。9.1概述監(jiān)督碼元：信息碼元序列中增加的一些差錯控制碼元，它們稱為監(jiān)督碼元。多余度：就是指增加的監(jiān)督碼元多少。例如，若編碼序列中平均每兩個信息碼元就添加一個監(jiān)督碼元，則這種編碼的多余度為1/3。編碼效率(簡稱碼率)

：設(shè)編碼序列中信息碼元數(shù)量為k，總碼元數(shù)量為n，則比值k/n就是碼率。冗余度：監(jiān)督碼元數(shù)(n-k)和信息碼元數(shù)k之比。理論上，差錯控制以降低信息傳輸速率為代價換取提高傳輸可靠性。第三頁，共69頁。9.1概述2差錯控制技術(shù)圖

三種差錯控制方式示意圖

第四頁，共69頁。

1.檢錯重發(fā)方式檢錯重發(fā)又稱自動請求重傳方式，記作ARQ(AutomaticRepeatRequest)。由發(fā)端送出能夠發(fā)現(xiàn)錯誤的碼，由收端判決傳輸中無錯誤產(chǎn)生，如果發(fā)現(xiàn)錯誤，則通過反向信道把這一判決結(jié)果反饋給發(fā)端，然后，發(fā)端把收端認(rèn)為錯誤的信息再次重發(fā)，從而達到正確傳輸?shù)哪康?。其特點是需要反饋信道，譯碼設(shè)備簡單，對突發(fā)錯誤和信道干擾較嚴(yán)重時有效，但實時性差，主要在計算機數(shù)據(jù)通信中得到應(yīng)用。11.1概述第五頁，共69頁。

2.前向糾錯方式前向糾錯方式記作FEC(ForwordErrorCorrection)。發(fā)端發(fā)送能夠糾正錯誤的碼，收端收到信碼后自動地糾正傳輸中的錯誤。特點:是單向傳輸，實時性好，但譯碼設(shè)備較復(fù)雜。

11.1概述第六頁，共69頁。

3.混合糾錯方式混合糾錯方式記作HEC(HybridErrorCorrection)是FEC和ARQ方式的結(jié)合。發(fā)端發(fā)送具有自動糾錯同時又具有檢錯能力的碼。收端收到碼后，檢查差錯情況，如果錯誤在碼的糾錯能力范圍以內(nèi)，則自動糾錯，如果超過了碼的糾錯能力，但能檢測出來，則經(jīng)過反饋信道請求發(fā)端重發(fā)。這種方式具有自動糾錯和檢錯重發(fā)的優(yōu)點，可達到較低的誤碼率，因此，近年來得到廣泛應(yīng)用。

11.1概述第七頁，共69頁。9.2糾錯編碼的基本原理1、分組碼基本原理：（舉例說明）設(shè)有一種由3位二進制數(shù)字構(gòu)成的碼組，它共有8種不同的可能組合。若將其全部用來表示天氣，則可以表示8種不同天氣，例如：“000”（晴），“001”（云），“010”（陰），“011”（雨），“100”（雪），“101”（霜），“110”（霧），“111”（雹）。其中任一碼組在傳輸中若發(fā)生一個或多個錯碼，則將變成另一個信息碼組。這時，接收端將無法發(fā)現(xiàn)錯誤。第八頁，共69頁。9.2糾錯編碼的基本原理若在上述8種碼組中只準(zhǔn)許使用4種來傳送天氣，例如：

“000”＝晴，“011”＝云，“101”＝陰，

“110”＝雨這時，雖然只能傳送4種不同的天氣，但是接收端卻有可能發(fā)現(xiàn)碼組中的一個錯碼。例如，若“000”（晴）中錯了一位，則接收碼組將變成“100”或“010”或“001”。這3種碼組都是不準(zhǔn)使用的，稱為禁用碼組。第九頁，共69頁。9.2糾錯編碼的基本原理接收端在收到禁用碼組時，就認(rèn)為發(fā)現(xiàn)了錯碼。當(dāng)發(fā)生3個錯碼時，“000”變成了“111”，它也是禁用碼組，故這種編碼也能檢測3個錯碼。但是這種碼不能發(fā)現(xiàn)一個碼組中的兩個錯碼，因為發(fā)生兩個錯碼后產(chǎn)生的是許用碼組。上面這種編碼只能檢測錯碼，不能糾正錯碼。例如，當(dāng)接收碼組為禁用碼組“100”時，接收端將無法判斷是哪一位碼發(fā)生了錯誤，因為晴、陰、雨三者錯了一位都可以變成“100”。第十頁，共69頁。9.2糾錯編碼的基本原理檢錯和糾錯要能夠糾正錯誤，還要增加多余度。例如，若規(guī)定許用碼組只有兩個：“000”（晴），“111”（雨），其他都是禁用碼組，則能夠檢測兩個以下錯碼，或能夠糾正一個錯碼。例如，當(dāng)收到禁用碼組“100”時，若當(dāng)作僅有一個錯碼，則可以判斷此錯碼發(fā)生在“1”位，從而糾正為“000”（晴）。因為“111”（雨）發(fā)生任何一位錯碼時都不會變成“100”這種形式。但是，這時若假定錯碼數(shù)不超過兩個，則存在兩種可能性：“000”錯一位和“111”錯兩位都可能變成“100”，因而只能檢測出存在錯碼而無法糾正錯碼。第十一頁，共69頁。9.2糾錯編碼的基本原理2、分組碼的結(jié)構(gòu)將信息碼分組，為每組信息碼附加若干監(jiān)督碼的編碼稱為分組碼。在分組碼中，監(jiān)督碼元僅監(jiān)督本碼組中的信息碼元。信息位和監(jiān)督位的關(guān)系：舉例如下（偶校驗）信息位監(jiān)督位晴000云011陰101雨110第十二頁，共69頁。9.2糾錯編碼的基本原理分組碼的一般結(jié)構(gòu)分組碼的符號：(n,k)N－碼組的總位數(shù)，又稱為碼組的長度（碼長），k－碼組中信息碼元的數(shù)目，n

–

k＝r－碼組中的監(jiān)督碼元數(shù)目，或稱監(jiān)督位數(shù)目。

第十三頁，共69頁。9.2糾錯編碼的基本原理3、分組碼的碼重和碼距碼重：把碼組中“1”的個數(shù)目稱為碼組的重量，簡稱碼重。碼距：把兩個碼組中對應(yīng)位上數(shù)字不同的位數(shù)稱為碼組的距離，簡稱碼距。碼距又稱漢明距離。例如，“000”＝晴，“011”＝云，“101”＝陰，“110”＝雨，4個碼組之間，任意兩個的距離均為2。最小碼距：把某種編碼中各個碼組之間距離的最小值稱為最小碼距(d0)。例如，上面的編碼的最小碼距d0=2。第十四頁，共69頁。碼距和檢糾錯能力的關(guān)系

(1)在一個碼組內(nèi)要想檢出e位誤碼，要求最小碼距為dmin≥e+1(2)在一個碼組內(nèi)要想糾正t位誤碼，要求最小碼距為dmin≥2t+1(3)在一個碼組內(nèi)要想糾正t位誤碼，同時檢測出e

位誤碼（e>t）,要求最小碼距為dmin≥t+e+1

9.2糾錯編碼的基本原理第十五頁，共69頁。9.3糾錯編碼的性能系統(tǒng)帶寬和信噪比的矛盾：由上節(jié)所述的糾錯編碼原理可知，為了減少接收錯誤碼元數(shù)量，需要在發(fā)送信息碼元序列中加入監(jiān)督碼元。這樣作的結(jié)果使發(fā)送序列增長，冗余度增大。若仍須保持發(fā)送信息碼元速率不變，則傳輸速率必須增大，因而增大了系統(tǒng)帶寬。系統(tǒng)帶寬的增大將引起系統(tǒng)中噪聲功率增大，使信噪比下降。信噪比的下降反而又使系統(tǒng)接收碼元序列中的錯碼增多。一般說來，采用糾錯編碼后，誤碼率總是能夠得到很大改善的。改善的程度和所用的編碼有關(guān)。第十六頁，共69頁。9.3糾錯編碼的性能編碼性能舉例未采用糾錯編碼時， 若接收信噪比等于

7dB，編碼前誤碼率 約為810-4，圖中A

點，在采用糾錯編碼 后，誤碼率降至約4

10-5，圖中B點。這樣， 不增大發(fā)送功率就能 降低誤碼率約一個半 數(shù)量級。10-610-510-410-310-210-1編碼后PeCDEAB信噪比(dB)第十七頁，共69頁。9.3糾錯編碼的性能由圖還可以看出，若保持誤碼率在10-5，圖中C點，未采用編碼時，約需要信噪比Eb/n0=10.5dB。在 采用這種編碼時，約需要信噪比7.5dB，圖中D點?？梢怨?jié)省功率2dB。通常稱這2dB為編碼增益。上面兩種情況付出的代 價是帶寬增大。10-610-510-410-310-210-1編碼后PeCDEAB信噪比(dB)第十八頁，共69頁。9.3糾錯編碼的性能傳輸速率和Eb/n0的關(guān)系 對于給定的傳輸系統(tǒng)式中，RB為碼元速率。 若希望提高傳輸速率， 由上式看出勢必使信 噪比下降，誤碼率增 大。假設(shè)系統(tǒng)原來工作 在圖中C點，提高速率后 由C點升到E點。但加用 糾錯編碼后，仍可將誤碼 率降到D點。這時付出的 代價仍是帶寬增大。10-610-510-410-310-210-1編碼后PeCDEAB信噪比(dB)第十九頁，共69頁。9.4簡單的實用編碼1、奇偶監(jiān)督碼奇偶監(jiān)督碼分為奇數(shù)監(jiān)督碼和偶數(shù)監(jiān)督碼兩種，兩者的原理相同。在偶數(shù)監(jiān)督碼中，無論信息位多少，監(jiān)督位只有1位，它使碼組中“1”的數(shù)目為偶數(shù)，即滿足下式條件： 式中a0為監(jiān)督位，其他位為信息位。 這種編碼能夠檢測奇數(shù)個錯碼。在接收端，按照上式求“模2和”，若計算結(jié)果為“1”就說明存在錯碼，結(jié)果為“0”就認(rèn)為無錯碼。 奇數(shù)監(jiān)督碼與偶數(shù)監(jiān)督碼相似，只不過其碼組中“1”的數(shù)目為奇數(shù)：第二十頁，共69頁。9.4簡單的實用編碼2、二維奇偶監(jiān)督碼（方陣碼）二維奇偶監(jiān)督碼的構(gòu)成 它是先把上述奇偶監(jiān)督碼的若干碼組排成矩陣，每一碼組寫成一行，然后再按列的方向增加第二維監(jiān)督位，如下圖所示第二十一頁，共69頁。9.4簡單的實用編碼圖中a01

a02

a0m為m行奇偶監(jiān)督碼中的m個監(jiān)督位。

cn-1

cn-2

c1

c0為按列進行第二次編碼所增加的監(jiān)督位，它們構(gòu)成了一監(jiān)督位行。二維奇偶監(jiān)督碼的性能這種編碼有可能檢測偶數(shù)個錯碼。因為每行的監(jiān)督位雖然不能用于檢測本行中的偶數(shù)個錯碼，但按列的方向有可能由cn-1

cn-2

c1

c0等監(jiān)督位檢測出來。有一些偶數(shù)錯碼不可能檢測出來。第二十二頁，共69頁。9.4簡單的實用編碼例如，構(gòu)成矩形的4個錯碼，如圖中 錯了，就檢測不出。這種二維奇偶監(jiān)督碼適于檢測突發(fā)錯碼。因為突發(fā)錯碼常常成串出現(xiàn)，隨后有較長一段無錯區(qū)間。由于方陣碼只對構(gòu)成矩形四角的錯碼無法檢測，故其檢錯能力較強。二維奇偶監(jiān)督碼不僅可用來檢錯，還可以用來糾正一些錯碼。例如，僅在一行中有奇數(shù)個錯碼時。第二十三頁，共69頁。9.4簡單的實用編碼3、恒比碼在恒比碼中，每個碼組均含有相同數(shù)目的“1”（和“0”）。由于“1”的數(shù)目與“0”的數(shù)目之比保持恒定，故得此名。這種碼在檢測時，只要計算接收碼組中“1”的數(shù)目是否對，就知道有無錯碼。恒比碼的主要優(yōu)點是簡單和適于用來傳輸電傳機或其他鍵盤設(shè)備產(chǎn)生的字母和符號。對于信源來的二進制隨機數(shù)字序列，這種碼就不適合使用了。第二十四頁，共69頁。11.4簡單的實用編碼4、正反碼正反碼的編碼：它是一種簡單的能夠糾正錯碼的編碼。其中的監(jiān)督位數(shù)目與信息位數(shù)目相同，監(jiān)督碼元與信息碼元相同或者相反則由信息碼中“1”的個數(shù)而定。例如，若碼長n=10，其中信息位k=5，監(jiān)督位r=5。其編碼規(guī)則為：當(dāng)信息位中有奇數(shù)個“1”時，監(jiān)督位是信息位的簡單重復(fù)；當(dāng)信息位有偶數(shù)個“1”時，監(jiān)督位是信息位的反碼。第二十五頁，共69頁。9.5線性分組碼一、基本概念代數(shù)碼：建立在代數(shù)學(xué)基礎(chǔ)上的編碼。線性碼：按照一組線性方程構(gòu)成的代數(shù)碼。在線性碼中信息位和監(jiān)督位是由一些線性代數(shù)方程聯(lián)系著的。線性分組碼：按照一組線性方程構(gòu)成的分組碼。

本節(jié)將以漢明碼為例引入線性分組碼的一般原理。第二十六頁，共69頁。9.5線性分組碼漢明碼～能夠糾正1位錯碼且編碼效率較高的一種線性分組碼1、漢明碼的構(gòu)造原理。在偶數(shù)監(jiān)督碼中，由于使用了一位監(jiān)督位a0，它和信息位an-1

…

a1一起構(gòu)成一個代數(shù)式： 在接收端解碼時，實際上就是在計算若S=0，就認(rèn)為無錯碼；若S=1，就認(rèn)為有錯第二十七頁，共69頁。9.5線性分組碼碼?，F(xiàn)將上式稱為監(jiān)督關(guān)系式，S稱為校正子。由于校正子S只有兩種取值，故它只能代表有錯和無錯這兩種信息，而不能指出錯碼的位置。一般來說，若碼長為n，信息位數(shù)為k，則監(jiān)督位數(shù)r＝n－k。如果希望用r個監(jiān)督位構(gòu)造出r個監(jiān)督關(guān)系式來指示1位錯碼的n種可能位置，則要求 下面通過一個例子來說明如何具體構(gòu)造這些監(jiān)督關(guān)系式。第二十八頁，共69頁。9.5線性分組碼例：設(shè)分組碼(n,k)中k=4，為了糾正1位錯碼，由上式可知，要求監(jiān)督位數(shù)r

3。若取r=3，則n=k+r=7。我們用a6

a5

a0表示這7個碼元，用S1、S2和S3表示3個監(jiān)督關(guān)系式中的校正子，則S1、S2和S3的值與錯碼位置的對應(yīng)關(guān)系可以規(guī)定如下表所列（表1）S1S2

S3錯碼位置S1S2

S3錯碼位置001a0101a4010a1110a5100a2111a6011a3000無錯碼第二十九頁，共69頁。9.5線性分組碼 由表中規(guī)定可見，僅當(dāng)一位錯碼的位置在a2

、a4、a5或a6時，校正子S1為1；否則S1為零。這就意味著a2

、a4、a5和a6四個碼元構(gòu)成偶數(shù)監(jiān)督關(guān)系： 同理，a1、a3、a5和a6構(gòu)成偶數(shù)監(jiān)督關(guān)系： 以及a0、a3、a4

和a6構(gòu)成偶數(shù)監(jiān)督關(guān)系第三十頁，共69頁。9.5線性分組碼在發(fā)送端編碼時，信息位a6、a5、a4和a3的值決定于輸入信號，因此它們是隨機的。監(jiān)督位a2、a1和a0應(yīng)根據(jù)信息位的取值按監(jiān)督關(guān)系來確定，即監(jiān)督位應(yīng)使上3式中S1、S2和S3的值為0（表示編成的碼組中應(yīng)無錯碼）： 上式經(jīng)過移項運算，解出監(jiān)督位第三十一頁，共69頁。9.5線性分組碼信息位a6a5a4a3監(jiān)督位a2a1a0信息位a6a5a4a3監(jiān)督位a2a1a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111給定信息位后，可以直接按上式算出監(jiān)督位，結(jié)果見表2：第三十二頁，共69頁。9.5線性分組碼接收端收到每個碼組后，先計算出S1、S2和S3，再查表判斷錯碼情況。例如，若接收碼組為，按上述公式計算可得：S1=0，S2=1，S3=1。由于S1

S2

S3

等于011，故查表1可知在a3位有1錯碼。按照上述方法構(gòu)造的碼稱為漢明碼。表中所列的(7,4)漢明碼的最小碼距d0=3。因此，這種碼能夠糾正1個錯碼或檢測2個錯碼。由于碼率k/n=(n-r)/n=1–

r/n，故當(dāng)n很大和r很小時，碼率接近1?？梢?，漢明碼是一種高效碼。第三十三頁，共69頁。9.5線性分組碼二、線性分組碼的一般原理1、線性分組碼的構(gòu)造H矩陣上面(7,4)漢明碼的例子有現(xiàn)在將上面它改寫為

上式中已經(jīng)將“”簡寫成“+”。

第三十四頁，共69頁。9.5線性分組碼上式可以表示成如下矩陣形式：

該式可以簡記為HAT=0T

或AHT=0第三十五頁，共69頁。9.5線性分組碼

式中A=[a6

a5

a4

a3

a2

a1

a0]，0=[000]

將H稱為監(jiān)督矩陣。 只要監(jiān)督矩陣H給定，編碼時監(jiān)督位和信息位的關(guān)系就完全確定了。第三十六頁，共69頁。9.5線性分組碼H矩陣的性質(zhì)：

1)H的行數(shù)就是監(jiān)督關(guān)系式的數(shù)目，它等于監(jiān)督位的數(shù)目r。H的每行中“1”的位置表示相應(yīng)碼元之間存在的監(jiān)督關(guān)系。例如，H的第一行表示監(jiān)督位a2是由a6

a5

a4之和決定的。H矩陣可以分成兩部分，例如式中，P為r

k階矩陣，Ir為r

r階單位方陣。我們將具有[PIr]形式的H矩陣稱為典型陣。第三十七頁，共69頁。9.5線性分組碼

2)由代數(shù)理論可知，H矩陣的各行應(yīng)該是線性無關(guān)的，否則將得不到r個線性無關(guān)的監(jiān)督關(guān)系式，從而也得不到r個獨立的監(jiān)督位。若一矩陣能寫成典型陣形式[PIr]，則其各行一定是線性無關(guān)的。因為容易驗證[Ir]的各行是線性無關(guān)的，故[PIr]的各行也是線性無關(guān)的。第三十八頁，共69頁。9.5線性分組碼G矩陣：上面漢明碼例子中的監(jiān)督位公式為

也可以改寫成矩陣形式：

或者寫成第三十九頁，共69頁。9.5線性分組碼

式中，Q為一個k

r階矩陣，它為P的轉(zhuǎn)置，即Q=

PT

上式表示，在信息位給定后，用信息位的行矩陣乘矩陣Q就產(chǎn)生出監(jiān)督位。第四十頁，共69頁。9.5線性分組碼我們將Q的左邊加上1個kk階單位方陣，就構(gòu)成1個矩陣G

G稱為生成矩陣，因為由它可以產(chǎn)生整個碼組，即有 或者 因此，如果找到了碼的生成矩陣G，則編碼的方法就完全確定了。具有[IkQ]形式的生成矩陣稱為典型生成矩陣。由典型生成矩陣得出的碼組A中，信息位的位置不變，監(jiān)督位附加于其后。這種形式的碼稱為系統(tǒng)碼。第四十一頁，共69頁。9.5線性分組碼G矩陣的性質(zhì)：

1)G矩陣的各行是線性無關(guān)的。因為由上式可以看出，任一碼組A都是G的各行的線性組合。G共有k行，若它們線性無關(guān)，則可以組合出2k種不同的碼組A，它恰是有k位信息位的全部碼組。若G的各行有線性相關(guān)的，則不可能由G生成2k種不同的碼組了。

2)實際上，G的各行本身就是一個碼組。因此，如果已有k個線性無關(guān)的碼組，則可以用其作為生成矩陣G，并由它生成其余碼組。第四十二頁，共69頁。9.5線性分組碼錯碼矩陣和錯誤圖樣

一般說來，A為一個n列的行矩陣。此矩陣的n個元素就是碼組中的n個碼元，所以發(fā)送的碼組就是A。此碼組在傳輸中可能由于干擾引入差錯，故接收碼組一般說來與A不一定相同。若設(shè)接收碼組為一n列的行矩陣B，即 則發(fā)送碼組和接收碼組之差為

B

–

A=E(模2)

第四十三頁，共69頁。9.5線性分組碼錯碼矩陣和錯誤圖樣

E就是傳輸中產(chǎn)生的錯碼行矩陣

式中

因此，若ei=0，表示該接收碼元無錯；若ei=1，則表示該接收碼元有錯。

B

–

A=E可以改寫成B=A+E

例如，若發(fā)送碼組A=[1000111]，錯碼矩陣E=[0000100]，則接收碼組B=[1000011]。 錯碼矩陣有時也稱為錯誤圖樣。第四十四頁，共69頁。9.5線性分組碼校正子S

當(dāng)接收碼組有錯時，E

0，將B當(dāng)作A代入公式(AHT=0)后，該式不一定成立。在錯碼較多，已超過這種編碼的檢錯能力時，B變?yōu)榱硪辉S用碼組，則該式仍能成立。這樣的錯碼是不可檢測的。在未超過檢錯能力時，上式不成立，即其右端不等于0。假設(shè)這時該式的右端為S，即

BHT=S

將B=A+E代入上式，可得

S=(A+E)HT=A

HT+E

HT

第四十五頁，共69頁。9.5線性分組碼校正子S

由于AHT=0，所以

S=EHT

式中S稱為校正子。它能用來指示錯碼的位置。

S和錯碼E之間有確定的線性變換關(guān)系。若S和E之間一一對應(yīng)，則S將能代表錯碼的位置。第四十六頁，共69頁。9.5線性分組碼二、線性分組碼的性質(zhì)封閉性：是指一種線性碼中的任意兩個碼組之和仍為這種碼中的一個碼組。 由于線性碼具有封閉性，所以兩個碼組(A1和A2)之間的距離（即對應(yīng)位不同的數(shù)目）必定是另一個碼組(A1+A2)的重量（即“1”的數(shù)目）。因此，碼的最小距離就是碼的最小重量（除全“0”碼組外）。第四十七頁，共69頁?！纠}1】

已知一線性(6，3)碼的生成矩陣為,寫出該碼組的所有許用碼組,并判斷該碼組的糾檢錯能力，求監(jiān)督矩陣。9.5線性分組碼第四十八頁，共69頁。【例題2】設(shè)一線性分組碼的一致監(jiān)督方程為下式關(guān)系,其中，C5、C4、C3為信息碼元（1）寫出監(jiān)督矩陣和生成矩陣。（2）寫出所有的碼字。（3）判斷下列碼是否為碼字，B1=（011101），B2=（101011），B3=（110101）。若為非碼字，如何糾錯或檢錯。9.5線性分組碼第四十九頁，共69頁。9.6循環(huán)碼1、循環(huán)碼原理循環(huán)性：循環(huán)性是指任一碼組循環(huán)一位（即將最右端的一個碼元移至左端，或反之）以后，仍為該碼中的一個碼組。在下表中給出一種(7,3)循環(huán)碼的全部碼組。碼組編號信息位監(jiān)督位碼組編號信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a01000000051001011200101116101110030101110711001014011100181110010第五十頁，共69頁。9.6循環(huán)碼

例如，表中的第2碼組向右移一位即得到第5碼組；第6碼組向右移一位即得到第7碼組。一般說來，若(an-1

an-2

…a0)是循環(huán)碼的一個碼組，則循環(huán)移位后的碼組

(an-2

an-3

…

a0

an-1) (an-3

an-4

…

an-1

an-2)

…

…

… (a0

an-1

…a2

a1)

也是該編碼中的碼組。第五十一頁，共69頁。9.6循環(huán)碼碼多項式碼組的多項式表示法 把碼組中各碼元當(dāng)作是一個多項式的系數(shù)，即把一個長度為n的碼組表示成

這種多項式中，x僅是碼元位置的標(biāo)記，例如上式表示第7碼組中a6、a5、a2和a0為“1”，其他均為0。因此我們并不關(guān)心x的取值。

第五十二頁，共69頁。9.6循環(huán)碼

碼多項式的按模運算在整數(shù)運算中，有模n運算。例如，在模2運算中，有

1+1=20(模2)，

1+2=31(模2)，

23=60(模2)

等等。一般說來，若一個整數(shù)m可以表示為式中，Q

－整數(shù)，

則在模n運算下，有m

p(模n)即，在模n運算下，一個整數(shù)m等于它被n除得的余數(shù)P。

第五十三頁，共69頁。9.6循環(huán)碼在碼多項式運算中也有類似的按模運算 若一任意多項式F(x)被一n次多項式N(x)除，得到商式Q(x)和一個次數(shù)小于n的余式R(x)，即 則寫為 這時，碼多項式系數(shù)仍按模2運算，即系數(shù)只取0和1。例如，x3被(x3+1)除，得到余項1。所以有

第五十四頁，共69頁。9.6循環(huán)碼

x4+x2+1xx3+1

x4+x

x2+x+1應(yīng)當(dāng)注意，由于在模2運算中，用加法代替了減法，故余項不是x2–x+1，而是x2+x+1。例：第五十五頁，共69頁。9.6循環(huán)碼循環(huán)碼的碼多項式在循環(huán)碼中，若T(x)是一個長為n的許用碼組，則xiT(x)在按模xn+1運算下，也是該編碼中的一個許用碼組，即若 則T(x)也是該編碼中的一個許用碼組。

第五十六頁，共69頁。9.6循環(huán)碼例如，循環(huán)碼組其碼長n=7?，F(xiàn)給定i=3，則

其對應(yīng)的碼組為，它正是表中第3碼組。

由上述分析可見，一個長為n的循環(huán)碼必定為按模(xn+1)運算的一個余式。第五十七頁，共69頁。9.6循環(huán)碼循環(huán)碼的生成矩陣G由上節(jié)中公式可知，有了生成矩陣G，就可以由k個信息位得出整個碼組，而且生成矩陣G的每一行都是一個碼組。例如，在此式中，若a6a5a4a3=1000，則碼組A就等于G的第一行；若a6a5a4a3=0100，則碼組A就等于G的第二行；等等。由于G是k行n列的矩陣，因此若能找到k個已知碼組，就能構(gòu)成矩陣G。如前所述，這k個已知碼組必須是線性不相關(guān)的，否則給定的信息位與編出的碼組就不是一一對應(yīng)的。第五十八頁，共69頁。9.6循環(huán)碼循環(huán)碼的生成矩陣G在循環(huán)碼中，一個(n,k)碼有2k個不同的碼組。若用g(x)表示其中前(k-1)位皆為“0”的碼組，則g(x)，xg(x)，x2g(x)，，xk-1g(x)都是碼組，而且這k個碼組是線性無關(guān)的。因此它們可以用來構(gòu)成此循環(huán)碼的生成矩陣G。在循環(huán)碼中除全“0”碼組外，再沒有連續(xù)k位均為“0”的碼組，即連“0”的長度最多只能有(k-1)位。否則，在經(jīng)過若干次循環(huán)移位后將得到一個k位信息位全為“0”，但監(jiān)督位不全為“0”的一個碼組。這在線性碼中顯然是不可能的。第五十九頁，共69頁。9.6循環(huán)碼因此，g(x)必須是一個常數(shù)項不為“0”的(n-k)次多項式，而且這個g(x)還是這種(n,k)碼中次數(shù)為(n

–

k)的唯一多項式。因為如果有兩個，則由碼的封閉性，把這兩個相加也應(yīng)該是一個碼組，且此碼組多項式的次數(shù)將小于(n

–

k)，即連續(xù)“0”的個數(shù)多于(k

–1)。顯然，這是與前面的結(jié)論矛盾的，故是不可能的。我們稱這唯一的(n

–

k)次多項式g(x)為碼的生成多項式。一旦確定了g(x)，則整個(n,k)循環(huán)碼就被確定了。

第六十頁，共69頁。9.6循環(huán)碼因此，循環(huán)碼的生成矩陣G可以寫成

第六十一頁，共69頁。9.6循環(huán)碼如何尋找任一(n,k)循環(huán)碼的生成多項式

由上式可知，任一循環(huán)碼多項式T(x)都是g(x)的倍式，故它可以寫成

T(x)=h(x)g(x) 而生成多項式g(x)本身也是一個碼組，即有

T

(x)=g(x) 由于碼組T

(x)是一個(n

–

k)次多項式，故xkT

(x)是一個n次多項式。由下式

第