CH13-差錯(cuò)控制和信道編碼

－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－通信原理程琳蘭州大學(xué)信息科學(xué)與工程學(xué)院M.P: +86-013993113069Email:chenglin@

or

chenglinwtt@Address：DepartmentofElectronics&InformationScience,SchoolofInformationScience&Engineering,LanzhouUniversity,TianshuiSouthernRoad222#，GansuProvince，P.R.ChinaPrinciplesofCommunications*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－2

第十三章差錯(cuò)控制和信道編碼主要內(nèi)容提要：

》差錯(cuò)控制方式及信道編碼的基本概念

》線性分組碼

》循環(huán)碼

》卷積碼

》其它信道編碼簡(jiǎn)介*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－3

本章的教學(xué)基本要求

本章要求掌握差錯(cuò)控制的基本方式、信道編碼的一些基本概念、線性分組碼特性及其設(shè)計(jì)、循環(huán)碼特性及其設(shè)計(jì)、卷積碼特性及其設(shè)計(jì)；其余的內(nèi)容可根據(jù)學(xué)時(shí)情況酌情加以了解即可。*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－4

在實(shí)際信道上傳輸數(shù)字信號(hào)時(shí)，由于信道傳輸特性不理想以及加性噪聲的影響，接收端所收到的數(shù)字信號(hào)不可避免地會(huì)發(fā)生錯(cuò)誤。產(chǎn)生差錯(cuò)的原因信道的電氣特性引起信號(hào)幅度、頻率、相位的畸變；信號(hào)反射；串?dāng)_；閃電、大功率電機(jī)的啟停產(chǎn)生脈沖干擾等。一般說(shuō)來(lái)，線路傳輸差錯(cuò)是不可避免的，但要盡量減小其影響?！?.引言*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－5

§1.引言信道差錯(cuò)的幾種模式隨機(jī)差錯(cuò)：差錯(cuò)的出現(xiàn)是隨機(jī)的，一般而言差錯(cuò)出現(xiàn)的位置是隨機(jī)分布的。這種情況一般是由信道的加性隨機(jī)噪聲引起的。一般將這種信道稱為隨機(jī)信道。突發(fā)差錯(cuò)：差錯(cuò)的出現(xiàn)是一連串出現(xiàn)的。這種情況如移動(dòng)通信中信號(hào)在某一段時(shí)間內(nèi)發(fā)生衰落，造成一串差錯(cuò)；光盤上的一條劃痕等等。這樣的信道我們稱之為突發(fā)信道?；旌喜铄e(cuò)：既有突發(fā)錯(cuò)誤又有隨機(jī)差錯(cuò)的情況。這種信道稱之為混合信道。*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－6

§1.引言降低誤碼的技術(shù)措施：》為了在已知信噪比情況下達(dá)到一定的誤比特率指標(biāo)，首先應(yīng)該合理設(shè)計(jì)基帶信號(hào)，選擇調(diào)制解調(diào)方式，采用時(shí)域/頻域均衡，使誤比特率盡可能降低。》但若誤比特率仍不能滿足要求，則必須采用信道編碼（即差錯(cuò)控制編碼），將誤比特率進(jìn)一步降低，以滿足系統(tǒng)指標(biāo)要求。隨著差錯(cuò)控制編碼理論的完善和數(shù)字電路技術(shù)的發(fā)展，信道編碼已經(jīng)成功地應(yīng)用于各種通信系統(tǒng)中，并且在計(jì)算機(jī)、磁記錄與存儲(chǔ)中也得到日益廣泛的應(yīng)用。*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－7

§1.引言我們研究的是編碼和譯碼，所以完全可以將調(diào)制、解調(diào)與信道合起來(lái)等效成一個(gè)等效信道——編碼信道。編碼信道根據(jù)調(diào)制解調(diào)的不同輸入和輸出具有不同的類型離散無(wú)記憶對(duì)稱二進(jìn)制輸入二進(jìn)制輸出信道（BSC）離散無(wú)記憶二進(jìn)制輸入多進(jìn)制輸出信道離散無(wú)記憶多進(jìn)制輸入多進(jìn)制輸出離散無(wú)記憶二進(jìn)制輸入連續(xù)輸出離散有記憶信道編碼信道信源編碼調(diào)制信道解調(diào)譯碼信宿*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－8

§1.引言信道編碼的目的：改善數(shù)字通信系統(tǒng)的傳輸質(zhì)量信道編碼(差錯(cuò)控制編碼)的基本思路：在發(fā)送端將被傳輸?shù)男畔⒏缴弦恍┍O(jiān)督碼元，這些冗余的碼元與信息碼元之間以某種確定的規(guī)則相互關(guān)聯(lián)（約束）。接收端按照既定的規(guī)則校驗(yàn)信息碼元與監(jiān)督碼元之間的關(guān)系，一旦傳輸發(fā)生差錯(cuò)，則信息碼元與監(jiān)督碼元的關(guān)系就受到破壞，從而接收端可以發(fā)現(xiàn)錯(cuò)誤乃至糾正錯(cuò)誤。信道編碼的任務(wù)：構(gòu)造出以最小多余度（冗余度）代價(jià)換取最大抗干擾性能的“好碼”。研究各種編碼和譯碼方法是信道編碼所要解決的主要問(wèn)題。

