第9章差錯(cuò)控制編碼

1、通信原理簡(jiǎn)明教程（第通信原理簡(jiǎn)明教程（第2版）版）2007年12月12007年12月2 信源編碼，目的是實(shí)現(xiàn)模擬信號(hào)數(shù)字化信源編碼，目的是實(shí)現(xiàn)模擬信號(hào)數(shù)字化 信道編碼，目的是提高數(shù)字通信的可靠性信道編碼，目的是提高數(shù)字通信的可靠性 差錯(cuò)率是信噪比的函數(shù)差錯(cuò)率是信噪比的函數(shù) 信道編碼，差錯(cuò)控制編碼，抗干擾編碼信道編碼，差錯(cuò)控制編碼，抗干擾編碼 信道編碼過(guò)程：信道編碼過(guò)程： 信息碼元序列監(jiān)督碼元信息碼元序列監(jiān)督碼元編碼碼組編碼碼組 信道譯碼過(guò)程：信道譯碼過(guò)程： 編碼碼組編碼碼組檢錯(cuò)或糾錯(cuò)檢錯(cuò)或糾錯(cuò)信息碼元序列信息碼元序列2007年12月3 9.1差錯(cuò)控制編碼的基本概念差錯(cuò)控制編碼的基本概念 9.2

2、線性分組碼線性分組碼 9.3循環(huán)碼循環(huán)碼 9.4卷積碼卷積碼 9.5 差錯(cuò)控制編碼對(duì)系統(tǒng)性能的改善差錯(cuò)控制編碼對(duì)系統(tǒng)性能的改善 9.6 數(shù)字通信系統(tǒng)的應(yīng)用舉例數(shù)字通信系統(tǒng)的應(yīng)用舉例 2007年12月4 9.1.1差錯(cuò)控制方式差錯(cuò)控制方式 9.1.2差錯(cuò)控制編碼分類差錯(cuò)控制編碼分類 9.1.3幾種簡(jiǎn)單的檢錯(cuò)碼幾種簡(jiǎn)單的檢錯(cuò)碼 9.1.4檢錯(cuò)和糾錯(cuò)的基本原理檢錯(cuò)和糾錯(cuò)的基本原理2007年12月5 常用的差錯(cuò)控制方式有三種：常用的差錯(cuò)控制方式有三種： 前向糾錯(cuò)（前向糾錯(cuò)（FEC:forward error correction） 發(fā)送能糾錯(cuò)的碼，在譯碼時(shí)自動(dòng)發(fā)現(xiàn)并糾正傳輸中的錯(cuò)誤發(fā)送能糾錯(cuò)的碼，在譯

3、碼時(shí)自動(dòng)發(fā)現(xiàn)并糾正傳輸中的錯(cuò)誤 只需正向信道，實(shí)時(shí)性好只需正向信道，實(shí)時(shí)性好 編譯碼設(shè)備復(fù)雜，適合單向信道和一發(fā)多收系統(tǒng)編譯碼設(shè)備復(fù)雜，適合單向信道和一發(fā)多收系統(tǒng) 檢錯(cuò)重發(fā)（檢錯(cuò)重發(fā)（ARQ:automatic repeat request） 發(fā)送端發(fā)出能夠檢錯(cuò)的碼，接收端檢驗(yàn)，接收端發(fā)出反饋應(yīng)答信號(hào)，發(fā)送端發(fā)出能夠檢錯(cuò)的碼，接收端檢驗(yàn)，接收端發(fā)出反饋應(yīng)答信號(hào)，發(fā)送端重新傳輸發(fā)送端重新傳輸 直到正確接收為止直到正確接收為止 工作原理簡(jiǎn)單，正向信道工作原理簡(jiǎn)單，正向信道+反向信道，傳輸效率低反向信道，傳輸效率低 混合糾錯(cuò)（混合糾錯(cuò)（HEC:hybrid error correction） 前向糾

4、錯(cuò)方式和檢錯(cuò)重發(fā)方式的結(jié)合與折衷前向糾錯(cuò)方式和檢錯(cuò)重發(fā)方式的結(jié)合與折衷 外層先采用前向糾錯(cuò)，當(dāng)前向糾錯(cuò)不能解決問(wèn)題時(shí)，內(nèi)層再采用檢錯(cuò)外層先采用前向糾錯(cuò)，當(dāng)前向糾錯(cuò)不能解決問(wèn)題時(shí)，內(nèi)層再采用檢錯(cuò)重發(fā)重發(fā)。2007年12月6 （a） FEC方式方式 （b）ARQ方式方式 （c） HEC方式方式2007年12月7 檢檢 錯(cuò)錯(cuò) 重重 發(fā)發(fā) 的的 三三 種種 方方 式式 停發(fā)等候重發(fā)停發(fā)等候重發(fā)返回重發(fā)返回重發(fā)選擇重發(fā)選擇重發(fā)2007年12月89.1.2 9.1.2 差錯(cuò)控制編碼分類差錯(cuò)控制編碼分類在編碼前先把信息序列分為在編碼前先把信息序列分為k位一組（稱為位一組（稱為信息信息碼碼），然后附加），然后

5、附加m位位監(jiān)督碼監(jiān)督碼，形成，形成n = k + m位的碼組。位的碼組。1、按信息碼和附加監(jiān)督碼間的檢驗(yàn)關(guān)系、按信息碼和附加監(jiān)督碼間的檢驗(yàn)關(guān)系 線性碼：監(jiān)督碼是信息碼的線性組合線性碼：監(jiān)督碼是信息碼的線性組合 非線性碼：監(jiān)督碼是信息碼的非線性組合非線性碼：監(jiān)督碼是信息碼的非線性組合2、按信息碼和監(jiān)督碼間的約束方式、按信息碼和監(jiān)督碼間的約束方式 分組碼：監(jiān)督碼僅與本碼組的信息碼有關(guān)分組碼：監(jiān)督碼僅與本碼組的信息碼有關(guān) 卷積碼：監(jiān)督碼與之前的若干個(gè)信息碼組的碼元有約束關(guān)系卷積碼：監(jiān)督碼與之前的若干個(gè)信息碼組的碼元有約束關(guān)系2007年12月91. 奇偶監(jiān)督碼奇偶監(jiān)督碼 編碼方法編碼方法 把信息碼元先

6、分組，在每組最后加一位監(jiān)督碼元，使把信息碼元先分組，在每組最后加一位監(jiān)督碼元，使該碼組中該碼組中1的數(shù)目為奇數(shù)或偶數(shù)的數(shù)目為奇數(shù)或偶數(shù) 奇數(shù)時(shí)稱為奇校驗(yàn)碼奇數(shù)時(shí)稱為奇校驗(yàn)碼 偶數(shù)時(shí)稱為偶校驗(yàn)碼偶數(shù)時(shí)稱為偶校驗(yàn)碼 偶校驗(yàn)碼偶校驗(yàn)碼 許用碼組為許用碼組為000，011，101，110 禁用碼組為禁用碼組為001，010，100，111 奇校驗(yàn)碼奇校驗(yàn)碼 禁用碼組為禁用碼組為000，011，101，110 許用碼組為許用碼組為001，010，100，1112007年12月10一般情況下：一般情況下： 設(shè)碼組長(zhǎng)為設(shè)碼組長(zhǎng)為n，且為：，且為： 則偶校驗(yàn)時(shí)有：則偶校驗(yàn)時(shí)有： 奇校驗(yàn)時(shí)有：奇校驗(yàn)時(shí)有： 譯碼

7、方法譯碼方法(與編碼方法相對(duì)應(yīng)與編碼方法相對(duì)應(yīng)) 不滿足校驗(yàn)關(guān)系，傳輸一定錯(cuò)誤！不滿足校驗(yàn)關(guān)系，傳輸一定錯(cuò)誤！ 奇偶校驗(yàn)只能發(fā)現(xiàn)奇數(shù)個(gè)奇偶校驗(yàn)只能發(fā)現(xiàn)奇數(shù)個(gè)(單個(gè)單個(gè))錯(cuò)誤，不能檢測(cè)出錯(cuò)誤，不能檢測(cè)出偶數(shù)個(gè)錯(cuò)誤。偶數(shù)個(gè)錯(cuò)誤。 編碼方法簡(jiǎn)單且實(shí)用性強(qiáng)，適用于檢測(cè)隨機(jī)零星錯(cuò)碼編碼方法簡(jiǎn)單且實(shí)用性強(qiáng)，適用于檢測(cè)隨機(jī)零星錯(cuò)碼 滿足校驗(yàn)關(guān)系，傳輸一定準(zhǔn)確嗎？滿足校驗(yàn)關(guān)系，傳輸一定準(zhǔn)確嗎？0321aaaannn0 110naaa1 110naaa2007年12月112. 二維奇偶監(jiān)督碼二維奇偶監(jiān)督碼 將奇偶校驗(yàn)碼的若干碼組排列成矩陣將奇偶校驗(yàn)碼的若干碼組排列成矩陣 每一碼組寫(xiě)成一行每一碼組寫(xiě)成一行 m個(gè)碼

