1、電力系統調度自動化電力系統調度自動化電氣工程學院電氣工程學院 林國松林國松第四章第四章 抗干擾編碼抗干擾編碼概述1抗干擾編碼的基本原理2線性分組碼3循環碼4循環碼的抗干擾能力5遠動信息的CRC校驗7BCH碼6第一節第一節 概述概述基本概念基本概念v誤碼率誤碼率v奇偶校驗碼奇偶校驗碼v抗干擾編碼抗干擾編碼差錯控制方法差錯控制方法v循環檢錯循環檢錯v檢錯重發檢錯重發v前向糾錯前向糾錯v反饋檢驗反饋檢驗第二節第二節 抗干擾編碼的基本原理抗干擾編碼的基本原理許用碼字許用碼字禁用碼字禁用碼字概念：概念：一、分組碼的概念一、分組碼的概念分組碼是對每個長度為分組碼是對每個長度為k k的信息組，以一定的規則增

2、加的信息組，以一定的規則增加r r個監督位，組成長度為個監督位，組成長度為n=k+rn=k+r的二進制序列的二進制序列 。這個長為這個長為n n的序列叫做的序列叫做碼字、碼組或碼矢碼字、碼組或碼矢，并稱此，并稱此2 2k k個個碼字的集合為碼字的集合為(n,k)(n,k)分組碼分組碼，其中，其中n n表示碼長，表示碼長，k k表示信息表示信息位長，位長，r=n-kr=n-k為監督位長。為監督位長。0121,.,CCCCnn第二節第二節 抗干擾編碼的基本原理抗干擾編碼的基本原理二、碼距和最大似然譯碼二、碼距和最大似然譯碼在分組碼中，碼字中在分組碼中，碼字中“1”1”的數目叫做碼字的重量，簡稱的數

3、目叫做碼字的重量，簡稱碼碼重重；任意兩個碼字對應位上的數字符號不同的位數叫做碼字距任意兩個碼字對應位上的數字符號不同的位數叫做碼字距離，簡稱離，簡稱碼距碼距。所有碼字間的最小距離叫做。所有碼字間的最小距離叫做最小碼距最小碼距，記，記作作d d0 0 。最大似然譯碼最大似然譯碼：收到的數字序列和哪一個許用碼字的距離：收到的數字序列和哪一個許用碼字的距離最小，就把它譯成這個碼字。最小，就把它譯成這個碼字。理解理解P111P111舉例說明。舉例說明。第二節第二節 抗干擾編碼的基本原理抗干擾編碼的基本原理三、分組碼的檢錯、糾錯能力三、分組碼的檢錯、糾錯能力要發現（檢查）要發現（檢查）e e個錯誤，要求

4、最小碼距：個錯誤，要求最小碼距： d d0 0 e + 1 e + 1要糾正要糾正t t個錯誤，要求最小碼距：個錯誤，要求最小碼距： d d0 0 2t + 1 2t + 1要糾正要糾正t t個錯誤，同時要發現個錯誤，同時要發現e e個錯誤，則要求最小碼個錯誤，則要求最小碼距：距： d d0 0 t + e + 1 (e t) t + e + 1 (e t) 第二節第二節 抗干擾編碼的基本原理抗干擾編碼的基本原理例如：例如： 某一（某一（n, kn, k）碼的最小碼距）碼的最小碼距d d0 01010， 則：則：e 9e 9 t 4.5 t 4.5 e et 9 t 9 即：該碼最多只能發現即

5、：該碼最多只能發現9 9個錯誤；或者：個錯誤；或者： 最多只能糾正最多只能糾正4 4個錯誤，但同時可查個錯誤，但同時可查5 5個錯誤；或者：個錯誤；或者： 糾正糾正3 3個錯誤，但同時可查個錯誤，但同時可查6 6個錯誤；或者：個錯誤；或者： 糾正糾正2 2個錯誤，但同時可查個錯誤，但同時可查7 7個錯誤等。個錯誤等。第三節第三節 線性分組碼線性分組碼一、代數運算知識簡介一、代數運算知識簡介v模模2運算運算v向量和矩陣向量和矩陣加法加法乘法乘法加法加法乘法乘法0+0=000=01+0=110=00+1=101=01+1=011=1向量：向量：在數學上的定義是一組有序的數，這里的在數學上的定義是一

