1、2020/8/28,1,第8章 差錯(cuò)控制編碼,8.1 差錯(cuò)控制編碼的基本概念 8.2 差錯(cuò)控制方式 8.3 差錯(cuò)控制編碼分類 8.4 檢錯(cuò)和糾錯(cuò)原理 8.5 幾種常用的檢錯(cuò)碼 8.6 線性分組碼 8.7 循環(huán)碼,2020/8/28,2,8.1 差錯(cuò)控制編碼的基本概念 不管是模擬通信系統(tǒng)還是數(shù)字通信系統(tǒng)，都存在 因干擾和信道傳輸特性不好對(duì)信號(hào)造成的不良影 響。 它使模擬信號(hào)波形會(huì)發(fā)生畸變，一旦失真很難 糾正。因此，在模擬系統(tǒng)中只能采取抗干擾、防干 擾措施,盡量將干擾降到最低程度以保證通信質(zhì)量。,2020/8/28,3,在數(shù)字系統(tǒng)中，干擾也會(huì)使信號(hào)產(chǎn)生變 形，但一定程度的信號(hào)畸變不會(huì)影響接收，因

2、為我們只關(guān)心數(shù)字信號(hào)的電平狀態(tài)（是高電平 還是低電平），而不太在乎其波形的失真。也 就是說(shuō)，數(shù)字系統(tǒng)對(duì)干擾或信道特性不良的寬 容度比模擬系統(tǒng)大。,2020/8/28,4,數(shù)字通信系統(tǒng)除了可采取與模擬系統(tǒng)同樣的措 施抗干擾外，還可對(duì)所傳數(shù)字信息進(jìn)行特殊的處 理（即差錯(cuò)控制編碼），對(duì)誤碼進(jìn)行檢錯(cuò)和糾 錯(cuò)，進(jìn)一步降低誤碼率。 因此，數(shù)字通信系統(tǒng)可從硬件上采用抗干擾措 施，軟件上采用信道編碼對(duì)信息傳輸中出現(xiàn)的錯(cuò) 誤進(jìn)行控制和糾正。,2020/8/28,5,圖81 兩種通信系統(tǒng)干擾示意圖,2020/8/28,6,香農(nóng)提出了有擾信道中信息傳輸?shù)闹匾?論香農(nóng)第二定理：對(duì)于一個(gè)給定的有擾信 道，若該信道容量

3、為C，則只要信道中的R小 于C，就一定存在一種編碼方式，使編碼后 的誤碼率隨著碼長(zhǎng)n的增加按指數(shù)下降到任意 小的值?；蛘哒f(shuō)只要RC，就存在傳輸速率 為R的糾錯(cuò)碼。,2020/8/28,7,該定理從理論上指出了信道編碼的努力 方向。 差錯(cuò)控制是信道編碼中要考慮的因素，其 基本思想就是在信號(hào)序列中加入冗余碼元， 它與信號(hào)序列中的信息碼元有著某種制約關(guān) 系，這種關(guān)系可發(fā)現(xiàn)或糾正在信息序列中出 現(xiàn)的錯(cuò)誤也就是誤碼，從而降低了誤碼率。,2020/8/28,8,冗余碼元稱為監(jiān)督（或校驗(yàn)）碼元。差錯(cuò) 控制編碼就是將信息碼元和監(jiān)督碼元編排在 一起的過(guò)程。需要說(shuō)明的是，有些書常把差 錯(cuò)控制編碼稱為信道編碼，而第

4、6章中，差錯(cuò) 控制編碼僅是信道編碼中的一個(gè)組成部分 （其它內(nèi)容包括位定時(shí)、分組同步、減少高 頻分量、去除直流分量等等）。,2020/8/28,9,8.2 差錯(cuò)控制方式 差錯(cuò)控制方式可分為：前向糾錯(cuò)（FEC）、 檢錯(cuò)重發(fā)（ARQ）和混合糾錯(cuò)（HEC）三 種。圖82是這三種方式構(gòu)成的差錯(cuò)控制系 統(tǒng)原理框圖。,2020/8/28,10,圖82 三種差錯(cuò)控制方式示意圖,2020/8/28,11,前向糾錯(cuò)(FEC)：發(fā)端將信息碼經(jīng)信道編碼后 變成能夠糾正錯(cuò)誤的碼，收端通過(guò)譯碼能自動(dòng)發(fā)現(xiàn) 并糾正因傳輸帶來(lái)的數(shù)據(jù)錯(cuò)誤。 優(yōu)點(diǎn)：只要求單向信道，適合于只能提供單向信 道的場(chǎng)合，或廣播傳輸方式。接收信號(hào)的延時(shí)小、

