差錯(cuò)控制編碼

1、第八章 差錯(cuò)控制編碼2022年5月7日28.1 差錯(cuò)控制編碼的基本概念差錯(cuò)控制編碼的基本概念數(shù)字通信中，根據(jù)不同的目的，編碼可分為數(shù)字通信中，根據(jù)不同的目的，編碼可分為信源編碼信源編碼和和信道編碼信道編碼。信源編碼是為了提高數(shù)字通信的有效性，以及為了使模信源編碼是為了提高數(shù)字通信的有效性，以及為了使模擬信號(hào)數(shù)字化而采取的編碼。擬信號(hào)數(shù)字化而采取的編碼。信道編碼是為了降低誤碼率，提高數(shù)字通信的可靠性而信道編碼是為了降低誤碼率，提高數(shù)字通信的可靠性而采取的編碼。采取的編碼。數(shù)字信號(hào)在傳輸?shù)倪^(guò)程中，加性噪聲、碼間串?dāng)_等都會(huì)數(shù)字信號(hào)在傳輸?shù)倪^(guò)程中，加性噪聲、碼間串?dāng)_等都會(huì)產(chǎn)生誤碼。為了提高系統(tǒng)的抗干擾

2、性能，可以加大發(fā)射產(chǎn)生誤碼。為了提高系統(tǒng)的抗干擾性能，可以加大發(fā)射功率，降低接收設(shè)備本身的噪聲，以及合理選擇調(diào)制、功率，降低接收設(shè)備本身的噪聲，以及合理選擇調(diào)制、解調(diào)方法等。此外，還可以采用信道編碼技術(shù)。解調(diào)方法等。此外，還可以采用信道編碼技術(shù)。2022年5月7日3差錯(cuò)控制編碼的基本思想差錯(cuò)控制編碼的基本思想：在發(fā)送端根據(jù)要傳輸?shù)臄?shù)字序列（信息碼元）在發(fā)送端根據(jù)要傳輸?shù)臄?shù)字序列（信息碼元）按一定的規(guī)律加入多余碼元，使原來(lái)不相關(guān)的按一定的規(guī)律加入多余碼元，使原來(lái)不相關(guān)的數(shù)字序列變?yōu)橄嚓P(guān)，然后把這些多余碼元和有數(shù)字序列變?yōu)橄嚓P(guān)，然后把這些多余碼元和有關(guān)的信息碼元一起傳送，接收端根據(jù)信息碼元關(guān)的信息

3、碼元一起傳送，接收端根據(jù)信息碼元與多余碼元之間的相關(guān)規(guī)則進(jìn)行檢驗(yàn)，從而發(fā)與多余碼元之間的相關(guān)規(guī)則進(jìn)行檢驗(yàn)，從而發(fā)現(xiàn)錯(cuò)誤。這時(shí)，或者通過(guò)反饋信道要求對(duì)方重現(xiàn)錯(cuò)誤。這時(shí)，或者通過(guò)反饋信道要求對(duì)方重發(fā)有錯(cuò)的信息，以進(jìn)行糾錯(cuò)；或者由接收端的發(fā)有錯(cuò)的信息，以進(jìn)行糾錯(cuò)；或者由接收端的譯碼器自動(dòng)把錯(cuò)誤糾正。譯碼器自動(dòng)把錯(cuò)誤糾正。這些多余碼元稱(chēng)為校驗(yàn)元或監(jiān)督元。它的加入這些多余碼元稱(chēng)為校驗(yàn)元或監(jiān)督元。它的加入不改變信息本身，也就是說(shuō)，它不傳送新的信不改變信息本身，也就是說(shuō)，它不傳送新的信息，它的作用只是使信道譯碼器能夠檢測(cè)和糾息，它的作用只是使信道譯碼器能夠檢測(cè)和糾正差錯(cuò)，從而控制系統(tǒng)差錯(cuò)概率，提高可靠性正差

4、錯(cuò)，從而控制系統(tǒng)差錯(cuò)概率，提高可靠性但這是以系統(tǒng)的有效性為代價(jià)的。但這是以系統(tǒng)的有效性為代價(jià)的。2022年5月7日48.1.1 差錯(cuò)控制方式差錯(cuò)控制方式2022年5月7日5前向糾錯(cuò)方式前向糾錯(cuò)方式前向糾錯(cuò)方式記作前向糾錯(cuò)方式記作FEC（Forword Error Correction）發(fā)端編碼器將數(shù)字信息按一定規(guī)則附加多余碼元，組成有糾錯(cuò)能力的碼發(fā)端編碼器將數(shù)字信息按一定規(guī)則附加多余碼元，組成有糾錯(cuò)能力的碼，發(fā)端發(fā)送能夠糾正錯(cuò)誤的碼；發(fā)端發(fā)送能夠糾正錯(cuò)誤的碼；收端譯碼器按預(yù)先規(guī)定的規(guī)則譯碼；若發(fā)收端譯碼器按預(yù)先規(guī)定的規(guī)則譯碼；若發(fā)現(xiàn)錯(cuò)誤，確定其出錯(cuò)位置并進(jìn)行糾正?，F(xiàn)錯(cuò)誤，確定其出錯(cuò)位置并進(jìn)行糾