8、組個(gè)碼組m行行 m個(gè)監(jiān)督位構(gòu)成了一監(jiān)督位列個(gè)監(jiān)督位構(gòu)成了一監(jiān)督位列 按列的方向增加第二維校驗(yàn)位按列的方向增加第二維校驗(yàn)位 n個(gè)監(jiān)督位構(gòu)成了一監(jiān)督位行個(gè)監(jiān)督位構(gòu)成了一監(jiān)督位行maaa02010 021cccnn012101212021222110111211ccccaaaaaaaaaaaannmmmnmnnnnn檢錯(cuò)能力檢錯(cuò)能力 檢出所有行和列中的奇數(shù)個(gè)檢出所有行和列中的奇數(shù)個(gè)差錯(cuò)差錯(cuò) 能檢出大多數(shù)偶數(shù)個(gè)差錯(cuò)能檢出大多數(shù)偶數(shù)個(gè)差錯(cuò) 檢測(cè)突發(fā)錯(cuò)碼也有一定的適檢測(cè)突發(fā)錯(cuò)碼也有一定的適應(yīng)能力應(yīng)能力方陣碼，交織碼方陣碼，交織碼2007年12月123. 重復(fù)碼重復(fù)碼 重復(fù)碼是在每位信息碼元之后，再簡(jiǎn)單重復(fù)

9、多次的編碼；重復(fù)碼是在每位信息碼元之后，再簡(jiǎn)單重復(fù)多次的編碼；接收端譯碼時(shí)采用多數(shù)表決法接收端譯碼時(shí)采用多數(shù)表決法 。4. 恒比碼恒比碼 從固定碼長(zhǎng)的碼組中選擇那些從固定碼長(zhǎng)的碼組中選擇那些1和和0的比例恒定的碼組作的比例恒定的碼組作為許用碼組，如五單位保護(hù)電碼等。為許用碼組，如五單位保護(hù)電碼等。5. ISBN國(guó)際統(tǒng)一圖書(shū)編號(hào)國(guó)際統(tǒng)一圖書(shū)編號(hào)2007年作了修改年作了修改2007年12月139.1.4 9.1.4 檢錯(cuò)與糾錯(cuò)的基本原理檢錯(cuò)與糾錯(cuò)的基本原理 差錯(cuò)編碼的基本思想是在被傳輸?shù)男畔⒅懈郊硬铄e(cuò)編碼的基本思想是在被傳輸?shù)男畔⒅懈郊颖O(jiān)督碼，用監(jiān)督碼，用信息的冗余度信息的冗余度來(lái)實(shí)現(xiàn)檢錯(cuò)和糾錯(cuò)。

10、來(lái)實(shí)現(xiàn)檢錯(cuò)和糾錯(cuò)。例如：例如：000000、001001、010010、011011、100100、101101、110110、111111用來(lái)傳遞信息，則無(wú)法檢錯(cuò)；用來(lái)傳遞信息，則無(wú)法檢錯(cuò)；000000、011011、101101、110110用來(lái)傳遞信息可以檢一位錯(cuò)，用來(lái)傳遞信息可以檢一位錯(cuò)，但無(wú)法糾錯(cuò)；但無(wú)法糾錯(cuò)；000000、111111用來(lái)傳遞信息可以檢一位或兩位錯(cuò)碼，還用來(lái)傳遞信息可以檢一位或兩位錯(cuò)碼，還可以糾一位錯(cuò)碼?？梢约m一位錯(cuò)碼。 可見(jiàn)，碼組間的差異與糾檢錯(cuò)能力十分重要?？梢?jiàn)，碼組間的差異與糾檢錯(cuò)能力十分重要。2007年12月14 定義定義1：碼組中非零碼元的數(shù)目稱為碼組的重

11、量，簡(jiǎn)稱碼組中非零碼元的數(shù)目稱為碼組的重量，簡(jiǎn)稱碼重。碼重。 定義定義2：兩碼組中對(duì)應(yīng)碼位上具有不同碼元的數(shù)目稱為兩碼組中對(duì)應(yīng)碼位上具有不同碼元的數(shù)目稱為兩碼組的距離，簡(jiǎn)稱碼距，又叫漢明距。兩碼組的距離，簡(jiǎn)稱碼距，又叫漢明距。 最小漢明距離最小漢明距離dmin決定糾檢錯(cuò)能力決定糾檢錯(cuò)能力 例例 8種碼組種碼組000000、001001、010010、011011、100100、101101、110110、111111均均為許用碼組時(shí)，最小碼距為為許用碼組時(shí)，最小碼距為1 在選在選4種碼組種碼組000000、011011、101101、110110為許用碼組情況下，最為許用碼組情況下，最小碼距為

12、小碼距為2 采用采用2種許用碼組種許用碼組000000、111111時(shí)，最小碼距為時(shí)，最小碼距為32007年12月15下圖為碼距的幾何解釋下圖為碼距的幾何解釋三種編碼組合，其漢明距分別為三種編碼組合，其漢明距分別為1，2，3。2007年12月16 對(duì)于分組碼，一般有如下結(jié)論：對(duì)于分組碼，一般有如下結(jié)論： (1) (1) 在一個(gè)碼組內(nèi)檢測(cè)在一個(gè)碼組內(nèi)檢測(cè)e e個(gè)誤碼，要求個(gè)誤碼，要求 ； (2) (2) 在一個(gè)碼組內(nèi)糾正在一個(gè)碼組內(nèi)糾正t t個(gè)誤碼，要求個(gè)誤碼，要求 ； (3) (3) 在一個(gè)碼組內(nèi)糾正在一個(gè)碼組內(nèi)糾正t t個(gè)誤碼，同時(shí)檢測(cè)個(gè)誤碼，同時(shí)檢測(cè) 個(gè)誤個(gè)誤碼，要求碼，要求 。 差錯(cuò)控制

