糾錯(cuò)碼Lecture2-基本概念

1、信道編碼理論信道編碼理論 邢莉娟、李卓，西安電子科技大學(xué)邢莉娟、李卓，西安電子科技大學(xué) Lecture 2 Lecture 2 基本概念基本概念 信道編碼理論信道編碼理論 2 信道模型與錯(cuò)誤圖樣信道模型與錯(cuò)誤圖樣 差錯(cuò)控制系統(tǒng)分類差錯(cuò)控制系統(tǒng)分類 糾錯(cuò)碼的基本原理糾錯(cuò)碼的基本原理 最大似然譯碼最大似然譯碼 漢明距離與重量漢明距離與重量 碼糾錯(cuò)能力及編碼增益碼糾錯(cuò)能力及編碼增益 信道編碼定理與信道容量信道編碼定理與信道容量 Lecture 2 Lecture 2 基本概念基本概念 信道編碼理論信道編碼理論 3 三種判決方法三種判決方法 硬判決：勉強(qiáng)作出是硬判決：勉強(qiáng)作出是0還是還是1的判決的判決

2、 刪除符號(hào)：對(duì)該碼元暫且不作判決，而輸出一個(gè)刪除符號(hào)：對(duì)該碼元暫且不作判決，而輸出一個(gè) 未知或待定的信號(hào)未知或待定的信號(hào)“x” 軟判決：輸出一種有關(guān)該碼元的信息，例如關(guān)于軟判決：輸出一種有關(guān)該碼元的信息，例如關(guān)于 0和和1 的后驗(yàn)概率和似然概率的后驗(yàn)概率和似然概率 Lecture 2 Lecture 2 基本概念基本概念 信道編碼理論信道編碼理論 4 BSC：二進(jìn)制對(duì)稱信道：二進(jìn)制對(duì)稱信道 Z信道信道 1-p 1-p p p 00 11 1 1-p p 00 11 Lecture 2 Lecture 2 基本概念基本概念 信道編碼理論信道編碼理論 DMC:離散無(wú)記憶信道離散無(wú)記憶信道 BEC:

3、二進(jìn)制刪除信道二進(jìn)制刪除信道 5 0 1 1 0 q-2 q-1 P(0|0) P(1|0) P(q-2|0) P(q-1|0) P(q-2|0) P(q-2|1) P(1|1) P(0|1) 1-p p p 1-p 00 1 e 1 Lecture 2 Lecture 2 基本概念基本概念 信道編碼理論信道編碼理論 6 BIAWGN:離散輸入連續(xù)輸出信道離散輸入連續(xù)輸出信道 假定信道編碼器的輸出符號(hào)取自 ，譯碼器輸入 為連續(xù)值Y=R，我們稱這類信道為離散輸入連續(xù)輸出信道，典型 的有：二元輸入高斯白噪聲信道（BIAWGN）和二元拉普拉斯 (Laplace)信道 BIAWGN輸入輸出可表示為 Y

4、=X+N 其中，N為加性高斯白噪聲，其均值為零，方差為 。給定一個(gè)輸 入 ， ，則Y是均值為xk，方差為 的 高斯變量 其他信道其他信道:有記憶（突發(fā)）信道，組合信道有記憶（突發(fā)）信道，組合信道 011 , q x xx X 2 k Xx0,1,1kq 2 2 1 ( |)exp ()/2 2 kk p y Xxyx Lecture 2 Lecture 2 基本概念基本概念 信道編碼理論信道編碼理論 7 錯(cuò)誤圖樣錯(cuò)誤圖樣 發(fā)送序列發(fā)送序列C: (1111011000) 錯(cuò)誤圖樣錯(cuò)誤圖樣E: (1001001110) 接收序列接收序列R: (0110010110) R=C+E or E=C+R

