第十一差錯(cuò)控制編碼演示文稿

第十一差錯(cuò)控制編碼演示文稿現(xiàn)在是1頁\一共有72頁\編輯于星期四（優(yōu)選）第十一差錯(cuò)控制編碼現(xiàn)在是2頁\一共有72頁\編輯于星期四§11.1

概述誤碼分類噪聲引入的隨機(jī)誤碼，均勻分布由干擾、快衰落引起的突發(fā)誤碼如何減少誤碼？從信源編碼看，誤碼引起的性能惡化盡可能小，容錯(cuò)技術(shù)從傳輸看，可采用抗干擾能力強(qiáng)的調(diào)制方式，信道特性不理想可采用均衡。特別需要差錯(cuò)控制技術(shù)。數(shù)字通信中，要求誤碼率10－8以下，必須采用差錯(cuò)控制。現(xiàn)在是3頁\一共有72頁\編輯于星期四

差錯(cuò)控制分類

1.反饋檢驗(yàn)法

2.檢錯(cuò)重發(fā)法（ARQ）

3.前向糾錯(cuò)（FEC）現(xiàn)在是4頁\一共有72頁\編輯于星期四1.

反饋檢驗(yàn)法需要雙向信道，和前向信道有相同的通信容。引入較大的停頓（不實(shí)時(shí)）?？梢约m正任何錯(cuò)誤?，F(xiàn)在是5頁\一共有72頁\編輯于星期四2.

檢錯(cuò)重發(fā)法（ARQ）自動請求重發(fā)也需要反向信道，但容量可以降低，也會引入停頓現(xiàn)在是6頁\一共有72頁\編輯于星期四3.

前向糾錯(cuò)（FECforwarderrorcorrection）不需要雙向信道不會引入停頓靠糾錯(cuò)編碼現(xiàn)在是7頁\一共有72頁\編輯于星期四§11.1.2差錯(cuò)控制編碼的基本原理如用三位二進(jìn)制編碼來代表八個(gè)字母

000 A 100 E 001 B 101 F 010 C 110 G 011 D 111 H不管哪一位發(fā)生錯(cuò)誤，都會使傳輸字母錯(cuò)誤如用三位字母傳四個(gè)字母

000 A 011 B 101 C 110 D發(fā)生一位錯(cuò)誤，準(zhǔn)用碼字將變成禁用碼字，接收端就能知道出錯(cuò)，但是不能糾錯(cuò)。現(xiàn)在是8頁\一共有72頁\編輯于星期四差錯(cuò)控制編碼如用三位字母傳二個(gè)字母

000 A 111 B 檢三個(gè)錯(cuò)誤，糾正一個(gè)錯(cuò)誤。結(jié)論具有檢錯(cuò)或糾錯(cuò)的碼組，其所用的比特?cái)?shù)必須大于信息碼組原來的比特?cái)?shù) －>引入多余度。現(xiàn)在是9頁\一共有72頁\編輯于星期四碼重、碼距碼重(weight)一個(gè)碼組中“1”的數(shù)目碼距(distance)兩個(gè)碼組之間對應(yīng)位置上1、0不同的位數(shù)，又叫漢明(Hamming)距。

10110碼重：3 011002距離：3現(xiàn)在是10頁\一共有72頁\編輯于星期四檢錯(cuò)、糾錯(cuò)能力為檢查出

個(gè)錯(cuò)誤，要求最小碼距為為糾正個(gè)錯(cuò)誤，要求最小碼距為為糾正個(gè)錯(cuò)誤，同時(shí)檢查出個(gè)錯(cuò)誤，要求最小碼距為

現(xiàn)在是11頁\一共有72頁\編輯于星期四.

