糾突錯誤碼課件

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

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

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

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

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

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ā)錯誤碼定義和基本性質糾突發(fā)錯誤碼定義和基本性質13.1.2 基本性質基本性質 東南大學移動通信國家重點實驗室 定理定理13.3 一個（一個（n, k）線性碼能糾正所有長度）線性碼能糾正所有長度 b的突的突發(fā)錯誤的充要條件是：長度發(fā)錯誤的充要條件是：長度 2b的突發(fā)不是一個碼字。的突發(fā)不是一個碼字。證明證明假設存在一個長假設存在一個長 2b的突發(fā)的

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

8、即它不能糾正所有長作為陪集首來糾錯也是無效的，即它不能糾正所有長 b 的突發(fā)錯誤。的突發(fā)錯誤。 充分性：充分性：若長度若長度 2b的突發(fā)的突發(fā)v不是碼字，則不是碼字，則u、w不在同一陪集中，不在同一陪集中，若它們都是陪集首，則都是可以糾正的長若它們都是陪集首，則都是可以糾正的長 b 的突發(fā)錯誤。的突發(fā)錯誤。 13.1糾突發(fā)錯誤碼定義和基本性質糾突發(fā)錯誤碼定義和基本性質13.1.2 基本性質基本性質 東南大學移動通信國家重點實驗室 定理定理13.4 糾正糾正b 長突發(fā)錯誤碼的校驗位數(shù)目至少是長突發(fā)錯誤碼的校驗位數(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) 一個一個(n, k)線性分組碼，若要糾正所有長度線性分組碼，若要糾正所有長度 b的突發(fā)錯誤，則應的突發(fā)錯誤，則應n k 2b。 (2)（n, k）碼的糾突上限為）碼的糾突上限為 ，稱為賴格爾限。，稱為賴格爾限。 滿足賴格爾限的碼是最佳的。滿足賴格爾限的碼是最佳的。 (3) 比率比率z=2b/(n k)被用來衡量碼的糾突發(fā)錯誤的效率，被用來衡量碼的糾突發(fā)錯誤的

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

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

12、誤圖樣，當它的錯誤局限在前i位和后位和后l i位時，即位時，即出現(xiàn)首尾相接的錯誤時出現(xiàn)首尾相接的錯誤時，有，有13.1糾突發(fā)錯誤碼定義和基本性質糾突發(fā)錯誤碼定義和基本性質13.1.2 基本性質基本性質 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ā)錯誤。證畢。的首尾相接的突發(fā)錯誤。證畢。東南大學移動通信國家重點實驗室法爾碼是最早也是最大的一類法爾碼是最早也是最大的一類用分析方法構造用分析方法構造出的糾單個突發(fā)錯誤的二進制循環(huán)碼出的糾單個突發(fā)錯誤的二進制循環(huán)碼。 由于可以根據(jù)不同的要求很方便地設計所由于可以根據(jù)不同的要求很方便地設計所需要的碼，譯碼也很簡單，因此法爾碼是一類需要的碼，譯碼也很簡單，因此法爾碼是一類比較實用的，也是比較實用的，也是最基本的糾單個突發(fā)錯誤循最基本的糾單個突發(fā)錯誤循環(huán)碼

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

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

16、bbbB xxbxb x東南大學移動通信國家重點實驗室13.2法爾碼法爾碼13.2.1 法爾碼的構造法爾碼的構造 如果假定如果假定xiA(x)和和xjB(x)在碼的同一陪集中在碼的同一陪集中，那么多項式，那么多項式 v(x) = xiA(x)+xjB(x) (13.4)必是一個碼多項式必是一個碼多項式。不失一般，假定。不失一般，假定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東南大學移動通信國家重點實驗室13.2法爾碼法爾碼13.2.1 法爾碼的構造法爾碼的構造 根據(jù)假定根據(jù)假定v (x)為碼多項式，而循環(huán)碼的為碼多項式，而循環(huán)碼的生成多項式為生成多項式為 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東南大學移動通信國家重點實驗室13.2法爾碼法爾碼13.2.1 法爾碼的