5、正。優(yōu)點(diǎn)：優(yōu)點(diǎn)： 單向傳輸，單向傳輸，只有正向信道；適合于只能提供單向信道的場(chǎng)合；一點(diǎn)只有正向信道；適合于只能提供單向信道的場(chǎng)合；一點(diǎn)發(fā)送多點(diǎn)接收的同播方式；譯碼延遲固定，適用于實(shí)時(shí)傳輸系統(tǒng)。發(fā)送多點(diǎn)接收的同播方式；譯碼延遲固定，適用于實(shí)時(shí)傳輸系統(tǒng)。缺點(diǎn)：缺點(diǎn)： 編譯碼設(shè)備復(fù)雜，為了糾正較多的錯(cuò)誤，需要附加的多余碼元較多，編譯碼設(shè)備復(fù)雜，為了糾正較多的錯(cuò)誤，需要附加的多余碼元較多，因而傳輸效率較低。因而傳輸效率較低。2022年5月7日6檢錯(cuò)重發(fā)方式檢錯(cuò)重發(fā)方式又稱(chēng)自動(dòng)請(qǐng)求重傳方式，記作又稱(chēng)自動(dòng)請(qǐng)求重傳方式，記作ARQ（Automatic Repeat Request）。）。發(fā)端編碼器將數(shù)字信息

6、按一定規(guī)則附加多余碼元，使之具有一定的檢錯(cuò)發(fā)端編碼器將數(shù)字信息按一定規(guī)則附加多余碼元，使之具有一定的檢錯(cuò)能力，收端譯碼器按一定規(guī)則對(duì)數(shù)據(jù)碼元組進(jìn)行錯(cuò)誤判決，并把判決結(jié)能力，收端譯碼器按一定規(guī)則對(duì)數(shù)據(jù)碼元組進(jìn)行錯(cuò)誤判決，并把判決結(jié)果形成應(yīng)答信號(hào)，通過(guò)反饋信道回送到發(fā)端，發(fā)端根據(jù)收到的應(yīng)答信號(hào)，果形成應(yīng)答信號(hào)，通過(guò)反饋信道回送到發(fā)端，發(fā)端根據(jù)收到的應(yīng)答信號(hào)，把收端認(rèn)為有錯(cuò)的那組數(shù)據(jù)碼元再次重傳，直到碼元組無(wú)錯(cuò)為止。把收端認(rèn)為有錯(cuò)的那組數(shù)據(jù)碼元再次重傳，直到碼元組無(wú)錯(cuò)為止。優(yōu)點(diǎn)：優(yōu)點(diǎn)： 只需要少量的多余碼元就能獲得極低的輸出誤碼率，并且其成本和只需要少量的多余碼元就能獲得極低的輸出誤碼率，并且其成本

7、和復(fù)雜性均比前向糾錯(cuò)低缺點(diǎn)。復(fù)雜性均比前向糾錯(cuò)低缺點(diǎn)。缺點(diǎn)：缺點(diǎn)： 必須提供反向信道；不能進(jìn)行同播（一點(diǎn)發(fā)多點(diǎn)收），收發(fā)端應(yīng)有必須提供反向信道；不能進(jìn)行同播（一點(diǎn)發(fā)多點(diǎn)收），收發(fā)端應(yīng)有緩沖存儲(chǔ)器和控制器；此外當(dāng)信道干擾較大時(shí)，整個(gè)系統(tǒng)可能處在重傳緩沖存儲(chǔ)器和控制器；此外當(dāng)信道干擾較大時(shí)，整個(gè)系統(tǒng)可能處在重傳循環(huán)中，因而通信效率降低，信息傳輸連貫性差，不適于實(shí)時(shí)傳輸系統(tǒng)，循環(huán)中，因而通信效率降低，信息傳輸連貫性差，不適于實(shí)時(shí)傳輸系統(tǒng)，主要在計(jì)算機(jī)通信中應(yīng)用。主要在計(jì)算機(jī)通信中應(yīng)用。常用的檢錯(cuò)重發(fā)系統(tǒng)有三種，即停發(fā)等候重發(fā)、返回重發(fā)和選擇重發(fā)。常用的檢錯(cuò)重發(fā)系統(tǒng)有三種，即停發(fā)等候重發(fā)、返回重發(fā)和選

8、擇重發(fā)。2022年5月7日8混合糾錯(cuò)方式混合糾錯(cuò)方式混合糾錯(cuò)方式記作混合糾錯(cuò)方式記作HEC（Hybrid Error Correction）發(fā)端發(fā)送具有自動(dòng)糾錯(cuò)同時(shí)又具有檢錯(cuò)能力的碼。收發(fā)端發(fā)送具有自動(dòng)糾錯(cuò)同時(shí)又具有檢錯(cuò)能力的碼。收端收到碼后，檢查差錯(cuò)情況，如果錯(cuò)誤在碼的糾錯(cuò)能端收到碼后，檢查差錯(cuò)情況，如果錯(cuò)誤在碼的糾錯(cuò)能力范圍以?xún)?nèi)，則自動(dòng)糾錯(cuò)，如果超過(guò)了碼的糾錯(cuò)能力力范圍以?xún)?nèi)，則自動(dòng)糾錯(cuò)，如果超過(guò)了碼的糾錯(cuò)能力但能檢測(cè)出來(lái)，則經(jīng)過(guò)反饋信道請(qǐng)求發(fā)端重發(fā)。但能檢測(cè)出來(lái)，則經(jīng)過(guò)反饋信道請(qǐng)求發(fā)端重發(fā)。這種方式具有自動(dòng)糾錯(cuò)和檢錯(cuò)重發(fā)的優(yōu)點(diǎn)，可達(dá)到較這種方式具有自動(dòng)糾錯(cuò)和檢錯(cuò)重發(fā)的優(yōu)點(diǎn)，可達(dá)到較低的誤碼