6、組有序的數，這里的數是數是0或或1；矩陣：矩陣：是是n維向量排列成維向量排列成m行的表，矩陣中的每行的表，矩陣中的每個元素都是個元素都是0或或1。第三節第三節 線性分組碼線性分組碼二、生成矩陣二、生成矩陣設設(7,3)(7,3)碼的碼的3 3個信息位是個信息位是C C6 6C C5 5C C4 4,4,4個監督位是個監督位是C C3 3C C2 2C C1 1C C0 0。信息組信息組碼字碼字000000001001010010011011100100101101110110111111000 000 00000000001 001 11011101010 010 01110111011 01

7、1 10101010100 100 11101110101 101 00110011110 110 10011001111 111 010001004560456145624563110011111101CCCCCCCCCCCCCCCC求監督位方程為求監督位方程為第三節第三節 線性分組碼線性分組碼二、生成矩陣二、生成矩陣G：生成矩陣（kn）Ik：為k階單位矩陣Q：為（kr）階矩陣 編碼：將待編信息組M乘以生成矩陣G就直接得到線性碼字C。MGC 1101001011101011101004560123456CCCCCCCCCCQIGk110100101110101110100456CCCM 寫成

8、矩陣形式第三節第三節 線性分組碼線性分組碼三、監督矩陣及線性碼的性質三、監督矩陣及線性碼的性質將監督方程改寫為：010001100010001100010111000011010123456012345601234560123456CCCCCCCCCCCCCCCCCCCCCCCCCCCC寫成矩陣形式000000010110010110010011110001010123456CCCCCCCPIrH00010110010110010011110001010TCH0THC監督矩陣監督矩陣說明線性碼中信息說明線性碼中信息位和監督位之間的位和監督位之間的線性關系。線性關系。第三節第三節 線性分組碼線性

