糾錯(cuò)碼Lecture6-卷積碼(I)

Lecture6

卷積碼(I)2內(nèi)容基本概念矩陣和多項(xiàng)式描述初始截段碼對(duì)偶碼與透明碼伴隨式計(jì)算與一般譯碼3基本概念分組碼的特點(diǎn)：分組碼編碼時(shí)，本組的n-k個(gè)校驗(yàn)元僅與本組的k個(gè)信息元有關(guān)，而與其它各組碼元無關(guān)。分組碼譯碼時(shí)，也僅從本碼組中的碼元內(nèi)提取有關(guān)譯碼信息，而與其它各組無關(guān)。卷積碼的特點(diǎn)：卷積碼編碼中，本組的n0-k0個(gè)校驗(yàn)元不僅與本組的k0個(gè)信息元有關(guān)，而且還與以前各時(shí)刻輸入至編碼器的信息組有關(guān)。同樣，在卷積碼譯碼過程中，不僅從此時(shí)刻收到的碼組中提取譯碼信息，而且還要利用以前或以后各時(shí)刻收到的碼組中提取有關(guān)信息。卷積碼編碼器

卷積碼每組的信息位k0和碼長(zhǎng)n0，通常比分組碼的k和n要小。二進(jìn)制卷積碼編碼器(3,1,2)卷積碼編碼器5卷積碼的定義一般將卷積碼標(biāo)記為(n0,k0,m)碼，其中n0：每時(shí)刻編碼器輸出的碼元個(gè)數(shù)；其集合稱為卷積碼的一個(gè)碼段或子組k0：每時(shí)刻編碼器輸入的信息位個(gè)數(shù)m：編碼存貯；m+1稱為編碼約束度，它表示編碼過程中互相約束的子碼個(gè)數(shù)；n0(m+1)稱為編碼約束長(zhǎng)度，表示編碼過程中互相約束的碼元個(gè)數(shù)碼率：R=k0/n0圖1為一個(gè)(3,1,2)卷積碼編碼器mp2p1圖1.(3,1,2)卷積碼編碼器6卷積碼的生成矩陣圖1的生成矩陣設(shè)圖1編碼器的初始狀態(tài)為全0，若輸入的信息序列M=(100…)則輸出碼序列為C=(111,010,001,000,…)。碼序列中第m+1段以后，后面各段取值均為0。若M=(111…)=(100…)+(010…)+(001…)+…，則有C=(111,010,001,000,…)+(000,111,010,001,000,…)+(000,000,111,010,001,000,…)+…C=MG∞基本生成矩陣7卷積碼的生成矩陣子生成元其中，gi,j表示第i個(gè)信息位對(duì)當(dāng)前及后續(xù)m個(gè)子碼的第j個(gè)碼元的影響生成多項(xiàng)式矩陣

維矩陣G(D)表示：卷積碼碼字中，每一段子碼的n0個(gè)碼元與k0個(gè)信息位之間的關(guān)系卷積碼的設(shè)計(jì)8Example1已知(2,1,3)碼的子生成元為1求出該碼的G(D)和G矩陣2畫出該碼的編碼器3求出相應(yīng)于信息序列M=(101)的碼序列4判斷此碼是否是系統(tǒng)碼Problemformulation9Example1Step1Step2DD

D＋＋c1c2m10Example1Step3Step4非系統(tǒng)碼11Example2Mi(1)Mi(2)ci(2)ci(1)ci(3)(3,2,2)卷積編碼器Problemformulation一個(gè)(3,2,2)系統(tǒng)卷積碼的編碼器如下圖所示，請(qǐng)給出該碼的的子生成元、基本生成矩陣、生成矩陣和生成矩陣多項(xiàng)式12Example2Step1Step2Step313Step4Example214卷積碼的生成矩陣（n0，k0，m）卷積碼生成矩陣G∞的一般形式為15卷積碼的生成矩陣基本生成矩陣

式中，gi（i=0,1,2,…，m）是一個(gè)k0×n0階陣，而空白的地方全為0。g∞共有k0個(gè)生成元每一個(gè)生成元g(j)的子生成元為16卷積碼的生成多項(xiàng)式矩陣因而相應(yīng)的生成多項(xiàng)式矩陣17系統(tǒng)卷積碼的生成矩陣若(n0,k0,m)是一個(gè)系統(tǒng)卷積碼，則g∞、G∞和G(D)分別為18系統(tǒng)卷積碼的生成多項(xiàng)式矩陣其中是一個(gè)以生成元為元素的k0×(k0-n0)階矩陣19卷積碼的校驗(yàn)矩陣卷積碼的校驗(yàn)矩陣矩陣20卷積碼的校驗(yàn)多項(xiàng)式矩陣

類似于碼的生成多項(xiàng)式矩陣G(D),也可以定義碼的校驗(yàn)多項(xiàng)式矩陣H(D)

式中為碼的子校驗(yàn)元，通常它也是一個(gè)次數(shù)小于m的多項(xiàng)式。由可以求出每個(gè)子校驗(yàn)元。21系統(tǒng)卷積碼的校驗(yàn)矩陣當(dāng)卷積碼為系統(tǒng)碼時(shí)，根據(jù),此時(shí)的校驗(yàn)矩陣為

