循環(huán)卷積交織編碼理論

循環(huán)卷積交織編碼理論第一頁，共五十四頁，2022年，8月28日9.1.1差錯控制分類需要雙向信道，和前向信道有相同的通信容。引入較大的停頓（不實時）?？梢约m正任何錯誤。1.反饋檢驗法第二頁，共五十四頁，2022年，8月28日2.檢錯重發(fā)法（ARQ）自動請求重發(fā)也需要反向信道，但容量可以降低，也會引入停頓第三頁，共五十四頁，2022年，8月28日3.前向糾錯（FEC）不需要雙向信道不會引入停頓靠糾錯編碼第四頁，共五十四頁，2022年，8月28日9.1.2差錯控制編碼的基本原理如用三位二進制編碼來代表八個字母

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

000 A 011 B 101 C 110 D發(fā)生一位錯誤，準用碼字將變成禁用碼字，接收端就能知道出錯，但是不能糾錯。第五頁，共五十四頁，2022年，8月28日差錯控制編碼如用三位字母傳二個字母

000 A 111 B 檢三個錯誤，糾正一個錯誤。結(jié)論具有檢錯或糾錯的碼組，其所用的比特數(shù)必須大于信息碼組原來的比特數(shù) －>引入余度。第六頁，共五十四頁，2022年，8月28日碼重、碼距碼重(weight)一個碼組中“1”的數(shù)目碼距(distance)兩個碼組之間對應位置上1、0不同的位數(shù)，又叫漢明(Hamming)距。

10110碼重：3 011002距離：3第七頁，共五十四頁，2022年，8月28日檢錯、糾錯能力為檢查出

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

01011 11001

表示十位數(shù)字，C53=10種許用碼組。第十四頁，共五十四頁，2022年，8月28日分組碼(1)分組碼的監(jiān)督方程矩陣形式9.2線性分組碼第十五頁，共五十四頁，2022年，8月28日分組碼(2)監(jiān)督矩陣H矩陣稱為典型形式，各行一定是線性無關(guān)的。而一個非典型形式的經(jīng)過運算可以化成典型形式，通過監(jiān)督矩陣可以知道監(jiān)督碼和信息碼的監(jiān)督關(guān)系。第十六頁，共五十四頁，2022年，8月28日分組碼(3)生成矩陣

，通過生成矩陣可以得到生成碼組。如果輸入碼組為0011第十七頁，共五十四頁，2022年，8月28日分組碼(4)由這種方式得到的生成矩陣稱為典型生成矩陣，由它產(chǎn)生的分組碼必定為系統(tǒng)碼，也就是信息碼字保持不變，監(jiān)督位附加其后，每行一定是線性無關(guān)的，每行都是一個生成碼組。第十八頁，共五十四頁，2022年，8月28日漢明碼 漢明碼監(jiān)督位為位，因此它可以組成種可能情況，其中一個為無錯。因此可以監(jiān)督碼位共 要糾正一個錯誤，必須滿足 最小碼距如果r位監(jiān)督位所組成的校正子碼組與誤碼圖樣一一對應，這種碼組稱為完備碼（取等號時）第十九頁，共五十四頁，2022年，8月28日擴展?jié)h明碼如果在漢明碼基礎上，再加上一位對所有碼字進行校驗的監(jiān)督位監(jiān)督碼字由r

位增加到

r+1位信息位不變碼長 碼結(jié)構(gòu)糾1位錯，檢測2位錯如（8，4），（16，11）第二十頁，共五十四頁，2022年，8月28日擴展?jié)h明碼矩陣如(7,4)－>(8,4)第二十一頁，共五十四頁，2022年，8月28日縮短漢明碼(n,k)－>(n-s,k-s)如(15,11)－>(12,8)

監(jiān)督矩陣Hs是將原H的前3列去掉縮短漢明碼的最小碼距至少和原來碼的碼距相同，因為監(jiān)督位沒有變。第二十二頁，共五十四頁，2022年，8月28日能糾t個錯誤的(n,k)應滿足