*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－9

信道編碼與信源編碼的區(qū)別信源編碼盡量減少信源的冗余度。即盡可能用最少的信息比特來(lái)表示信源。如話音壓縮編碼、圖象壓縮編碼。信道編碼在待傳輸信息中加入冗余信息，以此達(dá)到差錯(cuò)控制的目的，從而提高通信系統(tǒng)的可靠性。如糾錯(cuò)編碼、檢錯(cuò)重發(fā)編碼等*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－10

§2.差錯(cuò)控制方式及信道編碼的基本概念一、差錯(cuò)控制的三種方式：檢錯(cuò)重發(fā)（ARQ：AutomaticRepeatRequest

）在接收端根據(jù)編碼規(guī)則進(jìn)行檢查，如果發(fā)現(xiàn)規(guī)則被破壞，則通過(guò)反向信道要求發(fā)送端重新發(fā)送，直到接收端檢查無(wú)誤為止。ARQ系統(tǒng)需要反饋信道，效率較低，但是能達(dá)到很好的性能。前向糾錯(cuò)（FEC：ForwardErrorCorrection

）

發(fā)送端發(fā)送能糾正錯(cuò)誤的編碼，在接收端根據(jù)接收到的碼和編碼規(guī)則，能自動(dòng)糾正傳輸中的錯(cuò)誤。不需要反饋信道，實(shí)時(shí)性好，但是隨著糾錯(cuò)能力的提高，編譯碼設(shè)備復(fù)雜。混合方式（HEC：HybridErrorCorrection

）結(jié)合前向糾錯(cuò)FEC和ARQ的系統(tǒng)，在糾錯(cuò)能力范圍內(nèi)，自動(dòng)糾正錯(cuò)誤，超出糾錯(cuò)范圍則要求發(fā)送端重新發(fā)送。它是一種折中的方案。*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－11

差錯(cuò)控制的三種方式檢錯(cuò)重發(fā)（ARQ：Automatic

RepeatRequest

）前向糾錯(cuò)（FEC：ForwardErrorCorrection

）混合方式（HEC：Hybrid

ErrorCorrection

）發(fā)送接收可檢錯(cuò)的碼序列應(yīng)答信號(hào)發(fā)送接收可檢錯(cuò)和糾錯(cuò)的碼序列發(fā)送接收可檢錯(cuò)和糾錯(cuò)的碼序列應(yīng)答信號(hào)*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－12

差錯(cuò)控制的三種方式之ARQ檢錯(cuò)重發(fā)ARQ系統(tǒng)具有各種不同的重發(fā)機(jī)制停等ARQ發(fā)送方每發(fā)完一幀必須等接收方確認(rèn)后才能發(fā)下一幀。Go-back-NARQ(回退N)發(fā)送方可連續(xù)發(fā)送多幀。若前面某幀出錯(cuò)，從該幀以后的各幀都需重發(fā)。（一般與流控結(jié)合使用）選擇性重傳SARQ發(fā)送方可連續(xù)發(fā)送多幀。若前面某幀出錯(cuò)，只需重發(fā)該出錯(cuò)的幀。發(fā)送方需要緩存前面所有未被確認(rèn)的幀。……其它不常用的差錯(cuò)控制方式：信息反饋方式（IRQ）*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－13

差錯(cuò)控制的三種方式之ARQ停等ARQ回退N選擇性重傳碼組1ACKNAK碼組2ACK重發(fā)碼組2碼組3無(wú)錯(cuò)無(wú)錯(cuò)有錯(cuò)發(fā)送接收1234563456712345634567發(fā)現(xiàn)錯(cuò)誤NAK重發(fā)12345637891234563789發(fā)現(xiàn)錯(cuò)誤NAK重發(fā)*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－14

二、信道編碼的分類1、按功能劃分為：檢錯(cuò)碼、糾錯(cuò)碼、糾刪碼（兼檢錯(cuò)、糾錯(cuò)）2、按信息位和校驗(yàn)位的約束關(guān)系分為：線性碼、非線性碼3、按信息碼元和監(jiān)督碼元的約束關(guān)系分為：分組碼：監(jiān)督碼僅與本碼組信息碼有關(guān)卷積碼：監(jiān)督碼不僅與本碼組信息碼有關(guān)，而且與前面碼組的信息碼有關(guān)。4、按編碼后信息碼結(jié)構(gòu)是否發(fā)生變化分為：系統(tǒng)碼：編碼前后信息碼結(jié)構(gòu)不變非系統(tǒng)碼：編碼前后信息碼結(jié)構(gòu)發(fā)生改變5、按碼元的進(jìn)制進(jìn)行劃分：二進(jìn)制碼、多進(jìn)制碼：*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－15

