差錯(cuò)控制,什么是差錯(cuò)控制

差錯(cuò)控制,什么是差錯(cuò)控制

差錯(cuò)的特點(diǎn)

由于通信線路上總有噪聲存在，噪聲和有用信息中的結(jié)果，就會(huì)出現(xiàn)差錯(cuò)。

噪聲可分為兩類(lèi)，一類(lèi)是熱噪聲，另一類(lèi)是沖擊噪聲，熱噪聲引起的差錯(cuò)是一種隨機(jī)差錯(cuò)， 亦即某個(gè)碼元的出錯(cuò)具有獨(dú)立性，與前后碼元無(wú)關(guān)。

沖擊噪聲是由短暫原因造成的，例如電機(jī)的啟動(dòng)、停止，電器設(shè)備的放弧等，沖擊噪聲引起 的差錯(cuò)是成群的，其差錯(cuò)持續(xù)時(shí)間稱為突發(fā)錯(cuò)的長(zhǎng)度。

衡量信道傳輸性能的指標(biāo)之一是誤碼率PO。

PO=錯(cuò)誤接收的碼元數(shù)/接收的總碼元數(shù)

目前普通電話線路中,當(dāng)傳輸速率在600~2400bit/s時(shí)，PO在之間，對(duì)于大多數(shù)通信系統(tǒng)，PO在之間，而計(jì)算機(jī)之間的數(shù)據(jù)傳輸則要求誤碼率低于。

差錯(cuò)控制的基本方式

差錯(cuò)控制方式基本上分為兩類(lèi)，一類(lèi)稱為“反饋糾錯(cuò)”，另一類(lèi)稱為“前向糾錯(cuò)”。在這 兩類(lèi)基礎(chǔ)上又派生出一種稱為“混合糾錯(cuò)”。

(1)反饋糾錯(cuò)

這種方式在是發(fā)信端采用某種能發(fā)現(xiàn)一定程度傳輸差錯(cuò)的簡(jiǎn)單編碼方法對(duì)所傳信息進(jìn)行編碼 ，加入少量監(jiān)督碼元，在接收端則根據(jù)編碼規(guī)則收到的編碼信號(hào)進(jìn)行檢查，一量檢測(cè)出(發(fā) 現(xiàn))有錯(cuò)碼時(shí)，即向發(fā)信端發(fā)出詢問(wèn)的信號(hào)，要求重發(fā)。發(fā)信端收到詢問(wèn)信號(hào)時(shí)，立即重發(fā) 已發(fā)生傳輸差錯(cuò)的那部分發(fā)信息，直到正確收到為止。所謂發(fā)現(xiàn)差錯(cuò)是指在若干接收碼元中 知道有一個(gè)或一些是錯(cuò)的，但不一定知道錯(cuò)誤的準(zhǔn)確位置。圖6－1給出了“差錯(cuò)控制”的 示意方框圖。

(2)前向糾錯(cuò)

這種方式是發(fā)信端采用某種在解碼時(shí)能糾正一定程度傳輸差錯(cuò)的較復(fù)雜的編碼方法，使接收 端在收到信碼中不僅能發(fā)現(xiàn)錯(cuò)碼，還能夠糾正錯(cuò)碼。在圖6－1中，除去虛線所框部分就是前 向糾錯(cuò)的方框示意圖。采用前向糾錯(cuò)方式時(shí)，不需要反饋信道，也無(wú)需反復(fù)重發(fā)而延誤傳輸 時(shí)間，對(duì)實(shí)時(shí)傳輸有利，但是糾錯(cuò)設(shè)備比較復(fù)雜。

(3)混合糾錯(cuò)

混合糾錯(cuò)的方式是：少量糾錯(cuò)在接收端自動(dòng)糾正，差錯(cuò)較嚴(yán)重，超出自行糾正能力時(shí)，就向 發(fā)信端發(fā)出詢問(wèn)信號(hào)，要求重發(fā)。因此，“混合糾錯(cuò)”是“前向糾錯(cuò)”及“反饋糾錯(cuò)”兩種 方式的混合。

對(duì)于不同類(lèi)型的信道，應(yīng)采用不同的差錯(cuò)控制技術(shù)，否則就將事倍功半。

反饋糾錯(cuò)可用于雙向數(shù)據(jù)通信，前向糾錯(cuò)則用于單向數(shù)字信號(hào)的傳輸，例如廣播數(shù)字電視系統(tǒng)，因?yàn)檫@種系統(tǒng)沒(méi)有反饋通道。

