差錯(cuò)控制編碼技術(shù)

差錯(cuò)控制編碼技術(shù)第一頁，共五十二頁，2022年，8月28日8.1差錯(cuò)控制編碼的基本概念1.差錯(cuò)控制的工作方式按照噪聲或干擾的變化規(guī)律，可把信道分為三類：隨機(jī)信道、突發(fā)信道和混合信道。恒參高斯白噪聲信道是典型的隨機(jī)信道，其中差錯(cuò)的出現(xiàn)是隨機(jī)的，而且錯(cuò)誤之間是統(tǒng)計(jì)獨(dú)立的。具有脈沖干擾的信道是典型的突發(fā)信道，錯(cuò)誤是成串成群出現(xiàn)的，即在短時(shí)間內(nèi)出現(xiàn)大量錯(cuò)誤。第二頁，共五十二頁，2022年，8月28日差錯(cuò)控制的基本工作方式有4種：前向糾錯(cuò)、檢錯(cuò)重發(fā)、混合糾錯(cuò)和反饋校驗(yàn)。（1）前向糾錯(cuò)方式前向糾錯(cuò)方式記作FEC。發(fā)端發(fā)送能夠糾正錯(cuò)誤的碼，收端收到信碼后自動(dòng)地糾正傳輸中的錯(cuò)誤。其特點(diǎn)是單向傳輸，實(shí)時(shí)性好，但譯碼設(shè)備較復(fù)雜。（2）檢錯(cuò)重發(fā)方式檢錯(cuò)重發(fā)方式又稱自動(dòng)請(qǐng)求重傳方式，記作ARQ。第三頁，共五十二頁，2022年，8月28日（3）混合糾錯(cuò)方式 混合糾錯(cuò)方式記作HEC，是FEC和ARQ方式的結(jié)合。（4）信息反饋方式 信息反饋方式記作IF，信息反饋是收端將接收的消息原封不動(dòng)地送回發(fā)端，由發(fā)端將反饋信息和原發(fā)送信息進(jìn)行比較，發(fā)現(xiàn)錯(cuò)誤進(jìn)行重發(fā)，其優(yōu)點(diǎn)是方法和設(shè)備簡(jiǎn)單，無需糾（檢）錯(cuò)編譯系統(tǒng)。第四頁，共五十二頁，2022年，8月28日2.差錯(cuò)控制編碼的分類 （1）按照差錯(cuò)控制編碼的用途不同可分為檢錯(cuò)碼、糾錯(cuò)碼和糾刪碼。 （2）按照信息碼元和監(jiān)督碼元之間的函數(shù)關(guān)系可分為線性碼和非線性碼。 （3）按照對(duì)信息元處理方式的不同可分為分組碼和卷積碼。第五頁，共五十二頁，2022年，8月28日（4）按照碼組中信息碼元在編碼前后是否相同可分為系統(tǒng)碼和非系統(tǒng)碼。（5）按照糾（檢）錯(cuò)誤的類型可分為糾（檢）隨機(jī)錯(cuò)誤碼、糾（檢）突發(fā)錯(cuò)誤碼和既能糾（檢）隨機(jī)錯(cuò)誤同時(shí)又能糾（檢）突發(fā)錯(cuò)誤碼。（6）按照每個(gè)碼元的取值可分為二進(jìn)碼和多進(jìn)碼。第六頁，共五十二頁，2022年，8月28日3.差錯(cuò)控制編碼的基本原理 差錯(cuò)編碼的基本思想是在被傳輸信息中增加一些冗余碼，利用附加碼元和信息碼元之間的約束關(guān)系加以校驗(yàn)，以檢測(cè)和糾正錯(cuò)誤，增加冗余碼的個(gè)數(shù)可增加糾檢錯(cuò)能力。第七頁，共五十二頁，2022年，8月28日（1）碼長(zhǎng)、碼重、碼距 編碼碼組的碼元總位數(shù)稱為碼組的長(zhǎng)度，簡(jiǎn)稱碼長(zhǎng)。 碼組中，“1”碼元的數(shù)目稱為碼組的重量，簡(jiǎn)稱碼重。 兩個(gè)等長(zhǎng)碼組之間對(duì)應(yīng)位上碼元不同的數(shù)目稱為這兩個(gè)碼組的距離，簡(jiǎn)稱碼距。第八頁，共五十二頁，2022年，8月28日（2）檢錯(cuò)和糾錯(cuò)能力 ①檢測(cè)e個(gè)隨機(jī)錯(cuò)誤，則要求最小碼距d0≥e+1； ②糾正t個(gè)隨機(jī)錯(cuò)誤，則要求最小碼距d0≥2t+1； ③糾正t個(gè)同時(shí)檢測(cè)e（e＞t）個(gè)隨機(jī)錯(cuò)誤，則要求最小碼距d0≥t+e+1。第九頁，共五十二頁，2022年，8月28日（3）編碼效率 用差錯(cuò)控制編碼提高通信系統(tǒng)的的可靠性，是以降低有效性為代價(jià)換來的。定義編碼效率R來衡量有效性：R=k/n其中，k是信息元的個(gè)數(shù)，n為碼長(zhǎng)。第十頁，共五十二頁，2022年，8月28日4.常用的幾種簡(jiǎn)單編碼（1）奇偶監(jiān)督碼 奇偶監(jiān)督碼是在原信息碼后面附加一個(gè)監(jiān)督元，使得碼組中“1”的個(gè)數(shù)是奇數(shù)或偶數(shù)，或者說，它是含一個(gè)監(jiān)督元，碼重為奇數(shù)或偶數(shù)的（n，n-1）系統(tǒng)分組碼。奇偶監(jiān)督碼又分為奇監(jiān)督碼和偶監(jiān)督碼。第十一頁，共五十二頁，2022年，8月28日（2）行列監(jiān)督碼 奇偶監(jiān)督碼不能發(fā)現(xiàn)偶數(shù)個(gè)錯(cuò)誤。為了改善這種情況，引入行列監(jiān)督碼。這種碼不僅對(duì)水平（行）方向的碼元，而且對(duì)垂直（列）方向的碼元實(shí)施奇偶監(jiān)督。第十二頁，共五十二頁，2022年，8月28日（3）恒比碼 碼字中1的數(shù)目與0的數(shù)目保持恒定比例的碼稱為恒比碼。由于恒比碼中，每個(gè)碼組均含有相同數(shù)目的1和0，因此恒比碼又稱等重碼，定1碼。這種碼在檢測(cè)時(shí)，只要計(jì)算接收碼元中1的個(gè)數(shù)是否與規(guī)定的相同，就可判斷有無錯(cuò)誤。第十三頁，共五十二頁，2022年，8月28日（4）群計(jì)數(shù)碼 群計(jì)數(shù)碼是將信息碼元分組后，計(jì)算每組碼元中“1”的個(gè)數(shù)，然后將這個(gè)數(shù)目的二進(jìn)制表示作為監(jiān)督碼元，一起送往發(fā)送端。第十四頁，共五十二頁，2022年，8月28日8.2線性分組碼1.線性分組碼的定義和特點(diǎn) 線性分組碼，是指信息碼元與監(jiān)督碼元之間的關(guān)系可以用一組線性方程來表示的分組碼，即在（n，k）分組碼中，每一個(gè)監(jiān)督碼元都是碼組中某些信息碼元按模2和而得到的，線性分組碼是一類重要的糾錯(cuò)碼，應(yīng)用很廣。第十五頁，共五十二頁，2022年，8月28日2.監(jiān)督矩陣H和生成矩陣G（1）監(jiān)督矩陣第十六頁，共五十二頁，2022年，8月28日我們把H稱為監(jiān)督矩陣，或稱一致校驗(yàn)矩陣，一旦H給定，信息位和監(jiān)督位之間的關(guān)系也就確定了。H為r×n階矩陣，H矩陣每行之間是彼此線性無關(guān)的。H矩陣可分成兩部分，其中P為r×k階矩陣，Ir為r×r階單位陣。能寫成H=［PIr］形式的矩陣稱為典型監(jiān)督矩陣。第十七頁，共五十二頁，2022年，8月28日（2）生成矩陣第十八頁，共五十二頁，2022年，8月28日 稱為生成矩陣，由G和信息組就可以產(chǎn)生全部碼字。G為k×n階矩陣，各行也是線性無關(guān)的。生成矩陣也可以分為兩部分：其中Q為k×r階矩陣，Ik為k階單位陣，可以寫成式（8-12）形式的G矩陣，稱為典型生成矩陣。非典型形式的矩陣經(jīng)過運(yùn)算也一定可以化為典型矩陣形式。第十九頁，共五十二頁，2022年，8月28日（3）監(jiān)督矩陣H和生成矩陣G之間的關(guān)系 由上可知，監(jiān)督矩陣H和生成矩陣G之間有一一對(duì)應(yīng)的關(guān)系。由于G的每一行都為碼字，因此它必然滿足式（8-7）HAT=0T即HGT=0T第二十頁，共五十二頁，2022年，8月28日3.線性分組碼的譯碼——伴隨式（校正子）S 若某一碼字為許用碼組，則它必然滿足式（8-7）。利用這一關(guān)系，在接收端將收到的碼組和事先與發(fā)端約定好的監(jiān)督矩陣相乘，看是否為零。若滿足條件，則認(rèn)為接收正確；反之，則認(rèn)為傳輸過程中發(fā)生了錯(cuò)誤，進(jìn)而設(shè)法確定錯(cuò)誤的數(shù)目和位置。第二十一頁，共五十二頁，2022年，8月28日 令S=BHT，稱為伴隨式或校正子。S=BHT=（A+E）HT=EHT 由此可見，伴隨式S與錯(cuò)誤圖樣E之間有確定的線性變換關(guān)系，與發(fā)送碼組A無關(guān)。接收端譯碼器的任務(wù)就是從伴隨式確定錯(cuò)誤圖樣，然后從接收到的碼字中減去錯(cuò)誤圖樣。第二十二頁，共五十二頁，2022年，8月28日從以上分析可以得出線性分組碼譯碼的基本步驟：①計(jì)算接收碼組B的伴隨式S；②根據(jù)S找出錯(cuò)誤圖樣E，判定誤碼位置；③根據(jù)E糾正錯(cuò)誤，得到正確的碼組A=E+B。第二十三頁，共五十二頁，2022年，8月28日4.漢明碼 漢明碼是一類常見的線性分組碼，是一種能夠糾正單個(gè)錯(cuò)誤的完備碼。要糾正碼組中的單個(gè)錯(cuò)誤，則要求與單個(gè)錯(cuò)誤圖樣對(duì)應(yīng)的伴隨式各不相同，且不能為全零。若碼長(zhǎng)為n，監(jiān)督碼元的個(gè)數(shù)為r，則要求2r-1≥n。碼組為漢明碼時(shí)取等號(hào)。即用來糾正單個(gè)錯(cuò)誤時(shí)，漢明碼所用的監(jiān)督碼元個(gè)數(shù)最少，效率最高。第二十四頁，共五十二頁，2022年，8月28日漢明碼的特點(diǎn)如下。（1）監(jiān)督碼元的個(gè)數(shù)r=n-k，碼長(zhǎng)滿足n=2r-1，則k=n-r。r≥2。（2）無論碼長(zhǎng)n為多少，漢明碼最小碼距d0=3。（3）其編碼效率為η=k/n=2r-1-r/2r-1=1-r/n。第二十五頁，共五十二頁，2022年，8月28日8.3循環(huán)碼 循環(huán)碼是另一類重要的線性分組碼，它除了具有線性碼的一般性質(zhì)外，還具有循環(huán)性，即循環(huán)碼組中任一碼組循環(huán)移位所得的碼組仍為該循環(huán)碼中的一許用碼組。 在代數(shù)理論中，為了便于計(jì)算，常用碼多項(xiàng)式表示碼字。（n，k）循環(huán)碼的碼字，其碼多項(xiàng)式（以降冪順序排列）為A（x）=an-1xn-1+an-2xn-2+…+a1x+a0第二十六頁，共五十二頁，2022年，8月28日1.生成多項(xiàng)式和生成矩陣 如果一種碼的所有碼多項(xiàng)式都是多項(xiàng)式g（x）的倍式，則稱g（x）為該碼的生成多項(xiàng)式。在（n，k）循環(huán)碼中任意碼多項(xiàng)式A（x）都是最低次碼多項(xiàng)式的倍式。如表8-5的（7，3）循環(huán)碼中g(shù)（x）=A1（x）=x4+x3+x2+1第二十七頁，共五十二頁，2022年，8月28日 循環(huán)碼的生成矩陣可以很容易的由生成多項(xiàng)式得到，常用矩陣的形式表示。第二十八頁，共五十二頁，2022年，8月28日2.監(jiān)督多項(xiàng)式和監(jiān)督矩陣 為了便于對(duì)循環(huán)碼編譯碼，通常還定義監(jiān)督多項(xiàng)式，令其中g(shù)（x）是常數(shù)項(xiàng)為1的r次多項(xiàng)式，是生成多項(xiàng)式；h（x）是常數(shù)項(xiàng)為1的k次多項(xiàng)式，稱為監(jiān)督多項(xiàng)式。同理，它的監(jiān)督矩陣H第二十九頁，共五十二頁，2022年，8月28日第三十頁，共五十二頁，2022年，8月28日3.循環(huán)碼的編解碼方法和電路（1）循環(huán)碼的編碼 在編碼時(shí)，首先要根據(jù)給定的（n，k）值選定生成多項(xiàng)式g（x），即從xn+1的因式中選一個(gè)r次多項(xiàng)式作為g（x）。第三十一頁，共五十二頁，2022年，8月28日根據(jù)上述原理，循環(huán)碼編碼步驟可歸納如下。①用xr乘m（x）。這一運(yùn)算實(shí)際上是把信息碼后附加上r個(gè)“0”，給監(jiān)督位留出地方。②用g（x）去除xr·m（x），得到商Q（x）和余式r（x）。③編出的碼組為A（x）=xr·m（x）+r（x）。第三十二頁，共五十二頁，2022年，8月28日（2）循環(huán)碼的譯碼 原則上糾錯(cuò)可按下述步驟進(jìn)行： ①用生成多項(xiàng)式g（x）去除接收碼組B（x）=A（x）+E（x），得出余式r（x）； ②按余式r（x）用查表的方法或通過某種運(yùn)算得到錯(cuò)誤圖樣E（x），就可以確定錯(cuò)碼位置。 ③從B（x）中減去E（x），便得到已糾正錯(cuò)誤的原發(fā)送碼組A（x）。第三十三頁，共五十二頁，2022年，8月28日8.4卷積碼 卷積碼又稱連環(huán)碼，是1955年提出來的一種糾錯(cuò)碼，它和分組碼有明顯的區(qū)別，屬于非分組碼。1.卷積碼編碼 卷積碼常用符號(hào)（n，k，m）表示。其中，n為碼長(zhǎng)，k為碼組中信息碼元的個(gè)數(shù)，m為相互關(guān)聯(lián)的碼組的個(gè)數(shù)。第三十四頁，共五十二頁，2022年，8月28日 卷積碼同樣也可以用矩陣的方法描述，但較抽象。因此，采用圖解的方法直觀描述其編碼過程。常用的圖解法有3種：樹圖、狀態(tài)圖和格圖。（1）樹圖 樹圖描述的是在任何數(shù)據(jù)序列輸入時(shí)，碼字所有可能的輸出。對(duì)應(yīng)于圖8-4所示的（2，1，2）卷積碼的編碼電路，可以畫出其樹圖如圖8-5所示。第三十五頁，共五十二頁，2022年，8月28日?qǐng)D8-4卷積碼（2，1，2）編碼器第三十六頁，共五十二頁，2022年，8月28日?qǐng)D8-5（2，1，2）卷積碼的樹圖第三十七頁，共五十二頁，2022年，8月28日（2）狀態(tài)圖 除了用樹圖表示編碼器的工作過程外，還可以用狀態(tài)圖來描述。圖8-6所示的是該（2，1，2）卷積編碼器的狀態(tài)圖。（3）格圖 格圖也稱網(wǎng)絡(luò)圖或籬笆圖，它由狀態(tài)圖在時(shí)間上展開而得到。第三十八頁，共五十二頁，2022年，8月28日?qǐng)D8-6（2，1，2）卷積碼的狀態(tài)圖第三十九頁，共五十二頁，2022年，8月28日2.卷積碼的譯碼 卷積碼的譯碼可分為代數(shù)譯碼和概率譯碼兩大類。卷積碼不是分組碼，但仍屬于線性碼，同樣可由生成矩陣G和監(jiān)督矩陣H來確定。代數(shù)譯碼就是利用生成矩陣和監(jiān)督矩陣來譯碼，最主要的方法是代數(shù)邏輯譯碼。第四十頁，共五十二頁，2022年，8月28日（1）維特比譯碼 維特比譯碼。它是一種最大似然譯碼算法。最大似然譯碼算法的基本思路是，把接收碼字與所有可能的碼字比較，選擇一種碼距最小的碼字作為解碼輸出。第四十一頁，共五十二頁，2022年，8月28日（2）序列譯碼 當(dāng)m很大時(shí)，可以采用序列譯碼法。其過程如下。 譯碼先從碼樹的起始節(jié)點(diǎn)開始，把接收到的第一個(gè)子碼的n個(gè)碼元與自始節(jié)點(diǎn)出發(fā)的兩條分支按照最小漢明距離進(jìn)行比較，沿著差異最小的分支走向第二個(gè)節(jié)點(diǎn)。在第二個(gè)節(jié)點(diǎn)上，譯碼器仍以同樣原理到達(dá)下一個(gè)節(jié)點(diǎn)，依此類推，最后得到一條路徑。第四十二頁，共五十二頁，2022年，8月28日若接收碼組有錯(cuò)，則自某節(jié)點(diǎn)開始，譯碼器就一直在不正確的路徑中行進(jìn)，譯碼也一直錯(cuò)誤。因此，譯碼器有一個(gè)門限值，當(dāng)接收碼元與譯碼器所走的路徑上的碼元之間的差異總數(shù)超過門限值時(shí)，譯碼器判定有錯(cuò)，并且返回試走另一分支。經(jīng)數(shù)次返回找出一條正確的路徑，最后譯碼輸出。第四十三頁，共五十二頁，2022年，8月28日8.5網(wǎng)格編碼調(diào)制（TCM） 引入了編碼和調(diào)制相結(jié)合統(tǒng)一進(jìn)行設(shè)計(jì)的方法，也就是網(wǎng)絡(luò)編碼調(diào)制（TrellisCodedModulation，TCM）技術(shù)。它是利用編碼效率為n/（n+1）的卷積碼，并將每一碼段映射為2n+1個(gè)調(diào)制信號(hào)集中的一個(gè)信號(hào)，使信號(hào)點(diǎn)之間相互依賴。第四十四頁，共五十二頁，2022年，8月28日它有兩個(gè)基本特點(diǎn)。（1）在信號(hào)空間中的信號(hào)點(diǎn)數(shù)目比無編碼的調(diào)制情況下對(duì)應(yīng)的信號(hào)點(diǎn)數(shù)目要多，這些增加的信號(hào)點(diǎn)使編碼有了冗余，而不犧牲帶寬。（2）采用卷積碼的編碼規(guī)則，使信號(hào)點(diǎn)之間引入相互依賴關(guān)系。僅有某些信號(hào)點(diǎn)圖樣或序列是允許用的信號(hào)序列，并可模型化成為網(wǎng)格狀結(jié)構(gòu)，因此又稱為“格狀”編碼。第四十五頁，共五十二頁，2022年，8月28日在收端采用維特比算法執(zhí)行最大似然檢測(cè)。編碼網(wǎng)格狀圖中的每一條支路對(duì)應(yīng)于一個(gè)子集，而不是一個(gè)信號(hào)點(diǎn)。檢測(cè)的