信道編碼簡(jiǎn)介課件

編碼理論周武旸wyzhou@中國(guó)科學(xué)技術(shù)大學(xué)編碼理論周武旸助教劉磊：liul@助教第一章序論編碼理論的內(nèi)容包括三個(gè)方面以保證數(shù)字信息傳輸和處理的可靠性為目的的差錯(cuò)控制編碼（error-controlcoding），又稱(chēng)為信道編碼（channelcoding）；以提高數(shù)字信息傳輸、存儲(chǔ)處理的有效性為宗旨的信源編碼（Sourcecoding）；以增加數(shù)字信息傳輸、存儲(chǔ)的安全性為目標(biāo)的數(shù)據(jù)加密編碼（dataencryption）；我們主要討論差錯(cuò)控制編碼技術(shù)。第一章序論編碼理論的內(nèi)容包括三個(gè)方面差錯(cuò)控制編碼技術(shù)是適應(yīng)數(shù)字通信抗噪聲干擾的需要而誕生和發(fā)展起來(lái)的，它是于1948年、著名的信息論創(chuàng)始人C.E.Shannon（香農(nóng)）在貝爾系統(tǒng)技術(shù)雜志發(fā)表的“AMathematicalTheoryofCommunication”一文，開(kāi)創(chuàng)了一門(mén)新興學(xué)科和理論：信息論和編碼理論。差錯(cuò)控制編碼技術(shù)是適應(yīng)數(shù)字通信抗噪聲干擾的需要而誕生和發(fā)展起1.1

信道編碼的歷史及研究現(xiàn)狀1948年，Bell實(shí)驗(yàn)室的C.E.Shannon發(fā)表的《通信的數(shù)學(xué)理論》，是關(guān)于現(xiàn)代信息理論的奠基性論文，它的發(fā)表標(biāo)志著信息與編碼理論這一學(xué)科的創(chuàng)立。Shannon在該文中指出，任何一個(gè)通信信道都有確定的信道容量C，如果通信系統(tǒng)所要求的傳輸速率R小于C，則存在一種編碼方法，當(dāng)碼長(zhǎng)n充分大并應(yīng)用最大似然譯碼（MLD，MaximumLikelihoodDecdoding）時(shí)，信息的錯(cuò)誤概率可以達(dá)到任意小。從Shannon信道編碼定理可知，隨著分組碼的碼長(zhǎng)n或卷積碼的約束長(zhǎng)度N的增加，系統(tǒng)可以取得更好的性能（即更大的保護(hù)能力或編碼增益），而譯碼的最優(yōu)算法是MLD，MLD算法的復(fù)雜性隨n或N的增加呈指數(shù)增加，因此當(dāng)n或N較大時(shí)，MLD在物理上是不可實(shí)現(xiàn)的。因此，構(gòu)造物理可實(shí)現(xiàn)編碼方案及尋找有效譯碼算法一直是信道編碼理論與技術(shù)研究的中心任務(wù)。Shannon指出了可以通過(guò)差錯(cuò)控制碼在信息傳輸速率不大于信道容量的前提下實(shí)現(xiàn)可靠通信，但卻沒(méi)有給出具體實(shí)現(xiàn)差錯(cuò)控制編碼的方法。1.1信道編碼的歷史及研究現(xiàn)狀1948年，Bell實(shí)驗(yàn)室的20世紀(jì)40年代，R.Hamming和M.Golay提出了第一個(gè)實(shí)用的差錯(cuò)控制編碼方案，使編碼理論這個(gè)應(yīng)用數(shù)學(xué)分支的發(fā)展得到了極大的推動(dòng)。通常認(rèn)為是R.Hamming提出了第一個(gè)差錯(cuò)控制碼。當(dāng)時(shí)他作為一個(gè)數(shù)學(xué)家受雇于貝爾實(shí)驗(yàn)室，主要從事彈性理論的研究。他發(fā)現(xiàn)計(jì)算機(jī)經(jīng)常在計(jì)算過(guò)程中出現(xiàn)錯(cuò)誤，而一旦有錯(cuò)誤發(fā)生，程序就會(huì)停止運(yùn)行。這個(gè)問(wèn)題促使他編制了使計(jì)算機(jī)具有檢測(cè)錯(cuò)誤能力的程序，通過(guò)對(duì)輸入數(shù)據(jù)編碼，使計(jì)算機(jī)能夠糾正這些錯(cuò)誤并繼續(xù)運(yùn)行。Hamming所采用的方法就是將輸入數(shù)據(jù)每4個(gè)比特分為一組，然后通過(guò)計(jì)算這些信息比特的線性組合來(lái)得到3個(gè)校驗(yàn)比特，然后將得到的7個(gè)比特送入計(jì)算機(jī)。計(jì)算機(jī)按照一定的原則讀取這些碼字，通過(guò)采用一定的算法，不僅能夠檢測(cè)到是否有錯(cuò)誤發(fā)生，同時(shí)還可以找到發(fā)生單個(gè)比特錯(cuò)誤的比特的位置，該碼可以糾正7個(gè)比特中所發(fā)生的單個(gè)比特錯(cuò)誤。這個(gè)編碼方法就是分組碼的基本思想，Hamming提出的編碼方案后來(lái)被命名為漢明碼。Hamming,1915-199820世紀(jì)40年代，R.Hamming和M.Golay提出了第