差錯(cuò)控制編碼分類按功能分檢錯(cuò)碼糾錯(cuò)碼糾刪碼（發(fā)現(xiàn)不可糾正的錯(cuò)誤時(shí)，可發(fā)出指示或刪除）按信息碼元和監(jiān)督碼元之間的校驗(yàn)關(guān)系分線性碼非線性碼按信息碼元和監(jiān)督碼元之間的約束方式分分組碼卷積碼現(xiàn)在是12頁\一共有72頁\編輯于星期四香農(nóng)理論糾錯(cuò)碼建立在香農(nóng)理論基礎(chǔ)上香農(nóng)定理存在噪聲干擾的信道，若信道容量為C，只要發(fā)送端以低于C的速率R發(fā)送信息（R為輸入到編碼器的二進(jìn)制碼元速率），則一定存在一種編碼方式，使編碼的錯(cuò)誤概率隨著碼長n的增加將按指數(shù)下降到任一的值，即結(jié)論如碼長及發(fā)送信息速率一定，可以通過增大信道容量，使P減小。如在信道容量及發(fā)送信息速率一定，可以通過增加碼長，使錯(cuò)誤概率下降。現(xiàn)在是13頁\一共有72頁\編輯于星期四分組碼表示：(n,k) n:幀長 k/n:編碼效率特點(diǎn)監(jiān)督碼只用來監(jiān)督本幀中的信息位分類線性碼－信息碼與監(jiān)督碼之間為線性關(guān)系非線性碼－不存在線性關(guān)系現(xiàn)在是14頁\一共有72頁\編輯于星期四奇偶監(jiān)督碼偶監(jiān)督奇監(jiān)督如果以上關(guān)系被破壞，則出現(xiàn)錯(cuò)誤，因此能檢查出奇數(shù)個(gè)錯(cuò)誤，但不能檢測偶數(shù)個(gè)錯(cuò)誤。 最小碼距為dmin=2這種碼檢錯(cuò)能力不高，采用什么方法提高呢？現(xiàn)在是15頁\一共有72頁\編輯于星期四水平奇偶監(jiān)督碼和水平垂直監(jiān)督碼又叫二維奇偶監(jiān)督碼水平奇偶監(jiān)督碼檢碼字按行排成方陣，每行采用奇偶監(jiān)督碼，發(fā)送時(shí)按列的順序傳送，接收時(shí)仍將碼字排列成發(fā)送時(shí)方陣形式，然后按行進(jìn)行奇偶校驗(yàn)。在不增加冗余度時(shí)，不僅能發(fā)現(xiàn)某一行上奇數(shù)個(gè)錯(cuò)誤，而且也能發(fā)現(xiàn)不大于方陣行數(shù)的突發(fā)錯(cuò)誤。水平垂直奇偶監(jiān)督碼不僅對行進(jìn)行奇偶校驗(yàn)，而且也對列進(jìn)行奇偶校驗(yàn)?，F(xiàn)在是16頁\一共有72頁\編輯于星期四等比碼在碼長一定時(shí)，“1”碼和“0”碼的比例恒定。已用于電報(bào)傳輸中。五中取三

01011 11001

表示十位數(shù)字，C53=10種許用碼組?，F(xiàn)在是17頁\一共有72頁\編輯于星期四第十一章差錯(cuò)控制編碼

§11.1基本概念§11.2分組碼

§11.3循環(huán)碼

§11.4BCH碼

§11.5糾正和檢測突發(fā)錯(cuò)誤的分組碼

§11.6糾錯(cuò)碼的誤碼性能現(xiàn)在是18頁\一共有72頁\編輯于星期四§11.2分組碼（1）漢明碼：能糾一位錯(cuò)誤(7,4)

現(xiàn)在是19頁\一共有72頁\編輯于星期四分組碼（2）在接收端，按如下規(guī)律運(yùn)算現(xiàn)在是20頁\一共有72頁\編輯于星期四分組碼（3）分組碼的監(jiān)督方程矩陣形式現(xiàn)在是21頁\一共有72頁\編輯于星期四分組碼（4）監(jiān)督矩陣H矩陣稱為典型形式，各行一定是線性無關(guān)的。而一個(gè)非典型形式的經(jīng)過運(yùn)算可以化成典型形式，通過監(jiān)督矩陣可以知道監(jiān)督碼和信息碼的監(jiān)督關(guān)系?，F(xiàn)在是22頁\一共有72頁\編輯于星期四分組碼（5）生成矩陣