9、分組碼三、監督矩陣及線性碼的性質三、監督矩陣及線性碼的性質線性碼性質：（1）封閉性，即任意兩個線性碼字之和仍為一個線性碼字。設C1、C2是任意兩個線性碼字，有0)(2121TTTHCHCHCC所以，C1+C2是一個線性碼字。（2）線性碼字的最小碼距等于碼字的最小重量。因為任意兩個線性碼字之間的距離等于這兩個碼字的（模2）和的非零個數，由性質1知任意兩個線性碼字之和仍為一個線性碼字，所以最小碼距等于碼字的最小重量。第三節第三節 線性分組碼線性分組碼四、伴隨式四、伴隨式E為錯碼樣式接收端收到的碼字：E為（為（1n）矩陣，其元素為）矩陣，其元素為“0”（正確）或（正確）或“1”（錯誤）（錯誤）如如：

10、C(0011101) ，E（1000011） R（1011110）為）為禁用碼字，檢測錯誤禁用碼字，檢測錯誤檢錯檢錯判斷判斷R是否為許用碼字是否為許用碼字 定義伴隨式S為：ECR),.,(0111eeeeEnnTTTEHHECRHS)(第三節第三節 線性分組碼線性分組碼四、伴隨式四、伴隨式0110001110001011101001011000H0123456012345610000100001000011011111001110110001110001011101001011000eeeeeeeeeeeeeeEHSTT監督矩陣：第四節第四節 循環碼循環碼一、代數知識一、代數知識 循環碼是線性

11、分組碼的重要子類，有嚴格的代數結構，用代數方法可找出許多編碼效率高、檢糾錯能力強的循環碼。 循環碼的編碼、檢糾錯方法簡單、易實現，并且已找到許多有效的糾錯方法。 得到廣泛應用 循環碼可用多項式分析，其系數為“0”或“1”。多項式的系數是一組按冪次的有序數組，而碼字也是一組的有序數組，因此碼字：C=(Cn-1,Cn-2, C0)不但可用向量表示，也可用一個多項式表示稱為碼多項式。注意：多項式系數的加、乘為模2加、乘。012111.)(CxCxCxCxCnnnn第四節第四節 循環碼循環碼一、代數知識一、代數知識v模模f(x)加法，記作加法，記作 定義：兩個多項式f1(x)、f2(x)的模f(x)加

12、法是f1(x)加 f2(x)后，除以f(x)所得的余式。)(2121)()()()(xfxfxfxfxf如果f1(x)、f2(x)的次數都小于f(x)，則)()()()(2121xfxfxfxfv模模f(x)乘法，記作乘法，記作 定義：兩個多項式f1(x)、f2(x)的模f(x)乘法是f1(x)乘 f2(x)后，除以f(x)所得的余式。)(2121)()()()(xfxfxfxfxf第四節第四節 循環碼循環碼二、循環碼原理二、循環碼原理v循環碼的定義循環碼的定義定義：(n,k)循環碼是線性分組碼，并且任意碼字的每一次循環移位，得到的仍是一個碼字。第四節第四節 循環碼循環碼二、循環碼原理二、循環

13、碼原理v循環碼的生成多項式循環碼的生成多項式定義(n,k)循環碼的生成多項式是碼字中n-k次的碼多項式，記作g(x)。從2k個碼字中，取出一個前面k-1位均為0的碼字，其構成的多項式即是該碼字的生成多項式，其次數：n-1-(k-1)=n-k。如：(7,3)循環碼：前2位為0的碼字：0011101，其生成多項式： ，次數為6-2=41)(234xxxxg第四節第四節 循環碼循環碼二、循環碼原理二、循環碼原理因為g(x)是一個循環碼字，所以 都是碼字。循環碼是線性碼，由線性碼字的性質的：這k個碼字的線性組合也是一個碼字)().()(012111xgmxmxmxmxCkkkk把信息組 寫成多項式01

14、2111.)(mxmxmxmxmkkkk),.,(021mmmkk可以得到)()()(xgxmxC循環碼的碼字是待編碼的信息多項式乘生成多項式得到，m(x)共有2k種形式，可以生成2k個循環碼碼字，(n,k)循環碼只有2k個碼字，因此：所有循環碼字均可以由g(x)生成。)(),.,(),(12xgxxgxxxgk注意：直接由式生成的循環碼不是系統碼格式。第四節第四節 循環碼循環碼二、循環碼原理二、循環碼原理生成多項式的性質：生成多項式是次數最低的碼多項式。生成多項式可由 進行因式分解，然后取其n-k次因式就是g(x)，所以其次數就是n-k次。1nx將 進行因式分解：又因(7,3)碼的n-k=4

15、，g(x)應為4次多項式。前表中的(7,3)碼的g(x)為： 17x) 1)(1)(1(13237xxxxxx1)1)(1()(2343xxxxxxxg例：求(7,3)循環碼的生成多項式。第四節第四節 循環碼循環碼二、循環碼原理二、循環碼原理v系統碼格式的循環碼的編碼系統碼格式的循環碼的編碼(1)將待編信息多項式 乘以 ，得)()()()(xrxgxQxxmkn1)(234xxxxg111000000000012234343455234xxxxxxxxxxxxxxxxx(2)求余式：(3)碼多項式：例：求的(7,3)碼。解：knxknxxm)()()()()()(xrxxmxgxQxCknxx

16、m)() 1()(2xxxrC=0100111) 1() 1)(1()(22345xxxxxxxxxmkn1)()()(25xxxxrxxmxCkn)(xm第四節第四節 循環碼循環碼三、循環碼的伴隨式三、循環碼的伴隨式在發送端把信息序列編成循環碼字，發送給接收端，在傳輸中因干擾產生錯碼，接收端收到的不一定是循環碼字，而是一個數字序列R。設錯碼樣式為012111.)(exexexexEnnnn在接收端收到的數字序列多項式為)()(.)(012111xExCrxrxrxrxRnnnn循環碼的伴隨式記作 ，它是數字序列 除以生成多項式g(x)所得的余式。當 時， ； 時， 。所以，循環碼的檢錯方法是

17、：在接收端把接收到的數字序列 除以生成多項式g(x)所得的余式 ，如果 ，認為無錯碼；如果 ，則有錯碼。)(xS)(xR0)(xE0)(xS0)(xE0)(xS)(xS0)(xS0)(xS第四節第四節 循環碼循環碼四、縮短循環碼四、縮短循環碼v只取原系統中部分碼字，并刪去前面的只取原系統中部分碼字，并刪去前面的0，不再具，不再具有循環的特性。有循環的特性。v 只刪去只刪去0，不影響由信息生成碼字時的運算過程和，不影響由信息生成碼字時的運算過程和運算結果，實現的電路（程序）不變，監督位數不運算結果，實現的電路（程序）不變，監督位數不變、糾檢錯的能力不變。變、糾檢錯的能力不變。定義：任何一個給定的

18、(n,k)系統循環碼的2k個碼字中，一定存在2k-i(ik)個前i位為零的碼字。如果刪去2k-i個碼字中前面i位零，可以得到2k-i個長為(n-i)的碼字，由它們構成的(n-i,k-i)線性系統碼，稱為原(n,k)系統循環碼的縮短循環碼。第四節第四節 循環碼循環碼四、縮短循環碼四、縮短循環碼考察(7,4)系統循環碼。0120123rrrmmmmC 1111011110110011110101011001000111100110101000101100010010000000 在16個碼字中，1/2的碼字信息最高位為0。編碼時0不起作用，去掉不影響余式。刪去得到8個碼長為6的碼字，構成(6,3)

19、碼，校驗元同原來(7,4)碼，相同的生成多項式和編碼方法。稱(6,3)碼為原來(7,4)碼的縮短循環碼。將(7,4)碼的碼長和信息位同時減少1位，是(n-1,k-1)碼。 在16個碼字中，1/4的碼字信息前兩位為0。刪去得到4個碼長為5的碼字，構成(5,2)碼，也稱為原來(7,4)碼的縮短循環碼。將(7,4)碼的碼長和信息位同時減少2位，是(n-2,k-2)碼。第五節第五節 循環碼的抗干擾能力循環碼的抗干擾能力一、循環碼的隨機檢錯能力一、循環碼的隨機檢錯能力(1)如生成多項式 的項數是偶數，則能檢出所有奇數個差錯。因為當差錯個數為奇數時，錯誤圖樣 的項數也是奇數。 的項數是偶數， 的項數是奇數

20、， 不可能被 除盡，從而檢出了所有奇數個錯誤。(2)用 與任一 相乘所得的生成多項式 ，其項數必為偶數。)(xg)(xE)(xg)(xE)(xE)(xg)() 1()(12xgxxg)(1xg1x1.)() 1()(11112xgxgxxgxxgknknkn令01.1) 1 (0) 1 () 11 () 1 (11112gggggkn代入 有1x從循環碼的的檢錯譯碼的原理可知，要看收到的碼組從循環碼的的檢錯譯碼的原理可知，要看收到的碼組 是否能被生成多項式是否能被生成多項式 除盡，也就是錯誤圖樣除盡，也就是錯誤圖樣 是否能被生成是否能被生成多項式多項式 除盡，除不盡時伴隨式除盡，除不盡時伴隨式

21、 ，就能檢出錯誤。，就能檢出錯誤。)(xg)(xg)(xE)()()(xExCxR0)(xS第五節第五節 循環碼的抗干擾能力循環碼的抗干擾能力二、循環碼的突發檢錯能力二、循環碼的突發檢錯能力由突發干擾產生的錯誤是成串的差錯。第一個錯碼與最后一個錯碼之間的位數叫做突發長度，記作b。例如突發干擾使111111111錯成1010001011，其突發長度b=7。一個突發長度為b的突發錯誤，其首位和末位必定有錯，中間的碼元可能有錯，也可能無錯。若一個線性碼能發現（或糾正）碼組中所有長度小于等于b的突發錯誤，則該碼的突發檢錯（或糾錯）能力為b。設(n,k)循環碼的突發檢錯能力為b。突發長度為b的錯誤圖樣

22、可寫成1.)(1221xexexxEbbbb任意一個突發長度為b的錯誤多項式都可寫成)()(xExxEbi)(xEb第五節第五節 循環碼的抗干擾能力循環碼的抗干擾能力二、循環碼的突發檢錯能力二、循環碼的突發檢錯能力(1)由n-k次生成多項式生成的循環碼，能檢出所有突發長度 的突發錯誤。(2)若 ，則不能檢出的突發錯誤部分占同樣長度的突發錯誤總數的 。(3)若 ，則不能檢出的突發錯誤部分占同樣長度的突發錯誤總數的 。knb1knb)1(2kn1knb)(2knv(n,k)循環碼的監督位數越大時，不能被發現的突循環碼的監督位數越大時，不能被發現的突發錯誤占的比例就越小。發錯誤占的比例就越小。 第六

23、節第六節 BCH碼碼一、代數知識簡介一、代數知識簡介BCH碼是循環碼的一個子類，其生成多項式與最小碼距之碼是循環碼的一個子類，其生成多項式與最小碼距之間有直接關系。間有直接關系。(1)多項式的根。多項式 的根以符號表示， 。(2)既約多項式：指不能在二元域內再分解因式的多項式。0)(f例：例： 是可約多項式，是可約多項式， 是既約多項式。是既約多項式。17x13 xx如果如果 是是 的根，則的根，則 。01313 xx001) 1() 1(101) 1() 1(111) 1() 1(110) 1(0111327223262232543三位元素的域記作 ，共有 個元素，其中001-111叫做非零

24、元素。稱 是本原多項式，其根叫做本原元。)2(3GF82313 xx)(xf第六節第六節 BCH碼碼一般情況，一個m次既約多項式，如果其根 生成 中的所有非零元素，且兩兩不同，則此多項式稱本原多項式，其根叫做本原元。1,.,1221m)2(mGF)2(mGF(1)m次既約多項式必為 的因式，其中 。(2)定義：設是 中的某一元素，若m(x)是以為根的既約多項式，則稱m(x)是的最小多項式(稱為一階最小多項式)。(3)設是 中的本原元， 的最小多項式記作 ，稱為i階最小多項式。1nx12 mn)2(mGFi)2(mGF)(xmi(1)(n,k)BCH碼是循環碼，規定碼長 ，其中m為本原多項式的次

25、數。由于規定BCH碼的碼長 ，所以BCH碼是循環碼的子類，且BCH碼的生成多項式 必為 的因式。(2)本原BCH碼的生成多項式 定義為第六節第六節 BCH碼碼i二、二、BCH碼簡述碼簡述BCH碼分為兩類：一類稱本原BCH碼，另一類是非本原BCH碼。v本原本原BCH碼的定義碼的定義12mn12mn)(xg112mx)(xg)(),.,(),(),()(12531xmxmxmxmLCMxgtLCM-最小公倍式 - 的最小多項式)(xmi第六節第六節 BCH碼碼二、二、BCH碼簡述碼簡述如果已知碼長n和最小碼距d0，要求找到一個生成多項式 以編成BCH碼，具體步驟為：(1)確定BCH碼的碼長n， 。

26、(2)將 因式分解，且分解后各因式都是既約多項式；(3)求本原多項式，它的根是本原元；(4)確定各因式是幾階最小多項式；(5)求出BCH碼的生成多項式，確定BCH碼的形式。12mn1nxv非本原非本原BCH碼碼非本原BCH碼的定義和本原BCH碼定義相同，只是把本原元用非本原元代替即可。非本原BCH碼的碼長n只要滿足 條件，n就是 的因子。 1n12m要生成一個(n,k)循環碼，只需要將 分解，找出一個次數等于n-k次的因式，就可以作為(n,k)循環碼的生成多項式生成該碼組。如果在 的分解式中有多個n-k次的因式，則把其中任意一個作為生成多項式，都可以生成一個(n,k)循環碼。如果被選用的生成多項式的重量不同，它生成的循環碼最小距離也不相同。即使對次數相同又具有相同重量的生成多項式，只要它們的重量分布不同，所生成的循環碼碼字的重量分布也不相同。第七節第七節 遠動信息的遠動信息的CRC校驗校驗一、生成多項式一、生成多項式1nx1nx第七節第七節 遠動信息的遠動信息的CRC校驗校驗一、生成多項式一、生成多項式我國部頒循環式遠動規約規定，每幀遠動信息中的控制字和信息字都采用CRC校驗，并選用生成多項式 生成(48,40)循環碼，其陪集為FFH。規約中的(48,40)循環碼實際是(127,120)循環碼進行增余刪信(保證