13、編碼提高了通信系統(tǒng)的可靠性，也降低了有效差錯(cuò)控制編碼提高了通信系統(tǒng)的可靠性，也降低了有效性。性。 為衡量有效性，定義編碼效率為衡量有效性，定義編碼效率 。k k是編碼前碼組中的碼元數(shù)，即信息碼元數(shù)是編碼前碼組中的碼元數(shù)，即信息碼元數(shù)；n n是編碼后碼組中的碼元數(shù)，它包含了校驗(yàn)碼元是編碼后碼組中的碼元數(shù)，它包含了校驗(yàn)碼元。 1min ed12min td)(tee1minetdnkR/c2007年12月179.2 9.2 線性分組碼線性分組碼 線性碼組中的監(jiān)督碼是信息碼元的線性組合。線性碼組中的監(jiān)督碼是信息碼元的線性組合。 線性碼具有封閉性，即任意兩個(gè)許用碼組之和（模線性碼具有封閉性，即任意兩個(gè)

14、許用碼組之和（模2加），結(jié)果仍為一許用碼組。加），結(jié)果仍為一許用碼組。 設(shè)設(shè)n位分組碼用位分組碼用 表示，表示，k位信息碼用位信息碼用 表示，記該碼組為表示，記該碼組為(n , k)碼。碼。 將碼組和信息碼組用行矩陣表示出來(lái)，則有：將碼組和信息碼組用行矩陣表示出來(lái)，則有： nccc,21kddd,21nccc,21Ckddd,21D2007年12月18 kmkmmnkkkkkkkkdhdhdhcdhdhdhcdhdhdhcdcdcdc 221122221212121211112211n=k+m，n：編碼以后的位數(shù)：編碼以后的位數(shù)k：編碼以前的位數(shù)，即：編碼以前的位數(shù)，即信息碼信息碼m=n-k：

15、監(jiān)督位或校驗(yàn)位：監(jiān)督位或校驗(yàn)位2007年12月19 寫(xiě)成矩陣形式，有寫(xiě)成矩陣形式，有 ，G為生成矩陣為生成矩陣(k*n)，且：，且： 設(shè)設(shè) 則則GDCmkkkmmhhhhhhhhh212221212111100000100001G100000100001kImkkkmmhhhhhhhhh212221212111PmkkCDDPDDPDIPIDC , , , ,k行行k+m =n列列2007年12月20 與監(jiān)督位或校驗(yàn)位相對(duì)應(yīng)與監(jiān)督位或校驗(yàn)位相對(duì)應(yīng) 編碼的根據(jù)編碼的根據(jù) 譯碼的根據(jù)，檢糾錯(cuò)的根據(jù)譯碼的根據(jù)，檢糾錯(cuò)的根據(jù)矩陣矩陣P如何選擇？如何選擇？ 編碼前信息碼組有編碼前信息碼組有k位碼元，位碼

16、元，k位碼元共有位碼元共有 種組合種組合 編碼后碼組有編碼后碼組有n位碼元，位碼元，n位碼元共有位碼元共有 種組合，種組合， 矩陣矩陣P可有多種選擇可有多種選擇 較強(qiáng)的檢錯(cuò)或糾錯(cuò)能力較強(qiáng)的檢錯(cuò)或糾錯(cuò)能力 實(shí)現(xiàn)方法盡可能簡(jiǎn)單且編碼效率高實(shí)現(xiàn)方法盡可能簡(jiǎn)單且編碼效率高 在數(shù)學(xué)上已經(jīng)證明在數(shù)學(xué)上已經(jīng)證明 線性碼的最小碼距正好等于非零碼的最小碼重線性碼的最小碼距正好等于非零碼的最小碼重 為了估算線性碼的差錯(cuò)控制能力應(yīng)首先求出碼組的最為了估算線性碼的差錯(cuò)控制能力應(yīng)首先求出碼組的最小碼距小碼距k22nkn22 2007年12月21例例9-19-1已知已知(6,3)(6,3)碼的生成矩陣為碼的生成矩陣為G

17、G，試求：，試求：(1) (1) 編碼碼組編碼碼組和各碼組的碼重；和各碼組的碼重；(2) (2) 最小碼距最小碼距 及其差錯(cuò)控制及其差錯(cuò)控制能力。能力。 解解(1) (1) 由由3 3位碼組成的信息碼組矩陣為位碼組成的信息碼組矩陣為D D：011100110010101001Gmind111011101001110010100000D2007年12月22 由式由式 ，得碼組矩陣為：，得碼組矩陣為： 信息碼組、編碼碼組及碼重如下表所示：信息碼組、編碼碼組及碼重如下表所示：信息碼組信息碼組 編碼碼組編碼碼組 碼重碼重W 信息碼組信息碼組 編碼碼組編碼碼組 碼重碼重W0 0 0 0 0 0 0 0

18、0 0 1 0 0 1 0 0 1 0 1 30 0 1 0 0 1 1 1 0 3 1 0 1 1 0 1 0 1 1 40 1 0 0 1 0 0 1 1 3 1 1 0 1 1 0 1 1 0 40 1 1 0 1 1 1 0 1 4 1 1 1 1 1 1 0 0 0 3GDC000 011 110 101 101 110 011 000 111011101001110010100000011100110010101001 111011101001110010100000C2007年12月23 由前表可知，非零碼組的最小碼重為：由前表可知，非零碼組的最小碼重為： 所以最小碼距為：所以最

19、小碼距為： 因此，該碼有糾因此，該碼有糾1 1錯(cuò)，或檢錯(cuò)，或檢2 2錯(cuò)，或糾一錯(cuò)同時(shí)檢一錯(cuò)錯(cuò)，或糾一錯(cuò)同時(shí)檢一錯(cuò)的能力。的能力。 3minW3mind2007年12月24譯碼原理譯碼原理 由由 可知，可知， 或?qū)懗苫驅(qū)懗?設(shè)設(shè) ，則有，則有 。 任何線性分組碼碼組都應(yīng)該滿足上述關(guān)系任何線性分組碼碼組都應(yīng)該滿足上述關(guān)系 信息碼與監(jiān)督碼間的校驗(yàn)關(guān)系完全取決于信息碼與監(jiān)督碼間的校驗(yàn)關(guān)系完全取決于H H矩陣稱為矩陣稱為校驗(yàn)矩陣校驗(yàn)矩陣或或監(jiān)督矩陣，是譯碼的關(guān)鍵！監(jiān)督矩陣，是譯碼的關(guān)鍵！mkkCDDPDDPDIPIDC , , , ,mm 0DPCDPC, mm0PDCITm，HPIT 0CH2007年

20、12月25 設(shè)接收碼組為設(shè)接收碼組為R，它可分解為，它可分解為 。 其中，其中，C為正確碼組，為正確碼組，E為錯(cuò)誤碼組（差錯(cuò)圖案）為錯(cuò)誤碼組（差錯(cuò)圖案） 當(dāng)無(wú)錯(cuò)接收時(shí)，當(dāng)無(wú)錯(cuò)接收時(shí)，E為為0，當(dāng)有錯(cuò)接收時(shí)，當(dāng)有錯(cuò)接收時(shí)，E為非零矢量為非零矢量。 再設(shè)伴隨矩陣為：再設(shè)伴隨矩陣為： ， 則有：則有： 當(dāng)出現(xiàn)錯(cuò)碼時(shí)，當(dāng)出現(xiàn)錯(cuò)碼時(shí)，S為非零矢量，則根據(jù)上式可求得為非零矢量，則根據(jù)上式可求得E，然后再經(jīng)過(guò)計(jì)算然后再經(jīng)過(guò)計(jì)算 ，便可得到正確的碼組了。，便可得到正確的碼組了。ECR+=TRHS TTTEHEHCHSERC只與只與E有關(guān)，而與發(fā)送有關(guān)，而與發(fā)送的碼字的碼字C無(wú)關(guān)。只反映無(wú)關(guān)。只反映信道對(duì)碼字的

21、干擾信道對(duì)碼字的干擾RHT=S - E - C=R+E2007年12月26 由于信息碼組有由于信息碼組有 個(gè)，由于由個(gè)，由于由S計(jì)算出來(lái)的計(jì)算出來(lái)的E不唯一，不唯一，糾正后的糾正后的C就不同，這時(shí)，使用就不同，這時(shí)，使用最大似然比準(zhǔn)則最大似然比準(zhǔn)則，選擇，選擇與與R最接近的最接近的C作為正確的接收碼組。方法是：作為正確的接收碼組。方法是：在在 E中選擇碼重最中選擇碼重最 小的小的E，即表示，即表示 選擇與選擇與R最接近最接近 的的C。 右圖是查表法譯右圖是查表法譯 碼器原理圖。碼器原理圖。 k22007年12月27例例9-2 9-2 按照例按照例9-19-1生成矩陣生成矩陣G G，列出，列出S

22、 S與與E E的對(duì)照表。當(dāng)收到的對(duì)照表。當(dāng)收到碼組碼組R=1 1 1 0 1 1R=1 1 1 0 1 1時(shí)，解出對(duì)應(yīng)的信息碼組時(shí)，解出對(duì)應(yīng)的信息碼組D D。解：已知生成矩陣為：解：已知生成矩陣為： 又因?yàn)橛忠驗(yàn)?故故100010001011110101TmIPHTm，HPI2007年12月28 為為6 6X X3 3的矩陣，由式的矩陣，由式 可知，共有可知，共有 種形式，種形式，相應(yīng)的碼重最小矢量有相應(yīng)的碼重最小矢量有8 8種，見(jiàn)下表。由表可知，種，見(jiàn)下表。由表可知，(6,3)(6,3)碼具有碼具有糾糾1 1錯(cuò)能力。雖然錯(cuò)能力。雖然S S111111時(shí)對(duì)應(yīng)一種雙錯(cuò)圖案，但除此以外的時(shí)對(duì)應(yīng)一種

