通信原理-第十一章-差錯控制編碼

11.1概述

11.2糾錯編碼的基本原理

11.4簡單的實用編碼

11.5線性分組碼

11.6循環(huán)碼

11.7卷積碼

第十一章差錯控制編碼本章內容簡介11.1概述一.差錯的產生二.差錯控制方法噪聲與干擾■

檢錯重發(fā)法■

前向糾錯法■

反饋校驗法隨機噪聲與干擾突發(fā)噪聲與干擾混合噪聲與干擾隨機信道突發(fā)信道混合信道噪聲與干擾是通信出現(xiàn)差錯的基本原因。不同的噪聲與干擾信道，應采用不同的差錯控制策略。檢錯重發(fā)法：雙向信道工作。接收信息方具有檢錯能力，收到信息無誤，回發(fā)肯定應答；有誤則不發(fā)應答或發(fā)否定應答。前向糾錯法：單向信道工作。接收信息方具有糾錯能力，發(fā)現(xiàn)收到信息有誤時，確定誤碼的位置并按規(guī)則予以糾正。反饋校驗法：雙向信道工作。接收信息方簡單地將收到信息回傳給發(fā)送方，由發(fā)送方判斷前次發(fā)送是否無誤。第十一章差錯控制編碼11.1概述三.

自動要求重發(fā)(ARQ)系統(tǒng)第十一章差錯控制編碼接收碼組ACKACKNAKACKACKNAKACKt1233455發(fā)送碼組12334556t有錯碼組有錯碼組數據按分組發(fā)送。每發(fā)送一組數據后發(fā)送端等待接收端的確認(ACK)答復，然后再發(fā)送下一組數據。圖中的第3組接收數據有誤，接收端發(fā)回一個否認(NAK)答復。這時，發(fā)送端將重發(fā)第3組數據。系統(tǒng)是工作在半雙工狀態(tài)，時間沒有得到充分利用，傳輸效率較低。停止等待ARQ系統(tǒng)11.1概述三.

自動要求重發(fā)(ARQ)系統(tǒng)第十一章差錯控制編碼拉后ARQ系統(tǒng)接收數據有錯碼組有錯碼組91011101112214365798576ACK1NAK5NAK9ACK5發(fā)送數據57695214367981011101112重發(fā)碼組重發(fā)碼組發(fā)送端連續(xù)發(fā)送數據組，接收端對于每個接收到的數據組都發(fā)回確認(ACK)或否認(NAK)答復。例如，圖中第5組接收數據有誤，則在發(fā)送端收到第5組接收的否認答復后，從第5組開始重發(fā)數據組。在這種系統(tǒng)中需要對發(fā)送的數據組和答復進行編號，以便識別。顯然，這種系統(tǒng)需要雙工信道。11.1概述三.

自動要求重發(fā)(ARQ)系統(tǒng)第十一章差錯控制編碼選擇重發(fā)ARQ系統(tǒng)接收數據有錯碼組有錯碼組921436575981011131412發(fā)送數據995852143671011131412重發(fā)碼組重發(fā)碼組NAK9ACK1NAK5ACK5ACK9它只重發(fā)出錯的數據組，因此進一步提高了傳輸效率。11.1概述三.

自動要求重發(fā)(ARQ)系統(tǒng)圖11-1典型ARQ系統(tǒng)組成框圖

發(fā)送信源終端接收信宿終端編碼器、緩沖存儲重發(fā)控制解碼器指令產生輸出緩存雙向信道正確輸出錯誤刪除■ARQ系統(tǒng)主要優(yōu)點:1.

只需少量多余碼元；

2.適應不同差錯特性；

3.檢錯方法簡單。■ARQ系統(tǒng)主要缺點:1.

需要雙向信道；

2.出錯率高時，重發(fā)降低信道效率；

3.信息傳輸實時性差。第十一章差錯控制編碼11.1概述四.差錯控制編碼在信息碼元序列中加入一定數目的監(jiān)督碼元就稱為差錯控制編碼?！霾铄e控制編碼的檢糾錯能力■差錯控制編碼的編碼效率（碼率）一般說來，差錯控制編碼的檢糾錯能力取決于：●在信息碼元序列中加入的監(jiān)督碼元的多少。對于一定長度的信息碼元序列,加入的監(jiān)督碼元越多，檢糾錯能力越強?！癫煌木幋a規(guī)則與方法（有不同的檢錯或糾錯能力）。在一定長度信息碼元序列中加入監(jiān)督碼元的數目越多,差錯控制編碼的編碼效率越低。如信息碼長為k，監(jiān)督碼長為r,則編碼效率為k/(k+r)=k/n。監(jiān)督碼元數r和信息碼元數k之比r/k

=(n-k)/k

稱為冗余度。第十一章差錯控制編碼11.2糾錯編碼的基本原理第十一章差錯控制編碼