5、 實(shí)時(shí)性好。 缺點(diǎn)：設(shè)備復(fù)雜、成本高，且糾錯(cuò)能力愈強(qiáng)，設(shè)備 就愈復(fù)雜。,2020/8/28,12,檢錯(cuò)重發(fā)(ARQ)：發(fā)端將信息碼編成能夠檢錯(cuò) 的碼，收端收到后進(jìn)行檢驗(yàn)，將檢驗(yàn)結(jié)果（有誤碼 或者無(wú)誤碼）通過(guò)反向信道反饋給發(fā)端作為應(yīng)答信 號(hào)。發(fā)端根據(jù)收到的應(yīng)答信號(hào)做出是繼續(xù)發(fā)送新的 數(shù)據(jù)還是把出錯(cuò)的數(shù)據(jù)重發(fā)的判斷。 檢錯(cuò)重發(fā)系統(tǒng)可分為三種，停發(fā)等候重發(fā)系 統(tǒng)、返回重發(fā)系統(tǒng)和選擇重發(fā)系統(tǒng)。,2020/8/28,13,收端收到該碼組并檢驗(yàn)后，將應(yīng)答信號(hào) ACK發(fā)回發(fā)端，發(fā)端確認(rèn)碼組1無(wú)錯(cuò)，就將 碼組2發(fā)送出來(lái)；收端判斷該碼組有錯(cuò)并以 NAK信號(hào)告知發(fā)端，發(fā)端將碼組1重新發(fā)送 一次。,2020/8/2

6、8,14,圖83 檢錯(cuò)重發(fā)的三種工作方式,2020/8/28,15,返回重發(fā)系統(tǒng)如圖83（b）所示，發(fā)端不停 頓地發(fā)送信息碼組，不再等候ACK信號(hào)，如果收 端發(fā)現(xiàn)錯(cuò)誤并發(fā)回NAK信號(hào)，則發(fā)端從下一個(gè)碼 組開始重發(fā)前一段N個(gè)碼組，圖中N=5。收端收到 碼組2有錯(cuò)。發(fā)端在碼組6后重發(fā)碼組2、3、4、5、 6，這種返回重發(fā)系統(tǒng)的傳輸效率比停發(fā)等候系統(tǒng) 有很大改進(jìn)，在很多數(shù)據(jù)傳輸系統(tǒng)中得到應(yīng)用。,2020/8/28,16,圖83（c）：系統(tǒng)也是連續(xù)不斷地發(fā)送碼 組，收端檢測(cè)到錯(cuò)誤后發(fā)回NAK信號(hào)，但是發(fā)端不 是重發(fā)前N個(gè)碼組，而是只重發(fā)有錯(cuò)誤的那一組。 如只重發(fā)收端檢出有錯(cuò)的碼組2。 收端對(duì)已認(rèn)可的碼

7、組，從緩沖存儲(chǔ)器讀出時(shí)重 新排序，恢復(fù)出正常的碼組序列。 系統(tǒng)傳輸效率最高，但價(jià)格也最貴。,2020/8/28,17,混合糾錯(cuò)方式是前向糾錯(cuò)方式和檢錯(cuò)重發(fā)方式 的結(jié)合。如圖82（c）所示。 其內(nèi)層采用FEC方式，糾正部分差錯(cuò)；外層采 用ARQ方式，重傳那些雖已檢出但未糾正的差 錯(cuò)?；旌霞m錯(cuò)方式在實(shí)時(shí)性和譯碼復(fù)雜性方面是前 向糾錯(cuò)和檢錯(cuò)重發(fā)方式的折衷，較適合于環(huán)路延遲 大的高速數(shù)據(jù)傳輸系統(tǒng)。,2020/8/28,18,8.3 差錯(cuò)控制編碼分類 介紹幾種主要分類。 (1)根據(jù)編碼功能可分為檢錯(cuò)碼、糾錯(cuò)碼和糾 刪碼三種類型，只能完成檢錯(cuò)功能的叫檢錯(cuò) 碼；具有糾錯(cuò)能力的叫糾錯(cuò)碼；而糾刪碼既 可檢錯(cuò)也可