誤碼控制基本原理

我們先舉一個(gè)日常生活中的實(shí)例。如果你發(fā)出一個(gè)通知：“明天14：00~16：00開(kāi)會(huì)”，但在通知過(guò)程中由于某種原因產(chǎn)生了錯(cuò)誤，變成“明天10：00~16：00開(kāi)會(huì)”。別人收到這個(gè)錯(cuò)誤通知后由于無(wú)法判斷其正確與否，就會(huì)按這個(gè)錯(cuò)誤時(shí)間去行動(dòng)。為了使收者能判斷正誤，可以在發(fā)通知內(nèi)容中增加“下午”兩個(gè)字，即改為：“明天下午14：00~16：00開(kāi)會(huì)”， 這時(shí)，如果仍錯(cuò)為：“明天下午10：00~16：00開(kāi)會(huì)”，則收到此通知后根據(jù)“下午”兩字即 可 判斷出其中“10：00”發(fā)生了錯(cuò)誤。但仍不能糾正其錯(cuò)誤，因?yàn)闊o(wú)法判斷“10：00”錯(cuò)在何處，即無(wú)法判斷原來(lái)到底是幾點(diǎn)鐘。這時(shí)，收者可以告訴發(fā)端再發(fā)一次通知，這就是檢錯(cuò)重發(fā)。為了實(shí)現(xiàn)不但能判斷正誤(檢錯(cuò))，同時(shí)還能改正錯(cuò)誤(糾錯(cuò))，可以把發(fā)的通知內(nèi)容再增 加“兩個(gè)小時(shí)”四個(gè)字，即改為：“明天下14：00~16：00兩個(gè)小時(shí)開(kāi)會(huì)”。這樣，如果其 中“14：00”錯(cuò)為“10：00”，不但能判斷出錯(cuò)誤，同時(shí)還能糾正錯(cuò)誤，因?yàn)槠渲性黾拥摹?兩個(gè)小時(shí)”四個(gè)字可以判斷出正確的時(shí)間為14：00~16：00”。

通過(guò)上例可以說(shuō)明，為了能判斷傳送的信息是否有誤，可以在傳送時(shí)增加必要的附加判斷數(shù) 據(jù)；如果又能糾正錯(cuò)誤，則需要增加更多的附加判斷數(shù)據(jù)。這些附加數(shù)據(jù) 在不發(fā)生誤碼的情況之下是完全多余的，但如果發(fā)生誤碼，即可利用被傳信息數(shù)據(jù)與附加數(shù) 據(jù)之間的特定關(guān)系來(lái)實(shí)現(xiàn)檢出錯(cuò)誤和糾正錯(cuò)誤，這就是誤碼控制編碼的基本原理。具體地說(shuō) 就是：為了使信源代碼具有檢錯(cuò)和糾錯(cuò)能力，應(yīng)當(dāng)按一定的規(guī)則在信源編碼的基礎(chǔ)上增加 一些冗余碼元(又稱監(jiān)督碼)，使這些冗余碼元與被傳送信息碼元之間建立一定的關(guān)系，發(fā)信 端完成這個(gè)任務(wù)的過(guò)程就稱為誤碼控制編碼；在收信端，根據(jù)信息碼元與監(jiān)督碼元的特定關(guān) 系，實(shí)現(xiàn)檢錯(cuò)或糾錯(cuò)，輸出原信息碼元，完成這個(gè)任務(wù)的過(guò)程就稱誤碼控制譯碼(或解碼)。 另外，無(wú)論檢錯(cuò)和糾錯(cuò)，都有一定的誤別范圍，如上例中，若開(kāi)會(huì)時(shí)間錯(cuò)為“16：00~18：0 0”，則無(wú)法實(shí)現(xiàn)檢錯(cuò)與糾錯(cuò)，因?yàn)檫@個(gè)時(shí)間也同樣滿足附加數(shù)據(jù)的約束條件，這就應(yīng)當(dāng)增 加更多的附加數(shù)據(jù)(即冗余)。我們已知，信源編碼的中心任務(wù)是消去冗余，實(shí)現(xiàn)碼率壓縮， 可是為了檢錯(cuò)與糾錯(cuò)，又不得不增加冗余，這又必然導(dǎo)致碼率增加，傳輸效率降低；顯然這 是個(gè)矛盾。我們分析誤碼控制編碼的目的，正是為了尋求較好的編碼方式，能在增加冗余不 太多的前提下來(lái)實(shí)現(xiàn)檢錯(cuò)和糾錯(cuò)。 再者，經(jīng)過(guò)信源編碼，如果傳送信道容量與信源碼率相匹配，而且 信道內(nèi)引入的噪聲較小，則誤碼率一般是很低的。例如，當(dāng)信道的信雜比超過(guò)20dB時(shí),二元 單極性碼的誤碼率低于，即誤碼率只 分之一，故通過(guò)信道編碼實(shí)現(xiàn)檢錯(cuò) 和糾錯(cuò)是可以做到的。

