電腦基礎(chǔ)知識41-抗干擾編碼的基本概念

第四章抗干擾二元編碼§4.2檢錯碼§4.1抗干擾編碼的基本概念§4.3用于單向信道的簡單糾錯碼§4.4糾一位錯誤的漢明碼§4.6糾獨(dú)立錯誤的卷積碼§4.5循環(huán)碼§4.7糾突發(fā)錯誤的編碼§4.1抗干擾編碼的基本概念一、引言二、幾個名詞三、最小碼距與糾錯能力的關(guān)系

四、抗干擾編碼的基本原理五、抗干擾編碼的分類一、引言信號通過信道進(jìn)行傳遞時，由于噪聲的干擾，使得收到的信號受到破壞，稱為信道編碼。值得注意的是，抗干擾編碼不僅僅用于通信，其應(yīng)用的廣泛程度是當(dāng)初抗干擾編碼的創(chuàng)始者們?nèi)f萬沒有想到的。身份證的校驗(yàn)改造(即抗干擾編碼)，使信號具有抗干擾性。

條形碼的校驗(yàn)

DVD

糾錯計算機(jī)中的奇偶校驗(yàn)貨幣中的防偽編碼……………因此，常常需要對待傳遞的信號進(jìn)行編碼抗干擾編碼又一、引言1.基本思想有效性編碼是盡可能降低信號內(nèi)部的關(guān)聯(lián)性，而抗干擾編碼則是通過某種運(yùn)算方式使得信號(碼字)的內(nèi)部結(jié)構(gòu)具有破壞，就可以發(fā)現(xiàn)錯誤，甚至糾正錯誤。更強(qiáng)的規(guī)律性或者關(guān)聯(lián)性?？垢蓴_編碼的輸出碼字一般都采用等長碼。一旦這種規(guī)律性或者關(guān)聯(lián)性遭到一、引言2.編碼對象(1)直接針對消息或者字符；(2)針對(已經(jīng)過有效性編碼后的)二元序列。本章中除了定比碼是直接針對消息或者字符之外，其余的工作都是圍繞二元序列進(jìn)行的。3.引例方案一2

位不相同若收到0

1或1

0，則能夠發(fā)現(xiàn)錯誤；(檢錯)但不能糾正錯誤。(糾錯)則上述編碼方案得到一個相當(dāng)好的檢錯碼。事實(shí)上，如果假定每兩位同時出錯的概率非常小，注考慮某二元序列：編碼后的序列：一、引言方案二若出現(xiàn)一位錯，則能夠發(fā)現(xiàn)錯誤；(檢錯)但不能糾正錯誤。(糾錯)由于每兩位只增加一位，因此與方案一相比具有優(yōu)勢。

注編碼后的序列：2222222位不相同3.引例一、引言考慮某二元序列：方案三3

位不相同若收到0

0

1，則能夠發(fā)現(xiàn)錯誤；(檢錯)還“可以”糾正為0

0

0。(糾錯)事實(shí)上，由于錯一位的概率遠(yuǎn)遠(yuǎn)小于錯兩位的概率，

注因此通常采用

最小距離準(zhǔn)則

進(jìn)行

自動糾錯。編碼后的序列：3.引例一、引言考慮某二元序列：方案四若出現(xiàn)一位錯，則能夠發(fā)現(xiàn)錯誤；(檢錯)且能夠糾正錯誤。(糾錯)43333位不相同4編碼后的序列為：由于每兩位只增加三位，因此與方案三相比具有優(yōu)勢。

注3.引例一、引言考慮某二元序列：小結(jié)(1)碼字之間相差一個碼元

(2)碼字之間相差兩個碼元

(3)碼字之間相差三個碼元

或者糾正一位錯誤。(4)碼字之間相差四個碼元

一、引言不能發(fā)現(xiàn)錯誤。

——可以發(fā)現(xiàn)一位錯誤。

——可以發(fā)現(xiàn)兩位錯誤；

——

——?1.許用碼字與禁用碼字二、幾個名詞許用碼字抗干擾編碼后實(shí)際使用的碼字(或碼組)。例如某抗干擾編碼為：

全體許用碼字構(gòu)成碼字集合。禁用碼字抗干擾編碼后不使用的碼字(或碼組)。若收到的碼字為禁用碼字，則發(fā)現(xiàn)有錯。許用碼字

禁用碼字

