曾雪婷

(中國(guó)傳媒大學(xué) 理工學(xué)部，北京 100024)

重復(fù)累積碼幾種譯碼算法的研究

曾雪婷

(中國(guó)傳媒大學(xué) 理工學(xué)部，北京 100024)

介紹了一種可以進(jìn)行線性編碼、線性譯碼的好碼──重復(fù)累積碼，分析和推導(dǎo)了基于Tanner圖的三種譯碼算法，用MATLAB在高斯信道下對(duì)三種算法進(jìn)行仿真，對(duì)RA碼譯碼的結(jié)果進(jìn)行了比較。

重復(fù)累積碼；迭代譯碼；和積算法；最小和算法

1 引言

1998年，Divsalar D、Jin H等人提出了一種編碼Turbo-like碼，這種碼由一個(gè)碼率為1/q的重復(fù)碼和一個(gè)碼率為1、傳遞函數(shù)1/(1+D)為的卷積碼構(gòu)成，即重復(fù)累積碼，簡(jiǎn)稱RA碼(Repeat Accumulate Code)。他們嚴(yán)格證明了當(dāng)信息長(zhǎng)度k→∞時(shí)，RA碼在無(wú)記憶二進(jìn)制信道上最大似然譯碼的誤碼率趨于0[1]。2000年，Jin H提出了不規(guī)則RA(Irregular Repeat Accumulate，IRA)碼，并證明了在AWGN信道上通過(guò)迭代譯碼算法，IRA碼能實(shí)現(xiàn)線性時(shí)間譯碼并且信道的傳輸速率能非常接近香農(nóng)理論極限容量[2]。RA碼不僅可以看做特殊的串行Turbo碼，也可以看做LDPC碼，可以用奇偶校驗(yàn)矩陣和Tanner圖來(lái)描述并且能夠線性譯碼?？傊琑A碼是一種結(jié)構(gòu)簡(jiǎn)單、編碼復(fù)雜度低，能實(shí)現(xiàn)線性時(shí)間編碼和線性時(shí)間譯碼的好碼。

2 重復(fù)累積碼的結(jié)構(gòu)

RA碼編碼器由重復(fù)器、交織器、累加器組成，其結(jié)構(gòu)如圖1所示。

圖1

RA碼的校驗(yàn)矩陣H=[H1H2]可以直接由編碼器確定，其中H1的行重為常數(shù)，它的非零元素的位置由交織器決定，對(duì)應(yīng)Tanner圖中信息節(jié)點(diǎn)與校驗(yàn)節(jié)點(diǎn)之間的連接；H2為雙斜對(duì)角滿秩矩陣，由累加器決定，對(duì)應(yīng)Tanner圖中奇偶節(jié)點(diǎn)與校驗(yàn)節(jié)點(diǎn)之間的連接。改變交織器的行數(shù)、列數(shù)還有累加器的累加因子，可以構(gòu)造出不同碼長(zhǎng)、不同碼率的RA碼。本文研究的譯碼方法是和積算法及在和積算法的基礎(chǔ)上衍生出來(lái)的算法，因此，需要建立編碼器與校驗(yàn)矩陣的關(guān)系，從而在簡(jiǎn)單編碼的同時(shí)實(shí)現(xiàn)線性譯碼。

3 重復(fù)累積碼的幾種譯碼算法

3.1 和積算法

對(duì)RA碼進(jìn)行軟判決譯碼可以通過(guò)基于Tanner圖的和積算法(Sum-Product Algorithm，SPA)來(lái)實(shí)現(xiàn)。Tanner圖中的每個(gè)節(jié)點(diǎn)沿著Tanner圖的邊反復(fù)交換信息和更新信息，直到解碼后的比特信息滿足校驗(yàn)矩陣的約束條件。整個(gè)譯碼過(guò)程中在Tanner圖的邊上傳遞的信息為概率密度的對(duì)數(shù)似然比(Log-Likelihood Ratios，LLR)，其定義如(1)式所示，其中x和y分別為發(fā)送的碼字和接收的碼字。

