差錯(cuò)檢測(cè)與控制

第一頁(yè)，共七十四頁(yè)，2022年，8月28日第十章差錯(cuò)控制為什么要進(jìn)行差錯(cuò)控制差錯(cuò)控制的基本方法差錯(cuò)控制編碼的基本概念常用的簡(jiǎn)單編碼常用的線性分組碼第二頁(yè)，共七十四頁(yè)，2022年，8月28日（1）差錯(cuò)產(chǎn)生的原因數(shù)據(jù)通信系統(tǒng)的基本任務(wù)是高效率而無差錯(cuò)地傳送數(shù)據(jù)。數(shù)據(jù)信號(hào)在通信線路中傳輸時(shí)，難免受到來自信道內(nèi)部和外部的干擾，從而引起信號(hào)的失真，導(dǎo)致數(shù)據(jù)傳輸錯(cuò)誤。傳輸出錯(cuò)的原因：一是信道的加性噪聲；二是由于傳輸總特性（包括收、發(fā)濾波器和信道的特性）不理想引起的碼間串?dāng)_。噪聲是影響數(shù)據(jù)傳輸質(zhì)量的主要因素。根據(jù)產(chǎn)生的原因可以將噪聲分為四類：熱噪聲、交調(diào)噪聲、串音和脈沖噪聲四類。第三頁(yè)，共七十四頁(yè)，2022年，8月28日（2）噪聲的類型熱噪聲是由帶電粒子在導(dǎo)電介質(zhì)中的布朗運(yùn)動(dòng)引起的，它存在于任何工作在絕對(duì)零度以上的電路或系統(tǒng)中。熱噪聲屬于高斯白噪聲，其概率密度函數(shù)滿足正態(tài)分布統(tǒng)計(jì)特性，同時(shí)它的功率譜密度函數(shù)是均勻分布的（常數(shù)）。熱噪聲的特點(diǎn)是：時(shí)刻存在、不可排除、幅度較小、強(qiáng)度與頻率無關(guān)，但頻譜很寬，是一類隨機(jī)的噪聲。第四頁(yè)，共七十四頁(yè)，2022年，8月28日噪聲的類型交調(diào)噪聲是一種附加的頻率干擾。由于通信系統(tǒng)的非線性，將導(dǎo)致進(jìn)入通信系統(tǒng)的不同頻率的信號(hào)在系統(tǒng)的輸出端產(chǎn)生這些頻率之間的差頻信號(hào)或倍頻信號(hào)及其組合，這就是交調(diào)噪聲。對(duì)于交調(diào)噪聲可以通過適當(dāng)?shù)恼{(diào)制技術(shù)，人為地校正系統(tǒng)的非線性部分得到補(bǔ)償。第五頁(yè)，共七十四頁(yè)，2022年，8月28日噪聲的類型串音是一個(gè)通路的信號(hào)在相鄰的另一個(gè)通路引起的干擾現(xiàn)象。這是由于信號(hào)線路之間的電磁感應(yīng)引起的有害耦合。為了消除線路之間的有害耦合，可以將每一對(duì)線擰成一定扭絞節(jié)距的線纜。第六頁(yè)，共七十四頁(yè)，2022年，8月28日噪聲的類型脈沖噪聲是由于電火花或其他原因造成的突發(fā)振幅很大、持續(xù)時(shí)間比間隔時(shí)間短得多的離散脈沖耦合到信號(hào)通路中的干擾。脈沖噪聲也稱為沖擊噪聲，它將引起一連串的數(shù)據(jù)比特出錯(cuò)，它是數(shù)據(jù)傳輸差錯(cuò)的主要根源。脈沖噪聲產(chǎn)生的干擾很難消除，只能采用差錯(cuò)控制的方法來實(shí)現(xiàn)可靠傳輸。第七頁(yè)，共七十四頁(yè)，2022年，8月28日（3）差錯(cuò)的類型隨機(jī)差錯(cuò)指數(shù)據(jù)單元中的單比特差錯(cuò)。它通常由傳輸信道的熱噪聲引起。突發(fā)差錯(cuò)指數(shù)據(jù)單元中的兩個(gè)或兩個(gè)以上的比特發(fā)生成串密集性的差錯(cuò)，第一個(gè)錯(cuò)誤比特到最后一個(gè)錯(cuò)誤比特之間的位數(shù)稱為突發(fā)長(zhǎng)度。沖擊噪聲持續(xù)的時(shí)間通常大于數(shù)據(jù)傳輸中每比特的發(fā)送時(shí)間，因而會(huì)引起相鄰的多個(gè)數(shù)據(jù)位出錯(cuò)，從而導(dǎo)致突發(fā)差錯(cuò)。第八頁(yè)，共七十四頁(yè)，2022年，8月28日有差錯(cuò)的信道類型按照噪聲或干擾的變化規(guī)律，可把信道分為三類：隨機(jī)信道：

恒參高斯白噪聲信道是典型的隨機(jī)信道，其中差錯(cuò)的出現(xiàn)是隨機(jī)的，而且錯(cuò)誤之間是統(tǒng)計(jì)獨(dú)立的。突發(fā)信道：

具有脈沖干擾的信道，是典型的突發(fā)信道。錯(cuò)誤是成串成群出現(xiàn)的，即在短時(shí)間內(nèi)出現(xiàn)大量錯(cuò)誤?；旌闲诺溃?/p>

短波信道和對(duì)流層散射信道是混合信道的典型例子，隨機(jī)差錯(cuò)和成串的突發(fā)差錯(cuò)都占有相當(dāng)比例。第九頁(yè)，共七十四頁(yè)，2022年，8月28日（4）如何解決傳輸差錯(cuò)問題提高物理信道的質(zhì)量，盡量避免和減少差錯(cuò)：采用電纜屏蔽措施和適當(dāng)?shù)恼{(diào)制解調(diào)方法設(shè)置中繼設(shè)備對(duì)信號(hào)進(jìn)行整理再生和放大加大發(fā)射功率，降低接收設(shè)備本身的噪聲，以提高信噪比提高數(shù)據(jù)的健壯性，有效地進(jìn)行檢錯(cuò)和糾錯(cuò)：采用信道編碼技術(shù)，為數(shù)據(jù)信息增加冗余編碼，形成抗干擾編碼，使接收方能進(jìn)行檢錯(cuò)或糾錯(cuò)配合適當(dāng)?shù)牟铄e(cuò)控制方法進(jìn)行檢錯(cuò)或糾錯(cuò)。第十頁(yè)，共七十四頁(yè)，2022年，8月28日第十章差錯(cuò)控制為什么要進(jìn)行差錯(cuò)控制差錯(cuò)控制的基本方法差錯(cuò)控制編碼的基本概念常用的簡(jiǎn)單編碼常用的線性分組碼第十一頁(yè)，共七十四頁(yè)，2022年，8月28日差錯(cuò)控制的基本工作方式自動(dòng)反饋重發(fā)方式ARQ發(fā)端發(fā)送檢錯(cuò)碼，收端收到信碼后能夠檢查出錯(cuò)誤。前向糾錯(cuò)方式FEC發(fā)端發(fā)送能夠糾正錯(cuò)誤的碼，收端收到信碼后自動(dòng)地糾正傳輸中的錯(cuò)誤。混合糾錯(cuò)方式HEC是FEC和ARQ方式的結(jié)合。信息反饋方式IF是不用編碼的差錯(cuò)控制方式。第十二頁(yè)，共七十四頁(yè)，2022年，8月28日（1）自動(dòng)反饋重發(fā)ARQ

