第十一章 差錯(cuò)控制編碼

1、第十一章 差錯(cuò)控制編碼l11.1 基本概念l11.2 分組碼 l11.3 循環(huán)碼 l11.4 BCH碼 l11.5 糾正和檢測(cè)突發(fā)錯(cuò)誤的分組碼 l11.6 糾錯(cuò)碼的誤碼性能l誤碼分類噪聲引入的隨機(jī)誤碼，均勻分布由干擾、快衰落引起的突發(fā)誤碼l如何減少誤碼？從信源編碼看，誤碼引起的性能惡化盡可能小，容錯(cuò)技術(shù)從傳輸看，可采用抗干擾能力強(qiáng)的調(diào)制方式，信道特性不理想可采用均衡。特別需要差錯(cuò)控制技術(shù)。數(shù)字通信中，要求誤碼率108以下，必須采用差錯(cuò)控制。需要雙向信道，和前向信道有相同的通信容。引入較大的停頓（不實(shí)時(shí)）。可以糾正任何錯(cuò)誤。分組存儲(chǔ)發(fā)收收發(fā)kIkI控制自動(dòng)請(qǐng)求重發(fā)也需要反向信道，但容量可以降低，

2、也會(huì)引入停頓檢錯(cuò)編碼存儲(chǔ)發(fā)收收發(fā)kIkI檢錯(cuò)譯碼不需要雙向信道不會(huì)引入停頓靠糾錯(cuò)編碼l如用三位二進(jìn)制編碼來代表八個(gè)字母000 A100E001 B101F010C110G011D111H不管哪一位發(fā)生錯(cuò)誤，都會(huì)使傳輸字母錯(cuò)誤l如用三位字母?jìng)魉膫€(gè)字母000 A011B101 C110D發(fā)生一位錯(cuò)誤，準(zhǔn)用碼字將變成禁用碼字，接收端就能知道出錯(cuò)，但是不能糾錯(cuò)。l如用三位字母?jìng)鞫€(gè)字母000 A111B檢三個(gè)錯(cuò)誤，糾正一個(gè)錯(cuò)誤。l結(jié)論具有檢錯(cuò)或糾錯(cuò)的碼組，其所用的比特?cái)?shù)必須大于信息碼組原來的比特?cái)?shù)引入多余度。l碼重(weight)l一個(gè)碼組中“1”的數(shù)目l碼距(distance)l兩個(gè)碼組之間對(duì)應(yīng)位置

