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

1、9.1 概述概述n誤碼分類誤碼分類u噪聲引入的隨機(jī)誤碼，均勻分布噪聲引入的隨機(jī)誤碼，均勻分布u由干擾、快衰由干擾、快衰a落引起的突發(fā)誤碼落引起的突發(fā)誤碼n如何減少誤碼？如何減少誤碼？u從信源編碼看，誤碼引起的性能惡化盡可能小，從信源編碼看，誤碼引起的性能惡化盡可能小，容錯(cuò)技術(shù)容錯(cuò)技術(shù)u從傳輸看，可采用抗干擾能力強(qiáng)的調(diào)制方式，信從傳輸看，可采用抗干擾能力強(qiáng)的調(diào)制方式，信道特性不理想可采用均衡。特別需要差錯(cuò)控制技道特性不理想可采用均衡。特別需要差錯(cuò)控制技術(shù)。數(shù)字通信中，要求誤碼率術(shù)。數(shù)字通信中，要求誤碼率108以下，必須采以下，必須采用差錯(cuò)控制。用差錯(cuò)控制。9.1.1 差錯(cuò)控制分類差錯(cuò)控制分類 需

2、要雙向信道，和前向信道有相同的通信容。u引入較大的停頓（不實(shí)時(shí)）。引入較大的停頓（不實(shí)時(shí)）。u可以糾正任何錯(cuò)誤?？梢约m正任何錯(cuò)誤。分組存儲(chǔ)發(fā)收收發(fā)kIkI1.1. 反饋檢驗(yàn)法反饋檢驗(yàn)法2. 檢錯(cuò)重發(fā)法（檢錯(cuò)重發(fā)法（ARQ）u自動(dòng)請(qǐng)求重發(fā)自動(dòng)請(qǐng)求重發(fā)u也需要反向信道，但容量可以降低，也需要反向信道，但容量可以降低，也會(huì)引入停頓也會(huì)引入停頓檢錯(cuò)編碼存儲(chǔ)發(fā)收收發(fā)kIkI檢錯(cuò)譯碼3. 前向糾錯(cuò)（前向糾錯(cuò)（FEC）u不需要雙向信道不需要雙向信道u不會(huì)引入停頓不會(huì)引入停頓u靠糾錯(cuò)編碼靠糾錯(cuò)編碼9.1.2 差錯(cuò)控制編碼的基本原理差錯(cuò)控制編碼的基本原理n如用三位二進(jìn)制編碼來代表八個(gè)字母如用三位二進(jìn)制編碼來代表

3、八個(gè)字母000 A100E001 B101F010C110G011D111Hu不管哪一位發(fā)生錯(cuò)誤，都會(huì)使傳輸字母錯(cuò)誤不管哪一位發(fā)生錯(cuò)誤，都會(huì)使傳輸字母錯(cuò)誤n如用三位字母傳四個(gè)字母如用三位字母傳四個(gè)字母000 A011B101 C110Du發(fā)生一位錯(cuò)誤，準(zhǔn)用碼字將變成禁用碼字，接發(fā)生一位錯(cuò)誤，準(zhǔn)用碼字將變成禁用碼字，接收端就能知道出錯(cuò)，但是不能糾錯(cuò)。收端就能知道出錯(cuò)，但是不能糾錯(cuò)。差錯(cuò)控制編碼差錯(cuò)控制編碼n如用三位字母傳二個(gè)字母如用三位字母傳二個(gè)字母000 000 A A111111B Bu檢三個(gè)錯(cuò)誤，糾正一個(gè)錯(cuò)誤。檢三個(gè)錯(cuò)誤，糾正一個(gè)錯(cuò)誤。n結(jié)論結(jié)論u具有檢錯(cuò)或糾錯(cuò)的碼組，其所用的比特具有檢錯(cuò)