自動(dòng)反饋重發(fā)記作ARQ(AutomaticRepeatRequest)，又稱自動(dòng)請(qǐng)求重傳方式。發(fā)方按照一定的編碼規(guī)則處理待發(fā)信息，構(gòu)成具有檢錯(cuò)能力的編碼，發(fā)往傳輸信道；收方判決傳輸中無錯(cuò)誤產(chǎn)生，并通過反向信道把判決結(jié)果反饋給發(fā)方；發(fā)方根據(jù)反饋的結(jié)果決定是否執(zhí)行重傳動(dòng)作，如果接收方未正確接收，則重傳信息(出錯(cuò)重傳)在規(guī)定的時(shí)間內(nèi)，發(fā)方若未能收到應(yīng)答信號(hào)(稱為超時(shí))，則可以認(rèn)為傳輸出現(xiàn)差錯(cuò)，進(jìn)而執(zhí)行重傳動(dòng)作(超時(shí)重傳)。第十三頁(yè)，共七十四頁(yè)，2022年，8月28日主要的反饋重傳方式

反饋重傳方式的特點(diǎn)是譯碼設(shè)備簡(jiǎn)單，對(duì)突發(fā)錯(cuò)誤和信道干擾較嚴(yán)重時(shí)有效；但實(shí)時(shí)性差，主要在計(jì)算機(jī)數(shù)據(jù)通信系統(tǒng)中得到應(yīng)用。常用的反饋重傳方式有：發(fā)送-等待ARQ（停—等協(xié)議）連續(xù)發(fā)送ARQ（滑動(dòng)窗口協(xié)議）返回重傳ARQ選擇重傳ARQ發(fā)送方接收方抗干擾編碼應(yīng)答信號(hào)第十四頁(yè)，共七十四頁(yè)，2022年，8月28日（2）前向糾錯(cuò)法FEC前向糾錯(cuò)方式記作FEC(ForwordErrorCorrection)。發(fā)送方按照一定的編碼規(guī)則處理待發(fā)信息，構(gòu)成具有糾正錯(cuò)誤能力的代碼(糾錯(cuò)碼)發(fā)往傳輸信道；接收方根據(jù)編碼規(guī)則，檢查傳輸差錯(cuò)，并自動(dòng)加以糾正。其特點(diǎn)是單向傳輸，實(shí)時(shí)性好，但譯碼設(shè)備較復(fù)雜。第十五頁(yè)，共七十四頁(yè)，2022年，8月28日（3）混合糾錯(cuò)法混合糾錯(cuò)方式記作HEC(HybridErrorCorrection)是FEC和ARQ方式的結(jié)合。發(fā)方發(fā)送具有一定糾錯(cuò)能力同時(shí)又具有檢錯(cuò)能力的編碼。收方收到編碼后，檢查差錯(cuò)情況，如果錯(cuò)誤在編碼的糾錯(cuò)能力范圍以內(nèi)，則自動(dòng)糾錯(cuò)，否則經(jīng)過反饋信道請(qǐng)求發(fā)方重發(fā)。第十六頁(yè)，共七十四頁(yè)，2022年，8月28日（4）信息反饋法信息反饋法記作IRQ(InformationRepeatRequest)接收方把收到的信息代碼全部送回發(fā)送方，由發(fā)送方進(jìn)行差錯(cuò)檢驗(yàn)。發(fā)送方若發(fā)現(xiàn)傳輸差錯(cuò)，則重發(fā)信息代碼，直至不再發(fā)現(xiàn)差錯(cuò)為止。第十七頁(yè)，共七十四頁(yè)，2022年，8月28日幾種差錯(cuò)控制方法比較自動(dòng)反饋重傳法：