三、信道編碼的基本概念分組碼：將k比特信息編成n比特一組的碼字（碼組），記為（n，k）分組碼。K位碼元，作為信息碼元r=n-k位碼元，稱作冗余碼、監(jiān)督碼許用碼組：禁用碼組：碼重W：碼字中1的個(gè)數(shù)。如W(11000)=2;W(010)=1

碼距d

（漢明距離Hamming）：兩碼組中對(duì)應(yīng)位不同的比特（bit）數(shù)。如C1:11000，C2:11101,則d(C1，C2)=2*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－16

信道編碼的基本概念最小碼距：分組碼(n,k)中任何兩個(gè)碼字Ci、Cj之間的碼距的最小值，用dmin表示。最小碼距是衡量碼的一種內(nèi)在屬性最小碼距決定了碼的糾錯(cuò)、檢錯(cuò)性能若要發(fā)現(xiàn)e個(gè)獨(dú)立隨機(jī)錯(cuò)誤，要求dmin≥e+1若要糾正t個(gè)獨(dú)立隨機(jī)錯(cuò)誤，要求dmin≥2t+1若要發(fā)現(xiàn)e個(gè)同時(shí)又糾正t(e>t)個(gè)獨(dú)立隨機(jī)錯(cuò)誤，要求dmin≥e+t+1e+1ee2t+1tte+t+1et*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－17

四、常用簡(jiǎn)單檢錯(cuò)碼1.奇偶監(jiān)督碼（奇偶校驗(yàn)碼）最簡(jiǎn)單的檢錯(cuò)碼(1bit校驗(yàn))，在計(jì)算機(jī)數(shù)據(jù)傳輸中得到廣泛應(yīng)用傳送信息分組(an-1,…,a1,)+監(jiān)督位(a0)=一個(gè)傳輸碼組(an-1,…,a1,a0)偶校驗(yàn)：an-1+an-2+

…+a1+a0=0(mod2)

（即偶數(shù)個(gè)1）奇校驗(yàn)：an-1+an-2+

…+a1+a0=1(mod2)

（即奇數(shù)個(gè)1）可見這種碼的最小碼距為2，只能檢出1個(gè)獨(dú)立隨機(jī)差錯(cuò)。*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－18

簡(jiǎn)單的檢錯(cuò)碼2.二維奇偶監(jiān)督碼（行列監(jiān)督碼）可檢測(cè)出任一行或任一列上所有奇數(shù)個(gè)錯(cuò)碼信息碼元水平監(jiān)督碼010110110010101010010000110000110垂直監(jiān)督碼00111111011*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－19

簡(jiǎn)單的檢錯(cuò)碼3.恒比碼

每個(gè)碼組中的1的個(gè)數(shù)都是一樣的。典型應(yīng)用：一般用在電傳、電報(bào)。例如，我國(guó)電傳機(jī)傳輸漢字時(shí)每個(gè)漢字用4位阿拉伯?dāng)?shù)字表示，每個(gè)阿拉伯?dāng)?shù)字用5個(gè)比特的碼字表示，即從32種組合選取10個(gè)為阿拉伯?dāng)?shù)字編碼阿拉伯?dāng)?shù)字編碼阿拉伯?dāng)?shù)字編碼101011610101211001711100310110801110411010910011500111001101恒比碼的編譯碼可以采用查表的方法，檢錯(cuò)時(shí)檢查1的個(gè)數(shù)是否為3*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－20

簡(jiǎn)單的檢錯(cuò)碼4.ISBN國(guó)際統(tǒng)一圖書編號(hào)（例一）在國(guó)際圖書的發(fā)行中，經(jīng)常用編碼的方式來(lái)防止書號(hào)在通信過(guò)程中發(fā)生錯(cuò)誤，舉例如下所述。如《通信原理》的書號(hào)是ISBN7-5635-0525-3其中第一位數(shù)字“7”表示“中國(guó)”，“5635”表示出版社，“0525”表示書名編號(hào)，最后一位“3”表示校驗(yàn)位。這里所采用的校驗(yàn)方式如下所示：75635052537121821262631333841719375884110141174212253(模11)≡0若通信過(guò)程中統(tǒng)一書號(hào)發(fā)生了錯(cuò)誤，則上述累計(jì)和就不能被11整除，從而可以校驗(yàn)出來(lái)。*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－21

簡(jiǎn)單的檢錯(cuò)碼4.ISBN國(guó)際統(tǒng)一圖書編號(hào)（例二）如《通信原理》的書號(hào)是ISBN7-118-0429-X其中第一位數(shù)字“7”表示“中國(guó)”，“118”表示出版社，“01429”表示書名編號(hào)，最后一位“X”表示校驗(yàn)位（它是羅馬數(shù)字10的表示）。這里所采用的校驗(yàn)方式如下所示：71180429X=1078917172123324271524415879102134176176(模11)=0。又譬如：ISBN7－03－014456－2，大家可自行分析。*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－22

