糾突錯(cuò)誤碼課件

1、東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室第十三章糾突發(fā)錯(cuò)誤碼第十三章糾突發(fā)錯(cuò)誤碼東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室本章內(nèi)容提要本章內(nèi)容提要糾突發(fā)錯(cuò)誤碼的定義和基本性質(zhì)糾突發(fā)錯(cuò)誤碼的定義和基本性質(zhì)法爾碼法爾碼交錯(cuò)碼交錯(cuò)碼伯頓碼伯頓碼糾突發(fā)錯(cuò)誤卷積碼糾突發(fā)錯(cuò)誤卷積碼巖垂碼巖垂碼糾突發(fā)錯(cuò)誤循環(huán)碼的譯碼糾突發(fā)錯(cuò)誤循環(huán)碼的譯碼糾突發(fā)和隨機(jī)錯(cuò)誤碼糾突發(fā)和隨機(jī)錯(cuò)誤碼東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室 大部分實(shí)際信道如短波、散射、有線等信道中產(chǎn)生的大部分實(shí)際信道如短波、散射、有線等信道中產(chǎn)生的錯(cuò)誤是突發(fā)性的；某些數(shù)據(jù)存儲(chǔ)系統(tǒng)所產(chǎn)生的錯(cuò)誤，錯(cuò)誤是突發(fā)性的；某些數(shù)據(jù)存儲(chǔ)系統(tǒng)所產(chǎn)生的錯(cuò)誤，大部分也是突發(fā)性的，而不是隨機(jī)性的。大部分也

2、是突發(fā)性的，而不是隨機(jī)性的。 這些這些信道中所產(chǎn)生的錯(cuò)誤是突發(fā)錯(cuò)誤，或突發(fā)錯(cuò)誤與信道中所產(chǎn)生的錯(cuò)誤是突發(fā)錯(cuò)誤，或突發(fā)錯(cuò)誤與隨機(jī)錯(cuò)誤并存，通常稱這類信道為突發(fā)信道隨機(jī)錯(cuò)誤并存，通常稱這類信道為突發(fā)信道。 循環(huán)碼循環(huán)碼檢測突發(fā)錯(cuò)誤能力強(qiáng)，但糾錯(cuò)效果不大檢測突發(fā)錯(cuò)誤能力強(qiáng)，但糾錯(cuò)效果不大。 人們希望能設(shè)計(jì)出一類專門用作糾突發(fā)錯(cuò)誤的碼，這人們希望能設(shè)計(jì)出一類專門用作糾突發(fā)錯(cuò)誤的碼，這類碼稱為糾突發(fā)錯(cuò)誤碼。類碼稱為糾突發(fā)錯(cuò)誤碼。 這類碼在糾突發(fā)錯(cuò)誤時(shí)的效率應(yīng)比對(duì)付隨機(jī)錯(cuò)誤而設(shè)這類碼在糾突發(fā)錯(cuò)誤時(shí)的效率應(yīng)比對(duì)付隨機(jī)錯(cuò)誤而設(shè)計(jì)的碼要高計(jì)的碼要高，即對(duì)于給定的，即對(duì)于給定的n和和k， (n, k)有盡可能小的

3、有盡可能小的多余度，或者說多余度，或者說n k 盡可能小盡可能小。第第1313章糾突發(fā)錯(cuò)誤碼章糾突發(fā)錯(cuò)誤碼東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室定義定義13.1 長為長為b的突發(fā)是針對(duì)錯(cuò)誤圖樣來定義的突發(fā)是針對(duì)錯(cuò)誤圖樣來定義的：如果一個(gè)矢量的非零分量局限于的：如果一個(gè)矢量的非零分量局限于b個(gè)連續(xù)個(gè)連續(xù)數(shù)據(jù)位，且第一和最后一位是非零的，則數(shù)據(jù)位，且第一和最后一位是非零的，則稱該稱該矢量為一個(gè)長為矢量為一個(gè)長為b的突發(fā)的突發(fā)。一個(gè)線性碼如能糾正長為一個(gè)線性碼如能糾正長為b或更短的突發(fā)錯(cuò)誤，或更短的突發(fā)錯(cuò)誤，但不能糾正長為但不能糾正長為b+1的所有突發(fā)錯(cuò)誤，則的所有突發(fā)錯(cuò)誤，則稱此稱此碼是一個(gè)糾碼是一個(gè)糾b