5、突發(fā)圖樣突發(fā)圖樣: (100100111)；突發(fā)長(zhǎng)度：；突發(fā)長(zhǎng)度：9 二進(jìn)制運(yùn)算規(guī)則二進(jìn)制運(yùn)算規(guī)則 0 0 1 1 0 0 1 1 模2加 0 0 1 1 0 1 0 0 模2乘 Lecture 2 Lecture 2 基本概念基本概念 信道編碼理論信道編碼理論 8 FEC: 前向糾錯(cuò)方式前向糾錯(cuò)方式； ARQ: 重傳反饋方式重傳反饋方式 HEC: 混合糾錯(cuò)方式混合糾錯(cuò)方式; IRQ: 狹義信息反饋系統(tǒng)狹義信息反饋系統(tǒng) 可糾正錯(cuò)誤的碼 發(fā)收 FEC 能夠發(fā)現(xiàn)錯(cuò)誤的碼 發(fā)收 ARQ 應(yīng)答信號(hào) 能夠發(fā)現(xiàn)和糾正錯(cuò)誤的碼 發(fā)收 HEC 應(yīng)答信號(hào) 信息信號(hào) 發(fā)收 IRQ 信息信號(hào) Lecture 2 L

6、ecture 2 基本概念基本概念 信道編碼理論信道編碼理論 FEC: 前向糾錯(cuò)方式前向糾錯(cuò)方式 優(yōu)點(diǎn)：不需要反饋信道，譯碼實(shí)時(shí)性好，控制電路簡(jiǎn)單優(yōu)點(diǎn)：不需要反饋信道，譯碼實(shí)時(shí)性好，控制電路簡(jiǎn)單 缺點(diǎn)：譯碼設(shè)備復(fù)雜，信道適應(yīng)性較差缺點(diǎn)：譯碼設(shè)備復(fù)雜，信道適應(yīng)性較差 ARQ: 重傳反饋方式重傳反饋方式 優(yōu)點(diǎn)：編譯設(shè)備簡(jiǎn)單，糾錯(cuò)能力強(qiáng)，系統(tǒng)適應(yīng)性強(qiáng)優(yōu)點(diǎn)：編譯設(shè)備簡(jiǎn)單，糾錯(cuò)能力強(qiáng)，系統(tǒng)適應(yīng)性強(qiáng) 缺點(diǎn)：控制電路復(fù)雜，傳送消息的連貫性和實(shí)時(shí)性較差缺點(diǎn)：控制電路復(fù)雜，傳送消息的連貫性和實(shí)時(shí)性較差 HEC: 混合糾錯(cuò)方式混合糾錯(cuò)方式 特點(diǎn)：綜合了特點(diǎn)：綜合了FEC和和ARQ的優(yōu)點(diǎn)的優(yōu)點(diǎn) IRQ: 狹義信息反

7、饋系統(tǒng)狹義信息反饋系統(tǒng) 9 Lecture 2 Lecture 2 基本概念基本概念 信道編碼理論信道編碼理論 分組碼分組碼 分組碼是對(duì)每段分組碼是對(duì)每段k位長(zhǎng)的信息組，以一定的規(guī)則位長(zhǎng)的信息組，以一定的規(guī)則 增加增加r=n-k個(gè)校驗(yàn)元，組成長(zhǎng)為個(gè)校驗(yàn)元，組成長(zhǎng)為n的序列的序列(cn-1,cn-2, ,c1,c0)，稱這個(gè)序列為碼字（碼組、碼矢）。，稱這個(gè)序列為碼字（碼組、碼矢）。 卷積碼卷積碼 (n0,k0,m0)卷積碼是對(duì)每段卷積碼是對(duì)每段k0長(zhǎng)的信息組以一定的長(zhǎng)的信息組以一定的 規(guī)則增加規(guī)則增加r0=n0-k0個(gè)校驗(yàn)元，組成長(zhǎng)為個(gè)校驗(yàn)元，組成長(zhǎng)為n0的碼段。的碼段。 r0=n0-k0個(gè)校

8、驗(yàn)元不僅與本段的信息元有關(guān)，且與個(gè)校驗(yàn)元不僅與本段的信息元有關(guān)，且與 前前m段信息元有關(guān)，當(dāng)信息元不斷輸入時(shí)，輸出段信息元有關(guān)，當(dāng)信息元不斷輸入時(shí)，輸出 的碼序列是一個(gè)半無(wú)限長(zhǎng)序列。的碼序列是一個(gè)半無(wú)限長(zhǎng)序列。 10 Lecture 2 Lecture 2 基本概念基本概念 信道編碼理論信道編碼理論 11 以重復(fù)碼為例以重復(fù)碼為例 0000 1111 其他所有二進(jìn)制組合為禁用碼組(字) 若將每個(gè)比特重復(fù)n次，則構(gòu)成一個(gè)碼長(zhǎng)為n，信息位 長(zhǎng)度為1的(n,1)重復(fù)碼,且編碼效率(碼率) R=1/n n=2時(shí) 許用碼組：00, 11 禁用碼組：01, 10 可能接收碼字：00, 01, 10, 11