§3.線性分組碼近世代數(shù)學(xué)有限域的概念：有限個(gè)元素的集合，按規(guī)定可以進(jìn)行的代數(shù)四則運(yùn)算，其運(yùn)算結(jié)果仍屬于該集合中有限的元素。最簡(jiǎn)單的有限域{0，1}——Galois域1+1=0、1+0=1、0+1=1、0+0=01x1=1、1x0=0、0x0=0、0x1=0定義線性分組碼的加法為模2加，乘法為二進(jìn)制乘法。且碼字與碼字的運(yùn)算是各個(gè)相應(yīng)比特位上的上述二進(jìn)制運(yùn)算規(guī)則。*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－23

§3.線性分組碼基本概念碼組中監(jiān)督碼與信息碼之間滿足線性方程；任意兩個(gè)可用碼組之和(逐位模2加)仍為一個(gè)可用碼組奇偶監(jiān)督碼——最簡(jiǎn)單的線性分組碼偶校驗(yàn)時(shí)奇校驗(yàn)時(shí)不滿足線性分組碼的第二個(gè)性質(zhì)。定義校正子（校驗(yàn)子伴隨式）接收時(shí)進(jìn)行校驗(yàn)計(jì)算：

S=0→無(wú)錯(cuò)；

S=1→有錯(cuò)（奇數(shù)個(gè)）*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－24

§3.線性分組碼一般情況下：如果碼組中有2個(gè)監(jiān)督碼，校正子為S=[s1,s2]可以檢測(cè)到三種誤碼狀態(tài)*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－25

§3.線性分組碼如果碼組中有r個(gè)監(jiān)督碼，假設(shè)碼組中有K個(gè)信息碼，則線性分組碼的長(zhǎng)度應(yīng)該為n=K+r。碼的結(jié)構(gòu)線性分組碼（n，k）的性質(zhì)封閉性：任意兩個(gè)碼組的和還是許用的碼組碼的最小距離等于非零碼的最小碼重K位信息位r位監(jiān)督位n位碼組*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－26

§3.線性分組碼檢錯(cuò)能力：有r個(gè)校正子方程→可以指示（2r-1）個(gè)錯(cuò)誤糾錯(cuò)能力：對(duì)1位錯(cuò)碼，可以指示（2r-1）個(gè)錯(cuò)誤位置若2r-1≥n，可以糾正1bit或以上的錯(cuò)碼，即2r-1≥r+k，2r-1-r≥k設(shè)k=4，能糾正1位誤碼的最小r=3，則n=7

（7，4）線性分組碼，碼組C=[c6c5c4c3c2c1c0]，其中c6c5c4c3為信息碼，c2c1c0為監(jiān)督碼*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－27

§3.線性分組碼一般分析，對(duì)于線性分組碼（n,k）,若可記為：（Cn-1Cn-2Cn-3

……Cn-KCr-1Cr-2Cr-3……C1C0）

現(xiàn)令信息碼元與監(jiān)督碼元的約束關(guān)系為：*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－28

§3.線性分組碼據(jù)此可得如下結(jié)果：由上式可得一致監(jiān)督關(guān)系為：*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－29

§3.線性分組碼其中的H為：*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－30

§3.線性分組碼同樣可知：*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－31

§3.線性分組碼若令下述關(guān)系成立：對(duì)比H和G，可見：*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－32

§3.線性分組碼所以可得如下結(jié)果：

這里稱H為一致監(jiān)督矩陣；G則是生成矩陣。下面研究一個(gè)實(shí)際例子。*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－33

§3.線性分組碼現(xiàn)以一個(gè)(7,3)線性分組碼為例n=7,k=3,r=n-k=4編碼效率為：R=k/n=3/7

c0=u0

c3=u0+

u2

信息位c1=u1

監(jiān)督位c4=u0+

u1+

u2

c2=u2

c5=u0+

u1

c6=u1+

u2

則C=（c0c1c2c3c4c5c6）=（u0,u1,u2,u0+

u2,u0+

u1+

u2,

u0+

u1,u1+

u2）*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－34

§3.線性分組碼n位的碼組，由k個(gè)信息位的輸入消息u通過(guò)一個(gè)線性變換矩陣k×n階G來(lái)產(chǎn)生，稱G——生成矩陣G=，I為k階單位方陣——典型生成矩陣生成矩陣GC=(c0c1c2c3c4c5c6)=(u0,u1,u2,u0+u2,u0+u1+u2,u0+u1,u1+u2

)*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－35