雖然漢明碼的思想是比較先進(jìn)的，但是它也存在許多難以接受的缺點(diǎn)。首先，漢明碼的編碼效率比較低，它每4個(gè)比特編碼就需要3個(gè)比特的冗余校驗(yàn)比特。另外，在一個(gè)碼組中只能糾正單個(gè)的比特錯(cuò)誤。M.Golay研究了漢明碼的這些缺點(diǎn)，并提出了兩個(gè)以他自己的名字命名的高性能碼字：一個(gè)是二元Golay碼，在這個(gè)碼字中Golay將信息比特每12個(gè)分為一組，編碼生成11個(gè)冗余校驗(yàn)比特，相應(yīng)的譯碼算法可以糾正3個(gè)錯(cuò)誤。另外一個(gè)是三元Golay碼，它的操作對(duì)象是三元而非二元數(shù)字。三元Golay碼將每6個(gè)三元符號(hào)分為一組，編碼生成5個(gè)冗余校驗(yàn)三元符號(hào)。這樣由11個(gè)三元符號(hào)組成的三元Golay碼碼字可以糾正2個(gè)錯(cuò)誤。雖然漢明碼的思想是比較先進(jìn)的，但是它也存在許多難以接受的缺漢明碼和Golay碼的基本原理相同。它們都是將q元符號(hào)按每k個(gè)分為一組．然后通過(guò)編碼得到n-k個(gè)q元符號(hào)作為冗余校驗(yàn)符號(hào)，最后由校驗(yàn)符號(hào)和信息符號(hào)組成有n個(gè)q元符號(hào)的碼字符號(hào)。得到的碼字可以糾正t個(gè)錯(cuò)誤，編碼碼率為為k/n。這種類(lèi)型的碼字稱(chēng)為分組碼，一般記為(q,n,k,t)碼，二元分組碼可以簡(jiǎn)記為(n,k,t)碼或者(n,k)碼。漢明碼和Golay碼都是線性的，任何兩個(gè)碼字經(jīng)過(guò)模q的加操作之后，得到的碼字仍舊是碼集合中的一個(gè)碼字。漢明碼和Golay碼的基本原理相同。它們都是將q元符號(hào)按每k在Golay碼提出之后最主要的一類(lèi)分組碼就是Reed-Muller碼。它是Muller在1954年提出的，此后Reed在Muller提出的分組碼的基礎(chǔ)上得到了一種新的分組碼，稱(chēng)為Reed-Muller碼，簡(jiǎn)記為RM碼。在1969年到1977年之間，RM碼在火星探測(cè)方面得到了極為廣泛的應(yīng)用。即使在今天，RM碼也具有很大的研究?jī)r(jià)值，其快速的譯碼算法非常適合于光纖通信系統(tǒng)。在Golay碼提出之后最主要的一類(lèi)分組碼就是Reed-Mul在RM碼提出之后人們又提出了循環(huán)碼的概念。循環(huán)碼實(shí)際上也是一類(lèi)分組碼，但它的碼字具有循環(huán)移位特性，即碼字比特經(jīng)過(guò)循環(huán)移位后仍然是碼字集合中的碼字。這種循環(huán)結(jié)構(gòu)使碼字的設(shè)計(jì)范圍大大增加，同時(shí)大大簡(jiǎn)化了編譯碼結(jié)構(gòu)。循環(huán)碼的另一個(gè)特點(diǎn)就是它可以用一個(gè)冪次為n-k的多項(xiàng)式來(lái)表示，這個(gè)多項(xiàng)式記為g(D)，稱(chēng)為生成多項(xiàng)式，其中D為延遲算子。循環(huán)碼也稱(chēng)為循環(huán)冗余校驗(yàn)(CRC，CyclicRedundancyCheck)碼，并且可以用Meggitt譯碼器來(lái)實(shí)現(xiàn)譯碼。由于Meggitt譯碼器的譯碼復(fù)雜性隨著糾錯(cuò)能力t的增加而呈指數(shù)形式的增加，因此通常CRC碼用于糾正只有單個(gè)錯(cuò)誤的應(yīng)用情況，常用做檢錯(cuò)碼而非糾錯(cuò)碼。在RM碼提出之后人們又提出了循環(huán)碼的概念。循環(huán)碼實(shí)際上也是一循環(huán)碼的一個(gè)非常重要的子集就是分別由Hocquenghem在1959年、Bose和Ray-Chaudhuri研究組在1960年幾乎同時(shí)提出的BCH碼(BCH，BoseChaudhuriHocquenghem)，BCH碼的碼字長(zhǎng)度為n＝qm-1，其中m為一個(gè)整數(shù)。二元BCH碼（q=2）的糾錯(cuò)能力限為t<(2m-1)/2。1960年，Reed和Solomon將BCH碼擴(kuò)展到非二元（q>2）的情況，得到了RS（Reed-Solomon）碼。1967年，Berlekamp給出了一個(gè)非常有效的譯碼算法后，RS碼得到了廣泛的應(yīng)用。此后，RS碼在CD播放器、DVD播放器中得到了很好的應(yīng)用。循環(huán)碼的一個(gè)非常重要的子集就是分別由Hocquenghem在雖然分組碼在理論分析和數(shù)學(xué)描述方面已經(jīng)非常成熟，并且在實(shí)際的通信系統(tǒng)中也已經(jīng)得到了廣泛的應(yīng)用，但分組碼固有的缺陷大大限制了它的進(jìn)一步發(fā)展。首先，由于分組碼是面向數(shù)據(jù)塊的，因此，在譯碼過(guò)程中必須等待整個(gè)碼字全部接收到之后才能開(kāi)始進(jìn)行譯碼。在數(shù)據(jù)塊長(zhǎng)度較大時(shí)，引入的系統(tǒng)延時(shí)是非常大的。分組碼的第二個(gè)缺陷是它要求精確的幀同步，即需要對(duì)接收碼字或幀的起始符號(hào)時(shí)間和相位精確同步。另外，大多數(shù)基于代數(shù)的分組碼的譯碼算法都是硬判決算法，而不是對(duì)解調(diào)器輸出未量化信息的軟譯碼，從而造成了一定程度的增益損失。雖然分組碼在理論分析和數(shù)學(xué)描述方面已經(jīng)非常成熟，并且在實(shí)際的分組碼所存在的固有缺點(diǎn)可以通過(guò)采用其他的編碼方法來(lái)改善。這種編碼方法就是卷積碼。卷積碼是Elias等人在1955年提出的。卷積碼與分組碼的不同在于：它充分利用了各個(gè)信息塊之間的相關(guān)性。通常卷積碼記為(n，k，N)碼。卷積碼的編碼過(guò)程是連續(xù)進(jìn)行的，依次連續(xù)將每k個(gè)信息元輸入編碼器，得到n個(gè)碼元，得到的碼元中的檢驗(yàn)元不僅與本碼的信息元有關(guān)，還與以前時(shí)刻輸入到編碼器的信息元(反映在編碼寄存器的內(nèi)容上)有關(guān)。同樣，在卷積碼的譯碼過(guò)程中，不僅要從本碼中提取譯碼信息，還要充分利用以前和以后時(shí)刻收到的碼組．從這些碼組中提取譯碼相關(guān)信息，而且譯碼也是可以連續(xù)進(jìn)行的，這樣可以保證卷積碼的譯碼延時(shí)相對(duì)比較小。通常，在系統(tǒng)條件相同的條件下，在達(dá)到相同譯碼性能時(shí)，卷積碼的信息塊長(zhǎng)度和碼字長(zhǎng)度都要比分組碼的信息塊長(zhǎng)度和碼字長(zhǎng)度小，相應(yīng)譯碼復(fù)雜性也小一些。Elias,1923-2001分組碼所存在的固有缺點(diǎn)可以通過(guò)采用其他的編碼方法來(lái)改善。這種卷積碼的譯碼通常有如下幾個(gè)比較流行的譯碼算法：由Wozencraft和Reiffen在1961年提出，F(xiàn)ano和Jelinek分別在1963年和1969年進(jìn)行改進(jìn)了的序貫譯碼算法。該算法是基于碼字樹(shù)圖結(jié)構(gòu)的一種次優(yōu)概率譯碼算法。由Massey在1963年提出的門(mén)限譯碼算法。這個(gè)算法利用碼字的代數(shù)結(jié)構(gòu)進(jìn)行代數(shù)譯碼。由Viterbi在1967年提出的Viterbi算法。該算法是基于碼字格圖結(jié)構(gòu)的一種最大似然譯碼算法，是一種最優(yōu)譯碼算法。在Viterbi譯碼算法提出之后，卷積碼在通信系統(tǒng)中得到了極為廣泛的應(yīng)用。如GSM、3G、商業(yè)衛(wèi)星通信系統(tǒng)等。Viterbi,CDMA之父卷積碼的譯碼通常有如下幾個(gè)比較流行的譯碼算法：Viterbi近年來(lái)，在信道編碼定理的指引下，人們一直致力于尋找能滿(mǎn)足現(xiàn)代通信業(yè)務(wù)要求、結(jié)構(gòu)簡(jiǎn)單、性能優(yōu)越的好碼，并在分組碼、卷積碼等基本編碼方法和最大似然譯碼算法的基礎(chǔ)上提出了許多構(gòu)造好碼及簡(jiǎn)化譯碼復(fù)雜性的方法，提出了乘積碼、代數(shù)幾何碼、低密度校驗(yàn)碼(LDPC，LowDensityParityCheck)、分組-卷積級(jí)聯(lián)碼等編碼方法和逐組最佳譯碼、軟判決譯碼等譯碼方法以及編碼與調(diào)制相結(jié)合的網(wǎng)格編碼調(diào)制(TCM，TrellisCodedModulation)技術(shù)。其中對(duì)糾錯(cuò)碼發(fā)展貢獻(xiàn)比較大的有級(jí)聯(lián)碼、軟判決譯碼和TCM技術(shù)等。Gallager近年來(lái)，在信道編碼定理的指引下，人們一直致力于尋找能滿(mǎn)足現(xiàn)代雖然軟判決譯碼、級(jí)聯(lián)碼和編碼調(diào)制技術(shù)都對(duì)信道碼的設(shè)計(jì)和發(fā)展產(chǎn)生了重大影響，但是其增益與Shannon理論極限始終都存在2～3dB的差距。在1993年于瑞士日內(nèi)瓦召開(kāi)的國(guó)際通信會(huì)議(1CC'93)上，兩位任教于法國(guó)不列顛通信大學(xué)的教授C.Berrou、A.Glavieux和他們的緬甸籍博士生P.Thitimajshima首次提出了一種新型信道編碼方案——Turbo碼，由于它很好地應(yīng)用了Shannon信道編碼定理中的隨機(jī)性編、譯碼條件，從而獲得了幾乎接近Shannon理論極限的譯碼性能。仿真結(jié)果表明，在采用長(zhǎng)度為65536的隨機(jī)交織器并譯碼迭代18次情況下，在信噪比Eb/N0>=0.7dB并采用二元相移鍵控(BPSK)調(diào)制時(shí)，碼率為1/2的Turbo碼在加性高斯白噪聲信道上的誤比特率(BER)<=10-5，達(dá)到了與Shannon極限僅相差0.7dB的優(yōu)異性能。(1/2碼率的Shannon極限是0dB)。BerrouandForney雖然軟判決譯碼、級(jí)聯(lián)碼和編碼調(diào)制技術(shù)都對(duì)信道碼的設(shè)計(jì)和發(fā)展產(chǎn)1997年，Host、Johannesson、Ablov提出了編織卷級(jí)碼（WovenConvolutionalCode,WCC）的概念，隨后編織碼（Wovencode）便發(fā)展起來(lái)了。它是一種組合碼，其系統(tǒng)結(jié)構(gòu)可完全包容傳統(tǒng)分組碼、卷級(jí)碼以及各類(lèi)Turbo碼，開(kāi)創(chuàng)了編碼領(lǐng)域的一個(gè)新天地。編織碼的結(jié)構(gòu)綜合了并行級(jí)聯(lián)卷級(jí)碼（Turbo碼）和串行級(jí)聯(lián)卷級(jí)碼的結(jié)構(gòu)特點(diǎn)，當(dāng)外編碼器個(gè)數(shù)足夠多時(shí)，該碼型完全擁有了Shannon編碼定理中隨機(jī)長(zhǎng)碼的特性，因此，其糾錯(cuò)性能理論上比Turbo碼要優(yōu)異。但編織碼的編碼結(jié)構(gòu)復(fù)雜性較高，編碼效率也不高，目前研究最多的是1/3的編織卷級(jí)碼，譯碼采用BCJR算法的迭代譯碼。1997年，Host、Johannesson、Ablov提出發(fā)展概括1948年，Shannon發(fā)表開(kāi)創(chuàng)性文章“通信的數(shù)學(xué)理論”；1950年，Hamming發(fā)明了漢明碼；1955年，Elias引入了卷級(jí)碼；1957年，Prange提出了循環(huán)碼；1960年，Bose/Chaudhuri/Hocquenghem發(fā)明了BCH碼；Reed和Solomon提出了RS碼；1962年，Gallager提出了LDPC碼；1967年，Berlekamp引入了BCH/RS碼的快速譯碼算法；1968年，Gallager著書(shū)《Informationtheoryandreliablecommunication》；1971年，Viterbi引入卷級(jí)碼的最大似然譯碼；1972年，BCJR算法的提出；1981年，Tanner提出了用于理解信道編碼理論的Tanner圖；1982年，Ungerboeck引入編碼調(diào)制；1993年，Berrou/Glaveieux/Thitimajshima提出了Turbo碼；1995年，MacKay重新發(fā)現(xiàn)了LDPC碼；1997年，Host/Johannesson/Ablov提出了編織卷級(jí)碼。2000年，Aji與McEliece總結(jié)了應(yīng)用消息傳遞思想進(jìn)行譯碼的碼型；2003年，Koetter與Vardy提出了RS碼的代數(shù)軟判決譯碼；發(fā)展概括1948年，Shannon發(fā)表開(kāi)創(chuàng)性文章“通信的數(shù)學(xué)高效糾錯(cuò)編碼的研究現(xiàn)狀20世紀(jì)90年代以后，以迭代譯碼為基礎(chǔ)的高效糾錯(cuò)碼成為主要研究對(duì)象，不再將精力放在以代數(shù)為基礎(chǔ)的代數(shù)碼上，而是尋找新的糾錯(cuò)碼的認(rèn)識(shí)方式，其中有以Tanner圖為基礎(chǔ)發(fā)展起來(lái)的編譯碼的可視化方法，如因子圖，以及基于圖中雙邊上信息傳遞的和積算法，還有用于評(píng)估碼字性能限的數(shù)值化方法－－密度進(jìn)化、典型集合界理論等。由于最大似然譯碼性能最好，但復(fù)雜度隨碼長(zhǎng)指數(shù)增加（物理上不可實(shí)現(xiàn)），因此必須研究新的編譯碼方案，期望在性能和復(fù)雜度之間取得平衡。如串行級(jí)聯(lián)碼、乘積碼等編碼方案的目標(biāo)都是為了構(gòu)造出具有較大等效分組長(zhǎng)度的糾錯(cuò)碼，并且允許將最大似然譯碼分為幾個(gè)較簡(jiǎn)單的譯碼步驟（一種次優(yōu)但可實(shí)現(xiàn)的譯碼策略）；另一種次優(yōu)方法是迭代譯碼（Gallager的貢獻(xiàn)），1993年Berrou提出的Turbo碼采用軟輸出迭代譯碼，性能與Shannon限僅差0.7dB，1996年，MacKay與Neal仿真的LDPC碼性能與Shannon限僅差0.0045dB，這表明，迭代譯碼方法已成為靠近Shannon限的高效糾錯(cuò)碼的基本特征?？傊瑸閷?shí)現(xiàn)高效糾錯(cuò)，不是采用級(jí)聯(lián)方式構(gòu)造隨機(jī)長(zhǎng)碼，就是采用迭代譯碼，或兩者均采用，以逼近Shannon限。高效糾錯(cuò)編碼的研究現(xiàn)狀20世紀(jì)90年代以后，以迭代譯碼為基礎(chǔ)端到端的通信系統(tǒng)模型從圖中可知，數(shù)字通信的主要技術(shù)問(wèn)題包括：信源編譯碼、信道編譯碼、數(shù)字調(diào)制解調(diào)、基帶傳輸、信道與噪聲、接收時(shí)必須要解決的同步問(wèn)題、為了使通信過(guò)程保密，要進(jìn)行保密編譯碼的處理等。同步端到端的通信系統(tǒng)模型從圖中可知，數(shù)字通信的主要技術(shù)問(wèn)題包括：無(wú)線信道比有線信道要惡劣的多！無(wú)線信道比有線信道要惡劣的多！1.2

簡(jiǎn)單的編碼方式回顧在設(shè)計(jì)數(shù)字通信系統(tǒng)時(shí)，首先應(yīng)從合理地選擇調(diào)制解調(diào)方法、合適的發(fā)射功率等方面考慮，若仍不能滿(mǎn)足系統(tǒng)誤碼率要求，則要考慮采用本章所講的差錯(cuò)控制編碼措施。糾錯(cuò)碼，是當(dāng)消息經(jīng)過(guò)有噪信道傳輸或要恢復(fù)存儲(chǔ)的數(shù)據(jù)時(shí)用來(lái)糾錯(cuò)的。用來(lái)傳輸消息的物理介質(zhì)叫做信道（如電話線、衛(wèi)星連接、用于移動(dòng)通信的無(wú)線信道等）。因?yàn)榧m錯(cuò)碼試圖克服信道中噪聲造成的損害，因此其編碼過(guò)程又稱(chēng)為信道編碼，它是提高數(shù)字信號(hào)傳輸可靠性的有效方法之一。1.2簡(jiǎn)單的編碼方式回顧在設(shè)計(jì)數(shù)字通信系統(tǒng)時(shí)，首先應(yīng)從合理數(shù)字通信系統(tǒng)框圖數(shù)字通信系統(tǒng)框圖常用的差錯(cuò)控制方式有三種：