分組碼基本原理：舉例說明如下。設有一種由3位二進制數字構成的碼組，它共有8種不同的可能組合。若將其全部用來表示天氣，則可以表示8種不同天氣， 例如：“000”（晴），“001”（云）， “010”（陰），“011”（雨）， “100”（雪），“101”（霜）， “110”（霧），“111”（雹）。其中任一碼組在傳輸中若發(fā)生一個或多個錯碼，則將變成另一個信息碼組。這時，接收端將無法發(fā)現(xiàn)錯誤。11.2糾錯編碼的基本原理第十一章差錯控制編碼若在上述8種碼組中只準許使用4種來傳送天氣，例如：“000”＝晴“011”＝云“101”＝陰“110”＝雨這時，雖然只能傳送4種不同的天氣，但是接收端卻有可能發(fā)現(xiàn)碼組中的一個錯碼。例如，若“000”（晴）中錯了一位，則接收碼組將變成“100”或“010”或“001”。這3種碼組都是不準使用的，稱為禁用碼組。接收端在收到禁用碼組時，就認為發(fā)現(xiàn)了錯碼。當發(fā)生3個錯碼時，“000”變成了“111”，它也是禁用碼組，故這種編碼也能檢測3個錯碼。但是這種碼不能發(fā)現(xiàn)一個碼組中的兩個錯碼，因為發(fā)生兩個錯碼后產生的是許用碼組。11.2糾錯編碼的基本原理第十一章差錯控制編碼檢錯和糾錯上面這種編碼只能檢測錯碼，不能糾正錯碼。例如，當接收碼組為禁用碼組“100”時，接收端將無法判斷是哪一位碼發(fā)生了錯誤，因為晴、陰、雨三者錯了一位都可以變成“100”。要能夠糾正錯誤，還要增加多余度。例如，若規(guī)定許用碼組只有兩個：“000”（晴），“111”（雨），其他都是禁用碼組，則能夠檢測兩個以下錯碼，或能夠糾正一個錯碼。例如，當收到禁用碼組“100”時，若當作僅有一個錯碼，則可以判斷此錯碼發(fā)生在“1”位，從而糾正為“000”（晴）。因為“111”（雨）發(fā)生任何一位錯碼時都不會變成“100”這種形式。但是，這時若假定錯碼數不超過兩個，則存在兩種可能性：“000”錯一位和“111”錯兩位都可能變成“100”，因而只能檢測出存在錯碼而無法糾正錯碼。11.2糾錯編碼的基本原理表11-1差錯控制編碼舉例

消息信息位監(jiān)督位晴000

云011

陰101

雨110兩位信息位后加入一個監(jiān)督位,使每碼組中“1”的個數為偶數,能夠檢測出碼組中所有單數個誤碼。為每組信息碼后附加若干個監(jiān)督位構成的碼組集合,稱為分組碼。分組碼用符號(n,k)表示,k是信息位的數目,n是碼組總長度,n-k=r是監(jiān)督位數目。an-1an-2……ar

ar-1……a1a0k個信息位r個監(jiān)督位碼組總長度n=k+r圖11-2(n,k)分組碼的結構第十一章差錯控制編碼11.2糾錯編碼的基本原理■

碼重與碼距概念●

一條碼組中“1”的個數稱為該碼組的碼重?！?/p>

兩碼組中不同位的數目稱為該兩碼組的碼距?！?/p>

最小碼重與最小碼距●

某碼組集合中含“1”個數最少的碼組的碼重,稱該碼組集合的最小碼重?！衲炒a組集合中不同位數最少的兩碼組的碼距,稱該碼組集合的最小碼距。碼組集合①1001001②0011011③1011100④0111011⑤0100011⑥1000100碼重w=3w=4w=4w=5w=3w=2最小碼重w0=2碼重與碼距概念舉例碼距d12=3d13=3d14=4d15=3d16=3┇d24=1┇最小碼距d0=1第十一章差錯控制編碼11.2糾錯編碼的基本原理■

碼距(漢明Hamming距離)概念圖11-3碼距的幾何意義a0a1a2(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)■

如果使用全部8個三位的碼組分別表示8種不同信息，由于最小碼距d0=1,說明某碼組的任何一位錯誤，都可能變?yōu)槠渌戏ùa組,無檢錯或糾錯能力?！?/p>

如果使用其中4個三位的碼組分別表示4種不同信息，由于最小碼距d0=2,說明某碼組的任何一位錯誤，都不可能變?yōu)槠渌戏ùa組,能夠檢測出單個誤碼。最小碼距d0

是衡量差錯控制編碼系統(tǒng)檢錯及糾錯能力的決定性參數。第十一章差錯控制編碼11.2糾錯編碼的基本原理■

最小碼距d0與檢錯糾錯能力關系（1）只檢模式為檢測e個誤碼，要求最小碼距

d0≧e+1(11.2-2)AB0123ed0圖11-4碼距與檢錯糾錯能力的關系（a）只檢模式第十一章差錯控制編碼11.2糾錯編碼的基本原理■

最小碼距d0與檢錯糾錯能力關系（2）只糾模式為糾正t個誤碼，要求最小碼距