定義碼的基本校驗(yàn)矩陣為22系統(tǒng)卷積碼的校驗(yàn)多項(xiàng)式矩陣23Example2(continued)24Example2(continued)25Example2(continued)26初始截段碼定義編碼器初始狀態(tài)全為0時(shí)，編碼器輸出碼序列的前m+1段子碼所組成的碼字，稱為卷積碼的初始截段碼字，以表示，其中而以表示在同一時(shí)間段內(nèi)輸入至編碼器的信息序列。其中所有初始截段碼字的集合構(gòu)成一個(gè)((m+1)n0,(m+1)k0)線性碼27初始截段碼生成矩陣和校驗(yàn)矩陣基本校驗(yàn)矩陣基本生成矩陣28系統(tǒng)碼的對(duì)偶碼系統(tǒng)碼情況下,(n0,k0,m)碼的29系統(tǒng)碼的對(duì)偶碼相應(yīng)的(n0,n0-k0,m)對(duì)偶碼的30透明碼如果(n0,k0,m)卷積碼的每個(gè)子生成元中有奇數(shù)項(xiàng)，則稱為透明碼。透明碼的每個(gè)碼字的補(bǔ)碼也是該碼的一個(gè)碼字。(2,1,2)碼的生成矩陣,它的兩個(gè)生成元有奇數(shù)項(xiàng)。若,則碼序列它的補(bǔ)碼也是碼的一個(gè)碼字，因此該碼是透明碼。31伴隨式計(jì)算與一般譯碼

卷積碼的譯碼代數(shù)譯碼

概率譯碼

代數(shù)譯碼

與分組碼所定義的伴隨式相同，設(shè)發(fā)送的半無限長(zhǎng)碼序列為C∞，信道的半無限長(zhǎng)錯(cuò)誤圖樣為E∞，則接收到的半無限長(zhǎng)序列R∞=C∞+E∞。定義以下半無限長(zhǎng)序列為R∞的伴隨式。32伴隨式多項(xiàng)式若僅檢驗(yàn)接收序列中連續(xù)m+1段以內(nèi)的校驗(yàn)關(guān)系，則(n0,k0,m)碼的伴隨式定義為相應(yīng)的伴隨式多項(xiàng)式定義為33伴隨式多項(xiàng)式式中:

稱Si(D)為子伴隨式多項(xiàng)式序列。由此可知，伴隨式是一個(gè)有(m+1)(n0-k0)個(gè)分量的序列，它反映了編碼約束長(zhǎng)度內(nèi)有關(guān)錯(cuò)誤圖樣的信息。34系統(tǒng)卷積碼代數(shù)譯碼的基本概念

卷積碼的譯碼問題就是從收到的序列R(D)=C(D)+E(D)中，確定出發(fā)送的碼序列C(D)或相應(yīng)的信息序列M(D)，這相當(dāng)于要求譯碼器首先計(jì)算伴隨式S(D)，然后由S(D)確定錯(cuò)誤圖樣，最后得到了已經(jīng)糾正過的序列，它可能與原發(fā)送的序列相同，也可能不同。若，說明譯碼產(chǎn)生了錯(cuò)誤。35系統(tǒng)卷積碼的代數(shù)譯碼系統(tǒng)卷積碼的一般代數(shù)譯碼器的框圖錯(cuò)誤圖樣檢測(cè)器……伴隨式寄存器……修正伴隨式伴隨式計(jì)算電路輸入R(D)-……信息元緩沖寄存器36系統(tǒng)卷積碼的代數(shù)譯碼

(1)由收到的序列R中，分成兩個(gè)序列，信息序列M和校驗(yàn)序列P。M序列送入信息緩存寄存器寄存，同時(shí)送入伴隨式計(jì)算電路(它就是一個(gè)與發(fā)端相同的編碼器)計(jì)算新的校驗(yàn)元，并與收到的校驗(yàn)元序列進(jìn)行比較，得到伴隨式寄存在伴隨式寄存器中。(2)當(dāng)接收完第m+1段子組后，伴隨式寄存器中的伴隨式送到錯(cuò)誤圖樣檢測(cè)電路，以確定此時(shí)刻前第m個(gè)時(shí)間單位內(nèi)，收到的子組中的信息位內(nèi)的錯(cuò)誤圖樣 。這時(shí)第0子組的信息元已移至信息元存儲(chǔ)器的最右邊，與錯(cuò)誤圖樣相減后就得到了已糾正過的第0子組內(nèi)的信息元。若與原發(fā)送的信息元 相同，則認(rèn)為譯碼無錯(cuò)；否則有錯(cuò)。37系統(tǒng)卷積碼的代數(shù)譯碼

(3)由卷積碼的編碼過程可知，第0子組的信息元，對(duì)其后m段子碼中的校驗(yàn)元均有約束關(guān)系，因而為了消除第0子組中的錯(cuò)誤對(duì)以后m段子組的影響，充分發(fā)揮碼的糾錯(cuò)能力，就反饋一個(gè)信號(hào)給伴隨式寄存器以修正伴隨式，消除第0子組內(nèi)錯(cuò)誤對(duì)以后子組的影響。