23、雙錯(cuò)圖案，但除此以外的雙錯(cuò)卻不能得到糾正。雙錯(cuò)卻不能得到糾正。 E S E SE S E S 0 0 0 0 0 0 000 0 0 0 0 0 0 0 0 0 000 0 0 0 1 1 0 0 100 0 0 100 1 1 0 0 0 0 0 101 0 0 0 0 0 0 0 0 0 101 0 0 0 0 1 1 0 010 0 010 0 0 1 1 0 0 0 0 011 0 0 0 0 0 0 0 0 0 011 0 0 0 0 0 1 1 001 001 0 0 0 0 1 1 0 0 0 110 0 0 0 110 1 1 0 0 0 0 0 0 1 1 0 111 0 1

24、11THTEHS 322007年12月29 將碼組矢量將碼組矢量R=1 1 1 0 1 1代入代入 ，可得，可得S(如下如下)。 查查E-S對(duì)照表，可找到差錯(cuò)矢量為：對(duì)照表，可找到差錯(cuò)矢量為： 由式由式 ，可得到正確碼組，即，可得到正確碼組，即 所以信息碼組為：所以信息碼組為：TRHS 110100010001011110101 110111T RHS000010E110101ERC101DERC2007年12月30 漢明碼：漢明碼：能糾正單個(gè)錯(cuò)碼的稱為漢明碼。能糾正單個(gè)錯(cuò)碼的稱為漢明碼。 為能指出所有單錯(cuò)位置和無(wú)錯(cuò)情況，線性碼組碼長(zhǎng)為能指出所有單錯(cuò)位置和無(wú)錯(cuò)情況，線性碼組碼長(zhǎng)n、信息位信息位