d0≧2t+1(11.2-3)

圖11-4碼距與檢錯糾錯能力的關系（b）只糾模式AB0123td0t4567第十一章差錯控制編碼11.2糾錯編碼的基本原理■

最小碼距d0與檢錯糾錯能力關系（3）先糾后檢，糾檢結合模式為糾正t個誤碼,同時能檢出

e個誤碼,要求最小碼距

d0≧e+t+1(e>t)(11.2-4)

圖11-4碼距與檢錯糾錯能力的關系（c）糾檢結合模式ABtet1d0第十一章差錯控制編碼11.2糾錯編碼的基本原理■

最小碼距d0與檢錯糾錯能力關系(1)只檢模式由d0≧e+1,可知系統(tǒng)的檢錯能力：最多可檢出6位誤碼。(2)只糾模式由d0≧2t+1,可知系統(tǒng)的糾錯能力：最多可檢出3位誤碼。(3)糾檢結合模式由d0≧t+e+1(e>t),可知:?若先糾正1位誤碼，則還可以檢出5位以下的誤碼。[舉例]

某差錯控制編碼系統(tǒng)，碼組集合的最小碼距d0=7,試求該編碼系統(tǒng)的檢糾錯能力。ABe≦6t≦3t=1e≦5t=2e≦4?若先糾正2位誤碼，則還可以檢出4位以下的誤碼。第十一章差錯控制編碼11.2糾錯編碼的基本原理■差錯控制(糾錯)編碼的效用AB錯2位錯5位錯3位錯4位錯1位錯6位假設在隨機信道中發(fā)送“0”和“1”時的出錯概率相同，都等于Pe（

Pe<<1），則容易證明，在長度為n的碼組中恰好發(fā)生r個誤碼的概率為(11.2-5)例如，當碼長n=7，Pe

=10-3

時

P7(1)≈7×10-3P7(2)≈2.1×10-5P7(3)≈3.5×10-8采用差錯控制編碼,即使僅能夠檢出或糾正1—2個誤碼，也能使誤碼率降低幾個數量級。第十一章差錯控制編碼11.4常用的簡單編碼1.奇偶監(jiān)督碼■

偶監(jiān)督碼

信息位附加監(jiān)督位后，碼組中“1”的個數為偶數,即滿足

an-1⊕

an-2⊕

……⊕

a1⊕

a0=0

(11.4-1)由k=n-1個信息位an-1an-2……a1和r=1個監(jiān)督位a0構成的總長度為n=k+1的(k+1,k)分組碼?！?/p>

奇監(jiān)督碼

信息位附加監(jiān)督位后，碼組中“1”的個數為奇數,即滿足

an-1⊕

an-2⊕

……⊕

a1⊕

a0=1

(11.4-2)監(jiān)督關系式偶監(jiān)督碼由已知信息位獲得監(jiān)督位的表示式為

a0=an-1⊕

an-2⊕

……⊕

a1奇監(jiān)督碼由已知信息位獲得監(jiān)督位的表示式為

a0=an-1⊕

an-2⊕

……⊕

a1⊕1奇偶監(jiān)督碼的編碼效率η=(n-1)/n第十一章差錯控制編碼11.4常用的簡單編碼2.二維奇偶監(jiān)督碼■二維奇偶監(jiān)督碼有可能檢測出偶數個錯誤,甚至可能糾正一些錯誤。■二維奇偶監(jiān)督碼特別適合于檢測突發(fā)性錯誤。■二維奇偶監(jiān)督碼的編碼效率低于一維奇偶監(jiān)督碼。上例中，η=m(n-1)/n(m+1)二維奇偶監(jiān)督碼又稱為方陣碼。它是將上述的m條偶或奇監(jiān)督碼排成一個方陣，然后沿垂直方向加上垂直監(jiān)督位構成。a1n-1a1n-2……

a11a10a2n-1a2n-2……

a21a20amn-1amn-2……

am1am0cn-1cn-2……

c1c0信息位m×(n-1)水平監(jiān)督位m×1垂直監(jiān)督位

1×n第十一章差錯控制編碼信息位100110100101101011101110001001000010001110010101100000111.4常用的簡單編碼2.二維奇偶監(jiān)督碼

0水平監(jiān)督位垂直監(jiān)督位

0

1

1

1

0

11

0[舉例]本例中，信息位k=7×7=49位，監(jiān)督位r=7+8=15位，編碼效率η=49/(49+15)=49/64第十一章差錯控制編碼11.4常用的簡單編碼3.恒比碼(等重碼)在全部碼組集合中，每條碼組中包含“1”的數目相同。表11-2我國電傳機數字代碼字符保護電碼字符保護電碼

001101500111101011610101211001711100310110801110411010910011

恒比碼中無法清晰地將信息位與監(jiān)督位分開。因此一般只適用與傳輸電傳機或鍵盤設備輸入信息編碼。恒比碼不適合信源隨機信息的編碼。4.正反碼