§3.線性分組碼將監(jiān)督位線性方程組寫為即可見上述監(jiān)督關(guān)系的線性方程組完全由矩陣H所決定。故將此r×n的H矩陣稱為監(jiān)督矩陣H=,I為(n-k＝r)維（階）單位方陣

——典型監(jiān)督矩陣*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－36

§3.線性分組碼根據(jù)前面所得可推導(dǎo)：∴G與H生成的空間互為零空間，且G與H可以互相轉(zhuǎn)換。（即P、Q互為轉(zhuǎn)置矩陣）*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－37

§3.線性分組碼校正子（碼組伴隨式）發(fā)送碼組C經(jīng)過(guò)傳輸系統(tǒng)到達(dá)接收端時(shí)，假設(shè)收到的碼組為B，B=[bn-1bn-2…b0]差錯(cuò)關(guān)系為B-C=E，B＋E=CE=[en-1en-2…e0]，E又稱為錯(cuò)誤圖樣。其中接收時(shí)計(jì)算校正子為

*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－38

§3.線性分組碼編碼器若以{c0c1c2}為信息碼,由監(jiān)督碼的生成關(guān)系可得c3=1·c0+

0·c1+

1·c2c4=1·c0+

1·c1+1·

c2c5=1·c0+

1·c1+0·c2c6=0·c0+

1·c1+

1·c2C0C1C2++++u0u1u2C4C5C6C3*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－39

§3.線性分組碼譯碼器由校正子關(guān)系可得*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－40

§3.線性分組碼譯碼器b0b1b2b3b4b5b6++++b0s1s2s3s4s1s2s3s4與+r0c0b1與+r1c1b2與+r2c2b3與+r3c3b4與+r4c4b5與+r5c5b6與+r6c6伴隨式計(jì)算電路錯(cuò)誤圖樣檢測(cè)電路*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－41

系統(tǒng)碼VS.非系統(tǒng)碼非典型生成矩陣->典型生成矩陣?yán)贸醯刃凶儞Q以及列交換例如：*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－42

§3.線性分組碼漢明（海明）碼（Hamming）能糾正單個(gè)隨機(jī)錯(cuò)誤的線性分組碼碼長(zhǎng)n=2m-1信息位k=2m-1-m監(jiān)督位n-k=m，且m≥3最小距離dmin=d0=3漢明碼是一類高效率的糾錯(cuò)碼編碼效率R=k/n=(n-m)/n=1-m/nn很大時(shí)，R→1*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－43

§4.循環(huán)碼基本概念線性分組碼的一個(gè)子類，比較成熟任何一個(gè)可用碼組經(jīng)過(guò)循環(huán)移位后所得到的碼組仍為一個(gè)可用碼組原碼組C=[cn-1cn-2…

c1c0]左移一位C1=[cn-2cn-3…c0cn-1]右移一位C2=[c1cn-1…c3c2]移i位Ci=[cn-i-1cn-i-2…

cn-i]循環(huán)碼組C=[cn-1cn-2…

c1c0]可表示為多項(xiàng)式

C(x)=cn-1xn-1

+

cn-2xn-2

+…+

c1x+

c0式中x的冪次表示：①碼元的位置；②碼的移位次數(shù)*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－44

§4.循環(huán)碼基本概念如多項(xiàng)式C(x)=

x6

+

x4

+x+1→C=[1010011]c6x6可以看作c6從最低位c0左移6次的結(jié)果C(x)左移一位記作C(1)(x)C(1)(x)=cn-2xn-1

+

cn-3xn-2

+…+

c0x+

cn-1C(x)左移i位后為C(i)(x)=cn-i-1xn-1

+

cn-i-2xn-2

+…+

cn-i+1x+

cn-i*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－45

§4.循環(huán)碼循環(huán)碼多項(xiàng)式的運(yùn)算特性碼長(zhǎng)為n的循環(huán)碼，其碼多項(xiàng)式C(x)，則xi·C(x)=Q(x)·(xn+1)+C(i)(x)

即例如：某循環(huán)碼組為C=(1100101)，碼長(zhǎng)n=7，對(duì)應(yīng)的碼多項(xiàng)式為C(x)=x6

+x5

+

x2+

1左移一位后x·C(x)=x7

+x6

+

x3+

x因?yàn)镃(1)(x)≡x·C(x)

(mod（x7+1）)=x6

+x3

+

x

+

1

→（1001011）*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－46

§4.循環(huán)碼左移2位時(shí)x2·C(x)=x8

+x7

+

x4+

x2x+1x7

+1)x8

+x7

+

x4+

x2x8+x

x7

+

x4+

x2+xx7+1x4+

x2+x+1∴C(2)(x)=x4+

x2+x+1→(0010111)*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－47