8、糾錯(cuò)。,2020/8/28,19,(2) 按照信息碼元和附加的監(jiān)督碼元之間的 檢驗(yàn)關(guān)系可以分為線性碼和非線性碼。 線性碼：信息碼元與監(jiān)督碼元之間的關(guān)系為 線性關(guān)系，即監(jiān)督碼元是信息碼元的線性組 合，則稱為線性碼。 非線性碼：兩者不存在線性關(guān)系，稱為非線 性碼。,2020/8/28,20,(3) 按照信息碼元和監(jiān)督碼元之間的約束方式可分為分組碼和卷積碼。 分組碼：把信息序列分為k位一組，附加m位監(jiān)督碼 元，形成n=k+m位的碼組。監(jiān)督碼元僅與本碼組的 信息碼元有關(guān)，而與其它碼組無(wú)關(guān)。 卷積碼：碼組中的監(jiān)督碼元不但與本組信息碼元有 關(guān)，而且與前面碼組的信息碼元也有約束關(guān)系，卷 積碼又稱連環(huán)碼或鏈碼

9、。,2020/8/28,21,(4) 系統(tǒng)碼與非系統(tǒng)碼。在線性分組碼中所有碼組 的k位信息碼元在編碼前后保持原來(lái)形式的碼叫系 統(tǒng)碼，反之就是非系統(tǒng)碼。系統(tǒng)碼的編、譯碼都相 對(duì)比較簡(jiǎn)單，因此得到廣泛應(yīng)用。 (5) 糾正隨機(jī)錯(cuò)誤碼和糾正突發(fā)錯(cuò)誤碼。前者用于 糾正因信道中出現(xiàn)的隨機(jī)獨(dú)立干擾引起的誤碼，后 者主要對(duì)付信道中出現(xiàn)的突發(fā)錯(cuò)誤。,2020/8/28,22,8.4 檢錯(cuò)和糾錯(cuò)原理 數(shù)字通信中碼元的兩種錯(cuò)誤形式：隨機(jī)錯(cuò)誤和突發(fā) 錯(cuò)誤。 (1) 隨機(jī)錯(cuò)誤。由隨機(jī)噪聲引起的碼元錯(cuò)誤，其特 點(diǎn)是碼元中任意一位或幾位發(fā)生從0變1或從1變0的 錯(cuò)誤是相互獨(dú)立的，彼此之間沒(méi)有聯(lián)系，一般不會(huì) 引起成片的碼元錯(cuò)

10、誤。,2020/8/28,23,(2) 突發(fā)錯(cuò)誤。由突發(fā)噪聲引起的碼元錯(cuò)誤， 比如，閃電、電器開關(guān)的瞬態(tài)、磁帶缺陷等 都屬于突發(fā)噪聲。該錯(cuò)誤的特點(diǎn)是各錯(cuò)誤碼 元之間存在相關(guān)性，因此是成片出現(xiàn)，錯(cuò)誤 序列的長(zhǎng)度（包括首和尾在內(nèi)的錯(cuò)誤所波及 的段落長(zhǎng)度）稱為突發(fā)長(zhǎng)度。,2020/8/28,24,簡(jiǎn)單例子：介紹檢錯(cuò)和糾錯(cuò)的基本原理。 假設(shè)要發(fā)送一組具有四個(gè)狀態(tài)的數(shù)據(jù)信息 （比如，一個(gè)電壓信號(hào)的四個(gè)值，1V、2V、 3V、4V）。首先要用二進(jìn)制碼對(duì)數(shù)據(jù)信息進(jìn) 行編碼，顯然，用2位二進(jìn)制碼就可完成，編 碼表如表81所示。,2020/8/28,25,表81 2位編碼表,2020/8/28,26,假設(shè)不經(jīng)信

11、道編碼，在信道中直接傳輸 按表中編碼規(guī)則得到的0、1數(shù)字序列，則在 理想情況下，收端收到00就認(rèn)為是1V，收到 10就是3V。而在實(shí)際通信中由于干擾（噪 聲）的影響，會(huì)使信息碼元發(fā)生錯(cuò)誤從而出 現(xiàn)誤碼（比如碼組00變成10、01或11）。從 而引起信息傳輸錯(cuò)誤。,2020/8/28,27,因此，以這種編碼得到的數(shù)字信號(hào)在傳輸 中不具備檢錯(cuò)和糾錯(cuò)的能力。問(wèn)題的關(guān)鍵是2 位二進(jìn)制碼的全部組合都是信息碼組或稱許 用碼組，任何一位（或兩位）發(fā)生錯(cuò)誤都會(huì) 引起歧義。為了克服這一缺點(diǎn)，在每組碼后 面再加1位碼元，使2位碼組變成3位碼組。,2020/8/28,28,表82 3位編碼表,2020/8/28,2