誤碼控制編碼的分類(lèi)

隨著數(shù)字通信技術(shù)的發(fā)展，研究開(kāi)發(fā)了各種誤碼控制編碼方案，各自建立在不同的數(shù)學(xué)模型 基礎(chǔ)上，并具有不同的檢錯(cuò)與糾錯(cuò)特性，可以從不同的角度對(duì)誤碼控制編碼進(jìn)行分類(lèi)。

按照誤碼控制的不同功能，可分為檢錯(cuò)碼、糾錯(cuò)碼和糾刪碼等。檢錯(cuò)碼僅具備識(shí)別錯(cuò)碼功能 而無(wú)糾正錯(cuò)碼功能；糾錯(cuò)碼不僅具備識(shí)別錯(cuò)碼功能，同時(shí)具備糾正錯(cuò)碼功能；糾刪碼則不僅 具備識(shí)別錯(cuò)碼和糾正錯(cuò)碼的功能，而且當(dāng)錯(cuò)碼超過(guò)糾正范圍時(shí)可把無(wú)法糾錯(cuò)的信息刪除。

按照誤碼產(chǎn)生的原因不同，可分為糾正隨機(jī)錯(cuò)誤的碼與糾正突發(fā)性錯(cuò)誤的碼。前者主要用于 產(chǎn)生獨(dú)立的局部誤碼的信道，而后者主要用于產(chǎn)生大面積的連續(xù)誤碼的情況，例如磁帶數(shù)碼 記錄中磁粉脫落而發(fā)生的信息丟失。按照信息碼元與附加的監(jiān)督碼元之間的檢驗(yàn)關(guān)系可分為線性碼與非線性碼。如果兩者呈線性 關(guān)系，即滿足一組線性方程式，就稱為線性碼；否則，兩者關(guān)系不能用線性方程式來(lái)描述， 就稱為非線性碼。

按照信息碼元與監(jiān)督附加碼元之間的約束方式之不同，可以分為分組碼與卷積碼。在分組碼 中，編碼后的碼元序列每n位分為一組，其中包括k位信息碼元和r位附加監(jiān)督碼元，即n=k+r ，每組的監(jiān)督碼元僅與本組的信息碼元有關(guān)，而與其他組的信息碼元無(wú)關(guān)。卷積碼則不同， 雖然編碼后碼元序列也劃分為碼組，但每組的監(jiān)督碼元不但與本組的信息碼元有關(guān)，而且與前 面碼組的信息碼元也有約束關(guān)系。

按照信息碼元在編碼之后是否保持原來(lái)的形式不變，又可分為系統(tǒng)碼與非系統(tǒng)碼。在系統(tǒng)碼中，編碼后的信息碼元序列保持原樣不變，而在非系統(tǒng)碼中，信息碼元會(huì)改變其原有的信號(hào)序列。由于原有碼位發(fā)生了變化，使譯碼電路更為復(fù)雜，故較少選用。

根據(jù)編碼過(guò)程中所選用的數(shù)字函數(shù)式或信息碼元特性的不同，又包括多種編碼方式。對(duì) 于某種具體的數(shù)字設(shè)備，為了提高檢錯(cuò)、糾錯(cuò)能力，通常同時(shí)選用幾種誤碼控制編碼方式。 在表6－1中，列出了常見(jiàn)的幾種誤碼控制編碼方式。以下，以線性分組碼為例，對(duì)幾種簡(jiǎn)單 的編碼方式進(jìn)行介紹。

有關(guān)誤碼控制編碼的幾個(gè)基本概念

(1)信息碼元與監(jiān)督碼元

信息碼元又稱信息序列或信息位，這是發(fā)端由信源編碼后得到的被傳送的信息數(shù)據(jù)比特，通 常以k表示。由信息碼元組成的信息組為：

