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