使用的編/解碼設(shè)施比較簡(jiǎn)單，如果信道的質(zhì)量差或干擾嚴(yán)重，則可能經(jīng)常進(jìn)入重發(fā)狀態(tài)而影響通信效率。前向糾錯(cuò)法：編/解碼相對(duì)復(fù)雜，且編碼的效率很低，但是無需專門的反饋信道。主要應(yīng)用于沒有反饋信道的場(chǎng)合，或用于線路傳播時(shí)間很長(zhǎng)、要求重發(fā)在經(jīng)濟(jì)上不切實(shí)際的的場(chǎng)合。由于形成糾錯(cuò)碼要求較多的冗余信息，當(dāng)信道質(zhì)量較好時(shí)，也影響了傳輸?shù)男省；旌霞m錯(cuò)法：編/解碼相當(dāng)復(fù)雜、且編碼的效率很低，很少被采用。信息反饋法：反饋信息量太大，傳輸效率很低，很少被采用。第十八頁(yè)，共七十四頁(yè)，2022年，8月28日第十章差錯(cuò)控制為什么要進(jìn)行差錯(cuò)控制差錯(cuò)控制的基本方法差錯(cuò)控制編碼的基本概念常用的簡(jiǎn)單編碼常用的線性分組碼第十九頁(yè)，共七十四頁(yè)，2022年，8月28日差錯(cuò)控制編碼的基本原理差錯(cuò)控制的核心技術(shù)是信道編碼技術(shù)，即采用適當(dāng)?shù)牟铄e(cuò)控制編碼來傳輸信息。差錯(cuò)控制編碼的基本思想是在被傳輸信息中增加一些冗余碼，利用附加碼元和信息碼元之間的約束關(guān)系加以校驗(yàn)，以檢測(cè)和糾正錯(cuò)誤，增加的冗余碼元就稱為監(jiān)督碼元（校驗(yàn)碼元）。第二十頁(yè)，共七十四頁(yè)，2022年，8月28日信道編碼技術(shù)對(duì)于n位的二進(jìn)制碼有N=2n種組合。如果這N種組合都用來傳輸信息，這樣構(gòu)成的編碼并不具備抗干擾能力。因?yàn)椴还苣囊晃话l(fā)生錯(cuò)誤，都會(huì)使傳輸信息出錯(cuò)。但是，若這N種組合并未完全使用，情況將會(huì)怎樣呢？第二十一頁(yè)，共七十四頁(yè)，2022年，8月28日差錯(cuò)控制編碼的抗干擾機(jī)理【例】考慮n=3的情形，3位二進(jìn)制碼有8種組合：

000、001、010、011、100、101、110、111若選用以下四個(gè)碼組表作為準(zhǔn)用碼組，其余的作為禁用碼組：

000——A 011——B 101——C 110——D則只要發(fā)生一位錯(cuò)誤，準(zhǔn)用碼組就將變成禁用碼組，接收端就能知道出錯(cuò)，但是不能糾錯(cuò)。若只用兩個(gè)碼組作為準(zhǔn)用碼組000——A、111——B，其余的作為禁用碼組，并將8個(gè)碼組分為兩個(gè)子集：

{000、001、010、100}和{011、101、110、111}

前者對(duì)應(yīng)碼組000，后者對(duì)應(yīng)碼組111。則接收端可以檢測(cè)兩位及以下的差錯(cuò)，或糾正一位的差錯(cuò)?！窘Y(jié)論】增加監(jiān)督碼元的個(gè)數(shù)可提高糾檢錯(cuò)能力。第二十二頁(yè)，共七十四頁(yè)，2022年，8月28日抗干擾編碼的理論依據(jù)香農(nóng)定理（信道編碼定理）：在有噪聲干擾的信道中，若信道容量為C，發(fā)送端發(fā)送信息時(shí)輸入信道編碼器的二進(jìn)制碼元速率為R，只要R低于C，則一定存在一種編碼方式，使數(shù)據(jù)的誤碼率Pe滿足下列條件：

