管理信息學(xué)第4章3ppt課件

1、管理信息學(xué) 楊善林 胡笑旋編著第4章 信息傳輸與信息編碼2022-1-304.4.5 循環(huán)碼循環(huán)碼u 代數(shù)基礎(chǔ)知識(shí)代數(shù)基礎(chǔ)知識(shí)u 循環(huán)碼及其生成多項(xiàng)式循環(huán)碼及其生成多項(xiàng)式u 循環(huán)碼的校驗(yàn)多項(xiàng)式循環(huán)碼的校驗(yàn)多項(xiàng)式管理信息學(xué) 楊善林 胡笑旋編著第4章 信息傳輸與信息編碼2022-1-30由于線性碼的數(shù)學(xué)結(jié)構(gòu)太簡單，因此譯碼依然很困難，如譯由于線性碼的數(shù)學(xué)結(jié)構(gòu)太簡單，因此譯碼依然很困難，如譯100，80線性碼時(shí)，必須從線性碼時(shí)，必須從2100-80=220個(gè)校驗(yàn)子中找到個(gè)校驗(yàn)子中找到S (A)，再從，再從280個(gè)字中找到個(gè)字中找到A，這樣工作量依然很大。，這樣工作量依然很大。下面我們介紹一種比線性碼

2、有更多的代數(shù)結(jié)構(gòu)且使用最為廣下面我們介紹一種比線性碼有更多的代數(shù)結(jié)構(gòu)且使用最為廣泛的一種編碼泛的一種編碼循環(huán)碼。下面介紹的相關(guān)數(shù)學(xué)知識(shí)，證明都循環(huán)碼。下面介紹的相關(guān)數(shù)學(xué)知識(shí)，證明都省略了。省略了。4.4.5 循環(huán)碼：代數(shù)基礎(chǔ)知識(shí)循環(huán)碼：代數(shù)基礎(chǔ)知識(shí)管理信息學(xué) 楊善林 胡笑旋編著第4章 信息傳輸與信息編碼2022-1-30(000000, 011001, 101010, 110011, 110100, 101101, 011110, 000111)100110010101001011G100100010010001001G(000000, 001001, 010010, 011011, 1001

3、00, 101101, 110110, 111111)4.4.5 循環(huán)碼：代數(shù)基礎(chǔ)知識(shí)循環(huán)碼：代數(shù)基礎(chǔ)知識(shí)管理信息學(xué) 楊善林 胡笑旋編著第4章 信息傳輸與信息編碼定義定義4.14 記記Fn2x=系數(shù)在系數(shù)在F2中的關(guān)于中的關(guān)于 x 的的 n-1次多項(xiàng)式全體次多項(xiàng)式全體 則稱則稱( f(x) )= k(x)f(x) | k(x) Fn2x 是由是由f (x) ( f(x) Fn2x )生成的主理生成的主理想。想。定義定義4.15 稱稱 為為 g(x) 關(guān)于理想關(guān)于理想(f(x)的陪集。的陪集。(1)全部陪集構(gòu)成了全部陪集構(gòu)成了Fn2x的一個(gè)劃分的一個(gè)劃分:Fn2x/(f(x),它是由它是由Fn2

4、x中所有多項(xiàng)中所有多項(xiàng)式除以式除以 f(x) 所得的余式所得的余式 g(x) 的陪集組成。的陪集組成。 (2) 若若f(x)的最高次數(shù)為的最高次數(shù)為 n-k，共有，共有 2n-k 個(gè)陪集，每個(gè)陪集含有個(gè)陪集，每個(gè)陪集含有2 k 個(gè)多項(xiàng)式；個(gè)多項(xiàng)式； (3) 同一陪集的任意兩個(gè)多項(xiàng)式差屬于同一陪集的任意兩個(gè)多項(xiàng)式差屬于 (f(x)；同一個(gè)陪集內(nèi)的兩個(gè)多項(xiàng)式對；同一個(gè)陪集內(nèi)的兩個(gè)多項(xiàng)式對應(yīng)的陪集相等；對于應(yīng)的陪集相等；對于Fn2x/(f(x)中的任意兩個(gè)多項(xiàng)式中的任意兩個(gè)多項(xiàng)式 g(x)和和 h(x) 相等相等 ，當(dāng)，當(dāng)且僅當(dāng)有且僅當(dāng)有 f(x)|(g(x)-h(x)，此式等價(jià)于，此式等價(jià)于 g(

5、x)h(x)mod(f(x)()(| )()()(xfxaxaxgxg4.4.5 循環(huán)碼：代數(shù)基礎(chǔ)知識(shí)循環(huán)碼：代數(shù)基礎(chǔ)知識(shí)管理信息學(xué) 楊善林 胡笑旋編著第4章 信息傳輸與信息編碼2022-1-30二元多項(xiàng)式計(jì)算二元多項(xiàng)式計(jì)算例：計(jì)算例：計(jì)算F52x/(x3+1)F52x/(x3+1)，并分析其性質(zhì)。，并分析其性質(zhì)。例：計(jì)算例：計(jì)算(x8+x4+x+1)mod(x3+1)(x8+x4+x+1)mod(x3+1)。4.4.5 循環(huán)碼：代數(shù)基礎(chǔ)知識(shí)循環(huán)碼：代數(shù)基礎(chǔ)知識(shí)管理信息學(xué) 楊善林 胡笑旋編著第4章 信息傳輸與信息編碼2022-1-30定義定義4.16 設(shè)設(shè)C是二元是二元n，k線性碼，如果對線性

6、碼，如果對 都有都有則稱則稱C是循環(huán)碼。是循環(huán)碼。如如3，2線性碼線性碼000，110，101，011是循環(huán)碼。是循環(huán)碼。定理定理4.10 循環(huán)碼循環(huán)碼C的對偶碼的對偶碼C是循環(huán)碼。是循環(huán)碼。Cccccn),(110Ccccnn),(2014.4.5 循環(huán)碼：循環(huán)碼及其生成多項(xiàng)式循環(huán)碼：循環(huán)碼及其生成多項(xiàng)式管理信息學(xué) 楊善林 胡笑旋編著第4章 信息傳輸與信息編碼4.4.5 循環(huán)碼：循環(huán)碼及其生成多項(xiàng)式循環(huán)碼：循環(huán)碼及其生成多項(xiàng)式管理信息學(xué) 楊善林 胡笑旋編著第4章 信息傳輸與信息編碼2022-1-30例例2，C = 000, 110, 101, 011 是循環(huán)碼，那么是循環(huán)碼，那么 I(C)

7、= 0, 1+x, 1+x2, x+x2 。由于。由于 1+x 是是 I(C) 中次數(shù)最低的多項(xiàng)式，故中次數(shù)最低的多項(xiàng)式，故 g(x) = (1+x)，故，故 C 的生成矩陣為：的生成矩陣為：由定理由定理4.11知，任意一個(gè)循環(huán)碼可以唯一確定一個(gè)多項(xiàng)式，任知，任意一個(gè)循環(huán)碼可以唯一確定一個(gè)多項(xiàng)式，任給一個(gè)多項(xiàng)式，能否唯一地確定一個(gè)循環(huán)碼？給一個(gè)多項(xiàng)式，能否唯一地確定一個(gè)循環(huán)碼？110011G4.4.5 循環(huán)碼：循環(huán)碼及其生成多項(xiàng)式循環(huán)碼：循環(huán)碼及其生成多項(xiàng)式 循環(huán)碼循環(huán)碼(0000, 0101, 1010, 1111)的的 g(x) 和生成矩陣分別是什么？和生成矩陣分別是什么？管理信息學(xué) 楊善

8、林 胡笑旋編著第4章 信息傳輸與信息編碼2022-1-304.4.5 循環(huán)碼：循環(huán)碼及其生成多項(xiàng)式循環(huán)碼：循環(huán)碼及其生成多項(xiàng)式定理定理4.12 4.12 設(shè)設(shè) 滿足滿足 ，令，令 是是 在在Fn2xFn2x中生成的理想，即中生成的理想，即 ，那么，那么是一個(gè)二元是一個(gè)二元 的循環(huán)碼。的循環(huán)碼。定義定義4.17 4.17 設(shè)設(shè)C C是循環(huán)碼，假設(shè)是循環(huán)碼，假設(shè) 是是 中滿足中滿足 的次數(shù)最低的多項(xiàng)式，則稱的次數(shù)最低的多項(xiàng)式，則稱 是是C C的生成多項(xiàng)式。的生成多項(xiàng)式。顯然，顯然，C C的生成多項(xiàng)式是唯一的。的生成多項(xiàng)式是唯一的。2( ) ng xF x( )|1ng x x )(CI)(xg)(

9、)(xgCI)(| ),(1110110CIxcxcccccCnnn,gnn)(xg)()(xgCI)(xgFn2x管理信息學(xué) 楊善林 胡笑旋編著第4章 信息傳輸與信息編碼2022-1-304.4.5 循環(huán)碼：循環(huán)碼的校驗(yàn)多項(xiàng)式循環(huán)碼：循環(huán)碼的校驗(yàn)多項(xiàng)式定義定義4.18 4.18 設(shè)設(shè) ， ，則稱，則稱為為 的互反多項(xiàng)式。的互反多項(xiàng)式。顯然，顯然， 。容易證明，容易證明， 的充要條件是的充要條件是 。定理定理4.13 4.13 設(shè)設(shè) 是二元是二元 循環(huán)碼循環(huán)碼C C的生成多項(xiàng)式，令的生成多項(xiàng)式，令 ，那么，那么 是循環(huán)碼是循環(huán)碼 的生成多項(xiàng)式。的生成多項(xiàng)式。)(20111xFaxaxaxaxf

10、nnnn0naxfxxfnR1)()(xfnnnnRaxaxaxaxf1110)(1| )(nxxf1| )(nRxxf)(xg, kn)(1)(xgxxhn)(xhRC管理信息學(xué) 楊善林 胡笑旋編著第4章 信息傳輸與信息編碼2022-1-30設(shè)設(shè)G0,G1,Gk-1是二元是二元n, k循環(huán)碼循環(huán)碼C的基，則的基，則C的生成矩陣的生成矩陣為為G=(G0,G1,Gk-1)T。 設(shè)設(shè)hR(x)是是C的生成多項(xiàng)式，那么的生成多項(xiàng)式，那么hR(x), xhR(x),xn-k-1hR(x) 是是C的基，對應(yīng)的碼字分別記為的基，對應(yīng)的碼字分別記為H0,H1,Hn-k-1，令，令 則則H是碼是碼C的生成矩陣

11、，且的生成矩陣，且GHT=0。由于循環(huán)碼一定是線。由于循環(huán)碼一定是線性碼，因此性碼，因此cF2n為碼為碼C的碼字的充要條件是的碼字的充要條件是cHT=0。 nknknHHHH)(1104.4.5 循環(huán)碼：循環(huán)碼的校驗(yàn)多項(xiàng)式循環(huán)碼：循環(huán)碼的校驗(yàn)多項(xiàng)式管理信息學(xué) 楊善林 胡笑旋編著第4章 信息傳輸與信息編碼2022-1-304.4.5 循環(huán)碼：循環(huán)碼的校驗(yàn)多項(xiàng)式循環(huán)碼：循環(huán)碼的校驗(yàn)多項(xiàng)式解 由于dim C=4，故g(x), xg(x), x2g(x), x3g(x)是C的基，故C的生成矩陣為：管理信息學(xué) 楊善林 胡笑旋編著第4章 信息傳輸與信息編碼2022-1-301101000011010000

12、110100001101)()()()(32xgxxgxxxgxgG又 h(x) = (x7+1)/g(x) = x4+x3+x2+1故 hR(x) = x4h(1/x) = 1+x+x2+x4那么：HXT=0？X1=(1101001)， HX1T=(000)； X2=(1111100)，HX2T=(011)； 101110001011100010111H4.4.5 循環(huán)碼：循環(huán)碼的校驗(yàn)多項(xiàng)式循環(huán)碼：循環(huán)碼的校驗(yàn)多項(xiàng)式管理信息學(xué) 楊善林 胡笑旋編著第4章 信息傳輸與信息編碼2022-1-304.4.6 循環(huán)碼的編碼與譯碼循環(huán)碼的編碼與譯碼u 循環(huán)碼的除法編碼法循環(huán)碼的除法編碼法u 循環(huán)碼的乘法

13、編碼法循環(huán)碼的乘法編碼法u 循環(huán)碼的譯碼循環(huán)碼的譯碼管理信息學(xué) 楊善林 胡笑旋編著第4章 信息傳輸與信息編碼2022-1-30多項(xiàng)式變換多項(xiàng)式變換設(shè)設(shè) g(x) g(x) 是是 n, k n, k 循環(huán)碼循環(huán)碼 C C 的生成多項(xiàng)式，那么的生成多項(xiàng)式，那么 g(x), g(x), xg(x) , xk-1g(x)xg(x) , xk-1g(x)是是I(C) I(C) 的一組基，從而的一組基，從而 c(x) c(x)I(C) I(C) 當(dāng)當(dāng)且僅當(dāng)存在且僅當(dāng)存在 m0, m1, , mk-1 m0, m1, , mk-1F2F2使使即即c(x)c(x)對應(yīng)的碼字是原信息對應(yīng)的碼字是原信息(m0,

14、m1, mk-1)(m0, m1, mk-1)的編碼。的編碼。因 此 求 原 信 息 編 碼 等 價(jià) 于 求 原 信 息 對 應(yīng) 的 多 項(xiàng) 式因 此 求 原 信 息 編 碼 等 價(jià) 于 求 原 信 息 對 應(yīng) 的 多 項(xiàng) 式m(x)=m0+m1x+mk-1xk-1m(x)=m0+m1x+mk-1xk-1與與 C C 的生成多項(xiàng)式的生成多項(xiàng)式 g(x) g(x) 的乘積的的乘積的結(jié)果結(jié)果 c(x) = m(x)g(x) c(x) = m(x)g(x)。因此在工程上，循環(huán)碼可以用由。因此在工程上，循環(huán)碼可以用由 g(x) g(x) 確定的乘法電路完成。確定的乘法電路完成。 11011011( )

15、( )( )( )() ( )kkkkc xm g xm xg xmxg xmm xmxg x4.4.6 循環(huán)碼的編碼與譯碼：循環(huán)碼的乘法編碼法循環(huán)碼的編碼與譯碼：循環(huán)碼的乘法編碼法管理信息學(xué) 楊善林 胡笑旋編著第4章 信息傳輸與信息編碼2022-1-30例例5 給定原信息給定原信息1001，求以，求以g(x)=x3+x+1為生成多項(xiàng)式的為生成多項(xiàng)式的7,4循環(huán)碼的乘法編碼。循環(huán)碼的乘法編碼。 解：解：m(x)=1+x3，則，則c(x)=m(x)g(x)=(1+x3)(1+x+x3)= (1+x+x4+x6)所以，所以，c=(1100101)由于由于C的生成矩陣為的生成矩陣為則對應(yīng)信息則對應(yīng)信

16、息1001的碼字為的碼字為(1001)G=(1100101)，即乘法編，即乘法編碼結(jié)果正確。碼結(jié)果正確。1011000010110000101100001011G4.4.6 循環(huán)碼的編碼與譯碼：循環(huán)碼的乘法編碼法循環(huán)碼的編碼與譯碼：循環(huán)碼的乘法編碼法管理信息學(xué) 楊善林 胡笑旋編著第4章 信息傳輸與信息編碼2022-1-30步驟：步驟：由于循環(huán)碼一定是線性碼，因此線性碼的譯碼方法對循環(huán)碼由于循環(huán)碼一定是線性碼，因此線性碼的譯碼方法對循環(huán)碼當(dāng)然有效。故循環(huán)碼的譯碼也分為以下三步：當(dāng)然有效。故循環(huán)碼的譯碼也分為以下三步：(1) 計(jì)算收到的字計(jì)算收到的字 =(0, 1, n-1)的校驗(yàn)子的校驗(yàn)子s()

17、；(2) 根據(jù)校驗(yàn)子根據(jù)校驗(yàn)子 s() 找出錯(cuò)誤模式找出錯(cuò)誤模式 e()；(3) 將將譯為碼字譯為碼字 + e()。4.4.6 循環(huán)碼的編碼與譯碼：循環(huán)碼的譯碼循環(huán)碼的編碼與譯碼：循環(huán)碼的譯碼管理信息學(xué) 楊善林 胡笑旋編著第4章 信息傳輸與信息編碼2022-1-30定理定理4.14 4.14 設(shè)設(shè)H H 是二元是二元 循環(huán)碼循環(huán)碼C C的校驗(yàn)矩陣，的校驗(yàn)矩陣， 是是C C的的生成多項(xiàng)式，則對生成多項(xiàng)式，則對 的校驗(yàn)子的校驗(yàn)子 滿足滿足其中，其中， 。對對=(0,1,n-1)=(0,1,n-1)F2nF2n，則，則的校驗(yàn)子是的校驗(yàn)子是g(x)g(x)除除(x)(x)所得的余式對應(yīng)的向量。所得的余

18、式對應(yīng)的向量。 4.4.6 循環(huán)碼的編碼與譯碼：循環(huán)碼的譯碼循環(huán)碼的編碼與譯碼：循環(huán)碼的譯碼, kn)(xgnnF2110),( )S( )( )(mod ( )S xxg x11011011( ),( )nn knn kxxxS xss xsx 管理信息學(xué) 楊善林 胡笑旋編著第4章 信息傳輸與信息編碼2022-1-30利用校驗(yàn)子譯碼利用校驗(yàn)子譯碼定理定理4.15 4.15 設(shè)設(shè)g(x)g(x)是二元是二元n, k, dn, k, d的循環(huán)碼的循環(huán)碼C C的生的生成多項(xiàng)式，若收到的字成多項(xiàng)式，若收到的字滿足滿足 wt(s() (d- wt(s() (d-1)/2 1)/2 ，則，則應(yīng)譯為應(yīng)譯為

19、(x)+s(x)(x)+s(x)所對應(yīng)的碼字。所對應(yīng)的碼字。 其中其中s()s()是是的校驗(yàn)子。的校驗(yàn)子。4.4.6 循環(huán)碼的編碼與譯碼：循環(huán)碼的譯碼循環(huán)碼的編碼與譯碼：循環(huán)碼的譯碼管理信息學(xué) 楊善林 胡笑旋編著第4章 信息傳輸與信息編碼2022-1-30例例6 設(shè)設(shè)C是以是以 g(x) = x3+x2+1 為生成多項(xiàng)式的為生成多項(xiàng)式的7, 4, 3循環(huán)碼，循環(huán)碼，試譯收到的字試譯收到的字 = (0110110)解解 由于由于那么那么即即 s() = (010)又又 wt(s() = 1 = (3-1)/2，則，則(x)應(yīng)譯為：應(yīng)譯為：則譯為則譯為0010110）542542)()()(xxx

20、xxxxxxsx542)(xxxxx)(mod)(mod)(245xgxxgxxxxxs4.4.6 循環(huán)碼的編碼與譯碼：循環(huán)碼的譯碼循環(huán)碼的編碼與譯碼：循環(huán)碼的譯碼管理信息學(xué) 楊善林 胡笑旋編著第4章 信息傳輸與信息編碼2022-1-30 若收到的字若收到的字=(1011100)，則，則(x)=1+x2+x3+x4, 因此因此 s(x)(x)(mod g(x) 1+x+x2 (mod g(x), s()=(111)， 此時(shí)，此時(shí)，wt(s() = 3 (d-1)/2 = 1，無法譯出。，無法譯出。4.4.6 循環(huán)碼的編碼與譯碼：循環(huán)碼的譯碼循環(huán)碼的編碼與譯碼：循環(huán)碼的譯碼管理信息學(xué) 楊善林 胡

21、笑旋編著第4章 信息傳輸與信息編碼2022-1-30循環(huán)碼通用譯碼方法循環(huán)碼通用譯碼方法定理定理4.16循環(huán)碼的譯碼算法）循環(huán)碼的譯碼算法） 設(shè)設(shè) g(x) 是二元是二元 n, k, d 的循的循環(huán)碼的生成多項(xiàng)式，若收到的字環(huán)碼的生成多項(xiàng)式，若收到的字 (x) 滿足：滿足：(1) 至多有至多有(d-1)/2個(gè)錯(cuò)誤發(fā)生；個(gè)錯(cuò)誤發(fā)生；(2) 至少有連續(xù)至少有連續(xù) k 位碼元沒有發(fā)生錯(cuò)誤。位碼元沒有發(fā)生錯(cuò)誤。 記記 si (x) xi(x)(mod g(x) , i=0, 1, 2,找到找到 m 使使 sm(x) 對對應(yīng)字的漢明重量應(yīng)字的漢明重量 (d-1)/2. 設(shè)設(shè)e(x) xn-msm(x)(

22、mod xn+1)，則將，則將(x)譯為譯為(x)+ e(x)對對應(yīng)的碼字。應(yīng)的碼字。4.4.6 循環(huán)碼的編碼與譯碼：循環(huán)碼的譯碼循環(huán)碼的編碼與譯碼：循環(huán)碼的譯碼管理信息學(xué) 楊善林 胡笑旋編著第4章 信息傳輸與信息編碼2022-1-30例例7 設(shè)設(shè)C是以是以g(x)= x3+x2+1為生成多項(xiàng)式的為生成多項(xiàng)式的7, 4, 3循環(huán)碼，若收到循環(huán)碼，若收到的字都至多發(fā)生的字都至多發(fā)生1個(gè)錯(cuò)誤，且至少連續(xù)個(gè)錯(cuò)誤，且至少連續(xù)4位沒有發(fā)生錯(cuò)誤試譯位沒有發(fā)生錯(cuò)誤試譯=(1011100)解：解：(x)=(1011100)=1+x2+x3+x4，由于由于d = 3, 那么那么(d-1)/2=1,故要找故要找m使使sm(x)對應(yīng)的字的漢明重量對應(yīng)的字的漢明重量 1，計(jì)算計(jì)算si(x) xi(x)(mod g(x)，結(jié)果見右表。，結(jié)果見右表。由于由于s0(x)、 s1(x)、 s2(x)對應(yīng)的字的漢明重量都大于對應(yīng)的字的漢明重量都大于1，而，而s3(x)對對應(yīng)的字的漢明重量為應(yīng)的字的漢明重量為 1，故，故m=3。4.4.6 循環(huán)碼的編碼與譯碼：循環(huán)碼的譯碼循環(huán)碼的