，通過生成矩陣可以得到生成碼組。如果輸入碼組為0011現(xiàn)在是23頁\一共有72頁\編輯于星期四分組碼（6）由這種方式得到的生成矩陣稱為典型生成矩陣，由它產(chǎn)生的分組碼必定為系統(tǒng)碼，也就是信息碼字保持不變，監(jiān)督位附加其后，每行一定是線性無關(guān)的，每行都是一個(gè)生成碼組?，F(xiàn)在是24頁\一共有72頁\編輯于星期四漢明碼 漢明碼監(jiān)督位為位，因此它可以組成個(gè)可能情況，其中一個(gè)為無錯(cuò)。因此可以監(jiān)督碼位共 要糾正一個(gè)錯(cuò)誤，必須滿足 最小碼距如果r位監(jiān)督位所組成的校正子碼組與誤碼圖樣一一對應(yīng)，這種碼組稱為完備碼（取等號時(shí)）現(xiàn)在是25頁\一共有72頁\編輯于星期四擴(kuò)展?jié)h明碼如果在漢明碼基礎(chǔ)上，再加上一位對所有碼字進(jìn)行校驗(yàn)的監(jiān)督位監(jiān)督碼字由r

位增加到

r+1位信息位不變碼長 碼結(jié)構(gòu)糾1位錯(cuò)，檢測2位錯(cuò)如（8，4），（16，11）

現(xiàn)在是26頁\一共有72頁\編輯于星期四擴(kuò)展?jié)h明碼矩陣

如(7,4)－>(8,4)現(xiàn)在是27頁\一共有72頁\編輯于星期四縮短漢明碼(n,k)－>(n-s,k-s)如(15,11)－>(12,8)

監(jiān)督矩陣Hs是將原H的前3列去掉縮短漢明碼的最小碼距至少和原來碼的碼距相同，因?yàn)楸O(jiān)督位沒有變?，F(xiàn)在是28頁\一共有72頁\編輯于星期四縮短漢明碼能糾t個(gè)錯(cuò)誤的(n,k)應(yīng)滿足

取等號時(shí)為完備碼不同結(jié)構(gòu)的線性碼其糾錯(cuò)能力不同，能力和dmin有關(guān)，dmin越大越好?，F(xiàn)在是29頁\一共有72頁\編輯于星期四最小碼距界限上界：漢明界，普洛特金界下界：吉爾伯特界問題：給定碼長與編碼效率，尋找dmin例：dmin=5,碼長=63的分組碼設(shè)計(jì)

從漢明界得，

因此信息位最多可以取現(xiàn)在是30頁\一共有72頁\編輯于星期四最小碼距界限通過吉爾伯特界求下界線性碼

k越接近52，效率越高?，F(xiàn)在是31頁\一共有72頁\編輯于星期四第十一章差錯(cuò)控制編碼

§11.1基本概念§11.2分組碼

§11.3循環(huán)碼

§11.4BCH碼

§11.5糾正和檢測突發(fā)錯(cuò)誤的分組碼

§11.6糾錯(cuò)碼的誤碼性能現(xiàn)在是32頁\一共有72頁\編輯于星期四§11.3循環(huán)碼(Cycliccode)

1957年發(fā)現(xiàn)特點(diǎn)線性分組碼循環(huán)性——任一許用碼字經(jīng)過循環(huán)移位后，得到的碼組仍為一個(gè)許用碼組如是循環(huán)碼的一許用碼組

則也是一許用碼組

現(xiàn)在是33頁\一共有72頁\編輯于星期四碼多項(xiàng)式表示碼組 碼多項(xiàng)式碼組碼多項(xiàng)式左移一位左移位現(xiàn)在是34頁\一共有72頁\編輯于星期四循環(huán)碼性質(zhì)