25、k和監(jiān)督位和監(jiān)督位m間應(yīng)滿足下述關(guān)系：間應(yīng)滿足下述關(guān)系： 上式取等號(hào)時(shí)為漢明碼，此時(shí)有：上式取等號(hào)時(shí)為漢明碼，此時(shí)有： 由于由于m = nk， 所以，所以，12 nm1212mmnknmm)()(1log1log22nknnkn2007年12月31 上式表明：若信息碼組長(zhǎng)為上式表明：若信息碼組長(zhǎng)為k，則能糾正單個(gè)錯(cuò)碼所需，則能糾正單個(gè)錯(cuò)碼所需的最小碼組長(zhǎng)度的最小碼組長(zhǎng)度n。此時(shí)有。此時(shí)有 。 由上式可求得有由上式可求得有(3 , 1)(3 , 1)碼，碼，(7 , 4)(7 , 4)碼，碼，(15 , 11)(15 , 11)碼，碼，(31 , 26)(31 , 26)碼等。碼等。 漢明碼的編

26、碼效率為：漢明碼的編碼效率為： 一般地，若碼組有糾一般地，若碼組有糾t t個(gè)差錯(cuò)的能力，則應(yīng)能指出無(wú)個(gè)差錯(cuò)的能力，則應(yīng)能指出無(wú)錯(cuò)、單錯(cuò)到錯(cuò)、單錯(cuò)到t t個(gè)差錯(cuò)所有可能情況，此時(shí)校驗(yàn)位數(shù)個(gè)差錯(cuò)所有可能情況，此時(shí)校驗(yàn)位數(shù)m m應(yīng)滿應(yīng)滿足：足： 上式稱為漢明界。它給出了糾上式稱為漢明界。它給出了糾t t個(gè)錯(cuò)的必要條件個(gè)錯(cuò)的必要條件。3mind1211212cmmmmmnkRtjjnmC022007年12月329.3 9.3 循環(huán)碼循環(huán)碼9.3.1 循環(huán)碼的特點(diǎn)及表達(dá)式循環(huán)碼的特點(diǎn)及表達(dá)式 循環(huán)碼是一種系統(tǒng)分組碼，前循環(huán)碼是一種系統(tǒng)分組碼，前k位是信息碼，后位是信息碼，后r位是監(jiān)位是監(jiān)督碼。不僅具有督

27、碼。不僅具有封閉性封閉性，還具有，還具有循環(huán)性循環(huán)性，即一許用碼組，即一許用碼組經(jīng)循環(huán)移位后得到另一個(gè)許用碼組。經(jīng)循環(huán)移位后得到另一個(gè)許用碼組。 設(shè)設(shè) 是一個(gè)循環(huán)碼組，則可將之表示為：是一個(gè)循環(huán)碼組，則可將之表示為： 上式稱為碼多項(xiàng)式。上式稱為碼多項(xiàng)式。nccc,21Cnnncxcxcxc 2211)(2007年12月33 碼組碼組C移位移位1次得到的仍是碼組，它可寫(xiě)成：次得到的仍是碼組，它可寫(xiě)成： 不難驗(yàn)證：不難驗(yàn)證： 類似地，碼組類似地，碼組C經(jīng)經(jīng)i次移位后，得到的新的碼組次移位后，得到的新的碼組 是是 除以除以 的余式。的余式。 也就是說(shuō)，在模也就是說(shuō)，在模 意義下，意義下，若若c(x)

28、是碼多是碼多項(xiàng)式，則項(xiàng)式，則 都是碼多項(xiàng)式。都是碼多項(xiàng)式。 循環(huán)碼的編碼過(guò)程也可用多項(xiàng)式來(lái)描述循環(huán)碼的編碼過(guò)程也可用多項(xiàng)式來(lái)描述。123121 cxcxcxcxcnnn)()()()()()(xcxcxcxcxcxcxnnnn111211 )()(xci)(xcxi)(1nx)(1nx)(xcxi2007年12月34 一個(gè)一個(gè)k位信息碼組位信息碼組 用信息多項(xiàng)式表述出來(lái)，用信息多項(xiàng)式表述出來(lái)，則有：則有： 編碼問(wèn)題就是求解碼組多項(xiàng)式編碼問(wèn)題就是求解碼組多項(xiàng)式c(x) 的問(wèn)題。的問(wèn)題。 設(shè)設(shè) ，這里這里g(x)是是 的的nk次因式，次因式，稱為生成多項(xiàng)式。稱為生成多項(xiàng)式。 所以有所以有： 由于由

29、于 而前已證明：而前已證明： 顯然，顯然， ，d1(x)對(duì)應(yīng)某個(gè)信息碼組對(duì)應(yīng)某個(gè)信息碼組kddd,21Dkkkdxdxdxd 2211)()()()(xgxdxc)(1nx)()()()(xgdxgxdxgxdxckkk 2211)()()(xgxdxxcx)()()()(xcxcxcxn111 )()()()(xgxdxc112007年12月35 上式表明：上式表明： 對(duì)應(yīng)某個(gè)信息碼組，就是說(shuō)對(duì)應(yīng)某個(gè)信息碼組，就是說(shuō)c(x) 一定是一定是循環(huán)碼組。或者說(shuō)，循環(huán)碼完全由其碼組長(zhǎng)度循環(huán)碼組。或者說(shuō)，循環(huán)碼完全由其碼組長(zhǎng)度n及生成及生成多項(xiàng)式多項(xiàng)式g(x)所決定。由于所決定。由于g g( (x x

30、) )是一個(gè)能除盡是一個(gè)能除盡 的的n nk k次多項(xiàng)式，所以對(duì)次多項(xiàng)式，所以對(duì) 進(jìn)行因式分解，便可得進(jìn)行因式分解，便可得到相應(yīng)的到相應(yīng)的g g( (x x) )。 通常，由信息碼組通常，由信息碼組D和生成多項(xiàng)式求出的碼組不是系統(tǒng)和生成多項(xiàng)式求出的碼組不是系統(tǒng)碼。根據(jù)系統(tǒng)碼的定義，碼組的前碼。根據(jù)系統(tǒng)碼的定義，碼組的前k位是信息碼，后位是信息碼，后m位是校驗(yàn)碼。位是校驗(yàn)碼。 用多項(xiàng)式表示為：用多項(xiàng)式表示為：)(xd1)(1nx)(1nx)()()(xRxdxxckn2007年12月36 又因?yàn)橛忠驗(yàn)?，所以，有：，所以，有： 或?qū)懗桑夯驅(qū)懗桑?因此，有：因此，有： 可見(jiàn)，可見(jiàn)， 。)()()(

31、xgxdxc1)()()()(xgxdxRxdxkn1)()()()(xRxgxdxdxkn1)()()()()(xgxRxdxgxdxkn1)()()(xgxdxxRknremremainder 余數(shù)，余式，余項(xiàng)余數(shù)，余式，余項(xiàng) 2007年12月37例例9-3 9-3 求求(7 , 4)(7 , 4)循環(huán)碼的生成多項(xiàng)式循環(huán)碼的生成多項(xiàng)式g g( (x x) )。當(dāng)信息碼組當(dāng)信息碼組D=1 0 1 0 D=1 0 1 0 時(shí)，求輸出碼組時(shí)，求輸出碼組C C。解：由已知條件可知解：由已知條件可知n n = 7= 7，k k = 4= 4，m m = 3= 3，g g( (x x) ) 應(yīng)為應(yīng)為

32、的的3 3次因式。而次因式。而 得到得到2 2個(gè)個(gè)g g( (x x) )分別為：分別為： 和和 由由 可計(jì)算輸出碼組。計(jì)算過(guò)程如下：可計(jì)算輸出碼組。計(jì)算過(guò)程如下： 多項(xiàng)式運(yùn)算時(shí)遵循模多項(xiàng)式運(yùn)算時(shí)遵循模2 2規(guī)則，即規(guī)則，即 。 )(17x)()(11112337xxxxxx131xxxg)(1232xxxg)(333632111332654222( )()( )( )( )()(1)10 01110( )( )( )()(1)1110 010d xxxc xd x g xxx xxxxxxcxd x gxxx xxxxxxCC0iixx)()()(xgxdxc2007年12月38例例9-4

33、9-4 用例用例9-39-3的生成多項(xiàng)式的生成多項(xiàng)式g g( (x x) )求系統(tǒng)循環(huán)碼的碼組，求系統(tǒng)循環(huán)碼的碼組，已知已知D=1 0 1 0D=1 0 1 0。解：當(dāng)解：當(dāng) 時(shí)，信息多項(xiàng)式和升位后的多項(xiàng)式時(shí)，信息多項(xiàng)式和升位后的多項(xiàng)式分別為：分別為：求余式求余式R R( (x x) )的豎式為：的豎式為：131xxxg)(4633473xxxxxxdxxxxd)()()(3136464333 1( )1 1 1( )xd xxxxxxxxxxxxR x 2007年12月39 余式和碼組多項(xiàng)式分別為：余式和碼組多項(xiàng)式分別為： 可得系統(tǒng)循環(huán)碼碼組可得系統(tǒng)循環(huán)碼碼組C C為：為： 當(dāng)當(dāng) 時(shí)，用同樣

34、方法可得：時(shí)，用同樣方法可得： 由以上結(jié)果可以看出，用不同的生成多項(xiàng)式，都可以由以上結(jié)果可以看出，用不同的生成多項(xiàng)式，都可以得到系統(tǒng)循環(huán)碼。得到系統(tǒng)循環(huán)碼。 11461xxxxcxxR)()(11 0 1 0 0 1 1C1232xxxg)(6422( )1( )11 0 1 0 0 0 1R xc xxxC2007年12月409.3.2 循環(huán)碼的編碼和譯碼循環(huán)碼的編碼和譯碼 循環(huán)碼的優(yōu)點(diǎn)是其編譯碼電路都可用移位寄存器和模循環(huán)碼的優(yōu)點(diǎn)是其編譯碼電路都可用移位寄存器和模2 2加構(gòu)成的線性時(shí)序網(wǎng)絡(luò)來(lái)實(shí)現(xiàn)。編碼的關(guān)鍵是求出校驗(yàn)加構(gòu)成的線性時(shí)序網(wǎng)絡(luò)來(lái)實(shí)現(xiàn)。編碼的關(guān)鍵是求出校驗(yàn)位多項(xiàng)式位多項(xiàng)式R R(

35、(x x) )，而，而R R( (x x) )可通過(guò)式可通過(guò)式 求解。求解。 多項(xiàng)式除法可用帶反饋的線性移位寄存器來(lái)實(shí)現(xiàn)。多項(xiàng)式除法可用帶反饋的線性移位寄存器來(lái)實(shí)現(xiàn)。g g( (x x) )與移位寄存器的反饋邏輯相對(duì)應(yīng)，與移位寄存器的反饋邏輯相對(duì)應(yīng)， 是初始預(yù)置狀態(tài)，隨著碼元的節(jié)拍就可以進(jìn)行求解余式是初始預(yù)置狀態(tài)，隨著碼元的節(jié)拍就可以進(jìn)行求解余式的運(yùn)算。的運(yùn)算。 )()()(xgxdxxRknrem)(xdxkn2007年12月41 (7,4)循環(huán)碼編碼電路如下圖所示。循環(huán)碼編碼電路如下圖所示。 由于發(fā)送碼組由于發(fā)送碼組c(x) 是是g g( (x x) ) 的倍式。如果經(jīng)信道傳輸后的倍式。如

36、果經(jīng)信道傳輸后發(fā)生錯(cuò)誤，收到碼組多項(xiàng)式發(fā)生錯(cuò)誤，收到碼組多項(xiàng)式r r( (x x) ) 不再是不再是g g( (x x) ) 的倍式，的倍式，可表示為可表示為 或?qū)懗桑夯驅(qū)懗桑?()()()()(xgxsxmxgxr1)(/ )()(xgxrxsrem2007年12月42 s s( (x x) ) 是是r r( (x x) ) 除以除以g g( (x x) ) 的余式，是不大于的余式，是不大于m m1 1次的碼次的碼組多項(xiàng)式，稱為伴隨多項(xiàng)式或校正子多項(xiàng)式。組多項(xiàng)式，稱為伴隨多項(xiàng)式或校正子多項(xiàng)式。 接收碼組接收碼組r r( (x x) )可表示為發(fā)送碼組與差錯(cuò)多項(xiàng)式之和，可表示為發(fā)送碼組與差錯(cuò)多

37、項(xiàng)式之和，即即 r r( (x x) = ) = c c( (x x) + ) + e e( (x x) ) 。 所以，有：所以，有： 由此，可以通過(guò)由此，可以通過(guò)s s( (x x) )確定確定e e( (x x) )。 對(duì)于一個(gè)對(duì)于一個(gè)s s( (x x) )，可以有多個(gè)，可以有多個(gè)e e( (x x) )，依照最大似然比準(zhǔn)，依照最大似然比準(zhǔn)則，取最小碼重的則，取最小碼重的e e( (x x) )，于是，可得所接收到的碼組為：，于是，可得所接收到的碼組為：c c( (x x) = ) = r r( (x x) +) + e e( (x x) ) )()()()(xgxexcxsrem)(/

38、 )(xgxerem2007年12月43 右圖是循環(huán)碼譯碼器的一種。校正子計(jì)算電路計(jì)算出右圖是循環(huán)碼譯碼器的一種。校正子計(jì)算電路計(jì)算出相應(yīng)的相應(yīng)的s(x)， 錯(cuò)誤圖樣識(shí)別器錯(cuò)誤圖樣識(shí)別器 可通過(guò)查表法找可通過(guò)查表法找 到到e e( (x x) )，模，模2 2和用和用 來(lái)計(jì)算正確的譯來(lái)計(jì)算正確的譯 碼輸出碼輸出c c( (x x) = ) = r r( (x x) +) + e e( (x x) ) 。例例9-59-52007年12月44例例9-5 9-5 已知糾單錯(cuò)已知糾單錯(cuò)(7, 4)(7, 4)系統(tǒng)循環(huán)碼的生成多項(xiàng)式為系統(tǒng)循環(huán)碼的生成多項(xiàng)式為 ，試構(gòu)成譯碼表。，試構(gòu)成譯碼表。若接收碼組若

39、接收碼組R= 1 0 0 0 1 0 1R= 1 0 0 0 1 0 1，求發(fā)送碼組。，求發(fā)送碼組。解：根據(jù)書(shū)中式解：根據(jù)書(shū)中式(9-38)(9-38)，對(duì)碼重為，對(duì)碼重為1 1的差錯(cuò)多項(xiàng)式的差錯(cuò)多項(xiàng)式e e( (x x) )，求出相應(yīng)的伴隨多項(xiàng)式求出相應(yīng)的伴隨多項(xiàng)式s s( (x x) )，將其對(duì)應(yīng)結(jié)果列成譯碼表，將其對(duì)應(yīng)結(jié)果列成譯碼表，如下表所示。如下表所示。 e e( (x x) ) ：s s( (x x) ) ：123xxxg)(6x5x4x3x2xxxx 21x12 xx12x2xx2007年12月45 當(dāng)接收碼組無(wú)錯(cuò)誤時(shí)，當(dāng)接收碼組無(wú)錯(cuò)誤時(shí)，e e( (x x) = 0) = 0，

40、則，則s s( (x x) = 0) = 0。本題。本題給出的接收碼組為：給出的接收碼組為： 由此可寫(xiě)出接收碼組多項(xiàng)式：由此可寫(xiě)出接收碼組多項(xiàng)式： 由由 可計(jì)算出伴隨多項(xiàng)式：可計(jì)算出伴隨多項(xiàng)式： 查表得到：查表得到： 由由r r( (x x) ) 和和e e( (x x) ) 可得到譯碼碼組多項(xiàng)式可得到譯碼碼組多項(xiàng)式 ：1000101R126xxxr)()(/ )()(xgxrxsrem111rem2326xxxxxxs)(5xxe)(1256xxxxexrxc)()()(2007年12月46 相應(yīng)的碼組為：相應(yīng)的碼組為： 由于是系統(tǒng)循環(huán)碼，所以信息碼組為：由于是系統(tǒng)循環(huán)碼，所以信息碼組為：

41、據(jù)此分析構(gòu)成的一種譯碼器如下圖所示。圖中伴隨式據(jù)此分析構(gòu)成的一種譯碼器如下圖所示。圖中伴隨式計(jì)算電路對(duì)接收到的碼多項(xiàng)式計(jì)算出相應(yīng)的計(jì)算電路對(duì)接收到的碼多項(xiàng)式計(jì)算出相應(yīng)的s(x)s(x)。錯(cuò)誤。錯(cuò)誤圖樣識(shí)別器是一個(gè)具有圖樣識(shí)別器是一個(gè)具有n nk k個(gè)輸入端的邏輯電路，原則個(gè)輸入端的邏輯電路，原則上可采用查表方法，根據(jù)上可采用查表方法，根據(jù) 伴隨式找到錯(cuò)誤圖樣。伴隨式找到錯(cuò)誤圖樣。 緩存器用于存儲(chǔ)緩存器用于存儲(chǔ)k k位信位信 息碼元。模息碼元。模2 2和電路用和電路用 于糾正錯(cuò)誤。于糾正錯(cuò)誤。1100101C1100D2007年12月47引引 言言 卷積碼是非分組碼。卷積碼是非分組碼。 它充分利

42、用了各組之間的相關(guān)性，信息碼的碼它充分利用了各組之間的相關(guān)性，信息碼的碼長(zhǎng)長(zhǎng) k和卷積碼的碼長(zhǎng)和卷積碼的碼長(zhǎng)n 都比較小。都比較小。 卷積碼的性能在許多實(shí)際應(yīng)用情況下優(yōu)于分組卷積碼的性能在許多實(shí)際應(yīng)用情況下優(yōu)于分組碼，而且設(shè)備也較簡(jiǎn)單。碼，而且設(shè)備也較簡(jiǎn)單。 通常它更適用于前向糾錯(cuò)，在高質(zhì)量的通信設(shè)通常它更適用于前向糾錯(cuò)，在高質(zhì)量的通信設(shè)備中已得到廣泛應(yīng)用。備中已得到廣泛應(yīng)用。 2007年12月481編碼方法編碼方法 由由N 段輸入移位寄存器，段輸入移位寄存器，n 個(gè)模個(gè)模2加法器和加法器和n 級(jí)輸級(jí)輸出移位寄存器三部分組成。出移位寄存器三部分組成。 N 段輸入移位寄存器每段均為段輸入移位寄存

43、器每段均為k 位，這樣共有位，這樣共有Nk 位輸入移位寄存器。位輸入移位寄存器。 編碼器每輸入編碼器每輸入k 位信息比特，輸出移位寄存器輸位信息比特，輸出移位寄存器輸出出n 位比特的編碼。位比特的編碼。 2007年12月49 由圖可知，由圖可知，n 位輸出比特不但與當(dāng)前的位輸出比特不但與當(dāng)前的k個(gè)輸入信息比特個(gè)輸入信息比特有關(guān)，而且與以前的有關(guān)，而且與以前的(N1)k 個(gè)輸入信息比特有關(guān)。個(gè)輸入信息比特有關(guān)。 通常把通常把N 稱為編碼約束長(zhǎng)度，把卷積碼記作（稱為編碼約束長(zhǎng)度，把卷積碼記作（n，k，N），），編碼效率。編碼效率。 在有的文獻(xiàn)中將在有的文獻(xiàn)中將N1或或nN 稱為約束長(zhǎng)度。稱為約束長(zhǎng)

44、度。 2007年12月50 輸出移位寄存器用轉(zhuǎn)換開(kāi)關(guān)代替。輸出移位寄存器用轉(zhuǎn)換開(kāi)關(guān)代替。 每個(gè)時(shí)隙中，只有每個(gè)時(shí)隙中，只有1bit輸入信息進(jìn)入移位寄存器，并且移位寄輸入信息進(jìn)入移位寄存器，并且移位寄存器暫存的內(nèi)容向右移存器暫存的內(nèi)容向右移1位，開(kāi)關(guān)旋轉(zhuǎn)一周輸出位，開(kāi)關(guān)旋轉(zhuǎn)一周輸出2比特。比特。 bi 是當(dāng)前輸入信息位，是當(dāng)前輸入信息位，bi-1 為為bi 前面第一個(gè)信息位，前面第一個(gè)信息位， bi-2 為為bi 前前面第二個(gè)信息位。面第二個(gè)信息位。每輸入一個(gè)信息比特，經(jīng)編碼器產(chǎn)生每輸入一個(gè)信息比特，經(jīng)編碼器產(chǎn)生2個(gè)輸出比特個(gè)輸出比特c1和和c2 。2007年12月51c1和c2與與bi、bi-

45、1、bi-2的關(guān)系為的關(guān)系為22211iiiiibbcbbbc設(shè)起始狀態(tài)使所有級(jí)清零，即設(shè)起始狀態(tài)使所有級(jí)清零，即bi bi-1 bi-2 =000，當(dāng)?shù)诋?dāng)?shù)?位數(shù)據(jù)為位數(shù)據(jù)為1時(shí)，即時(shí)，即bi=1，bi-2 bi-1=00，輸出碼組，輸出碼組c1 c2=11。當(dāng)?shù)诋?dāng)?shù)?位數(shù)據(jù)為位數(shù)據(jù)為1時(shí)，即時(shí)，即bi=1，bi-2 bi-1=01，輸出碼組，輸出碼組c1 c2=01。依此類推，可求出所有輸入數(shù)據(jù)輸入后的輸出碼組。依此類推，可求出所有輸入數(shù)據(jù)輸入后的輸出碼組。 2007年12月52若輸入數(shù)據(jù)為若輸入數(shù)據(jù)為11010，編碼器的狀態(tài)如下表所示，編碼器的狀態(tài)如下表所示 表表9-6 圖圖9-11編碼