4、或糾錯(cuò)的碼組，其所用的比特?cái)?shù)必須大于信息碼組原來的比特?cái)?shù)數(shù)必須大于信息碼組原來的比特?cái)?shù) 引入余度。引入余度。碼重、碼距碼重、碼距n碼重碼重(weight)v一一個(gè)碼組中個(gè)碼組中“1”1”的數(shù)目的數(shù)目n碼距碼距(distance)v兩個(gè)碼組之間對(duì)應(yīng)位置上兩個(gè)碼組之間對(duì)應(yīng)位置上1 1、0 0不同的位數(shù)，不同的位數(shù)，又叫漢明又叫漢明(Hamming)(Hamming)距。距。10 1 1 0 碼重：碼重：301 1 0 0 2 距離：距離：3檢錯(cuò)、糾錯(cuò)能力檢錯(cuò)、糾錯(cuò)能力1) 為檢查出為檢查出 個(gè)錯(cuò)誤，要求最小碼距為個(gè)錯(cuò)誤，要求最小碼距為2) 為糾正為糾正 個(gè)錯(cuò)誤，要求最小碼距為個(gè)錯(cuò)誤，要求最小碼距為

5、3) 為糾正為糾正 個(gè)錯(cuò)誤，同時(shí)檢查出個(gè)錯(cuò)誤，同時(shí)檢查出 個(gè)錯(cuò)個(gè)錯(cuò)誤，要求最小碼距為誤，要求最小碼距為lmin1dl min21dtmin1()dltlt ttl9.1.3. 差錯(cuò)控制編碼分類差錯(cuò)控制編碼分類n按功能分按功能分v檢錯(cuò)碼檢錯(cuò)碼 v糾錯(cuò)碼糾錯(cuò)碼v糾刪碼糾刪碼（發(fā)現(xiàn)不可糾正的錯(cuò)誤時(shí)，可發(fā)出指示或刪除）（發(fā)現(xiàn)不可糾正的錯(cuò)誤時(shí)，可發(fā)出指示或刪除）n按信息碼元和監(jiān)督碼元之間的校驗(yàn)關(guān)系分按信息碼元和監(jiān)督碼元之間的校驗(yàn)關(guān)系分v線性碼線性碼v非線性碼非線性碼n按信息碼元和監(jiān)督碼元之間的約束方式分按信息碼元和監(jiān)督碼元之間的約束方式分v分組碼分組碼v卷積碼卷積碼香農(nóng)理香農(nóng)理 糾錯(cuò)碼的理論基礎(chǔ)糾錯(cuò)碼的

6、理論基礎(chǔ)n香農(nóng)定理香農(nóng)定理u存在噪聲干擾的信道，若信道容量為存在噪聲干擾的信道，若信道容量為C C，只要發(fā)送端以，只要發(fā)送端以低于低于C C的速率的速率R R發(fā)送信息（發(fā)送信息（R R為輸入道編碼器的二進(jìn)制碼為輸入道編碼器的二進(jìn)制碼元速率），則一定存在一種編碼方式，使編碼的錯(cuò)誤元速率），則一定存在一種編碼方式，使編碼的錯(cuò)誤概率隨著碼長概率隨著碼長n n的增加將按指數(shù)下降道任一的值，即的增加將按指數(shù)下降道任一的值，即n結(jié)論結(jié)論u如碼長及發(fā)送信息速率一定，可以通過增大信如碼長及發(fā)送信息速率一定，可以通過增大信道容量，使道容量，使P P減小。減小。u如在信道容量及發(fā)送信息速率一定，可以通過如在信道容

7、量及發(fā)送信息速率一定，可以通過增加碼長，使錯(cuò)誤概率下降。增加碼長，使錯(cuò)誤概率下降。nE RPe分組碼分組碼n表示：表示： (n,k)n : 幀長幀長k/n : 編碼效率編碼效率n特點(diǎn)特點(diǎn)u監(jiān)督碼只用來監(jiān)督本幀中的信息位監(jiān)督碼只用來監(jiān)督本幀中的信息位n分類分類u線性碼線性碼 信息碼與監(jiān)督碼之間為線性關(guān)系信息碼與監(jiān)督碼之間為線性關(guān)系u非線性碼非線性碼 不存在線性關(guān)系不存在線性關(guān)系 奇偶監(jiān)督碼奇偶監(jiān)督碼n偶監(jiān)督偶監(jiān)督n奇監(jiān)督奇監(jiān)督n如果以上關(guān)系被破壞，則出現(xiàn)錯(cuò)誤，因此能檢查如果以上關(guān)系被破壞，則出現(xiàn)錯(cuò)誤，因此能檢查出奇數(shù)個(gè)錯(cuò)誤，但不能檢測偶數(shù)個(gè)錯(cuò)誤。出奇數(shù)個(gè)錯(cuò)誤，但不能檢測偶數(shù)個(gè)錯(cuò)誤。最小碼距為最小