9、率，因此，近年來(lái)得到廣泛應(yīng)用低的誤碼率，因此，近年來(lái)得到廣泛應(yīng)用。在實(shí)際通信系統(tǒng)中，選擇那種差錯(cuò)控制方式，要視具在實(shí)際通信系統(tǒng)中，選擇那種差錯(cuò)控制方式，要視具體情況而定，可以根據(jù)信源的性質(zhì)，信息傳輸?shù)奶攸c(diǎn)體情況而定，可以根據(jù)信源的性質(zhì)，信息傳輸?shù)奶攸c(diǎn)信道干擾的種類(lèi)和對(duì)誤碼率的要求而適當(dāng)選擇差錯(cuò)控信道干擾的種類(lèi)和對(duì)誤碼率的要求而適當(dāng)選擇差錯(cuò)控制方式。制方式。2022年5月7日98.1.2 差錯(cuò)控制編碼的分類(lèi)差錯(cuò)控制編碼的分類(lèi)根據(jù)信息元和監(jiān)督元的函數(shù)關(guān)系，可分為根據(jù)信息元和監(jiān)督元的函數(shù)關(guān)系，可分為線(xiàn)性碼線(xiàn)性碼和和非非線(xiàn)性碼線(xiàn)性碼。如果函數(shù)關(guān)系是線(xiàn)性的，即滿(mǎn)足一組線(xiàn)性方。如果函數(shù)關(guān)系是線(xiàn)性的，即滿(mǎn)足

10、一組線(xiàn)性方程式，則稱(chēng)為線(xiàn)性碼，否則為非線(xiàn)性碼。程式，則稱(chēng)為線(xiàn)性碼，否則為非線(xiàn)性碼。 根據(jù)上述關(guān)系涉及的范圍，可分為根據(jù)上述關(guān)系涉及的范圍，可分為分組碼分組碼和和卷積碼卷積碼。分組碼的各碼元僅與本組的信息元有關(guān)；卷積碼中的分組碼的各碼元僅與本組的信息元有關(guān)；卷積碼中的碼元不僅與本組的信息元有關(guān)，而且還與前面若干組碼元不僅與本組的信息元有關(guān)，而且還與前面若干組的信息元有關(guān)。的信息元有關(guān)。根據(jù)碼的用途，可分為根據(jù)碼的用途，可分為檢錯(cuò)碼檢錯(cuò)碼和和糾錯(cuò)碼糾錯(cuò)碼。檢錯(cuò)碼以檢。檢錯(cuò)碼以檢錯(cuò)為目的，不一定能糾錯(cuò)；而糾錯(cuò)碼以糾錯(cuò)為目的，錯(cuò)為目的，不一定能糾錯(cuò)；而糾錯(cuò)碼以糾錯(cuò)為目的，一定能檢錯(cuò)。一定能檢錯(cuò)。 20

11、22年5月7日108.1.3 幾種簡(jiǎn)單的檢錯(cuò)碼幾種簡(jiǎn)單的檢錯(cuò)碼(1)奇偶監(jiān)督碼奇偶監(jiān)督碼設(shè)碼字A=an-1,an-2,a1,a0，對(duì)偶監(jiān)督碼有： an-1 an-2 a1 a0 = 0 奇監(jiān)督碼情況相似， 只是碼組中“1”的數(shù)目為奇數(shù)， 即 滿(mǎn)足條件： an-1 an-2 a1 a0 = 1 而檢錯(cuò)能力與偶監(jiān)督碼相同。 2022年5月7日11奇偶監(jiān)督碼奇偶監(jiān)督碼編碼方法：把信息碼元分組，在每組信息碼元編碼方法：把信息碼元分組，在每組信息碼元 的后面附加一位監(jiān)督碼元，使得的后面附加一位監(jiān)督碼元，使得 碼組中碼組中1的數(shù)目為奇數(shù)或偶數(shù)即可的數(shù)目為奇數(shù)或偶數(shù)即可 編碼規(guī)則：碼組長(zhǎng)度編碼規(guī)則：碼組長(zhǎng)度

12、n；信息位；信息位n-1 特點(diǎn)：是一種能發(fā)現(xiàn)奇數(shù)個(gè)差錯(cuò)的分組碼；特點(diǎn)：是一種能發(fā)現(xiàn)奇數(shù)個(gè)差錯(cuò)的分組碼；n 較大，即編碼碼組較長(zhǎng)時(shí)，編碼效率較大，即編碼碼組較長(zhǎng)時(shí)，編碼效率 接近于接近于1;（n-1）/n 信息碼元比信息碼元比 碼組碼元碼組碼元 適用于檢測(cè)隨機(jī)的零星錯(cuò)碼適用于檢測(cè)隨機(jī)的零星錯(cuò)碼加性白噪聲加性白噪聲造造 成的成的2022年5月7日128.1.3 幾種簡(jiǎn)單的檢錯(cuò)碼幾種簡(jiǎn)單的檢錯(cuò)碼(2)二維奇偶監(jiān)督碼二維奇偶監(jiān)督碼 (6,11)行列監(jiān)督碼 2022年5月7日13二維奇偶監(jiān)督碼二維奇偶監(jiān)督碼 編碼方法：把碼元排成方陣，按行列進(jìn)行奇偶校驗(yàn)編碼方法：把碼元排成方陣，按行列進(jìn)行奇偶校驗(yàn) 分別附

13、加一位監(jiān)督碼元分別附加一位監(jiān)督碼元 特點(diǎn)：不僅可檢測(cè)每行（每列）中奇數(shù)個(gè)錯(cuò)誤，而且特點(diǎn)：不僅可檢測(cè)每行（每列）中奇數(shù)個(gè)錯(cuò)誤，而且 可通過(guò)水平監(jiān)督和垂直監(jiān)督來(lái)確定錯(cuò)碼的位置可通過(guò)水平監(jiān)督和垂直監(jiān)督來(lái)確定錯(cuò)碼的位置 糾正僅一行（一列）出現(xiàn)的奇數(shù)個(gè)錯(cuò)誤糾正僅一行（一列）出現(xiàn)的奇數(shù)個(gè)錯(cuò)誤 通過(guò)水平監(jiān)督和垂直監(jiān)督的關(guān)系可以發(fā)現(xiàn)單行中出現(xiàn)通過(guò)水平監(jiān)督和垂直監(jiān)督的關(guān)系可以發(fā)現(xiàn)單行中出現(xiàn) 的偶數(shù)個(gè)錯(cuò)誤；但不能發(fā)現(xiàn)構(gòu)成矩形的的偶數(shù)個(gè)錯(cuò)誤；但不能發(fā)現(xiàn)構(gòu)成矩形的4個(gè)錯(cuò)誤碼元個(gè)錯(cuò)誤碼元 適用于突發(fā)差錯(cuò)適用于突發(fā)差錯(cuò)由突發(fā)干擾（突發(fā)脈沖，如：由突發(fā)干擾（突發(fā)脈沖，如： 閃電，電火花等）在短時(shí)間內(nèi)錯(cuò)碼成串出現(xiàn)，在某閃電，