§4.循環(huán)碼生成多項(xiàng)式g(x)對(duì)于(n,k)循環(huán)碼來(lái)說(shuō)，生成多項(xiàng)式g(x)是一個(gè)能除盡xn+1的（n-k）階多項(xiàng)式。階數(shù)低于n并能被g(x)除盡的一組多項(xiàng)式就構(gòu)成一個(gè)(n,k)循環(huán)碼階數(shù)小于等于(n-1)并能被g(x)除盡的每個(gè)多項(xiàng)式都是循環(huán)碼的可用碼組多項(xiàng)式。所以，循環(huán)碼完全由其碼組長(zhǎng)度n和生成多項(xiàng)式g(x)所決定。*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－48

§4.循環(huán)碼生成多項(xiàng)式g(x)設(shè)構(gòu)成循環(huán)碼的信息碼多項(xiàng)式為u(x)，其階數(shù)不大于(k-1)，則有循環(huán)碼組為C(x)=u(x)·g(x)例如，n=7，g(x)=x4+x3+x2+1是x7+1的一個(gè)因式；g(x)最高冪次為4=n-k；則k=3，r=4（即信息碼3bits，監(jiān)督碼4bits）?？捎么a組如下：*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－49

§4.循環(huán)碼生成多項(xiàng)式g(x)以上是一個(gè)（7，3）循環(huán)碼，最小碼距dmin=4，其信息碼多項(xiàng)式如下：*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－50

§4.循環(huán)碼生成多項(xiàng)式g(x)為了得到g(x)，需對(duì)xn+1進(jìn)行因式分解對(duì)于大部分n值，xn+1僅有很少的幾個(gè)因式；只有很少的幾個(gè)n值，

xn+1才有較多因式設(shè)g(x)·h(x)=xn+1

或g(x)·h(x)≡0mod(xn+1)

以（7，3）循環(huán)碼為例，n=7

x7+1=(x+1)(x3+x2+1)(x3+x+1)*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－51

§4.循環(huán)碼生成多項(xiàng)式g(x)n=7，

x7+1=(x+1)(x3+x2+1)(x3+x+1)循環(huán)碼dming(x)h(x)(7,6)2x+1(x3+x2+1)(x3+x+1)(7,4)3x3+x2+1(x+1)(x3+x+1)x3+x+1(x+1)(x3+x2+1)(7,3)4(x+1)(x3+x+1)x3+x2+1(x+1)(x3+x2+1)x3+x+1(7,1)7(x3+x2+1)(x3+x+1)x+1顯然，(7，3)、(7，4)循環(huán)碼可以互為對(duì)偶碼.*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－52

§4.循環(huán)碼生成矩陣GC(x)=u(x)·g(x)

=(uk-1xk-1+uk-2xk-1+…+u1x+u0)·g(x)=uk-1xk-1g(x)+uk-2xk-2g(x)+…+u0g(x)

=u·G根據(jù)u的不同取值可求得(n,k)循環(huán)碼的所有2k個(gè)碼字，但這樣所得到的碼并非系統(tǒng)碼。*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－53

§4.循環(huán)碼生成矩陣G為了進(jìn)一步得到系統(tǒng)碼，可作如下運(yùn)算：xn-ku(x)=Q(x)g(x)+r(x)C(x)=xn-ku(x)+r(x)=Q(x)g(x)+r(x)+r(x)=Q(x)g(x)構(gòu)造系統(tǒng)循環(huán)碼：只需將信息碼多項(xiàng)式升(n-k)階，然后以g(x)為模求余，所得余式即為監(jiān)督碼多項(xiàng)式——“除法求余”過(guò)程*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－54

§4.循環(huán)碼例如：已知(7,4)系統(tǒng)碼的生成多項(xiàng)式為g(x)=x3+x2+1，求其生成矩陣。解：由先求出*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－55

§4.循環(huán)碼監(jiān)督矩陣H由于xn+1=g(x)·h(x)生成多項(xiàng)式g(x)=gn-kxn-k+…+g1x+g0監(jiān)督多項(xiàng)式h(x)=hkxk+…+h1x+h0*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－56

§4.循環(huán)碼例如，已知(7,3)系統(tǒng)循環(huán)碼的生成多項(xiàng)式g(x)=x4+x3+x2+1，求生成矩陣G及監(jiān)督矩陣H。解：由g(x)·h(x)=x7+1的關(guān)系可得：

h(x)=x3+x2+1=h3x3+h2x2+h1x+h0根據(jù)前例方法先計(jì)算rn-i(x)≡[xn-i]modg(x)可得*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－57

§4.循環(huán)碼編碼器循環(huán)碼的特點(diǎn)一：可以采用反饋線性移位寄存器實(shí)現(xiàn)編碼和伴隨式計(jì)算以g(x)=x3+x+1的（7，4）循環(huán)編碼器為例D0D1D2++門輸入u(x)·xn-k12碼字輸出1XX2X3*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－58