8、碼距為 dmin=2n這種碼檢錯(cuò)能力不高，采用什么方法提高呢？這種碼檢錯(cuò)能力不高，采用什么方法提高呢？01221 aaaaann信息位監(jiān)督位12100nnaaaa12101nnaaaa水平奇偶監(jiān)督碼和水平垂直監(jiān)督碼水平奇偶監(jiān)督碼和水平垂直監(jiān)督碼n又叫又叫 二維奇偶監(jiān)督碼二維奇偶監(jiān)督碼n水平奇偶監(jiān)督碼水平奇偶監(jiān)督碼u檢碼字按行排成方陣，每行采用奇偶監(jiān)督碼，檢碼字按行排成方陣，每行采用奇偶監(jiān)督碼，發(fā)送時(shí)按列的順序傳送，接收時(shí)仍將碼字排列發(fā)送時(shí)按列的順序傳送，接收時(shí)仍將碼字排列成發(fā)送時(shí)方陣形式，然后按行進(jìn)行奇偶校驗(yàn)。成發(fā)送時(shí)方陣形式，然后按行進(jìn)行奇偶校驗(yàn)。u在不增加冗余度時(shí)，不僅發(fā)現(xiàn)某一行上奇數(shù)個(gè)在

9、不增加冗余度時(shí)，不僅發(fā)現(xiàn)某一行上奇數(shù)個(gè)錯(cuò)誤，而且也能發(fā)現(xiàn)不大于方陣行數(shù)的突發(fā)錯(cuò)錯(cuò)誤，而且也能發(fā)現(xiàn)不大于方陣行數(shù)的突發(fā)錯(cuò)誤。誤。n水平垂直奇偶監(jiān)督碼水平垂直奇偶監(jiān)督碼u不僅對(duì)行進(jìn)行奇偶校驗(yàn)，而且也對(duì)列進(jìn)行奇偶不僅對(duì)行進(jìn)行奇偶校驗(yàn)，而且也對(duì)列進(jìn)行奇偶校驗(yàn)。校驗(yàn)。等比碼等比碼n在碼長一定時(shí)，在碼長一定時(shí)，“1”碼和碼和“0”碼的比例恒碼的比例恒定。已用于電報(bào)傳輸中。定。已用于電報(bào)傳輸中。n五中取三五中取三0101111001表示十位數(shù)字，表示十位數(shù)字，C53=10種許用碼組。種許用碼組。分組碼分組碼 (1)n分組碼的監(jiān)督方程分組碼的監(jiān)督方程n矩陣形式矩陣形式654265316430000aaaaaa

10、aaaaaa6543210111010001101010010110010Taaaaaaa 9.2 線性分組碼線性分組碼分組碼分組碼 (2)n監(jiān)督矩陣監(jiān)督矩陣nH矩陣稱為典型形式，各行一定是線性無關(guān)的。矩陣稱為典型形式，各行一定是線性無關(guān)的。而一個(gè)非典型形式的經(jīng)過運(yùn)算可以化成典型形而一個(gè)非典型形式的經(jīng)過運(yùn)算可以化成典型形式，通過監(jiān)督矩陣可以知道監(jiān)督碼和信息碼的式，通過監(jiān)督矩陣可以知道監(jiān)督碼和信息碼的監(jiān)督關(guān)系。監(jiān)督關(guān)系。11101001101010,1011001r rr kr rHPI分組碼分組碼 (3)n生成矩陣生成矩陣 ，通過生成矩陣可以得到生成碼組。，通過生成矩陣可以得到生成碼組。n如果