12、9,在許用碼組000、011、101、110中，右 邊加上的1位碼元就是監(jiān)督碼元，它的加入 原則是使碼組中1的個(gè)數(shù)為偶數(shù)?，F(xiàn)在我們 再看一下出現(xiàn)誤碼的情況，假設(shè)許用碼組 000出現(xiàn)1位誤碼，即變成001、010或100三 個(gè)碼組中的一個(gè)，可見(jiàn)這三個(gè)碼組中1的個(gè) 數(shù)都是奇數(shù)，是禁用碼組。,2020/8/28,30,因此，當(dāng)收端收到這三個(gè)碼組中的任何一 個(gè)時(shí)，就知道是誤碼，用這種方法可以發(fā)現(xiàn)1 位或3位出現(xiàn)錯(cuò)誤的碼組，而無(wú)法檢出2位錯(cuò) 誤，通過(guò)增加1位監(jiān)督碼元，我們可以檢出1 位或3位錯(cuò)誤（3位出錯(cuò)的概率極?。?，但無(wú) 法糾正錯(cuò)誤。,2020/8/28,31,能否通過(guò)增加監(jiān)督碼元的位數(shù)來(lái)增加檢錯(cuò) 位

13、數(shù)或?qū)崿F(xiàn)糾錯(cuò)功能呢？比如我們?cè)诒?-2中 再加1位監(jiān)督碼元變成4位編碼（表83）。,表83 4位編碼表,2020/8/28,32,編碼原則仍然是偶校驗(yàn)。顯然，檢錯(cuò)1位 和3位沒(méi)問(wèn)題，但檢錯(cuò)2位還不行（比如0000 變成1100，而1100是許用碼組）。設(shè)誤碼為 1110，則可能的原碼為0110、1010、1100、 1111四個(gè)（還按1位誤碼考慮），而0110、 1010、1100都是許用碼組，所以無(wú)法糾錯(cuò)。,2020/8/28,33,可見(jiàn)，簡(jiǎn)單地增加1位監(jiān)督碼元并沒(méi)有提 高檢錯(cuò)與糾錯(cuò)能力，那么，檢錯(cuò)與糾錯(cuò)能力 到底與什么有關(guān)呢？在回答這個(gè)問(wèn)題之前， 我們先介紹兩個(gè)新概念碼元距離和碼元重 量。

14、,2020/8/28,34,碼距（也稱漢明距）：兩個(gè)碼組中對(duì)應(yīng)碼位上 碼元不同的個(gè)數(shù)。 碼距反映的是碼組之間的差異程度，比如，00 和01兩組碼的碼距為1；011和100的碼距為3。多個(gè) 碼組之間相互比較，可能會(huì)有不同的碼距，其中的 最小值被稱為最小碼距（用dmin表示）。比如， 000、001、110三個(gè)碼組相比較，碼距有1和2兩個(gè) 值，則最小碼距為1；,2020/8/28,35,分析表明，一種編碼方式的檢錯(cuò)、糾錯(cuò)能力與 許用碼組中的最小碼距有關(guān)。比如，表82中8個(gè) 碼組的最小碼距為1，若這8個(gè)碼組都作為許用碼 組，則沒(méi)有檢錯(cuò)能力，更不用說(shuō)糾錯(cuò)了； 若只選其中四個(gè)作為許用碼組，則最小碼距為

15、2，可檢1位或3位錯(cuò)誤；若只選000和111為許用碼 組時(shí)，其最小碼距為3，那么就可發(fā)現(xiàn)所有2位以下 的錯(cuò)誤，若用來(lái)糾錯(cuò)，則可糾正1位錯(cuò)誤。,2020/8/28,36,根據(jù)理論推導(dǎo)，可以得出以下結(jié)論： 在一個(gè)碼組內(nèi)要檢出e位誤碼，要求最小碼距為： dmine+1 (8.41) (2) 在一個(gè)碼組內(nèi)要糾正t位誤碼，要求最小碼距為： dmin2t+1 (8.42) (3) 在一個(gè)碼組內(nèi)要糾正t位誤碼，同時(shí)檢測(cè)出e 位誤碼（et）,要求最小碼距為： dmint+e+1 (8.43),2020/8/28,37,要提高編碼的糾、檢錯(cuò)能力，方法是： 增加監(jiān)督碼元位數(shù)（即冗余度）； 加大最小碼距，最小碼距增

16、大，碼元的冗余度就 增大。冗余度增大，最小碼距不一定增大。 編碼方式具有檢錯(cuò)和糾錯(cuò)能力的必要條件是信 息編碼必須有冗余，而充分條件是碼元之間要有一 定的碼距。另外，檢錯(cuò)要求的冗余度比糾錯(cuò)要低。,2020/8/28,38,把k位信息碼編成n位差錯(cuò)控制碼，信息碼的位數(shù) k與差錯(cuò)控制碼的位數(shù)n之比定義為編碼效率，用 Rc表示，即 因?yàn)閗n，所以，Rc1。顯然，編碼的冗余度越 大，編碼效率越低。即，通信系統(tǒng)可靠性的提高， 是以降低有效性（即編碼效率）來(lái)?yè)Q取的。,2020/8/28,39,差錯(cuò)控制編碼的關(guān)鍵技術(shù)就是尋找好的編 碼方法，在一定的差錯(cuò)控制能力下，使編碼 效率盡可能的高，譯碼方法盡可能的簡(jiǎn)單。

