【正文】 第 4章 信道編碼技術(shù) 在維特比譯碼算法中 ,把匯聚在每個(gè)節(jié)點(diǎn)上的兩條路徑的對(duì)數(shù)似然函數(shù)累加值進(jìn)行比較 ,然后把具有較大對(duì)數(shù)似然函數(shù)累加值的路徑保存下來(lái) ,而丟棄另一條路徑 ,經(jīng)挑選后第 N級(jí)只留下 2 (N1) 條幸存路徑 ,選出的路徑連同它們的對(duì)數(shù)似然函數(shù)累加值一起被存儲(chǔ)起來(lái) 。 顯然 ,譯碼過程的計(jì)算量隨 L增加而呈指數(shù)增長(zhǎng) ,這在實(shí)際中難以實(shí)現(xiàn) ,因此只能采用次最佳的譯碼方法 。 但在給定 n,k和 N時(shí) ,無(wú)法得到自由距與卷積碼生成多項(xiàng)式之間的計(jì)算公式 ,必須逐個(gè)計(jì)算不同卷積碼的生成函數(shù) ,才能得到具有最大自由距的最好碼 。 由于卷積碼并不劃分碼組 ,因而以自由碼距作為糾錯(cuò)能力的度量更為合適 。 第 4章 信道編碼技術(shù) 圖 413 （ 2,1,3）卷積碼的狀態(tài)圖 a dcb1000 00 1011 0111 01狀態(tài)a ＝ 00b ＝ 01c ＝ 10d ＝ 11第 4章 信道編碼技術(shù) 假如利用圖 410所示的卷積碼編碼器對(duì)輸入序列110111001000進(jìn)行編碼 ,我們就可以用上述 3種方法當(dāng)中的任意一種來(lái)分析編碼器的輸出序列和狀態(tài)變化路徑 。 顯然 ,對(duì)于第 j個(gè)輸入位 ,就有 2j條分支 ,但是在 j=N≥ 3時(shí) ,樹狀圖的節(jié)點(diǎn)自上而下開始重復(fù)出現(xiàn)這 4種狀態(tài) 。 移位過程可能產(chǎn)生的各種序列可以用圖 411所示的樹狀圖來(lái)表示 。 整個(gè)編碼過程可以看成是輸入信息序列與信道編碼器的卷積 ,卷積碼即由此得名 。 因此 ,糾錯(cuò)碼譯碼器的復(fù)雜性主要取決于譯碼過程的第 （ 2） 步 。 當(dāng)傳輸中未發(fā)生錯(cuò)誤時(shí) ,接收的碼組與發(fā)送的碼組相同 ,即 A(x)=B(x),接收的碼組 B(x)必能被 g(x)整除； 若傳輸中發(fā)生了錯(cuò)誤 ,則 A(x) ≠ B(x), B(x)不能被 g(x)整除 。m(x)的次數(shù)必小于 n,用 xnk(xk+1) (451) 式 (451)表明 ,生成多項(xiàng)式 g(x)是 (xn+1)的一個(gè)因式 ,因此 ,為了確定生成多項(xiàng)式 ,必須首先對(duì) (xn+1)進(jìn)行因式分解 ,然后再用計(jì)算進(jìn)行篩選 , 第 4章 信道編碼技術(shù) 對(duì)于一個(gè) (n, k) 循環(huán)碼 ,其生成多項(xiàng)式應(yīng)該是 (xn+1)的一個(gè) (nk)次因子 , (n, k)g(x),乘上 (x+1)后得到生成多項(xiàng)式 ,可以構(gòu)造 (n, k1)循環(huán)碼 。 因?yàn)槿绻袃蓚€(gè) ,則由于碼的封閉性 ,把這兩個(gè)碼相加也應(yīng)該是一個(gè)碼組 ,且此碼組多項(xiàng)式的次數(shù)將小于 (nk),即出現(xiàn)連續(xù) “ 0”的個(gè)數(shù)將多于(k1)的情況 ,這與 (n, k)循環(huán)碼是線性碼的特性相違背 ,故是不可能的 。A(x)除以 (xn+1)的商 ,而 A（ i） (x)表示所得余式 。 循環(huán)碼是線性碼的一個(gè)重要子集 ,是目前研究得最成熟的一類碼 。 ei= 第 4章 信道編碼技術(shù) 在實(shí)踐中經(jīng)常會(huì)遇到的線性分組碼主要有以下兩種： 1. 漢明 (Hamming) 漢明碼既有二進(jìn)制的 ,也有非二進(jìn)制的 ,這里僅討論二進(jìn)制漢明碼的性質(zhì) 。 因此 ,可以用 a6a5a4a3a2a1a0表示這 7個(gè)碼元 ,用 S S S3表示由三個(gè)監(jiān)督方程計(jì)算得到的校正子 ,并假設(shè) S S S3三位校正子碼組與誤碼位置的關(guān)系如表 41所示 。 在圖中用 A和 B分別表示兩個(gè)碼距為 d0的碼組 ,當(dāng)碼組出現(xiàn) t個(gè)或小于 t個(gè)錯(cuò)誤時(shí) ,系統(tǒng)按照糾錯(cuò)方式工作；當(dāng)碼組出現(xiàn)大于 t個(gè)而小于 e個(gè)錯(cuò)誤時(shí) ,系統(tǒng)按照檢錯(cuò)方式工作； 若 A發(fā)生 t個(gè)錯(cuò)誤 ,B發(fā)生 e個(gè)錯(cuò)誤時(shí) ,既要糾 A的錯(cuò)誤 ,又要檢 B的錯(cuò)誤 ,則 A和 B之間距離應(yīng)大于 t+e,也就是滿足式 (429)。 對(duì)于二進(jìn)制碼組而言 ， 兩個(gè)碼組之間的模 2相加 ， 其不同的對(duì)應(yīng)位必為 1， 相同的對(duì)應(yīng)位必為 0， 因此 ， 兩個(gè)碼組之間模 2相加得到的信碼組的重量就是這兩個(gè)碼組之間的距離 。 除上述信道編碼的分類方法以外 ， 我們還可以將它分為二進(jìn)制信道編碼和多進(jìn)制信道編碼等等 。 卷積碼則不同 ， 雖然編碼后序列也可以分為碼組 ， 但監(jiān)督碼元不但與本信息碼元有關(guān) ， 而且與前面碼組的信息碼元也有約束關(guān)系 。 第 4章 信道編碼技術(shù) 在差錯(cuò)控制系統(tǒng)中 ， 信道編碼存在著多種形式 ， 同時(shí)信道編碼也有多種分類方法 。 顯然 ， 這種選擇重發(fā)系統(tǒng)傳輸效率最高 ， 但控制最為復(fù)雜 。 然后 ， 發(fā)送端把前面發(fā)出的信息重新傳送一次 ， 直到接收端認(rèn)為已經(jīng)正確為止 。 因此 ， 理想系統(tǒng)只能作為實(shí)際系統(tǒng)的理論極限 。 這是因?yàn)?n0 =0意味著信道無(wú)噪聲 ， 而 S=∞意味著發(fā)送功率達(dá)到無(wú)窮大 ， 顯然這在任何實(shí)際系統(tǒng)中都是很難實(shí)現(xiàn)的 。若 DMC的輸入選自 X符號(hào)集的 n個(gè)符號(hào) u1 , u2, … , un的序列 ,相應(yīng)的輸出選自 Y符號(hào)集的n個(gè)符號(hào) v1 , v2, … , vn的序列 ,則聯(lián)合條件概率為 P(Y1=v1,Y2=v2 , … , Yn=vn/X1=u1,X2=u2, … , Xn=un)= ??nkkk XYP1)/((42) 第 4章 信道編碼技術(shù) 這個(gè)表達(dá)式正是無(wú)記憶條件的數(shù)學(xué)表述。發(fā)信機(jī)由信道編碼器和調(diào)制器組成 ,接收機(jī)由解調(diào)器和信道譯碼器組成 ,在圖 41中 ,c和 g之間是編碼信道 ,屬于離散信道； d和 f之間是調(diào)制信道 ,屬于模擬信道。假設(shè)發(fā)送的符號(hào)集為 X={xi}， i=1, 2, … , L,有 L種符號(hào)； 接收符號(hào)集為 Y={yj}， j =1, 2, … , M,有 M種符號(hào)。 第 4章 信道編碼技術(shù) 信道容量定義為： )1( S N RlbBC ??? (b/s) 以上為著名的香農(nóng) (Shannon) 定理表達(dá)式， 它表明當(dāng)信號(hào)和作用在信道上的起伏噪聲的平均功率給定時(shí)， 在一定頻帶寬度 B的信道上，理論上單位時(shí)間內(nèi)可能傳輸信息量的極限值。 n0也趨于無(wú)窮大 。 因此 ， 前向糾錯(cuò)編碼需要附加較多的冗余碼元 ， 影響數(shù)據(jù)傳輸效率 ， 同時(shí)其編譯碼設(shè)備比較復(fù)雜 。 在返回重發(fā)系統(tǒng)中 ， 發(fā)送端無(wú)停頓地送出一個(gè)又一個(gè)碼組 ， 不再等待 ACK信號(hào) ， 一旦接收端發(fā)現(xiàn)錯(cuò)誤并發(fā)回NAK信號(hào) ， N組信號(hào) ， N的大小取決于信號(hào)傳遞及處理所帶來(lái)的延遲 ， 這種系統(tǒng)比停發(fā)等候重發(fā)系統(tǒng)有很大的改進(jìn) ， 在許多數(shù)據(jù)傳輸系統(tǒng)中得到應(yīng)用 。 在這種系統(tǒng)中接收端不但具有糾正錯(cuò)誤的能力 ， 而且對(duì)超出糾錯(cuò)能力的錯(cuò)誤有檢測(cè)能力 。 第 4章 信道編碼技術(shù) （ 3） 按照信息碼元和監(jiān)督碼元之間的約束方式不同 ， 可以將它分為分組碼和卷積碼 。 前者主要用于發(fā)生零星獨(dú)立錯(cuò)誤的信道 ， 而后者用于對(duì)付以突發(fā)錯(cuò)誤為主的信道 。 對(duì)于二進(jìn)制碼來(lái)講 ， 碼重W就是碼元中 1的數(shù)目 ， 例如碼組 10100的碼長(zhǎng) n=5， 碼重W=2。 在圖中用 A和 B分別表示兩個(gè)碼距為 d0的碼組 ,若 A發(fā)生 t個(gè)錯(cuò)誤 ,則 A就變成以 A為球心 ,t為半徑的球面上的碼組； 若 B發(fā)生 t個(gè)錯(cuò)誤 ,則 B就變成以 B為球心 ,t為半徑的球面上的碼組 。 線性分組碼是建立在代數(shù)群論基礎(chǔ)之上的 ,各許用碼的集合構(gòu)成了代數(shù)學(xué)中的群 ,它們的主要性質(zhì)如下： (1) 任意兩許用碼之和 （ 對(duì)于二進(jìn)制碼這個(gè)和的含義是模 2和 ） 仍為一許用碼 ,也就是說 ,線性分組碼具有封閉性； (2) 碼組間的最小碼距等于非零碼的最小碼重。G=［ a6 a5a4 a3］ G (438) 由式 (437)表示的生成矩陣形式被稱為典型生成矩陣 ,利用式 (438)產(chǎn)生的分組碼必為系統(tǒng)碼 ,也就是信息碼元保持不變 ,監(jiān)督碼元附加在其后 。 ??????1000第 4章 信道編碼技術(shù) (443) 式中 , Mn為 Mn的互補(bǔ)矩陣 ,按上述規(guī)律 M4和 就可以分別表示為 ???????nnnnn MMMMM2?????????????????????????????????1001001101011111,0110110010100000422222MMMMMMn(444) 4M第 4章 信道編碼技術(shù) 至此 ,可以利用 M4和 的行構(gòu)成一個(gè)碼長(zhǎng) n=4的二進(jìn)制線性分組碼 ,該碼由 8個(gè)碼組構(gòu)成 ,最小碼距為 d0=2。 為了利用代數(shù)理論研究循環(huán)碼 ,可以將碼組用代數(shù)多項(xiàng)式來(lái)表示 ,這個(gè)多項(xiàng)式被稱為碼多項(xiàng)式 ,對(duì)于許用循環(huán)碼A=(an1an2 … a1 a0),可以將它的碼多項(xiàng)式表示為 A(x)=an1xn1+an2xn2+… +a1x+a0 (445) 第 4章 信道編碼技術(shù) 對(duì)于二進(jìn)制碼組 ,多項(xiàng)式的每個(gè)系數(shù)不是 0就是 1,x僅是碼元位置的標(biāo)志 ,因此 ,我們這里并不關(guān)心 x 設(shè)上述循環(huán)許用碼組 A左循環(huán)一位得到的碼組記作 A（ 1） = (an2an3 … a0 an1