Pe≤Ae-nE(R)其中，n為碼字長(zhǎng)度、A是正的系數(shù)、E是R的正實(shí)函數(shù)。第二十三頁(yè)，共七十四頁(yè)，2022年，8月28日結(jié)論P(yáng)e≤Ae-nE(R)根據(jù)香農(nóng)定理只要R低于C，則一定存在一種編碼方式，使數(shù)據(jù)的誤碼率隨著碼長(zhǎng)n的增長(zhǎng)按指數(shù)下降到任一值。如碼長(zhǎng)n及發(fā)送速率R一定，可以通過增大信道容量，使誤碼率下降。如信道容量C及發(fā)送速率R一定，可以通過增加碼長(zhǎng)，使誤碼率下降。第二十四頁(yè)，共七十四頁(yè)，2022年，8月28日碼長(zhǎng)、碼重、碼距碼長(zhǎng)——編碼碼組的長(zhǎng)度，即碼組中的碼元總位數(shù)。碼重——碼組的重量，即一個(gè)碼組中“1”碼元的數(shù)目。碼距——兩個(gè)等長(zhǎng)碼組的海明(Hamming)距離，即兩個(gè)碼組之間對(duì)應(yīng)碼位上碼元不同的數(shù)目。最小碼距——一個(gè)碼組集中任意兩個(gè)碼組之間距離的最小值。最小碼距是抗干擾編碼的一個(gè)重要參數(shù)，它是衡量編碼檢錯(cuò)、糾錯(cuò)能力的依據(jù)?！纠吭谇笆隼又?，碼組集{000、011、101、110}的最小碼距為2，而碼組集{000、111}的最小碼距為3。第二十五頁(yè)，共七十四頁(yè)，2022年，8月28日編碼的檢錯(cuò)和糾錯(cuò)能力理論證明，編碼的抗干擾能力與最小碼距密切相關(guān)：為檢查出e個(gè)錯(cuò)碼，要求最小碼距為dmin≥e+1為糾正t個(gè)錯(cuò)碼，要求最小碼距為dmin≥2t+1為糾正t個(gè)錯(cuò)碼，同時(shí)檢查出e個(gè)錯(cuò)碼，要求最小碼距為dmin≥e+t+1 (e>t)第二十六頁(yè)，共七十四頁(yè)，2022年，8月28日編碼效率用差錯(cuò)控制編碼提高通信系統(tǒng)的的可靠性，是以降低有效性為代價(jià)換來的。定義編碼效率R來衡量有效性：R=k/(k+r)其中，k是信息碼元的個(gè)數(shù)，r為校驗(yàn)碼元個(gè)數(shù)

。校驗(yàn)碼元越長(zhǎng)，編碼的檢錯(cuò)能力越強(qiáng)，編碼/解碼越復(fù)雜；附加的冗余信息在整個(gè)編碼中所占的比例越大，傳輸?shù)挠行С煞衷降?，傳輸?shù)男氏陆怠５诙唔?yè)，共七十四頁(yè)，2022年，8月28日對(duì)糾、檢錯(cuò)碼的基本要求對(duì)糾、檢錯(cuò)碼的基本要求是:檢錯(cuò)和糾錯(cuò)能力盡量強(qiáng)、編碼效率盡量高、編碼規(guī)律盡量簡(jiǎn)單。實(shí)際中要根據(jù)具體指標(biāo)要求，保證有一定的糾、檢錯(cuò)能力和編碼效率，并且易于實(shí)現(xiàn)。第二十八頁(yè)，共七十四頁(yè)，2022年，8月28日差錯(cuò)控制編碼的分類按照信息碼元和監(jiān)督碼元之間的函數(shù)關(guān)系分為：線性碼和非線性碼。前者碼元之間能滿足一組線性方程組，后者則不然。按照對(duì)信息元的處理方式分為：分組碼和卷積碼。前者的各碼元僅與本組的信息元有關(guān)；后者的碼元不僅與本組的信息元有關(guān)，而且還與前面若干組的信息元有關(guān)。按照差錯(cuò)控制編碼的用途分為：檢錯(cuò)碼和糾錯(cuò)碼。前者以檢錯(cuò)為目的，不一定能糾錯(cuò)；而后者以糾錯(cuò)為目的，一定能檢錯(cuò)。按照碼組中信息碼元在編碼前后是否相同分為：系統(tǒng)碼和非系統(tǒng)碼。第二十九頁(yè)，共七十四頁(yè)，2022年，8月28日第十章差錯(cuò)控制為什么要進(jìn)行差錯(cuò)控制差錯(cuò)控制的基本方法差錯(cuò)控制編碼的基本概念常用的簡(jiǎn)單編碼常用的線性分組碼第三十頁(yè)，共七十四頁(yè)，2022年，8月28日常用的簡(jiǎn)單編碼奇偶校驗(yàn)碼水平奇偶校驗(yàn)（行校驗(yàn)）垂直奇偶校驗(yàn)（列校驗(yàn)）水平垂直奇偶校驗(yàn)（方陣碼）定比碼（恒比碼）第三十一頁(yè)，共七十四頁(yè)，2022年，8月28日奇偶校驗(yàn)碼

奇偶校驗(yàn)碼是在原信息碼元后面附加一個(gè)監(jiān)督碼元，使得碼組中“1”的個(gè)數(shù)為奇數(shù)或偶數(shù)。因此，奇偶校驗(yàn)碼是含一個(gè)監(jiān)督碼元，碼重為奇數(shù)或偶數(shù)的（n,n-1）系統(tǒng)分組碼。奇偶監(jiān)督碼又分為奇監(jiān)督碼和偶監(jiān)督碼。第三十二頁(yè)，共七十四頁(yè)，2022年，8月28日奇偶校驗(yàn)碼的特點(diǎn)