17、 碼元重量簡(jiǎn)稱碼重，定義為一個(gè)碼組中非 零碼元的個(gè)數(shù)。比如，碼組100110的碼重為 3，0110的碼重是2。它反映一個(gè)碼組中“0”和 “1”的“比重”。,2020/8/28,40,8.5 幾種常用的檢錯(cuò)碼 8.5.1 奇偶校驗(yàn)碼 是常見(jiàn)的簡(jiǎn)單檢錯(cuò)碼，其編碼規(guī)則是：把 信息碼先分組，形成多個(gè)許用碼組，在每一 個(gè)許用碼組最后（最低位）加上一位監(jiān)督碼 元。加上監(jiān)督碼元后使該碼組中1的數(shù)目為奇 數(shù)的編碼稱為奇校驗(yàn)碼，為偶數(shù)的編碼稱為 偶校驗(yàn)碼。,2020/8/28,41,奇偶校驗(yàn)碼的監(jiān)督關(guān)系可用下式進(jìn)行表述。假設(shè) 一個(gè)碼組的長(zhǎng)度為n，表示為（an-1an-2an-3a0），其 中前n-1位是信息碼，

18、最后一位a0為校驗(yàn)位，那么， 對(duì)于偶校驗(yàn)碼必須保證 :,監(jiān)督碼元a0的取值（0或1）可由下式?jīng)Q定：,2020/8/28,42,對(duì)于奇校驗(yàn)碼必須保證 :,監(jiān)督碼元a0的取值（0或1）可由下式?jīng)Q定：,2020/8/28,43,根據(jù)奇偶校驗(yàn)的規(guī)則可以看到，當(dāng)碼組中 的誤碼為偶數(shù)時(shí)，校驗(yàn)失效。不會(huì)改變碼組 的奇偶性，偶校驗(yàn)碼中1的個(gè)數(shù)仍為偶數(shù)， 奇校驗(yàn)碼中1的個(gè)數(shù)仍為奇數(shù)。因此，簡(jiǎn)單 的奇偶校驗(yàn)碼只能檢測(cè)出奇數(shù)個(gè)位發(fā)生錯(cuò)誤 的碼組。,2020/8/28,44,討論奇偶校檢碼的碼距問(wèn)題。設(shè)兩個(gè)碼組 同為奇（或偶）校驗(yàn)碼組，如果兩組碼只有1 位不同，則它們的奇偶性就不同，這與假設(shè) 相矛盾；如果兩組碼有2位

19、不同，則它們的奇 偶性不變。換句話說(shuō)，構(gòu)造不出碼距為1的奇 偶校檢碼，所以奇偶校驗(yàn)碼的最小碼距為2。,2020/8/28,45,8.5.2 水平奇偶校驗(yàn)碼 將經(jīng)過(guò)簡(jiǎn)單奇偶校驗(yàn)編碼的碼組按行排列 成方陣，每一行是一個(gè)碼組，若有n個(gè)碼組則 方陣就有n行。比如，有經(jīng)過(guò)奇偶校驗(yàn)編碼的 7個(gè)碼組 01011011001、 01010100100、 00110000110、 11000111001、 00111111110、 00010011111、 11101100001 排成方陣共有7行。,2020/8/28,46,若發(fā)端按列傳輸，收端按列接收后再按行還原成 發(fā)端的方陣，然后按行進(jìn)行奇偶校驗(yàn)，則糾錯(cuò)情

20、況 就會(huì)發(fā)生變化。 在一列中不管出現(xiàn)幾個(gè)誤碼（偶數(shù)或奇數(shù)），對(duì) 應(yīng)每一行都只是一位誤碼，故都可以通過(guò)水平奇偶 校驗(yàn)檢驗(yàn)出來(lái)；但對(duì)于每一行（一個(gè)碼組）而言仍 然只能檢出所有奇數(shù)個(gè)錯(cuò)誤。與簡(jiǎn)單奇偶校驗(yàn)編碼 相比，其最大優(yōu)點(diǎn)是可以檢出所有長(zhǎng)度小于行數(shù) （碼組數(shù)）的突發(fā)錯(cuò)誤。,2020/8/28,47,表84 水平偶校驗(yàn)碼,2020/8/28,48,8.5.3 二維奇偶校驗(yàn)碼 在水平奇偶校驗(yàn)編碼的基礎(chǔ)上，再加上垂 直奇偶校驗(yàn)編碼就構(gòu)成二維奇偶校驗(yàn)碼。如 表85所示。 在發(fā)送時(shí)仍按列發(fā)送，收端順序接收后仍 還原成表8-5的方陣形式。它多了個(gè)列校驗(yàn)， 因此，其檢錯(cuò)能力有所提高。,2020/8/28,49,