為許用碼組，則也是許用碼組性質(zhì) 若是長度為n的循環(huán)碼組，則在按模進(jìn)行運(yùn)算后，也是一個(gè)循環(huán)碼組，也就是用多項(xiàng)式除后所得之余式，即為所求的碼組。

現(xiàn)在是35頁\一共有72頁\編輯于星期四循環(huán)碼例子碼組左移3位去除得余式如左移3位后，得是許用碼組現(xiàn)在是36頁\一共有72頁\編輯于星期四循環(huán)碼生成多項(xiàng)式g(D)g(D)是D的(n-k)次即r次多項(xiàng)式信息多項(xiàng)式為M(D),k位，(k-1)次多項(xiàng)式現(xiàn)在是37頁\一共有72頁\編輯于星期四g(D)定理.一個(gè)(n,k)的二進(jìn)制循環(huán)碼可以看成是唯一由它的生成多項(xiàng)式產(chǎn)生，即如(7,3)循環(huán)碼，n=7,k=3,r=4如果信息位為010，M(D)=D

生成碼為0111010現(xiàn)在是38頁\一共有72頁\編輯于星期四生成矩陣G(D)由于k位信息位共有個(gè)碼組，都可用此法產(chǎn)生，如果現(xiàn)有信息碼生成k個(gè)碼字，且這k個(gè)碼組都線性無關(guān)，用這k個(gè)碼組作為一個(gè)矩陣G的k行構(gòu)成生成矩陣G(D)稱為循環(huán)碼的生成矩陣多項(xiàng)式現(xiàn)在是39頁\一共有72頁\編輯于星期四(7,3)

循環(huán)碼(7,3)循環(huán)碼生成矩陣現(xiàn)在是40頁\一共有72頁\編輯于星期四生成矩陣和監(jiān)督矩陣這樣構(gòu)成的循環(huán)碼并非是系統(tǒng)碼系統(tǒng)碼的生成矩陣典型形式非系統(tǒng)碼系統(tǒng)碼生成矩陣監(jiān)督矩陣現(xiàn)在是41頁\一共有72頁\編輯于星期四非系統(tǒng)碼系統(tǒng)碼系統(tǒng)碼的碼多項(xiàng)式為例如，(7,4)碼，1011

現(xiàn)在是42頁\一共有72頁\編輯于星期四非系統(tǒng)碼系統(tǒng)碼(7,3)碼現(xiàn)在是43頁\一共有72頁\編輯于星期四尋找生成多項(xiàng)式循環(huán)碼的生成多項(xiàng)式必須能除盡

h(D)是監(jiān)督多項(xiàng)式，是

K階多項(xiàng)式例：要構(gòu)成(7,3)循環(huán)碼，求g(D).

解：g(D)應(yīng)為4階都能生成(7,3)生成(7,6)循環(huán)碼生成(7,1)循環(huán)碼

現(xiàn)在是44頁\一共有72頁\編輯于星期四循環(huán)碼的編碼器原理：按系統(tǒng)碼的生成方式：將信息碼多項(xiàng)式升(n-k)次冪后，再除生成多項(xiàng)式，然后將余式置于升冪后的信息多項(xiàng)式之后 以(7,4)碼為例

現(xiàn)在是45頁\一共有72頁\編輯于星期四循環(huán)碼的譯碼器譯碼比編碼復(fù)雜得多譯碼三步伴隨式S的計(jì)算由S得到錯(cuò)誤圖樣糾正現(xiàn)在是46頁\一共有72頁\編輯于星期四伴隨式的計(jì)算發(fā)送碼組接收碼組誤差碼組校正子只與E有關(guān)，根本是計(jì)算校正子

現(xiàn)在是47頁\一共有72頁\編輯于星期四校正子S的計(jì)算生成多項(xiàng)式g(D)去除接收碼字B(D)現(xiàn)在是48頁\一共有72頁\編輯于星期四第十一章差錯(cuò)控制編碼