正反碼中信息位數目和監(jiān)督位數目相同。當信息位中“1”為奇數時，監(jiān)督位與信息位相同;當信息位中“1”為偶數時，監(jiān)督位與信息位相反。正反碼的編碼效率η=1/2,是具有糾錯能力的編碼。詳見教材（略）第十一章差錯控制編碼11.5

線性分組碼前述的偶監(jiān)督碼，n-1個信息位附加1個監(jiān)督位，構成整個碼組中“1”的個數為偶數,唯一的監(jiān)督關系滿足

an-1⊕

an-2⊕

……⊕

a1⊕

a0=0在接收端，由收到整個碼組an-1an-2……

a1a0，計算校正子SS=an-1⊕

an-2⊕

……⊕

a1⊕

a0(11.5-1)單個校正子S的取值只有兩種可能，“0”或“1”。若S=0,表示“無錯”,S=1,表示“有錯”。無法確定誤碼的位置進行糾正。增加監(jiān)督位的數量，可以建立監(jiān)督位和信息位關系（監(jiān)督關系）的多個監(jiān)督關系式。在接收端，由收到整個碼組an-1an-2……

a1a0，計算多個校正子S1、S2、……

Sr

。組合取值有2r

種可能，一種表示“無錯”,其他2r

-1種可以用來確定誤碼的位置以進行糾正。第十一章差錯控制編碼11.5

線性分組碼若由信息位和監(jiān)督位構成的整個碼組的總長度n滿足

n≦2r

–1或2r≧n+1=k+r+1(11.5-2)則除一種狀態(tài)表示“無錯”外，校正子S1、S2、……

Sr

組合的其他2r

-1種狀態(tài),至少可以確定長度為n的碼組中，一個單個誤碼的位置。若碼組的總長度n滿足

n=

2r

–1或2r=n+1這時r個校正子組合的2r

種狀態(tài),恰好可以表示出“無錯”和n位碼組當中的1位誤碼位置。作為能夠糾正1位誤碼的一種編碼，其編碼效率是最高的,稱為漢明(Hamming)碼。能夠糾正1位誤碼的(7,4)、(15,11)、(31,26)、(63,57)、…….，其編碼效率在同碼長的編碼中都是最高的,都是漢明碼。第十一章差錯控制編碼11.5

線性分組碼現(xiàn)在通過（7,4）分組碼例子說明漢明碼的監(jiān)督關系式構造。信息位(k=4):a6a5a4a3

監(jiān)督位(r=3):a2a1a0

表11-3校正子與誤碼位置的對應關系S1S2S3

誤碼位置S1S2S3

誤碼位置

000無錯011a3001a0101a4010a1110a5100a2111a6可以看出，僅當1位誤碼位置在a2、a4、a5或a6時，校正子S1為1；否則S1為0。這意味著a2、a4、a5、a64個碼元構成偶監(jiān)督關系

S1=a6⊕

a5⊕

a4⊕

a2

(11.5-3)第十一章差錯控制編碼同理可得到關于S2、S3的偶監(jiān)督關系，有

S1=a6⊕

a5⊕

a4⊕

a2

(11.5-3)S2=a6⊕

a5⊕

a3⊕

a1

(11.5-4)S3=a6⊕

a4⊕

a3⊕

a0

(11.5-5)11.5

線性分組碼表11-3校正子與誤碼位置的對應關系S1S2S3

誤碼位置S1S2S3

誤碼位置

000無錯011a3001a0101a4010a1110a5100a2111a6編碼時，給信息位加入監(jiān)督位應使得S1=S2=

S3=0，即滿足

a6⊕

a5⊕

a4⊕

a2

=0

a6⊕

a5⊕

a3⊕

a1

=0(11.5-6)

a6⊕

a4⊕

a3⊕

a0

=0第十一章差錯控制編碼11.5

線性分組碼由監(jiān)督關系式（方程組）

a6⊕

a5⊕

a4⊕

a2

=0

a6⊕

a5⊕

a3⊕

a1

=0(11.5-6)

a6⊕

a4⊕

a3⊕

a0

=0整理可得到已知信息位求監(jiān)督位的關系式

a2

=a6⊕

a5⊕

a4a1

=a6⊕

a5⊕

a3(11.5-7)a0

=a6⊕

a4⊕

a3對于信息位k=4情況，共有24=16種信息碼組合，由式(11.5-7)求出每種信息組合所附加的監(jiān)督位，進而得到全部24=16條完整碼組，如表11-4所示（教材P337）。第十一章差錯控制編碼例如：接收到碼組“0000011”,該碼組確實是表11-4中某碼組傳輸中產生了1位誤碼所致。由式(11.5-3)、(11.5-4)和(11.5-5)分別計算3個校正子，有

S1=a6⊕

a5⊕

a4⊕

a2=0

⊕0

⊕0

⊕0=0S2=a6⊕

a5⊕

a3⊕

a1=0

⊕0

⊕0

⊕1=1S3=a6⊕

a4⊕

a3⊕

a0=0

⊕0

⊕0