(1)

標(biāo)準(zhǔn)的和積譯碼算法可以分為兩個(gè)部分：校驗(yàn)節(jié)點(diǎn)的更新和變量節(jié)點(diǎn)的更新。

(1)校驗(yàn)節(jié)點(diǎn)的更新：在第q次迭代中，每個(gè)校驗(yàn)節(jié)點(diǎn)接收到與其相連的所有變量節(jié)點(diǎn)發(fā)出的信息后按(3)式更新該校驗(yàn)節(jié)點(diǎn)的信息。

(2)

(2)變量節(jié)點(diǎn)的更新：在第q次迭代中，每個(gè)變量節(jié)點(diǎn)接收到與其相連的所有校驗(yàn)節(jié)點(diǎn)發(fā)出的信息后按(2)式更新該變量節(jié)點(diǎn)的信息。

(3)

(4)

(5)

若迭代次數(shù)超過(guò)最大譯碼次數(shù)或滿足?HT=0時(shí)停止迭代，輸出譯碼結(jié)果。

3.2 最小和算法

在和積算法中，在計(jì)算對(duì)數(shù)似然比時(shí)要用到乘法操作和非線性的雙曲正切函數(shù)的反函數(shù)，計(jì)算復(fù)雜度的增加帶來(lái)了譯碼時(shí)間和硬件實(shí)現(xiàn)的成本的增加。在最小和算法(Min-Sum Algorithm，MSA)中，利用了雙正切函數(shù)的單調(diào)性，在更新校驗(yàn)節(jié)點(diǎn)時(shí)用φ(min(x))來(lái)近似代替∑φ(x)，用|x|來(lái)替換φ(φ(x))，重寫(xiě)(2)式，有：

(6)

校驗(yàn)節(jié)點(diǎn)的每一次更新只需要比較運(yùn)算和加法運(yùn)算，這樣以對(duì)量化噪聲不敏感為代價(jià)，使得算法的復(fù)雜度明顯地降低。

最小和算法消息傳遞的過(guò)程順序與和積算法相同，每次迭代時(shí)，變量節(jié)點(diǎn)先向校驗(yàn)節(jié)點(diǎn)發(fā)送信息，更新校驗(yàn)節(jié)點(diǎn)，然后校驗(yàn)節(jié)點(diǎn)向變量節(jié)點(diǎn)發(fā)送信息更新變量節(jié)點(diǎn)，同時(shí)計(jì)算每一個(gè)信息比特的后驗(yàn)概率作出判決，最后觀察被譯出的碼字比特是否滿足所有校驗(yàn)約束，滿足則輸出碼字，不滿足則進(jìn)行下一次迭代。

3.3 分層譯碼

分層譯碼算法(Layered Decoding)也是在和積算法的基礎(chǔ)上進(jìn)一步改進(jìn)，分層算法的主要思路就是將RA碼的校驗(yàn)矩陣看做一組串聯(lián)的水平層進(jìn)行逐層譯碼，將上一層得到的后驗(yàn)概率信息傳到下一層參與計(jì)算。具體算法可表示為：

forq=1：I

for=k=1：L

end

ifcqHT=0thengotoEndofDecoding

end

EndofDecoding

其中I為最大迭代次數(shù)，L為層數(shù)。由上述的算法可知，分層譯碼將對(duì)整個(gè)校驗(yàn)矩陣的譯碼拆分成不同層來(lái)進(jìn)行譯碼，這樣能使最新更新的外部信息即該層的對(duì)數(shù)似然比能馬上傳遞到下一層并參與計(jì)算，層與層之間的迭代使得總的迭代次數(shù)減少，從而速度得到進(jìn)一步提升，硬件開(kāi)銷(xiāo)也相對(duì)減少。

4 仿真結(jié)果與分析

本文采用圖2中的數(shù)字通信系統(tǒng)用MATLAB進(jìn)行仿真。