檢錯(cuò)重發(fā)方式，又稱(chēng)為自動(dòng)重發(fā)請(qǐng)求（ARQ），發(fā)送端發(fā)送能夠發(fā)現(xiàn)錯(cuò)誤的碼，由接收端判斷接收中有無(wú)錯(cuò)誤發(fā)生。如果發(fā)現(xiàn)錯(cuò)誤，則通過(guò)反向信道把這一判決結(jié)果反饋給發(fā)送端，然后發(fā)送端再把錯(cuò)誤的信息重發(fā)一次。常用的差錯(cuò)控制方式有三種：前向糾錯(cuò)方式（FEC）：發(fā)送端發(fā)送能夠糾正錯(cuò)誤的碼，接收端收到后自動(dòng)糾正傳輸中的錯(cuò)誤，特點(diǎn)是單向傳輸。

混合糾錯(cuò)方式（HEC）：發(fā)送端發(fā)送既能自動(dòng)糾錯(cuò)，又能檢測(cè)的碼。接收端收到碼流后，檢查差錯(cuò)情況，如果錯(cuò)誤在糾錯(cuò)能力范圍以?xún)?nèi)，則自動(dòng)糾錯(cuò)，如果超過(guò)了糾錯(cuò)能力，但能檢測(cè)出來(lái)，則經(jīng)過(guò)反饋信道請(qǐng)求發(fā)送端重發(fā)。

