漢明編解碼

⑴ 什麼是解碼

解碼是編碼的逆過程，同時去掉比特流在傳播過程中混入的雜訊。利用解碼表把文字譯成一組組數碼或用解碼表將代表某一項信息的一系列信號譯成文字的過程稱之為解碼。
解碼器是電子技術中的一種多輸入多輸出的組合邏輯電路，負責將二進制代碼翻譯為特定的對象（如邏輯電平等），功能與編碼器相反。解碼器一般分為通用解碼器和數字顯示解碼器兩大類。
數字電路中，解碼器（如n線－2n線BCD解碼器）可以擔任多輸入多輸出邏輯門的角色，能將已編碼的輸入轉換成已編碼的輸出，這里輸入和輸出的編碼是不同的。
輸入使能信號必須接在解碼器上使其正常工作，否則輸出將會是一個無效的碼字。解碼在多路復用、七段數碼管和內存地址解碼等應用中是必要的。

⑵ PDF417解碼，RS糾錯碼，求糾錯碼生成多項式零點問題！

糾錯碼能夠檢錯或糾錯，主要是靠碼字之間有較大的差別。這可用碼字之間的漢明距離d(x，y)來衡量。它的定義為碼字x與y之間的對應位取不同值的碼元個數。一種糾錯碼的最小距離d定義為該種碼中任兩個碼字之間的距離的最小值。一種碼要能發現e個錯誤,它的最小距離d應不小於e+1。若要能糾正t個錯誤，則d應不小於2t+1。一個碼字中非零碼元的個數，稱為此碼字的漢明重量。一種碼中非零碼字的重量的最小值，稱為該碼的最小重量。對線性碼來說，一種碼的最小重量與其最小距離在數值上是相等的。
在構造線性碼時，數字上是從n維空間中選一k維子空間，且使此子空間內各非零碼字的重量盡可能大。當構造循環碼時,可進一步將每一碼字看成一多項式,將整個碼看成是多項式環中的理想,這一理想是主理想,故可由生成多項式決定；而多項式完全可由它的根規定。這樣,就容易對碼進行構造和分析。這是BCH碼等循環碼構造的出發點。一般地說，構造一種碼時，均設法將它與某種代數結構相聯系，以便對它進行描述，進而推導它的性質，估計它的性能和給出它的解碼方法。若一種碼的碼長為n，碼字數為M,或信息位為h,以及最小距離為d，則可把此碼記作【n,M,d】碼。若此碼為線性碼，常簡記作(n，k)或(n,k,d)碼。人們還常用R=log2M/n表示碼的信息率或簡稱碼率,單位為比特/碼元。R越大,則每個碼元所攜帶的信息量越大，編碼效率越高。 糾錯碼實現中最復雜的部分是解碼。它是糾錯碼能否應用的關鍵。根據式(1),採用的碼長n越大,則誤碼率越小。但n越大，編譯碼設備也越復雜,且延遲也越大。人們希望找到的解碼方法是:誤碼率隨碼長n的增加按指數規律下降;解碼的復雜程度隨碼長n的增加接近線性地增加；解碼的計算量則與碼長n基本無關。可惜，已經找到的碼能滿足這樣要求的很少。不過由於大規模集成電路的發展，即使應用比較復雜的但性能良好的碼，成本也並不太高。因此，糾錯碼的應用越來越廣泛。
糾錯碼傳輸的都是數字信號。這既可用硬體實現，也可用軟體實現。前者主要用各種數字電路，主要是採用大規模集成電路。軟體實現特別適合計算機通信網等場合。因為這時可以直接利用網中的計算機進行編碼和解碼，不需要另加專用設備。硬體實現的速度較高，比軟體可快幾個數量級。
在傳信率一定的情況下，如果採用糾錯碼提高可靠性，要求信道的傳輸率增加，帶寬加大。因此，糾錯碼主要用於功率受限制而帶寬較大的信道，如衛星、散射等系統中。糾錯碼還用在一些可靠性要求較高，但設備或器件的可靠性較差，而餘量較大的場合，如磁帶、磁碟和半導體存儲器等。
在分組碼的研究中，譜分析的方法受到人們的重視。糾同步錯誤碼、算術碼、不對稱碼、不等錯誤糾正碼等，也得到較多的研究。 分組碼是對信源待發的信息序列進行分組（每組K位）編碼，它的校驗位僅同本組的信息位有關。自20世紀50年代分組碼的理論獲得發展以來，分組碼在數字通信和數據存儲系統中已被廣泛應用。
分組碼的碼長n和碼字個數M是一個碼的主要構造參數。碼長為n的碼中所有碼字的位數均為n；若要用一個碼傳送k比特信息，則碼字的個數M必須滿足。典型的分組碼是由k位信息位和r位監督位組成的，這樣構成的碼一般稱為系統碼。
分組碼中應用最廣的線性分組碼。線性分組碼中的M個碼字之間具有一定線性約束關系，即這些碼字總體構成了n維線性空間的一個k維子空間。稱此k維子空間為（n，k）線性分組碼。線性系統碼的特點是每個碼字的前k位均由這個碼字所對應的信息位組成，並通過對這k位信息位的線性運算得到後面n—k是位監督位。
線性分組碼中應用最廣的是循環碼，循環碼的主要特徵是任何碼字在循環移位後個碼字。循環碼的優點在於其編碼和解碼手續比一般線性碼簡單，因而易於在設備上實現。在循環碼中，碼字可表示為多項式。循環碼的碼字多項式都可表示成為循環碼的生成多項式與這個碼字所代表的信息多項式的乘積，即，因此一個循環碼可以通過給出其生成多項式來規定。常用的循環碼有BCH碼和RS碼。
網格碼有多種描述方法，網格圖是常用方法之一，它能表示出編碼過程。一個碼率為1/2、包含四種狀態的網格碼的網格圖如圖所示。圖1中00，01，10，11表示編碼器所具有的四種狀態，以「·」示出，從每一狀態出發都存在兩條支路，位於上面的一條支路對應於編碼器輸入為「0」的情況，位於下面的一條支路對應於編碼器輸入為「1」的情況，而每一支路上所列出的兩個二進位碼則表示相應的編碼輸出。因而可知，編碼輸出不僅決定於編碼器的當前輸入，還決定於編碼器的狀態，例如在圖中從「00」狀態出發；，若輸入的二進制數據序列為1011，則編碼器的狀態轉移過程為00→01→10→01→11，而相應的編碼輸出序列為11010010。在網格圖中任意兩條從同一狀態出發；，經不同的狀態轉移過程後又歸於另一相同狀態（該狀態也可與初始狀態相同）的路徑間的距離的最小值稱為碼的自由距離。如該圖中的為5。對於卷積碼來說，的計算可簡化為始於且終於零狀態的非全零路徑與全零路徑間距離的最小值。是表徵網格碼糾錯能力的重要參數。維特比演算法是廣泛採用的網格碼的解碼方法。由於網格碼的狀態越多，解碼越復雜，所以狀態個數是度量網格碼解碼復雜性的重要參數。一般說來可以通過增大解碼復雜性來增加，從而提高碼的糾錯能力。
BCH碼、網格碼已被廣泛地應用於移動通信、衛星通信和頻帶數據傳輸中。RS碼也被廣泛應用於光碟的存儲中。
大多數糾錯碼是設計來糾隨機誤碼的，可以通過交織的方法使它適用於對突發誤碼的糾錯。交織是一種使得集中出現的突發誤碼在解碼時進行分散化的措施，從而使其不超出糾錯碼的糾錯能力范圍。 卷積碼不對信息序列進行分組編碼，它的校驗元不僅與當前的信息元有關，而且同以前有限時間段上的信息元有關。卷積碼在編碼方法上尚未找到像分組碼那樣有效的數學工具和系統的理論。但在解碼方面，不論在理論上還是實用上都超過了分組碼，因而在差錯控制和數據壓縮系統中得到廣泛應用。