⊕1=1根據表11-3校正子與誤碼位置對應關系，可以確定1位誤碼的位置在a3處，正確的碼組應該為“0001011”，它就是表11-4中的第2條碼組。11.5

線性分組碼

表11-3校正子與誤碼位置對應關系S1S2S3

誤碼位置S1S2S3

誤碼位置

000無錯011a3001a0101a4010a1110a5100a2111a6如果1條碼組在傳輸過程中確實產生了1位錯誤，前述的(7,4)漢明碼就能無誤地指出誤碼位置以進行糾正。第十一章差錯控制編碼11.5

線性分組碼從表11-4(7,4)漢明碼的全部碼組可以看到，這種碼的最小碼距(數值上和非全零碼的最小碼重相等)d0=3，用于檢錯可檢測出e=2

位以下的誤碼，用于糾錯只可糾正t=1

位誤碼。這種碼的編碼效率η=k/n=4/7。漢明碼能夠糾正1位誤碼，其編碼效率在同碼長的編碼中是最高的。具有1位誤碼糾正能力的(7,4)、(15,11)、(31,26)、(63,57)、…….都是漢明碼。漢明碼的編碼效率隨著碼組總長n的增加而增加。因為碼組越長，信息位所占比例越大，監(jiān)督位所占比例越小。

當碼長n很大時，編碼效率接近于1。漢明碼2r=n+1第十一章差錯控制編碼11.5

線性分組碼改寫監(jiān)督關系式（方程組）

a6⊕

a5⊕

a4⊕

a2

=0

a6⊕

a5⊕

a3⊕

a1

=0(11.5-6)

a6⊕

a4⊕

a3⊕

a0

=0為

1·a6+

1·a5+

1·a4+

0·a3+

1·a2

+

0·a1+

0·a0=01·a6+

1·a5+

0·a4+

1·a3+

0·a2

+1·a1+

0·a0=0

(11.5-8)1·a6+

0·a5+

1·a4+

1·a3+

0·a2

+0·a1+

1·a0

=0為簡化將“⊕”改寫為“+”,均表示模2加。并可表示為矩陣形式

111010011010101011001a6a5a4a3a2

a1a0000(11.5-9)簡記為H?AT=OT

或A

?HT=O(11.5-10)r×n監(jiān)督矩陣[a6a5a4a3a2

a1a0]1×n碼組向量[

000]1×r零向量第十一章差錯控制編碼11.5

線性分組碼式(11.5-9)中的監(jiān)督矩陣是一個

r行×n列的矩陣，內容可以分為兩部分其中P為

r×k階矩陣，Ir為

r×r

階單位矩陣。具有[P┊Ir]形式的監(jiān)督矩陣稱為典型監(jiān)督矩陣。(11.5-11)111010011010101011001P┊Ir

H111010011010101011001式(11.5-7)改寫可得到已知信息位a6a5a4a3求監(jiān)督位a2

a1a0的矩陣關系式a2

a1a0111011011011a6

a5a4a3或(11.5-12)(11.5-13)a2a1a0a6a5a4a3111110101011Pr×k

Qk×r其Q為

k×r

階,它是P的轉置矩陣Q=PT

(11.5-14)第十一章差錯控制編碼11.5

線性分組碼對已知信息位a6a5a4a3求監(jiān)督位a2

a1a0的關系(11.5-7)擴充，變?yōu)橐阎畔⑽籥6a5a4a3求整個碼組a6a5a4a3a2

a1a0的關系式a2=a6⊕

a5⊕

a4a1=a6⊕

a5⊕

a3a0=a6⊕

a4⊕

a3a6=a6a5=a5a4=a4a3

=

a3矩陣形式a6

a5a4a3a6

a5a4a3a2

a1a01000010000100001111011011011簡記為A=[a6a5a4a3]·G(11.5-17)G10001110100110001010100010111000111010011000101010001011Ik┊Q(11.5-15)GTk×k

階單位矩陣Ikk×r階矩陣Q典型生成矩陣生成矩陣第十一章差錯控制編碼11.5

線性分組碼●線性分組碼具有封閉性。它是指一種線性分組碼的任意兩條合法碼組相異或，得到的結果仍然是該線性分組碼的一條合法碼組?！鼍€性分組碼的兩個重要性質●線性分組碼的最小碼重（全零碼除外），就是該線性分組碼的最小碼距。這是因為，任一碼組中“1”的個數（碼重），都是某兩條碼組不相同位的數目（碼距）。性質1（線性分組碼的封閉性）給我們提供了利用某些已知碼組獲得一些未知碼組的一條可能的途徑。性質2（最小碼距=最小碼重）給我們提供了從碼組獲得最小碼距，并判斷檢錯糾錯能力的便捷方法。第十一章差錯控制編碼11.6

循環(huán)碼