在二元碼情況下，每個(gè)信息碼元m的取值只有0或1.監(jiān)督碼元又稱監(jiān)督位或附加數(shù)據(jù)比特，這是為了檢糾錯(cuò)碼而在信道編碼時(shí)加入的判斷數(shù)據(jù)位 。通常以r表示，即為：

n=k+r或r=n－k

經(jīng)過(guò)分組編碼后的碼又稱為(n,k)碼，即表示總碼長(zhǎng)為n位，其中信息碼長(zhǎng)(碼元數(shù))為k位， 監(jiān)督碼長(zhǎng)(碼元數(shù))為r=n－k。通常稱其為長(zhǎng)為n的碼字(或碼組、碼矢)。

(2)許用碼組與禁用碼組

信道編碼后的總碼長(zhǎng)為n，總的碼組數(shù)應(yīng)為，即為。其中被傳送的信息碼組 有個(gè)，通常稱為許用碼組；其余的碼組共有()個(gè)，不傳送，稱為禁用碼組。 發(fā)端誤碼控制編碼的任務(wù)正是尋求某種規(guī)則從總碼組()中選出許用碼組；而收端譯碼的 任務(wù)則是利用相應(yīng)的規(guī)則來(lái)判斷及校正收到的碼字符合許用碼組。通常又把信息碼元數(shù)目k 與編碼后的總碼元數(shù)目(碼組長(zhǎng)度)n之比稱為信道編碼的編碼效率或編碼速率，表示為：

R=k/n=k/k+r

這是衡量糾錯(cuò)碼性能的一個(gè)重要指標(biāo)，一般情況下，監(jiān)督位越多(即r越大)，檢糾錯(cuò)能力越 強(qiáng)，但相應(yīng)的編碼效率也隨之降低了。

(3)碼重與碼距

在分組編碼后，每個(gè)碼組中碼元為“1”的數(shù)目稱為碼的重量，簡(jiǎn)稱碼重。兩個(gè)碼組對(duì)應(yīng)位置上取值不同(1或0)的位數(shù)，稱為碼組的距離，簡(jiǎn)稱碼距，又稱漢明距離，通常用d表示。 例如：000與101之間碼距d=2；000與111之間碼距d=3。對(duì)于(n,k)碼，許用碼組為個(gè)， 各碼組之間距離最小值稱為最小碼距，通常用表示。碼距又稱漢明距。

最小碼距的大小與信道編碼的檢糾錯(cuò)能力密切相關(guān)。以下舉例說(shuō)明分組編碼的最小碼距 與檢糾錯(cuò)能力的關(guān)系。

設(shè)有兩個(gè)信息A和B，可用1比特表示，即0表示A，1表示B，碼距=1。如果直接傳送信息 碼，就沒(méi)有檢糾錯(cuò)能力，無(wú)論由1錯(cuò)為0，或由0錯(cuò)為1，收端都無(wú)法判斷其錯(cuò)否，更不能糾正 ，因?yàn)樗鼈兌际呛戏ǖ男畔⒋a(許用碼)。這可用圖6－2來(lái)說(shuō)明。由圖中看出，A與B之間最小 碼距為1，只要發(fā)生一位誤碼就會(huì)變成另一個(gè)許用碼，無(wú)法檢糾其錯(cuò)誤。

如果對(duì)這兩個(gè)信息A和B經(jīng)過(guò)信道編碼，增加1比特監(jiān)督碼元，得到(2，1)碼組，即：n=2、k= 1、r=n-k=1，就具有檢錯(cuò)能力。