⑶ LDPC碼的碼的構造

對LDPC碼來說，不考慮碼長和次數分布的情況下，校驗矩陣的結構就成了影響其性能的重要因素，反映在二分圖上對編碼性能有重要影響的就是圖中環的長度分布，需要採用一定的方法對校驗矩陣進行構造，獲得好的編碼。
目前LDPC碼的構造方法主要可以分為兩大類：隨機或偽隨機構造方法和代數的構造方法。
隨機或偽隨機的構造方法主要考慮的是碼的性能，在碼長比較長(接近或超過10000) 時，性能非常接近香農限。代數的構造方法通常考慮的是降低編解碼的復雜度，在碼長比較短的時候更有優勢。
1. Gallager LDPC碼
用和乘積演算法(SPA:Sum-pordcuct algorithm)進行解碼取得最大後驗概率的解碼性能的條件是二分圖中沒有小的環，即girth為4的環，無4環的條件反映到二分圖中就是任意兩行中1的交迭數目不超過1個。無4環的二元高比特率LDPc碼可以通過隨機生成行構成，一般來說，這種方法不能生成固定行重量的矩陣。
Gallaegr提出了一種替代的方法：採用隨機置換的方法來構造規則LDPC碼。對於碼長為N的(j，k)正則碼，將M*N矩陣H通過j個大小為(M/j)*N的子矩陣構成，每個子矩陣本身也是LDPC矩陣，列重量為1，行重量為k，第一個子矩陣為階梯型，即第1行的k個1的列號是從(i-1)*k l到1*k，而其他子矩陣都是第一個子矩陣的隨機列置換，這樣每個子矩陣每行都有k個1，每列都有1個1。這種構造方法要求M必須是j的整數倍。
(20，3，4)LDPC碼的校驗矩陣
Gallager曾給出了一個碼長為20的規則(3，4）LDPC碼的校驗矩陣，如圖所示。圖中的第一個子矩陣就是一個階梯型矩陣，而第2個和第3個矩陣都是第一個子矩陣的列置換。
Gallager同時證明了隨機置換得到的GaHager LDPC碼的最小漢明距離能夠隨著碼長的增加而線性增加，而且在對稱無記憶信道中，採用最大似然解碼時，其誤碼率隨著碼長的增加而呈指數形式下降，這說明隨機置換得到的Gallager LDPC碼是一類相當好的碼。
但是，Gallager在構造LDPC碼時採用的是隨機置換，這就給實現帶來了麻煩，就需要大量的存儲單元來存儲校驗矩陣中這些1的位置。
2. 確定性結構的LDPC碼
確定性結構的DLPC碼也稱為准循環LDPC碼。相對於隨機結構的矩陣是很容易獲得的確定性結構的矩陣，這種矩陣可以通過更少的參數來定義LDPC碼。確定性結構的LDPC碼的構造方法基於「陣列碼」(Array Code)。陣列碼是用來檢測和糾正突發差錯的二維碼。
通過三個參數定義LDPC碼。一個基本參數p和兩個整數j和k。令H為jp*kp的矩陣，定義為：
LDPC碼
其中這里的I是p*p的單位陣，Bi.j是Ip*p的左循環移位Bm.n或右循環移位Bm.n的置換矩陣。顯然，H矩陣中1的分布就只與循環位數Bm.n有關。對LDPC碼的分析就可以轉換為對Bm.n的分析。
將各小矩陣的循環移動位數寫成一個矩陣為
LDPC碼
上面的校驗矩陣提供了一個可以用於SAP解碼的稀疏矩陣。而且，這個校驗矩陣結構上沒有四線循環。

⑷ 信道編碼技術及電子系統工程應用的探討論文

信道編碼技術及電子系統工程應用的探討論文

根據信道編碼理論及編碼、解碼方法和技術的發展，結合工程實際從理論到實踐進行了簡要的闡述。

隨著信息及信號傳輸技術的發展，應用電子領域也隨之擴大並得到發展。通過對信源編碼、信道編碼、編碼的方法，以及對壓縮後的信息進行糾錯編碼，以抗擊信道、網路及傳輸過程的誤碼或數據丟失，即信道編碼問題的系統認識與理解對實際工程應用具有重要的意義。從電子系統工程的應用角度，對相關知識的理解與應用體會更為深刻。在此，就實際應用中貫穿其中的相關知識及帶來的思考與啟發扼要介紹。

一、信道編碼理論及編、解碼問題

衡量任何一個信號通信系統性能優劣的基本因素是有效性和可靠性，有效性是信道傳輸信息的速度快慢，可靠性是信道傳輸信息的准確程度。在數字通信系統中，信源編碼是為了提高有效性，信道編碼是為了提高可靠性，而在一個通信系統中，有效性和可靠性是互相矛盾的，也是可以互換的。我們可以用降低有效性的辦法提高可靠性，也可以用用降低可靠性的辦法提高有效性。而糾錯編碼，即信道編碼問題是重點。

(一)編、解碼問題

信道編碼是以香農第二定理和香農第三定理為理論支持。在錯誤控制編碼方面，主要是糾錯線性分組碼與非分組的卷積碼。對於線性分組碼，採用增加冗餘碼作為監督碼，這樣編出的碼具有一定的檢錯和糾錯能力。在解碼方面，根據最大似然法解碼，判斷碼的漢明距離，找到漢明距離最小的碼，那就是在發送端傳輸過來的碼。編碼是一個比較抽象的概念，採用矩陣的描述方式表示編碼，將輸入的信息序列與生成矩陣相乘，那麼就可以得到編碼後的符號。在解碼方面，通過奇偶校驗矩陣就可以檢測解碼是否正確。

(二)關於卷積碼

卷積碼是編碼不一樣的領域，因為這種碼在判決時用到過去的信息，也就是說，它是需要記憶的。這也就是卷積碼得名的由來。卷積碼的編碼器由一個移位寄存器和相關邏輯電路組成，對每一個進入的信息幀，編碼器都產生一個碼字幀。當然，還可以畫編碼器的狀態圖，比較直觀表示編碼器根據輸入情況而變化。根據狀態圖可畫出網格圖;由網格圖很容易地知道卷積碼的距離，這是卷積碼解碼的一個依據。卷積碼用一個生成多項式矩陣表示，在編碼方面極為方便，編碼操作可以簡單地描述為信息量矩陣與生成矩陣的乘積。而更加嚴謹、方便地表達，則需要生成函數。通過修改狀態圖，很容易得到生成函數。對生成函數的級數展開，可以很直觀地得到漢明距離和輸入路徑的信息，最後還可以知道給定漢明距離全零路徑的數量。

(三)Turbo碼和LDPC碼

Turbo碼與LDPC碼是兩種性能接近香農極限的信道編碼。Turbo碼在低信噪比的情況下，性能比其他編碼要好。Turbo碼的優良性能在非實時數據通信方面被廣泛採用。Turbo碼是分組碼和卷積碼的「准」混合物。Turbo碼有並行級聯卷積碼、串列級聯卷積碼和混雜級聯卷積碼三種不同的排列。因為有交織器的存在，所以編碼器的糾錯能力很好。LDPC碼是一類可以用非常稀疏的校驗矩陣或二分圖定義的線性分組碼，其特點是：解碼演算法具有線性復雜度可採用並行迭代方式，具有解碼自校驗特性，在高信噪比條件下能有效降低解碼復雜度，提高誤比特率性能;可以滿足高性能信號通信要求。LDPC碼以最低的復雜度提供了最好的性能。這意味著在同等性能情況下， LDPC碼的復雜度只有Turbo碼的1/4。與Turbo碼相比，LDPC碼尤其是非規則LDPC碼具有非常出色的性能，優於迄今為止已知的其它編碼方式。LDPC碼與其它編碼相比還有一些獨特的優點：解碼可以完全並行，因此可以獲得更高的解碼速度;解碼器的復雜度大幅降低;解碼是可驗證的;非規則LDPC碼具有天然的不等錯誤保護能力。

二、從信道編碼定理看編、解碼方法的發展

(一)信道編、解碼方法的多樣性

信道編碼的'核心是「糾錯」;信道編、解碼的最終目的是實現信道與信號通信系統在可靠性指標下的優化。其方法是糾錯編碼，即抗干擾編碼。奇偶校驗碼是一種檢錯分組碼;由此原理派生出改進的：水平奇偶校驗碼、垂直奇偶校驗碼、群計數碼等。定比碼是一種只能發現錯誤的簡單檢錯碼，且需通過反向信道系統方能實現抗干擾。而重復碼是前向糾錯碼，也是一種最簡單的糾錯碼，實際應用較廣泛。而由漢明碼引出的線性分組碼是一種具有線性代數關系的編碼。在實際應用中，為得到希望的碼長和信息位長度，將信息位縮減而得到原碼的縮短碼。在漢明碼的基礎上增加一位監督元，則產生增余漢明碼或擴展漢明碼，使糾錯能力得到提高。而由完備碼產生的完備解碼、非完備解碼，則反映了分組碼的糾錯能力是全部用於糾錯，還是部分糾錯檢錯。循環碼是線性分組碼中重要的一類碼，從應用角度其編碼與解碼電路較為簡單，易於實現;且編、解碼方法方便、成熟。

(二)信道編、解碼方法的發展過程與啟示

不難看出，信道編碼的方法是豐富多彩的。也是漸進發展，逐步完善的過程。由此可見，理論指導是發展的方向。對信道編碼的理論支撐及方向的指引，使得信道編碼方法沿著豐富而日臻完善、接近而趨於極限的方向發展。從這一發展過程可以看出，任何一種新的或衍生的方法，都是有局限性的。但這種局限和不完善性，並不會阻礙新的方法的產生和發展。舊的矛盾解決的同時，新的矛盾又會出現。正如，糾錯檢錯能力的提高，對信息進行錯誤保護，以抵禦信道或網路等信息傳輸過程的干擾所產生的誤碼或數據丟失的同時，也將使編碼及信息傳輸效率降低。由於信道編碼增加了數據量，其結果只能是以降低傳送有用信息碼率為代價。因此，不同的編碼方式，其糾、檢錯的能力不同，編碼效率(信息傳輸效率)也有所不同。

三、從工程應用實例看理論支撐點

(一)智能住宅小區建設中信道編碼技術的應用

在工程中首次接觸的，應用於數字電視地面廣播(DTTB)的編碼調制方案中，涉及到：以多級分組乘積碼代替傳統的串列級聯編碼結構，提高了頻譜效率;同時採用一種多解析度星座圖，可在一個DTTB信道中提供3種級別的服務.在接收端採用基於MAX—LOG—MAP准則的迭代Turbo解碼演算法以獲得可靠接收。模擬結果表明，在視覺門限BER=3×10-6處，高優先順序碼流的比特信噪比約為7dB，適用於高可靠性的服務.中優先順序和低優先順序碼流可支持室外固定接收。由此，也加深了對並行級聯卷積碼的反饋迭代結構的理解。

(二)網路編碼與網路安全

在網路工程中，接觸到多址信道中聯合網路編碼和信道編碼的設計方案。該方案利用LDPC碼和網路編碼的線性特性以及軟輸入軟輸出模塊設計，不僅減少了編解碼的復雜度，而且提高了編解碼效率。同時，了解了網路——信道編碼分離定理，以及該定理成立的條件，即當網路中的信道是確定型廣播信道時，分離定理不成立。而信道安全編碼與網路安全編碼同樣重要，又有所區別。信道編碼問題，其核心是對傳送的信息進行錯誤保護，以抗擊信道或網路等信息傳輸媒介所帶來的誤碼或數據丟失。而網路中的通信安全是網路編碼研究的重要課題之一，網路安全編碼更側重於網路使用者信息及使用的安全層面。網路編碼技術的發展可以大幅度提高網路的吞吐量。

四、結束語

專業技術的專長與拓展並存，這是專業技術發展的必然趨勢。身處信息時代，信息科學是研究信息的獲取、傳輸以及應用的科學，是信息資源與技術開發及其推廣應用的理論基礎，是信息技術及信息產業的核心。通信工程、電子信息工程、計算機科學、計算機應用等眾多應用技術與信息科學、信息技術及信息產業息息相關。信道編碼從理論上要解決理想編碼器、解碼器的存在性問題，即解決信道能傳送的最大信息率的可能性和超過這個最大值時的傳輸問題;同時構造性的編碼方法以及這些方法能達到的性能界限。筒言之，通過信道編碼器和解碼器來實現的用於提高信道可靠性的理論和方法。