前向糾錯(cuò)方式（FEC）：發(fā)送端發(fā)送能夠糾正錯(cuò)誤的碼，接收端收差錯(cuò)控制編碼的基本原理

在信息碼元序列中附加一些監(jiān)督碼元，在兩者之間建立某種校驗(yàn)關(guān)系，當(dāng)這種校驗(yàn)關(guān)系因傳輸錯(cuò)誤而受到破壞時(shí)，可以被發(fā)現(xiàn)和糾正。不同的編碼方法，有不同的檢錯(cuò)和糾錯(cuò)能力。一般來(lái)說(shuō)，付出的代價(jià)越大，檢（糾）錯(cuò)的能力就越強(qiáng)。這里所說(shuō)的代價(jià)，指增加的監(jiān)督碼元的多少。例如，若編碼序列中，平均每?jī)蓚€(gè)信息碼元就有一個(gè)監(jiān)督碼元，則這種編碼的多余度為1/3，或者說(shuō)，這種編碼的編碼速率為2/3，可見(jiàn)，差錯(cuò)控制編碼是以降低信息傳輸速率來(lái)?yè)Q取信息傳遞的可靠性提高。

差錯(cuò)控制編碼的基本原理在信息碼元序列中附加一些監(jiān)督碼元，在差錯(cuò)控制編碼的分類(lèi)