設(shè)有n-1位信息碼元為Cn-1，Cn-2，……，C1，校驗(yàn)碼為C0對(duì)于偶校驗(yàn)，有 對(duì)于奇校驗(yàn)，有奇偶校驗(yàn)碼只能檢測(cè)出代碼序列中的奇數(shù)個(gè)錯(cuò)誤。沒有糾錯(cuò)能力最小碼距為dmin=2編碼效率為R=（n-1）/n第三十三頁(yè)，共七十四頁(yè)，2022年，8月28日33行、列監(jiān)督碼奇偶校驗(yàn)碼不能發(fā)現(xiàn)偶數(shù)個(gè)錯(cuò)誤。為了改善這種情況，引入行、列監(jiān)督碼。這類編碼不僅對(duì)水平(行)方向的碼元，而且對(duì)垂直(列)方向的碼元實(shí)施奇偶校驗(yàn)。既可以逐行傳輸，也可以逐列傳輸。這類編碼具有較強(qiáng)的檢測(cè)能力，適于檢測(cè)突發(fā)錯(cuò)誤，還有一定的糾錯(cuò)能力。第三十四頁(yè)，共七十四頁(yè)，2022年，8月28日水平奇偶校驗(yàn)（HRC）

屬于水平方向冗余校驗(yàn)：把要傳輸?shù)臄?shù)據(jù)以適當(dāng)?shù)拈L(zhǎng)度劃分成若干個(gè)小組，每個(gè)小組由若干個(gè)碼字組成。把碼字按順序一列一列地排列起來，然后對(duì)水平方向的碼元進(jìn)行奇偶校驗(yàn)，得到一列校驗(yàn)碼字，附加在其它各列之后，最后按列的順序進(jìn)行傳輸。第三十五頁(yè)，共七十四頁(yè)，2022年，8月28日水平奇偶校驗(yàn)之例

字符位ABCDEFGHI偶校驗(yàn)位11010101011201100110003000111100040000000110500000000006000000000071111111111水平奇偶校驗(yàn)?zāi)馨l(fā)現(xiàn)水平方向奇數(shù)個(gè)錯(cuò)誤，以及所有突發(fā)長(zhǎng)度<=n（n為碼字長(zhǎng)度）的突發(fā)性錯(cuò)誤。第三十六頁(yè)，共七十四頁(yè)，2022年，8月28日垂直奇偶校驗(yàn)（VRC）

屬于垂直方向冗余校驗(yàn)碼：把要傳輸?shù)臄?shù)據(jù)以適當(dāng)?shù)拈L(zhǎng)度劃分成若干個(gè)小組，每個(gè)小組由若干個(gè)碼字組成。把碼字按順序一列一列地排列起來。然后對(duì)垂直方向的碼元進(jìn)行奇偶校驗(yàn)，得到一行校驗(yàn)位字，附加在其它各列之后，最后按列的順序進(jìn)行傳輸。第三十七頁(yè)，共七十四頁(yè)，2022年，8月28日垂直奇偶校驗(yàn)之例

垂直奇偶校驗(yàn)?zāi)馨l(fā)現(xiàn)垂直方向奇數(shù)個(gè)錯(cuò)誤，以及50%的突發(fā)性錯(cuò)誤。字符位ABCDEFGHI1101010101201100110030001111004000000011500000000060000000007111111111奇校驗(yàn)位110100110第三十八頁(yè)，共七十四頁(yè)，2022年，8月28日水平垂直奇偶校驗(yàn)（LRC）

水平垂直奇偶校驗(yàn)碼，也稱為方陣校驗(yàn)碼。它不僅對(duì)行進(jìn)行奇偶校驗(yàn)，而且也對(duì)列進(jìn)行奇偶校驗(yàn)。這種方法按列傳輸時(shí)能發(fā)現(xiàn)所有長(zhǎng)度<=n+1（n為碼字長(zhǎng)度）的突發(fā)性錯(cuò)誤和其它錯(cuò)誤；按行傳輸時(shí)能發(fā)現(xiàn)所有長(zhǎng)度<=m+1（m為碼字個(gè)數(shù)）的突發(fā)性錯(cuò)誤和其它錯(cuò)誤；并且具有一定的糾錯(cuò)能力。第三十九頁(yè)，共七十四頁(yè)，2022年，8月28日水平垂直奇偶校驗(yàn)之例

字符位ABCDEFGHI偶校驗(yàn)位11010101011201100110003000111100040000000110500000000006000000000071111111111奇校驗(yàn)位1101001101第四十頁(yè)，共七十四頁(yè)，2022年，8月28日定比碼定比碼的碼字中1的數(shù)目與0的數(shù)目保持恒定比例，也稱為恒比碼。由于恒比碼中，每個(gè)碼組均含有相同數(shù)目的1和0，因此恒比碼又稱等重碼，定1碼。這種碼在檢測(cè)時(shí)，只要計(jì)算接收碼元中1的數(shù)目是否正確，就可判斷有無差錯(cuò)。