21、除了檢出行中的所有奇數(shù)個(gè)誤碼及長(zhǎng)度不 大于行數(shù)的突發(fā)性錯(cuò)誤外，還可檢出列中的 所有奇數(shù)個(gè)誤碼及長(zhǎng)度不大于列數(shù)的突發(fā)性 錯(cuò)誤。 同時(shí)還能檢出碼組中大多數(shù)出現(xiàn)偶數(shù)個(gè) 錯(cuò)誤的情況，但具體是哪一個(gè)碼組（那一 行）出現(xiàn)誤碼還無(wú)法判斷。,2020/8/28,50,表85 二維偶校驗(yàn)碼,2020/8/28,51,8.5.4 群計(jì)數(shù)碼 在奇偶校驗(yàn)碼中，添加監(jiān)督位將碼組的碼 重配成奇數(shù)或偶數(shù)。 群計(jì)數(shù)碼的編碼：先算出信息碼組的碼 重，然后用二進(jìn)制計(jì)數(shù)法將碼重作為監(jiān)督碼 元添加到信息碼組的后面。比如表84中的7 個(gè)信息碼組變成群計(jì)數(shù)碼后的形式見(jiàn)表 86。,2020/8/28,52,表86 群計(jì)數(shù)碼,2020/8/

22、28,53,這種碼屬于非線性分組系統(tǒng)碼，檢錯(cuò)能力 很強(qiáng)，除了能檢出碼組中奇數(shù)個(gè)錯(cuò)誤之外， 還能檢出偶數(shù)個(gè)1變0或0變1的錯(cuò)誤，但對(duì)1 變0和0變1成對(duì)出現(xiàn)的誤碼無(wú)能為力?？梢?驗(yàn)證，除了無(wú)法檢出1變0和0變1成對(duì)出現(xiàn)的 誤碼外，它還可檢出其它所有形式的錯(cuò)誤。,2020/8/28,54,8.5.5 恒比碼 從碼組中挑選那些“1”和“0”個(gè)數(shù)的比值相同的 碼組作為許用碼組。 表87是郵電部門在國(guó)內(nèi)通信中采用的五單位數(shù) 字保護(hù)電碼，它是五中取三的恒比碼。每個(gè)碼組的 長(zhǎng)度為5，其中“1”的個(gè)數(shù)為3，每個(gè)許用碼組中“1” 和“0”個(gè)數(shù)的比值恒為3/2。許用碼組的個(gè)數(shù)就是5中 取3的組合數(shù)，即 C35 =

23、 5! /(3!2!) = 10，正好表示10個(gè)阿拉伯?dāng)?shù)字。,2020/8/28,55,不難看出這種碼的最小碼距是2，它能夠 檢出碼組中所有奇數(shù)個(gè)錯(cuò)誤和部分偶數(shù)個(gè)錯(cuò) 誤。該碼也是非線性分組碼，但不是系統(tǒng) 碼，其主要優(yōu)點(diǎn)是簡(jiǎn)單，適用于對(duì)電傳機(jī)或 其它鍵盤設(shè)備產(chǎn)生的字母和符號(hào)進(jìn)行編碼。,2020/8/28,56,表87 五單位保護(hù)電碼表,2020/8/28,57,8.6 線性分組碼 在分組碼中，二元信息序列分成碼元數(shù)固 定的一組組信息，每組信息的碼元由k位二進(jìn) 制碼元組成，共有2k個(gè)不同的組合信息。 簡(jiǎn)單地說(shuō)，將信息碼進(jìn)行分組，然后為 每組信息碼附加若干位監(jiān)督碼元的編碼方法 得到的碼集合稱為分組碼