根據(jù)的函數(shù)關(guān)系，可分為線性碼和非線性碼。根據(jù)信息碼元和監(jiān)督碼元之間的約束方式，可分為分組碼和卷積碼。在分組碼中，監(jiān)督碼元僅與本碼組的信息碼元有關(guān)，而在卷積碼中，監(jiān)督碼元不僅與本組的信息碼元有關(guān)，還與前面若干組的信息碼元有關(guān)。

差錯(cuò)控制編碼的分類(lèi)根據(jù)的函誤差控制編碼的目標(biāo)用可以糾正的錯(cuò)誤個(gè)數(shù)來(lái)衡量糾錯(cuò)能力；快速有效地對(duì)消息進(jìn)行編碼；快速有效地對(duì)消息進(jìn)行解碼；單位時(shí)間內(nèi)所能傳輸?shù)男畔it數(shù)盡量大（即盡量減少冗余度）。矛盾！折衷！誤差控制編碼的目標(biāo)用可以糾正的錯(cuò)誤個(gè)數(shù)來(lái)衡量糾錯(cuò)能力；矛盾！使用糾錯(cuò)編碼的原因權(quán)衡1：差錯(cuò)性能和帶寬；權(quán)衡2：功率與帶寬；權(quán)衡3：數(shù)據(jù)速率與帶寬；權(quán)衡4：容量與帶寬；使用糾錯(cuò)編碼的原因權(quán)衡1：差錯(cuò)性能和帶寬；幾種常用的簡(jiǎn)單檢錯(cuò)碼

奇偶監(jiān)督碼

就是在原信息碼元后面附加一個(gè)監(jiān)督碼元，使得碼組中的“1”的個(gè)數(shù)為奇數(shù)或偶數(shù)。接收端譯碼時(shí)，對(duì)各碼元進(jìn)行模2加運(yùn)算，其結(jié)果為0或1，如果傳輸過(guò)程中任何一位發(fā)生錯(cuò)誤，就會(huì)使校驗(yàn)條件不滿(mǎn)足，但當(dāng)有偶數(shù)個(gè)錯(cuò)誤發(fā)生時(shí)，這種編碼就無(wú)能為力了。

行列監(jiān)督碼（水平奇偶監(jiān)督碼）

對(duì)行和列都實(shí)施奇偶監(jiān)督。

恒比碼：即碼字中“1”和“0”的數(shù)目保持恒定比例的碼。

幾種常用的簡(jiǎn)單檢錯(cuò)碼奇偶監(jiān)督碼1.2.1

線性分組碼1.2.1線性分組碼基本名詞定義在信道編碼中，非零碼元的數(shù)目稱(chēng)為漢明重量（HammingWeight)，也稱(chēng)為碼重。記為w(c)。兩個(gè)等長(zhǎng)碼組之間相應(yīng)位取值不同的數(shù)目稱(chēng)為這兩個(gè)碼組的漢明距離（HammingDistance），簡(jiǎn)稱(chēng)碼距。記為d(c1,c2),可得d(c1,c2)=w(c1-c2)。例:考慮有兩個(gè)碼字{0100,1111}的碼C，則w(0100)=1,w(1111)=4,這兩個(gè)碼字間的漢明距離為3。通過(guò)觀察，有

w(0100-1111)=w(1011)=3=d(0100,1111)基本名詞定義在信道編碼中，非零碼元的數(shù)目稱(chēng)為漢明重量（Ham碼組集中任意兩個(gè)碼字之間距離的最小值稱(chēng)為最小碼距（dmin），它關(guān)系著這種編碼的檢錯(cuò)和糾錯(cuò)能力。為檢測(cè)出e個(gè)錯(cuò)碼，為糾正t個(gè)錯(cuò)碼，為檢測(cè)出e個(gè)錯(cuò)碼,同時(shí)糾正t個(gè)錯(cuò)碼，且碼組集中任意兩個(gè)碼字之間距離的最小值稱(chēng)為最小碼距（dmin）線性碼具有下述性質(zhì)兩個(gè)屬于該碼的碼字的和仍是一個(gè)屬于該碼的碼字；全零字總是一個(gè)碼字；一個(gè)線性碼的兩個(gè)碼字之間的最小距離等于任何非零碼字的最小漢明重量。例：碼C＝{0000,1010,0101,1111}是一個(gè)分組長(zhǎng)度為4的線性分組碼。線性碼具有下述性質(zhì)兩個(gè)屬于該碼的碼字的和仍是一個(gè)屬于該碼的碼以分組碼為例，一般以（n，k）表示，k是信息碼元數(shù)目，n是碼組總碼元數(shù)，又稱(chēng)為碼長(zhǎng)，因此，n－k＝r就是監(jiān)督碼元的數(shù)目。信道編碼可表示為由編碼前的信息碼元空間Uk到編碼后的碼字空間Cn的一個(gè)映射f，即：

f：UkCn,編碼速率為R=k/n。在二進(jìn)制情況下，共有2k個(gè)不同的信息組，相應(yīng)地有2k個(gè)不同的碼字，稱(chēng)為許用碼組，其余2n－2k個(gè)就稱(chēng)為禁用碼組。以分組碼為例，一般以（n，k）表示，k是信息碼元數(shù)目，n是碼（7，4）線性分組碼舉例基本概念