第四十一頁(yè)，共七十四頁(yè)，2022年，8月28日定比碼應(yīng)用舉例我國(guó)電傳通信中普遍采用3∶2碼，又稱“5中取3”的定比碼，即每個(gè)碼組的長(zhǎng)度為5，其中3個(gè)“1”。這時(shí)可能編成的不同碼組數(shù)目等于從5中取3的組合數(shù)10，這10個(gè)許用碼組恰好可表示10個(gè)阿拉伯?dāng)?shù)字。而每個(gè)漢字又是以四位十進(jìn)制數(shù)來代表的。國(guó)際通用的ARQ電報(bào)通信系統(tǒng)采用“7中取3”的定比碼?！?中取3”碼可以檢出所有的單比特差錯(cuò)和奇數(shù)個(gè)差錯(cuò)，但只能檢出部分偶數(shù)位差錯(cuò)。第四十二頁(yè)，共七十四頁(yè)，2022年，8月28日第十章差錯(cuò)控制為什么要進(jìn)行差錯(cuò)控制差錯(cuò)控制的基本方法差錯(cuò)控制編碼的基本概念常用的簡(jiǎn)單編碼線性分組碼第四十三頁(yè)，共七十四頁(yè)，2022年，8月28日分組碼分組碼一般用(n,k)表示。其中，k是每組二進(jìn)制信息碼元的數(shù)目，n是編碼碼組的碼長(zhǎng)。n-k=r為每個(gè)碼組中的監(jiān)督碼元數(shù)目。簡(jiǎn)單地說，分組碼是對(duì)每段k位長(zhǎng)的信息組以一定的規(guī)則增加r個(gè)監(jiān)督元，組成碼長(zhǎng)為n的碼字。在二進(jìn)制情況下，共有2k個(gè)不同的信息組，相應(yīng)地可得到2k個(gè)不同的碼字，稱為許用碼組。其余2n-2k個(gè)碼字未被選用，稱為禁用碼組。分組碼=k個(gè)信息碼元+r個(gè)監(jiān)督碼元（校驗(yàn)碼元）第四十四頁(yè)，共七十四頁(yè)，2022年，8月28日（1）線性分組碼線性分組碼是指信息碼元與監(jiān)督碼元之間的關(guān)系可以用一組線性方程來表示的分組碼。在(n,k)分組碼中，每一個(gè)監(jiān)督碼元都是碼組中某些信息碼元按模2運(yùn)算而得到的。設(shè)(7,4)分組碼的碼字為

A=［a6a5a4a3a2a1a0］其中前4位是信息碼元，后3位是監(jiān)督碼元。該分組碼可用右邊的線性方程組來描述。第四十五頁(yè)，共七十四頁(yè)，2022年，8月28日監(jiān)督方程與監(jiān)督矩陣這組線性方程（即監(jiān)督方程）可用矩陣形式表示為：上式簡(jiǎn)記為：其中H稱為監(jiān)督矩陣，一旦H給定，信息位和監(jiān)督位之間的關(guān)系也就確定了。

第四十六頁(yè)，共七十四頁(yè)，2022年，8月28日監(jiān)督矩陣的特點(diǎn)可以寫成H=［Pr×k,Ir］形式的矩陣稱為典型監(jiān)督矩陣。HAT=0T，說明H矩陣與碼字的轉(zhuǎn)置乘積必為零，可以用來作為判斷接收碼字A是否出錯(cuò)的依據(jù)。根據(jù)線性代數(shù)的理論，H的各行一定是線性無關(guān)的。而一個(gè)非典型形式的H經(jīng)過運(yùn)算可以化成典型形式，第四十七頁(yè)，共七十四頁(yè)，2022年，8月28日監(jiān)督位的計(jì)算把監(jiān)督方程改寫，就可以根據(jù)信息位計(jì)算監(jiān)督位：上式寫成矩陣形式：其中Q=PT第四十八頁(yè)，共七十四頁(yè)，2022年，8月28日生成矩陣在矩陣Q的左邊加上k階單位矩陣Ik，得到G：通過G可以產(chǎn)生整個(gè)碼組，G就稱為生成矩陣。具有［Ik,Q］形式的G矩陣，稱為典型生成矩陣。由它產(chǎn)生的分組碼必定為系統(tǒng)碼，也就是信息碼字保持不變，監(jiān)督位附加其后，每行一定是線性無關(guān)的，每行都是一個(gè)生成碼組。第四十九頁(yè)，共七十四頁(yè)，2022年，8月28日（2）循環(huán)冗余碼（CRC）循環(huán)碼是一類重要的線性分組碼，它除了具有線性碼的一般性質(zhì)外，還具有循環(huán)性，即循環(huán)碼組中任一碼組循環(huán)移位所得的碼組仍為該循環(huán)碼中的一許用碼組。循環(huán)冗余碼（CRC碼）是數(shù)據(jù)通信領(lǐng)域中最常用的一種差錯(cuò)檢驗(yàn)碼，其特征是信息碼元和校驗(yàn)碼元的長(zhǎng)度可以任意選定。第五十頁(yè)，共七十四頁(yè)，2022年，8月28日CRC碼的原理假定我們構(gòu)成(n=7,k=3)這樣的線性分組碼，若已知三個(gè)信息碼元為C6、C5和C4，而校驗(yàn)碼元C3、C2、C1和C0是未知的。校驗(yàn)碼元與信息碼元間的關(guān)系是根據(jù)以下四個(gè)線性關(guān)系式確立的。 第五十一頁(yè)，共七十四頁(yè)，2022年，8月28日CRC碼的原理按上頁(yè)編出的線性碼為：信息碼元碼組C6C5C4C6C5C4C3C2C1C000000000000010011101010010011101101110101001001110101101001111011010011111110100當(dāng)我們從表中任意挑選出兩個(gè)碼組時(shí)，將對(duì)應(yīng)比特按模2相加，所得到的新碼組仍然是表中的某一碼組。這說明由8個(gè)碼字組成的線性碼具有封閉性。封閉性是線性碼的一個(gè)重要特性。第五十二頁(yè)，共七十四頁(yè)，2022年，8月28日循環(huán)冗余碼的基本思想把要傳輸?shù)臄?shù)據(jù)信息當(dāng)作一個(gè)報(bào)文碼多項(xiàng)式f(x)的系數(shù)，發(fā)送時(shí)用一個(gè)標(biāo)準(zhǔn)的生成多項(xiàng)式g(x)來除f(x)，將所除得余式r(x)的系數(shù)附加在報(bào)文碼之后發(fā)出；接收時(shí)用同一生成多項(xiàng)式g(x)來除收到的碼字多項(xiàng)式，能除盡說明傳輸正確，否則說明有錯(cuò)。實(shí)現(xiàn)：用簡(jiǎn)單的移位寄存器電路即可。第五十三頁(yè)，共七十四頁(yè)，2022年，8月28日碼多項(xiàng)式