11、輸入碼組為如果輸入碼組為 001110001110100110,00101010001011kGIQTQP10001110100110001 1001 1001 1 1 1000101010001011AG分組碼分組碼 (4)n由這種方式得到的生成矩陣稱為典型生成矩陣，由這種方式得到的生成矩陣稱為典型生成矩陣，由它產(chǎn)生的分組碼必定為系統(tǒng)碼，也就是信息碼由它產(chǎn)生的分組碼必定為系統(tǒng)碼，也就是信息碼字保持不變，監(jiān)督位附加其后，每行一定是線性字保持不變，監(jiān)督位附加其后，每行一定是線性無關(guān)的，每行都是一個(gè)生成碼組。無關(guān)的，每行都是一個(gè)生成碼組。00110011 110漢明碼漢明碼漢明碼監(jiān)督位為漢明碼監(jiān)督

12、位為 位，因此它可以組成位，因此它可以組成 種可種可能情況，其中一個(gè)為無錯(cuò)。因此可以監(jiān)督碼位能情況，其中一個(gè)為無錯(cuò)。因此可以監(jiān)督碼位共共 要糾正一個(gè)錯(cuò)誤，必須滿足要糾正一個(gè)錯(cuò)誤，必須滿足最小碼距最小碼距v如果如果 r r 位監(jiān)督位所組成的校正子碼組與誤碼圖位監(jiān)督位所組成的校正子碼組與誤碼圖樣一一對(duì)應(yīng)，這種碼組稱為完備碼（取等號(hào)時(shí)）樣一一對(duì)應(yīng)，這種碼組稱為完備碼（取等號(hào)時(shí)）r2r21r21, 21rrnkr 即min3d擴(kuò)展?jié)h明碼擴(kuò)展?jié)h明碼n如果在漢明碼基礎(chǔ)上，再加上一位對(duì)所有碼字如果在漢明碼基礎(chǔ)上，再加上一位對(duì)所有碼字進(jìn)行校驗(yàn)的監(jiān)督位進(jìn)行校驗(yàn)的監(jiān)督位u監(jiān)督碼字由監(jiān)督碼字由 r r 位增加到位增

13、加到 r r+1 +1 位位u信息位不變信息位不變v碼長碼長 碼結(jié)構(gòu)碼結(jié)構(gòu)v糾糾 1 位錯(cuò)，檢測位錯(cuò)，檢測 2 位錯(cuò)位錯(cuò)v如如 （8，4），（），（16，11）rn2) 12 ,2( rrr擴(kuò)展?jié)h明碼矩陣擴(kuò)展?jié)h明碼矩陣如如 (7,4) (8,4)1111000EHH縮短漢明碼縮短漢明碼n(n,k) (n-s, k-s)n如如 (15,11) (12,8)監(jiān)督矩陣監(jiān)督矩陣 Hs 是將原是將原 H 的前的前 3 列列 去掉去掉n縮短漢明碼的最小碼距至少和原來碼的碼縮短漢明碼的最小碼距至少和原來碼的碼距相同，因?yàn)楸O(jiān)督位沒有變。距相同，因?yàn)楸O(jiān)督位沒有變。n能糾能糾 t 個(gè)錯(cuò)誤的個(gè)錯(cuò)誤的(n,k)應(yīng)滿足

14、應(yīng)滿足取等號(hào)時(shí)為完備碼取等號(hào)時(shí)為完備碼n不同結(jié)構(gòu)的線性碼其糾錯(cuò)能力不同，能力和不同結(jié)構(gòu)的線性碼其糾錯(cuò)能力不同，能力和dmin 有關(guān)，有關(guān)，dmin 越大越好。越大越好。120221trn ktinnnniCCCC 最小碼距界限最小碼距界限n上界：上界： 漢明界，漢明界， 普洛特金界普洛特金界n下界：下界： 吉爾伯特界吉爾伯特界n問題：問題： 給定碼長與編碼效率，尋找給定碼長與編碼效率，尋找 dminn例：例： dmin=5, 碼長碼長=63 的分組碼設(shè)計(jì)的分組碼設(shè)計(jì)從漢明界得，從漢明界得，因此信息位最多可以取因此信息位最多可以取263min022(5,2)rn kiiCd糾 個(gè)錯(cuò)誤22017,