14、電火花等）在短時(shí)間內(nèi)錯(cuò)碼成串出現(xiàn)，在某 一行中出現(xiàn)多個(gè)錯(cuò)碼一行中出現(xiàn)多個(gè)錯(cuò)碼2022年5月7日148.1.3 幾種簡(jiǎn)單的檢錯(cuò)碼幾種簡(jiǎn)單的檢錯(cuò)碼(3)重復(fù)碼重復(fù)碼 在每位信息碼元之后，用簡(jiǎn)單重復(fù)多次的方法編碼。在每位信息碼元之后，用簡(jiǎn)單重復(fù)多次的方法編碼。例：重復(fù)兩次時(shí)，用例：重復(fù)兩次時(shí)，用111傳輸傳輸1碼，用碼，用000傳輸傳輸0碼碼 編碼方法：每位信息碼元簡(jiǎn)單重復(fù)多次；編碼方法：每位信息碼元簡(jiǎn)單重復(fù)多次； 收端收端 譯碼采用多數(shù)表決法；譯碼采用多數(shù)表決法；例：重復(fù)例：重復(fù)2 2次次特點(diǎn)：糾正特點(diǎn)：糾正1 1個(gè)錯(cuò)，檢出個(gè)錯(cuò)，檢出2 2個(gè)錯(cuò)個(gè)錯(cuò)2022年5月7日158.1.3 幾種簡(jiǎn)單的檢錯(cuò)碼

15、幾種簡(jiǎn)單的檢錯(cuò)碼(4)恒比碼恒比碼碼字中碼字中 1 1 的數(shù)目與的數(shù)目與 0 0 的數(shù)目保持的數(shù)目保持恒定比例的碼稱(chēng)為恒比碼恒定比例的碼稱(chēng)為恒比碼。這種碼在檢測(cè)時(shí)，只要計(jì)算接收碼這種碼在檢測(cè)時(shí)，只要計(jì)算接收碼元中元中 1 1 的數(shù)目是否正確，的數(shù)目是否正確，就知道有無(wú)錯(cuò)誤。就知道有無(wú)錯(cuò)誤。 2022年5月7日16恒比碼恒比碼例：例：5中取中取3恒比碼恒比碼用于電報(bào)電碼用于電報(bào)電碼 每個(gè)碼組長(zhǎng)度為每個(gè)碼組長(zhǎng)度為5，共有，共有25=32種不同的碼組，種不同的碼組， 其中有其中有3個(gè)個(gè)1的碼組為可用碼組，共有的碼組為可用碼組，共有10種種 表示表示10個(gè)阿拉伯?dāng)?shù)字，用它拼成漢字（每個(gè)阿拉伯?dāng)?shù)字，用它

16、拼成漢字（每4阿拉阿拉 伯?dāng)?shù)字組成伯?dāng)?shù)字組成1個(gè)漢字電碼）；其余的個(gè)漢字電碼）；其余的22個(gè)為禁用個(gè)為禁用 碼組。碼組。特點(diǎn)：簡(jiǎn)單；除了特點(diǎn)：簡(jiǎn)單；除了1錯(cuò)為錯(cuò)為0與與0錯(cuò)為錯(cuò)為1成對(duì)出現(xiàn)（對(duì)換成對(duì)出現(xiàn)（對(duì)換 性）差錯(cuò)不能檢測(cè)外，其它任何奇數(shù)個(gè)或偶數(shù)性）差錯(cuò)不能檢測(cè)外，其它任何奇數(shù)個(gè)或偶數(shù) 個(gè)錯(cuò)碼都可以被檢測(cè)出來(lái)。個(gè)錯(cuò)碼都可以被檢測(cè)出來(lái)。只適用于傳輸種類(lèi)較少且有固定代碼的字符，而不適只適用于傳輸種類(lèi)較少且有固定代碼的字符，而不適用于表示由信源來(lái)的二進(jìn)制隨機(jī)，數(shù)字序列。用于表示由信源來(lái)的二進(jìn)制隨機(jī)，數(shù)字序列。2022年5月7日178.1.3 幾種簡(jiǎn)單的檢錯(cuò)碼幾種簡(jiǎn)單的檢錯(cuò)碼(4)ISBN國(guó)際統(tǒng)一

17、圖書(shū)編號(hào)國(guó)際統(tǒng)一圖書(shū)編號(hào)例例 ISBN 04710297772022年5月7日188.1.4 檢錯(cuò)和糾錯(cuò)的基本原理檢錯(cuò)和糾錯(cuò)的基本原理如用如用三位二進(jìn)制編碼來(lái)代表八個(gè)字母三位二進(jìn)制編碼來(lái)代表八個(gè)字母000 A000 A100100E E001 001 B B101101F F010010C C110110G G011011D D111111H H不管哪一位發(fā)生錯(cuò)誤，都會(huì)使傳輸字母錯(cuò)誤不管哪一位發(fā)生錯(cuò)誤，都會(huì)使傳輸字母錯(cuò)誤如用三位字母?jìng)魉膫€(gè)字母如用三位字母?jìng)魉膫€(gè)字母000 A000 A011011B B101 101 C C110110D D發(fā)生一位錯(cuò)誤，準(zhǔn)用碼字將變成禁用碼字，接收端就能知道發(fā)