3、上1、0不同的位數(shù)，又叫漢明(Hamming)距。10 1 1 0 碼重：301 1 00 2 距離：3l 為檢查出 個(gè)錯(cuò)誤，要求最小碼距為l 為糾正 個(gè)錯(cuò)誤，要求最小碼距為l 為糾正 個(gè)錯(cuò)誤，同時(shí)檢查出 個(gè)錯(cuò)誤，要求最小碼距為 e1minedt12min td)(1mintetedetl按功能分l檢錯(cuò)碼 l糾錯(cuò)碼l糾刪碼（發(fā)現(xiàn)不可糾正的錯(cuò)誤時(shí)，可發(fā)出指示或刪除）l按信息碼元和監(jiān)督碼元之間的校驗(yàn)關(guān)系分l線性碼l非線性碼l按信息碼元和監(jiān)督碼元之間的約束方式分l分組碼l卷積碼l糾錯(cuò)碼建立在香農(nóng)理論基礎(chǔ)上l香農(nóng)定理存在噪聲干擾的信道，若信道容量為C，只要發(fā)送端以低于C的速率R發(fā)送信息（R為輸入到編碼

4、器的二進(jìn)制碼元速率），則一定存在一種編碼方式，使編碼的錯(cuò)誤概率隨著碼長(zhǎng)n的增加將按指數(shù)下降到任一的值，即l結(jié)論如碼長(zhǎng)及發(fā)送信息速率一定，可以通過增大信道容量，使P減小。如在信道容量及發(fā)送信息速率一定，可以通過增加碼長(zhǎng)，使錯(cuò)誤概率下降。RnEePl表示： (n,k)n : 幀長(zhǎng)k/n : 編碼效率l特點(diǎn)監(jiān)督碼只用來監(jiān)督本幀中的信息位l分類線性碼 信息碼與監(jiān)督碼之間為線性關(guān)系非線性碼 不存在線性關(guān)系kn-k信息位監(jiān)督位nl偶監(jiān)督l奇監(jiān)督l如果以上關(guān)系被破壞，則出現(xiàn)錯(cuò)誤，因此能檢查出奇數(shù)個(gè)錯(cuò)誤，但不能檢測(cè)偶數(shù)個(gè)錯(cuò)誤。最小碼距為 dmin=2l這種碼檢錯(cuò)能力不高，采用什么方法提高呢？01221 aaa

5、aann信息位監(jiān)督位00121aaaann10121aaaannl又叫 二維奇偶監(jiān)督碼l水平奇偶監(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ò)誤。l水平垂直奇偶監(jiān)督碼不僅對(duì)行進(jìn)行奇偶校驗(yàn)，而且也對(duì)列進(jìn)行奇偶校驗(yàn)。l在碼長(zhǎng)一定時(shí)，“1”碼和“0”碼的比例恒定。已用于電報(bào)傳輸中。l五中取三0101111001表示十位數(shù)字，C53=10種許用碼組。l11.1 基本概念l11.2 分組碼 l11.3 循環(huán)碼 l11.4 BCH碼 l11.5

6、糾正和檢測(cè)突發(fā)錯(cuò)誤的分組碼 l11.6 糾錯(cuò)碼的誤碼性能l漢明碼：能糾一位錯(cuò)誤(7,4)監(jiān)督位信息位0123456,aaaaaaa346035614562aaaaaaaaaaaa監(jiān)督方程：在接收端，按如下規(guī)律運(yùn)算034631356224561aaaaSaaaaSaaaaS無錯(cuò)錯(cuò)碼位置0001110111011100010101006543210111aaaaaaaSSS）。稱為校正子（或伴隨式、因此應(yīng)糾為：錯(cuò)誤。，知道，運(yùn)算后得到如收到的結(jié)果，就可以糾錯(cuò)。、根據(jù)32133213210001011100000011SSSaSSSSSSl分組碼的監(jiān)督方程l矩陣形式000034613562456aa

7、aaaaaaaaaa0001001101010101100101110123456Taaaaaaal監(jiān)督矩陣lH矩陣稱為典型形式，各行一定是線性無關(guān)的。而一個(gè)非典型形式的經(jīng)過運(yùn)算可以化成典型形式，通過監(jiān)督矩陣可以知道監(jiān)督碼和信息碼的監(jiān)督關(guān)系。rrkrrrIPH,100110101010110010111l生成矩陣 ，通過生成矩陣可以得到生成碼組。l如果輸入碼組為 00111101010111111000010000100001,QIGkTPQ 0111100110101011111100001000010000111001100GA110 00110011l由這種方式得到的生成矩陣稱為典型生成

8、矩陣，由它產(chǎn)生的分組碼必定為系統(tǒng)碼，也就是信息碼字保持不變，監(jiān)督位附加其后，每行一定是線性無關(guān)的，每行都是一個(gè)生成碼組。漢明碼監(jiān)督位為 位，因此它可以組成 個(gè)可能情況，其中一個(gè)為無錯(cuò)。因此可以監(jiān)督碼位共 要糾正一個(gè)錯(cuò)誤，必須滿足最小碼距l(xiāng)如果 r 位監(jiān)督位所組成的校正子碼組與誤碼圖樣一一對(duì)應(yīng)，這種碼組稱為完備碼（取等號(hào)時(shí)）rr212 r12 ,12rknrr即3mindl如果在漢明碼基礎(chǔ)上，再加上一位對(duì)所有碼字進(jìn)行校驗(yàn)的監(jiān)督位監(jiān)督碼字由 r 位增加到 r+1 位信息位不變l碼長(zhǎng) 碼結(jié)構(gòu)l糾 1 位錯(cuò)，檢測(cè) 2 位錯(cuò)l如 （8，4），（16，11） rn2) 12 ,2( rrr如 (7,4)

9、(8,4)0001111HHEl(n,k) (n-s, k-s)l如 (15,11) (12,8)監(jiān)督矩陣 Hs 是將原 H 的前 3 列 去掉l縮短漢明碼的最小碼距至少和原來碼的碼距相同，因?yàn)楸O(jiān)督位沒有變。l能糾 t 個(gè)錯(cuò)誤的(n,k)應(yīng)滿足取等號(hào)時(shí)為完備碼l不同結(jié)構(gòu)的線性碼其糾錯(cuò)能力不同，能力和dmin 有關(guān)，dmin 越大越好。tiintnnnknrCCCC021122l上界： 漢明界， 普洛特金界l下界： 吉爾伯特界l問題： 給定碼長(zhǎng)與編碼效率，尋找 dminl例： dmin=5, 碼長(zhǎng)=63 的分組碼設(shè)計(jì)從漢明界得，因此信息位最多可以取)2, 5(22min2063個(gè)錯(cuò)誤糾dCiik

10、nr最小監(jiān)督位數(shù)11,20172knrkn上界521163l通過吉爾伯特界求下界l線性碼 k 越接近 52， 效率越高。下界信息位481563, 563, 52220rndCdiinrnr5248 kl11.1 基本概念l11.2 分組碼 l11.3 循環(huán)碼 l11.4 BCH碼 l11.5 糾正和檢測(cè)突發(fā)錯(cuò)誤的分組碼 l11.6 糾錯(cuò)碼的誤碼性能l1957 年發(fā)現(xiàn)l特點(diǎn)線性分組碼循環(huán)性任一許用碼字經(jīng)過循環(huán)移位后，得到的碼組仍為一個(gè)許用碼組l如 是循環(huán)碼的一許用碼組 l則 也是一許用碼組 )(0123456aaaaaaa)(1234560aaaaaaal碼組碼多項(xiàng)式碼組碼多項(xiàng)式l左移一位l左移

11、 位)(1012nnaaaaA)()(012211aDaDaDaDAnnnn)1011100(A2346)(DDDDDA)()(102312)1(nnnnnaDaDaDaDA)(0121aaaaAnn)()(12211)(ininninniniaDaDaDaDAi)(121)(ininininiaaaaAl 為許用碼組，則 也是許用碼組l性質(zhì)若 是長(zhǎng)度為n的循環(huán)碼組，則 在按模 進(jìn)行運(yùn)算后，也是一個(gè)循環(huán)碼組，也就是 用 多項(xiàng)式除后所得之余式，即為所求的碼組。 )(DA)()()(DADDAii)(DADi1nD)(DA)(DADi1nD碼組左移 3 位去除 得余式如 左移 3 位后，得 是許用

12、碼組015566)(aDaDaDaDA304185963)(DaDaDaDaDAD17D455263aDaDaDa1100101A0101110lg(D) 是 D的 (n-k) 次即r 次多項(xiàng)式l信息多項(xiàng)式為M(D),k 位，(k-1)次多項(xiàng)式101)(111或irrrgDgDgDDg0111)(mDmDmDMkkl定理.一個(gè)(n,k) 的二進(jìn)制循環(huán)碼可以看成是唯一由它的生成多項(xiàng)式產(chǎn)生，即J如(7,3)循環(huán)碼，n=7, k=3, r=4J如果信息位為 010， M(D)=D 生成碼為 0111010)()()(DgDMDA1)(234DDDDgDDDDDgDMDA345)()()(l由于 k

13、位信息位共有 個(gè)碼組，都可用此法產(chǎn)生，如果現(xiàn)有信息碼 生成 k 個(gè)碼字，且這 k 個(gè)碼組都線性無關(guān)，用這 k 個(gè)碼組作為一個(gè)矩陣G 的 k行 構(gòu)成生成矩陣 G(D)1)()()(021DDMDDMDDMkk)(1)()()(21DgDgDDgDDGkkk2稱為循環(huán)碼的生成矩陣多項(xiàng)式l(7,3) 循環(huán)碼1)(234DDDDg1) 1(1) 1() 1()(23434524562342342342DDDDDDDDDDDDDDDDDDDDDDDG010110001011100010111G生成矩陣NK l這樣構(gòu)成的循環(huán)碼并非是系統(tǒng)碼l系統(tǒng)碼的生成矩陣典型形式 l非系統(tǒng)碼 系統(tǒng)碼生成矩陣監(jiān)督矩陣QIG

14、krTIQH100010011100100111001010110001011100010111GkIQ1000110010001100101110001101H列行NKl系統(tǒng)碼的碼多項(xiàng)式為l例如，(7,4)碼，1011)()()(DrDDMDAkn1)(23DDDg1)(3DDDM3463)(DDDDDM)()()()()(DgDrDqDgDMDkn22454535623346231DDDDDDDDDDDDDDDD 2)(DDr監(jiān)督位為10111001011l(7,3)碼)(1)()()(21DgDgDDgDDGkk所得的余式除是ininknrnrknrkDDgDrDrDDrDDDrDDDG

15、)()()(1)()()(2211101110011100100111001Gl 循環(huán)碼的生成多項(xiàng)式必須能除盡 h(D)是監(jiān)督多項(xiàng)式，是 K階多項(xiàng)式l例：要構(gòu)成(7,3)循環(huán)碼，求g(D). 解：g(D)應(yīng)為4階 都能生成(7,3)l生成(7,6)循環(huán)碼l生成(7,1)循環(huán)碼 1nD)()(1DhDgDn1) 1)(1()(1) 1)(1()() 1)(1)(1(1234324233237DDDDDDDgDDDDDDDgDDDDDD或 1)( DDg) 1)(1()(323DDDDDgl原理：按系統(tǒng)碼的生成方式：將信息碼多項(xiàng)式升(n-k)次冪后，再除生成多項(xiàng)式，然后將余式置于升冪后的信息多項(xiàng)式

16、之后以(7,4)碼為例 )()()(DrDDMDAkn1)(23DDDg)()()()()(DgDrDqDgDMDknD1D2+D3+輸入校驗(yàn)位碼字輸出l譯碼比編碼復(fù)雜得多l(xiāng)譯碼三步伴隨式S的計(jì)算由S得到錯(cuò)誤圖樣糾正l發(fā)送碼組 l接收碼組l誤差碼組l校正子只與 E 有關(guān)，根本是計(jì)算校正子021aaaAnn021bbbbnnEAB021eeeEnn iiiiiibaebae則則如果, 1, 0EABTTTTT)(EHEHAHHEAHBSl生成多項(xiàng)式 g(D)去除接收碼字B(D)(Mod)()(DgDBDSl11.1 基本概念l11.2 分組碼 l11.3 循環(huán)碼 l11.4 BCH碼 l11.5

17、 糾正和檢測(cè)突發(fā)錯(cuò)誤的分組碼 l11.6 糾錯(cuò)碼的誤碼性能l特點(diǎn)：它也屬于循環(huán)碼，具有糾多個(gè)隨機(jī)錯(cuò)誤的能力，構(gòu)造容易。因此由碼的最小距離，可以很快得到碼的生成多項(xiàng)式l即約多項(xiàng)式一個(gè) m 次多項(xiàng)式不能被二元域上任何次數(shù)小于m的，但大于0的多項(xiàng)式除盡，如 是即約的。l本原多項(xiàng)式若m次多項(xiàng)式P(x)除盡的 的最小正整數(shù) n 滿足 ，就稱為本原的。如 能除盡 ，但除不盡 的 。如 ： 是即約的，但不是本原的，因它能除盡 。 125 DD1nx12mn1)(4xxxp115x151 n1nx1234xxxx15xl由本原多項(xiàng)式構(gòu)成的碼稱為本原碼。l特點(diǎn)碼長(zhǎng)為它的生成多項(xiàng)式是由若干m階或以m的因子為最高階

18、的多項(xiàng)式相乘而構(gòu)成。l要判定(n,k) 的循環(huán)碼是否存在，只需要判斷 n-k 階的生成多項(xiàng)式是否能由 Dn+1的因式構(gòu)成。 為正整數(shù)mm, 12l生成多項(xiàng)式的階次為 r, 該生成多項(xiàng)式是否是 的因此。l一個(gè)m階即約多項(xiàng)式一定能除盡l如，m5，共有6個(gè)5階即約多項(xiàng)式。l再加上 因子， 是以上7個(gè)多項(xiàng)式的乘積。 kknrnknmm12, 12),(1nD1112mDDn111111345123535245234525DDDDDDDDDDDDDDDDDDDD ) 1(D131Dl表11-12表示了m12的即約多項(xiàng)式l在表中多項(xiàng)式的系數(shù)是用8進(jìn)制表示的，而且反多項(xiàng)式?jīng)]有表示 如 m=5, 45, 75

19、, 67 100101 111101 110111l如果循環(huán)碼的生成多項(xiàng)式具有如下形式l 為糾錯(cuò)個(gè)數(shù) ， 為最小多項(xiàng)式， 為最小公倍數(shù)，由這種方式生成的循環(huán)碼是BCH碼最小碼距 碼長(zhǎng)為 的BCH碼稱為 本原BCH碼（狹義BCH碼） 碼長(zhǎng)為 則稱為非本原BCH碼 ),(),(),(LCM)(1231DmDmDmDgt)(DmiLCMt 12mn12mn12 tdl由于g(D)有t個(gè)因式，且每個(gè)因式的最高次為m，因此監(jiān)督碼元最多有mt位。l對(duì)于糾t 個(gè)錯(cuò)誤的本原BCH碼，其生成多項(xiàng)式l糾單個(gè)錯(cuò)誤的本原BCH碼為漢明碼。表1113給出了 n511的本原BCH碼。 1114給出了部分非本原BCH碼。)