15、11n krnk 最小監(jiān)督位數(shù)63 11 52 上界最小碼距界限最小碼距界限n通過吉爾伯特界求下界通過吉爾伯特界求下界n線性碼線性碼 k 越接近越接近 52， 效率越高。效率越高。20225,635,63 15 48drn riniCdnr信息位 下界4852k9.3 循環(huán)碼循環(huán)碼 (Cyclic code) n1957 年發(fā)現(xiàn)年發(fā)現(xiàn)n特點(diǎn)特點(diǎn)u線性分組碼線性分組碼u循環(huán)性循環(huán)性任一許用碼字經(jīng)過循環(huán)移位后，得任一許用碼字經(jīng)過循環(huán)移位后，得到的碼組仍為一個(gè)許用碼組到的碼組仍為一個(gè)許用碼組v如如 是循環(huán)碼的一許用碼組是循環(huán)碼的一許用碼組 v則則 也是一許用碼組也是一許用碼組 6543210()a

16、a a a a a a0654321()a a a a a a a碼多項(xiàng)式表示碼多項(xiàng)式表示n碼組碼組碼多項(xiàng)式碼多項(xiàng)式u碼組u碼多項(xiàng)式n左移一位左移一位n左移左移 位位1210()nnAaaa a121210( )()nnnnA DaDaDa Da(1011100)A 6432()A DDDDD2101()nnAaa a a(1)122301()()nnnnnADaDaDa Da121()nininin iAaaaa ( )12121()()innnininin iADaDaDaDa i循環(huán)碼性質(zhì)循環(huán)碼性質(zhì)n 為許用碼組，則為許用碼組，則 也是許用碼組也是許用碼組n性質(zhì)性質(zhì)若若 是長度為是長度為

17、n的循環(huán)碼組，則的循環(huán)碼組，則 在按模在按模 進(jìn)行運(yùn)算后，也是一個(gè)循環(huán)碼組，也進(jìn)行運(yùn)算后，也是一個(gè)循環(huán)碼組，也就是就是 用用 多項(xiàng)式除后所得之余式，多項(xiàng)式除后所得之余式，即為所求的碼組。即為所求的碼組。()A D()()iiA DD A D( )iD A D1nD ()A D( )iD A D1nD 循環(huán)碼例子循環(huán)碼例子碼組碼組左移左移 3 位位去除去除 得余式得余式如如 左移左移 3 位后，得位后，得 是許用碼組是許用碼組656510()A Da Da Da Da398436510()D A Da Da Da Da D71D 653254a Da Da Da1100101A 0101110循

18、環(huán)碼生成多項(xiàng)式循環(huán)碼生成多項(xiàng)式g(D)ng(D) 是是 D的的 (n-k) 次即次即r 次多項(xiàng)式次多項(xiàng)式n信息多項(xiàng)式為信息多項(xiàng)式為M(D),k 位，位，(k-1)次多項(xiàng)式次多項(xiàng)式111( )10 1rrrig DDgDg Dg或1110()kkM DmDm DmnTheo.一個(gè)一個(gè)(n,k) 的二進(jìn)制循環(huán)碼可以看成是唯一的二進(jìn)制循環(huán)碼可以看成是唯一由它的生成多項(xiàng)式產(chǎn)生，即由它的生成多項(xiàng)式產(chǎn)生，即J如如(7,3)循環(huán)碼，循環(huán)碼，n=7, k=3, r=4J如果信息位為如果信息位為 010010， M(D)=DM(D)=D 生成碼為生成碼為 01110100111010()( ) ()A DM d

19、 g D432()1g DDDD543()() ()A DM D g DDDDD循環(huán)碼生成多項(xiàng)式循環(huán)碼生成多項(xiàng)式g(D)生成矩陣生成矩陣 G(D)n由于由于 k 位信息位共有位信息位共有 個(gè)碼組，都可用此法產(chǎn)生，個(gè)碼組，都可用此法產(chǎn)生，如果現(xiàn)有信息碼如果現(xiàn)有信息碼 生成生成 k 個(gè)碼字，且這個(gè)碼字，且這 k 個(gè)碼字都線性無關(guān)，用這個(gè)碼字都線性無關(guān)，用這 k 個(gè)碼字作為一個(gè)矩陣個(gè)碼字作為一個(gè)矩陣G 的的 k行行 構(gòu)成生成矩陣構(gòu)成生成矩陣 G(D)120()()()1kkMDDMDDMDD12()()()1()kkDg DDg DG Dg D2k循環(huán)碼循環(huán)碼n(7,3) 循環(huán)碼循環(huán)碼432()1g