§11.1基本概念§11.2分組碼

§11.3循環(huán)碼

§11.4BCH碼

§11.5糾正和檢測突發(fā)錯(cuò)誤的分組碼

§11.6糾錯(cuò)碼的誤碼性能現(xiàn)在是49頁\一共有72頁\編輯于星期四§11.4BCH碼特點(diǎn)：它也屬于循環(huán)碼，具有糾多個(gè)隨機(jī)錯(cuò)誤的能力，構(gòu)造容易。因此由碼的最小距離，可以很快得到碼的生成多項(xiàng)式即約多項(xiàng)式一個(gè)m次多項(xiàng)式不能被二元域上任何次數(shù)小于m的，但大于0的多項(xiàng)式除盡，如是即約的。本原多項(xiàng)式若m次多項(xiàng)式P(x)除盡的的最小正整數(shù)n滿足，就稱為本原的。如能除盡，但除不盡的。如：是即約的，但不是本原的，因它能除盡。

現(xiàn)在是50頁\一共有72頁\編輯于星期四§11.4.1本原循環(huán)碼由本原多項(xiàng)式構(gòu)成的碼稱為本原碼。特點(diǎn)碼長為它的生成多項(xiàng)式是由若干m階或以m的因子為最高階的多項(xiàng)式相乘而構(gòu)成。要判定(n,k)的循環(huán)碼是否存在，只需要判斷n-k階的生成多項(xiàng)式是否能由Dn+1的因式構(gòu)成。

現(xiàn)在是51頁\一共有72頁\編輯于星期四循環(huán)碼例子生成多項(xiàng)式的階次為r,該生成多項(xiàng)式是否是的因此。一個(gè)m階即約多項(xiàng)式一定能除盡如，m＝5，共有6個(gè)5階即約多項(xiàng)式。再加上因子，是以上7個(gè)多項(xiàng)式的乘積。

現(xiàn)在是52頁\一共有72頁\編輯于星期四循環(huán)碼例子表11-12表示了m<12的即約多項(xiàng)式在表中多項(xiàng)式的系數(shù)是用8進(jìn)制表示的，而且反多項(xiàng)式?jīng)]有表示如m=5,45,75,67100101111101110111現(xiàn)在是53頁\一共有72頁\編輯于星期四§11.4.2BCH碼的生成多項(xiàng)式如果循環(huán)碼的生成多項(xiàng)式具有如下形式為糾錯(cuò)個(gè)數(shù)，為最小多項(xiàng)式， 為最小公倍數(shù)，由這種方式生成的循環(huán)碼是BCH碼最小碼距碼長為的BCH碼稱為本原BCH碼（狹義BCH碼）碼長為則稱為非本原BCH碼

現(xiàn)在是54頁\一共有72頁\編輯于星期四BCH碼由于g(D)有t個(gè)因式，且每個(gè)因式的最高次為m，因此監(jiān)督碼元最多有mt位。對于糾t個(gè)錯(cuò)誤的本原BCH碼，其生成多項(xiàng)式糾單個(gè)錯(cuò)誤的本原BCH碼為漢明碼。表11－13給出了n<511的本原BCH碼。

11－14給出了部分非本原BCH碼?，F(xiàn)在是55頁\一共有72頁\編輯于星期四BCH碼例子糾正3個(gè)錯(cuò)誤，碼長為15的BCH碼 解：n=15,m=4查表11-12得，

23 37 07m1(D)m3(D)m5(D)

這是(15,5)碼。

現(xiàn)在是56頁\一共有72頁\編輯于星期四重要的BCH碼

(23,12)表11－14中最重要的非本原BCH碼是(23,12)