由于n=2，故總碼組數(shù)為，以由于k=1，故許用碼組數(shù)，其余為禁用碼組。由圖中看出，許用碼組有兩種選 擇方式，即00與11，或01與10，其結(jié)果是相同的，只是信息碼元與監(jiān)督碼元之間的約束規(guī)律 不同?，F(xiàn)采用信息碼元重復(fù)一次得到許用碼組的編碼方式，故許用碼組為00表示A，11表 示B。這時(shí)A和B都具有1位檢錯(cuò)能力，因?yàn)闊o(wú)論A(00)或B(11)如果發(fā)生一位錯(cuò)碼，必將變成01 或10，這都是禁用碼組，故收端完全可以按不符合信息碼重復(fù)一次的準(zhǔn)則來(lái)判斷為誤碼。但 卻不能糾正其錯(cuò)誤，因?yàn)闊o(wú)法判斷誤碼(01或10)是A(00)錯(cuò)誤造成還是B(11)錯(cuò)誤造成，即無(wú) 法 判定原信息是A或B，或說(shuō)A與B形成誤碼(01或10)的可能性(或概率)是相同的。如果產(chǎn)生二位錯(cuò)碼，即00錯(cuò)為11，或11錯(cuò)為00，結(jié)果將從一個(gè)許用碼組變成另 一個(gè)許用碼組，收端就無(wú)法判斷其錯(cuò)否。通常用e表示檢錯(cuò)能力(位數(shù))，用t表示糾錯(cuò)能力( 位數(shù))。由上述分析可知，當(dāng)=2的情況下，碼組的檢錯(cuò)能力e=1，糾錯(cuò)能力t=0。

為了提高檢糾錯(cuò)能力，可對(duì)上述二個(gè)信息A和B經(jīng)過(guò)信道編碼增加2比特監(jiān)督碼元，得到(3，1 )碼組，即n=3、k=1、r=n－k=2，總的碼組數(shù)為，由圖6－4來(lái)說(shuō)明其檢 糾錯(cuò)能力。

信道編碼后，許用碼組之間的最小碼距d0越大，檢糾錯(cuò)的能力就越高。此例中由于k=1,=2，故只有2個(gè)許用碼組，其余6個(gè)為禁用碼組。由圖中可以看出，滿足 最 小碼距為最大的條件共有4種選擇方式，即為(000與111)、(001與110)、(010和101)、(011 與100)，這四種選擇方式具有相同的最小碼距，故其抗干擾能力或檢糾錯(cuò)能力也相同。為了 編碼直接、簡(jiǎn)便，選擇二重重復(fù)編碼方式，即按信息碼元重復(fù)二次的規(guī)律來(lái)產(chǎn)生許用碼組， 編碼結(jié)果為000表示A，111表示B，由圖中黑點(diǎn)代表，A與B之間的碼距=3。

由圖中可以看出，這時(shí)的兩個(gè)許用碼組A或B都具有一位糾錯(cuò)能力。例如，當(dāng)信息A(000)產(chǎn)生 一位錯(cuò)誤時(shí)，將有三種誤碼形式，即001或010或100，這些都是禁用碼組，可確定是誤碼。而且這三個(gè)誤碼距離最近的許用碼組的000，與另一個(gè)許用碼組111的距離較遠(yuǎn)，根據(jù)誤碼 少的概率大于誤碼多的概率的規(guī)律，可以判定原來(lái)的正確碼組是000，只要把誤碼中的1改 為0即可得到糾正。同理，如果信息B(111)產(chǎn)生一位錯(cuò)誤時(shí)，則有另三種誤碼可能產(chǎn)生，即1 10或101 或011，根據(jù)同樣道理可以判定原來(lái)的正確碼組是111，并能糾正錯(cuò)誤。但是，如果 信息A(000)或信息B(111)產(chǎn)生兩位錯(cuò)誤時(shí)，雖然能根據(jù)出現(xiàn)禁用碼組識(shí)別其錯(cuò)誤，但糾錯(cuò)時(shí) 卻會(huì)作出錯(cuò)誤的糾正造成誤糾錯(cuò)。如果信息A(000)或信息B(111)產(chǎn)生三位錯(cuò)誤時(shí)，將從一個(gè) 許 用碼組A(或B)變成了另一個(gè)許用碼組B(或A)，這時(shí)既檢不出錯(cuò)，更不會(huì)糾錯(cuò)了，因?yàn)檎`碼已 成為合法組合的許用碼組，譯碼后必然產(chǎn)生錯(cuò)誤。

綜上所述，可以得到分組編碼最小碼距與檢糾錯(cuò)能力的關(guān)系有以下三條結(jié)論：

①在一個(gè)碼組內(nèi)為了檢測(cè)e個(gè)誤碼，要求最小碼距應(yīng)滿足：

≥e＋1

②在一個(gè)碼組內(nèi)為了糾正t個(gè)誤碼，要求最小碼距應(yīng)滿足：

≥2t＋1

③在一個(gè)碼組內(nèi)為了糾正t個(gè)誤碼，同時(shí)能檢測(cè)e個(gè)誤碼(e＞t)，要求最小碼距應(yīng)滿足：

≥e＋t＋1