20、 DDDD24326542432543432432(1)()(1)1 (1)1DDDDDDDDG DDDDDDDDDDDDDDD1110100()01110100011010G D生成矩陣和監(jiān)督矩陣生成矩陣和監(jiān)督矩陣n這樣構(gòu)成的循環(huán)碼并非是系統(tǒng)碼這樣構(gòu)成的循環(huán)碼并非是系統(tǒng)碼n系統(tǒng)碼的生成矩陣典型形式系統(tǒng)碼的生成矩陣典型形式 n非系統(tǒng)碼非系統(tǒng)碼 系統(tǒng)碼系統(tǒng)碼u生成矩陣生成矩陣u監(jiān)督矩陣監(jiān)督矩陣kGIQrTIQH100010011100100111001010110001011100010111)(DGkIQ101011001001110011101H非系統(tǒng)碼非系統(tǒng)碼 系統(tǒng)碼系統(tǒng)碼n系統(tǒng)碼的碼多項(xiàng)

21、式為系統(tǒng)碼的碼多項(xiàng)式為n例如，例如，(7,4)碼，碼，1011()()()n kA DM DDr D32()1g DDD3()1M DDD3643()M DDDDD()()()()()n kDM Dr Dq Dg Dg D32326436535454221DDDDDDDDDDDDDDDD2()r DD監(jiān)督位為10111011100非系統(tǒng)碼非系統(tǒng)碼 系統(tǒng)碼系統(tǒng)碼12()()()1()kkDg DDg DG Dg D1122()()()1()()()krnkrnrn kn in iDDrDDDrDG DDrDrDg DD是除所得的余式1110100()01110100011010G D尋找生成多項(xiàng)

22、式尋找生成多項(xiàng)式nTheo. 循環(huán)碼的生成多項(xiàng)式必須能除盡循環(huán)碼的生成多項(xiàng)式必須能除盡 h(D)是監(jiān)督多項(xiàng)式是監(jiān)督多項(xiàng)式n例：要構(gòu)成例：要構(gòu)成(7,3)循環(huán)碼，求循環(huán)碼，求g(D). 解：解：g(D)應(yīng)為應(yīng)為4階階 v生成生成(7,6)(7,6)循環(huán)碼循環(huán)碼v生成生成(7,1)(7,1)循環(huán)碼循環(huán)碼1nD 1() ()nDg D h D 7323324234321(1)(1)(1)()(1)(1)1()(1)(1)1DDDDDDg DDDDDDDg DDDDDDDD 或()1g DD323()(1)(1)g DDDDD循環(huán)碼的編碼器循環(huán)碼的編碼器n原理：按系統(tǒng)碼的生成方式原理：按系統(tǒng)碼的生成方

23、式以以(7,4)碼為例碼為例 ()()()n kA DM DDr D32()1g DDD()()()()()n kDM Dr Dq Dg Dg DD1D2+D3+輸入校驗(yàn)位碼字輸出循環(huán)碼的譯碼器循環(huán)碼的譯碼器n譯碼比編碼復(fù)雜得多譯碼比編碼復(fù)雜得多n譯碼三步譯碼三步u伴隨式伴隨式S S的計(jì)算的計(jì)算u由由S S得到錯(cuò)誤圖樣得到錯(cuò)誤圖樣u糾正糾正伴隨式的計(jì)算伴隨式的計(jì)算n發(fā)送碼組發(fā)送碼組 n接收碼組接收碼組n誤差碼組誤差碼組v校正子只與校正子只與 E E 有關(guān)，根本是計(jì)算校正子有關(guān)，根本是計(jì)算校正子120nnAaaa120nnbbbbBAE120nnElll0,1,iiiiiilablab如果則則B

24、AETTTTT()SB HAEHAHEHEH9.4 BCH碼碼n即約多項(xiàng)式即約多項(xiàng)式u一個(gè)一個(gè) m m 次多項(xiàng)式不能被二元域上任何二次數(shù)小于次多項(xiàng)式不能被二元域上任何二次數(shù)小于的，但大于的，但大于0 0的多項(xiàng)式除盡，如的多項(xiàng)式除盡，如 是即約的。是即約的。n本原多項(xiàng)式本原多項(xiàng)式u若m次多項(xiàng)式P(x)除盡的 的最小正整數(shù) n 滿足 ，就稱為本原的。u如 能除盡 ，但除不盡 的。u如 ： 是即約的，但不是本原的，因它能除盡 。521DD1nx 21mn 4( )1p xxx151x115n1nx 4321xxxx51x 9.4.1 本原循環(huán)碼本原循環(huán)碼n由本原多項(xiàng)式構(gòu)成的碼稱為本原碼。由本原多項(xiàng)式

25、構(gòu)成的碼稱為本原碼。n特點(diǎn)特點(diǎn)u碼長為碼長為u它的生成多項(xiàng)式是由若干它的生成多項(xiàng)式是由若干m m階或以階或以m m的因的因子為最高階的多項(xiàng)式相乘而構(gòu)成。子為最高階的多項(xiàng)式相乘而構(gòu)成。v要判定要判定(n,k) (n,k) 的循環(huán)碼是否存在，只需要判的循環(huán)碼是否存在，只需要判斷斷 n-k n-k 階的生成多項(xiàng)式是否能由階的生成多項(xiàng)式是否能由 D Dn n+1+1的因的因式構(gòu)成。式構(gòu)成。21,mm為正整數(shù)循環(huán)碼例子循環(huán)碼例子n生成多項(xiàng)式的階次為生成多項(xiàng)式的階次為 r, 該生成多項(xiàng)式是否是該生成多項(xiàng)式是否是 的因此。的因此。n一個(gè)一個(gè)m階即約多項(xiàng)式一定能除盡階即約多項(xiàng)式一定能除盡n如，如，m5，共有，

26、共有6個(gè)個(gè)5階即約多項(xiàng)式。階即約多項(xiàng)式。n再加上再加上 因子，因子， 是以上是以上7個(gè)多項(xiàng)式的乘積。個(gè)多項(xiàng)式的乘積。( , ),21,21mmn k nrnkk 1nD 2111mnDD 525432542535321543111111DDDDDDDDDDDDDDDDDDDD(1)D 311D9.4.2 BCH 碼的生成多項(xiàng)式碼的生成多項(xiàng)式n如果循環(huán)碼形式的形式為如果循環(huán)碼形式的形式為v 為糾錯(cuò)個(gè)數(shù)為糾錯(cuò)個(gè)數(shù) ， 為最小多項(xiàng)式，為最小多項(xiàng)式， 為最小公倍數(shù)為最小公倍數(shù)最小碼距最小碼距 碼長為碼長為 的的BCH碼稱為碼稱為 本本BCH碼（俠義）碼（俠義） 碼長為碼長為 則稱為非本原則稱為非本原B

27、CH碼碼1321()LCM(),(),(),tg Dm D m DmD()im DLCMt21mn 21mn 21dtBCH 碼碼n由于由于g(D)有有t個(gè)因式，且每個(gè)因式的最高次為個(gè)因式，且每個(gè)因式的最高次為m，因此監(jiān)督碼元最多有因此監(jiān)督碼元最多有mt位。位。n對(duì)于糾對(duì)于糾t 個(gè)錯(cuò)誤的本原個(gè)錯(cuò)誤的本原BCH碼，其生成多項(xiàng)式碼，其生成多項(xiàng)式n糾單個(gè)錯(cuò)誤的本原糾單個(gè)錯(cuò)誤的本原BCH碼字為漢明碼。碼字為漢明碼。u表表11111313給出了給出了 n5n5的本原的本原BCHBCH碼。碼。 1114給出了部分非本原給出了部分非本原BCH碼。碼。1321()()()()tg Dm D m DmDBCH

28、碼例子碼例子n糾正糾正 3 個(gè)錯(cuò)誤，碼長為個(gè)錯(cuò)誤，碼長為15的的BCH碼碼解：解：n=15, m=5 查表查表11-12得，得，233707 這是這是(15,5)碼。碼。 13544322108542( )( )( )( )(1)(1)(1)1g Dm D m D m DDDDDDDDDDDDDDD 重要的重要的BCH碼碼 (23,12)n表表1114中最重要的中最重要的BCH碼是碼是(23,12)稱為格雷碼，碼間為稱為格雷碼，碼間為7，能糾正，能糾正3個(gè)錯(cuò)誤。個(gè)錯(cuò)誤。生成多項(xiàng)式生成多項(xiàng)式n在實(shí)際通信系統(tǒng)中，所要求的在實(shí)際通信系統(tǒng)中，所要求的n、k并不是碼表中所推薦并不是碼表中所推薦的值，在這

29、時(shí)我們可以采用縮短或擴(kuò)展的方式加以修正，的值，在這時(shí)我們可以采用縮短或擴(kuò)展的方式加以修正，也就是通過增加信息符號(hào)或校驗(yàn)符號(hào)來增加碼組長度，或也就是通過增加信息符號(hào)或校驗(yàn)符號(hào)來增加碼組長度，或減少信息和校驗(yàn)位來減少碼組長度。減少信息和校驗(yàn)位來減少碼組長度。119765()1g DDDDDDDBCH碼碼n如如 BCH碼的碼長為奇數(shù)，而有時(shí)需要偶數(shù)碼長，碼的碼長為奇數(shù)，而有時(shí)需要偶數(shù)碼長，這時(shí)可以在原這時(shí)可以在原BCH碼生成多項(xiàng)式中乘以（碼生成多項(xiàng)式中乘以（D+1)因子，從而得到（因子，從而得到（n+1,k）擴(kuò)展）擴(kuò)展BCH碼，這時(shí)相碼，這時(shí)相當(dāng)于在原當(dāng)于在原BCH碼上加一個(gè)全校驗(yàn)位，從而將碼距碼上

