第8章差錯控制編碼技術(shù)

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