[信息與通信]計(jì)算及通信第8章 差錯(cuò)控制編碼.ppt

2019/4/14,1,第8章 差錯(cuò)控制編碼,8.1 引言 8.2 常用簡(jiǎn)單分組碼 8.3 線性分組碼 8.4 循環(huán)碼 8.5 卷積碼,2019/4/14,2,8.1 引言,8.1.1 信源編碼與信道編碼的基本概念 在數(shù)字通信系統(tǒng)中，為了提高數(shù)字信號(hào)傳輸?shù)挠行远扇〉木幋a稱為信源編碼；為了提高數(shù)字通信的可靠性而采取的編碼稱為信道編碼。 1、信源編碼,2019/4/14,3,2、信道編碼（差錯(cuò)控制編碼） 差錯(cuò)控制編碼是在信息序列上附加上一些監(jiān)督碼元，利用這些冗余的碼元，使原來(lái)不規(guī)律的或規(guī)律性不強(qiáng)的原始數(shù)字信號(hào)變?yōu)橛幸?guī)律的數(shù)字信號(hào)；差錯(cuò)控制譯碼則利用這些規(guī)律性來(lái)鑒別傳輸過(guò)程是否發(fā)生錯(cuò)誤，或進(jìn)而糾正錯(cuò)誤。,2019/4/14,4,8.1.2 糾錯(cuò)編碼的分類 （1）按照信道編碼的不同功能，可以將它分為檢錯(cuò)碼和糾錯(cuò)碼。 （2）按照信息碼元和監(jiān)督碼元之間的檢驗(yàn)關(guān)系，可以將它分為線性和非線性碼。 （3）按照信息碼元和監(jiān)督碼元之間的約束方式不同，可以將它分為分組碼和卷積碼。 （4）按照信息碼元在編碼后是否保持原來(lái)的形式，可以將它分為系統(tǒng)碼和非系統(tǒng)碼。,2019/4/14,5,（5）按照糾正錯(cuò)誤的類型不同，可以將它分為糾正隨機(jī)錯(cuò)誤碼和糾正突發(fā)錯(cuò)誤碼。 （6）按照信道編碼所采用的數(shù)學(xué)方法不同，可以將它分為代數(shù)碼、幾何碼和算術(shù)碼。 隨著數(shù)字通信系統(tǒng)的發(fā)展，可以將信道編碼器和調(diào)制器統(tǒng)一起來(lái)綜合設(shè)計(jì)，這就是所謂的網(wǎng)格編碼調(diào)制。,2019/4/14,6,8.1.2 差錯(cuò)控制方式,2019/4/14,7,檢錯(cuò)重發(fā)方式： 檢錯(cuò)重發(fā)（ARQ）的優(yōu)點(diǎn)主要表現(xiàn)在： （1）只需要少量的冗余碼，就可以得到極低的輸出誤碼率； （2）有一定的自適應(yīng)能力；,2019/4/14,8,某些不足主要表現(xiàn)在： （1）需要反向信道，故不能用于單向傳輸系統(tǒng)，并且實(shí)現(xiàn)重發(fā)控制比較復(fù)雜； （2）通信效率低，不適合嚴(yán)格實(shí)時(shí)傳輸系統(tǒng)。 混合糾錯(cuò)方式是前向糾錯(cuò)方式和檢錯(cuò)重發(fā)方式的結(jié)合。,2019/4/14,9,8.1.2 糾錯(cuò)編碼的基本原理 信道編碼有關(guān)的基本概念： 碼長(zhǎng)：碼字中碼元的數(shù)目； 碼重：碼字中非0數(shù)字的數(shù)目； 碼距：兩個(gè)等長(zhǎng)碼字之間對(duì)應(yīng)位不同的數(shù)目，有時(shí)也稱作這兩個(gè)碼字的漢明距離。 最小碼距：在碼字集合中全體碼字之間距離的最小數(shù)值。,10,糾錯(cuò)碼的抗干擾能力完全取決于許用碼字之間的距離，碼的最小距離越大，說(shuō)明碼字間的最小差別越大，抗干擾能力就越強(qiáng)。 分組碼的最小漢明距離d0與檢錯(cuò)和糾錯(cuò)能力之間滿足下列關(guān)系： （1）當(dāng)碼字用于檢測(cè)錯(cuò)誤時(shí)，如果要檢測(cè)e個(gè)錯(cuò)誤，則 d0 e+1； （2）當(dāng)碼字用于糾正錯(cuò)誤時(shí)，如果要糾正t個(gè)錯(cuò)誤，則 d0 2t+1；,2019/4/14,11,（3）若碼字用于糾t個(gè)錯(cuò)誤，同時(shí)檢e個(gè)錯(cuò)誤時(shí)（et），則 d0 t+e+1。 編碼效率Rc可以用下式表示：,2019/4/14,12,8.2 常用簡(jiǎn)單分組碼,8.2.1 奇偶監(jiān)督碼 可以表示成為（n，n-1）。如果是奇監(jiān)督碼，在附加上一個(gè)監(jiān)督元以后，碼長(zhǎng)為n的碼字中“1”的個(gè)數(shù)為奇數(shù)個(gè)；如果是偶監(jiān)督碼，在附加上一個(gè)監(jiān)督元以后，碼長(zhǎng)為n的碼字中“1”的個(gè)數(shù)為偶數(shù)個(gè)。 an-1+an-2+a1+a0 = 0,2019/4/14,13,奇偶監(jiān)督碼的編碼可以用軟件實(shí)現(xiàn)，也可用硬件電路實(shí)現(xiàn)。 如果碼組B無(wú)錯(cuò)，BA，則M0；如果碼組B有單個(gè)（或奇數(shù)個(gè)）錯(cuò)誤，則M1。,2019/4/14,14,8.2.2 行列監(jiān)督碼 行列監(jiān)督碼又稱水平垂直一致監(jiān)督碼或二維奇偶監(jiān)督碼，有時(shí)還被稱為矩陣碼。,2019/4/14,15,二維奇偶監(jiān)督碼適于檢測(cè)突發(fā)錯(cuò)碼。二維奇偶監(jiān)督碼不僅可用來(lái)檢錯(cuò)，還可用來(lái)糾正一些錯(cuò)碼。 8.2.3 恒比碼 恒比碼又稱等重碼，該碼的碼字中1和0的位數(shù)保持恒定的比例。具體情況見(jiàn)表8-3。 目前我國(guó)電傳通信中普遍采用3：2碼，國(guó)際上通用的ARQ電報(bào)通信系統(tǒng)中，采用3：4碼即7中取3碼。,2019/4/14,16,8.3 線性分組碼,8.3.1 基本概念 分組碼是一組固定長(zhǎng)度的碼組，可表示為（n , k），通常它用于前向糾錯(cuò)。在編碼時(shí)，k個(gè)信息位被編為n位碼組長(zhǎng)度，而n-k個(gè)監(jiān)督位的作用就是實(shí)現(xiàn)檢錯(cuò)與糾錯(cuò)。 這樣，一個(gè)k比特信息的線性分組碼可以映射到一個(gè)長(zhǎng)度為n碼組上。,2019/4/14,17,線性分組碼的主要性質(zhì)如下： （1）任意兩許用碼之和仍為一許用碼，也就是說(shuō)，線性分組碼具有封閉性； （2）碼組間的最小碼距等于非零碼的最小碼重。 對(duì)偶校驗(yàn)時(shí)的監(jiān)督關(guān)系。在接收端解碼時(shí)，實(shí)際上就是在計(jì)算： S = bn-1+bn-2+b1+b0 若S0，則無(wú)錯(cuò)；若S1就認(rèn)為有錯(cuò)。,2019/4/14,18,當(dāng)r個(gè)監(jiān)督方程式計(jì)算得到的校正子有r位，可以用來(lái)指示2r-1種誤碼圖樣。 如果希望用r個(gè)監(jiān)督位構(gòu)造出r個(gè)監(jiān)督關(guān)系式來(lái)指示一位錯(cuò)碼的n種可能，則要求： 例如r 3，若取r = 3，則n = k+r = 7。假設(shè)S3、S2、S1三位校正字碼組與誤碼位置的關(guān)系如表8-4。根據(jù)表8-4，可以構(gòu)成如下關(guān)系式：,2019/4/14,19,S1= a6+a5+a4+a2 , S2= a6+a5+a4+a2 , S3= a6+a4+a3+a0 進(jìn)而得到下面的方程組形式： 接收端收到每個(gè)碼組后，計(jì)算出S3、S2和S1，如不全為0，則可按表8-4確定誤碼的位置，然后予以糾正。不難看出，上述（7，4）碼的最小碼距dmin3。,2019/4/14,20,8.3.2 監(jiān)督矩陣H和生成矩陣G 將（7，4）碼的三個(gè)監(jiān)督方程式可以重新改寫(xiě)為如下形式： 上式可以記作：HAT=0T或AHT=0 ，其中,2019/4/14,21,也可以用矩陣形式來(lái)表示： 或表示成為： 這時(shí)Q = PT，如果在Q矩陣的左邊在加上一個(gè)kk的單位矩陣，就形成了一個(gè)新矩陣G：,2019/4/14,22,這里G稱為生成矩陣，利用它可以產(chǎn)生整個(gè)碼組：,2019/4/14,23,8.3.3 校驗(yàn)子S 設(shè)發(fā)送組碼A，在傳輸過(guò)程中有可能出現(xiàn)誤碼，這時(shí)接收到的碼組為B。則收發(fā)碼組之差為： 其中： 則接收端利用接收到的碼組B計(jì)算校正子： S=BHT=(A+E)HT= AHT + EHT = EHT 因此，校正子僅與E有關(guān)，即錯(cuò)誤圖樣與校正子之間有確定的關(guān)系。,2019/4/14,24,8.3.4 漢明碼 漢明碼是一種能夠糾正單個(gè)錯(cuò)誤的線性分組碼。它有以下特點(diǎn)： （1）最小碼距dmin3，可糾正一位錯(cuò)誤； （2）碼長(zhǎng)n與監(jiān)督元個(gè)數(shù)r之間滿足關(guān)系式： 。 通常二進(jìn)制漢明碼可以表示為：,2019/4/14,25,（7，4）系統(tǒng)漢明碼的編碼器和譯碼器電路：,2019/4/14,26,2019/4/14,27,8.4 循環(huán)碼,循環(huán)碼是線性分組碼的一個(gè)重要子集，是目前研究得最成熟的一類碼，它有許多特殊的代數(shù)性質(zhì)。 8.4.1 循環(huán)碼的特點(diǎn) 循環(huán)特性是指：循環(huán)碼中任一許用碼組經(jīng)過(guò)循環(huán)移位后，所得到的碼組仍然是許用碼組。,2019/4/14,28,為了利用代數(shù)理論研究循環(huán)碼，可以將碼組用代數(shù)多項(xiàng)是來(lái)表示，這個(gè)多項(xiàng)式被稱為碼多項(xiàng)式，對(duì)于許用循環(huán)碼A=(an-1 an-2 a1 a0)，可以將它的碼多項(xiàng)式表示為： 若一個(gè)整數(shù)m可以表示為: 則在模n運(yùn)算下，有mp（模n），同樣對(duì)于多項(xiàng)式而言：,2019/4/14,29,則可以寫(xiě)為：F(x)R(x) （模N(x)）。 在循環(huán)碼中，若A(x)是一個(gè)長(zhǎng)為n的許用碼組，則在按模 運(yùn)算下，亦是一個(gè)許用碼組。例如， 其對(duì)應(yīng)的碼組為0101110，它正是表8-7中第3碼字。,2019/4/14,30,8.4.2 循環(huán)碼的生成多項(xiàng)式和生成矩陣 循環(huán)碼中次數(shù)最低的碼多項(xiàng)式稱為生成多項(xiàng)式，用g(x)表示?？梢宰C明生成多項(xiàng)式g(x)具有以下特性： （1） g(x)是一個(gè)常數(shù)項(xiàng)為1的 次多項(xiàng)式； （2） g(x)是 的一個(gè)因式； （3）該循環(huán)碼中其它碼多項(xiàng)式都是g(x)的倍式。,2019/4/14,31,為了保證構(gòu)成的生成矩陣G的各行線性不相關(guān)，通常用g(x)來(lái)構(gòu)造生成矩陣， 顯然，上式不符合 形式，所以此生成矩陣不是典型形式。,因此，一旦生成多項(xiàng)式g(x)確定以后，該循環(huán)碼的生成矩陣就可以確定。,2019/4/14,32,利用循環(huán)碼的特點(diǎn)來(lái)確定監(jiān)督矩陣H： 由于（n,k）循環(huán)碼中g(shù)(x)是xn +1的因式，因此可令： 監(jiān)督矩陣表示為：,2019/4/14,33,8.4.3 循環(huán)碼的編、譯碼方法 1、編碼過(guò)程 首先需要根據(jù)給定循環(huán)碼的參數(shù)確定生成多項(xiàng)式g(x) ，然后，利用循環(huán)碼的編碼特點(diǎn)，即所有循環(huán)碼多項(xiàng)式A(x)都可以被g(x)整除，來(lái)定義生成多項(xiàng)式A(x)。下面就將以上各步處理加以解釋： （1）用xn-k乘m(x)。這一運(yùn)算實(shí)際上是把信息碼后附加上（n-k）個(gè)“0”。,2019/4/14,34,（2）求r(x)。由于循環(huán)碼多項(xiàng)式A(x)都可以被g(x)整除，也就是： 上式也等效于： 這樣我們就得到了r(x)。 （3）編碼輸出系統(tǒng)循環(huán)碼多項(xiàng)式A(x)為：,2019/4/14,35,上述三步編碼過(guò)程，在硬件實(shí)現(xiàn)時(shí)，可以利用除法電路來(lái)實(shí)現(xiàn)。 2、譯碼過(guò)程 循環(huán)碼的譯碼可以分三步進(jìn)行： （1）由接收到的碼多項(xiàng)式B(x)計(jì)算校正子（伴隨式）多項(xiàng)式S(x)；,2019/4/14,36,（2）由校正子S(x)確定錯(cuò)誤圖樣E(x)； （3）將錯(cuò)誤圖樣E(x)與B(x)相加，糾正錯(cuò)誤。,2019/4/14,37,8.5 卷積碼,卷積碼中編碼后的n個(gè)碼元不僅與當(dāng)前段的k個(gè)信息有關(guān)，而且也與前面（N-1）段的信息有關(guān)，編碼過(guò)程中相互關(guān)聯(lián)的碼元為nN個(gè)。因此，這N段時(shí)間內(nèi)的碼元數(shù)目nN通常被稱為這種碼的約束長(zhǎng)度。 由于與前面m段規(guī)定時(shí)間內(nèi)的信息位有關(guān)，這里的mN-1通常用（n