循環(huán)碼是一種簡單、重要、常用的線性分組碼。除了具有線性分組碼的一般性質外，還具有循環(huán)性，即碼組集合中任一碼組循環(huán)左移或右移若干位，得到的結果仍然為該碼組集合中的一條合法碼組。11.6.1循環(huán)碼原理表11-6(7,3)循環(huán)碼舉例碼組信息位監(jiān)督位編號a6a5a4a3a2

a1a0

1000000020010111301011104011100151001011610111007110010181110010循環(huán)m位循環(huán)左移3位循環(huán)左移2位本例中，只要知道一條非全零碼組,通過移位就可求出全部碼組。循環(huán)右移3位第十一章差錯控制編碼11.6

循環(huán)碼

■

碼的多項式表示

對于碼組an-1an-2……

a1a0，若將各碼元作為多項式系數，則可得到碼組的多項式表示

T(x)=an-1xn-1+

an-2xn-2+

……+

a1x

+

a0(11.6-1)對于前例的(7,3)碼,任一碼組都可表示為

T(x)=a6x6+

a5x5+a4x4+a3x3+a2x2+

a1x

+

a0(11.6-2)而其中的第7條碼組“1100101”可表示為多項式

T7(x)=x6+

x5+x2+1(11.6-3)11.6.1循環(huán)碼原理對于碼長為n的碼組，碼多項式的最高次數為xn-1。多項式系數取值是模2的，即只能是“1”或“0”。第十一章差錯控制編碼11.6

循環(huán)碼11.6.1循環(huán)碼原理1.碼多項式的按模運算

■如整數的按模運算

對整數m按模n運算,將整數m除以整數n,商為整數Q,余數為p(p<n),即我們說整數m按模n運算之結果為

m≡p(模n)(11.6-4)(11.6-5)

■多項式的按模運算

對任意多項式F(x)被另一個n次多項式N(x)除，得到一商式Q(x)和一個次數小于n的余式R(x),即

F(x)=N(x)Q(x)+R(x)我們說多項式F(x)按模N(x)運算之結果為

F(x)

≡R(x)

(模N(x))(11.6-6)(11.6-7)第十一章差錯控制編碼11.6

循環(huán)碼11.6.1循環(huán)碼原理1.碼多項式的按模運算

■多項式的按模運算[例]●x3按模(x3+1)運算，結果為

x3

≡1(模x3+1)●x4+x2+1按模(x3+1)運算，結果為

x4+x2+1

≡x2+x

+1

(模x3+1)(11.6-6)(11.6-7)x3+1x4+x2+1xx4+xx2+x

+1注意:多項式系數是模2的,取值只能是“1”或“0”,這也是余式為x2+x

+1,而不為x2-x

+1

的原因。重要結論:在循環(huán)碼中，若T(x)是一個長度為n的碼組，則xi

T(x)

在按模xn+1運算下，也是該循環(huán)碼的一個許用碼組。第十一章差錯控制編碼11.6

循環(huán)碼11.6.1循環(huán)碼原理1.碼多項式的按模運算重要結論:在循環(huán)碼中，若T(x)是一個長度為n的碼組，則xi

T(x)

在按模xn+1運算下，也是該循環(huán)碼的一個許用碼組。證明詳見教材。[舉例]

T(x)=x4+x2+x+1

是一個長度為7

的合法碼組,可以證明

T′(x)=x3T(x)=x7+x5+x4+

x3

按模x7+1運算,其結果為

T′(x)≡x5+x4+

x3

+1

也是一個長度為7

的合法碼組。表11-6(7,3)循環(huán)碼舉例碼組信息位監(jiān)督位編號a6a5a4a3a2

a1a0

1000000020010111301011104011100151001011610111007110010181110010第十一章差錯控制編碼11.6

循環(huán)碼11.6.1循環(huán)碼原理2.循環(huán)碼生成矩陣和生成多項式生成矩陣G用于由給定信息位生成完整碼組，它由k行n列構成，其每一行都是彼此線性無關的合法碼組。在循環(huán)碼中,一個(n,k)碼有2k種不同碼組?，F(xiàn)用g(x)表示前(k-1)位皆為“0”的碼組,則g(x)、xg(x)、x2g(x)、…、xk-1g(x)是k個彼此線性無關的合法碼組,可用來構成循環(huán)碼的生成矩陣G(x)g(x)xg(x)xk-1g(x)xk-2g(x)(11.6-15)可以證明,除全零碼外,g(x)前(k-1)位皆為“0”是唯一前面連續(xù)“0”最多的碼組,且常數項一定為“1”,否則經若干次循環(huán)移位后會得到一個信息位全零的“非全零”碼組，而這是不可能的。第十一章差錯控制編碼11.6

循環(huán)碼11.6.1循環(huán)碼原理2.循環(huán)碼生成矩陣和生成多項式表11-6(7,3)循環(huán)碼舉例碼組信息位監(jiān)督位編號a6a5a4a3a2

a1a0

1000000020010111301011104011100151001011610111007110010181110010[舉例]g(x)

對應前(k-1)位皆為“0”是唯一前面連續(xù)“0”最多的碼組,因此，除全零碼外，g(x)是一個次數最低的碼多項式。是一個常數項不為零的(n-k)次多項式。g(x)=x4+x2+x+1