取等號時為完備碼不同結(jié)構(gòu)的線性碼其糾錯能力不同，能力和dmin有關(guān)，dmin越大越好。第二十三頁，共五十四頁，2022年，8月28日最小碼距界限上界：漢明界，普洛特金界下界：吉爾伯特界問題：給定碼長與編碼效率，尋找dmin例：dmin=5,碼長=63的分組碼設計

從漢明界得，

因此信息位最多可以取第二十四頁，共五十四頁，2022年，8月28日最小碼距界限通過吉爾伯特界求下界線性碼

k越接近52，效率越高。第二十五頁，共五十四頁，2022年，8月28日9.3循環(huán)碼(Cycliccode)

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

則也是一許用碼組

第二十六頁，共五十四頁，2022年，8月28日碼多項式表示碼組 碼多項式碼組碼多項式左移一位左移位第二十七頁，共五十四頁，2022年，8月28日循環(huán)碼性質(zhì)

為許用碼組，則也是許用碼組性質(zhì) 若是長度為n的循環(huán)碼組，則在按模進行運算后，也是一個循環(huán)碼組，也就是用多項式除后所得之余式，即為所求的碼組。第二十八頁，共五十四頁，2022年，8月28日循環(huán)碼例子碼組左移3位去除得余式如左移3位后，得是許用碼組第二十九頁，共五十四頁，2022年，8月28日循環(huán)碼生成多項式g(D)g(D)是D的(n-k)次即r次多項式信息多項式為M(D),k位，(k-1)次多項式第三十頁，共五十四頁，2022年，8月28日Theo.一個(n,k)的二進制循環(huán)碼可以看成是唯一由它的生成多項式產(chǎn)生，即如(7,3)循環(huán)碼，n=7,k=3,r=4如果信息位為010，M(D)=D

生成碼為0111010循環(huán)碼生成多項式g(D)第三十一頁，共五十四頁，2022年，8月28日生成矩陣G(D)由于k位信息位共有個碼組，都可用此法產(chǎn)生，如果現(xiàn)有信息碼生成k個碼字，且這k個碼字都線性無關(guān)，用這k個碼字作為一個矩陣G的k行構(gòu)成生成矩陣G(D)第三十二頁，共五十四頁，2022年，8月28日循環(huán)碼(7,3)循環(huán)碼第三十三頁，共五十四頁，2022年，8月28日生成矩陣和監(jiān)督矩陣這樣構(gòu)成的循環(huán)碼并非是系統(tǒng)碼系統(tǒng)碼的生成矩陣典型形式非系統(tǒng)碼系統(tǒng)碼生成矩陣監(jiān)督矩陣第三十四頁，共五十四頁，2022年，8月28日非系統(tǒng)碼系統(tǒng)碼系統(tǒng)碼的碼多項式為例如，(7,4)碼，1011第三十五頁，共五十四頁，2022年，8月28日非系統(tǒng)碼系統(tǒng)碼第三十六頁，共五十四頁，2022年，8月28日尋找生成多項式Theo.循環(huán)碼的生成多項式必須能除盡

h(D)是監(jiān)督多項式例：要構(gòu)成(7,3)循環(huán)碼，求g(D).

解：g(D)應為4階

生成(7,6)循環(huán)碼生成(7,1)循環(huán)碼第三十七頁，共五十四頁，2022年，8月28日循環(huán)碼的編碼器原理：按系統(tǒng)碼的生成方式 以(7,4)碼為例