24、。,2020/8/28,58,信息碼組：k位二進(jìn)制碼元，用矩陣D表示， 分組碼： n位二進(jìn)制碼元， nk 分組碼元（n位）= 信息碼元（k位）+監(jiān)督碼 元（n-k位） 2k個(gè)不同碼組用矩陣C表示。 有時(shí)把監(jiān)督碼元稱為或校驗(yàn)碼元。,2020/8/28,59,k值越大，編碼設(shè)備越復(fù)雜，因?yàn)榫幋a設(shè) 備必須儲(chǔ)存2k個(gè)碼長(zhǎng)為n的碼組。因此，我 們需要構(gòu)造碼組之間有某種關(guān)系的分組碼， 以降低編碼的復(fù)雜性，線性分組碼就是滿足 這一條件的一種分組碼。,2020/8/28,60,線性分組碼：是一種長(zhǎng)度為n，其中2k個(gè)許 用碼組（代表信息的碼組）中的任意兩個(gè)碼 組的模2和仍為一個(gè)許用碼組的分組碼。稱為 線性（n，

25、k）碼。 重要性質(zhì)：封閉性，即任意兩個(gè)許用碼 組之模2和仍為一許用碼組；碼組的最小碼 距等于非零碼的最小碼重。,2020/8/28,61,圖84 線性分組碼格式,具有這種結(jié)構(gòu)的線性分組碼又叫做線性分組系統(tǒng)碼。,2020/8/28,62,相應(yīng)的信息碼組行向量和分組碼碼組行向 量為 C =c1, c2, , cn (8.61) D =d1, d2, , dk (8.62) 一個(gè)分組碼組的前k位是信息碼元，后n-k 位是監(jiān)督碼元（設(shè)監(jiān)督碼元位數(shù)為m，則有 m=n-k），每一個(gè)分組碼組可以由信息碼元 線性組合而成，即：,2020/8/28,63,2020/8/28,64,式中,hmidi表示模2乘，也

26、可表示為hmidi。其運(yùn) 算規(guī)則是：10=01=00=0；11=1。可見(jiàn)，在 線性分組碼中，信息碼元和監(jiān)督碼元可以用線性方 程聯(lián)系起來(lái)。 將上述C與D的n個(gè)關(guān)系式用矩陣表示為,2020/8/28,65,即 C=DG (8.63) 式中, G稱為生成矩陣，是一個(gè)kn階矩陣，具體形式為,2020/8/28,66,該矩陣又可分解為兩個(gè)子矩陣:,2020/8/28,67,其中Ik是kk階單位陣，P為km階矩 陣，即：,2020/8/28,68,這樣，分組碼C又可表示為 C = DIk P （8.64） 需要說(shuō)明的是，上述各式中的C和D可以是 由一個(gè)碼組構(gòu)成的一個(gè)行向量，也可以是由 2k個(gè)行向量構(gòu)成的2

27、kn階分組碼矩陣或2kk 階信息碼矩陣。,2020/8/28,69,式（8.63）說(shuō)明：（n，k）線性碼完全由生 成矩陣G的k行元素決定，即任意一個(gè)分組碼碼組 都是G的線性組合。（n，k）線性碼中的任何k 個(gè)線性無(wú)關(guān)的碼組都可用來(lái)構(gòu)成生成矩陣，所以， 生成矩陣G的各行都線性無(wú)關(guān)。G的各行本身就是 一個(gè)碼組。如果已有k個(gè)線性無(wú)關(guān)的碼組，則可 用其直接構(gòu)成G矩陣，并由此生成其余碼組。,2020/8/28,70,綜上所述，由于可用一個(gè)kn階矩陣G生 成2k個(gè)不同的碼組，因此，編碼器只需儲(chǔ)存 G矩陣的k行元素（而不是一般分組碼的2k碼 組），就可根據(jù)信息向量構(gòu)造出相應(yīng)的一個(gè) 分組碼碼組（或根據(jù)信息碼矩

28、陣構(gòu)造出相應(yīng) 的一個(gè)分組碼矩陣），從而降低了編碼的復(fù) 雜性，并提高了編碼效率。,2020/8/28,71,【例題81】給定一個(gè)（7，4）線性分組碼的生成矩陣,若信息碼為d=1101，求該信息碼的線性分組編碼C。,2020/8/28,72,解: 根據(jù)式（8.63）可得,2020/8/28,73,即對(duì)信息碼1101的線性分組編碼為 1101000。注意在矩陣乘法中，是模2 乘和模2加。上式也可寫成,2020/8/28,74,以上討論可知，編碼前的信息碼組共有2k 種組合，編碼后的碼組在k位信息碼元之外還 附加了m位校驗(yàn)碼元，共有2n種組合， 2n2k，這就是說(shuō)C與D的關(guān)系不惟一。 因此，選擇適當(dāng)?shù)?/p>