從數(shù)學(xué)角度來看，所有的X進(jìn)制數(shù)都可以用一個(gè)以X為基的多項(xiàng)式來表示。對(duì)于二進(jìn)制數(shù)，基X=2，多項(xiàng)式的系數(shù)只取0、1。對(duì)于長(zhǎng)度為n的任一二進(jìn)制碼字，可以用一個(gè)x的n-1次多項(xiàng)式來表示。碼字中每個(gè)碼元的值就是該多項(xiàng)式中的相應(yīng)的系數(shù)。此多項(xiàng)式就成為碼多項(xiàng)式。如：

Cn-1Cn-2……C1

C0的碼多項(xiàng)式為：

Cn-1

xn-1+

Cn-2xn-2+……+

C1x1+

C0x0又如：碼字1010111對(duì)應(yīng)的多項(xiàng)式為x6+x4+x2+x+1，而多項(xiàng)式為x5+x3+x2+x+1對(duì)應(yīng)的碼字為101111。第五十四頁(yè)，共七十四頁(yè)，2022年，8月28日生成多項(xiàng)式如果一種碼的所有碼多項(xiàng)式都是多項(xiàng)式g(x)的倍式，則稱g(x)為該碼的生成多項(xiàng)式。在(n,k)循環(huán)碼中任意碼多項(xiàng)式A(x)都是最低次碼多項(xiàng)式的倍式。在如前所述的(7,3)循環(huán)碼中，

g(x)=x4+x3+x2+1

其它碼多項(xiàng)式都是g(x)的倍式。因此，循環(huán)碼中次數(shù)最低的多項(xiàng)式(全0碼字除外)就是生成多項(xiàng)式g(x)。第五十五頁(yè)，共七十四頁(yè)，2022年，8月28日循環(huán)碼的生成多項(xiàng)式和生成矩陣可以證明，循環(huán)碼的生成多項(xiàng)式g(x)是常數(shù)項(xiàng)為1的r=n-k次多項(xiàng)式，是xn+1的一個(gè)因式?？梢员硎緸椋篻(x)=xr+gr-1xr-1+…+g1x+1

循環(huán)碼的生成矩陣常用

多項(xiàng)式的形式來表示。第五十六頁(yè)，共七十四頁(yè)，2022年，8月28日循環(huán)冗余碼（CRC）

設(shè)：

k個(gè)信息碼元Cn-1，Cn-2，……，Cn-k對(duì)應(yīng)的碼多項(xiàng)式為f(x)；r次的生成多項(xiàng)式為g(x)

（n=k+r）；用g(x)去除f(x)（模2運(yùn)算）所得余式為r(x)；f(x)=Cn-1

xk-1+

Cn-2xk-2+……+

Cn-k

x0r(x)=Cr-1

xr-1+

Cr-2

xr-2+……+

C0x0Cn-1，Cn-2，……，Cn-k，Cr-1，……，C0第五十七頁(yè)，共七十四頁(yè)，2022年，8月28日循環(huán)冗余編碼工作原理

發(fā)送方接收方發(fā)送數(shù)據(jù)f(x)生成多項(xiàng)式g(x)f(x)xr.g(x)=q(x)+r(x)g(x)實(shí)際發(fā)送:f(x)xr.+r(x)信息字段校驗(yàn)字段f(x)xr.r(x)接收數(shù)據(jù)f(x)+r(x)生成多項(xiàng)式g(x)r'(x)=r(x)接收正確r'(x)≠r(x)接收出錯(cuò)發(fā)送f(x)xr.g(x)=q(x)+r'(x)g(x)第五十八頁(yè)，共七十四頁(yè)，2022年，8月28日CRC校驗(yàn)碼軟件生成方法設(shè)：信息代碼M為1011001，生成多項(xiàng)式為g(x)=x4+x3+1，則：k=7，r=4，CRC碼字長(zhǎng)度為n=11對(duì)應(yīng)f(x)=x6+x4+x3+1，g(x)的代碼為11001x4f(x)=x10+x8+x7+x4采用多項(xiàng)式除法，得余數(shù)為1010