稱為格雷碼，碼距為7，能糾正3個(gè)錯(cuò)誤。 生成多項(xiàng)式它是一個(gè)完備碼在實(shí)際通信系統(tǒng)中，所要求的n、k并不是碼表中所推薦的值，在這時(shí)我們可以采用縮短或擴(kuò)展的方式加以修正，也就是通過增加信息符號或校驗(yàn)符號來增加碼組長度，或減少信息和校驗(yàn)位來減少碼組長度?，F(xiàn)在是57頁\一共有72頁\編輯于星期四BCH碼如BCH碼的碼長為奇數(shù)，而有時(shí)需要偶數(shù)碼長，這時(shí)可以在原BCH碼生成多項(xiàng)式中乘以（D+1)因子，從而得到（n+1,k）擴(kuò)展BCH碼，這時(shí)相當(dāng)于在原BCH碼上加一個(gè)全校驗(yàn)位，從而將碼距增加1，這時(shí)的碼字不具有循環(huán)性。如果BCH碼不是2m-1或它的因式，這時(shí)可以采用縮短的方式，去掉s位信息，(n-s,k-s)

縮短BCH碼現(xiàn)在是58頁\一共有72頁\編輯于星期四RS碼Reed-Solomon非二進(jìn)制BCH碼，輸入以符號來考慮假定每組有K個(gè)符號，每個(gè)符號用m比特，輸入信息將是K×m比特。RS碼一般寫成（n,k,d）最小碼距現(xiàn)在是59頁\一共有72頁\編輯于星期四RS碼RS碼適合于糾正突發(fā)錯(cuò)誤，糾正的錯(cuò)誤圖樣有對于一個(gè)長度為符號的RS碼，每個(gè)符號都可以看成是有限域中的一個(gè)元素，如RS碼的最小碼距為d符號，則生成多項(xiàng)式現(xiàn)在是60頁\一共有72頁\編輯于星期四第十一章差錯(cuò)控制編碼

§11.1基本概念§11.2分組碼

§11.3循環(huán)碼

§11.4BCH碼

§11.5糾正和檢測突發(fā)錯(cuò)誤的分組碼

§11.6糾錯(cuò)碼的誤碼性能現(xiàn)在是61頁\一共有72頁\編輯于星期四§11.5糾正和檢測突發(fā)錯(cuò)誤的分組碼

－交織碼interleaved在水平垂直監(jiān)督碼中將信息碼排列成方陣，然后對行和列分別進(jìn)行檢驗(yàn)，可以達(dá)到檢測突發(fā)錯(cuò)誤的目的。如果方陣中行碼是能糾t個(gè)隨機(jī)錯(cuò)誤，交織后能糾t個(gè)長度為i的突發(fā)錯(cuò)誤。i稱為交織深度?，F(xiàn)在是62頁\一共有72頁\編輯于星期四如果每行能糾正b個(gè)突發(fā)錯(cuò)誤，用上面的同樣方法，構(gòu)成方陣，可以糾正突發(fā)長度為bi個(gè)突發(fā)錯(cuò)誤。通常把i稱為交織深度現(xiàn)在是63頁\一共有72頁\編輯于星期四循環(huán)碼構(gòu)成交織碼采用循環(huán)碼構(gòu)成交織碼時(shí)，可以不采用方陣就能實(shí)現(xiàn)編碼。假設(shè)交織碼每行為循環(huán)碼，其生成多項(xiàng)式為，可以除盡，如交織深度為其交織碼為,其生成多項(xiàng)式為可以除盡，所以 也是循環(huán)碼。

現(xiàn)在是64頁\一共有72頁\編輯于星期四循環(huán)碼構(gòu)成交織碼(續(xù))如，循環(huán)碼(7,4)，其生成多項(xiàng)式為 構(gòu)成交織深度為3的(21,12)交織碼。 交織碼的生成多項(xiàng)式為 它也是循環(huán)碼，可以用循環(huán)碼的方式構(gòu)成。在發(fā)送端可以不排成方陣，但是在譯碼時(shí)，必須將碼元排列成陣列，然后分別獨(dú)立的對每行碼字進(jìn)行譯