18、生一位錯(cuò)誤，準(zhǔn)用碼字將變成禁用碼字，接收端就能知道出錯(cuò)，但是不能糾錯(cuò)出錯(cuò)，但是不能糾錯(cuò)。如果進(jìn)一步將許用碼組限制為兩種如果進(jìn)一步將許用碼組限制為兩種000 A 111 B000 A 111 B檢錯(cuò)和糾錯(cuò)能力是用信息量的冗余度來(lái)?yè)Q取的。檢錯(cuò)和糾錯(cuò)能力是用信息量的冗余度來(lái)?yè)Q取的。2022年5月7日19檢錯(cuò)和糾錯(cuò)的基本原理檢錯(cuò)和糾錯(cuò)的基本原理檢錯(cuò)和糾錯(cuò)能力是用信息量的冗余度換取的檢錯(cuò)和糾錯(cuò)能力是用信息量的冗余度換取的與碼組之間的差別有關(guān)；不同的編碼方法和與碼組之間的差別有關(guān)；不同的編碼方法和形式，檢錯(cuò)和糾錯(cuò)能力不同。形式，檢錯(cuò)和糾錯(cuò)能力不同。例：例： n = 3，共有，共有8種組合，都用于傳輸消息，

19、種組合，都用于傳輸消息，在傳輸過(guò)程中若發(fā)生一個(gè)誤碼，則一種碼組就在傳輸過(guò)程中若發(fā)生一個(gè)誤碼，則一種碼組就會(huì)錯(cuò)誤地變成另一種碼組，但接收端卻不能發(fā)會(huì)錯(cuò)誤地變成另一種碼組，但接收端卻不能發(fā)現(xiàn)錯(cuò)誤，因?yàn)槿魏我粋€(gè)碼組都是許用碼組?，F(xiàn)錯(cuò)誤，因?yàn)槿魏我粋€(gè)碼組都是許用碼組。 在差錯(cuò)控制編碼中，定義碼組中非零碼元的數(shù)目為碼字的在差錯(cuò)控制編碼中，定義碼組中非零碼元的數(shù)目為碼字的漢明漢明(Hamming)(Hamming)重量重量， 簡(jiǎn)稱(chēng)簡(jiǎn)稱(chēng)碼重碼重。例如，碼字。例如，碼字 1011010110，碼重，碼重w w=3=3。 定義兩個(gè)等長(zhǎng)碼組之間相應(yīng)位取值不同的數(shù)目為這兩個(gè)碼組的定義兩個(gè)等長(zhǎng)碼組之間相應(yīng)位取值不同的

20、數(shù)目為這兩個(gè)碼組的漢漢明明(Hamming)(Hamming)距離距離， 簡(jiǎn)稱(chēng)簡(jiǎn)稱(chēng)碼距碼距。例如。例如 11000 11000 與與 1001110011之間的距離之間的距離d=3d=3。 碼組集中任意兩個(gè)碼字之間距離的最小值稱(chēng)為碼組集中任意兩個(gè)碼字之間距離的最小值稱(chēng)為碼的最小距離碼的最小距離，用，用d dminmin表示。最小碼距是碼的一個(gè)重要參數(shù)，表示。最小碼距是碼的一個(gè)重要參數(shù)， 它是衡量碼檢錯(cuò)、糾錯(cuò)能它是衡量碼檢錯(cuò)、糾錯(cuò)能力的依據(jù)。力的依據(jù)。 2022年5月7日21最小碼距與檢錯(cuò)糾錯(cuò)能力的關(guān)系最小碼距與檢錯(cuò)糾錯(cuò)能力的關(guān)系 碼組內(nèi)的距離反映了碼組之間的差別，碼組內(nèi)的距離反映了碼組之間的差

21、別，最小距離越大，說(shuō)明兩個(gè)碼組間的最小最小距離越大，說(shuō)明兩個(gè)碼組間的最小差別越大，或者說(shuō)其中一個(gè)碼組錯(cuò)為另差別越大，或者說(shuō)其中一個(gè)碼組錯(cuò)為另一個(gè)碼組的可能性就越小，那么其檢錯(cuò)一個(gè)碼組的可能性就越小，那么其檢錯(cuò)和糾錯(cuò)能力也就越強(qiáng)，因此可以說(shuō)最小和糾錯(cuò)能力也就越強(qiáng)，因此可以說(shuō)最小碼距是衡量一種糾錯(cuò)編碼的檢錯(cuò)，糾錯(cuò)碼距是衡量一種糾錯(cuò)編碼的檢錯(cuò)，糾錯(cuò)能力大小的標(biāo)準(zhǔn)。能力大小的標(biāo)準(zhǔn)。 碼的最小距離直接關(guān)系著碼的檢錯(cuò)和糾錯(cuò)能力；任一碼的最小距離直接關(guān)系著碼的檢錯(cuò)和糾錯(cuò)能力；任一( (n,kn,k) )分組碼，若要在碼字內(nèi)分組碼，若要在碼字內(nèi): : (1) (1) 檢測(cè)檢測(cè)e e個(gè)隨機(jī)錯(cuò)誤，則要求碼的最小距