圖2

設(shè)置信息比特長(zhǎng)度分別設(shè)為300和3000，幀長(zhǎng)為20，碼率為2/3，最大迭代次數(shù)為50，在AWGN信道下進(jìn)行BPSK調(diào)制的RA碼的誤碼率仿真如圖3和圖4所示。在信噪比較低的情況下，相同誤碼率下，分層譯碼算法相對(duì)于和積譯碼算法與最小和算法表現(xiàn)出更強(qiáng)的糾錯(cuò)能力，由于最小和算法是和積譯碼算法的近似，最小和算法在低信噪比下的糾錯(cuò)能力略差。但是，在較高的信噪比下，和積譯碼算法的誤碼率相對(duì)于其他兩個(gè)譯碼算法有了明顯的下降，表現(xiàn)出優(yōu)秀的糾錯(cuò)能力，并且沒(méi)有出現(xiàn)錯(cuò)誤平底效應(yīng)。

圖3

圖4

圖5顯示了在不同信噪比下不同譯碼算法進(jìn)行一次譯碼所需要的時(shí)間。由圖可知，運(yùn)行一次譯碼所需的時(shí)間隨著信噪比的增加而減少。由于最小和算法將和積算法中大量的乘法和非線性函數(shù)轉(zhuǎn)換為加法和比較運(yùn)算，提高了譯碼的速度，不論碼長(zhǎng)長(zhǎng)短最小和算法進(jìn)行一次譯碼的時(shí)間均比和積算法短，而分層譯碼在碼長(zhǎng)較短時(shí)通過(guò)層與層之間的迭代縮短了總的迭代次數(shù)使得完成一次譯碼的時(shí)間在最小和算法的基礎(chǔ)上進(jìn)一步縮短，但是在碼長(zhǎng)較長(zhǎng)時(shí)便失去了譯碼速度快優(yōu)勢(shì)。

圖5

5 總結(jié)

本文對(duì)重復(fù)累積碼的幾種譯碼算法進(jìn)行了研究，對(duì)這三種算法在高斯信道下進(jìn)行了仿真，通過(guò)改變不同的參數(shù)來(lái)比較三種譯碼算法的性能和復(fù)雜度。在硬件實(shí)現(xiàn)時(shí)，可以根據(jù)實(shí)際需要選擇適當(dāng)?shù)淖g碼算法。此外，重復(fù)累積碼的譯碼算法在復(fù)雜度和誤碼性能上還有更多的提升空間。

[1]Jin H.Analysis and design of Turbo-like codes [D].California：California Institute of Technology，2001.

[2]Khandekar H J A，McEliece R.Irregular Repeat Accumulate Codes[C].Proc 2nd Int Conf on Turbo codes，2000.

[3]高宏峰.重復(fù)累積碼及其在通信系統(tǒng)中的應(yīng)用[M].北京：科學(xué)出版社，2007.

[4]賀鶴云.LDPC碼基礎(chǔ)與應(yīng)用[M].北京：人民郵電出版社，2009.

[5]劉東華.信道編碼與MATLAB仿真[M].北京：電子工業(yè)出版社，2014.

(責(zé)任編輯：王謙)

Research of Different RA Decoding Algorithms

ZENG Xue-ting

(Faculty of Science and Technology，Communication University of China，Beijing 100024，China)

This paper introduces a kind of good code called repeat accumulate code which can be linear coding and linear decoding.Analysis and derivation of three decoding algorithms are made based on Tanner graph.We simulate the three RA decoding algorithms in the AWGN channel by MATLAB and make comparisons of the different decoding performance.

repeat accumulate code；iteration decoding；sum-product；min-sum

2015-04-21

曾雪婷(1991-)，女(漢族)，湖北潛江人，中國(guó)傳媒大學(xué)碩士研究生.E-mail：13261116602@189.cn

TN919.3+3

A

1673-4793(2015)06-0040-04