18、構造法爾碼的構造 假定假定 (13.7) 令令D (x)的次數(shù)為的次數(shù)為d，那么，那么D (x) (x2b 1 +1 )的次數(shù)是的次數(shù)是2b 1+ d。因為。因為A (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東南大學移動通信國家重點實驗室13.2法爾碼法爾碼13.2.1 法爾碼的構造法爾碼的構造 從式從式(13.10)可知可知 中有中有 這一項。因為這一項。因為2b 1b d ，故，故D(x)(x2b 1+1)不能有不能有 這一這一 項。項。 這與假設這與假設 相矛盾。相矛盾。所以必有所以必有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東南大學移動通信國家重點實驗室13.2法爾碼法爾碼13.2.1 法爾碼的構造法爾碼的構造 注意到注意到B(x)的次數(shù)小于的次數(shù)小于b，所以，所以 。因此，。因此，B(x)和和p(x)互素。已假定互素。已假定v(x)是碼多項式，所以是碼多項式，所以xj i +1必能被必能被p(x)整除，整除，ji

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

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

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

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

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

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

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

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

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

30、3.2 交錯碼的性能交錯碼的性能 （4）若）若原碼是循環(huán)的原碼是循環(huán)的，其生成多項式為，其生成多項式為g(x)，則，則交錯碼也交錯碼也是循環(huán)的是循環(huán)的，且生成多項式為，且生成多項式為g (x )。 證明證明 設經(jīng)設經(jīng) 次交錯后得到的碼是次交錯后得到的碼是 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東南大學移動通信國家重點實驗室13.3 交錯碼交錯碼13.3.2 交錯碼的性能交錯碼的性能 如果把上述（如果把上述（ n, k）線性分組碼循環(huán)移位一次，得）線性分組碼循環(huán)移位一次，得 20212,130313,11,01,11,1,0,1,11,1101,2.nnnnnnvvvvvvvvvvvvvvv(13.15)顯然，其中的每一行仍是顯然，其中的每一行仍是(g (x)的碼矢量。所以這個的碼矢量。所以這個（ n, k）線性分組碼是個循環(huán)碼。）線性分組碼是個循環(huán)碼。 東南大學移動通信國家重點實驗室13.3 交錯碼交錯碼13.3.2 交錯碼的性能交錯碼的性能 若把式若把式( (13.14) )的

32、循環(huán)碼用多項式表示，則其碼多項式為的循環(huán)碼用多項式表示，則其碼多項式為 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東南大學移動通信國家重點實驗室13.3 交錯碼交錯碼13.3.2 交錯碼的性能交錯碼的性能 （5）交錯技術把尋求）交錯技術把尋求長而有效的糾突發(fā)錯誤碼

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

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

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

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

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

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

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

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

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

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

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

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

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

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

47、m）B1型糾突發(fā)錯誤卷積碼。 特點是譯碼較為簡單，并且當n0較小時接近最佳碼。 巖垂碼的n0 1個子生成元為（13.23) 其中 (13.24) 為整數(shù)。當i = 1時，上式中的b (1) 達到最大，此時 (13.25) 碼的約束度為m = b (1)，能糾正長度為b1 = n0的B1型突發(fā)錯誤，要求的防護區(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東南大學移動通信國家重點實驗室

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

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

50、情況：0, 0,00, 00,0, 000,121103311030220302011eeeeeeeeeEEE13.6 巖垂碼巖垂碼東南大學移動通信國家重點實驗室, 0000000282726252423222120110211020322ssssssssseeeeeTHES, 0000000383736353433323130111211120333ssssssssseeeeeTHES , 0000000181716151413121110010201020311ssssssssseeeeeTHES對應的伴隨式分別為13.6 巖垂碼巖垂碼由伴隨式S1可知， 構成了對e01碼元位的兩個正交校驗

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

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

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

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

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

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

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

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

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

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