分組碼：將信息碼分組，為每組信碼附加若干監(jiān)督碼的編碼，稱(chēng)為分組碼。

線性分組碼：每個(gè)監(jiān)督碼元都是碼組中某些信息碼元的線性相加得到的。

下面以（7，4）分組碼進(jìn)行說(shuō)明。

其碼字

（7，4）線性分組碼舉例基本概念據(jù)此，可得到16個(gè)碼字，dmin＝3，能檢測(cè)出2個(gè)錯(cuò)誤，糾正1個(gè)錯(cuò)誤。

據(jù)此，可得到16個(gè)碼字，dmin＝3，能檢測(cè)出2個(gè)錯(cuò)誤，糾正監(jiān)督矩陣H和生成矩陣G

將上面的方程重寫(xiě)為：

這就是監(jiān)督矩陣??！監(jiān)督矩陣H和生成矩陣G將上面的方程重寫(xiě)為：這就是監(jiān)督矩陣H矩陣是一個(gè)r×n的矩陣，它的每行之間是線性無(wú)關(guān)的。將H矩陣分為兩部分：所以，P矩陣是一個(gè)r×k階的矩陣，Ir是r階的單位陣?？蓪?xiě)為H＝[PIr]形式的矩陣稱(chēng)為典型監(jiān)督矩陣。如果監(jiān)督矩陣H不是一個(gè)典型矩陣，可以對(duì)它進(jìn)行初等變換，化為典型監(jiān)督矩陣。H矩陣是一個(gè)r×n的矩陣，它的每行之間是線性無(wú)關(guān)的。將H矩這個(gè)式子說(shuō)明H矩陣與碼字的轉(zhuǎn)置乘積為零，據(jù)此可作為接收碼字A是否出錯(cuò)的依據(jù)。若把監(jiān)督方程補(bǔ)充為下列方程：

這個(gè)式子說(shuō)明H矩陣與碼字的轉(zhuǎn)置乘積為零，據(jù)此可作為接收碼字A定義：則有：

因此，由信息碼元和生成矩陣G就可產(chǎn)生全部碼字。

定義：觀察G，可得

其中：因此，可寫(xiě)為上式形式的G矩陣就稱(chēng)為典型生成矩陣。

觀察G，可得(7,4)線性分組碼編碼器(7,4)線性分組碼編碼器例：已知（6，3）碼的生成矩陣為試求：（1）編碼碼組和各個(gè)碼組的碼重；（2）最小碼距dmin和該碼的差錯(cuò)控制能力；

解：（1）由3位碼組成的信息碼組矩陣為：例：已知（6，3）碼的生成矩陣為試求：解：因此，

因此，（2）最小碼距dmin＝3，該碼能檢錯(cuò)2位，或糾錯(cuò)1位，或糾錯(cuò)1位同時(shí)檢錯(cuò)1位的能力。

(6,3)線性分組碼編碼器（2）最小碼距dmin＝3，該碼能檢錯(cuò)2位，或糾錯(cuò)1位，或糾伴隨式（校正子）S碼組在傳輸中可能由于干擾而出錯(cuò)，例如發(fā)送碼組為A，接收到的碼組卻是B，它們都是n位碼的行矢量，我們就定義E＝B－A為錯(cuò)碼矩陣。其中B＝A＋E定義為伴隨式伴隨式（校正子）S碼組在傳輸中可能由于干擾而出錯(cuò)，例如發(fā)送有：因此，如果傳輸無(wú)錯(cuò)，S矩陣為零矩陣；如果有錯(cuò)誤，S就是一個(gè)非零矢量，就能從伴隨式確定錯(cuò)誤圖樣，然后從接收到的碼字中減去錯(cuò)誤圖樣，即A＝B－E，注意這里的加減都是模2加運(yùn)算，就可得到正確的碼組了。

有：應(yīng)該注意的是，上式的解答不是唯一的。我們知道，B是一個(gè)1×n的矩陣，HT是一個(gè)n×r的矩陣，所以S是一個(gè)1×r的矩陣，因此它有2r種可能。而錯(cuò)誤圖樣E的個(gè)數(shù)遠(yuǎn)大于2r，因此，必然有多個(gè)錯(cuò)誤圖樣對(duì)應(yīng)同一個(gè)校正子S。而錯(cuò)誤圖樣等于B－A，即與接收到的碼組是一一對(duì)應(yīng)的，為了選擇正確的結(jié)果，要使用最大似然比準(zhǔn)則，選擇與B最相似的A。從幾何意義上來(lái)說(shuō)，就是選擇與B距離最小的碼組，也就是差錯(cuò)矢量E中1碼最少的矢量。

應(yīng)該注意的是，上式的解答不是唯一的。我們知道，B是一個(gè)1×n對(duì)于（7，4）碼來(lái)說(shuō)，它的伴隨式與錯(cuò)誤圖樣的對(duì)應(yīng)關(guān)系如下表所示：由表可以看出，伴隨式S的2r種形式分別代表A碼無(wú)錯(cuò)和2r－1種有錯(cuò)的圖樣。對(duì)于（7，4）碼來(lái)說(shuō)，它的伴隨式與錯(cuò)誤圖樣的對(duì)應(yīng)關(guān)系如下表所例：仍以上面的例題，已知生成矩陣G如下，列出S與E的對(duì)照表。當(dāng)收到碼組B＝[111011]時(shí)，解出對(duì)應(yīng)的信息碼組D。解：已知生成矩陣為：

IkQ

例：仍以上面的例題，已知生成矩陣G如下，列出S與E的對(duì)照表。我們知道S有23種形式，相應(yīng)的碼重最小的E矢量有8種。S與E的對(duì)照表如下：

我們知道S有23種形式，相應(yīng)的碼重最小的E矢量有8種。S與E我們知道，（6，3）碼具有糾錯(cuò)1位的能力，雖然S＝111時(shí)對(duì)應(yīng)一種雙錯(cuò)圖案，但除此之外的雙錯(cuò)不能得到糾正。我們知道，（6，3）碼具有糾錯(cuò)1位的能力，雖然S＝111時(shí)對(duì)查表我們可知，E矢量為：E=[010000]

這樣我們就可得到正確的碼組A，即

