卷積編解碼及糾錯性能驗證報告

❶ 糾錯碼的基本原理和性能參數

糾錯碼能夠檢錯或糾錯，主要是靠碼字之間有較大的差別。這可用碼字之間的漢明距離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碼也被廣泛應用於光碟的存儲中。
大多數糾錯碼是設計來糾隨機誤碼的，可以通過交織的方法使它適用於對突發誤碼的糾錯。交織是一種使得集中出現的突發誤碼在解碼時進行分散化的措施，從而使其不超出糾錯碼的糾錯能力范圍。 卷積碼不對信息序列進行分組編碼，它的校驗元不僅與當前的信息元有關，而且同以前有限時間段上的信息元有關。卷積碼在編碼方法上尚未找到像分組碼那樣有效的數學工具和系統的理論。但在解碼方面，不論在理論上還是實用上都超過了分組碼，因而在差錯控制和數據壓縮系統中得到廣泛應用。

❷ 卷積碼的解碼方法

若信道干擾序列為，其中。接收序列為
其中和。這里「+」為模 2 運算（q=p元碼按模p運算）。解碼就是根據編碼規則和信道干擾的統計特性，對信息序列u(x）作出估值的方法。常用的有三類解碼方法，即代數解碼、維特比解碼和序貫解碼。
⒈代數
代數解碼是將卷積碼的一個編碼約束長度的碼段看作是[n0(m+1），k0(m+1)]線性分組碼，每次根據（m+1）分支長接收數字，對相應的最早的那個分支上的信息數字進行估計，然後向前推進一個分支。上例中信息序列 =(10111），相應的碼序列 c=(11100001100111）。若接收 序列R=(10100001110111），先根據R的前三個分支（101000）和碼樹中前三個分支長的所有可能的 8條路徑(000000…）、（000011…）、（001110…）、（001101…）、（111011…）、（111000…）、（110101…）和（110110…）進行比較，可知（111001）與接收序列（101000）的距離最小，於是判定第 0分支的信息數字為 0。然後以R的第 1～3分支數字（100001）按同樣方法判決，依此類推下去，最後得到信息序列的估值為=(10111），遂實現了糾錯。這種解碼法，解碼時採用的接收數字長度或解碼約束長度為（m+1)n0，所以只能糾正不多於（dmin-1)/2個錯誤（n長上的）。實用中多採用反饋擇多邏輯解碼法實現。
⒉維特比
維特比解碼過程
維特比解碼是根據接收序列在碼的格圖上找出一條與接收序列距離（或其他量度）為最小的一種演算法。它和運籌學中求最短路徑的演算法相類似。若接收序列為R=(10100101100111），解碼器從某個狀態，例如從狀態ɑ出發，每次向右延伸一個分支（對於l<L，從每個節點出發都有 2=2種可能的延伸，其中L是信息序列段數，對l≥L，只有一種可能），並與接收數字相應分支進行比較，計算它們之間的距離，然後將計算所得距離加到被延伸路徑的累積距離值中。對到達每個狀態的各條路徑（有2=2條）的距離累積值進行比較，保留距離值最小的一條路徑，稱為倖存路徑（當有兩條以上取最小值時，可任取其中之一），解碼過程如圖。圖中標出到達各級節點的倖存路徑的距離累積值。對給定 R的估值序列為=(10111）。這種演算法所保留的路徑與接收序列之間的似然概率為最大，所以又稱為最大似然解碼。這種解碼的解碼 約束長度常為編碼約束長度的數倍，因而可以糾正不多於（df/2）個錯誤。
維特比解碼器的復雜性隨m呈指數增大。實用中m不大於10。它在衛星和深空通信中有廣泛的應用。在解決碼間串擾和數據壓縮中也可應用。
⒊ 序貫解碼
序貫解碼是根據接收序列和編碼規則，在整個碼樹中搜索（既可以前進，也可以後退）出一條與接收序列距離（或其他量度）最小的一種演算法。由於它的解碼器的復雜性隨m值增大而線性增長，在實用中可以選用較大的m值（如20～40）以保證更高的可靠性。許多深空和海事通信系統都採用序貫解碼。

❸ 什麼是卷積編碼

卷積碼是將k個信息比特編成n個比特，但k和n通常很小，特別適合以串列形式進行傳輸，時延小。
卷積碼定義：

若以（n,k,m）來描述卷積碼，其中k為每次輸入到卷積編碼器的bit數，n為每個k元組碼字對應的卷積碼輸出n元組碼字，m為編碼存儲度，也就是卷積編碼器的k元組的級數，稱m+1= K為編碼約束度m稱為約束長度。卷積碼將k元組輸入碼元編成n元組輸出碼元，但k和n通常很小，特別適合以串列形式進
卷積碼的編碼器
行 傳輸，時延小。與分組碼不同，卷積碼編碼生成的n元組元不僅與當前輸入的k元組有關，還與前面m-1個輸入的k元組有關，編碼過程中互相關聯的碼元個數為n*m。卷積碼的糾錯性能隨m的增加而增大，而差錯率隨N的增加而指數下降。在編碼器復雜性相同的情況下，卷積碼的性能優於分組碼。
編碼原理：
卷積碼編碼器
以二元碼為例，編碼器如圖。輸入信息序列為u=(u0，u1，…），其多項式表示為u(x)=u0+u1x+…+ulxl+…。編碼器的連接可用多項式表示為g(1,1)(x)=1+x+x2和g(1,2)(x)=1+x2，稱為碼 的子生成多項式。它們的系數矢量g(1,1)=(111）和g(1,2)=(101）稱作碼的子生成元。以子生成多項式為陣元構成的多項式矩陣G(x)=[g(1,1)(x),g(1,2)(x)]，稱為碼的生成多項式矩陣。

❹ 2:1卷積碼 c語言編解碼

charinput[10]={0,0,1,1,1,0,1,1,1,1};
charoutput[5]={0};

intr1=0,r2=0;
inti;

for(i=0;i<5;i++)
{
output[i]=(input[2*i]+r1+r2)&1;
r2=r1;
r1=output[i];
}

for(i=0;i<5;i++)
printf("%d",output[i]);
printf("
");

❺ 卷積碼糾錯最好的是哪個

卷積碼是一種性能優越的信道編碼，它的編碼器和解碼器都比較容易實現，同時它具有較強的糾錯能力，隨著糾錯編碼理論的研究不斷深入，卷積碼的實際應用越來越廣泛。本文不僅對卷積碼和卷積碼的編解碼有一個簡單的介紹，而且對（2 1 2）卷積碼進行了編碼和解碼，最後，通過MATLAB對（2 1 2）卷積碼進行編譯的模擬，對模擬結果進行了解釋。

❻ 題目，信道編碼和信源編碼有什麼不同，糾錯碼能檢錯和糾錯的原因

糾錯碼(error correcting code)，在傳輸過程中發生錯誤後能在收端自行發現或糾正的碼。僅用來發現錯誤的碼一般常稱為檢錯碼。為使一種碼具有檢錯或糾錯能力，須對原碼字增加多餘的碼元，以擴大碼字之間的差別 ，即把原碼字按某種規則變成有一定剩餘度（見信源編碼）的碼字，並使每個碼字的碼之間有一定的關系。關系的建立稱為編碼。碼字到達收端後，可以根據編碼規則是否滿足以判定有無錯誤。當不能滿足時，按一定規則確定錯誤所在位置並予以糾正。糾錯並恢復原碼字的過程稱為解碼。檢錯碼與其他手段結合使用，可以糾錯。

糾錯編碼又稱信道編碼，它與信源編碼是信息傳輸的兩個方面。它們之間存在對偶的關系。應用信道解碼直接對一些自然信息進行處理，可以去掉剩餘度，以達到壓縮數據的目的。
為了使一種碼具有檢錯或糾錯能力，必須對原碼字增加多餘的碼元，以擴大碼字之間的差別，使一個碼字在一定數目內的碼元上發生錯誤時，不致錯成另一個碼字。准確地說，即把原碼字按某種規則變成有一定剩餘度的碼字，並使每個碼字的碼元間有一定的關系。關系的建立稱為編碼。碼字到達收端後，用編碼時所用的規則去檢驗。如果沒有錯誤，則原規則一定滿足，否則就不滿足。由此可以根據編碼規則是否滿足以判定有無錯誤。當不能滿足時，在可糾能力之內按一定的規則確定錯誤所在的位置，並予以糾正。糾錯並恢復原碼字的過程稱為解碼；碼元間的關系為線性時，稱為線性碼；否則稱為非線性碼。檢錯碼與其他手段結合使用，可以糾錯。檢錯反饋重發系統（ARQ系統）就是一例。
在構造糾錯碼時，將輸入信息分成k位一組以進行編碼。若編出的校驗位僅與本組的信息位有關，則稱這樣的碼為分組碼。若不僅與本組的k個信息位有關，而且與前若干組的信息位有關，則稱為格碼。這種碼之所以稱為格碼，是因為用圖形分析時它象籬笆或格架。線性格碼在運算時為卷積運算，所以叫卷積碼。

❼ 糾錯編碼大作業相關資料

趙哥太折磨人了。讓你們做這么多的大作業，慘不忍睹啊。

❽ 採用卷積編碼器當輸入信息位10110時輸出編碼位多少

參考資料：http://hi..com/wuruide/blog/item/33d28bbf1b34940818d81f26.html
在一個二進制分組碼（n,k）當中，包含k個信息位，碼組長度為n，每個碼組的（n-k）個校驗位僅與本碼組的k個信息位有關，而與其它碼組無關。為了達到一定的糾錯能力和編碼效率（＝k/n），分組碼的碼組長度n通常都比較大。編解碼時必須把整個信息碼組存儲起來，由此產生的延時隨著n的增加而線性增加。
為了減少這個延遲，人們提出了各種解決方案，其中卷積碼就是一種較好的信道編碼方式。這種編碼方式同樣是把k個信息比特編成n個比特，但k和n通常很小，特別適宜於以串列形式傳輸信息，減小了編碼延時。
與分組碼不同，卷積碼中編碼後的n個碼元不僅與當前段的k個信息有關，而且也與前面（N-1）段的信息有關，編碼過程中相互關聯的碼元為nN個。因此，這N時間內的碼元數目nN通常被稱為這種碼的約束長度。卷積碼的糾錯能力隨著N的增加而增大，在編碼器復雜程度相同的情況下，卷段積碼的性能優於分組碼。另一點不同的是：分組碼有嚴格的代數結構，但卷積碼至今尚未找到如此嚴密的數學手段，把糾錯性能與碼的結構十分有規律地聯系起來，目前大都採用計算機來搜索好碼。
下面通過一個例子來簡要說明卷積碼的編碼工作原理。正如前面已經指出的那樣，卷積碼編碼器在一段時間內輸出的n位碼，不僅與本段時間內的k位信息位有關，而且還與前面m段規定時間內的信息位有關，這里的m＝N-1通常用（n，k，m）表示卷積碼（注意：有些文獻中也用（n，k，N）來表示卷積碼）。圖8-8就是一個卷積碼的編碼器，該卷積碼的n = 2，k = 1，m = 2，因此，它的約束長度nN = n×(m+1) = 2×3 = 6。
（2，1，2）卷集碼編碼器
在圖8-8中，與為移位寄存器，它們的起始狀態均為零。、與、、之間的關系如下：
（8-41）
假如輸入的信息為D = [11010]，為了使信息D全部通過移位寄存器，還必須在信息位後面加3個零。表8-9列出了對信息D進行卷積編碼時的狀態。
表8-9 信息D進行卷積編碼時的狀態 輸入信息D
1
1
0
1
0
0
0
0
b3b2
0 0
0 1
1 1
1 0
0 1
1 0
0 0
0 0
輸出C1C2
1 1
0 1
0 1
0 0
1 0
1 1
0 0
0 0
描述卷積碼的方法有兩類，也就是圖解表示和解析表示。解析表示較為抽象難懂，而用圖解表示法來描述卷積碼簡單明了。常用的圖解描述法包括樹狀圖、網格圖和狀態圖等。基於篇幅原因這里就不詳細介紹了。
卷積碼的解碼方法可分為代數解碼和概率解碼兩大類。代數解碼方法完全基於它的代數結構，也就是利用生成矩陣和監督矩陣來解碼，在代數解碼中最主要的方法就是大數邏輯解碼。概率解碼比較常用的有兩種，一種叫序列解碼，另一種叫維特比解碼法。雖然代數解碼所要求的設備簡單，運算量小，但其解碼性能（誤碼）要比概率解碼方法差許多。因此，目前在數字通信的前向糾錯中廣泛使用的是概率解碼方法。