2.碼距與最小碼距二、幾個名詞碼距兩個碼字之間對應(yīng)位置的不同碼元的個數(shù)。碼距有時也稱為漢明(Hamming)碼距。具體設(shè)有兩個碼字分別為：其中則(漢明)碼距為模

2

加：如果引入模

2

加，則有2.碼距與最小碼距二、幾個名詞最小碼距碼字集合中各個碼字之間碼距的最小值。碼重碼字中碼元為

“1”

的個數(shù)；碼重又稱為漢明碼重。

例如碼字的碼重為

3。例如最小碼距為

2最小碼距為

32222222編碼方案(一)343334編碼方案(二)三、最小碼距與糾錯能力的關(guān)系

則

最小碼距必須滿足條件：(1)若要發(fā)現(xiàn)e位錯誤，

結(jié)論(2)若要糾正t位錯誤，則必須滿足條件：(3)若要糾正t位錯誤，且“發(fā)現(xiàn)”e位錯誤，其中則必須滿足條件：(如何理解?)①檢錯三、最小碼距與糾錯能力的關(guān)系

(1)對于編碼方案:

例如最小碼距為3。能夠發(fā)現(xiàn)2位錯。②

糾錯

能夠糾正1位錯。(純粹進(jìn)行檢錯)(采用最小距離準(zhǔn)則自動糾錯)

問題：如果出現(xiàn)2位錯，會怎么樣？結(jié)果：不能發(fā)現(xiàn)，而是自動糾“錯”了，比如發(fā)送的是收到的是即將自動地糾“錯”為糾正

1

位錯誤。

當(dāng)最小碼距為

3

時，其糾錯能力為：①檢錯三、最小碼距與糾錯能力的關(guān)系

最小碼距為4。②

糾錯

能夠發(fā)現(xiàn)3位錯。(純粹進(jìn)行檢錯)能夠糾正1位錯。(采用最小距離準(zhǔn)則自動糾錯)

問題：(1)如果出現(xiàn)2位錯，會怎么樣？結(jié)果：(1)無法自動糾錯，只能報告出來;(2)對于編碼方案:

例如(2)如果出現(xiàn)3位錯，又會怎么樣？(2)不能發(fā)現(xiàn)，而是自動糾

“錯”

了。當(dāng)最小碼距為4時，其糾錯能力為：糾正1

位錯誤，且“報告”2

位錯誤。三、最小碼距與糾錯能力的關(guān)系

最小碼距為

5。①檢錯能夠發(fā)現(xiàn)4位錯。(純粹進(jìn)行檢錯)②

糾錯

能夠糾正2位錯。(采用最小距離準(zhǔn)則自動糾錯)

(3)對于編碼方案:

例如則不能發(fā)現(xiàn)，而是自動糾

“錯”

了。如果出現(xiàn)3位錯或者4位錯，

糾正

2

位錯誤。

當(dāng)最小碼距為

5

時，其糾錯能力為：問:如果最小碼距為

5，但只糾1

位錯，結(jié)果會如何？可以只糾正1

位錯誤，且“報告”3

位錯誤。答:三、最小碼距與糾錯能力的關(guān)系

糾正3位錯且“報告”4位錯糾正2位錯且“報告”3位錯糾正1位錯且“報告”2位錯

糾正3位錯

糾正2位錯

糾正1位錯無無糾錯能力發(fā)現(xiàn)7位錯發(fā)現(xiàn)6位錯發(fā)現(xiàn)5位錯發(fā)現(xiàn)4位錯發(fā)現(xiàn)3位錯發(fā)現(xiàn)2位錯發(fā)現(xiàn)1位錯無檢錯能力87654321最小碼距

關(guān)系表(部分)：通常會選擇最小碼距為奇數(shù)的編碼方案。注1.基本方法四、抗干擾編碼的基本原理(1)針對有效性編碼后的二元序列每

k

個碼元作為一組，對應(yīng)到長度為

n(

>

k

)的一個碼字。

通常的方法是在原始碼組的基礎(chǔ)上進(jìn)行

“擴(kuò)充”，原始二元序列…

…編碼后的序列…

…某種規(guī)律，添加一些新的碼元來構(gòu)成相應(yīng)的碼字。這些新的碼元稱為

監(jiān)督位；而原始碼元稱為

信息位。

抗干擾編碼效率：抗即按照1.基本方法四、抗干擾編碼的基本原理(2)針對消息(或者符號)