9、 能夠發(fā)現(xiàn)一個(gè)錯(cuò)誤，但不能糾正錯(cuò)誤能夠發(fā)現(xiàn)一個(gè)錯(cuò)誤，但不能糾正錯(cuò)誤 許用碼組(字) Lecture 2 Lecture 2 基本概念基本概念 信道編碼理論信道編碼理論 12 n=3 許用碼組：000, 111 禁用碼組：001, 010, 100, 101, 110, 011 可能接收碼字： 000, 001, 010, 100, 101, 110, 011, 111 能夠發(fā)現(xiàn)兩個(gè)錯(cuò)誤，糾正一個(gè)錯(cuò)誤能夠發(fā)現(xiàn)兩個(gè)錯(cuò)誤，糾正一個(gè)錯(cuò)誤 n=4 許用碼組：0000，1111 假定發(fā)送碼字為：00000 禁用碼組：0001, 0010, 0100, 1000, 0011, 0101, 0110, 110

10、0, 1001, 1010, 0111, 1101, 1110, 1011 能夠糾正一個(gè)錯(cuò)誤同時(shí)發(fā)現(xiàn)兩個(gè)錯(cuò)誤；或能夠糾正一個(gè)錯(cuò)誤同時(shí)發(fā)現(xiàn)兩個(gè)錯(cuò)誤；或發(fā)現(xiàn)三個(gè)錯(cuò)誤發(fā)現(xiàn)三個(gè)錯(cuò)誤 譯碼正確 譯碼失敗 譯碼錯(cuò)誤 Lecture 2 Lecture 2 基本概念基本概念 信道編碼理論信道編碼理論 13 譯碼失敗譯碼失?。鹤g碼器根據(jù)接收到的信號(hào)無(wú)法作出明 確判斷,不完備譯碼; 譯碼錯(cuò)誤譯碼錯(cuò)誤：譯碼器根據(jù)接收到的信號(hào)作出錯(cuò)誤判 斷; 完備譯碼完備譯碼：根據(jù)接收信號(hào)，譯碼器一定能作出是 哪一組信息的判斷 糾錯(cuò)碼的基本原理：糾錯(cuò)碼的基本原理： 在信息序列之后按照一定的規(guī)則添加一定長(zhǎng)度的保護(hù)在信息序列之后按照一

11、定的規(guī)則添加一定長(zhǎng)度的保護(hù) 比特比特(校驗(yàn)比特或監(jiān)督比特校驗(yàn)比特或監(jiān)督比特) Lecture 2 Lecture 2 基本概念基本概念 信道編碼理論信道編碼理論 14 譯碼問(wèn)題譯碼問(wèn)題 MC R；如何根據(jù)接收信號(hào)R估計(jì)發(fā)送序列C,進(jìn)而 估計(jì)信息序列M 設(shè)計(jì)譯碼算法的原則：使譯碼錯(cuò)誤概率最小 最大后驗(yàn)概率最大后驗(yàn)概率(MAP: Maximum Posterior Probability)譯碼譯碼 R E RPREPPRCCPREP RCCMinPREMinPMinPE 1MinP CC RMinP CC R RCCMaxP Lecture 2 Lecture 2 基本概念基本概念 信道編碼理論信

12、道編碼理論 在在先驗(yàn)等概的情況下，先驗(yàn)等概的情況下，MAP簡(jiǎn)化為簡(jiǎn)化為ML 由貝葉斯公式由貝葉斯公式 若發(fā)端發(fā)送每個(gè)碼字的概率均相同，則若發(fā)端發(fā)送每個(gè)碼字的概率均相同，則 15 | | ii i pp p p CR C CR R 1,2,1,2, , max|max| kk ii ii pp CRR C , 22 Lecture 2 Lecture 2 基本概念基本概念 信道編碼理論信道編碼理論 16 漢明距離漢明距離 兩個(gè)n重x、y之間，對(duì)應(yīng)位取值不同的 個(gè)數(shù)，稱為它們之間的漢明距離，用d(x,y)表示。 例如，若x=10101，y=01111，則 d(x,y)=3。 漢明重量漢明重量 n重