(即校驗(yàn)字段為1010)發(fā)送方發(fā)出的傳輸編碼為:

1011001

1010

信息字段

校驗(yàn)字段接收方使用相同的生成碼進(jìn)行校驗(yàn)，將接收到的字段除以生成碼（二進(jìn)制除法），如果能夠除盡，則正確，否則出錯(cuò)。第五十九頁(yè)，共七十四頁(yè)，2022年，8月28日簡(jiǎn)化算法

11111101√1010000

1110110010

1110111110

1110111將信息碼字左移n-k位，后面補(bǔ)上n-k個(gè)0；用所得的碼字除以生成多項(xiàng)式g(x)的系數(shù)；將所得的n-k位余數(shù)接在信息碼字之后，即可得到CRC編碼。例：設(shè)(7,3)碼的信息碼字為101，生成多項(xiàng)式為：g(x)=x4+x3+x2+1求CRC編碼的碼字的過程如右圖所示。余數(shù)為0011，CRC編碼為1010011。第六十頁(yè)，共七十四頁(yè)，2022年，8月28日例1設(shè)信息代碼M=1010001101，r=5,G=110101。模2運(yùn)算的結(jié)果是：商Q=1101010110，余數(shù)R=01110。將余數(shù)R作為冗余碼添加在信息M的后面發(fā)送出去，即發(fā)送的數(shù)據(jù)是101000110101110，或2rM+R。第六十一頁(yè)，共七十四頁(yè)，2022年，8月28日例1的計(jì)算過程

1101010110

←

Q

商

除數(shù)

P→

110101101000110100000

←

2rM被除數(shù)

110101

111011

110101

111010

110101

111110

110101

101100

110101

110010

110101

01110

←

R

余數(shù)第六十二頁(yè)，共七十四頁(yè)，2022年，8月28日

1100111001110011100111001110010100001110011000011001G(x)1100110000110011001R(x)100001Q(x)f(x).xr例2110011發(fā)送數(shù)據(jù)比特序列CRC校驗(yàn)碼比特序列1001帶CRC校驗(yàn)碼的發(fā)送數(shù)據(jù)比特序列第六十三頁(yè)，共七十四頁(yè)，2022年，8月28日例3原始數(shù)據(jù)M=1101011011G(x)=x4+x+1的系數(shù)=1001111010110110000100111001110011100111011010011101001001111101100001010余數(shù)傳輸碼元

=原始數(shù)據(jù)（左移位后）+余數(shù)

11010110111110第六十四頁(yè)，共七十四頁(yè)，2022年，8月28日標(biāo)準(zhǔn)CRC生成多項(xiàng)式G(x)CRC-12：G（x）=x12+x11+x3+x2+x+1CRC-16：G（x）=x16+x15+x2+1CRC-CCITT：G（x）=x16+x12+x5+1CRC-32：G（x）=x32+x26+x23+x22+x16+x12+x11+x10+x8+

x7+x5+x4+

x2+x+1第六十五頁(yè)，共七十四頁(yè)，2022年，8月28日循環(huán)碼的檢錯(cuò)能力

理論證明，CRC碼能查出：全部的單個(gè)比特錯(cuò)誤；所有的離散的雙位錯(cuò)（不相鄰）；全部≤n-k（冗余位數(shù)）的突發(fā)性錯(cuò)誤；對(duì)于n-k+1位的突發(fā)性錯(cuò)誤；檢出率為1-2-(n-k-1)；對(duì)于多于n-k+1位的突發(fā)性錯(cuò)誤；檢出率為1-2-(n-k)；實(shí)驗(yàn)表明，如果使用16位冗余碼可以檢出所有奇數(shù)位的差錯(cuò)及所有雙位錯(cuò)，和長(zhǎng)度小于16位的突發(fā)錯(cuò)誤，還能查出99.997%的17位和99.998%18位或更長(zhǎng)位的突發(fā)性錯(cuò)誤。傳輸速率為9600bps時(shí)，傳輸3000年才會(huì)有一個(gè)錯(cuò)誤。第六十六頁(yè)，共七十四頁(yè)，2022年，8月28日海明碼Hamming于1950年在美國(guó)貝爾實(shí)驗(yàn)室提出了海明碼，是第一個(gè)用來糾錯(cuò)的線性分組碼，被廣泛地應(yīng)用在數(shù)據(jù)通信和數(shù)據(jù)存儲(chǔ)系統(tǒng)的差錯(cuò)控制中。所謂海明校驗(yàn)實(shí)質(zhì)上是奇偶校驗(yàn)，是分組奇偶校驗(yàn)。它可以糾正一位差錯(cuò)。設(shè)海明碼長(zhǎng)為n，監(jiān)督碼元的個(gè)數(shù)為r，海明碼它利用r個(gè)監(jiān)督關(guān)系式產(chǎn)生的r個(gè)校正因子來區(qū)分無錯(cuò)和在碼字中的n個(gè)不同位置的一位錯(cuò)。第六十七頁(yè)，共七十四頁(yè)，2022年，8月28日海明