分組碼與卷積信道碼.ppt

分組碼與卷積信道碼讀書報(bào)告,專業(yè)：通信與信息系統(tǒng)學(xué)號(hào)：0820080087姓名：顧杰,第八章：分組碼與卷積信道碼,本章主要內(nèi)容：1、線性分組碼2、卷積碼3、*帶限信道的編碼調(diào)制-網(wǎng)格編碼調(diào)制,什么是線性分組碼？,若編碼規(guī)則僅局限在本碼組之內(nèi)，即本碼組的校驗(yàn)元僅與本碼組的信息元相關(guān)，則稱這類碼為分組碼。對(duì)于分組碼，如果校驗(yàn)元和信息元的關(guān)系是一種線性關(guān)系，即能夠用一線性代數(shù)方程表示，那么稱這種分組碼為線性分組碼。,線性分組碼的表示,線性分組碼一般用符號(hào)(n,k)表示，其中n為碼字的長(zhǎng)度，k為每個(gè)碼字中信息碼元的數(shù)目。定義為線性分組碼的碼率，即,線性分組碼的基本特性,設(shè)是某(n,k)分組碼的任意兩個(gè)碼字，這兩個(gè)碼字的差別是用對(duì)應(yīng)元素上不相同元素的個(gè)數(shù)來衡量的，這種度量稱為碼字間的Hamming距離，記作。個(gè)碼字集合中的最小值稱為該碼的最小Hamming距離，用表示。定義一個(gè)碼字中所有非零元素的個(gè)數(shù)為該碼字的Hamming重量。線性分組碼的最小Hamming距離等于最小Hamming重量。,線性分組碼的生成矩陣和奇偶校驗(yàn)矩陣,在(n,k)線性分組碼中，假設(shè)為編碼器的輸入信息碼元序列，為編碼器的輸出序列，則編碼器的輸入輸出關(guān)系可以表示為：式中，G為該線性分組碼的生成矩陣。任何矩陣都可以表示成生成矩陣行向量的線性組合。生成矩陣可化成“系統(tǒng)形式”：,線性分組碼的生成矩陣和奇偶校驗(yàn)矩陣,校驗(yàn)矩陣常用符號(hào)H表示，一種碼的校驗(yàn)矩陣等于該碼的對(duì)偶碼的生成矩陣，因此對(duì)于(n,k)線性分組碼，它的校驗(yàn)矩陣H和生成矩陣G滿足這里的0代表一個(gè)由全零元素組成的維矩陣。假定(n,k)線性分組碼是系統(tǒng)碼，則其校驗(yàn)矩陣可表示為：式中為P的轉(zhuǎn)置矩陣。,幾種特殊的線性分組碼,Hamming碼Hadamard碼Golay碼,循環(huán)碼,在線性分組碼中，有一種重要的碼稱為循環(huán)碼。它除了具有線性分組碼的一般特點(diǎn)外，還具有循環(huán)性：循環(huán)碼中任一碼字的碼元循環(huán)移位（左移或右移）后仍是該碼的一個(gè)碼字。其編碼和譯碼的電路較簡(jiǎn)單，且檢、糾錯(cuò)能力較強(qiáng)，目前已成為研究最深入、理論最成熟、應(yīng)用最廣泛的一類線性分組碼。,循環(huán)碼,理論研究時(shí)常用多項(xiàng)式來表示循環(huán)碼，即有：式中：為循環(huán)碼的任一碼字。對(duì)于二進(jìn)制碼，多項(xiàng)式的每個(gè)系數(shù)不是0就是1?？梢杂靡粋€(gè)n-k次的生成多項(xiàng)式產(chǎn)生一個(gè)循環(huán)碼。(n,k)循環(huán)碼的生成多項(xiàng)式一定是多項(xiàng)式的因子，其通式為：,循環(huán)碼,定義一個(gè)消息多項(xiàng)式如下：這里代表k位信息比特。則由該k位信息比特生成的碼字為：可以證明上式滿足循環(huán)特性。BCH是循環(huán)碼中一種重要的碼型，能夠糾正多比特錯(cuò)誤。,線性分組碼的最佳軟判決譯碼,線性分組碼的最佳軟判決譯碼是通過使用匹配率濾波器作為最佳接收機(jī)并后接一個(gè)譯碼器實(shí)現(xiàn)的，譯碼器用來生成與M種碼字對(duì)應(yīng)的M個(gè)判決變量。令表示發(fā)送任一指定碼字后匹配濾波器的n個(gè)輸出取樣。假設(shè)信號(hào)采用BPSK傳輸，則當(dāng)碼字的第j比特是1時(shí)：當(dāng)碼字的第j比特是0時(shí)：其中表示傳輸碼字的一個(gè)比特所需的信號(hào)能量，變量表示取樣瞬間的高斯白噪聲。,線性分組碼的最佳軟判決譯碼,根據(jù)已知的M中可能發(fā)送的碼字和接收到值，最佳譯碼器形成M個(gè)相關(guān)度：式中：便是第i個(gè)碼字第j個(gè)位置上的比特。最佳譯碼器選擇相關(guān)度均值最大的碼字作為譯碼輸出。最佳軟判決譯碼的算法比較簡(jiǎn)單，但當(dāng)碼字?jǐn)?shù)量很大時(shí)計(jì)算量就會(huì)變得無法接受，巨大的計(jì)算量降低了其在工程中適用度。,線性分組碼的硬判決譯碼,針對(duì)軟判決譯碼巨大的計(jì)算量，硬判決譯碼將模擬樣值量化，然后用數(shù)字方式實(shí)現(xiàn)譯碼，這種方法的一種實(shí)現(xiàn)方式是最小距離譯碼，也稱最大似然譯碼。譯碼方案：來自解調(diào)器的與接收碼字對(duì)應(yīng)的n個(gè)比特被送往譯碼器，譯碼器將接收的碼字和M種可能發(fā)送的碼字進(jìn)行比較，把與接收碼字漢明距離最小的判決為譯碼碼字。,線性分組碼的硬判決譯碼,使用校驗(yàn)矩陣H是一種有效的硬判決譯碼方法。假定是發(fā)送碼字，Y是解調(diào)器輸出的接收碼字，一般Y可以表示為：其中，e代表一個(gè)任意的二進(jìn)制差錯(cuò)矢量，那么式中，(n-k)維矢量S叫做差錯(cuò)圖案的伴隨式。由于S,H,Y是可知的，所以最終可以求出發(fā)送碼字。,硬判決譯碼和軟判決譯碼的性能比較,軟判決譯碼和硬判決譯碼碼字差錯(cuò)概率比較軟判決譯碼差錯(cuò)概率上邊界：硬判決譯碼差錯(cuò)概率精確值：在范圍內(nèi)，硬判決譯碼和軟判決譯碼的碼字差錯(cuò)概率性能約相差2dB，且軟判決譯碼性能較好。,硬判決譯碼和軟判決譯碼的性能比較,軟判決譯碼和硬判決譯碼單位比特最小信噪比比較在碼率趨近于零的極限時(shí)，硬判決譯碼和軟判決譯碼的信噪比值相差約為2dB。隨著碼率的增大，兩種譯碼技術(shù)的單位比特最小信噪比差值越來越小，當(dāng)時(shí)，差值約為1.5dB。,卷積碼的定義,線性碼分為分組碼和卷積碼，卷積碼又稱連環(huán)碼，由埃里亞斯于1955年首次提出。若本碼組的校驗(yàn)元不僅與本碼組的信息元相關(guān)，而且還與本碼組相鄰的前幾個(gè)碼組的信息元相關(guān)，則稱這類碼為卷積碼。,卷積碼的表示,卷積碼一般用符號(hào)表示，稱m為編碼存貯，它表示輸入信息子組在編碼器中滯留的單元時(shí)間；稱m+1為編碼約束度，表示編碼過程中相互約束的子碼個(gè)數(shù)；稱為編碼約束長(zhǎng)度，表示編碼過程中互相約束的碼元個(gè)數(shù)。,卷積碼的描述方法,解析表示法1、離散卷積法2、生成矩陣法3、碼多項(xiàng)式法圖形表示法1、樹圖法2、網(wǎng)格圖法3、狀態(tài)圖法,卷積碼的樹圖表示,碼率為1/3，K=3卷積碼的樹圖,卷積碼的網(wǎng)格圖和狀態(tài)圖表示,碼率為1/3，K=3卷積碼的網(wǎng)格圖,碼率為1/3，K=3卷積碼的狀態(tài)圖,卷積碼的編碼,卷積碼編碼器,卷積碼的譯碼,卷積碼有三種主要的譯碼方法：序列譯碼、門限譯碼和最大似然譯碼。1957年伍成克拉夫(Wozencraft)提出了一種有效的譯碼方法，即序列譯碼。1963年梅西(Massey)提出了一種性能稍差，但比較實(shí)用的門限譯碼方法。1967年維特比(Viterbi)提出了最大似然譯碼法，它又稱為維特比譯碼。門限譯碼是一種代數(shù)譯碼法，序列譯碼和維特比最大似然譯碼都是概率譯碼。代數(shù)譯碼利用編碼本身得代數(shù)結(jié)構(gòu)進(jìn)行解碼，并不考慮信道的統(tǒng)計(jì)特性。比如門限譯碼，它以分組碼理論為基礎(chǔ)，其主要特點(diǎn)是算法簡(jiǎn)單，易于實(shí)現(xiàn)，但是它的誤碼性能要比概率譯碼差。它的譯碼方法是從線性碼的監(jiān)督子出發(fā)，找到一組特殊的能夠檢查信息位置是否發(fā)生錯(cuò)誤的方程組，從而實(shí)現(xiàn)糾錯(cuò)譯碼。概率譯碼的基本思想是：把已經(jīng)接收到的序列與所有可能的發(fā)送序列相比較，選擇其中漢明距離最小的一個(gè)序列作為發(fā)送序列。維特比譯碼是目前用得較多的一種譯碼方法。它是一種最大似然譯碼，其譯碼的復(fù)雜性均隨m按指數(shù)增長(zhǎng)。最大似然譯碼對(duì)存儲(chǔ)器級(jí)數(shù)較小的卷積碼很容易實(shí)現(xiàn)，被廣泛地應(yīng)用于現(xiàn)代通信中。隨著大規(guī)模集成電路技術(shù)的發(fā)展，對(duì)存儲(chǔ)器級(jí)數(shù)較大的卷積碼也可以采用最大似然譯碼。目前維特比譯碼已經(jīng)得到了廣泛的應(yīng)用。,卷積碼的最佳譯碼-維特比算法,不像分組碼那樣有固定的長(zhǎng)度n，卷積碼基本是一個(gè)有限狀態(tài)機(jī)，因此它的最佳譯碼器是一個(gè)最大似然序列估計(jì)器。卷積碼的譯碼就是遍歷網(wǎng)格圖找出最可能的序列。根據(jù)解調(diào)器后的譯碼器執(zhí)行軟判決或硬判決，遍歷網(wǎng)格圖時(shí)所用的度量可以是Hamming距離，也可以是歐氏距離。,維特比譯碼算法的實(shí)現(xiàn),基本原理：譯碼器將接收到的序列和所有可能的發(fā)送序列作比較，選擇其中漢明距離最小的序列當(dāng)作是現(xiàn)在的發(fā)送序列。例：假設(shè)卷積碼為(n,k,m)=(3,1,2)碼現(xiàn)在的發(fā)送信息位為1101為了使移存器中的信息位全部移出，在信息位后面加入了3個(gè)“0”，即1101000編碼后的發(fā)送序列：111110010100001011000接收序列：111010010110001011000(紅色為錯(cuò)碼)對(duì)于(3,1,2)卷積碼，發(fā)送序列的約束長(zhǎng)度，所以首先需考察3個(gè)信息段，即考察接收序列的前3n=9位“111010010”。,維特比譯碼算法的實(shí)現(xiàn),解碼第1步由網(wǎng)格圖可見，沿路徑每一級(jí)有4種狀態(tài)a,b,c和d。每種狀態(tài)只有兩條路徑可以到達(dá)。故4種狀態(tài)共有8條到達(dá)路徑。比較網(wǎng)格圖中的這8條路徑和接收序列之間的漢明距離。例如，由出發(fā)點(diǎn)狀態(tài)a經(jīng)過3級(jí)路徑后到達(dá)狀態(tài)a的兩條路徑中上面一條為“000000000”。它和接收序列“111010010”的漢明距離等于5；下面一條為“111001011”,它和接收序列的漢明距離等于3。,維特比譯碼算法的實(shí)現(xiàn),將這8個(gè)比較結(jié)果列表如下：比較到達(dá)每個(gè)狀態(tài)的兩條路徑的漢明距離，將距離小的一條路徑保留，稱為幸存路徑。這樣，就剩下4條路徑了，即表中第2,4,6和8條路徑。,維特比譯碼算法的實(shí)現(xiàn),解碼第2步：繼續(xù)考察接收序列中的后繼3個(gè)比特“110”計(jì)算4條幸存路徑上增加1級(jí)后的8條可能路徑的漢明距離。計(jì)算結(jié)果列于下表中。表中總距離最小為2，其路徑是abdc+b，相應(yīng)序列為111110010100。它和發(fā)送序列相同，故對(duì)應(yīng)發(fā)送信息位1101。,維特比譯碼算法的實(shí)現(xiàn),按照上表中的幸存路徑畫出的網(wǎng)格圖示于下圖中。圖中粗線路徑是距漢明離最小(等于2)的路徑。,維特比譯碼算法的實(shí)現(xiàn),在編碼時(shí)，信息位后面加了3個(gè)“0”。若把這3個(gè)“0”仍然看作是信息位，則可以按照上述算法繼續(xù)解碼。這樣得到的幸存路徑網(wǎng)格圖示于下圖中。圖中的粗線仍然是漢明距離最小的路徑。,維特比譯碼算法的實(shí)現(xiàn),若已知這3個(gè)碼元是（為結(jié)尾而補(bǔ)充的）“0”，則在解碼時(shí)就預(yù)先知道在接收這3個(gè)“0”碼元后，路徑必然應(yīng)該回到狀態(tài)a。而由圖可見，由于只有兩條路徑可以回到a狀態(tài)，所以這時(shí)上圖可以簡(jiǎn)化成：,維特比譯碼算法的實(shí)現(xiàn),在上例中卷積碼的約束長(zhǎng)度為N=3，需要存儲(chǔ)和計(jì)算8條路徑的參量。由此可見，維特比算法的復(fù)雜度隨約束長(zhǎng)度N按指數(shù)形式增長(zhǎng)。故維特比算法適合約束長(zhǎng)度較小的編碼。對(duì)于約束長(zhǎng)度大的卷積碼，可以采用其他解碼算法。,卷積碼軟判決譯碼的差錯(cuò)概率,加性高斯白噪聲信道中