第三十八頁，共五十四頁，2022年，8月28日循環(huán)碼的譯碼器譯碼比編碼復雜得多譯碼三步伴隨式S的計算由S得到錯誤圖樣糾正第三十九頁，共五十四頁，2022年，8月28日伴隨式的計算發(fā)送碼組接收碼組誤差碼組校正子只與E有關(guān)，根本是計算校正子第四十頁，共五十四頁，2022年，8月28日9.4BCH碼即約多項式一個m次多項式不能被二元域上任何二次數(shù)小于的，但大于0的多項式除盡，如是即約的。本原多項式若m次多項式P(x)除盡的的最小正整數(shù)n滿足，就稱為本原的。如能除盡，但除不盡的 。如：是即約的，但不是本原的，因它能除盡。第四十一頁，共五十四頁，2022年，8月28日9.4.1本原循環(huán)碼由本原多項式構(gòu)成的碼稱為本原碼。特點碼長為它的生成多項式是由若干m階或以m的因子為最高階的多項式相乘而構(gòu)成。要判定(n,k)的循環(huán)碼是否存在，只需要判斷n-k階的生成多項式是否能由Dn+1的因式構(gòu)成。第四十二頁，共五十四頁，2022年，8月28日循環(huán)碼例子生成多項式的階次為r,該生成多項式是否是的因此。一個m階即約多項式一定能除盡如，m＝5，共有6個5階即約多項式。再加上因子，是以上7個多項式的乘積。第四十三頁，共五十四頁，2022年，8月28日9.4.2BCH碼的生成多項式如果循環(huán)碼形式的形式為為糾錯個數(shù)，為最小多項式， 為最小公倍數(shù)最小碼距碼長為的BCH碼稱為本BCH碼（俠義）碼長為則稱為非本原BCH碼第四十四頁，共五十四頁，2022年，8月28日BCH碼由于g(D)有t個因式，且每個因式的最高次為m，因此監(jiān)督碼元最多有mt位。對于糾t個錯誤的本原BCH碼，其生成多項式糾單個錯誤的本原BCH碼字為漢明碼。表11－13給出了n<5的本原BCH碼。

11－14給出了部分非本原BCH碼。第四十五頁，共五十四頁，2022年，8月28日BCH碼例子糾正3個錯誤，碼長為15的BCH碼 解：n=15,m=5查表11-12得，

23 37 07

這是(15,5)碼。

第四十六頁，共五十四頁，2022年，8月28日重要的BCH碼(23,12)表11－14中最重要的BCH碼是(23,12)

稱為格雷碼，碼間為7，能糾正3個錯誤。 生成多項式在實際通信系統(tǒng)中，所要求的n、k并不是碼表中所推薦的值，在這時我們可以采用縮短或擴展的方式加以修正，也就是通過增加信息符號或校驗符號來增加碼組長度，或減少信息和校驗位來減少碼組長度。第四十七頁，共五十四頁，2022年，8月28日BCH碼如BCH碼的碼長為奇數(shù)，而有時需要偶數(shù)碼長，這時可以在原BCH碼生成多項式中乘以（D+1)因子，從而得到（n+1,k）擴展BCH碼，這時相當于在原BCH碼上加一個全校驗位，從而將碼距增加1，這時的碼字不具有循環(huán)性。如果BCH碼不是2m-1或它的因式，這時可以采用縮短的方式，去掉s位信息，(n-s,k-s)第四十八頁，共五十四頁，2022年，8月28日RS碼Reed-Solomon非二進制BCH碼，輸入以符號來考慮假定每組有K個符號，每個符號用m比特，輸入信息將是K×m比特。第四十九頁，共五十四頁，2022年，8月28日RS碼RS碼適合于糾正突發(fā)錯誤，糾正的錯誤圖樣有對于一個長度為符號的RS碼，每個符號都可以看成是有限域中的一個元素，如RS碼的最小碼距為d符號，則生成多項式第五十頁，共五十四頁，2022年，8月28日9.5糾正和檢測突發(fā)錯誤的分組碼

－交織碼interleaved在水平垂直監(jiān)督碼中將信息碼排列成方陣，然后對行和列分別進行檢驗，可以達到檢測突發(fā)錯誤的目的。如