所以，信息碼組為：查表我們可知，E矢量為：E=[010000]伴隨式譯碼步驟歸納如下：1.原始發(fā)送矢量為A；2.計(jì)算接收矢量B的伴隨式S=B·HT；3.由伴隨式S決定相對(duì)應(yīng)的錯(cuò)誤圖樣E；4.將B譯成。伴隨式譯碼器伴隨式譯碼步驟歸納如下：伴隨式譯碼器例3(7,4)線性分組碼的譯碼電路前面已經(jīng)給出(7,4)線性分組碼的生成矩陣G為和監(jiān)督矩陣H為假設(shè)消息序列為(0010),則經(jīng)過(guò)編碼后的序列為A=(0010101),接收后為B=(1010101),如何通過(guò)譯碼電路糾正錯(cuò)誤！例3(7,4)線性分組碼的譯碼電路前面已經(jīng)給出(7,4)線根據(jù)公式S=BHT,其中S=[s2,s1,s0],B=[b6,b5,b4,b3,b2,b1,b0],可得以下關(guān)系：

s2=b6+b5+

b4+

b2s1=b6+b5+

b3+

b1s0=b6+b4+

b3+

b0根據(jù)公式S=EHT,其中E=[e6,e5,e4,e3,e2,e1,e0],可得以下關(guān)系：e6=s2+s1+s0;e5=s2+s1e4=s2+s0;e3=s1+s0e2=s2;e1=s1;e0=s0根據(jù)公式S=BHT,其中S=[s2,s1,s0],B=[b糾正了錯(cuò)誤，輸出變?yōu)榱?010101??！糾正了錯(cuò)誤，輸出變?yōu)榱?010101?。h明碼（Hamming）

為了指示所有單錯(cuò)位置和無(wú)錯(cuò)情況，線性分組碼的碼長(zhǎng)n、信息碼元長(zhǎng)度k和監(jiān)督碼元長(zhǎng)度r之間滿(mǎn)足不等式：上式取等號(hào)時(shí)，就是漢明碼。由以上方法構(gòu)成的線性分組碼中，能糾正單個(gè)錯(cuò)誤的線性分組碼稱(chēng)為漢明碼，是Hamming于1949年提出的。此時(shí)，n、k、r的關(guān)系為：n=2r–1k=n–r=2r–r–1

其中r為的正整數(shù)。漢明碼（Hamming）為了指示所有單錯(cuò)位置和無(wú)錯(cuò)情況，線由，我們可知，上式在給定信息碼組長(zhǎng)度k后，可以求出能糾正單錯(cuò)的碼組最小長(zhǎng)度n，而且dmin=3。這樣我們就可知道，k=1/4/11時(shí)，n=3/7/15。構(gòu)成（3，1）、（7，4）、（15，11）碼。

漢明碼的編碼效率為：當(dāng)r很大時(shí)，趨于1。

由，我們可知，1.2.2

循環(huán)碼1.2.2循環(huán)碼2023/8/562引言在處理線性分組碼時(shí)，在分組碼的結(jié)構(gòu)上加入了線性限制的條件，這些結(jié)構(gòu)上的性質(zhì)可以幫助我們尋找好的能夠快速、簡(jiǎn)易地編碼和譯碼的線性分組碼；本章，我們將研究線性分組碼中的一個(gè)重要子類(lèi)：循環(huán)碼，該碼在結(jié)構(gòu)上有另外的限制，即一個(gè)碼字任意循環(huán)移位的結(jié)果仍是一個(gè)有效碼字。循環(huán)碼是1957年由Prange首先提出的，其特點(diǎn)是:(1)可以用反饋移位寄存器很容易實(shí)現(xiàn)編碼和伴隨式計(jì)算;(2)由于循環(huán)碼有很多固有的代數(shù)結(jié)構(gòu)，從而可以找到各種簡(jiǎn)單使用的譯碼方法。2023/7/3162引言在處理線性分組碼時(shí)，在分組碼的結(jié)構(gòu)2023/8/563多項(xiàng)式的運(yùn)算加法：f1(D)=D3+D+1,f2(D)=D+1

則f1(D)+f2(D)=D3乘法：f1(D)*f2(D)=D4+D2+D+D3+D+1=D4+D3+D2+1除法：f1(D)/f2(D)D2+DD+1D3+D+1D3+D2D2+D+1D2+D12023/7/3163多項(xiàng)式的運(yùn)算加法：f1(D)=D3+D2023/8/564如果一個(gè)(n,k)線性碼具有以下的屬性，則稱(chēng)為循環(huán)碼(cycliccode):如果n元組c={c0,c1,…,cn-1}是子空間S的一個(gè)碼字，則經(jīng)過(guò)循環(huán)移位得到的c(1)={cn-1,c0,…,cn-2}也同樣是S中的一個(gè)碼字；或者，一般來(lái)說(shuō)，經(jīng)過(guò)j次循環(huán)移位后得到的

c(j)={cn-j,cn-j+1,…,cn-1,c0,c1,…,cn-j-1}也是S中的一個(gè)碼字。2023/7/3164如果一個(gè)(n,k)線性碼具有以下的屬性2023/8/565碼字c={cn-1…c1,c0}的各個(gè)分量可以看作是多項(xiàng)式c(D)的系數(shù)，即

c(D)=cn-1Dn-1+…+c1D+c0

每一項(xiàng)的存在或不存在對(duì)應(yīng)了n元組中相應(yīng)的位置為1或0，如果cn-1非0，那么多項(xiàng)式的階數(shù)為n-1。2023/7/3165碼字c={cn-1…c1,c0}2023/8/566如（7，3）循環(huán)碼的全部碼字為：

2023/7/3166如（7，3）循環(huán)碼的全部碼字為：2023/8/567為了便于計(jì)算，常用碼多項(xiàng)式表示碼字，如（n，k）循環(huán)碼，其多項(xiàng)式表示為：第2號(hào)碼字可用多項(xiàng)式表示為：2023/7/3167為了便于計(jì)算，常用碼多項(xiàng)式表示碼字，如2023/8/568生成多項(xiàng)式g(D)及生成矩陣G如果一種碼的所有碼多項(xiàng)式都是多項(xiàng)式g(D)的倍式，則稱(chēng)g(D)為該碼的生成多項(xiàng)式。在循環(huán)碼中，次數(shù)最低的多項(xiàng)式（0除外）就是生成多項(xiàng)式g(D)，其他碼多項(xiàng)式都是其倍數(shù)。且該g(D)的階數(shù)為r=n–k，常數(shù)項(xiàng)為1，是Dn+1的一個(gè)因式。為了尋求生成多項(xiàng)式，必須對(duì)Dn+1進(jìn)行因式分解。2023/7/3168生成多項(xiàng)式g(D)及生成矩陣G如果一2023/8/569以D7＋1為例：