46、器的狀態(tài)編碼器的狀態(tài)為保證全部數(shù)據(jù)通過(guò)移位寄存器，還必須在數(shù)據(jù)后加為保證全部數(shù)據(jù)通過(guò)移位寄存器，還必須在數(shù)據(jù)后加3個(gè)個(gè)0。 當(dāng)?shù)诋?dāng)?shù)?位數(shù)據(jù)輸入時(shí)，第位數(shù)據(jù)輸入時(shí)，第1位數(shù)據(jù)移出移位寄存器而消失。位數(shù)據(jù)移出移位寄存器而消失。 每一位數(shù)據(jù)影響每一位數(shù)據(jù)影響3個(gè)輸出碼組，即（個(gè)輸出碼組，即（2，1，3）卷積碼的約束度）卷積碼的約束度為為3。 bi11010000 bi-2bi-10001111001100000 c1c21101010010110000狀態(tài)狀態(tài)abdcbcaa2007年12月53 圖解法圖解法 用圖示的方法描述卷積碼的狀態(tài)和輸入輸出情用圖示的方法描述卷積碼的狀態(tài)和輸入輸出情況。圖解

47、法描述編碼過(guò)程比較直觀。況。圖解法描述編碼過(guò)程比較直觀。 樹(shù)狀圖樹(shù)狀圖 狀態(tài)圖狀態(tài)圖 網(wǎng)格圖網(wǎng)格圖 解析法解析法 用編碼的生成多項(xiàng)式或者生成矩陣描述卷積碼用編碼的生成多項(xiàng)式或者生成矩陣描述卷積碼的狀態(tài)和輸入輸出情況。的狀態(tài)和輸入輸出情況。 生成多項(xiàng)式生成多項(xiàng)式 生成矩陣生成矩陣2007年12月54 描述在任何數(shù)據(jù)序列輸入時(shí)，碼組所有可能的輸出。描述在任何數(shù)據(jù)序列輸入時(shí)，碼組所有可能的輸出。 對(duì)應(yīng)上面的（對(duì)應(yīng)上面的（2，1，3）卷積碼編碼器，樹(shù)狀圖如下）卷積碼編碼器，樹(shù)狀圖如下把樹(shù)狀圖的起始節(jié)點(diǎn)放把樹(shù)狀圖的起始節(jié)點(diǎn)放在最左邊。在最左邊。 以以bi=0，bi-2 bi-1=00作為起作為起點(diǎn)，用點(diǎn)