22、離個(gè)隨機(jī)錯(cuò)誤，則要求碼的最小距離d dminmine e+1;+1; (2) (2) 糾正糾正t t個(gè)隨機(jī)錯(cuò)誤，個(gè)隨機(jī)錯(cuò)誤， 則要求碼的最小距離則要求碼的最小距離d dminmin22t t+1;+1; (3) (3) 糾正糾正t t個(gè)同時(shí)檢測(cè)個(gè)同時(shí)檢測(cè)e e(t t) )個(gè)隨機(jī)錯(cuò)誤，則要求個(gè)隨機(jī)錯(cuò)誤，則要求碼的最小距離碼的最小距離d dminmint t+ +e e+1+1。 t1eAB2022年5月7日23 用差錯(cuò)控制編碼提高通信系統(tǒng)的可靠性， 是以降低有效性為代價(jià)換來(lái)的。我們定義編碼效率R來(lái)衡量有效性: Rc=k/n其中, k是信息元的個(gè)數(shù)，n為碼長(zhǎng)。 對(duì)糾錯(cuò)碼的基本要求是: 檢錯(cuò)和糾錯(cuò)

23、能力盡量強(qiáng)； 編碼效率盡量高；編碼規(guī)律盡量簡(jiǎn)單。實(shí)際中要根據(jù)具體指標(biāo)要求，保證有一定糾、檢錯(cuò)能力和編碼效率，并且易于實(shí)現(xiàn)。 編碼效率編碼效率2022年5月7日248.2 線(xiàn)性分組碼線(xiàn)性分組碼線(xiàn)性分組碼的構(gòu)成線(xiàn)性分組碼的構(gòu)成 將信息序列劃分為等長(zhǎng)將信息序列劃分為等長(zhǎng)(k位位)的序列段的序列段 共有共有2k個(gè)不同的序列段，在每一信息個(gè)不同的序列段，在每一信息 段之后，附加段之后，附加m位監(jiān)督元，構(gòu)成長(zhǎng)度位監(jiān)督元，構(gòu)成長(zhǎng)度 n = k + m的分組碼的分組碼(n ，k) 監(jiān)督元與信息碼元為線(xiàn)性關(guān)系監(jiān)督元與信息碼元為線(xiàn)性關(guān)系2022年5月7日25例例 信息元長(zhǎng)度信息元長(zhǎng)度k = 3共有共有2k = 8

24、個(gè)不同的信息組個(gè)不同的信息組 每組信息組加每組信息組加4個(gè)監(jiān)督元，構(gòu)成一個(gè)長(zhǎng)度為個(gè)監(jiān)督元，構(gòu)成一個(gè)長(zhǎng)度為7 的的(7，3)線(xiàn)性分組碼。線(xiàn)性分組碼。 設(shè)：設(shè)： 每組信息元為每組信息元為C1C2C3監(jiān)督元為監(jiān)督元為C4 C5 C6C7 根據(jù)下列線(xiàn)性方程組求監(jiān)督元根據(jù)下列線(xiàn)性方程組求監(jiān)督元 C4 = C1 + C3 C5 = C1 + C2 + C3 C6 = C1 + C2 C7 = C2 + C32022年5月7日26例例 (7，3)碼有碼有8個(gè)信息組，信息組按上方程組求得每個(gè)個(gè)信息組，信息組按上方程組求得每個(gè) 信息組的信息組的4個(gè)監(jiān)督元，得到個(gè)監(jiān)督元，得到(7，3)碼的所有碼的所有8個(gè)碼字個(gè)碼

25、字 信息組信息組 碼元碼元 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 0 1 1 0 1 0 0 1 1 1 1 0 1 1 0 1 0 0 1 1 1 1 1 1 1 0 1 0 0重要特性，線(xiàn)性碼有封閉性重要特性，線(xiàn)性碼有封閉性 2022年5月7日278.2 線(xiàn)性分組碼線(xiàn)性分組碼設(shè)分組碼由設(shè)分組碼由n n位碼組構(gòu)成，記為位碼組構(gòu)成，記為c c1 1，c c2 2，c cn n，信息碼組由，信息碼組由k k位位碼組成，記為碼組成，記

26、為d d1 1，d d2 2，d dk k。則該分組碼記為（。則該分組碼記為（n n，k k）碼。）碼。碼組和信息碼組可用行矩陣碼組和信息碼組可用行矩陣C C和和D D表示表示若為線(xiàn)性分組碼，若為線(xiàn)性分組碼，C C中的中的n n個(gè)元素都是由個(gè)元素都是由D D中的中的k k個(gè)元素經(jīng)線(xiàn)性組合個(gè)元素經(jīng)線(xiàn)性組合形成的?？捎靡宦?lián)立方程表示為形成的。可用一聯(lián)立方程表示為1212,nkCc ccDd dd112211111221221122221122,kkkkkkkknmmmkcdcdcdch dh dh dch dh dh dch dh dh dmnk其中是校驗(yàn)位數(shù)將碼組將碼組C寫(xiě)成矩陣形式寫(xiě)成矩陣形式

27、GC=D矩陣矩陣G稱(chēng)為生成矩陣，它是一個(gè)稱(chēng)為生成矩陣，它是一個(gè)kn的矩陣的矩陣2022年5月7日29生成矩陣生成矩陣G 112111222212112111222212100001000001,100001000001C,mmkkmkkkkkkkmkkkmhhhhhhGhhhGIPhhhhhhIPhhhCD IPDIDPD DPD C碼組 又可表示為2022年5月7日30生成矩陣生成矩陣GIk 單位矩陣，單位矩陣，k行行k列列(k x k階階)P矩陣，矩陣，k行行m列列(k x m階階)編碼前編碼前k位，編碼后有位，編碼后有n位，位，2n 2k；選擇選擇P矩陣，可得到有較強(qiáng)檢錯(cuò)糾錯(cuò)能力，實(shí)現(xiàn)矩