29、矩陣P，就可得到既具 有較強(qiáng)檢錯(cuò)或糾錯(cuò)能力，又較簡(jiǎn)單且編碼效 率較高的線性分組碼。目前已經(jīng)找到不少性 能較好的矩陣P。,2020/8/28,75,【例題82】 已知線性（6，3）碼的生成 矩陣為,求線性分組碼、各碼組的碼重、最小碼距和該碼的差錯(cuò)控制能力。 解：因?yàn)閗=3，故信息碼組矩陣（38）為,2020/8/28,76,2020/8/28,77,則由式（8.63）可得出分組碼碼組 矩陣（68階）為,2020/8/28,78,表88 例82編碼表,2020/8/28,79,從表中可見(jiàn)非零碼組的最小碼重為3，則 分組碼的最小碼距dmin=3，根據(jù)式（8.41）、 （8.42）和（8.43）可知該

30、分組碼能夠檢2 位錯(cuò)，糾1位錯(cuò)，或同時(shí)糾1位錯(cuò)檢1位錯(cuò)。 需要說(shuō)明的是，任何線性分組碼都包含全 零碼組。因任一碼組與其本身模2加都會(huì)得到 全零碼組。,2020/8/28,80,下面我們簡(jiǎn)要介紹譯碼原理。從式（8.47）可得,（8.66）,（8.65）,式中，Cm是km階監(jiān)督碼元矩陣。將式(8.66)改寫為:,(8.67),(8.68),2020/8/28,81,該式說(shuō)明線性分組碼中任一碼組與校驗(yàn)矩 陣H的轉(zhuǎn)置相乘，其結(jié)果為m位全零向量，因 此，用校驗(yàn)矩陣檢查二元序列是不是給定分 組碼中的碼組非常方便，“校驗(yàn)”由此而來(lái)。 可以推導(dǎo)出校驗(yàn)矩陣H與生成矩陣G滿足 GHT = HGT = 0 (8.6

31、9),2020/8/28,82,設(shè)行向量R=r1，r2，rn是收信端收 到的碼組。由于信道干擾產(chǎn)生誤碼，接收向 量R和發(fā)送向量C就有差別，用向量E=e1， e2，en表示這種差別。由此定義三者之 間的關(guān)系為,（8.610）,2020/8/28,83,若R中的某一位ri與C中的相同位ci一樣 時(shí)，E中的ei=0；若不同（即出現(xiàn)誤碼），則 ei=1?？梢?jiàn)向量E能夠反映誤碼狀況，故稱之 為錯(cuò)誤向量或錯(cuò)誤圖樣?？梢?jiàn)，E的碼重就 是誤碼的個(gè)數(shù)，因此E的碼重越小越好。,2020/8/28,84,式（8.610）也可寫為 R = E C （8.611） 定義矩陣S為伴隨式 S = RHT （8.612） S

32、是長(zhǎng)度為m=n-k的二元序列，有2m種組合。由式 （8.68）、（8.611）和（8.612）得 S =（E C）HT = E HT C HT = E HT （8.6-13）,2020/8/28,85,式（8.613）表明伴隨式S只與錯(cuò)誤圖樣E 有關(guān)，與發(fā)送碼組無(wú)關(guān)。S稱為R的伴隨式或 稱校正子。 當(dāng)S為零矢量時(shí)，說(shuō)明R沒(méi)有錯(cuò)，R是碼組 C；否則，說(shuō)明R有錯(cuò)，R不是碼組C。 當(dāng)通信雙方確定了信道編碼后，生成矩陣G 和監(jiān)督矩陣H也就隨之而定。收端可以知道 G、H和R。,2020/8/28,86,譯碼方法： 收端先求出伴隨式 S 解出錯(cuò)誤圖樣 E 解出發(fā)送碼組 C,2020/8/28,87,需要說(shuō)

33、明的是，上述步驟只是一個(gè)概念上 的解釋，具體方法還比較麻煩。因?yàn)閷?duì)于一個(gè) 伴隨式S，有2k個(gè)錯(cuò)誤圖樣與之對(duì)應(yīng)，換句話 說(shuō)，就是式(8.613)的解不唯一，真正的錯(cuò)誤 圖樣只是2k個(gè)錯(cuò)誤圖樣中的一個(gè)。,2020/8/28,88,【例題83】 已知一線性(6，3)碼的生成矩陣G、S和E的對(duì)照表分別為：,2020/8/28,89,求當(dāng)接收端收到碼組R=111011時(shí)，所對(duì)應(yīng)的信息碼組D。,2020/8/28,90,解： 根據(jù)前面HT的定義式可得,將接收碼組R=111011代入(8.612)式，可得：,2020/8/28,91,2020/8/28,92,從SE關(guān)系表中可知，S=011所對(duì)應(yīng)的錯(cuò)誤 圖樣為E =010000。將R =111011 和E=010000代入式 (813)或式(814)可得 C = R E =101011 從C中分出信息碼組為 D=101 信息碼組為D