直接將原始信源中的每一個消息(或者符號)對應(yīng)到一個

抗干擾編碼效率：

抗(關(guān)于抗干擾編碼效率的說明)長度為n

的等長的二元碼字。

為了能夠抗干擾，其碼長肯定比所需的碼長要長一些。其中，為原始信源的最大熵。2.代數(shù)編碼四、抗干擾編碼的基本原理例如設(shè)某編碼方案為

代數(shù)編碼

是指碼字中的碼元之間滿足一定的代數(shù)關(guān)系。將碼字記為生成陣監(jiān)督陣信息碼組監(jiān)督位信息位(1)(生成)(2)(監(jiān)督)則有2.代數(shù)編碼四、抗干擾編碼的基本原理

代數(shù)編碼

是指碼字中的碼元之間滿足一定的代數(shù)關(guān)系。除了代數(shù)編碼之外，還有幾何編碼、算術(shù)編碼以及組合(1)分組代數(shù)碼，簡稱為

分組碼

或者

塊碼；(2)卷積代數(shù)碼，簡稱為

卷積碼

或者

連環(huán)碼。編碼等等。

按照碼組之間的關(guān)系，代數(shù)編碼又可分為兩類：

目前所使用的編碼大部分都屬于代數(shù)編碼。2.代數(shù)編碼四、抗干擾編碼的基本原理(1)分組碼信息序列…

…編碼序列…

…方法將信息序列按k位一組分割后，

進(jìn)行代數(shù)編碼，從而對應(yīng)到長度為n(

>

k)的一個碼字；此時，分組碼又稱為

(

)碼。n

,k每一個信息碼組獨(dú)立地2.代數(shù)編碼四、抗干擾編碼的基本原理(1)分組碼特點(diǎn)分組碼中的各個碼組之間沒有關(guān)聯(lián)；當(dāng)前輸入的信息碼組有關(guān)。顯然，一個()分組碼的許用碼字共有個；

n

,k系統(tǒng)碼如果在一個()分組碼的碼字中，信息碼元安排在n

,k前k

位，監(jiān)督碼元安排在后位，組碼為系統(tǒng)碼(或

組織碼)；否則稱為非系統(tǒng)碼。而禁用碼字則有

個。即輸出的碼組僅與則稱這種分

2.代數(shù)編碼四、抗干擾編碼的基本原理(2)卷積碼方法將信息序列按位一組分割后，

前面?zhèn)€

信息碼組

一起進(jìn)行代數(shù)運(yùn)算，

與當(dāng)前信息

碼

組

對應(yīng)的一

個長

度

為

的碼字；此時，卷積碼又稱為碼。信息序列………編碼序列……m

組每一個信息碼組和它從而得到2.代數(shù)編碼四、抗干擾編碼的基本原理特點(diǎn)卷積碼中的各個碼組之間是相互關(guān)聯(lián)的；不僅與當(dāng)前輸入的信息碼組有關(guān)系，而且與前面輸入的顯然，對于同樣的一個信息碼組，由于其前面輸入的信息碼組不一樣，因而所對應(yīng)的碼字也會不一樣。(2)卷積碼若干個信息碼組有關(guān)系。因此，一個卷積碼的許用碼字的個數(shù)可能高達(dá)個。即輸出的碼組2.代數(shù)編碼四、抗干擾編碼的基本原理約束長度顯然，當(dāng)時，卷積碼就是分組碼。(2)卷積碼對于一個卷積碼，(1)稱m

為編碼器的約束長度或者編碼約束長度，它反映了卷積碼中相互制約的碼組個數(shù)；它反映了卷積碼中相互制約的碼元個數(shù)。(2)稱

為

卷

積

碼的約束長

度，五、抗干擾編碼的分類1.根據(jù)用途的不同進(jìn)行分類

檢錯碼單純地用于檢測錯誤。

采用檢錯碼的通訊系統(tǒng)要有反饋信道，到的消息有錯誤時，通過反饋信道要求重發(fā)。適用于“一站發(fā)一站收”的情況。糾錯碼自動糾正差錯。根據(jù)某種糾錯原則直接糾錯，不需要反饋信道。適用于“一站發(fā)多站收(即群發(fā))”的情況。當(dāng)發(fā)現(xiàn)收五、抗干擾編碼的分類2.根據(jù)干擾性質(zhì)的不同進(jìn)行分類