【導(dǎo)讀】擾的影響，系統(tǒng)輸出的數(shù)字信息不可避免地會(huì)出現(xiàn)差錯(cuò)。因此，為了保證通信內(nèi)容。為了降低誤碼率，常用的方法有兩種：一種是降低數(shù)字信道本身引起的誤碼，措施，使用信道編碼。在許多情況下，信道的改善是不可能的或者是不經(jīng)濟(jì)的，這。時(shí)只能采用信道編碼方法。因此實(shí)現(xiàn)信道編碼方法具有重要的意義。信道編碼的本質(zhì)是增加通信的可靠性，或者說(shuō)增加整個(gè)系統(tǒng)的抗干擾。對(duì)信道編碼有下列要求：：要求對(duì)所傳消息的內(nèi)容不加任何限制；2.加一些碼，要求加入最少的比特?cái)?shù)而得到最大的利益；。減少發(fā)生差錯(cuò)的可能性；二是增加糾錯(cuò)能力，使得即便出現(xiàn)差錯(cuò)，也能

　　

【正文】 沒(méi)有反饋通道。 誤碼控制的基本原理 為了能判斷傳送的信息是否有誤，可以在傳送時(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： 00” ，則無(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ò)是可以做到的。 誤碼控制編碼的分類 隨著數(shù)字通信技術(shù)的發(fā)展，研究開(kāi)發(fā)了各種誤碼控制編碼方案，各自建立在不同的數(shù)學(xué)模型基礎(chǔ)上，并具有 不同的檢錯(cuò)與糾錯(cuò)特性，可以從不同的角度對(duì)誤碼控制編碼進(jìn)行分類。 按照誤碼控制的不同功能，可分為檢錯(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)描述，就稱為非線性碼。 糾錯(cuò)檢錯(cuò)的基本原理 13 按照信息碼元與監(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í)選用幾種誤碼控制編碼方式。以下，以線性分組碼為例，對(duì)幾種簡(jiǎn)單的編碼方式進(jìn)行介紹。 有關(guān)誤碼控制編碼的基本概念 (1)信息碼元與監(jiān)督碼元 信息碼元又稱信息序列或信息位，這是發(fā)端由信源編碼后得到的被傳送的信息數(shù)據(jù)比特，通常以 k 表示。由信息碼元組成的信息組為： M=(mk1,mk2…m 0) 在二元碼情況下，每個(gè)信息碼元 m 的取值只有 0 或 1，故總的信息碼組數(shù)共有 個(gè)，即不同信息碼元取值的組合共有 組。 監(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)為 2n，即為 2k+r 。其中被傳送的信息碼組有 2k個(gè)，通常稱為許用碼組；其余的碼組共有個(gè) (2n2k)，不傳送，稱為禁用碼組。發(fā)端誤碼控制編碼的任務(wù)正是尋求某種規(guī)則從總碼組 (2n)中選出許用碼組；而收端譯碼的任務(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)稱碼重。兩 糾錯(cuò)檢錯(cuò)的基本原理 14 個(gè)碼組對(duì)應(yīng)位置上取值不同 (1 或 0)的位數(shù)，稱為碼組的距離，簡(jiǎn)稱碼距，又稱漢明距離，通常用 d表示。例如： 000 與 101 之間碼距 d=2； 000 與 111 之間碼距 d=3。對(duì)于 (n,k)碼，許用碼組為 個(gè)，各碼組之間距離最小值稱為最小碼距，通常用 d0表示。碼距又稱漢明距。 最小碼距 d0 的大小與信道編碼的檢糾錯(cuò)能力密切相關(guān)。以下舉 例說(shuō)明分組編碼的最小碼距與檢糾錯(cuò)能力的關(guān)系。 設(shè)有兩個(gè)信息 A 和 B，可用 1比特表示，即 0 表示 A， 1表示 B，碼距 d0=1。如果直接傳送信息碼，就沒(méi)有檢糾錯(cuò)能力，無(wú)論由 1 錯(cuò)為 0，或由 0 錯(cuò)為 1，收端都無(wú)法判斷其錯(cuò)否，更不能糾正，因?yàn)樗鼈兌际呛戏ǖ男畔⒋a (許用碼 )。這可用圖 41來(lái)說(shuō)明。由圖中看出， A 與 B 之間最小碼距為 1，只要發(fā)生一位誤碼就會(huì)變成另一個(gè)許用碼，無(wú)法檢糾其錯(cuò)誤。 如果對(duì)這兩個(gè)信息 A和 B經(jīng)過(guò)信道編碼，增加 1比特監(jiān)督碼元，得到 (2， 1)碼組，即： n= k= r=nk=1，就具有檢錯(cuò)能力，由圖 4－ 3來(lái)說(shuō) 明。 由于 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)的可能性 (或概率 )是相同的。由圖 4－ 3 中又可看出，如果產(chǎn)生二位錯(cuò)碼，即 00 錯(cuò)為 11，或 11錯(cuò)為 00，結(jié)果將從一個(gè)許用碼組變成另一個(gè)許用碼組，收端就無(wú)法判斷其錯(cuò)否。通常用 e表示檢錯(cuò)能力 (位數(shù) )，用 t 表示糾錯(cuò)能力 (位數(shù) )。由上述分析可知，當(dāng) d0=2的情況下，碼組的檢錯(cuò)能力 e=1，糾錯(cuò)能力 t=0。 為了提高檢糾錯(cuò)能力，可對(duì)上述二個(gè)信息 A和 B經(jīng)過(guò)信道編碼增加 2比特監(jiān)督碼元，得到 (3， 1)碼組，即 n= k= r=n－ k=2，總的碼組數(shù)為 2n=23=8，由圖 43來(lái)說(shuō)明其檢糾錯(cuò)能力。 信道編碼后，許用碼組之間的最小碼距 d0越大，檢糾錯(cuò)的能力就越高。此例中由于 k=1,2k=21=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，由圖中 糾錯(cuò)檢錯(cuò)的基本原理 15 黑點(diǎn)代表， A 與 B之間的碼距 d0=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)生，即 110 或 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) 滿足： d0≥e ＋ 1； ② 在一個(gè)碼組內(nèi)為了糾正 t 個(gè)誤碼，要求最小碼距應(yīng)滿足： d0≥2t ＋ 1； ③ 在一個(gè)碼組內(nèi)為了糾正 t 個(gè)誤碼，同時(shí)能檢測(cè) e 個(gè)誤碼 (e＞ t)，要求最小碼距應(yīng)滿足： d0≥e ＋ t＋ 1。 糾錯(cuò)編碼方式簡(jiǎn)介 奇偶監(jiān)督碼 奇偶 校驗(yàn)碼也稱奇偶監(jiān)督碼，它是一種最簡(jiǎn)單的線性分組檢錯(cuò)編碼方式。其方法是首先把信源編碼后的信息數(shù)據(jù)流分成等長(zhǎng)碼組，在每一信息碼組之后加入一位(1比特 )監(jiān)督碼元作為奇偶檢驗(yàn)位，使得總碼長(zhǎng) n(包括信息位 k和監(jiān)督位 1)中的碼重為偶數(shù) (稱為偶校驗(yàn)碼 )或?yàn)槠鏀?shù) (稱為奇校驗(yàn)碼 )。如果 在傳輸過(guò)程中任何一個(gè)碼組發(fā)生一位 (或奇數(shù)位 )錯(cuò)誤，則收到的碼組必然不再符合奇偶校驗(yàn)的規(guī)律，因此可以發(fā)現(xiàn)誤碼。奇校驗(yàn)和偶校驗(yàn)兩者具有完全相同的工作原理和檢錯(cuò)能力，原則上采用任一種都是可以的。 由于每?jī)蓚€(gè) 1的模 2相加為 0，故利用模 2加法可以判斷一個(gè)碼組中碼重是奇數(shù)或是偶數(shù)。模 2加法等同于 “ 異或 ” 運(yùn)算?，F(xiàn)以偶監(jiān)督為例。 對(duì)于偶校驗(yàn)，應(yīng)滿足 ， 故監(jiān)督位碼元 c0可由下式求出： （ 41） 不難理解，這種奇偶校驗(yàn)編碼只能檢出單個(gè)或奇數(shù)個(gè)誤碼，而無(wú)法檢知偶數(shù)個(gè) 糾錯(cuò)檢錯(cuò)的基本原理 16 誤碼，對(duì)于連續(xù)多位的突發(fā)性誤碼也不能檢知，故檢錯(cuò)能力有限，另外，該編碼后碼組的最小碼距為 d0=2，故沒(méi)有糾錯(cuò)碼能力。 奇偶監(jiān)督碼常用于反饋糾錯(cuò) 法。 行列監(jiān)督碼 行列 監(jiān)督碼是二維的奇偶監(jiān)督碼，又稱為矩陣碼，這種碼可以克服奇偶監(jiān)督碼不能發(fā)現(xiàn)偶數(shù)個(gè)差錯(cuò)的缺點(diǎn)，并且是一種用以糾正突發(fā)差錯(cuò)的簡(jiǎn)單糾正編碼。 其基本原理與簡(jiǎn)單的奇偶監(jiān)督碼相似，不同的是每個(gè)碼元要受到縱和橫的兩次監(jiān)督。具體編碼方法如下：將若干個(gè)所要傳送的碼組編成一個(gè)矩陣，矩陣中 每一行為一碼組，每行的最后加上一個(gè)監(jiān)督碼元，進(jìn)行奇偶監(jiān)督，矩陣中的每一列則由不同碼組相同位置的碼元組成，在每列最后也加上一個(gè)監(jiān)督碼元，進(jìn)行奇偶監(jiān)督。如果用 表示信息位，由矩陣碼的結(jié)構(gòu)可如圖 4－ 5 所示，這樣，它的一致監(jiān)督關(guān)系按行及列組成。每一行每一列都是一個(gè)奇偶監(jiān)督碼，當(dāng)某一行 (或某一列 )出現(xiàn)偶數(shù)個(gè)差錯(cuò)時(shí)，該行 (或該列 )雖不能發(fā)現(xiàn)，但只要差錯(cuò)所在的列 (或行 )，沒(méi)有同時(shí)出現(xiàn)偶數(shù)個(gè)差錯(cuò)，則這種差錯(cuò)仍然可以被發(fā)現(xiàn)。矩陣碼不能發(fā)現(xiàn)的差錯(cuò)只有這樣一類：差錯(cuò)數(shù)正好為 4 倍數(shù)，而且差錯(cuò)位置正好構(gòu)成矩形的四個(gè)角，如圖 4－ 5中所 示有的差錯(cuò)情況。因此，矩陣碼發(fā)現(xiàn)錯(cuò)碼的能力是十分強(qiáng)的，它的編碼效率當(dāng)然比奇偶監(jiān)督碼要低 恒比碼 恒比碼又稱為定比碼。在恒比碼中，每個(gè)碼組 “1” 和 “0” 都保持固定的比例，故得此名。這種碼在檢測(cè)時(shí)，只要計(jì)算接收到的碼組中 “1” 的數(shù)目是否對(duì)就知道有無(wú)錯(cuò)誤。在我國(guó)用電傳機(jī)傳輸漢字時(shí)，只使用阿拉伯?dāng)?shù)字代表漢字。這時(shí)采用的所謂 “ 保護(hù)電碼 ” 就是 “3 ∶ 2” 或稱 “5 中取 3” 的恒比碼，即每個(gè)碼組的長(zhǎng)度為 5，其中 “1” 的個(gè)數(shù)總是 3，而 “0” 的個(gè)數(shù)總是 2。如表 41所示。 表 41 數(shù)字字符 普通的五單位碼 恒比碼 1 2 3 4 5 11101 11001 10000 01010 00001 01011 11001 10110 11010 00111 6 7 8 9 0 10101 11100 01100 00011 01101 10101 11100 01110 10011 01101 糾錯(cuò)檢錯(cuò)的基本原理 17 本來(lái)以 5 位碼元組成的碼組總共可以有 25=32 種，而恒比碼規(guī)定只有確切地含有 3 個(gè) “1” ， 2 個(gè) “0” 的那些碼組為準(zhǔn)用碼組，而有 3 個(gè) “1” ， 2 個(gè) “0” 的 5位碼組共有多少 ？ 這是 “5 中取 3” 求組合的算法，組合數(shù)為 35 10c? ， 一般情況下，從 “n 中取 m”(m ＜ n)恒比碼的碼組數(shù)為： ? ?!!!mn nC m n m? ? 由此可以看出，恒比碼實(shí)際上是 n 個(gè)碼元傳送 比特信息，例如上述 “3 ∶2” 即 “5 中取 2” 恒比碼，用 5 位碼只傳 10 種信息。每個(gè)碼組的信息量為，有 = 作為代價(jià)付出。 恒比碼適用于傳輸字母和符號(hào) 。 漢明碼 漢明碼 屬于線性分組編碼方式，大多數(shù)分組碼屬于線性編碼，其基本原理是，使信息碼元與監(jiān)督碼元通過(guò)線性方程式聯(lián)系起來(lái)。線性碼建立在代數(shù)學(xué)群論的 基礎(chǔ)上，各許用碼組的集合構(gòu)成代數(shù)學(xué)中的群，故又稱為群碼。 校驗(yàn)子和監(jiān)督關(guān)系式 我們先回顧下按式（ 41）條件構(gòu)成的偶數(shù)監(jiān)督碼。由于我們使用了一位監(jiān)督碼 c0，它就能和信息碼 一起構(gòu)成一個(gè)代數(shù)式，在接收端解碼時(shí)，我們實(shí)際上是計(jì)算： (4－ 3) 若 s=0，就認(rèn)為無(wú) 錯(cuò) 碼。若 s=1，就認(rèn)為有錯(cuò)碼。上式就是一致監(jiān)督關(guān)系式。 S稱為 “ 校驗(yàn)子 ” 。由于校驗(yàn)子 S 的取值只有這樣兩種，它就只能代表有錯(cuò)和無(wú)錯(cuò)兩種信息，而不能指出錯(cuò)碼的位置。我們不難推想， 如監(jiān)督位增加一位，變成兩位，則能增加一個(gè)類似于式 (4－ 3)的監(jiān)督關(guān)系式。兩個(gè)校驗(yàn)子的可能值有 4種組合 00，01， 10， 11。故能表示 4種不同的信息 ，其中一種表示無(wú)錯(cuò)，其余三種就有可能用來(lái)指示一位錯(cuò)碼的 3 種不同位置。同理， r 個(gè)監(jiān)督關(guān)系式能指示一位錯(cuò)碼的 （ 2r1）個(gè)可能位置。 一般說(shuō)來(lái)，若碼長(zhǎng)為 n，信息碼為 k，則監(jiān)督碼數(shù) r=nk。若希望用 r個(gè)監(jiān)督碼構(gòu)造出 r 個(gè)監(jiān)督關(guān)系式來(lái)指示一位錯(cuò)碼的 n種可能位置，則要求： (4－ 4) 下面通過(guò) 一個(gè)例子來(lái)說(shuō)明如何具體構(gòu)造這些監(jiān)督關(guān)系式。 設(shè)分組碼 (n、 k)中 k=4，為了能糾正一位錯(cuò)碼，按式 (4－ 4)可知，要求監(jiān)督碼數(shù) r≥3 ，現(xiàn)取 r=3，則 n=k+r=4+3=7，這是一種 ( 4)分組碼。我們用 糾錯(cuò)檢錯(cuò)的基本原理 18 表示這 7 個(gè)碼元， ，表示三個(gè)監(jiān)督關(guān)系式中的校驗(yàn)子，則 的值與錯(cuò)碼位置的對(duì)應(yīng)關(guān)系可以規(guī)定如表 42， (當(dāng)然也可以規(guī)定成另一種對(duì)應(yīng)關(guān)系，這不影響討論一般性 )。 按表 42的規(guī)定，僅當(dāng)有一個(gè)錯(cuò)碼位置在 時(shí)，校驗(yàn)子 s1 為 1，否則s1 為 0，這就意味著 四個(gè)碼元構(gòu)成偶數(shù)監(jiān)督關(guān)系： 表 42 錯(cuò)碼位置 錯(cuò)碼位 置 001 101 010 110 100 111 011 000 無(wú)錯(cuò)碼 同理， 構(gòu)成偶數(shù)監(jiān)督關(guān)系： 以及 構(gòu)成偶數(shù)監(jiān)督關(guān)系： （ 1） 監(jiān)督碼的確定 在發(fā)送端編碼時(shí)，信息碼 的值決定于輸入信號(hào)，是隨機(jī)的。而監(jiān)督碼 則應(yīng)根據(jù)信息碼的取值按監(jiān)督關(guān)系式?jīng)Q定。即監(jiān)督碼的取值應(yīng)使上三式中 的值為 0，表示編成的碼組中無(wú)錯(cuò)碼： 由上式移項(xiàng)解出監(jiān)督碼： (在模 2 加法中，移項(xiàng)后沒(méi)有負(fù)號(hào) ) 糾錯(cuò)檢錯(cuò)的基本原理 19 已知信息碼后，直接按上式可算出監(jiān)督碼，計(jì)算結(jié)果得出 16 個(gè)碼組列于表 43 中。 表 43 信 息碼 監(jiān)督碼 信息碼 監(jiān)督碼 0000 000 1000 111 0001 011 1001 100 0010 101 1010 010 0011 110 1011 001 0100 110 1100 001 0101 101 1101 010 0110 011 1110 100 0111 000 1111 111 （ 2） 解碼過(guò)程 接收端收到每個(gè)碼組后，按下述順序解碼。先按式 (43)～ (4－ 6)計(jì)算出c0,a3,a4, 42 判斷錯(cuò)誤情況。例如，若接收碼組為 0000011，按式 (4－4)～ (4－ 6)計(jì)算得： s1=0,s2=1,s3=1，由于 s1s2s3=011，查表 42可知有一錯(cuò)碼為a3。 （ 3） 漢明碼的效率 漢明碼的編碼效率 η=1 r/n 當(dāng) n 很大時(shí)，效率是很高的 。 循環(huán)碼（ CRC） （ 1） 循環(huán)碼是一種重要的線性碼，它有三個(gè)主要數(shù)學(xué)特征： ，即循環(huán)碼中任一碼組循環(huán)一位 (將最右端的碼移至左端 )以后，仍為該碼中的一個(gè)碼組。 (模 2)必定為該碼組集合中的一個(gè)碼組。 ，各碼元之間還存在一個(gè)循環(huán)依賴關(guān) 系， b 代表碼元，則有 （ 2） 用多項(xiàng)式碼作為檢驗(yàn)碼的編解碼過(guò)程 糾錯(cuò)檢錯(cuò)的基本原理 20 用多項(xiàng)式碼作為檢驗(yàn)碼時(shí)，發(fā)送器和接收器必須具有相同的生成多項(xiàng)式(GeneratorPolynomial)G(x)，其最高、最低項(xiàng)系數(shù)必須為 1。 CRC 編碼過(guò)程是將要發(fā)送的二進(jìn)制序列看作是多項(xiàng)式的系數(shù)，除以生成多項(xiàng)式，然后把余數(shù)掛在原多項(xiàng)式之后。 CRC 譯碼過(guò)程是接收方用同一生成多項(xiàng)式除以接收到的 CRC 編碼，若余數(shù)為零，則傳輸無(wú)錯(cuò)。 編碼譯碼方法： 令 r 為生成多項(xiàng)式 G(x)的階，將 r個(gè) “0” 附加在信息 (數(shù)據(jù) )元的低端，使其長(zhǎng)度變?yōu)?k