28、陣，可得到有較強(qiáng)檢錯(cuò)糾錯(cuò)能力，實(shí)現(xiàn) 方法盡可能簡(jiǎn)單，編碼效率又高的線(xiàn)性分組碼方法盡可能簡(jiǎn)單，編碼效率又高的線(xiàn)性分組碼由于線(xiàn)性碼具有封閉性，故任何二個(gè)碼組之間的距離由于線(xiàn)性碼具有封閉性，故任何二個(gè)碼組之間的距離必須與某一個(gè)碼組中必須與某一個(gè)碼組中“1”的個(gè)數(shù)相等，而碼組中非零的個(gè)數(shù)相等，而碼組中非零碼元的數(shù)目碼元的數(shù)目“1”的個(gè)數(shù)為碼組的重量（碼重）所以線(xiàn)的個(gè)數(shù)為碼組的重量（碼重）所以線(xiàn)性碼任意二個(gè)碼字之間的距離必須等于碼中某一個(gè)碼性碼任意二個(gè)碼字之間的距離必須等于碼中某一個(gè)碼字的重量字的重量線(xiàn)性碼最小碼距正好等于非零碼的最小線(xiàn)性碼最小碼距正好等于非零碼的最小碼重碼重估算線(xiàn)性碼的差錯(cuò)控制能力：估

29、算線(xiàn)性碼的差錯(cuò)控制能力： 求最小碼距求最小碼距最小碼重最小碼重2022年5月7日31例例 已知（已知（6，3）碼的生成距陣，求：編碼碼組）碼的生成距陣，求：編碼碼組2022年5月7日32監(jiān)督矩陣監(jiān)督矩陣H0,00,mmTTTmmmmDPCDPCPPD CCHHorHPIII寫(xiě)成矩陣形式，有或?qū)懗善渲行ｒ?yàn)矩陣或監(jiān)督矩陣校驗(yàn)矩陣或監(jiān)督矩陣H H： m x n m x n 階階P PT T: : m m行行k k列列 k + m = nk + m = n列列2022年5月7日33伴隨式（校正子）伴隨式（校正子）S 設(shè)發(fā)送碼組設(shè)發(fā)送碼組C=C=c cn n-1-1, ,c cn n-2-2, , ,c

30、 c1 1, ,c c0 0，在傳輸過(guò)程中可能在傳輸過(guò)程中可能 發(fā)生誤碼。接收碼組發(fā)生誤碼。接收碼組R R = =r rn n-1-1, ,r rn n-2-2, , ,r r1 1, ,r r0 0，則收發(fā)碼組之則收發(fā)碼組之差定差定義為錯(cuò)誤圖樣義為錯(cuò)誤圖樣E E， 也稱(chēng)為誤差矢量，也稱(chēng)為誤差矢量， 即即 E E =R=RC C =en-1,en-2,e1,e0，且且 01ie= 當(dāng)ri=ci 當(dāng)rici 令令 S = RHT，稱(chēng)為稱(chēng)為伴隨式伴隨式或或校正子校正子 S = RHS = RHT T = CH = CHT T EHEHT T = = EHEHT T S S只與錯(cuò)誤圖形有關(guān)，與發(fā)送的

31、碼組只與錯(cuò)誤圖形有關(guān)，與發(fā)送的碼組C C無(wú)關(guān)無(wú)關(guān) H HT T ：n x m n x m 階；階；E E：1x n 1x n 階；階；S S：1x m 1x m 階；階；S = sS = s1 1 s s2 2 s sm m 解得誤差矢量解得誤差矢量E E，求得糾錯(cuò)后的碼組求得糾錯(cuò)后的碼組 C = R C = R E E2022年5月7日34檢錯(cuò)與糾錯(cuò)檢錯(cuò)與糾錯(cuò)檢錯(cuò)：當(dāng)碼組出現(xiàn)錯(cuò)誤檢錯(cuò)：當(dāng)碼組出現(xiàn)錯(cuò)誤S為非零矢量為非零矢量糾錯(cuò)：糾錯(cuò)： S = RHT = CHT EHT = EHT S與與E之間有著確定的線(xiàn)性關(guān)系之間有著確定的線(xiàn)性關(guān)系由由H矩陣矩陣 確定（也就是與確定（也就是與G（P）矩陣有關(guān)

32、）矩陣有關(guān)） S=s1 s2 sm 共有共有2m種不同的形式，除全種不同的形式，除全 0外，可代表外，可代表2m -1種有錯(cuò)誤的圖形種有錯(cuò)誤的圖形 信息碼組有信息碼組有2k個(gè)錯(cuò)誤圖形，有多種不同的形式個(gè)錯(cuò)誤圖形，有多種不同的形式可能有可能有2k種解答；為了選擇正確的結(jié)果，要使種解答；為了選擇正確的結(jié)果，要使用最大似然比準(zhǔn)則，選擇與用最大似然比準(zhǔn)則，選擇與R最相似的最相似的C（與（與R距離最小的碼組距離最小的碼組E是是1碼最小的矢量）碼最小的矢量）。2022年5月7日35例：（例：（6，3）碼）碼2022年5月7日36S與與E對(duì)照表對(duì)照表 E S 0 0 0 0 0 0 0 0 0 1 0 0

33、0 0 0 1 0 1 0 1 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 1 1 1 （6，3）碼具有糾碼具有糾1位錯(cuò)的能力位錯(cuò)的能力發(fā)生發(fā)生1 1個(gè)錯(cuò)誤的情況：個(gè)錯(cuò)誤的情況： S S是是H HT T的第的第i i行，說(shuō)明行，說(shuō)明R R中第中第i i位位 產(chǎn)生了錯(cuò)誤，可以把它糾正產(chǎn)生了錯(cuò)誤，可以把它糾正發(fā)生發(fā)生2個(gè)錯(cuò)誤的情況：個(gè)錯(cuò)誤的情況： 除除S=111對(duì)應(yīng)第對(duì)應(yīng)第1，5位有錯(cuò)位有錯(cuò) 其它的雙錯(cuò)不能得到糾正其它的雙錯(cuò)不能得到糾正 例：例：