4、長突發(fā)錯(cuò)誤碼，即該碼的糾錯(cuò)能長突發(fā)錯(cuò)誤碼，即該碼的糾錯(cuò)能力為力為b。 13.1糾突發(fā)錯(cuò)誤碼定義和基本性質(zhì)糾突發(fā)錯(cuò)誤碼定義和基本性質(zhì)13.1.1 定義定義 東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室 定理定理13.1 長長n的二元碼字中，突發(fā)長度不大于的二元碼字中，突發(fā)長度不大于b 的碼字的碼字的總數(shù)的總數(shù)N=2b-1(n+2 b) 。證明證明 在長為在長為n的二元碼字中，考慮的二元碼字中，考慮b為各種可能值的情為各種可能值的情況況 （突發(fā)字個(gè)數(shù)）如下：（突發(fā)字個(gè)數(shù)）如下：b = 0 1個(gè)個(gè) （0, 0, , 0） 1 n個(gè)個(gè) 2 n 1個(gè)個(gè) 3 2(n 2)個(gè)個(gè) bibibninnN212)2(2)1(2

5、113.1糾突發(fā)錯(cuò)誤碼定義和基本性質(zhì)糾突發(fā)錯(cuò)誤碼定義和基本性質(zhì)13.1.2 基本性質(zhì)基本性質(zhì) 證畢。證畢。東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室 定理定理13.2 一個(gè)一個(gè) (n, k) 線性分組碼，線性分組碼，能發(fā)現(xiàn)長度不大于能發(fā)現(xiàn)長度不大于b的錯(cuò)誤圖樣的條件是的錯(cuò)誤圖樣的條件是n k b 1 + lb(n + 2 b) 證明證明 由于對(duì)于所有的錯(cuò)誤圖樣，若由于對(duì)于所有的錯(cuò)誤圖樣，若s0則能被發(fā)現(xiàn)，則能被發(fā)現(xiàn)，(n, k) 線性分組碼的陪集數(shù)為線性分組碼的陪集數(shù)為(2n 2k )/2k = 2n k 1 相應(yīng)的，在陪集中總錯(cuò)誤圖樣數(shù)為相應(yīng)的，在陪集中總錯(cuò)誤圖樣數(shù)為長度長度 b的突發(fā)錯(cuò)誤圖樣：的突發(fā)錯(cuò)

6、誤圖樣： 2 b 1 (n + 2 b ) 所以所以2 n k 1 2 b 1 (n + 2 b ) 一般有一般有2n k 1 , n b所以所以 n k b 1 + lb(n + 2 b) （13.2） 或或 n k b 證畢。證畢。 13.1糾突發(fā)錯(cuò)誤碼定義和基本性質(zhì)糾突發(fā)錯(cuò)誤碼定義和基本性質(zhì)13.1.2 基本性質(zhì)基本性質(zhì) 東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室 定理定理13.3 一個(gè)（一個(gè)（n, k）線性碼能糾正所有長度）線性碼能糾正所有長度 b的突的突發(fā)錯(cuò)誤的充要條件是：長度發(fā)錯(cuò)誤的充要條件是：長度 2b的突發(fā)不是一個(gè)碼字。的突發(fā)不是一個(gè)碼字。證明證明假設(shè)存在一個(gè)長假設(shè)存在一個(gè)長 2b的突發(fā)的

7、突發(fā)v是一個(gè)碼字，則是一個(gè)碼字，則 v = u + w ，其中，其中 u、w都是長度都是長度 b的突發(fā)。的突發(fā)。 必要性必要性：若：若v是碼字，因任意一陪集只有一個(gè)錯(cuò)誤圖樣，則是碼字，因任意一陪集只有一個(gè)錯(cuò)誤圖樣，則u和和w必在同一陪集中。設(shè)必在同一陪集中。設(shè)u為陪集首，則陪集中每一個(gè)字的錯(cuò)誤都是為陪集首，則陪集中每一個(gè)字的錯(cuò)誤都是此陪集首，此陪集首，w必為不可糾錯(cuò)誤，否則不可能與必為不可糾錯(cuò)誤，否則不可能與u同在一個(gè)陪集。這同在一個(gè)陪集。這樣盡管樣盡管v是一是一“碼字碼字”，但它是一個(gè)錯(cuò)碼，與假設(shè)，但它是一個(gè)錯(cuò)碼，與假設(shè)v是一碼字矛盾，是一碼字矛盾，因此把因此把u作為陪集首來糾錯(cuò)也是無效的，

8、即它不能糾正所有長作為陪集首來糾錯(cuò)也是無效的，即它不能糾正所有長 b 的突發(fā)錯(cuò)誤。的突發(fā)錯(cuò)誤。 充分性：充分性：若長度若長度 2b的突發(fā)的突發(fā)v不是碼字，則不是碼字，則u、w不在同一陪集中，不在同一陪集中，若它們都是陪集首，則都是可以糾正的長若它們都是陪集首，則都是可以糾正的長 b 的突發(fā)錯(cuò)誤。的突發(fā)錯(cuò)誤。 13.1糾突發(fā)錯(cuò)誤碼定義和基本性質(zhì)糾突發(fā)錯(cuò)誤碼定義和基本性質(zhì)13.1.2 基本性質(zhì)基本性質(zhì) 東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室 定理定理13.4 糾正糾正b 長突發(fā)錯(cuò)誤碼的校驗(yàn)位數(shù)目至少是長突發(fā)錯(cuò)誤碼的校驗(yàn)位數(shù)目至少是2b + lb (n + 2 2b )。 證明證明根據(jù)定理根據(jù)定理13.1，

9、將其中的，將其中的b 換成換成2b，得，得 n k 2b 1 + lb(n + 2 2b) （13.3）證畢。）證畢。 由由n 2b 知知 lb(n+22b) 1 ，代入定理，代入定理13.4得得 n-k 2b 。 表述為：表述為：(1) 一個(gè)一個(gè)(n, k)線性分組碼，若要糾正所有長度線性分組碼，若要糾正所有長度 b的突發(fā)錯(cuò)誤，則應(yīng)的突發(fā)錯(cuò)誤，則應(yīng)n k 2b。 (2)（n, k）碼的糾突上限為）碼的糾突上限為 ，稱為賴格爾限。，稱為賴格爾限。 滿足賴格爾限的碼是最佳的。滿足賴格爾限的碼是最佳的。 (3) 比率比率z=2b/(n k)被用來衡量碼的糾突發(fā)錯(cuò)誤的效率，被用來衡量碼的糾突發(fā)錯(cuò)誤的

10、效率，最佳碼糾突發(fā)錯(cuò)誤的效率等于最佳碼糾突發(fā)錯(cuò)誤的效率等于1。 13.1糾突發(fā)錯(cuò)誤碼定義和基本性質(zhì)糾突發(fā)錯(cuò)誤碼定義和基本性質(zhì)13.1.2 基本性質(zhì)基本性質(zhì) 2knb東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室 定理定理13.5 （n, k）循環(huán)碼能檢測長）循環(huán)碼能檢測長 n k的任何突發(fā)錯(cuò)的任何突發(fā)錯(cuò)誤，誤，包括首尾相接包括首尾相接的突發(fā)錯(cuò)誤。的突發(fā)錯(cuò)誤。 證明：證明：設(shè)錯(cuò)誤圖樣設(shè)錯(cuò)誤圖樣e(x)是是長度長度 n k的突發(fā)錯(cuò)誤，則的突發(fā)錯(cuò)誤，則e(x)可表示為可表示為 e(x)=x jB(x)，0 j n 1 式中，式中， B(x)是次數(shù)是次數(shù) n k 1的多項(xiàng)式的多項(xiàng)式。 由于由于B(x)的次數(shù)小于循環(huán)碼

11、生成多項(xiàng)式的次數(shù)小于循環(huán)碼生成多項(xiàng)式g(x)的次數(shù)，因的次數(shù)，因此此B(x)不能為不能為g(x)所整除所整除。 又因?yàn)橛忠驗(yàn)間(x)是是xn 1的因式，因此的因式，因此g(x)與與x j互素互素。因此。因此g(x)也不能整除也不能整除x jB(x)。 因此，由此因此，由此e(x)產(chǎn)生的產(chǎn)生的伴隨式不為零伴隨式不為零。即一個(gè)。即一個(gè)(n, k)循循環(huán)碼能檢測長環(huán)碼能檢測長 n k的任何突發(fā)錯(cuò)誤。的任何突發(fā)錯(cuò)誤。13.1糾突發(fā)錯(cuò)誤碼定義和基本性質(zhì)糾突發(fā)錯(cuò)誤碼定義和基本性質(zhì)13.1.2 基本性質(zhì)基本性質(zhì) 東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室對(duì)于長度對(duì)于長度 n k的突發(fā)錯(cuò)誤圖樣，當(dāng)它的錯(cuò)誤局限在前的突發(fā)錯(cuò)