D7+1=(D+1)(D3+D+1)(D3+D2+1)

這樣，我們可知，

（n，k）

g(D)

（7，6）

D+1

（7，4）

D3+D+1或D3+D2+1

（7，3）

(D+1)(D3+D+1)或

(D+1)(D3+D2+1)

（7，1）

(D3+D+1)(D3+D2+1)

2023/7/3169以D7＋1為例：2023/8/570循環(huán)碼的生成矩陣多項(xiàng)式為：

然后將系數(shù)提出就得到生成矩陣G。2023/7/3170循環(huán)碼的生成矩陣多項(xiàng)式為：2023/8/571例如，已知（7，4）碼的生成多項(xiàng)式g(D)=D3+D2+1，求生成矩陣。解：k=4

這樣我們就可直接得到生成矩陣G為：2023/7/3171例如，已知（7，4）碼的生成多項(xiàng)式g(2023/8/572由A＝MG，其中M=[mk-1mk-2…m1m0]表示輸入信息碼元序列，我們可求出編碼后的輸出碼組序列，但這樣得到的循環(huán)碼不是一個(gè)系統(tǒng)碼。所謂系統(tǒng)碼，指的是碼組A的左邊k位與M中的k個(gè)元素相同，而后面n–k位是M中元素的線性組合，表示監(jiān)督碼元。為了得到系統(tǒng)碼，就要求G矩陣的左邊是一個(gè)k階的單位陣，即是一個(gè)典型生成矩陣G=[IkQ]形式。2023/7/3172由A＝MG，其中M=[mk-1mk-2023/8/573這樣的系統(tǒng)碼用多項(xiàng)式表示即為：

A(D)=Dn-kM(D)+r(D)

式中M(D)是不大于k-1次多項(xiàng)式，Dn-kM(D)是不大于n-1次多項(xiàng)式，r(D)是不大于r-1次多項(xiàng)式，稱(chēng)為監(jiān)督碼多項(xiàng)式，它等于Dn-kM(D)除以g(D)得到的余式，表示為

r(D)=Dn-kM(D)modg(D)

或2023/7/3173這樣的系統(tǒng)碼用多項(xiàng)式表示即為：2023/8/574由于典型生成矩陣G=[IkQ]形式，與單位矩陣Ik每行對(duì)應(yīng)的信息多項(xiàng)式為：

Dn-kmi(D)=Dn-kDk-i=Dn-i

，i＝1,2,…,kri(D)=Dn-imodg(D)

由此得到生成矩陣中每行的碼生成多項(xiàng)式為：

Ci(D)=Dn-i+ri(D),i=1,2,…,k

這樣系統(tǒng)循環(huán)碼生成矩陣多項(xiàng)式的一般表示式為：

2023/7/3174由于典型生成矩陣G=[IkQ]形2023/8/575例2：我們?cè)賹?duì)前面我們的例題進(jìn)行求解，已知g(D)=D3+D2+1，希望給出系統(tǒng)循環(huán)碼的生成矩陣。解：

r1(D)=D6modg(D)=D2+Dr2(D)=D5modg(D)=D+1r3(D)=D4modg(D)=D2+D+1r4(D)=D3modg(D)=D2+1

所以，我們可寫(xiě)出生成矩陣多項(xiàng)式為：2023/7/3175例2：我們?cè)賹?duì)前面我們的例題進(jìn)行求解，2023/8/576

生成矩陣G可寫(xiě)為：其實(shí)這個(gè)矩陣我們也可以通過(guò)初等變換從第74頁(yè)的矩陣得到。2023/7/3176生成矩陣G可寫(xiě)為：2023/8/5772023/7/31772023/8/578監(jiān)督多項(xiàng)式h(D)和監(jiān)督矩陣H由于GHT=0,對(duì)循環(huán)碼相應(yīng)的有g(shù)(D)h(D)≡0,mod(Dn+1)監(jiān)督矩陣多項(xiàng)式可寫(xiě)為：其中系數(shù)不同??！2023/7/3178監(jiān)督多項(xiàng)式h(D)和監(jiān)督矩陣H由于G2023/8/579例如：（7，3）循環(huán)碼的生成多項(xiàng)式為g(D)=D4+D3+D2+1，求其監(jiān)督矩陣。解：2023/7/3179例如：（7，3）循環(huán)碼的生成多項(xiàng)式為g2023/8/580循環(huán)碼的編碼和譯碼我們知道，系統(tǒng)碼用多項(xiàng)式表示即為：

A(D)=Dn-kM(D)+r(D)

編碼的關(guān)鍵是求出r(D)，而r(D)則要通過(guò)

來(lái)求解。

2023/7/3180循環(huán)碼的編碼和譯碼我們知道，系統(tǒng)碼用2023/8/581例：已知（7，4）系統(tǒng)循環(huán)碼的生成多項(xiàng)式為g(D)=D3+D2+1，若信息碼為1001，求編碼后的循環(huán)碼組。解：信息碼多項(xiàng)式為M(D)=D3+1，其對(duì)應(yīng)的碼組為10010112023/7/3181例：已知（7，4）系統(tǒng)循環(huán)碼的生成多項(xiàng)2023/8/582多項(xiàng)式除法可以用帶反饋的線性移位寄存器來(lái)實(shí)現(xiàn)。g(D)與移位寄存器的反饋邏輯相對(duì)應(yīng)。如假設(shè)g(D)=D6+D5+D4+D3+1，則采用內(nèi)接異或門(mén)的電路如下圖所示，2023/7/3182多項(xiàng)式除法可以用帶反饋的線性移位寄存器2023/8/583以（7，4）系統(tǒng)循環(huán)碼為例，已知它的生成多項(xiàng)式為g(D)=D3+D2+1，所對(duì)應(yīng)的編碼電路入下圖所示。2023/7/3183以（7，4）系統(tǒng)循環(huán)碼為例，已知它的生2023/8/584“與”門(mén)1在1拍～4拍接通，其余時(shí)間斷開(kāi)；“與”門(mén)2在5拍～7拍接