48、，用a、b、c和和d表示表示bi-2 bi-1的四種可能狀態(tài)的四種可能狀態(tài)00、01、10、11。當(dāng)?shù)诋?dāng)?shù)?位輸入位輸入bi=0時(shí)，輸出時(shí)，輸出碼組碼組c1 c2=00。若。若bi=1，則，則c1c2=00。因此從因此從a點(diǎn)出發(fā)有兩條支路點(diǎn)出發(fā)有兩條支路（樹(shù)叉）可供選擇。（樹(shù)叉）可供選擇。bi=0時(shí)取上支路，時(shí)取上支路，bi=1時(shí)取下時(shí)取下支路。支路。 2007年12月55 輸入第輸入第2位比特時(shí)，移位寄存器狀態(tài)右移一位，上支路移位寄位比特時(shí)，移位寄存器狀態(tài)右移一位，上支路移位寄存器狀態(tài)仍為存器狀態(tài)仍為00，下支路的狀態(tài)則為，下支路的狀態(tài)則為01，即狀態(tài)，即狀態(tài)b。 新的一位輸入比特到來(lái)時(shí)，隨

49、著移位寄存器狀態(tài)和輸入比特的新的一位輸入比特到來(lái)時(shí)，隨著移位寄存器狀態(tài)和輸入比特的不同，樹(shù)狀圖繼續(xù)分叉成不同，樹(shù)狀圖繼續(xù)分叉成4條支路，條支路，2條向上，條向上，2條向下。條向下。 如此，即可得到上圖所示的二叉樹(shù)圖形。如此，即可得到上圖所示的二叉樹(shù)圖形。 樹(shù)狀圖中，每條樹(shù)叉上所標(biāo)注的是輸出比特，每個(gè)節(jié)點(diǎn)上標(biāo)注樹(shù)狀圖中，每條樹(shù)叉上所標(biāo)注的是輸出比特，每個(gè)節(jié)點(diǎn)上標(biāo)注的為移位寄存器的狀態(tài)。的為移位寄存器的狀態(tài)。 由圖可以看出，從第三條支路開(kāi)始，樹(shù)狀圖呈現(xiàn)出重復(fù)性，即由圖可以看出，從第三條支路開(kāi)始，樹(shù)狀圖呈現(xiàn)出重復(fù)性，即圖中表明的上半部與下半部完全相同，這意味著從第圖中表明的上半部與下半部完全相同，這

50、意味著從第4位數(shù)據(jù)位數(shù)據(jù)開(kāi)始，輸出碼組已與第一位數(shù)據(jù)無(wú)關(guān)，這也解釋了前述編碼約開(kāi)始，輸出碼組已與第一位數(shù)據(jù)無(wú)關(guān)，這也解釋了前述編碼約束度為束度為3的含義。的含義。 當(dāng)輸入數(shù)據(jù)為當(dāng)輸入數(shù)據(jù)為11010時(shí)，沿樹(shù)狀圖可得到輸出序列為，其路徑時(shí)，沿樹(shù)狀圖可得到輸出序列為，其路徑如圖中虛線所示。如圖中虛線所示。 2007年12月56 生成多項(xiàng)式表示生成多項(xiàng)式表示 編碼器中輸入移位寄存器與模編碼器中輸入移位寄存器與模2加法器的連接關(guān)系以及輸加法器的連接關(guān)系以及輸入、輸出序列都可表示為延時(shí)算子入、輸出序列都可表示為延時(shí)算子D的多項(xiàng)式。的多項(xiàng)式。 例如輸入序列為例如輸入序列為11010的表達(dá)式為的表達(dá)式為31

51、)(DDDB式中式中D的冪次等于時(shí)間起點(diǎn)的單位延時(shí)數(shù)，一般選擇第一個(gè)比的冪次等于時(shí)間起點(diǎn)的單位延時(shí)數(shù)，一般選擇第一個(gè)比特作為時(shí)間起點(diǎn)。特作為時(shí)間起點(diǎn)。 通常把表示移位寄存器與模通常把表示移位寄存器與模2加法器之間的連接關(guān)系多項(xiàng)式稱加法器之間的連接關(guān)系多項(xiàng)式稱為生成多項(xiàng)式。為生成多項(xiàng)式。因?yàn)橛伤鼈兛梢杂枚囗?xiàng)式相乘計(jì)算出輸出序因?yàn)橛伤鼈兛梢杂枚囗?xiàng)式相乘計(jì)算出輸出序列。列。 2007年12月57 若某級(jí)寄存器與某個(gè)模若某級(jí)寄存器與某個(gè)模2加法器相連接，則生成多項(xiàng)式相應(yīng)系加法器相連接，則生成多項(xiàng)式相應(yīng)系數(shù)取數(shù)取1，否則取，否則取0。 上面提到的（上面提到的（2，1，3）卷積碼的編碼器結(jié)構(gòu)可以用以下兩個(gè)