編碼器以g(x)=x3+x+1的（7，4）循環(huán)編碼器為例節(jié)拍信息組輸入依存狀態(tài)輸出碼字D0(x0)D1(x1)D2(x2)0000111101200110301110410111500116000170000初態(tài)為000門開四次移位后信息1001全部輸出，關(guān)門，輸出開關(guān)倒向2又循環(huán)回到初始狀態(tài)信息位監(jiān)督位D0D1D2++門輸入u(x)·xn-k12碼字輸出*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－59

§4.循環(huán)碼譯碼器仍以g(x)=x3+x+1生成的（7，4）循環(huán)碼譯碼為例復(fù)用器++門1門2+門2Y(x)s0s1s2錯(cuò)誤圖樣檢測(cè)電路只有1套，其譯碼電路比一般的(7,4)線性分組碼大大簡(jiǎn)化*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－60

§4.循環(huán)碼(7，4)循環(huán)碼d=3g(x)=(x3+x+1)(8,4)非循環(huán)碼d=4(7，3)循環(huán)碼d=4g(x)=(x3+x+1)(x+1)刪減增擴(kuò)收縮加長(zhǎng)縮短擴(kuò)展*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－61

§4.循環(huán)碼循環(huán)碼檢錯(cuò)——CRC(CyclicRedundancyCheck,循環(huán)冗余校驗(yàn))一般能檢測(cè)的錯(cuò)誤：突發(fā)長(zhǎng)度<n-k+1的突發(fā)錯(cuò)誤大部分突發(fā)長(zhǎng)度=n-k+1的錯(cuò)誤，其中不可檢出錯(cuò)誤僅占2-(n-k-1)大部分突發(fā)長(zhǎng)度>n-k+1的錯(cuò)誤，其中不可檢出錯(cuò)誤僅占2-(n-k)所有與許用碼組碼距≤dmin-1的錯(cuò)誤所有奇數(shù)個(gè)錯(cuò)誤CRC碼在數(shù)據(jù)通信及移動(dòng)通信中得到廣泛應(yīng)用*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－62

§4.循環(huán)碼循環(huán)碼檢錯(cuò)：——CRC(CyclicRedundancyCheck,循環(huán)冗余校驗(yàn))常用的CRC碼——國(guó)際標(biāo)準(zhǔn)CRC-12：g(x)=x12+x11+x3+x2+x+1CRC-16:g(x)=x16+x15+x2+1CRC-CCITT:g(x)=x16+x12+x5+1CRC-32:g(x)=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1CRC-12用于字符長(zhǎng)度為6bits情況，后三種用于8bits字符。*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－63

CRC

校驗(yàn)示例待校驗(yàn)數(shù)據(jù)：1101,0110,11g(x)=x4+x+1,即10011

1101011011

00001001111000010101001110011100110000101101001110100100111110余數(shù)∴傳送序列T(x)=1101,0110,11

11,10待發(fā)送的原數(shù)據(jù)校驗(yàn)碼*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－64

CRC接收端的處理過(guò)程假設(shè)收到序列R(X)=1101,1110,1111,10≠T(x)(出錯(cuò))

仍然用g(x)=x4+x+1,即10011

做除數(shù)110111101111101001111001011001001110001100111010110011110111001110001100111010非0余數(shù)表示有錯(cuò)*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－65

接收端的處理過(guò)程（續(xù)）假設(shè)收到序列無(wú)誤，則有

R(X)=T(X)=1101,0110,1111,10仍然用g(x)=x4+x+1,即10011

做除數(shù)110101101111101001111000010101001110011100110010111100111001110011

000000余數(shù)為0表示正確接收*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－66

§5.卷積碼卷積碼是非分組碼的典型代表，亦稱連環(huán)碼。它是1955年由埃里亞斯（Elias）最早提出。與分組碼的主要差異：卷積碼編碼器有記憶，在任意給定的時(shí)段，編碼器的n個(gè)輸出不僅與此時(shí)段的k個(gè)輸入有關(guān)，而且與前m個(gè)輸入有關(guān)卷積碼記為（n，k，m）n為輸出碼元數(shù)k為輸入碼元數(shù)m為編碼器的存儲(chǔ)器數(shù)卷積碼記為（n，k，K）n為輸出碼元數(shù)k為輸入碼元數(shù)K為卷積碼的約束長(zhǎng)度K=m+1*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－67

§5.卷積碼卷積碼編碼串并轉(zhuǎn)換….有限狀態(tài)的有記憶系統(tǒng)（最大延遲為m）….并串轉(zhuǎn)換輸出碼字序列C輸入信息序列uu①c①u②c②描述時(shí)序網(wǎng)絡(luò)的方法解析表示法離散卷積法、生成矩陣法、碼多項(xiàng)式法圖形表示法狀態(tài)圖法、樹圖法、格圖法*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－68

§5.卷積碼卷積碼編碼現(xiàn)以一個(gè)二元（2，1，4）卷積碼為例有限狀態(tài)的有記憶系統(tǒng)k=1，即一個(gè)輸入位n=2，即兩個(gè)輸出位K=4即約束長(zhǎng)度為4；即m=3，有三級(jí)移位寄存器輸入信息序列u=(u0u1u2…)++輸出碼字序列c=(c0①

c0②c1①

c1②

c2①

c2②

……)