34、接收碼組接收碼組R111011 2022年5月7日37查表法譯碼器的原理查表法譯碼器的原理S = RHT = CHT EHT = EHT算出伴隨式算出伴隨式S與最小碼重的差錯(cuò)與最小碼重的差錯(cuò)矢量矢量E的對(duì)照表，提供譯碼使用的對(duì)照表，提供譯碼使用2022年5月7日38漢明碼漢明碼按上述方法構(gòu)造的能糾正單個(gè)錯(cuò)誤的線(xiàn)性分組碼稱(chēng)為按上述方法構(gòu)造的能糾正單個(gè)錯(cuò)誤的線(xiàn)性分組碼稱(chēng)為 漢明碼。漢明碼。對(duì)于線(xiàn)性分組碼，為了指示所有單錯(cuò)位置和無(wú)錯(cuò)的情況，對(duì)于線(xiàn)性分組碼，為了指示所有單錯(cuò)位置和無(wú)錯(cuò)的情況，必須滿(mǎn)足不等式必須滿(mǎn)足不等式漢明碼具有以下特點(diǎn)：漢明碼具有以下特點(diǎn)：漢明碼的編碼效率漢明碼的編碼效率213211

35、mmndkmtmnk碼長(zhǎng)最小碼距信息碼位糾錯(cuò)能力監(jiān)督碼位21mn（取等號(hào)時(shí)即為漢明碼）2112121mcmmkmmRn 2022年5月7日39漢明界漢明界如果碼組有糾如果碼組有糾t個(gè)差錯(cuò)的能力，則應(yīng)能指出無(wú)錯(cuò)、單錯(cuò)到個(gè)差錯(cuò)的能力，則應(yīng)能指出無(wú)錯(cuò)、單錯(cuò)到t個(gè)差錯(cuò)所個(gè)差錯(cuò)所有可能的情況，校驗(yàn)位數(shù)有可能的情況，校驗(yàn)位數(shù)m應(yīng)滿(mǎn)足不等式：應(yīng)滿(mǎn)足不等式：02tmjnjC漢明界，是糾正t個(gè)差錯(cuò)的一個(gè)必要條件2022年5月7日408.3 循環(huán)碼循環(huán)碼特點(diǎn)特點(diǎn)線(xiàn)性分組碼循環(huán)性任一許用碼字經(jīng)過(guò)循環(huán)移位后，得到的碼組仍為一個(gè)許用碼組 如 是循環(huán)碼的一許用碼組 則 也是一許用碼組 移位i次得到 也是許用碼組12,nC

36、c cc(1)231,nCc cc c( )121,iiiniCccc cc2022年5月7日418.3.1 循環(huán)碼的特點(diǎn)及表達(dá)循環(huán)碼的特點(diǎn)及表達(dá)碼多項(xiàng)式表示碼多項(xiàng)式表示以此類(lèi)推，碼組以此類(lèi)推，碼組C移位移位i i次，相應(yīng)的碼多項(xiàng)式次，相應(yīng)的碼多項(xiàng)式c c(i)(i)(x)(x)是是x xi ic(x)c(x)除以除以（x xn n+1)+1)后的余式。后的余式。在模在模（x xn n+1)+1)意義下，若意義下，若c(xc(x) )是碼多項(xiàng)式，則是碼多項(xiàng)式，則x xi ic(x)c(x)都都是碼多項(xiàng)式。是碼多項(xiàng)式。1212(1)(1)122311(1)121( )( )( )(1)( )nn

37、nnnnnnnnCc xc xc xcCcxc xc xc xcx c xc xc xc xc xcx (1)( )( )1ncxx c xx正好是除以后的余式2022年5月7日42循環(huán)碼的編碼過(guò)程循環(huán)碼的編碼過(guò)程一個(gè)一個(gè)k位的信息碼組位的信息碼組 可用信息多項(xiàng)式表示可用信息多項(xiàng)式表示假設(shè)碼組多項(xiàng)式可表示為假設(shè)碼組多項(xiàng)式可表示為12,kDd dd1212( )kkkd xd xd xd( )( )( )c xd xg x1212(1)1(1)1( )( )( )( )( )( )( )( )(1)( )( )( )kkknc xd xg xd xg xd g xx c xx d xg xg x

38、x c xcxcxcxdx g x ）是的 倍 式而）如果如果( (n n +1) +1)是是g(g() )的倍式的倍式 C C（1 1）( ()=)=d(d()g()g()+ aC)+ aC1 1g(g() ) = =d(d()+ aC)+ aC1 1g(g()= d)= d1( ()g()g() ) d d1 1( () )對(duì)應(yīng)某個(gè)信息碼組對(duì)應(yīng)某個(gè)信息碼組2022年5月7日43生成多項(xiàng)式生成多項(xiàng)式g() (n +1)是是g()的倍式，且的倍式，且g()為為n-k次多次多項(xiàng)式，所以對(duì)項(xiàng)式，所以對(duì)(n +1)進(jìn)行因式分解，便進(jìn)行因式分解，便可得到相應(yīng)的可得到相應(yīng)的g()。對(duì)對(duì)(n +1)進(jìn)行因式進(jìn)行因式分解可由計(jì)算機(jī)完成，有表格給出。分解可由計(jì)算機(jī)完成，有表格給出。由信息多項(xiàng)式求解碼多項(xiàng)式由信息多項(xiàng)式求解碼多項(xiàng)式 C() = d() g() n-1次次 k-1次次 n-k次次2022年5月7日44例例 (7，4) n=7k=4 m=n-k=3 g()應(yīng)為應(yīng)為(7 + 1 )的的3次因式次因式 + 1 = (+ 1 ) ( + + 1 ) ( + + 1 ) g1() = ( + + 1 ) g2() = ( + + 1 )D = 1010 d() = ( + )C1() = d()g1() = ( + ) ( + + 1 ) = + + + C1 = 10011