【正文】 性碼的編碼 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 例 : 設(shè) C是二元 ［ 6， 3］ 線性碼 ， 其生成矩陣為 求原始信息 A = 110, B = 010的編碼 。 證明提示： (1) d(C) = min{d(X,Y)}， wt(C) = min{d(X,0)},所以d(C) ≤ wt(C) (2) d(C) =min{d(X, Y)}= min{ wt(X+Y) } ≥ min{ wt(X) } = wt(C) 二元線性碼 ：線性碼的漢明重量 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 二元線性碼的檢錯(cuò)和糾錯(cuò)能力 定理 設(shè) H是二元 ［ n， k］ 線性碼 C的校驗(yàn)矩陣 ， 如果 H的任意 t 列都線性無(wú)關(guān) ， 且 H有 t+1 列線性相關(guān) ， 則 (1) d(C) = wt(C) = t + 1 (2) C是可檢 t 個(gè)錯(cuò)誤的檢錯(cuò)碼 ， 且 C是可糾 [t/2]個(gè)錯(cuò)誤的糾 錯(cuò)碼 二元線性碼 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 二元線性碼的檢錯(cuò)和糾錯(cuò)能力 證明提示： （ 1） ① 任何碼字 c∈ C的漢明重量均 ≥t+1。 二元線性碼 ：線性碼的生成矩陣與校驗(yàn)矩陣 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 定義 稱 C⊥ 的生成矩陣 H為 C的校驗(yàn)矩陣 。 設(shè) h1, h2,… , hnk是 C⊥ 的基 ， 則 是 C⊥ 的生成矩陣 。 S = {1000 , 0100 , 0000 , 1100} 是 [ 4, 2 ] 線性碼 二元線性碼 ： 線性碼的生成矩陣與校驗(yàn)矩陣 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 線性碼的碼字個(gè)數(shù) 定理 : 設(shè) C是二元 [ n, k ] 線性碼 ， 則 (1) C恰好含有 M=2k個(gè)碼字； (2)當(dāng) C是自對(duì)偶碼時(shí)， k = n/2。 則 X的基礎(chǔ)解系含有 nk 個(gè)解向量 。 二元線性碼 ：有限域上的線性空間 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 ?定義 : 設(shè) 則稱： 為 X 與 Y 的內(nèi)積；如果 X 線性碼是最基礎(chǔ)的也是最重要的碼 。 檢錯(cuò)與糾錯(cuò)能力定理 例： {0000,0101,1010,1 11}； t =1。 ?例： 在碼長(zhǎng)為 5的碼 C=｛ 00000， 00011， 00111， 11111｝ 中，由于 d(00011， 00111) = 1，而其它任何兩個(gè)不同碼字的漢明距離都 ≥2，故 d( C ) = 1，從而 C是 (5， 4， 1)碼 。 ?若記 則 d(X,Y) = d(x1,y1) + d(x2,y2) + … d(xn,yn) 1,( , )0,iiiiiixyd x yxy??? ??? 信道編碼：極大似然譯碼法 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 ?漢明距離性質(zhì)： ?(1) (非負(fù)且有界性 ) 0 ≤ d (X, Y) ≤ n； ?(2) (自反性 ) d (X,Y) = 0當(dāng)且僅當(dāng) X = Y； ? (3) (對(duì)稱性 ) d (X, Y) = d (Y, X)； ?(4) (三角不等式 ) d (X, Z) ≤ d (X, Y) + d (Y, Z) 信道編碼：極大似然譯碼法 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 漢明距離譯碼 ? 設(shè)收到字 A，在所有碼字中，如果 c是與 A的漢明距離最小的碼字（ 即 c是發(fā)生傳送錯(cuò)誤分量個(gè)數(shù)最少的碼字而成為 A的 ），從而在所有碼字中， c 是前向傳送概率最大而成為 A的碼字，因此應(yīng)將 A譯為 c，從而 等價(jià)于將 A譯成與 A的漢明距離最小的碼字。 如果發(fā)送碼字 CA 收到 A 的前向傳送概率達(dá)到最大值 ， 即 則將 A 譯為 CA， 稱這種譯碼方法為 極大似然譯碼法 (Maximum likelihood decoding)。 ? 如果我們把信道輸入符號(hào)重復(fù)傳輸 N次，即對(duì)于信源符號(hào)“ 0”，信道輸入端不只發(fā)一個(gè)“ 0”，而是連續(xù)發(fā) N個(gè)“ 0”；對(duì)于信源符號(hào)“ 1”，信道輸入端不只發(fā)一個(gè)“ 1”，而是連續(xù)發(fā) N個(gè)“ 1”。 40 1 2 3 40( ) , , , , , iic c c c c c c????? ???? ?500iir??? 信道編碼 ：檢錯(cuò)與糾錯(cuò)原理 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 定義 設(shè)原信息集合是 F2上 k 維向量組成的向量空間 Vk， σ是 Vk到 Vn 的一個(gè)單射 (nk)，則稱 Vk 的全體象 C = σ(Vk) 為碼， C中的每一個(gè) n 維向量為 碼字 ，碼字的分量稱為 碼元?？垢蓴_的有效做法是在采用種種技術(shù)措施的同時(shí)，在信息傳送前進(jìn)行一次抗干擾編碼，再傳送抗干擾編碼后的數(shù)字信息。 信道編碼 ：二元對(duì)稱傳送 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 ?如果在傳送過(guò)程中，傳送任何一個(gè)信息是否發(fā)生錯(cuò)誤與前面已傳送的信息是否發(fā)生了錯(cuò)誤無(wú)關(guān)，則稱這種傳送為 無(wú)記憶傳送 。0=0 Ct 實(shí)際上是信道的最大信息傳輸速率。定義這個(gè)最大的信息傳輸率為信道容量，記為 C。Y ) 是信源概率分布 P(X) 和信道轉(zhuǎn)移概率分布 P(Y|X) 的函數(shù)。它是平均意義上每傳送一個(gè)符號(hào)流經(jīng)信道的信息量。 信道及信道容量 ( | )( 。 上式稱 I(X。 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 信道矩陣 設(shè)輸入 X的符號(hào)表是 {a1, a2, …, a n}，輸出 Y的符號(hào)表是 {b1, b2, …, b m}。這個(gè)數(shù)學(xué)模型也可以寫作 { X P(Y|X) Y}。 1 1 2 1 11 2 2 2 212( | ) ( | ) ( | )( | ) ( | ) ( | )( | ) ( | ) ( | )mmn n m np b a p b a p b ap b a p b a p b ap b a p b a p b a???????? 信道及信道容量 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 互信息公式： 互信息表示當(dāng)收到 bj后 ， 可以提取到的關(guān)于 ai的信息量。 Y) 克服了互信息的隨機(jī)性，成為一個(gè)確定的量，因此可以作為信道中信息流通的測(cè)度。 Y)。 Y ) 信道及信道容量 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 由于 I( X。 而總能找到某一種 P(X)（即某一種信源），使信道所能傳送的信息率達(dá)到最大。若信道平均傳輸一個(gè)符號(hào)需要事件 t，則單位時(shí)間的信道容量為 Ct的單位是比特 /秒，用 bit/s表示。1=1， 1 如前文的英文字母示例。 二元對(duì)稱傳送 信道編碼 ：二元對(duì)稱傳送 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 ? 抗干擾編碼 ： 數(shù)字信息在傳送過(guò)程中會(huì)受到各種可能的干擾而出現(xiàn)錯(cuò)誤，這樣收到的信息可能就不是傳送的原信息。傳送 σ(c)，設(shè)收到的向量是r=(r0,r1,r2,r3,r4,r5)，則 : 若 ，則在傳送過(guò)程中一定發(fā)生了錯(cuò)誤，且有奇數(shù)個(gè)分量發(fā)生了錯(cuò)誤；否則傳送過(guò)程可能沒(méi)有發(fā)生錯(cuò)誤，也可能發(fā)生了偶數(shù)個(gè)錯(cuò)誤。 信道編碼 ：檢錯(cuò)與糾錯(cuò)原理 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 示例 5維原信息 (數(shù)組信息 ) 編碼 (1位奇偶校驗(yàn)碼 ) 6維編碼信息 00000 0 000000 00001 1 000011 … … … 11010 1 110101 11011 0 110110 11100 1 111001 11101 0 111010 11110 0 111100 11111 1 111111 k=5 n=6 碼空間 Vn 碼字 碼元 原信息空間 Vk 映射 ? 信道編碼 ：檢錯(cuò)與糾錯(cuò)原理 管理信息學(xué) 楊善林 胡笑旋編著 第 4章 信息傳輸與信息編碼 2022/2/5 ? 如果 p = ，從統(tǒng)計(jì)意義上講，每發(fā)送 100個(gè)符號(hào)就可能有一個(gè)錯(cuò)誤產(chǎn)生，這顯然不能滿足傳輸?shù)囊蟆? )(21)|(13222222381