G(x)g(x)xg(x)x2g(x)(11.6-16)G001011101011101011100(11.6-17)非典型陣典型化線性變換G001011101011101001011典型陣G=[Ik┊Q]第十一章差錯控制編碼11.6

循環(huán)碼11.6.1循環(huán)碼原理3.如何尋找(n,k)碼的生成多項式生成多項式g(x)

是循環(huán)碼的最關鍵因素。由它可容易地獲得生成矩陣G,并根據信息位產生全部碼組。下面研究的g(x)獲得方法?！?/p>

由(n,k)循環(huán)碼的全部條碼組尋找g(x)

(7,4)循環(huán)碼舉例碼組信息位監(jiān)督位編號a6a5a4a3a2

a1a0

10000000

20001011

30010110

40011101

50100111

60101100

70110001

80111010碼組信息位監(jiān)督位編號a6a5a4a3a2

a1a0

91000101

101001110

111010011

121011000

131100010

141101001

151110100

161111111前(k-1)位皆為“0”的碼組，也是信息位為“0…01”的碼組。g(x)=x3+x+11011000010110000101100001011G=第十一章差錯控制編碼11.6

循環(huán)碼11.6.1循環(huán)碼原理3.如何尋找(n,k)碼的生成多項式■

由(n,k)循環(huán)碼的部分碼組尋找g(x)1011000010110000101100001011G=

(7,4)循環(huán)碼舉例碼組信息位監(jiān)督位編號a6a5a4a3a2

a1a0

10000000

┇┇00111010100111010110001100010111010┇┇161111111循環(huán)左移3位，得到前(k-1)=3位皆為“0”的碼組“0001011”，對應

g(x)=x3+x+1線性變換典型化1000101010011100101100001011G=1000101010011100101100001011Ik┊Q第十一章差錯控制編碼11.6

循環(huán)碼11.6.1循環(huán)碼原理3.如何尋找(n,k)碼的生成多項式■

由(n,k)循環(huán)碼的部分碼組尋找g(x)

(7,4)循環(huán)碼舉例碼組信息位監(jiān)督位編號a6a5a4a3a2

a1a0

10000000

┇┇001110101001111010011

┇

┇0111010┇┇161111111兩條碼組模2加后，循環(huán)左移1位，得到前(k-1)=3位皆為“0”的碼組“0001011”，對應g(x)=x3+x+1如何尋找g(x)

？第十一章差錯控制編碼1011000010110000101100001011G=線性變換典型化1000101010011100101100001011G=1000101010011100101100001011Ik┊Q11.6

循環(huán)碼11.6.1循環(huán)碼原理3.如何尋找(n,k)碼的生成多項式■

無已知條件下，求(n,k)循環(huán)碼的g(x)如何尋找g(x)

？可以證明(見教材)，生成多項式g(x)

是(xn

+1)的一個因式。上述結論告訴我們，可以通過對(xn

+1)分解因式獲得g(x)

。(xn

+1)的因式可能有多個，只有那些常數項不為零的n-k次因式才可作為(n,k)循環(huán)碼的生成多項式g(x)

。例如：為獲得(7,4)循環(huán)碼的生成多項式g(x)

，分解(x7+1)得

(x7+1)=(x+1)(x3+x2

+1)(x3+x+1)g1(x)和g2(x)都可作為(7,4)循環(huán)碼的生成多項式。g1(x)g2(x)(11.6-24)同理,(7,3)循環(huán)碼的生成多項式也是分解(x7+1)所得

g2(x)=x4+x3

+x2+

1(11.6-26)g1(x)=x4+x2

+x+

1(11.6-25)(x+1)(x3+x2

+1)(x+1)(x3+x+1)第十一章差錯控制編碼11.6

循環(huán)碼11.6.2循環(huán)碼的編解碼方法■編碼步驟(1)用信息碼多項式m(x)乘以xn-k

，該運算相當于給信息碼后加(n-k)個“0”。例如，信息碼為“110”,相當于m(x)=x2+x

。當n-k=7-3=4時，xn-k

m(x)=x4(x2+x)=x6+x5，相當于“1100000”。(2)用xn-k

m(x)除以g(x),得到商Q(x)和余式r(x),既

xn-k

m(x)=g(x)Q(x)+R(x)(11.6-27)

若取g(x)=x4+x2+x+1

，對于上例可得相當于

110000010111

10110111=111+(11.6-28)(11.6-29)第十一章差錯控制編碼11.6

循環(huán)碼11.6.2循環(huán)碼的編解碼方法■編碼步驟(3)編出碼組T(x)為

T(x)=xn-k

m(x)+r(x)(11.6-30)

在上例中

T(x)=1100000+101=1100101

正是表11-6中第7條碼組。

a

b

c

d⊕⊕⊕

S

e

f

m信息碼輸入編碼輸出圖11-6(7,3)循環(huán)碼編碼器第十一章差錯控制編碼11.6