52、）卷積碼的編碼器結(jié)構(gòu)可以用以下兩個(gè)生成多項(xiàng)式描述：生成多項(xiàng)式描述： 211)(DDDG221)(DDG仍以輸入數(shù)據(jù)仍以輸入數(shù)據(jù)11010為例，可得為例，可得5432111)1)(1 ()()()(DDDDDDDBDGDC5232221)1)(1 ()()()(DDDDDDDBDGDC2007年12月582個(gè)模個(gè)模2和的輸出序列分別為和的輸出序列分別為 1000111c1110012c輸出序列為輸出序列為11110101001021cc這個(gè)結(jié)果和樹(shù)狀圖法得到的結(jié)果是相同的。這個(gè)結(jié)果和樹(shù)狀圖法得到的結(jié)果是相同的。為了方便，可以用二進(jìn)制數(shù)或八進(jìn)制數(shù)來(lái)表示生成多項(xiàng)式的系為了方便，可以用二進(jìn)制數(shù)或八進(jìn)制

53、數(shù)來(lái)表示生成多項(xiàng)式的系數(shù)數(shù)82121)7()111(1)(gDDDG82222)5()101(1)(gDDG2007年12月59 代數(shù)譯碼代數(shù)譯碼 利用編碼本身的代數(shù)結(jié)構(gòu)進(jìn)行譯碼，而不考慮信道的統(tǒng)利用編碼本身的代數(shù)結(jié)構(gòu)進(jìn)行譯碼，而不考慮信道的統(tǒng)計(jì)特性。計(jì)特性。 硬件實(shí)現(xiàn)簡(jiǎn)單，但性能較差。硬件實(shí)現(xiàn)簡(jiǎn)單，但性能較差。 門(mén)限譯碼：從線性譯碼的校正子出發(fā)，找到一組特殊的能夠檢門(mén)限譯碼：從線性譯碼的校正子出發(fā)，找到一組特殊的能夠檢查信息位置是否發(fā)生錯(cuò)誤的方程組，實(shí)現(xiàn)糾錯(cuò)譯碼。查信息位置是否發(fā)生錯(cuò)誤的方程組，實(shí)現(xiàn)糾錯(cuò)譯碼。 概率譯碼概率譯碼 建立在最大似然準(zhǔn)則的基礎(chǔ)上，在計(jì)算時(shí)用到了信道的建立在最大似然準(zhǔn)

54、則的基礎(chǔ)上，在計(jì)算時(shí)用到了信道的統(tǒng)計(jì)特性。統(tǒng)計(jì)特性。 提高了譯碼性能，但同時(shí)增加了硬件的復(fù)雜性。提高了譯碼性能，但同時(shí)增加了硬件的復(fù)雜性。 維特比譯碼譯碼：把已經(jīng)接收到的序列與所有可能的發(fā)送序列維特比譯碼譯碼：把已經(jīng)接收到的序列與所有可能的發(fā)送序列相比較，選擇其中漢明距離最小的一個(gè)發(fā)送序列作為譯碼輸出。相比較，選擇其中漢明距離最小的一個(gè)發(fā)送序列作為譯碼輸出。 序列譯碼：在硬件和性能方面介于門(mén)限譯碼和維特比譯碼之間，序列譯碼：在硬件和性能方面介于門(mén)限譯碼和維特比譯碼之間，適用于約束長(zhǎng)度很大的卷積碼。適用于約束長(zhǎng)度很大的卷積碼。 2007年12月609.5 9.5 差錯(cuò)控制編碼對(duì)系統(tǒng)性能的改善差錯(cuò)

55、控制編碼對(duì)系統(tǒng)性能的改善 這里僅討論信號(hào)功率相同和信道條件相同條件下，糾這里僅討論信號(hào)功率相同和信道條件相同條件下，糾t個(gè)差錯(cuò)的情況。個(gè)差錯(cuò)的情況。 設(shè)在設(shè)在T時(shí)間內(nèi)傳送時(shí)間內(nèi)傳送k位信息碼元，對(duì)無(wú)編碼系統(tǒng)，編碼位信息碼元，對(duì)無(wú)編碼系統(tǒng)，編碼前信息傳送速率前信息傳送速率 與信道傳送的信息速率與信道傳送的信息速率 相同，即相同，即 但對(duì)編碼系統(tǒng)，則有但對(duì)編碼系統(tǒng)，則有 其信息速率比無(wú)編碼系統(tǒng)高其信息速率比無(wú)編碼系統(tǒng)高n/k倍。倍。 bRbcRbbc/(bit/s)RRk TbbcRknknTkTnR)/()/)(/(/2007年12月61 傳輸帶寬大傳輸帶寬大n/k倍，信噪比低倍，信噪比低n/k

56、倍，也就導(dǎo)致了誤比特倍，也就導(dǎo)致了誤比特率高于無(wú)編碼系統(tǒng)。但譯碼后的誤碼組率卻明顯降低了！率高于無(wú)編碼系統(tǒng)。但譯碼后的誤碼組率卻明顯降低了！ 對(duì)無(wú)編碼系統(tǒng)，設(shè)碼組有對(duì)無(wú)編碼系統(tǒng)，設(shè)碼組有k位碼元，則其誤碼組率為：位碼元，則其誤碼組率為： 通常，有通常，有 ，所以，所以， 。 對(duì)編碼系統(tǒng)，由于能糾對(duì)編碼系統(tǒng)，由于能糾t個(gè)錯(cuò)，設(shè)此時(shí)誤比特率為個(gè)錯(cuò)，設(shè)此時(shí)誤比特率為 ，在在n n位碼的碼組中有位碼的碼組中有t t個(gè)以上差錯(cuò)時(shí)，碼組才會(huì)出錯(cuò)。在個(gè)以上差錯(cuò)時(shí)，碼組才會(huì)出錯(cuò)。在n n位碼中錯(cuò)位碼中錯(cuò)i i位碼的概率為：位碼的概率為：kPP)(ew111ePewkPP ecPiniinPPCniP)(),(

57、ecec12007年12月62 由此得誤碼組率為：由此得誤碼組率為： 當(dāng)當(dāng) 時(shí)，時(shí)，出現(xiàn)出現(xiàn)t t+1+1個(gè)差錯(cuò)的概率遠(yuǎn)大于出現(xiàn)個(gè)差錯(cuò)的概率遠(yuǎn)大于出現(xiàn)t t+1+1個(gè)個(gè)以上差錯(cuò)的概率，于是有以上差錯(cuò)的概率，于是有： 設(shè)系統(tǒng)采用設(shè)系統(tǒng)采用2PSK傳輸，信息傳輸速率為傳輸，信息傳輸速率為 ，信道白，信道白噪聲功率譜密度為噪聲功率譜密度為 ，并設(shè)，并設(shè) ， 為信號(hào)平均功率。則對(duì)無(wú)編碼系統(tǒng)，有：為信號(hào)平均功率。則對(duì)無(wú)編碼系統(tǒng)，有： ， ， 。inintiinPPCP)(ecec1wc11ecP1ec1wcttnPCPbR20/nb0iRnS /iSbcbRR 2eQP 2wkQP 2007年12月63

58、 而對(duì)編碼系統(tǒng)，則而對(duì)編碼系統(tǒng)，則有有 ， ， 當(dāng)當(dāng)n=7，k=4，t=1時(shí)，時(shí)， 有有 有無(wú)糾錯(cuò)時(shí)誤碼組率比較：節(jié)省有無(wú)糾錯(cuò)時(shí)誤碼組率比較：節(jié)省1 dB.bbcRknR)/()/(nkQP2ec11wc2ttnnkQCP)/(24wQP 2wc14121.QP2007年12月649.6 9.6 數(shù)字通信系統(tǒng)應(yīng)用舉例數(shù)字通信系統(tǒng)應(yīng)用舉例9.6.1 用于市話網(wǎng)的用于市話網(wǎng)的PCM終端設(shè)備終端設(shè)備 下圖是局間交換機(jī)使用模擬交換機(jī)的情況。其弊端是繩下圖是局間交換機(jī)使用模擬交換機(jī)的情況。其弊端是繩路有限，交換機(jī)容量受限，市話網(wǎng)的電纜容量也有限。路有限，交換機(jī)容量受限，市話網(wǎng)的電纜容量也有限。2007年

59、12月65 下圖是局間直接數(shù)字中繼傳輸?shù)那闆r。下圖是局間直接數(shù)字中繼傳輸?shù)那闆r。 兩模擬交換機(jī)間通過(guò)各自的兩模擬交換機(jī)間通過(guò)各自的PCM終端機(jī)完成中繼，以終端機(jī)完成中繼，以二次群為例，使用二次群為例，使用2對(duì)線，可以替代模擬中繼的對(duì)線，可以替代模擬中繼的120對(duì)線。對(duì)線。2007年12月66 下圖是光纖數(shù)字傳輸系統(tǒng)連接方式圖。下圖是光纖數(shù)字傳輸系統(tǒng)連接方式圖。 1616端端PCMPCM基群?jiǎn)卧苫簡(jiǎn)卧葾 A局中繼輸出，經(jīng)局中繼輸出，經(jīng)2 2、3 3、4 4次群復(fù)接次群復(fù)接成成140 Mbit/s140 Mbit/s四次群信號(hào)。四次群信號(hào)經(jīng)光端機(jī)進(jìn)行光四次群信號(hào)。四次群信號(hào)經(jīng)光端機(jī)進(jìn)行光調(diào)制

60、，光信號(hào)經(jīng)光纜傳輸?shù)竭_(dá)光接收端機(jī)，經(jīng)光電檢測(cè)調(diào)制，光信號(hào)經(jīng)光纜傳輸?shù)竭_(dá)光接收端機(jī)，經(jīng)光電檢測(cè)器變換，再經(jīng)分接器分接為器變換，再經(jīng)分接器分接為1616端端PCMPCM基群信號(hào)，接入基群信號(hào)，接入B B局局中繼入線。中繼入線。 2007年12月67 移動(dòng)通信是指通信的雙方至少有一方是移動(dòng)的。移動(dòng)通信是指通信的雙方至少有一方是移動(dòng)的。 20世紀(jì)世紀(jì)80年代發(fā)展起來(lái)的模擬蜂窩移動(dòng)通信系統(tǒng)被稱為第年代發(fā)展起來(lái)的模擬蜂窩移動(dòng)通信系統(tǒng)被稱為第一代（一代（1G）移動(dòng)通信系統(tǒng)。）移動(dòng)通信系統(tǒng)。 主要技術(shù)：模擬調(diào)頻、碼分多址主要技術(shù)：模擬調(diào)頻、碼分多址 主要業(yè)務(wù)：電話主要業(yè)務(wù)：電話 主要缺點(diǎn)：容量小、干擾嚴(yán)重、不