g①輸出c①=u*g①=(c0①c1①c2①…)輸出c②=u*g②=(c0②

c1②

c2②…)g

②*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－69

卷積碼編碼——離散卷積法以一個(gè)二元（2，1，4）卷積碼為例由圖可知g1(x)=1+x2+x3

→g①=(1011)

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

→g②=(1111)設(shè)u=(10111)，則有

c①=(10111)*(1011)=(10000001)

c②=(10111)*(1111)=(11011101)最后輸出的碼字為c=(1101000101010011)生成序列輸入信息序列u=(u0u1u2…)++輸出碼字序列c=(c0①

c0②c1①

c1②

c2①

c2②

……)

g①輸出c①=u*g①=(c0①c1①c2①…)輸出c②=u*g②=(c0②

c1②

c2②…)g

②*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－70

§5.卷積碼生成矩陣G——生成矩陣法理論分析g0①g0②g1①g1②g2①g2②g3①g3②0

00g0①g0②g1①g1②g2①g2②g3①g3②0G=00g0①g0②g1①g1②g2①g2②g3①g3②

…

…

…

…

…生成矩陣G是一個(gè)半無(wú)限的矩陣編碼方程的矩陣形式：c=u·G*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－71

§5.卷積碼生成矩陣G已知u=(10111)，求得

g①=(1011),g②=(1111)

代入公式，可求得

11

01

11

11

0

000011

01

11

11

0000011

01

11

11

0000011

01

11

11

0000011

01

11

11

C=u·G=(10111)=(1101000101010011)*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－72

§5.卷積碼碼多項(xiàng)式表達(dá)式——工程應(yīng)用u=(10111)=1+x2+x3+x4g①=(1011)=1+x2+x3g②=(1111)=1+x+x2+x3

則卷積碼輸出為：c①=(1+x2+x3+x4)(1+x2+x3)=1+x7=(10000001)c②=(1+x2+x3+x4)(1+x+x2+x3)=1+x+x3+x4+x5+x7=(11011101)輸出序列為

C=(1101000101010011)*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－73

§5.卷積碼狀態(tài)圖法描述現(xiàn)以（2，1，3）卷積碼為例：

k=1，n=2，K=3，m=2總的可能狀態(tài)數(shù)為

2km=22=4種，即00,10,01,11每次可能的輸入有兩個(gè)即2k=2每次可能的輸出狀態(tài)也只有兩個(gè)狀態(tài)圖的畫法圓圈中的數(shù)字——狀態(tài)狀態(tài)之間的連線和箭頭——轉(zhuǎn)移方向（分支）分支上的數(shù)字——轉(zhuǎn)移時(shí)輸出的碼字括號(hào)中的數(shù)字——轉(zhuǎn)移時(shí)輸入的信息數(shù)字*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－74

§5.卷積碼狀態(tài)圖法（2，1，3）卷積碼為例：（2，1，3）卷積碼狀態(tài)轉(zhuǎn)移圖0011100111(1)01(1)01(0)11(0)10(0)00(1)00(0)10(1)*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－75

§5.卷積碼樹圖法按時(shí)間展開l=0l=1l=2l=3l=4l=5l=6l=7l節(jié)點(diǎn)級(jí)數(shù)樹根0分支1分支a00110000001111100111100110010011011011000110001110010011011000110011優(yōu)點(diǎn)：時(shí)序關(guān)系清晰對(duì)每一個(gè)信息輸入序列有且僅有一個(gè)不重復(fù)的樹枝結(jié)構(gòu)相對(duì)應(yīng)缺點(diǎn)：進(jìn)行到一定時(shí)序后，狀態(tài)重復(fù)且樹圖越來(lái)越復(fù)雜*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－76

§5.卷積碼樹圖法l=0l=1l=2l=3l=4l=5l=6l=7l節(jié)點(diǎn)級(jí)數(shù)樹根0分支1分支a00110000001111100111100110010011011011000110001110010011011010011100C=(1110000110011100)輸入序列為u=(10111000)*－蘭州大學(xué)信息科學(xué)與工程學(xué)院電信、通信工程系－77

§5.卷積碼格圖法（籬笆圖）二維狀態(tài)l=0l=1l=2l=3l=4l=5l=6l=7l節(jié)點(diǎn)級(jí)數(shù)a=00b=10c=01d=110000000000000011111111111110011001011010100111000110011011110110010000111100在l=3時(shí)狀態(tài)abcd呈現(xiàn)重復(fù)圖示說(shuō)明：輸入為0所走的分支輸入為1所走的分支C=(11100001100111)所對(duì)應(yīng)的路徑*－蘭州大學(xué)信息科學(xué)與工程