12、誤圖樣，當(dāng)它的錯(cuò)誤局限在前i位和后位和后l i位時(shí)，即位時(shí)，即出現(xiàn)首尾相接的錯(cuò)誤時(shí)出現(xiàn)首尾相接的錯(cuò)誤時(shí)，有，有13.1糾突發(fā)錯(cuò)誤碼定義和基本性質(zhì)糾突發(fā)錯(cuò)誤碼定義和基本性質(zhì)13.1.2 基本性質(zhì)基本性質(zhì) 11)()(1110000)(nnilnilniixexexexeexe如果將它乘以如果將它乘以 xl - i ,則則 111101)()(000)(liilililnilnilxexexexeexex由于它的由于它的次數(shù)小于次數(shù)小于g(x)的次數(shù)的次數(shù)，所以它的伴隨式不為零。，所以它的伴隨式不為零。又由于又由于xl - i與與g(x)互素，因此互素，因此g(x)不能整除不能整除e(x)，即，即

13、e(x)= f(x) g(x)+s(x)，而，而s(x) 0。所以。所以(n , k)循環(huán)碼也能檢測長度循環(huán)碼也能檢測長度 n k的首尾相接的突發(fā)錯(cuò)誤。證畢。的首尾相接的突發(fā)錯(cuò)誤。證畢。東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室法爾碼是最早也是最大的一類法爾碼是最早也是最大的一類用分析方法構(gòu)造用分析方法構(gòu)造出的糾單個(gè)突發(fā)錯(cuò)誤的二進(jìn)制循環(huán)碼出的糾單個(gè)突發(fā)錯(cuò)誤的二進(jìn)制循環(huán)碼。 由于可以根據(jù)不同的要求很方便地設(shè)計(jì)所由于可以根據(jù)不同的要求很方便地設(shè)計(jì)所需要的碼，譯碼也很簡單，因此法爾碼是一類需要的碼，譯碼也很簡單，因此法爾碼是一類比較實(shí)用的，也是比較實(shí)用的，也是最基本的糾單個(gè)突發(fā)錯(cuò)誤循最基本的糾單個(gè)突發(fā)錯(cuò)誤循環(huán)碼

14、環(huán)碼。13.2法爾碼法爾碼13.2.1 法爾碼的構(gòu)造法爾碼的構(gòu)造 東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室定義定義13.2 設(shè)設(shè)p(x)是是GF(2)上的上的m次既約多項(xiàng)式次既約多項(xiàng)式，令，令是使是使p(x) 整除整除x+1的最小整數(shù)，稱的最小整數(shù)，稱為為p(x)的的周期周期；令；令b是使是使b m且且2b 1不能被不能被整除的正整數(shù)，則整除的正整數(shù)，則由生成多項(xiàng)式由生成多項(xiàng)式g(x)=(x2b 1 +1) p(x) 生成的碼稱為法爾碼生成的碼稱為法爾碼。法爾碼能糾正法爾碼能糾正b長的突發(fā)錯(cuò)誤長的突發(fā)錯(cuò)誤碼的長度碼的長度n等于等于和和2b 1的最小公倍數(shù)，即的最小公倍數(shù)，即n=LCM2b 1, 碼的校驗(yàn)

15、位數(shù)是碼的校驗(yàn)位數(shù)是 m + 2b + 1。13.2法爾碼法爾碼13.2.1 法爾碼的構(gòu)造法爾碼的構(gòu)造 東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室證明證明 只要證明只要證明長度長度 b的任何突發(fā)都位于碼的不的任何突發(fā)都位于碼的不同陪集中同陪集中，這樣它們便能作為陪集首而成為可，這樣它們便能作為陪集首而成為可糾正的錯(cuò)誤圖樣。糾正的錯(cuò)誤圖樣。令令x iA(x)和和x jB(x)分別表示兩個(gè)長為分別表示兩個(gè)長為b1和和b2突發(fā)突發(fā)的多項(xiàng)式，且的多項(xiàng)式，且b1 b ，b2 b ，而，而 13.2法爾碼法爾碼13.2.1 法爾碼的構(gòu)造法爾碼的構(gòu)造 1111221( )1bbbA xxaxa x2221221( )1

16、bbbB xxbxb x東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室13.2法爾碼法爾碼13.2.1 法爾碼的構(gòu)造法爾碼的構(gòu)造 如果假定如果假定xiA(x)和和xjB(x)在碼的同一陪集中在碼的同一陪集中，那么多項(xiàng)式，那么多項(xiàng)式 v(x) = xiA(x)+xjB(x) (13.4)必是一個(gè)碼多項(xiàng)式必是一個(gè)碼多項(xiàng)式。不失一般，假定。不失一般，假定i j，用，用2b 1除除j i得得 (21)jiqbb (13.5)把式（把式（13.5）代入式（）代入式（13.4），那么），那么v (x)可表示為可表示為 021bb(13.6) 1)()()( )()()()( )()()()12()12()12(bqbib

17、ibbqbbibbqixxBxxBxxAxxBxxBxxBxxAxxBxxAxxv東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室13.2法爾碼法爾碼13.2.1 法爾碼的構(gòu)造法爾碼的構(gòu)造 根據(jù)假定根據(jù)假定v (x)為碼多項(xiàng)式，而循環(huán)碼的為碼多項(xiàng)式，而循環(huán)碼的生成多項(xiàng)式為生成多項(xiàng)式為 g(x) = (x2b 1 +1 ) p(x)，所以所以(x2b 1+1 )|v(x)。由于由于(x2b 1+1 )| xq(2b 1)+1 ，因此式，因此式( (13.6) )中的中的 或能被整除或等于零?；蚰鼙徽虻扔诹?。 ( )( )bA xx B x東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室13.2法爾碼法爾碼13.2.1 法爾碼的

18、構(gòu)造法爾碼的構(gòu)造 假定假定 (13.7) 令令D (x)的次數(shù)為的次數(shù)為d，那么，那么D (x) (x2b 1 +1 )的次數(shù)是的次數(shù)是2b 1+ d。因?yàn)?。因?yàn)锳 (x)的次數(shù)是的次數(shù)是b11，所以，所以 的次數(shù)的次數(shù)必定由必定由 的次數(shù)決定，而的次數(shù)決定，而 的次數(shù)是的次數(shù)是b+ +b21。由式（由式（13.7）可得）可得 b+ +b21= 2b 1+ d (13.8)根據(jù)假定根據(jù)假定b1 b ，b2 b ，所以由式（，所以由式（13.8）可得）可得b b1 + d (13.9)又因又因b11 0，由式，由式( (13.9) )可得可得b b11 + d ，故有，故有 b d (13.10

19、)21( )( )( )(1)bbA xx B xD x x( )( )bA xx B x( )bx B x( )( )bA xx B x東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室13.2法爾碼法爾碼13.2.1 法爾碼的構(gòu)造法爾碼的構(gòu)造 從式從式(13.10)可知可知 中有中有 這一項(xiàng)。因?yàn)檫@一項(xiàng)。因?yàn)?b 1b d ，故，故D(x)(x2b 1+1)不能有不能有 這一這一 項(xiàng)。項(xiàng)。 這與假設(shè)這與假設(shè) 相矛盾。相矛盾。所以必有所以必有D(x)=0和和 =0，這要求，這要求b =0和和A(x)=B(x) (13.11)由于由于b =0 ，根據(jù)，根據(jù)j i = q(2b 1)+ b可知可知 j i = q(

20、2b 1) (13.12)把式（把式（13.11）和（）和（13.12）代入式（）代入式（13.4）可得）可得( (13.13) ) ( )( )bA xx B xbxbx21( )( )( )(1)bbA xx B xD x x( )( )bA xx B x( )( )(1)j iv xx B x x東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室13.2法爾碼法爾碼13.2.1 法爾碼的構(gòu)造法爾碼的構(gòu)造 注意到注意到B(x)的次數(shù)小于的次數(shù)小于b，所以，所以 。因此，。因此，B(x)和和p(x)互素。已假定互素。已假定v(x)是碼多項(xiàng)式，所以是碼多項(xiàng)式，所以xj i +1必能被必能被p(x)整除，整除，ji

21、必為必為p(x)的周期的周期 的整數(shù)倍。但由式的整數(shù)倍。但由式(13.12)知，知，ji也是也是2b1的整數(shù)倍。由此，的整數(shù)倍。由此，ji必是必是n=LCM2b1, 的倍的倍數(shù)。顯然，因?yàn)閿?shù)。顯然，因?yàn)閖和和i都小于都小于n，所以這是不可能的。，所以這是不可能的。綜上所述，長度綜上所述，長度 b的兩個(gè)突發(fā)的兩個(gè)突發(fā)xiA(x)和和xjB(x)在同一個(gè)陪在同一個(gè)陪集中的假設(shè)是不對(duì)的。因此所有長度集中的假設(shè)是不對(duì)的。因此所有長度 b的突發(fā)都處在的突發(fā)都處在 g(x) = =(x2b 1+1)p(x)定義的定義的g(x)生成的法爾碼的不同陪集中，因而生成的法爾碼的不同陪集中，因而它們是可糾正的錯(cuò)誤圖

22、樣。由于碼是循環(huán)的，所以它亦能它們是可糾正的錯(cuò)誤圖樣。由于碼是循環(huán)的，所以它亦能糾正長度糾正長度 b的首尾相接的突發(fā)錯(cuò)誤。的首尾相接的突發(fā)錯(cuò)誤。 ( )( )B xbp xm 東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室 例例13.1 考慮既約多項(xiàng)式考慮既約多項(xiàng)式 p(x)=1+x2+x5 , 已知它是本原多已知它是本原多項(xiàng)式，項(xiàng)式，m= op(x)=5， 周期周期 =251=31；令；令b=5，可算得，可算得2b1=9不能整除不能整除 =31，故可構(gòu)造法爾碼，其生成多項(xiàng)，故可構(gòu)造法爾碼，其生成多項(xiàng)式為式為 ：碼長為：碼長為： n=LCM9,31=279 k = n (m + 2b 1 ) =279 14