20、()()()(1231DmDmDmDgtl糾正 3 個(gè)錯(cuò)誤，碼長(zhǎng)為15的BCH碼解：n=15, m=4 查表11-12得， 23 37 07 m1(D) m3(D) m5(D) 這是(15,5)碼。 1) 1)(1)(1()()()()(24581022344531DDDDDDDDDDDDDDDmDmDmDgl表1114中最重要的非本原BCH碼是(23,12)稱為格雷碼，碼距為7，能糾正3個(gè)錯(cuò)誤。生成多項(xiàng)式 它是一個(gè)完備碼l在實(shí)際通信系統(tǒng)中，所要求的n、k并不是碼表中所推薦的值，在這時(shí)我們可以采用縮短或擴(kuò)展的方式加以修正，也就是通過增加信息符號(hào)或校驗(yàn)符號(hào)來增加碼組長(zhǎng)度，或減少信息和校驗(yàn)位來減少

21、碼組長(zhǎng)度。1)(567911DDDDDDDgl如 BCH碼的碼長(zhǎng)為奇數(shù)，而有時(shí)需要偶數(shù)碼長(zhǎng)，這時(shí)可以在原BCH碼生成多項(xiàng)式中乘以（D+1)因子，從而得到（n+1,k）擴(kuò)展BCH碼，這時(shí)相當(dāng)于在原BCH碼上加一個(gè)全校驗(yàn)位，從而將碼距增加1，這時(shí)的碼字不具有循環(huán)性。l如果BCH碼不是2m-1或它的因式，這時(shí)可以采用縮短的方式，去掉s位信息，(n-s , k-s) 縮短BCH碼l非二進(jìn)制BCH碼，輸入以符號(hào)來考慮l假定每組有 K 個(gè)符號(hào)，每個(gè)符號(hào)用m比特，輸入信息將是 Km 比特。RS碼一般寫成（n,k,d） 最小碼距l(xiāng)RS碼適合于糾正突發(fā)錯(cuò)誤，糾正的錯(cuò)誤圖樣有l(wèi)對(duì)于一個(gè)長(zhǎng)度為 符號(hào)的RS碼，每個(gè)符

22、號(hào)都可以看成是有限域 中的一個(gè)元素，如RS碼的最小碼距為d符號(hào)，則生成多項(xiàng)式個(gè)突發(fā)比特的總長(zhǎng)度為個(gè)突發(fā)比特的總長(zhǎng)度為比特的單個(gè)突發(fā)總長(zhǎng)度為iimitbmtbmtb12) 12(23)3(1) 1(11112m)2(mGF)()()()(132dDDDDDg中的一個(gè)元素是)(miGRl11.1 基本概念l11.2 分組碼 l11.3 循環(huán)碼 l11.4 BCH碼 l11.5 糾正和檢測(cè)突發(fā)錯(cuò)誤的分組碼 l11.6 糾錯(cuò)碼的誤碼性能l在水平垂直監(jiān)督碼中將信息碼排列成方陣，然后對(duì)行和列分別進(jìn)行檢驗(yàn)，可以達(dá)到檢測(cè)突發(fā)錯(cuò)誤的目的。l如果方陣中行碼是能糾 t 個(gè)隨機(jī)錯(cuò)誤，交織后能糾t個(gè)長(zhǎng)度為i的突發(fā)錯(cuò)誤。

23、i稱為交織深度。itl如果每行能糾正 b 個(gè)突發(fā)錯(cuò)誤，用上面的同樣方法，構(gòu)成方陣，可以糾正突發(fā)長(zhǎng)度為bi個(gè)突發(fā)錯(cuò)誤。l通常把i稱為交織深度ibl采用循環(huán)碼構(gòu)成交織碼時(shí)，可以不采用方陣就能實(shí)現(xiàn)編碼。l假設(shè)交織碼每行為 循環(huán)碼，其生成多項(xiàng)式為 ， 可以除盡 ，如交織深度為 其交織碼為 ,其生成多項(xiàng)式為 可以除盡 ，所以 也是循環(huán)碼。 1nD),(kini)()(iiDgDg11)(niniDDi),(kn)(Dg)(Dg)(iDg),(kinil如，循環(huán)碼(7,4)， 其生成多項(xiàng)式為構(gòu)成交織深度為3 的(21,12)交織碼。交織碼的生成多項(xiàng)式為它也是循環(huán)碼，可以用循環(huán)碼的方式構(gòu)成。在發(fā)送端可以不排成方陣，