30、加一個(gè)全校驗(yàn)位，從而將碼距增加增加1，這時(shí)的碼字不具有循環(huán)性。，這時(shí)的碼字不具有循環(huán)性。n如果如果BCH碼不是碼不是2m-1或它的因式，這時(shí)可以采用或它的因式，這時(shí)可以采用縮短的方式，去掉縮短的方式，去掉s位信息，位信息，(n-s , k-s)RS碼碼 Reed-Solomonn非二進(jìn)制非二進(jìn)制BCH碼，輸入以符號(hào)來考慮碼，輸入以符號(hào)來考慮n假定每組有假定每組有 K 個(gè)符號(hào)，每個(gè)符號(hào)用個(gè)符號(hào)，每個(gè)符號(hào)用m比特，輸比特，輸入信息將是入信息將是 Km 比特。比特。RS碼碼nRS碼適合于糾正突發(fā)錯(cuò)誤，糾正的錯(cuò)誤圖樣有碼適合于糾正突發(fā)錯(cuò)誤，糾正的錯(cuò)誤圖樣有n對(duì)于一個(gè)長度為對(duì)于一個(gè)長度為 符號(hào)的符號(hào)的RS碼，每個(gè)符號(hào)碼，每個(gè)符號(hào)都可以看成是有限域都可以看成是有限域 中的一個(gè)元素，如中的一個(gè)元素，如RS碼的最小碼距為碼的最小碼距為d符號(hào)，則生成多項(xiàng)式符號(hào)，則生成多項(xiàng)式111(1)1(3)13(21)21btmbtmbtimii總長度為比特的單個(gè)突發(fā)總長度為比特的 個(gè)突發(fā)總長度為比特的 個(gè)突發(fā)21m(2 )mGRs231()()()()()dg DDDDD()imGR是中 的 一 個(gè) 元 素9.5 糾正和檢測突發(fā)錯(cuò)誤的分組碼糾正和檢測突發(fā)錯(cuò)誤的分組碼交織碼交織碼interlea