23、=265所以該法爾碼是所以該法爾碼是 (279, 265) 循環(huán)碼，能糾長度循環(huán)碼，能糾長度 5的任的任何突發(fā)錯(cuò)誤。何突發(fā)錯(cuò)誤1)(1()(xxxxxxxxxg13.2法爾碼法爾碼13.2.1 法爾碼的構(gòu)造法爾碼的構(gòu)造 東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室 法爾碼的糾突發(fā)錯(cuò)誤的效率為法爾碼的糾突發(fā)錯(cuò)誤的效率為 若若b等于等于m，則有，則有 當(dāng)當(dāng)m的值較大時(shí)，的值較大時(shí)，z約等于約等于2/3。因此，相對(duì)于賴格爾限。因此，相對(duì)于賴格爾限而言，法爾碼的效率并不是很高。而言，法爾碼的效率并不是很高。 能夠糾正任何長度為能夠糾正任何長度為b或更少的突發(fā)錯(cuò)誤、并同時(shí)檢測或更少的突發(fā)錯(cuò)誤

24、、并同時(shí)檢測長為長為l b的任何突發(fā)的法爾碼，可用下式生成：的任何突發(fā)的法爾碼，可用下式生成： 該碼長度等于該碼長度等于和和b + l 1的最小公倍數(shù)。的最小公倍數(shù)。 122bmbz132mmz13.2法爾碼法爾碼13.2.2 法爾碼的性能法爾碼的性能 )() 1()(1xpxxglb東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室交錯(cuò)是一種非常交錯(cuò)是一種非常簡單簡單而又而又有效有效的構(gòu)造碼的構(gòu)造碼的方法，它可以大大提高糾隨機(jī)錯(cuò)誤碼的方法，它可以大大提高糾隨機(jī)錯(cuò)誤碼的糾突發(fā)錯(cuò)誤能力，可的糾突發(fā)錯(cuò)誤能力，可使抗較短使抗較短突發(fā)錯(cuò)突發(fā)錯(cuò)誤的碼誤的碼變成抗較長變成抗較長突發(fā)錯(cuò)誤的碼，使糾突發(fā)錯(cuò)誤的碼，使糾正正單個(gè)定段

25、單個(gè)定段突發(fā)錯(cuò)誤的碼突發(fā)錯(cuò)誤的碼變成糾多個(gè)定變成糾多個(gè)定段段突發(fā)錯(cuò)誤的碼。突發(fā)錯(cuò)誤的碼。這種方法所付出的這種方法所付出的代價(jià)代價(jià)是增加存儲(chǔ)設(shè)備是增加存儲(chǔ)設(shè)備和加大通信時(shí)延。和加大通信時(shí)延。13.3交錯(cuò)碼交錯(cuò)碼東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室 將將 個(gè)個(gè) (n, k) 碼的碼矢排成碼的碼矢排成 n的矩形陣列，每行一個(gè)的矩形陣列，每行一個(gè)碼矢，然后碼矢，然后按列送至通信信道按列送至通信信道，在收端恢復(fù)矩形陣列，在收端恢復(fù)矩形陣列的排列次序，就構(gòu)成交錯(cuò)度為的排列次序，就構(gòu)成交錯(cuò)度為 的交錯(cuò)碼。即給定一個(gè)的交錯(cuò)碼。即給定一個(gè) (n, k) 循環(huán)碼，用交錯(cuò)法將碼長擴(kuò)大循環(huán)碼，用交錯(cuò)法將碼長擴(kuò)大 倍，信息位

26、數(shù)目倍，信息位數(shù)目也擴(kuò)大了也擴(kuò)大了 倍，倍，構(gòu)成一個(gè)（構(gòu)成一個(gè)（ n, k）循環(huán)碼）循環(huán)碼，見圖，見圖13.1。 13.3 交錯(cuò)碼交錯(cuò)碼13.3.1 交錯(cuò)碼的編譯碼方法交錯(cuò)碼的編譯碼方法 nkk圖圖13.1 交錯(cuò)碼的編碼方法，其中交錯(cuò)碼的編碼方法，其中為交錯(cuò)度為交錯(cuò)度東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室實(shí)現(xiàn)交錯(cuò)碼的簡明方法是排出陣列，按行編碼和譯碼。一實(shí)現(xiàn)交錯(cuò)碼的簡明方法是排出陣列，按行編碼和譯碼。一般地說，這并不是最簡單的實(shí)現(xiàn)方法。般地說，這并不是最簡單的實(shí)現(xiàn)方法。最簡單的實(shí)現(xiàn)方法是基于這樣一個(gè)事實(shí)，即若最簡單的實(shí)現(xiàn)方法是基于這樣一個(gè)事實(shí)，即若原碼是循環(huán)原碼是循環(huán)的，則交錯(cuò)碼也是循環(huán)的的，則交錯(cuò)碼

27、也是循環(huán)的。如果原碼的生成多項(xiàng)式是如果原碼的生成多項(xiàng)式是g (x)，則交錯(cuò)碼的生成多項(xiàng)式是，則交錯(cuò)碼的生成多項(xiàng)式是g (x )。因此，可用。因此，可用移位寄存器完成編碼和糾錯(cuò)移位寄存器完成編碼和糾錯(cuò)。只要簡單地將原碼譯碼器的每個(gè)移位寄存器用只要簡單地將原碼譯碼器的每個(gè)移位寄存器用 級(jí)置換，級(jí)置換，即可根據(jù)原碼的譯碼器推導(dǎo)出交錯(cuò)碼的譯碼器，而不必改變即可根據(jù)原碼的譯碼器推導(dǎo)出交錯(cuò)碼的譯碼器，而不必改變其他連接。其他連接。所以，如果原碼譯碼器較簡單，則交錯(cuò)碼也同樣簡單，而所以，如果原碼譯碼器較簡單，則交錯(cuò)碼也同樣簡單，而對(duì)于短碼而言，原碼譯碼器通常是比較簡單的。對(duì)于短碼而言，原碼譯碼器通常是比較簡

28、單的。 13.3 交錯(cuò)碼交錯(cuò)碼13.3.1 交錯(cuò)碼的編譯碼方法交錯(cuò)碼的編譯碼方法 東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室交錯(cuò)碼的性能交錯(cuò)碼的性能（1）交錯(cuò)編碼）交錯(cuò)編碼使錯(cuò)誤分散使錯(cuò)誤分散，長，長 的任何突發(fā)無論從何處開始，的任何突發(fā)無論從何處開始，都至多只能影響每行中的一位。都至多只能影響每行中的一位。（2）當(dāng)且僅當(dāng)每行中的錯(cuò)誤圖樣是原（）當(dāng)且僅當(dāng)每行中的錯(cuò)誤圖樣是原（n, k）碼中可糾正的）碼中可糾正的圖樣時(shí)，此錯(cuò)誤圖樣圖樣時(shí)，此錯(cuò)誤圖樣對(duì)整個(gè)陣列來說才是可糾正的對(duì)整個(gè)陣列來說才是可糾正的。（3）若原碼能糾正）若原碼能糾正 b的任何單個(gè)突發(fā)，則交錯(cuò)碼能糾正的任何單個(gè)突發(fā)，則交錯(cuò)碼能糾正 b 的任何

29、單個(gè)突發(fā)，的任何單個(gè)突發(fā)，碼長擴(kuò)大碼長擴(kuò)大 倍，糾突能力也擴(kuò)大倍，糾突能力也擴(kuò)大 倍。倍。 若若 (n, k) 碼有最大可能的糾正突發(fā)錯(cuò)誤能力，即碼有最大可能的糾正突發(fā)錯(cuò)誤能力，即nk2b=0，則交錯(cuò)碼，則交錯(cuò)碼 ( n, k)也具有最大可能的糾正突發(fā)也具有最大可能的糾正突發(fā)錯(cuò)誤能力。交錯(cuò)具有最大糾正突發(fā)錯(cuò)誤能力的短碼，能夠錯(cuò)誤能力。交錯(cuò)具有最大糾正突發(fā)錯(cuò)誤能力的短碼，能夠構(gòu)成實(shí)際上任意長的、具有最大可能糾突發(fā)錯(cuò)誤能力的碼。構(gòu)成實(shí)際上任意長的、具有最大可能糾突發(fā)錯(cuò)誤能力的碼。13.3 交錯(cuò)碼交錯(cuò)碼13.3.2 交錯(cuò)碼的性能交錯(cuò)碼的性能 東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室13.3 交錯(cuò)碼交錯(cuò)碼13.

30、3.2 交錯(cuò)碼的性能交錯(cuò)碼的性能 （4）若）若原碼是循環(huán)的原碼是循環(huán)的，其生成多項(xiàng)式為，其生成多項(xiàng)式為g(x)，則，則交錯(cuò)碼也交錯(cuò)碼也是循環(huán)的是循環(huán)的，且生成多項(xiàng)式為，且生成多項(xiàng)式為g (x )。 證明證明 設(shè)經(jīng)設(shè)經(jīng) 次交錯(cuò)后得到的碼是次交錯(cuò)后得到的碼是 10111,120212,101,1.nnnvvvvvvvvv(13.14)它的輸出方式與圖它的輸出方式與圖13.1相同，其中相同，其中 ，所以有所以有 ，即它們都是循環(huán)碼，即它們都是循環(huán)碼 (g (x)中的碼矢量。中的碼矢量。 01,1(,.)( ( )iiii nvvvvg x(1),10,2(,.)( ( )ii nii nvvvvg

31、x東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室13.3 交錯(cuò)碼交錯(cuò)碼13.3.2 交錯(cuò)碼的性能交錯(cuò)碼的性能 如果把上述（如果把上述（ n, k）線性分組碼循環(huán)移位一次，得）線性分組碼循環(huán)移位一次，得 20212,130313,11,01,11,1,0,1,11,1101,2.nnnnnnvvvvvvvvvvvvvvv(13.15)顯然，其中的每一行仍是顯然，其中的每一行仍是(g (x)的碼矢量。所以這個(gè)的碼矢量。所以這個(gè)（ n, k）線性分組碼是個(gè)循環(huán)碼。）線性分組碼是個(gè)循環(huán)碼。 東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室13.3 交錯(cuò)碼交錯(cuò)碼13.3.2 交錯(cuò)碼的性能交錯(cuò)碼的性能 若把式若把式( (13.14) )的

32、循環(huán)碼用多項(xiàng)式表示，則其碼多項(xiàng)式為的循環(huán)碼用多項(xiàng)式表示，則其碼多項(xiàng)式為 1) 1(1, 1) 1(1, 1) 1(1,11 , 11 , 110 , 10 , 10 ,)(xxvxxvxvxxvxxvxvxvvxvnnnnnn 111, 11 , 10 , 111, 11 , 10 , 111,1 ,0 ,xxvxvvxxvxvvxvxvvnnnnnn xgxxkxxkxk111式中101,1()()() ()niii nivvxvxk xg x東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室13.3 交錯(cuò)碼交錯(cuò)碼13.3.2 交錯(cuò)碼的性能交錯(cuò)碼的性能 （5）交錯(cuò)技術(shù)把尋求）交錯(cuò)技術(shù)把尋求長而有效的糾突發(fā)錯(cuò)誤碼

33、長而有效的糾突發(fā)錯(cuò)誤碼這個(gè)問題，這個(gè)問題，簡化為尋求好的短碼簡化為尋求好的短碼。（6）交錯(cuò)碼需增加）交錯(cuò)碼需增加存儲(chǔ)設(shè)備存儲(chǔ)設(shè)備，加大，加大通信時(shí)延通信時(shí)延。交錯(cuò)是一種交錯(cuò)是一種時(shí)間擴(kuò)散技術(shù)時(shí)間擴(kuò)散技術(shù)，它使信道突發(fā)錯(cuò)誤的相關(guān)性，它使信道突發(fā)錯(cuò)誤的相關(guān)性減小。當(dāng)減小。當(dāng)足夠大時(shí)可將突發(fā)錯(cuò)誤離散為隨機(jī)錯(cuò)誤，從而足夠大時(shí)可將突發(fā)錯(cuò)誤離散為隨機(jī)錯(cuò)誤，從而可用糾隨機(jī)錯(cuò)誤碼來糾突發(fā)錯(cuò)誤。因此交錯(cuò)技術(shù)在短波、可用糾隨機(jī)錯(cuò)誤碼來糾突發(fā)錯(cuò)誤。因此交錯(cuò)技術(shù)在短波、散射、有線等有記憶的信道中得到了廣泛的應(yīng)用。散射、有線等有記憶的信道中得到了廣泛的應(yīng)用。（7）交錯(cuò)技術(shù)是一種）交錯(cuò)技術(shù)是一種等效長碼等效長碼的技術(shù)。根

34、據(jù)的技術(shù)。根據(jù)Shannon第第二定理，必然有更好的性能。二定理，必然有更好的性能。東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室 伯頓發(fā)現(xiàn)一類糾正定段突發(fā)錯(cuò)誤的循環(huán)碼。考慮一伯頓發(fā)現(xiàn)一類糾正定段突發(fā)錯(cuò)誤的循環(huán)碼?？紤]一(n, k)碼，碼，碼長碼長n是整數(shù)是整數(shù)m的倍數(shù)，如的倍數(shù)，如n = m。碼多項(xiàng)式表示如下。碼多項(xiàng)式表示如下 定義下式的定義下式的m個(gè)相鄰碼位個(gè)相鄰碼位vi m, vi m + 1, , v ( i+ 1) m 1 為一個(gè)分組，其中為一個(gè)分組，其中0 i 。因此其碼矢由。因此其碼矢由 個(gè)分組組成。個(gè)分組組成。 當(dāng)且僅當(dāng)長度等于或小于當(dāng)且僅當(dāng)長度等于或小于 m的突發(fā)局限在的突發(fā)局限在 個(gè)相鄰分

35、組內(nèi)個(gè)相鄰分組內(nèi)時(shí)，稱此突發(fā)為定段突發(fā)，時(shí)，稱此突發(fā)為定段突發(fā)， 是小于是小于 的正整數(shù)。的正整數(shù)。 一個(gè)長一個(gè)長n = m可糾正全部限制在等于或小于可糾正全部限制在等于或小于 個(gè)分組內(nèi)的定個(gè)分組內(nèi)的定段突發(fā)錯(cuò)誤的線性碼，稱為糾段突發(fā)錯(cuò)誤的線性碼，稱為糾 m長定段突發(fā)錯(cuò)誤碼。長定段突發(fā)錯(cuò)誤碼。 長為長為 ( 1) m +1的突發(fā)不論從何處開始，最多只影響的突發(fā)不論從何處開始，最多只影響 個(gè)個(gè)分組，顯然，糾分組，顯然，糾 m長定段突發(fā)錯(cuò)誤碼能夠糾正任何長度等長定段突發(fā)錯(cuò)誤碼能夠糾正任何長度等于或小于于或小于( 1 ) m +1的單個(gè)突發(fā)錯(cuò)誤。糾的單個(gè)突發(fā)錯(cuò)誤。糾 m長定段突發(fā)錯(cuò)長定段突發(fā)錯(cuò)誤碼可

36、當(dāng)作糾誤碼可當(dāng)作糾( 1) m +1長單個(gè)突發(fā)錯(cuò)誤碼使用。長單個(gè)突發(fā)錯(cuò)誤碼使用。112210)(mmxvxvxvvxv13.4 伯頓碼伯頓碼東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室 定義定義13.3 令令p(x)是是m次既約多項(xiàng)式，令次既約多項(xiàng)式，令 是能使是能使x +1被被p(x)整除的最小正整數(shù)，并令整除的最小正整數(shù)，并令n是是m和和 的最小公倍數(shù)的最小公倍數(shù) n = LCM (m, ) = m則對(duì)于任何正整數(shù)對(duì)于任何正整數(shù)m，都存在一個(gè)長，都存在一個(gè)長n = m的糾正的糾正m長定段突發(fā)錯(cuò)誤的伯頓碼，由下式生成長定段突發(fā)錯(cuò)誤的伯頓碼，由下式生成)() 1()(xpxxgm13.4 伯頓碼伯頓碼13.

37、4.1 伯頓碼的構(gòu)造伯頓碼的構(gòu)造 此碼的校驗(yàn)位數(shù)目是此碼的校驗(yàn)位數(shù)目是2m，是，是 m, ( 2)m 循環(huán)碼。循環(huán)碼。 每個(gè)碼矢包括每個(gè)碼矢包括 個(gè)分組。為了證明由上述生成式產(chǎn)生的個(gè)分組。為了證明由上述生成式產(chǎn)生的伯頓碼可以糾正全部局限在伯頓碼可以糾正全部局限在m位長的單個(gè)分組內(nèi)的定段突位長的單個(gè)分組內(nèi)的定段突發(fā)錯(cuò)誤，只要證明沒有這樣的兩個(gè)突發(fā)存在于此碼標(biāo)準(zhǔn)陣發(fā)錯(cuò)誤，只要證明沒有這樣的兩個(gè)突發(fā)存在于此碼標(biāo)準(zhǔn)陣列的相同陪集中的充分必要性。列的相同陪集中的充分必要性。 東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室 對(duì)糾正對(duì)糾正m長定段突發(fā)錯(cuò)誤的伯頓碼交錯(cuò)，產(chǎn)生的長定段突發(fā)錯(cuò)誤的伯頓碼交錯(cuò)，產(chǎn)生的( n, k)交

38、錯(cuò)碼交錯(cuò)碼可糾正任何限制在可糾正任何限制在 個(gè)相鄰分組內(nèi)的定段突發(fā)錯(cuò)誤個(gè)相鄰分組內(nèi)的定段突發(fā)錯(cuò)誤 將糾正將糾正m長定段突發(fā)錯(cuò)誤的長定段突發(fā)錯(cuò)誤的 個(gè)碼矢排列成為矩陣的個(gè)碼矢排列成為矩陣的 行。此時(shí)行。此時(shí)將每行的一個(gè)分組作為一個(gè)單元，則陣列包含將每行的一個(gè)分組作為一個(gè)單元，則陣列包含 列，每列包含列，每列包含 個(gè)分組，將矩陣按列發(fā)送，每次從每行中發(fā)送一個(gè)分組。所個(gè)分組，將矩陣按列發(fā)送，每次從每行中發(fā)送一個(gè)分組。所以在交錯(cuò)碼中，一個(gè)碼矢包括個(gè)以在交錯(cuò)碼中，一個(gè)碼矢包括個(gè) 分組。分組。 任何局限在任何局限在 個(gè)分組的定段突發(fā)錯(cuò)誤無論從何處開始，對(duì)每個(gè)分組的定段突發(fā)錯(cuò)誤無論從何處開始，對(duì)每行的影響都

39、不會(huì)多于一個(gè)分組。若按行對(duì)接收陣列進(jìn)行譯碼，行的影響都不會(huì)多于一個(gè)分組。若按行對(duì)接收陣列進(jìn)行譯碼，則此定段突發(fā)能夠被糾正。若此交錯(cuò)碼用作糾（則此定段突發(fā)能夠被糾正。若此交錯(cuò)碼用作糾（( 1) m+1）長突發(fā)錯(cuò)誤碼，則糾突發(fā)錯(cuò)誤效率為長突發(fā)錯(cuò)誤碼，則糾突發(fā)錯(cuò)誤效率為mmmmknmz1112112)(11213.4 伯頓碼伯頓碼13.4.2 伯頓碼的性能伯頓碼的性能 東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室 當(dāng)當(dāng) 趨于無窮大時(shí)，伯頓碼的糾突發(fā)錯(cuò)誤效率趨于趨于無窮大時(shí)，伯頓碼的糾突發(fā)錯(cuò)誤效率趨于1，即即 。因而將伯頓碼交錯(cuò)，可以得到一類漸近最。因而將伯頓碼交錯(cuò)，可以得到一類漸近最佳的糾突發(fā)錯(cuò)誤碼。當(dāng)佳的糾突發(fā)

40、錯(cuò)誤碼。當(dāng) 值較大時(shí)，交錯(cuò)的伯頓碼比具值較大時(shí)，交錯(cuò)的伯頓碼比具有同樣糾突發(fā)錯(cuò)誤能力的法爾碼更有效。有同樣糾突發(fā)錯(cuò)誤能力的法爾碼更有效。 實(shí)現(xiàn)將伯頓碼交錯(cuò)的簡便方法是組成編碼陣列，按行實(shí)現(xiàn)將伯頓碼交錯(cuò)的簡便方法是組成編碼陣列，按行編碼和譯碼。因此，交錯(cuò)碼的編碼器包括原碼編碼器編碼和譯碼。因此，交錯(cuò)碼的編碼器包括原碼編碼器和用作存貯編碼陣列行矢量的緩沖器。交錯(cuò)碼的譯碼和用作存貯編碼陣列行矢量的緩沖器。交錯(cuò)碼的譯碼器包括原碼譯碼器和用作存貯接收編碼陣列的緩沖器。器包括原碼譯碼器和用作存貯接收編碼陣列的緩沖器。 1limz13.4 伯頓碼伯頓碼13.4.2 伯頓碼的性能伯頓碼的性能 東南大學(xué)移動(dòng)通信

41、國家重點(diǎn)實(shí)驗(yàn)室 糾突發(fā)錯(cuò)誤卷積碼分為糾突發(fā)錯(cuò)誤卷積碼分為B1型碼和型碼和B2型碼兩類。從糾正型碼兩類。從糾正突發(fā)錯(cuò)誤能力的角度，突發(fā)錯(cuò)誤能力的角度，B1型碼作用于碼元、型碼作用于碼元、B2型碼則型碼則作用于碼段，類似于分組碼中的糾定段突發(fā)錯(cuò)誤碼，作用于碼段，類似于分組碼中的糾定段突發(fā)錯(cuò)誤碼，可以認(rèn)為是可以認(rèn)為是B1型碼的特例。型碼的特例。 假設(shè)（假設(shè)（n0, k0, m）B1型碼的糾突發(fā)錯(cuò)誤的能力為型碼的糾突發(fā)錯(cuò)誤的能力為b1，則，則它的糾它的糾B2型突發(fā)錯(cuò)誤的能力型突發(fā)錯(cuò)誤的能力b2為為(13.17) 若若(n0, k0, m)B2型碼的糾突發(fā)錯(cuò)誤的能力為型碼的糾突發(fā)錯(cuò)誤的能力為b2 = n

42、0，則它的糾則它的糾B1型突發(fā)錯(cuò)誤的能力型突發(fā)錯(cuò)誤的能力b1為為(13.18)0102nbnb1) 1(01nb13.5 糾突發(fā)錯(cuò)誤卷積碼糾突發(fā)錯(cuò)誤卷積碼東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室 如果將連續(xù)兩個(gè)突發(fā)錯(cuò)誤之間的無誤區(qū)間定義為防護(hù)區(qū)間，則對(duì)于不同型的碼要求有不同的防護(hù)區(qū)間。如果譯碼約束長度是n0 (m+1)，則B1型碼的防護(hù)區(qū)間長度f1為 (13.19)而B2型碼所要求的防護(hù)區(qū)間長度f2則為 (13.20) B1型碼和B2型碼都屬于無誤糾突發(fā)錯(cuò)誤碼無誤糾突發(fā)錯(cuò)誤碼，能糾正長度分別 b1和 b2的全部突發(fā)錯(cuò)誤全部突發(fā)錯(cuò)誤。糾突發(fā)錯(cuò)誤卷積碼通常都是指無誤糾突發(fā)錯(cuò)誤碼。還有一類糾突發(fā)錯(cuò)誤卷積碼，雖

43、然不能糾正長度不能糾正長度 b的所有突發(fā)錯(cuò)誤，但能糾正的所有突發(fā)錯(cuò)誤，但能糾正其中絕大部分錯(cuò)誤其中絕大部分錯(cuò)誤，即能以很小的譯碼錯(cuò)誤概率糾正長度 b的突發(fā)錯(cuò)誤，這類碼稱為有誤糾突發(fā)錯(cuò)誤碼。 ) 1(1) 1(010mnfmnmnf0213.5 糾突發(fā)錯(cuò)誤卷積碼糾突發(fā)錯(cuò)誤卷積碼東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室 定理定理13.6 （n0, k0, m）卷積碼糾突發(fā)錯(cuò)誤能力為）卷積碼糾突發(fā)錯(cuò)誤能力為b的充的充要條件是：其校驗(yàn)矩陣要條件是：其校驗(yàn)矩陣H中，由任意相鄰中，由任意相鄰b列為一組的列為一組的互不相交的兩組，它們列的任意線性組合不能為互不相交的兩組，它們列的任意線性組合不能為0，且，且其中一組至

44、少有一列在其中一組至少有一列在H矩陣中的首矩陣中的首n0列中選取。列中選取。 定理定理13.6表明，兩個(gè)不重疊的長度表明，兩個(gè)不重疊的長度 b的突發(fā)，其中一的突發(fā)，其中一個(gè)突發(fā)從第個(gè)突發(fā)從第0碼段開始，則它們共同組成的錯(cuò)誤圖樣，碼段開始，則它們共同組成的錯(cuò)誤圖樣，與與H矩陣相乘所得的伴隨式不能為矩陣相乘所得的伴隨式不能為0。 也即要求不同的突發(fā)錯(cuò)誤圖樣具有不同的伴隨式，也即要求不同的突發(fā)錯(cuò)誤圖樣具有不同的伴隨式，才能保證譯碼器能正確區(qū)分兩個(gè)不同的突發(fā)，從而進(jìn)才能保證譯碼器能正確區(qū)分兩個(gè)不同的突發(fā)，從而進(jìn)行正確的判決。行正確的判決。 13.5 糾突發(fā)錯(cuò)誤卷積碼糾突發(fā)錯(cuò)誤卷積碼東南大學(xué)移動(dòng)通信國家

45、重點(diǎn)實(shí)驗(yàn)室 定理定理13.7對(duì)一個(gè)糾突發(fā)能力為對(duì)一個(gè)糾突發(fā)能力為b的有限記憶的二進(jìn)制的有限記憶的二進(jìn)制線性碼，其防護(hù)區(qū)間線性碼，其防護(hù)區(qū)間f、糾突能力、糾突能力b和碼率和碼率R之間必滿足之間必滿足(13.21) 例如對(duì)糾突發(fā)能力為b的(n, k)線性分組碼，f =n b，則可以解得， 對(duì)于有誤糾突發(fā)錯(cuò)誤碼，f, b和R之間必須滿足下式： (13.22)RRbf11knknRRbbn112knb13.5 糾突發(fā)錯(cuò)誤卷積碼糾突發(fā)錯(cuò)誤卷積碼RRbf1東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室 在式（13.21）和（13.22）中，能使能使等號(hào)成立的碼，等號(hào)成立的碼，稱稱為為最佳糾突發(fā)錯(cuò)誤碼，最佳糾突發(fā)錯(cuò)誤碼，簡

46、稱為簡稱為最佳碼最佳碼。 尋找和構(gòu)造最佳或接近最佳糾突發(fā)錯(cuò)誤卷積碼的方法：方法： 采用交錯(cuò)技術(shù)，由約束長度較短的最佳碼得到約束長度較長的最佳碼。 利用分析法構(gòu)造糾單個(gè)突發(fā)錯(cuò)誤的最佳碼，如巖垂碼。 確定突發(fā)位置然后予以糾正，即糾突發(fā)刪除碼，這類碼屬有誤糾突發(fā)錯(cuò)誤卷積碼。 在同樣的碼率和糾錯(cuò)能力下，有誤糾突發(fā)錯(cuò)誤卷積碼所要求的防護(hù)區(qū)間比無誤糾突發(fā)錯(cuò)誤卷積碼要小得多。因此，在突發(fā)錯(cuò)誤較為嚴(yán)重的信道中，采用有誤糾突發(fā)錯(cuò)誤卷積碼通常能取得更好的效果13.5 糾突發(fā)錯(cuò)誤卷積碼糾突發(fā)錯(cuò)誤卷積碼東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室 巖垂（Iwadare）碼是一種較為實(shí)用的糾突發(fā)錯(cuò)誤卷積碼，屬于（n0, n0 1,

47、m）B1型糾突發(fā)錯(cuò)誤卷積碼。 特點(diǎn)是譯碼較為簡單，并且當(dāng)n0較小時(shí)接近最佳碼。 巖垂碼的n0 1個(gè)子生成元為（13.23) 其中 (13.24) 為整數(shù)。當(dāng)i = 1時(shí)，上式中的b (1) 達(dá)到最大，此時(shí) (13.25) 碼的約束度為m = b (1)，能糾正長度為b1 = n0的B1型突發(fā)錯(cuò)誤，要求的防護(hù)區(qū)間為 (13.26)1, 2 , 1,)(0)()(),(0niDDDibianig1, 3)2)(1()(1, 1)(1()(00iinibiniamnb2) 12)(1() 1 (013.6 巖垂碼巖垂碼1) 12)(1(1) 1(00001nnnmnf東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室

48、H矩陣的首n0列構(gòu)成了B0陣，一旦B0陣確定，則H矩陣也就確定了。 由式（13.23），巖垂碼B0陣的首n0 1列中的每列只有兩個(gè)1，其位置是a (i)和b (i)，第n0列中只有一個(gè)1處于第0行即首行。 由此B0陣構(gòu)成的H矩陣，與長度 n0的任何突發(fā)錯(cuò)誤圖樣相乘所得的伴隨式均不相同，且不為0，滿足定理13.6的要求，因此能夠糾正任何長度 n0的單個(gè)突發(fā)錯(cuò)誤。13.6 巖垂碼巖垂碼東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室 例例13.2 設(shè) =1，n0 =3，k0 =2，m=8，構(gòu)造一個(gè)(3, 2, 8)巖垂碼，能夠糾正長度為b1 = n0 =3個(gè)碼元的任何單個(gè)突發(fā)錯(cuò)誤。分析此巖垂碼的編譯碼方式。解解 碼

49、的兩個(gè)子生成元為： H矩陣為7)3 , 2(83)3 , 1 ()()(DDDDDDgg13.6 巖垂碼巖垂碼8 7 6 5 4 3 2 1 0001010000100000000000010100001010100010001010100000001010100000001010100000001010100001010000001010001H 東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室 H矩陣的n0 (3)列構(gòu)成了B0陣，陣的前兩列中只有兩個(gè)1，分別位于由a (i)和b (i)決定的行，也即第3、第8行和第1、第7行；而第3列只有一個(gè)1，位于第0行。 長度為n0 =3比特的B1型突發(fā)錯(cuò)誤圖樣共有3種

50、情況：0, 0,00, 00,0, 000,121103311030220302011eeeeeeeeeEEE13.6 巖垂碼巖垂碼東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室, 0000000282726252423222120110211020322ssssssssseeeeeTHES, 0000000383736353433323130111211120333ssssssssseeeeeTHES , 0000000181716151413121110010201020311ssssssssseeeeeTHES對(duì)應(yīng)的伴隨式分別為13.6 巖垂碼巖垂碼由伴隨式S1可知， 構(gòu)成了對(duì)e01碼元位的兩個(gè)正交校驗(yàn)

51、和， 構(gòu)成了對(duì)e02碼元位的兩個(gè)正交校驗(yàn)和。1813,ss1711,ss東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室 對(duì)E2錯(cuò)誤圖樣而言，雖然 能構(gòu)成對(duì)e02碼元位正交的兩個(gè)校驗(yàn)和，但 卻不能構(gòu)成對(duì)e01碼元位正交的兩個(gè)校驗(yàn)和。 同樣，對(duì)E3錯(cuò)誤圖樣而言，也不能從 和 構(gòu)成對(duì)e12和e11的兩個(gè)正交校驗(yàn)和。 因此采用一次大數(shù)邏輯譯碼的方法無法糾正B1型碼的長度為3的單個(gè)突發(fā)圖樣。必須進(jìn)行分段大數(shù)邏輯譯碼。 由H矩陣的表達(dá)式可得2721,ss2823,ss3731,ss3833,ss8372511278231212eeeesseess13.6 巖垂碼巖垂碼構(gòu)成對(duì)第一碼段第2信息比特e12的兩個(gè)正交校驗(yàn)和式。東

52、南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室 用上兩式的大數(shù)判決結(jié)果對(duì)該碼元進(jìn)行糾錯(cuò)后，該子分組在譯碼器中進(jìn)入第0碼段位置，由于第2信息元已糾錯(cuò)，錯(cuò)誤對(duì)該信息元的影響已消除，所以由H矩陣的第4行和第9行可得 它們構(gòu)成了對(duì)第0段碼第1個(gè)信息比特e01的兩個(gè)正交校驗(yàn)和式，利用大數(shù)準(zhǔn)則對(duì)該信息比特進(jìn)行糾錯(cuò)。 因此采用這種二次分段大數(shù)邏輯譯碼后，就實(shí)現(xiàn)了對(duì)e01和e02的糾錯(cuò)。 一般而言，n0 1個(gè)信息比特中的錯(cuò)誤，可以用n0 1次分段大數(shù)邏輯譯碼方法譯碼。8372510183322013eeeeseees13.6 巖垂碼巖垂碼東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室 （3, 2, 8）巖垂碼的譯碼器原理圖如圖13.2所示。輸

53、出 R(1)(D) 輸入 R(2)(D) s8 s3 s2 A1 A2 13.6 巖垂碼巖垂碼圖13.2 （3，2，8）巖垂碼譯碼器 東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室 （3, 2, 8）巖垂碼的譯碼步驟譯碼步驟（1）將輸入R (D)中的每一段的前兩個(gè)信息元送入編碼器求出新的校驗(yàn)元，與后面輸入的校驗(yàn)元進(jìn)行比較，得到相應(yīng)的伴隨式分量，送入伴隨式寄存器。（2）如果與門A2輸出1，則表明第1碼段的第2個(gè)信息元出錯(cuò)，對(duì)它進(jìn)行糾錯(cuò)，同時(shí)修正伴隨式以消去此錯(cuò)誤的影響。（3）如果與門A1輸出1，則表明第0碼段的第1個(gè)信息元出錯(cuò)，對(duì)它進(jìn)行糾錯(cuò)，同時(shí)修正伴隨式以消去此錯(cuò)誤的影響。13.6 巖垂碼巖垂碼東南大學(xué)移動(dòng)通

54、信國家重點(diǎn)實(shí)驗(yàn)室 用這種分段大數(shù)邏輯譯碼方法能夠糾正約束長度內(nèi)的任意的長度 的突發(fā)錯(cuò)誤。 當(dāng) = 1時(shí)，巖垂碼的防護(hù)區(qū)間與糾突發(fā)能力之比為 對(duì)于R = ( n0 1) / n0的最佳B1型碼而言，由式（13.21）可知12110nRRbf13.6 巖垂碼巖垂碼0001)34(1) 1(nnbnmbf東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室 對(duì)糾正對(duì)糾正b長突發(fā)錯(cuò)誤的循環(huán)碼的譯碼方法基于如下事實(shí)：長突發(fā)錯(cuò)誤的循環(huán)碼的譯碼方法基于如下事實(shí)： 令令r(x)是接收矢量，是接收矢量， e(x)是錯(cuò)誤矢量，是錯(cuò)誤矢量，r(x)的伴隨式為的伴隨式為 如果如果e(x)的錯(cuò)誤限制在的錯(cuò)誤限制在r(x)的的b個(gè)高階校驗(yàn)位個(gè)

55、高階校驗(yàn)位 上，上，則則 s(x)的的b個(gè)高階位個(gè)高階位 與與e(x)錯(cuò)誤一致，且錯(cuò)誤一致，且s(x)的的nkb個(gè)低階位個(gè)低階位 為為0。 設(shè)設(shè)e(x)的錯(cuò)誤局限在的錯(cuò)誤局限在r(x)的某的某b個(gè)相鄰位上（包括首尾相接情個(gè)相鄰位上（包括首尾相接情況）。則況）。則r(x)經(jīng)過經(jīng)過i次循環(huán)移位后，錯(cuò)誤被移位到次循環(huán)移位后，錯(cuò)誤被移位到r (x)的第的第i次次移位移位r(i)(x)的的 位上。位上。 令令 si(x)是是r(i)(x)的伴隨式，則的伴隨式，則si(x)的前的前b個(gè)高階位與錯(cuò)誤一致，個(gè)高階位與錯(cuò)誤一致，且且si(x)的的nkb個(gè)低階位是個(gè)低階位是0。112210)(knknxsxsxs

56、sxs12,.,knknbknxxx12,.,knknbknsssbknsss,.,1013.7 糾突發(fā)錯(cuò)誤循環(huán)碼的譯碼糾突發(fā)錯(cuò)誤循環(huán)碼的譯碼12,.,knknbknxxx東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室 基于以上分析所設(shè)計(jì)的捕錯(cuò)譯碼器如圖基于以上分析所設(shè)計(jì)的捕錯(cuò)譯碼器如圖13.3所示。所示。 (n-k)級(jí)伴隨式寄存器 輸入 門 1 反饋連接 . 或門 b 級(jí) 門 2 緩沖寄存器 輸入 門 3 已糾正的輸出 13.7 糾突發(fā)錯(cuò)誤循環(huán)碼的譯碼糾突發(fā)錯(cuò)誤循環(huán)碼的譯碼東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室 譯碼步驟譯碼步驟 步驟1：門1打開，門2和門3關(guān)閉。將接收矢量r(x)全部移入伴隨式寄存器，形成伴隨式s

57、(x)，同時(shí)將r(x)的k位接收信息數(shù)字存入緩沖寄存器中。 步驟2：門1打開，門2和門3關(guān)閉。伴隨式寄存器開始移位。到最左邊nkb級(jí)僅包含0時(shí)，最右邊的b級(jí)就包含突發(fā)圖樣，可用于實(shí)現(xiàn)糾錯(cuò)。分別考慮以下3種情況。 步驟3：如果第i次移位之后，0 i n k b，伴隨式寄存器的最左邊n k b級(jí)包含0，則突發(fā)e(x)的錯(cuò)誤限制在r(x)的校驗(yàn)部分。因此緩沖器中k位接收信息數(shù)字是無錯(cuò)的。然后門3打開，緩沖器中k位無錯(cuò)信息數(shù)字移出，送到信宿。如果在伴隨式寄存器的前n k b次移位期間，伴隨式寄存器的最左邊n k b級(jí)從未包含0，則突發(fā)不是限制在n k個(gè)校驗(yàn)位上。13.7 糾突發(fā)錯(cuò)誤循環(huán)碼的譯碼糾突發(fā)錯(cuò)

58、誤循環(huán)碼的譯碼東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室 步驟步驟4：若伴隨式寄存器第：若伴隨式寄存器第nkb+i次移位后，最左邊次移位后，最左邊nkb級(jí)包含級(jí)包含0，則突發(fā)限制在則突發(fā)限制在r(x)的的xni,xn1, x0, , xbi1 位。從右端數(shù)起，伴隨式位。從右端數(shù)起，伴隨式寄存器第寄存器第b, (b1), , (bi+1)級(jí)中的位與級(jí)中的位與r(x)的的xni , xn2 , xn1 位上位上的錯(cuò)誤比特相對(duì)應(yīng)。此時(shí)，時(shí)鐘從的錯(cuò)誤比特相對(duì)應(yīng)。此時(shí)，時(shí)鐘從nkb+i+1開始計(jì)數(shù)。門開始計(jì)數(shù)。門1關(guān)閉，關(guān)閉，伴隨式寄存器移位。一旦時(shí)鐘計(jì)數(shù)到伴隨式寄存器移位。一旦時(shí)鐘計(jì)數(shù)到nk，伴隨式寄存器中最右端

59、，伴隨式寄存器中最右端i位比特就與緩沖寄存器中首位比特就與緩沖寄存器中首i位接收信息數(shù)字的相對(duì)應(yīng)。然后門位接收信息數(shù)字的相對(duì)應(yīng)。然后門2和和門門3打開。接收信息從緩沖寄存器中讀出并進(jìn)行糾正。打開。接收信息從緩沖寄存器中讀出并進(jìn)行糾正。 步驟步驟5：若伴隨式寄存器已移位：若伴隨式寄存器已移位nk次，而最左邊次，而最左邊nkb從未全含從未全含0，則門則門3打開，數(shù)字從緩沖寄存器一次一個(gè)讀出。同時(shí)門打開，數(shù)字從緩沖寄存器一次一個(gè)讀出。同時(shí)門1打開，伴隨打開，伴隨式寄存器移位。一旦伴隨式寄存器最左邊式寄存器移位。一旦伴隨式寄存器最左邊nkb級(jí)包含級(jí)包含0，其最右邊，其最右邊b級(jí)內(nèi)容就與將從緩沖寄存器輸

60、出的級(jí)內(nèi)容就與將從緩沖寄存器輸出的b位接收數(shù)字中的錯(cuò)誤對(duì)應(yīng)。然后位接收數(shù)字中的錯(cuò)誤對(duì)應(yīng)。然后門門2打開，錯(cuò)誤信息用伴隨式寄存器輸出（門打開，錯(cuò)誤信息用伴隨式寄存器輸出（門1關(guān)閉）的數(shù)字進(jìn)行糾關(guān)閉）的數(shù)字進(jìn)行糾正。正。13.7 糾突發(fā)錯(cuò)誤循環(huán)碼的譯碼糾突發(fā)錯(cuò)誤循環(huán)碼的譯碼東南大學(xué)移動(dòng)通信國家重點(diǎn)實(shí)驗(yàn)室13.7 糾突發(fā)錯(cuò)誤循環(huán)碼的譯碼糾突發(fā)錯(cuò)誤循環(huán)碼的譯碼當(dāng)當(dāng)k位信息已從緩沖器輸出而伴隨式寄存器最左邊位信息已從緩沖器輸出而伴隨式寄存器最左邊nkb級(jí)級(jí)從未全含從未全含0，則查出長度，則查出長度b的突發(fā)或不能糾正突發(fā)。的突發(fā)或不能糾正突發(fā)。上述譯碼器僅能糾正長度上述譯碼器僅能糾正長度 b的突發(fā)，錯(cuò)誤圖