循環(huán)碼11.6.2循環(huán)碼的編解碼方法■解碼步驟(1)用接收碼組R(x)=T(x)+E(x)除以生成多項式g(x),得到余式r(x)。(2)根據余式r(x)用查表方法或運算得到錯誤圖樣E(x),就可確定誤碼位置。(3)從R(x)中減去E(x),就可得到已經糾正錯誤的原始發(fā)送碼組T(x)。解碼信息輸出圖11-7b(7,3)循環(huán)碼糾錯解碼器⊕

a

b

c

d⊕⊕⊕

與門⊕

緩沖移位寄存器接收編碼輸入第十一章差錯控制編碼11.6

循環(huán)碼11.6.3縮短循環(huán)碼研究表明，并不是任意碼組長度n

和信息位k都可以找到滿足某糾錯能力的循環(huán)碼。但若將某已知循環(huán)碼縮短，就可能滿足碼長n

、信息位長度k和糾錯能力要求。給定已知(n,k)循環(huán)碼集合，使前i(0<i<k)個高階信息位數字全為“0”,于是得到有2k-i個碼組的集合,然后從這些碼組中刪去這i個零信息位數字，最終得到一組新的(n-i,k-i)線性分組碼，就是縮短循環(huán)碼。例如，若欲構造具有1位誤碼糾正能力的(13,9)碼，則可以由(15,11)漢明碼的全部211條碼組中，挑選出前兩位皆為“0”的碼組29

，構成一個新的碼組集合。而在傳輸時，兩個零信息位不發(fā)送，即發(fā)送的是(13,9)縮短循環(huán)碼。縮短循環(huán)碼和原始循環(huán)碼相比，縮短的是信息位，監(jiān)督位并沒減少，因此檢錯糾錯能力不會減少。第十一章差錯控制編碼11.6

循環(huán)碼11.6.4BCH(Bose-Chaudhuri-Hocguenghem)碼在系統(tǒng)設計中，通常是在給定糾正隨機誤碼的個數條件下尋找碼生成多項式g(x)，從而得到滿足一定抗干擾性能要求的編碼。BCH碼就是為解決這一問題研究發(fā)展起來的一類糾正多個隨機錯誤的循環(huán)碼。■

本原BCH碼本原BCH碼的碼長為n=2m-1(m是大于或等于3的整數),其生成多項式g(x)中含有最高次數為m次的本原多項式?！?/p>

非本原BCH碼本原BCH碼的碼長n為(2m-1)的一個因子，其生成多項式g(x)中不含有最高次數為m次的本原多項式?？梢宰C明：

對于正整數m(m≧3)和t(t<m/2),必存在“碼長n=2m-1，監(jiān)督位數目r

≦

mt,能夠糾正不大于t

個的隨機誤碼”的BCH碼。第十一章差錯控制編碼11.6

循環(huán)碼11.6.4BCH(Bose-Chaudhuri-Hocguenghem)碼表11-8二進制本原BCH碼參數——

n、k、t、g(x)n

k

t

g(x)n

k

t

g(x)41136357110313775121247111123453170131772721394166623567532467365103350042317777773061574641653472614524717323260404441212355118101363026512351725163107657115542332512712012116731336504711324156711517777777777多項式系數(八進制)111010001g(x)=x8+x7+x6+x4+1第十一章差錯控制編碼11.6

循環(huán)碼11.6.4BCH(Bose-Chaudhuri-Hocguenghem)碼11.6

循環(huán)碼11.6.5里德-索洛蒙(Reed-Solomon)碼見講義（略）表11-9部分非本原BCH碼參數nktg(x)17927272112216632312353433322251454121466471334724543073357655321076165404354300067734641717773537多項式系數(八進制)101001100101g(x)=x11+x9+x6+x5+x2+1255=17×152047=23×89第十一章差錯控制編碼11.7

卷積碼(連環(huán)碼)前述的分組碼在編碼時，各長度為n的碼組進行分別編碼。即對于給定的k個信息位，附加上僅僅與這k個信息位有關的r個監(jiān)督位，形成長度為n的碼組。各個碼組之間沒有任何約束關系，因此在譯碼時各個碼組也是分別獨立地進行。卷積碼在編碼時，長度為n的碼組由k個信息位附加上r個監(jiān)督位，形成長度為n的碼組。但是這r個監(jiān)督位不僅僅與當前的k個信息位有關，還和前面的(N-1)個碼組中的信息位有關。這樣若干個(N)碼組形成一種約束關系。卷積碼的約束長度:以碼組為單位時為N,以碼元為單位時為nN

。碼組長度為n,信息位組長度為k,約束長度為N個碼組的卷積碼記為(n,k,N)卷積碼,卷積碼的編碼效率為Rc=k/n。第十一章差錯控制編碼11.7

卷積碼11.7.1

卷積碼的圖形表示M3M2M1⊕⊕輸入序列m1,m2,…,mj

,…輸出序列m1y21y31,m2y22y32,…圖