13、x中非零碼元的個(gè)數(shù)，稱為它的漢明 重量，簡(jiǎn)稱重量，用w(x)表示。 w(x)=3,w(y)=4 最小距離最小距離 (n, k)分組碼中，任意兩個(gè)碼字之間距 離的最小值，稱為該分組碼的最小漢明距離d0，簡(jiǎn) 稱最小距離。 0 ,(n,k) min, x y dd x y Lecture 2 Lecture 2 基本概念基本概念 信道編碼理論信道編碼理論 在在BSC信道中，最大似然譯碼信道中，最大似然譯碼=最小漢明距離譯碼最小漢明距離譯碼 由由 可知，可知，MLD譯碼器尋求可能出現(xiàn)的錯(cuò)誤圖樣，就譯碼器尋求可能出現(xiàn)的錯(cuò)誤圖樣，就 是在碼字集中，尋求與是在碼字集中，尋求與R的漢明距離最小的碼字的漢明距離

14、最小的碼字 Ci，為最可能發(fā)送碼字，即最小漢明距離譯碼。，為最可能發(fā)送碼字，即最小漢明距離譯碼。 17 1,2,1,2, , max|max| kk ii ii pp CRR C , 22 ERC Lecture 2 Lecture 2 基本概念基本概念 信道編碼理論信道編碼理論 18 任一任一(n, k)分組碼，若要在碼字內(nèi)：分組碼，若要在碼字內(nèi)： 1) 檢測(cè)e個(gè)隨機(jī)錯(cuò)誤，則要求碼的最小漢明距離 d0=e+1 2) 糾正t個(gè)隨機(jī)錯(cuò)誤，則要求d0=2t+1 3) 糾正t個(gè)隨機(jī)錯(cuò)誤，同時(shí)檢測(cè)e (e=t)個(gè)錯(cuò)誤，則要求 d0=e+t+1 4) 糾正t個(gè)隨機(jī)錯(cuò)誤和個(gè)刪除，則要求 d0=2t+1 編

15、碼增益：編碼增益： 給定性能前提下， 編碼增益編碼增益=未編碼時(shí)需要的信噪比未編碼時(shí)需要的信噪比(dB) 編碼時(shí)需要的編碼時(shí)需要的 信噪比信噪比(dB) Lecture 2 Lecture 2 基本概念基本概念 信道編碼理論信道編碼理論 19 信道編碼定理信道編碼定理 任意離散輸入無(wú)記憶平穩(wěn)有噪信道都有一個(gè)被稱為信信 道容量道容量的值C，它標(biāo)志著信道傳輸能力的上限上限，只要只要 信息傳輸速率信息傳輸速率RC，就存在一種編碼方式，當(dāng)平均碼，就存在一種編碼方式，當(dāng)平均碼 長(zhǎng)足夠大時(shí)，譯碼錯(cuò)誤概率可以做到任意小；反之，長(zhǎng)足夠大時(shí)，譯碼錯(cuò)誤概率可以做到任意??；反之， 則無(wú)論采用何種編碼方式也不可能保證

16、錯(cuò)誤概率任意則無(wú)論采用何種編碼方式也不可能保證錯(cuò)誤概率任意 小。小。 信道容量信道容量 信道容量定義為信道輸入與信道輸出的互信息信道輸入與信道輸出的互信息，它表 征了信道可靠傳輸?shù)淖畲笏俾省?這個(gè)容量?jī)H在輸入服從高斯分布的情況下輸入服從高斯分布的情況下可以達(dá)到。 如果輸入信號(hào)調(diào)制受限，那么容量將會(huì)小于上面這個(gè) 值。 Lecture 2 Lecture 2 基本概念基本概念 信道編碼理論信道編碼理論 20 BSC 對(duì)轉(zhuǎn)移概率為對(duì)轉(zhuǎn)移概率為p的二進(jìn)制對(duì)稱信道而言，當(dāng)輸?shù)亩M(jìn)制對(duì)稱信道而言，當(dāng)輸 入等概時(shí)，互信息取得最大值，信道容量為入等概時(shí)，互信息取得最大值，信道容量為 其中其中 是二元熵函數(shù)。是二元熵函數(shù)。 BEC 對(duì)于刪余概率為對(duì)于刪余概率為p的二進(jìn)制刪除信道，其信道的二進(jìn)制刪除信道，其信道 容量為容量為 22 1log(1)log (1) 1(