信息論與編碼課件第5章

第五章信息論對(duì)于每一個(gè)有噪聲存在的信確如何來構(gòu)造這組信號(hào)也沒有保證在現(xiàn)實(shí)世界上確實(shí)可以建立起這樣的通信系差錯(cuò)控制編碼是信道編碼的重要組成部。通過線性分組碼來闡明碼的編碼方力。性分組碼中，有一類所謂循環(huán)碼，別是通信系統(tǒng)中在本章最后一。在大多數(shù)通自動(dòng)控制系統(tǒng)和計(jì)所以我們也主要是在二元域F2中來討論糾不難直接推廣到任意有限Fq上去。道編碼的基本概念一.有擾信道噪噪聲是指信息系統(tǒng)中導(dǎo)致有用信號(hào)失真信道，噪聲不可忽略的信道稱為有擾信道。k(t)n(t)，它的存在獨(dú)立于有用信②自然噪聲，③內(nèi)部噪聲。信號(hào)在有中的傳輸過程可用下式來eo(t)=k(t)·ei 其中，ei(t)為發(fā)信端發(fā)出的信號(hào)，eo(t)為接收端收到的信號(hào)。我們希望k(t)=K（常數(shù)，n(t)=0.ei(teo(t譯編解調(diào)調(diào)制媒質(zhì)所經(jīng)過的所有轉(zhuǎn)換器及傳輸媒質(zhì)統(tǒng)稱為編ei(teo(t譯編解調(diào)調(diào)制媒質(zhì)5-1廣義信道示意 p(y1/x1) p(y2/x1p(y2/x1)p(y1/x2)p(y2/x2)發(fā) 收端 5-2二元信道模型5-2所表示的是一般二元信道的模型。p(yj/xi)xiyj的概率，稱為轉(zhuǎn)移概率(i,j=1,2).也可以用表格表示，如表5-1；或用矩陣表示，如式(5-P(y/x)

p12

表5-1元信道轉(zhuǎn)移概p(yp(y/x)y1 y2x1x2p(y1/x1) p(y2/x1)p(y1/x2) p(y2/x2)

p22

其中pijp(yj平均錯(cuò)誤概率的計(jì)算由式（5-3） pep(xi)p(yi/xi

i

jp(y/x)y1y2x10.80.2x20.40.6例5-1p(y/x)y1y2x10.80.2x20.40.6P(y

x)

p(x10.6p(x20.4時(shí)，平均錯(cuò)誤概率pe=p(x1)·p(y2/x1)＋p(x2)·p(y1/x2)=0.6×0.2＋0.4×0.4=無二元對(duì)稱信道，而道為對(duì)稱信道。在二元信道中，若p(y2/x1)p(y1/x2)的數(shù)字信道我們所討論的主要種信道二元?jiǎng)h除它的模型5-3所示。其中q為錯(cuò)誤概1率，x

pqpqx15-3BEC號(hào)按錯(cuò)碼分布規(guī)律的以下態(tài)分布的白噪聲引起的錯(cuò)碼就具有這種性產(chǎn)生突發(fā)錯(cuò)碼的主要原因是脈沖干擾和信道現(xiàn)象。響，則需從其它途徑解決。進(jìn)行信道是其中一種重要而有效的統(tǒng)的能力。由于我們僅討論第二類，近年來，編碼理論發(fā)展十分迅速。主要擁擠。如何有效地利用信道，可靠地So/NoB按指數(shù)律增加。而調(diào)集成電路和計(jì)算機(jī)通信的發(fā)展也是編碼理下面我們以打?yàn)槔齺碚f明信道編“別用01當(dāng)收0時(shí)就認(rèn)為是無雨，當(dāng)收到1時(shí)就認(rèn)為是有雨。當(dāng)把0錯(cuò)收為1時(shí)，就會(huì)把無雨當(dāng)成有雨。我000表示無雨111表示有雨。例如，發(fā)送000時(shí)，由于干擾而錯(cuò)收為010.在假定三個(gè)碼元中最多有一個(gè)碼元發(fā)生錯(cuò)誤時(shí)，我們就可以認(rèn)為發(fā)送的是000，而不是111.這樣的編碼具有糾正一位錯(cuò)碼的能多可有兩個(gè)碼元發(fā)生錯(cuò)誤，例如，把000錯(cuò)收為011，我們就無法確定發(fā)送的是哪一個(gè)個(gè)碼元都發(fā)生錯(cuò)誤這樣可能會(huì)將000錯(cuò)收為111這時(shí)， 仍以上述為例，假如老王只是一個(gè)那么他可以，但是無法確定是哪個(gè)字聽錯(cuò)了進(jìn)制數(shù)來表示，見表5-2。但是這樣的代碼錯(cuò)，都會(huì)使一個(gè)消息錯(cuò)收成另一個(gè)消且無法被接收者發(fā)現(xiàn)如果將上述1位碼“1偶數(shù)個(gè),如表5-2所示收端就可以發(fā)現(xiàn)代碼中的1位3位錯(cuò)碼，但是無法確定哪一位

5-2監(jiān)晴0云1陰1雨0“1代碼中原有的代表消息的碼元稱為信息督位n位長(zhǎng)的碼字。這些碼重復(fù)碼和奇偶監(jiān)督碼是兩種最簡(jiǎn)單的編一種適合實(shí)際需要既具有較強(qiáng)的現(xiàn)的編碼。這就是對(duì)信道編碼的基本要道編碼的分檢錯(cuò)碼只能在譯碼中自動(dòng)發(fā)現(xiàn)錯(cuò)誤糾錯(cuò)碼不僅能發(fā)現(xiàn)而且能自動(dòng)糾正糾刪碼能自動(dòng)糾正和刪除錯(cuò)誤根據(jù)信息元與監(jiān)督元的關(guān)系線性碼監(jiān)督元與信息元之間是線性關(guān)系。非線性碼監(jiān)督元與信息元之間不是線性關(guān)分組碼監(jiān)督元僅與本組的信息元有卷積碼監(jiān)督元不僅與本組而且與前后若干糾正隨機(jī)錯(cuò)誤的碼；糾正突發(fā)錯(cuò)誤的正混合錯(cuò)誤的碼；糾正同步錯(cuò)誤的碼述劃分方法用圖5-4來表示。5-4信道編碼分類檢錯(cuò)重發(fā)法（ARQ）接收端在收到的前向糾錯(cuò)法（FEC）接收端在收到的反饋校驗(yàn)法收端將收到的消息全部返回到發(fā)端，由發(fā)端進(jìn)行檢測(cè)，發(fā)現(xiàn)錯(cuò)誤后，ARQ系統(tǒng)組成方框圖發(fā)發(fā)收檢錯(cuò)檢錯(cuò)糾檢糾檢5-5差錯(cuò)控制方法信編和緩存雙向譯緩存信源重發(fā)控指令產(chǎn)錯(cuò)誤時(shí)宿圖5- 組碼和信道編碼定理一.分組碼的概念它分成信息組，每個(gè)信息組有k位碼元，因而可有2k種不同的全體構(gòu)成F2{0,1}上的一k維向量空間，記作：Vk(F2).Vk(F2)={(mk－1mk－2…m1m0=0,1,…,m表示。m=(mk－1mk－2…m1m0的能力把每個(gè)k位長(zhǎng)的信息組變換（n＞k.A稱為碼長(zhǎng)n，信息位為k的碼r=n－k位，它們不含有信息，但可r個(gè)監(jiān)督元可以分布在碼字的不同位置上，若恰好集中rk位碼元衡量分組碼性能的一個(gè)重要參數(shù)是分組用R表示：R=k/ 分組碼的另外兩個(gè)重要參數(shù)是碼重碼距abA中的兩個(gè)碼a=(an－1an－2…a1b=(bn－1bn－2…b1b0)定義為碼0碼元的個(gè)數(shù)，wa表示 ai∈F2時(shí)

wa

i0

ai∈Fq

waai0所有非0碼字的碼重當(dāng)中最小的一個(gè)稱最小碼重wmin表示定義碼距又叫漢明（Hamming）距離，值不同的個(gè)數(shù)d并用dmin≠0)表ai,bi∈F2時(shí)，d(ab

aii

aibi∈Fqd(a,b)

1i0aibia= ),b= )碼字awa=4b的重量wb=3碼字ab之間的距d(ab5設(shè)某種三進(jìn)制碼中的兩個(gè)碼字為a= ),b= )碼字awa=4b的重量wb=3碼字ab之間的距d(ab5{00000011001}它的最小碼wmin2;最小碼dmin2除了上節(jié)介紹的重復(fù)碼和奇偶監(jiān)督碼之二維奇偶監(jiān)督碼（方陣碼它是把上述奇偶監(jiān)督碼的若干碼字排成的方向增加第二監(jiān)個(gè)監(jiān)行。如圖5-7所示，最右邊的一列是一維a21

a22am

a2n amn5-7。能被發(fā)現(xiàn)數(shù)情形的錯(cuò)誤不能被發(fā)現(xiàn)。。方陣碼保留了一維奇偶監(jiān)督碼的編碼效率高的優(yōu)點(diǎn)。當(dāng)碼長(zhǎng)為n時(shí)，一維奇偶監(jiān)督.→1m－1n位長(zhǎng)的碼字構(gòu)成一個(gè)矩陣，再加上一行監(jiān)督位行，則構(gòu)成一個(gè)×n階矩陣。它R=(m－1)(n－1)/mnmn→∞時(shí)，同樣R等重碼（恒比碼當(dāng)每個(gè)碼字中所含1的個(gè)這種編碼為因?yàn)?的個(gè)數(shù)恒只要計(jì)算接收碼字1知道是說，它能夠檢測(cè)出碼字中除了“0變1”與“1變0”成對(duì)出現(xiàn)錯(cuò)碼之外的其它所有錯(cuò)優(yōu)點(diǎn)：簡(jiǎn)單和適合做各種鍵盤字符的代缺點(diǎn)：是剩余度大，編碼效率低其中每字都有三個(gè)1和兩個(gè)0.因?yàn)榻M5合數(shù)C3=10,所以碼集中共有十個(gè)這樣的改進(jìn)后能使錯(cuò)碼率降至原來的十分之一左右表5-3a是五單元國(guó)際電碼中的數(shù)5數(shù)保電國(guó)電數(shù)保電國(guó)電1627384950取三碼其中每字都由三個(gè)1和四個(gè)

335個(gè)碼字。見5-3b75-3b國(guó)際通用七中取三 001101 010101 001100 100010 100110 011001D001110 100100 011100 010010 001001 001011G110000 001010H101001Z011000 111000100001J010001101100 000101010011 110001000111 101000110100 101010(不用000011 100011011010 100101α010100 000110β010110 110010正反，1的個(gè)數(shù)而定?，F(xiàn)以電報(bào)通信中常用的五單元電碼為例說報(bào)通信用的正反碼的碼長(zhǎng)n=10..位中有奇數(shù)個(gè)1時(shí)，監(jiān)督位是位中有偶數(shù)個(gè)1時(shí)，監(jiān)督位是例5-3若信息元為11001碼字為.接收端譯碼的方法先將接收向B的前五ML異或，得到一個(gè)合成碼組Q，即：B= Q=然后，由此合成碼組產(chǎn)生一組P.產(chǎn)生的方法仍按“偶反奇不反”的規(guī)則M中有1P最后根據(jù)P中1的個(gè)數(shù)進(jìn)行并糾正①若P=00000，則無錯(cuò)碼②若P中有四個(gè)1和一個(gè)0，則信息元在與P中的0對(duì)應(yīng)的位置上有一位錯(cuò)③若P中有四個(gè)0和一個(gè)1，則監(jiān)督元在與P中的1對(duì)應(yīng)的位置上有一位錯(cuò)④若不是上述三種情況，則接收序例5-4發(fā)送碼字為A 碼組Q11001⊕11001＝00000.M中有奇數(shù)個(gè)所以，P=Q=00000.根據(jù)規(guī)則①，無錯(cuò)碼若B= ，則合成碼組Q=10001⊕11001＝01000.由于M中有偶數(shù)個(gè)所以P=Q=10111.根據(jù)規(guī)則②，信息元在第二位上有若B= ，則合成碼組Q=11001⊕01001＝10000。由于M中有奇數(shù)若B= ，則合成碼組Q=10011⊕11001=01010。由于M中有奇數(shù)個(gè)1，所以，P=Q=01010。根據(jù)規(guī)則B中有多個(gè)錯(cuò)碼。R=0.5。漢明（Hamming）使碼字中1的個(gè)數(shù)為偶數(shù)關(guān)系可an－1⊕an－2⊕…⊕a1⊕a0= 因?yàn)樵谂急O(jiān)督碼中1的個(gè)S0在接收端按式(5-7)為校正子或伴隨式由于S0和1無錯(cuò)有錯(cuò)(5-7)類似的監(jiān)督方校正子S1和S2)00011011例如前面的重復(fù)碼{000,111}就具有這A=(a2a1a0)，則有a2a1a0，即a2a1，a2a0，a2⊕a10，a2⊕a00。因此它的兩個(gè)監(jiān)督方程為

S2

S2

容易驗(yàn)證SS1S200時(shí)，表示無錯(cuò)S=11,10,01時(shí)，分別表示碼元a2,a1,a0發(fā)生了錯(cuò)誤。而把a(bǔ)1a0們也可a1a0當(dāng)做信息位，而把其余兩位

S2

校1 校111110101011100010001000無若繼續(xù)增加監(jiān)督碼情況。一般說來，增r個(gè)監(jiān)督碼元，可以產(chǎn)生r個(gè)監(jiān)督方程，能組碼，其監(jiān)督位數(shù)r=n－k，若想指示出所有一位的錯(cuò)碼情況（共有n種，則要求：2r－1≥n或2r≥n＋1 能使式(5-10)中等號(hào)成立的編碼就是漢明碼?？梢姶a長(zhǎng)n=3的重復(fù)碼同時(shí)又是一種漢明下面再舉一個(gè)例子來說明如何具體構(gòu)造5-5設(shè)(nk)分組碼k4為了能糾正一位錯(cuò)碼，根據(jù)式(5-102rn＋1k＋a6a5,…,a1,a07S=(S1S2S3)表示三位校正子，并按表5-4建立校生在a6a5a4a2S1=1，否則S10這就意味a6a5a4a2四個(gè)碼元與S1有關(guān)，可構(gòu)成一個(gè)偶監(jiān)督關(guān)系式：a6

S1a6

S2

a6

S3a6a5a6a5a6

0

a6a5a4a3當(dāng)作信息位，把其它三位a6

a2a6

a1

a6

a0可見，只要給出信息位a6a5a4a3,就可按上式求出a2a1a0的值而可以得到這種碼的全部碼字，見表5-5.5-5(7,4)漢明碼信息監(jiān)督信息監(jiān)督a6a5a4aa2a1aa6a5a4aa2a1a0000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111當(dāng)接收到一個(gè)n元序列時(shí)，先按式(5-11)并予以糾正。例如，接收到的n，由式(5-11)可求得(S1S2S3)= 不難求出，漢明碼的編碼R=k/n=(2r－1－r)/(2r－1)n很大時(shí)，R趨近1.所以，漢明碼是先介紹幾個(gè)發(fā)送向量：aan－1an－2…a1接收向量：bbn－1bn－2…b1錯(cuò)誤格式：een－1en－2…e1e0a⊕b，其中ei=ai⊕bi;i=0,1,…,(n－1)。e1的個(gè)數(shù)ab時(shí)的ab的漢明距離等于t時(shí)，我們就t重錯(cuò)誤圖樣。由概率的知識(shí)可知，ab的概率為pt=pt(1－p) pt＋1=pt＋1(1－p) 用式(5-15)去除式(5-16K=pt＋1/pt=p/p＜0.5時(shí)，有K＜1，即：pt＋1pt上述結(jié)果表明，碼字在平均錯(cuò)誤概率0.5的二元無信道中傳輸時(shí),發(fā)生一個(gè)＋1)重錯(cuò)誤的概t重錯(cuò)誤的.絕大多數(shù)信道中p<<0.5但在理論證明過程中，還必須考慮p>0.5的情況，而在況下，只要把接收向量取反碼就一定可使p<0.5，從而上述p=0.5而錯(cuò)誤重?cái)?shù)等于發(fā)送向量與接收向量間的離的性質(zhì)，然后，再給出最小碼dmin與糾漢明距離的性質(zhì)對(duì)任abc有d(a,b)

0a

⒉對(duì)稱性：d(a,b)=d(b, d(a,b)＋d(b,c)≥d(a, 明距離的定義來證，下面只證性3。aan－1an－2…a1a0bbn－1bn－2…b1b0),c=(cn－1cn－2…c1c0)。ac時(shí)，由性1d(ac0仍由性質(zhì)1的非負(fù)性可得式(5-19)的左端≥0故=ci不能同時(shí)成或者ai≠bi,或者bi≠ci，二者必居其一。因此式(5-19)總有左≥右，于是性3成立。定理5-1碼距dmin與糾檢能力的關(guān)A是碼長(zhǎng)為n的分組碼，最小碼距dmin總存在tt1t2使下列命題成立dmin≥t＋1時(shí)，A是可以檢測(cè)所≤t重錯(cuò)的檢錯(cuò)碼tdmin≥2t＋1時(shí)，A是可以糾正所≤t重錯(cuò)的糾錯(cuò)碼tdmin≥2t1＋t2＋1時(shí)，A是可以糾正所有≤t1重錯(cuò)并同時(shí)檢測(cè)≤(t1＋t2)重錯(cuò)的糾檢碼，簡(jiǎn)稱為“t1(t1＋t2)碼”證Ai（≤t的錯(cuò)誤圖樣，由性質(zhì)3得d(Aj,Ai＋e)＋d(Ai＋e,Ai)≥d(Aj,Ai)≥t＋1由假設(shè)d(AiAi＋e)≤上式減去此式得：d(Aj,Ai＋e)≥t＋1－t=1此式說明，A中任字發(fā)生≤t重錯(cuò)誤都對(duì)于(2)dmin≥2t＋1e重?cái)?shù)≤t的錯(cuò)誤圖樣，由性質(zhì)3得d(Ai＋e,Aj＋e)＋d(Ai,Ai＋e)＋d(Aj,Aj＋≥d(Ai,Aj＋e)＋d(Aj,Aj＋e)≥d(Aj,Ai)用此二式去減上式得Aj＋e)此式說明，A中任意兩個(gè)碼字發(fā)生t重錯(cuò)（已知dmin≥2t1＋t2＋1，設(shè)是t2]區(qū)間的錯(cuò)誤圖樣dmin≥2t1t2＋1>2t1＋1,（2）t1重的＋＋(＋,A＋(＋,d(Ai＋e d(AjAj＋e)≤t1用此二式去d(Ai＋e,Aj＋e)≥1A量能在糾正t1重錯(cuò)的同時(shí)檢測(cè)(t1＋t2)重錯(cuò)。 上述結(jié)論的幾何解釋見圖5-8.11t11tt1 例5-6某分組碼A={A1,A2,A3,A4}。其中 A1=(000000),A2=(011101),A3=(100111),A4=(111010).容易求得其最小碼距為dminmin{d(Ai,│i,j=1,2,3,4;i≠j}=4dmin3＋1t3.A可3碼，它可檢測(cè)所有≤3重的錯(cuò)誤dmin＞2×1＋1，即t1dmin=2×1＋1＋1t1=1，t21,t1＋t22,A可作成糾12碼。它由于經(jīng)過信道編碼的數(shù)字信號(hào)具有一定碼錯(cuò)誤率即誤碼字率pw.下面介紹它的計(jì)i重錯(cuò)誤的概率為：pi=pi(1－p)當(dāng)碼長(zhǎng)n時(shí)，所有可能i重錯(cuò)誤圖樣nCi種，所以碼字中發(fā)in概率為pCpC

i=

ipnC假定這種碼的糾檢能t，即能糾正或檢t重的接nC1

i

CCp(1n

p)ni從而得到誤碼字率為1pip i

pi(1

p)

或

it

pi(1

p)ni

5-7仍以上例中的分組碼A為例。信道平均誤碼率p=0.01誤碼字pw解：上例中碼長(zhǎng)n6（1）A被用作檢錯(cuò)碼時(shí)，它的檢錯(cuò)能力=根據(jù)pi=pi(1－p)n－i，可求出p0= p1= p2= p3=9.70299×10－7 又∵C60= C1= C2= 63=6 i從而得誤碼

1C6i

i（2）A被用作糾錯(cuò)碼時(shí)，它的糾錯(cuò)能力=1，可得誤碼字率為16wi 1Ci6wii

t2=2，同理可得誤碼字率為：1Cpipi ii

檢約降低為原來68用作糾錯(cuò)碼低為原來的6.8分之這種可靠性的提高是以有效性的降低為代價(jià)A中只有klog42，而碼n6位，編碼效率只有三備碼與漢明錯(cuò)碼，必須增加r個(gè)監(jiān)督r個(gè)監(jiān)取值共有2r碼情況建立2式右邊的第一項(xiàng)表示n個(gè)碼元都不發(fā).n生一位錯(cuò)碼的情況n種，即C1nn要糾正兩位以下的n碼元中發(fā)生兩位錯(cuò)碼的情況有C2n位錯(cuò)碼與一位錯(cuò)碼是完全不同的情況共有(C0＋C1＋C2)種情況。因此碼字 督元的個(gè)數(shù)2

0

＋C 碼字中所有≤t則監(jiān)督元的數(shù)目必須滿足nn或

0

1＋…＋Cnntnn2r

Ci

nin稱式(5-22)為漢明不等式若恰有一種編碼使?jié)h明不等式中的等號(hào)成立，則稱這種碼為完備碼。在完備碼中，較正子的取值恰好與所有≤t重的錯(cuò)誤圖樣有≤3重的隨機(jī)錯(cuò)誤。我們借助計(jì)算機(jī)，在n≤4096的范圍內(nèi)，除了漢明碼和重復(fù)碼之組為(n,krt2312113),另一組為(n,krt9078122).前者正是上述的(23,12)碼，后者為(90,78)碼。不過人們(90n還存在滿足漢明不等式的以上的討論僅限于二元域q元內(nèi)討論，漢明不等式應(yīng)改為下式tnqr(q1)iCini人們?cè)谌騼?nèi)(q3)還找到一種糾多錯(cuò)的完備碼，即(11,6)碼，它可以糾正≤2位的2r2nk

2k

Ci

2k ntintCni0令此式右端的值的整數(shù)部分為M 2 2tM t

Ci

nM為漢明界2k≤M，它表示準(zhǔn)用碼組的個(gè)數(shù)不得超M.我們總希2k等于M.但是尋找完備碼是很的，人們只五.信道編碼定理（香農(nóng)第二編碼定理從分組碼糾檢能力dmin的關(guān)系來看要想提高糾檢能力，必須增大dmin，也就是要增加監(jiān)督碼元的數(shù)目。似乎要想無錯(cuò)傳YCH就要無限增大監(jiān)督碼而使編碼效率R無限YCH一個(gè)出乎意料的結(jié)論只要信息速率不超過

定理5-2香農(nóng)第二編碼定理將熵為H(bit/符號(hào))的信源接至信道容量為C(bit/符號(hào))的有錯(cuò)系統(tǒng)時(shí)，則有：H＜C，總存在著無錯(cuò)傳輸?shù)木幋aH＞C不存在無錯(cuò)傳輸?shù)木幋a方法H＞C（這個(gè)定理可以用圖5-9來表示（（是嚴(yán)格的證明（對(duì)證明感的讀者請(qǐng)看本書末所介紹的有關(guān)參考文獻(xiàn)設(shè)信道輸入端的熵為H(X)CmaxH(X)H(XP(

/Y

CmaxH(Y)H(Y/XP(又設(shè)信源消息的熵H，將消息序列k有2kH個(gè)就幾乎是全部。再從信道碼2kH(X)個(gè)碼元序列作為碼字。適當(dāng)安排碼符HH(X)＜C并建立消息H(Y/X)x1就和2kH(Y/X)個(gè)接收向量的y1相對(duì)應(yīng)；同樣x2對(duì)應(yīng)y2；…，xiyi；…。如果這些向量的集合y1,y2,…,yi,…不，也就得隨著k的增大可使部分的概率趨于零。又因?yàn)榻邮障蛄靠偣灿?kH(Y)以它所包含的yi2kH(Y)/2kH(Y/X)=2k[H(Y)H(Y/X)]H(Y)－H(Y/X)＜C，這就說明了只要2kH2kC，就可以實(shí)現(xiàn)無錯(cuò)編碼，相當(dāng)于圖反之若y1,y2,…,yi,…之間有則不這時(shí)，在信息kH中，只能傳kC的信息量k(H－C)的信息量不能傳輸，故H(X/Y)為(H－C)5-9（3）區(qū)pwenE(R) 其中pw為誤碼字率；n為碼長(zhǎng)；E(R)為誤是信R＜CE(R)＞0息速R小于C，就能保E(R)0，于是n→∞時(shí)pw→0。但在n間是有的糾錯(cuò)編碼理論本身正是在為了說明香農(nóng)第二編碼例5-8設(shè)有一個(gè)隨機(jī)產(chǎn)生二進(jìn)制序列的信源和一個(gè)平均誤碼率p0.01的二元對(duì)稱信道。若直接傳送

碼00000001101001則誤碼率顯然為0.01.R=k/n=0.5的編碼效率進(jìn)行編碼。先k=2分組，然后編出碼長(zhǎng)為4的(4，2)的分組碼。組和對(duì)應(yīng)的碼字如表5-6所示。譯碼碼字12個(gè)禁用碼組別列于碼字之收向量落入哪一列就譯為哪一列所對(duì)應(yīng)的5-7(4,2碼碼由譯碼表可以看出發(fā)送的碼字在傳輸5-7可以計(jì)算出這種(42)碼的誤碼字率約0.0103，幾乎和原來一樣。（6，3）此時(shí)保持不變。其編、譯碼表見表5-8由表5-8可知，發(fā)送碼字的六位碼元中任字率降低為0.00136，約為原來信道誤碼率的七分之一?？梢奟不變的情況加碼長(zhǎng)為n可以使誤碼字率迅速下降組性分組碼一.線性分組的定義和性質(zhì)對(duì)于分組碼n按前述譯碼查找工作量從含有2n個(gè)向量的譯碼表里查出接收向量所在的位碼表都無法建立據(jù)估計(jì)整個(gè)系里原的個(gè)數(shù)101402465即使用個(gè)原子存貯一個(gè)碼字，也只能存貯2465個(gè)碼) 看作是n維向空間Vn(F2)中的一個(gè)向那么，分組碼的全部碼字一定是Vn(F2)的一個(gè)看作線性代數(shù)中的一種代數(shù)結(jié)構(gòu)——線性Vn(F2)F2上的nA是它的一k稱A是碼長(zhǎng)為信息位為k的線性分組碼，值得的是Vn(F2)的加法群的子群一是個(gè)線性子空間，因此我們說，如果A是A線性碼的性質(zhì)封閉性根據(jù)群的性質(zhì)可知，線性分組AVn(F2)2加法和仍然在A的模22加與模2減是等效的，故將A2A1=A2⊕A3恒等性因?yàn)閷?duì)任意Ai∈A，有Ai⊕0=0⊕Ai=Ai個(gè)碼字之間的距離必然等于另字的重線性分組碼的最小碼距等于它的最小碼重，即dmin=wmin.這就為我們尋找它的最小碼利用性質(zhì)12，我們可以方便地上節(jié)5-8所給出的(6，3)碼二.線性分組碼的構(gòu)造原理和生成矩k維子空間的基k個(gè)線性無關(guān)的向量組成的。設(shè)(n，k)線性碼A的一組基底向量為g1g2,…gk,用它們構(gòu)成一個(gè)kn的矩陣g1g gG 2

...g g kAi=Mi·G其中Mi=(mk－1，mk－2，…，m0任一信息組這里2乘及模2加都用算術(shù)乘和算2乘及2加。反之，g1,g2,…,gk的任意一個(gè)線性組合都是A中的碼向量G叫做線性碼A的一個(gè)生成矩陣A都可比其編的存貯量可由原來的2k個(gè)碼向量減少Gk個(gè)向k465時(shí)，只要存465個(gè)向量就夠了。由于A的基底不是唯一以同一性碼A，可以有多個(gè)生成矩陣。由線性代數(shù)的理論可知，F(xiàn)2上的兩個(gè)秩為k的k×n階矩陣GG′是同一線性A的兩個(gè)生成矩陣要條件是存在一個(gè)k階可逆矩陣K，使KG=G′，或者說GG′行等對(duì)其另一個(gè)。因此，要確定一切碼長(zhǎng)為n，維數(shù)為k的二元線性碼，只要定出F2上的一組兩兩不行等價(jià)的秩kk×n階矩陣即定義單位列單位陣I中的每一個(gè)列向量都稱為單順序分別記作I1,I2,…,Ik.即：II1I2Ik定義典型陣如果一個(gè)k×n階矩陣V的前k列恰好構(gòu)成一個(gè)單位陣，則稱矩陣V為典型陣，記做Vo.Vo=[Ik,Q定義準(zhǔn)典型k×n階矩陣矩陣V為準(zhǔn)典型陣，記Vs.定義非單位列矩陣中未被選作單位所有的非單位列按順序構(gòu)成的矩陣記Qs.如果只G進(jìn)行行初等總能將它化Gs=[l1，l2，…，ln] 其中l(wèi)ii1，2，…，n)Gs中的列向量。假定在n個(gè)列向k個(gè)單位列：li1,li2, ,lik若用GsM進(jìn)行編碼，即：MA,則有ai1mk－1,ai2mk－2,…,aikm0即碼字中的i1,i2,…,ik位碼元分別與信息組的第k－1,k－2,…,0位相其余的碼mk－1,mk－2,…,m0的的線性組合。因此，我們可以把碼字中的i1,i2,…,ik位看如果不僅對(duì)G進(jìn)行了行進(jìn)行了列置換，那么總能化成典型陣G0 [Ik,Q] 其中Ikk階單位矩陣，Q是任一k×r階矩陣(r=n－k).可以看出G0所生成k位就是原來的信息位，后r位則是監(jiān)督位，稱種碼為系統(tǒng)碼。而典型生G0就是系G經(jīng)行初等變換和列置換后GGG″不能生成同一能力的是碼字中1的個(gè)數(shù)G先經(jīng)過行初等變換得到G′，因?yàn)樗鼈兪切械葍r(jià)的，所以可生成同空間A；而再由G′經(jīng)過列G″，由于列置換不會(huì)改變碼向量中1而不會(huì)改變碼的糾檢錯(cuò)能力G″生成的碼空間AA″相同的糾檢錯(cuò)能力且稱GG″互為組合5-9在以前介紹的漢明碼的例子

a6

a2a6

a1

a6

a0若用矩陣表示，可

11Q00

00 11 Q的左邊補(bǔ)充一k階單位陣便可得到典型生成矩G0：04 04

00,Q

0 0 1 1任意給信息都可求出它所對(duì)應(yīng)的碼字Ai= 對(duì)所有的碼A 0000001110011010101011000G'00不難驗(yàn)證，由G′所生成的碼空間與表5-55兩列對(duì)換得G″： 1G" 1

0 0 1 1不難驗(yàn)證，由G″生成的碼空間A″跟原的最小碼距與A的最小碼距相等三.線性分組碼的監(jiān)督矩1101110101010101100

a a5 此式還可以簡(jiǎn)記為

a0a

H·AT=O 或A·HT=

H

0,Aa6a5a4a3a2a1a0,O 我們稱H方程的定義可知個(gè)碼向量都與H的各行H進(jìn)行一切可能的行初等變換，仍能使式(5-31)Hr的線性組合構(gòu)成了一個(gè)r維的線性子空間A*.A*中的每一個(gè)向量都A正交。由對(duì)偶空間的定義A*與A互為對(duì)偶空看作是一個(gè)(n，r)線性碼A*A互為對(duì)偶碼。HA*的生成矩陣。A的生成矩G同時(shí)又A*的監(jiān)督矩陣。=BHTOB一定是碼向量。BHT≠OB不是碼向量。E，則B=A＋E，代入監(jiān)督方程S=BHT=(A＋E)·HT=AHT＋EHT(5-已知AHT=O，故有 EHT 式中S為較正子伴隨式式可知，S只與錯(cuò)誤圖樣E有關(guān)送向A無定理5-3監(jiān)督矩陣與糾檢能力的關(guān)系定理A是個(gè)線性分組碼H是它的一個(gè)監(jiān)督H的任意t列都線性無關(guān)，而H有(t＋1)列線A的最小碼重等于(t＋1)A是可t重錯(cuò)誤的檢錯(cuò)碼；或者是可以糾正所證：用反證法。設(shè)碼向量Ai∈A，其重量wt，Ai(an－1an－2…a0).又設(shè)A的監(jiān)督矩陣Hhn－1hn－2…h(huán)0]hi為列向量。則AiHT=O.等于0.設(shè)它們ai1,ai2,…,ait.ai1hi1＋ai2hi2＋…＋aithit=0此式表明H中有一t的列向量線A中沒有重量t的碼向量再根據(jù)定理?xiàng)l件H(t＋1)列線性相關(guān)，A中就有重量為(t＋1)的碼向量。A的最小碼重wmin=t＋1由線性碼的性質(zhì)可知，A的最小碼距dmin=wmin然后直接定理5-即dmin與糾（證畢四.生成矩陣與監(jiān)督矩陣由線性代數(shù)的理論n維向空間中對(duì)于其中每個(gè)k維子空間A，總存在一個(gè)與A*就是(n－k)G的秩k，H的秩為(n－k).因?yàn)锳A*互為對(duì)偶空間A*·AT=O，又G∈A，H∈A*所以：A*·GT=O，A·HT=O，G·HT=根據(jù)這些關(guān)們對(duì)GH，只要知典型陣互求典型矩G0H0的互求設(shè)典型生成矩陣為，G0IkQ]則它所對(duì)應(yīng)的典型監(jiān)督矩陣：H0P,Ir].5-10（53線性碼的典型生

G0

00kk

00

,則它的監(jiān)督 P,

1 1其中

P

rnk53生成矩陣（或監(jiān)督矩陣如果有可能，一般總是先把它化成典型再利用G0矩陣G）來。

G

11通過行初等變換得到；

00

HH

1 1由于HH0是行等價(jià)的也就是所要求的H上面的方法只有當(dāng)Gk列能夠假定Gk列不就把它看作對(duì)偶空間A*的監(jiān)督矩陣要求的HA*的典型陣互求法，可以很快地求出H來。

G

11 G

1

換 100換001100010

0HH

G*

具Gkk列都不能化成單位陣，那么這些方法就要失效5-13設(shè)生成矩

G

11Mm2m1m0)，A=(a4a3a2a1a5)，由于MGA，即:(m2m1m0)·G=(a4a3a2a1a0)

式(5-33)＋式(5-35)a4=式(5-35)＋式(5-37)a2=將式(5-34)(5-36)式代入式(5-38)(5-39)式經(jīng)整理得到兩個(gè)獨(dú)立方程

a

a2 它們構(gòu)成了監(jiān)督方矩陣

要求的監(jiān)督雖然解方程組互求法克服了前兩種互求法n較大時(shí)，這種方法是很繁面介紹一種既簡(jiǎn)便又通用的互求法——準(zhǔn)GH時(shí)，其步驟如下（若給定H要求G時(shí)，只要將GHPQH,G,Q,P即可）k個(gè)單位列的先后順序不變，但它們可以散布在n列中的任何位置上）由非單位列按順序構(gòu)成QsPsQTs按下列規(guī)則構(gòu)成Hs（Hs仍是一個(gè)規(guī)則1Hs中的單位列按Gs中規(guī)則2Hs中的非單位列由Ps的各列求的監(jiān)督矩H.5-14仍以前面的例子G化為準(zhǔn)典型陣

G

1

1

注：Gs1、3、4列為單位列，相當(dāng)于一Qss s

P

s1 s1s按上述規(guī)則構(gòu)成ss s

02、5列為單位列Gs中的非單位依次填入Ps的三個(gè)列向服了典型陣互求法不通用為快速互求法時(shí)盡G矩陣k列可Gs,Hs來。0100111001101001111000G 0 0G367列已經(jīng)是單列了k=4產(chǎn)生一個(gè)單位列就可以了又看到第1,5兩列都各有兩個(gè)可以很快化為單位一列。G

G 0101

0 000100110111101010110010

0101

0 000 00后三00

11（2）Gs1367列為單位列24524,5并轉(zhuǎn)置

HH

0 0 如果Gs的單位列恰好k列時(shí)，這種首先證明一個(gè)引理：K·KT=I.K是列置換所對(duì)應(yīng)的矩陣假定這種兩列互換t次，依次設(shè)為K1，K2,…KtKK1…Kt對(duì)于同一個(gè)兩列互換進(jìn)行兩次就等于沒有換，即：KiKi=I (I=1,2,…,t).容易證Ki是一個(gè)對(duì)稱陣，即：Ki= KKT=(K1…Kt)(K1…Kt)T=Kt·KTt…K1T=K1…Kt-1·KTt-1…K1T=…=GsHs經(jīng)過相同的列置K可分別得到典型G0H0，即：GsK= ，HsK=H0根據(jù)GsHs的構(gòu)成規(guī)則G0=[IkQs]H0=[QTsIr]，注2運(yùn)算規(guī)則下，Qs=Qs再由線性代數(shù)的理論可知，G0H0T=O即：(GsK)(HsK)T=GsKKTHsT=O，由引理KKT= GsHsT=O （5-一變換NG=N為可逆∴N－1Gs=N1GsHsT=GHsT=On∴Hs是與 相對(duì)應(yīng)的監(jiān)督矩陣（證畢由上一節(jié)的23表譯碼，不2nn維向量按一定的規(guī)則劃分為2k個(gè)互不相交的子集D0,D1,…,D2k1,使得每個(gè)子集Di僅含一個(gè)碼字Ai.DiAi一一對(duì)應(yīng)。設(shè)發(fā)送時(shí)，接收向量Bi.Bi位于Di之內(nèi)，則把它譯Ai.誤仍Bi位Di則譯碼是正確它們都是由于發(fā)生了最常見的錯(cuò)誤而由Ai下面介紹一2nn維向量的一種方2k個(gè)碼向量置全零碼字為最左面的元素A0=(000).在其余2n－2k個(gè)向量中一個(gè)置于AiE1.然后E2＋AiAi之下(i0，1，…，2k－1).再在余下的向量中任選一個(gè)作為E3，置于E2之下，并按上述r=n－k.AA E1 E1 EE EE1

A2AEA標(biāo)準(zhǔn)陣列的兩個(gè)性質(zhì)定理性質(zhì)定理1陣列的同一行中沒有相同的證：用反證法設(shè)在第l行中有El＋Ai= 設(shè)有一個(gè)向量出現(xiàn)在第lt行，并假定l＜t，則對(duì)于某ij有Et＋Ai=或 Et=碼字，則有：EtEl＋As.這意Et在l行中已出現(xiàn)過這與陣列的構(gòu)成方法。因?yàn)榘匆?guī)定Et應(yīng)該是前面沒有用過這個(gè)定理說明了陣列中每個(gè)向量都不相按可分為2r每一行為一個(gè)陪2k性質(zhì)定理2同一陪集的向量都具有相同陪集首為El＋Ai的伴S=(El＋Ai)HT=ElHT＋AiHT=El即陪集內(nèi)任一元素的伴隨式等于陪集首的用反證法證明定理的第二個(gè)結(jié)l個(gè)陪集和第t個(gè)陪集具有相同的伴隨式，l＜ElHT=EtHT，或(ElEt)HT=這就是說，(El＋Et)AjEl＋AjEt是第l個(gè)陪集中的向量。這與陣列的構(gòu)成（證畢（隨式Syndrome有醫(yī)并的意思收向量Bi與錯(cuò)誤圖Ei“并發(fā)”在同一個(gè)陪集里）選用給定信道下最可能出現(xiàn)的錯(cuò)誤圖樣作陪集首以前曾經(jīng)證BSC低重為最佳標(biāo)準(zhǔn)陣列5-7和表5-8所給出的利用標(biāo)準(zhǔn)陣列譯碼需要從2r個(gè)伴隨式中，再從這個(gè)伴隨式所在行的2k個(gè)向量中找出譯成這個(gè)碼字nk相當(dāng)大時(shí)，這種方80)線性碼，220280都是相當(dāng)大的數(shù)線性碼譯碼步驟如下Bi的伴隨式：Si=BiHT;找出相應(yīng)于這個(gè)伴隨式Ei，并把它作為錯(cuò)誤圖樣：Si=EiHT;A：A=Ai＇就是發(fā)送向Ai5-16利用表5-8進(jìn)行譯碼。因?yàn)檫@是一種(6，3)碼。首先從準(zhǔn)用碼組中選k=3個(gè)線性無關(guān)的碼字作為生成矩陣。為簡(jiǎn)盡量找到一個(gè)典型生成矩2,3 G

11然后再G求出H，容H

0 0 Bi=

0S0SBHT 0 101110011000

找到與SiEi：∵Si=EiHT，Si=(001)∴Ei=(000001)Ai=Bi＋Ei=(110111)＋(000001)=(110110)Ei為單重錯(cuò)時(shí)，HTSiT相同的列恰好與Ei中“1”的位置相對(duì)應(yīng)。若錯(cuò)碼不止1SiHTEi中“1”的位置相對(duì)應(yīng)的那些列向量的模2Ei(7,4)碼為例，給出它的編譯和傳輸過程示意圖（見圖5-10，5-11，5-編信息

000000011100110101000101G (7,4)碼“2運(yùn)算（異或）的簡(jiǎn)記。譯

H

00 5-11(7,4)碼e6e5e4緩存器緩存器 息 5-12（7，4）碼傳輸過程示意一.循環(huán)碼原理使我們能利用線性碼的代數(shù)性質(zhì)對(duì)它進(jìn)行n較大時(shí)，其工作量仍是相當(dāng)可觀的，為易用簡(jiǎn)單的具有反饋聯(lián)接的移位寄存器來譯的復(fù)雜度與碼長(zhǎng)n成正比為線性復(fù)雜度而一般線性碼編譯的復(fù)雜度與n2循環(huán)碼的定A是一個(gè)(nk)線性碼。如果A中任字循環(huán)移位后，仍是A中的碼字，那A是循環(huán)碼。為了易于用代數(shù)理論來討論循環(huán)碼的數(shù)多項(xiàng)式來表示，稱為碼多項(xiàng)式。設(shè)向量Ai=(an—1,an—1,…,a1a0)，那么它所對(duì)應(yīng)的碼多a(x)=an－1xn—1＋an－2xn—2＋…＋a1例5-16下表所給出的線性碼就是循5-9(7,3)循環(huán)序號(hào)信組碼多項(xiàng)012345670000010101001010x4＋x3＋x2＋1x5＋x2＋x＋1x5＋x4＋x3＋xx6＋x3＋x2＋xx6＋x4＋x＋1x6＋x5＋x3＋1x6＋x5＋x4＋x2用多項(xiàng)式表示一個(gè)碼和用向量表示并沒有重要的是要賦于這個(gè)多項(xiàng)式集合以一定的才能達(dá)到建立起循環(huán)碼的目的呢？我們?nèi)?1)，相應(yīng)的多項(xiàng)式為A1(x)=是字A3=(0111010)，相應(yīng)的多項(xiàng)式A4(x)=x5＋x4＋x3＋x=x?A1(x)。再左移循環(huán)一次得到的又是字A7=(110100碼A中的一并且相應(yīng)的多項(xiàng)式等于A6(x1101001).若按上面x3·A1(x)=x7＋x6＋x5＋x3.但 A6(x)=x3?A1(x)所對(duì)應(yīng)的數(shù)字序列為11101它包含了8位碼元同時(shí)由于多項(xiàng)式x7，越出了多項(xiàng)式集合要使它不越出，可以令x71.這樣一來，x3·A8(xx6＋x5＋x3＋1就成立了。照此辦x4·A8(x)=x8＋x7＋x6＋x4x6＋x4＋x＋1.它所對(duì)應(yīng)的A31010011).繼續(xù)下得到（碼的全部碼字的任一個(gè)非零碼字所對(duì)應(yīng)的多項(xiàng)式依次乘以xx2,…，從而得到其它的碼多項(xiàng)式。只要加上代數(shù)結(jié)構(gòu)x71就可以了F2(x7)x7＋1=1，即x7(x7＋1)除,得到的余（73）碼的任一非零碼多項(xiàng)式乘xii=0,1,…,6然除(x7＋1)得到3）碼的其他非零碼多項(xiàng)式一般地可以F[x]

來表示所 x次數(shù)小于n的多項(xiàng)式的集合。即F[x]

={

xn—

xn—2＋…＋a x

i∈F2;i=0,1,…,n－1 而用A[x]來表示

[x]

中所有的碼式集合，即

xA[x]={an－1xn—1＋an－2xn—2＋…＋a0│(an－1an－2…a1a0)∈A 顯然，F(xiàn)2[x]xn＋1中的元素與n維向量Vn(F2)中的元素存在著一一對(duì)應(yīng)的關(guān)即

)a(x)

xn1

xn2

x

1

同樣A[x]中的元素與A中的元素也存在一所以，A[x]F[x

這個(gè)多項(xiàng)式 x合所構(gòu)成的線性空間中的一個(gè)子空間如果在集合F2[x]xn＋1中規(guī)定了加法和乘法a(x)b(x)= a(x)b(x)= 其中a(x),b(x)∈F[x]

x x則F2[x]xn＋1對(duì)于所有規(guī)定的加法和x的多項(xiàng)式模(xn＋1)的環(huán)?，F(xiàn)在我們?cè)O(shè)A是循環(huán)碼，a(x)∈A[x]x和a(x)都屬于F[x] ，所 xn2=(an－1xn＋an2

x2＋ax)10x10x顯然有x⊙a(bǔ)(x)∈A[x].用數(shù)學(xué)歸納法可推出xi⊙a(bǔ)(x)∈A[x], i=0,1,…,n－1.由于F[x]

中任一元素都是若干xi x系數(shù)屬于F2的線性組合，又由于A[x]F[x]

的一個(gè)線性子空間。所以 xm(x)，都有m(x)⊙a(bǔ)(x)∈A[x]A[x]F[x]

的一個(gè)理想 x且A[x]本身就可以由A[x]中次數(shù)最低的多即A[x]{m(xg(x)m(x)ng(x)}且 可以證明

g(x)nk那么xk－1g(x),xk－2g(x),…,xg(x),g(x)就是證G(x)={xk－1g(x),xk－2g(x),…,g(x),g(x)先證G(x)中各元素是線性獨(dú)立的ak－1xk－1g(x)＋ak－2xk－2g(x)＋…＋a1x＋a0g(x)=其中g(shù)(x)=grxr＋gr－1xr－1＋…＋g1x＋g0.x的多項(xiàng)式后，其各項(xiàng)0.首先常數(shù)項(xiàng)應(yīng)0，即：a0g00g0≠0，否g(x)=grxr＋gr－1xr－1＋…＋g1x=x( 1＋gr－1x=0g(x)1)的假設(shè)相，故只有a0=0。接著應(yīng)有0a0g1a1g0=a1g0=0，從而a10ak－1=0。這說明G(x)中各元素是線性獨(dú)立的。次證A[x]中每個(gè)元素都可表示為G(x)中如前所 g(x)∈這里 m(x)=mk－1xk－1＋mk－2＋m1x＋m0 (mk－1,mk－1,…,m1,m0∈則m(x)g(x)=m(x)g(x)=mk－1xk－1g(x)＋mk－2xk－2g(x)＋…＋m1xg(x)＋m0g(x)∈A[x]A[x]kmi(i=0,1,…,k－1)的取值是任意的，所以上面的線性組合可A[x]中的所有元素。所以xk－1g(xxk－2g(x…xg(xg(x)確 根據(jù)A[x]和A間的一一對(duì)應(yīng)關(guān)系這一組所對(duì)應(yīng)kA的一組gr00G

gr1gr0

gr1

00 0 0

000g000g

gr1

g0我們A[x]的生成A的生成多并稱A是由它的生成多項(xiàng)式生成的循數(shù)最低的一個(gè)碼多項(xiàng)式g(x)=x4＋x3＋x2＋0G0

0 0 不難驗(yàn)證，由G所生成的碼就是上述(g(x)){m(x)g(x)m(x)n3）循反過來說g(x)F2[x]中的一個(gè)多項(xiàng)式g(x)|xn＋1代數(shù)理論可g(x)F[x]

中所生成的 xAan－1其中ai∈F2 I=0,1,…,n－1那么A是一個(gè)碼長(zhǎng)n，信息位數(shù)等ng(x那么g(x)就是這個(gè)理想中次數(shù)最低的一個(gè)多這一點(diǎn)可用反證法來證明。假定有g(shù)′(x)＋g(x)=g″(x)≠并 g"(x)g'(x)由于g″(x)(g(x))g″(x)是其中次數(shù)更低的多項(xiàng)式g(x)次數(shù)最低的假設(shè)g(x)n

，那么(g(x))xk－1g(xxk－2g(x),…,xg(x),g(x)k個(gè)xi(i=0,1,…,k－1)的線性組合，于是對(duì)于任一f(x)∈(g(x))，有f(x)=m(x)g(x)=mk－1xk－1g(x)＋mk－22g(x)＋…＋m1xg(x)＋m0這就是說，任意一個(gè)f(x)∈(g(x))，必可表示為(g(x))的一組基底的線性組合，并且(g(x))的維數(shù)是k.下面再證A必是一個(gè)循環(huán)碼。(an－1xn－1＋an－2xn－2＋…＋a1那么就x(an－1xn－1＋an－2xn－2＋…＋a1=(an－2xn－1＋…＋a1x2＋a0即(an－2xn－1＋…＋a1x2＋a0x＋an－1)也可表達(dá)成(g(x))的一組基底的線性組合因此也是一個(gè)碼多項(xiàng)式，并且(an－2…a1a0an－1)∈A.故A是個(gè)循環(huán)碼。 為了從認(rèn)識(shí)g(x)|xn＋1這個(gè)條件的重要性，下面舉一個(gè)反例，說明g(x?令g(x)=x4＋x＋1. G

00G所生成的線性碼不是循環(huán)碼。以上我們著重討論了循環(huán)碼的生成矩陣A(n,k)循環(huán)碼，g(x)是它的生成多項(xiàng)式，根據(jù)以上證明，(an－1an－2…a1∈A的充分必要條件 g(x)|(an－1an－2xn－2＋…＋a1x＋a0)因?yàn)間(x|xn＋1，故可令：h(xg(x1. (h(x)g(x))xn＋1=設(shè)a(x)=(an－1xn—1＋an－2xn—2＋…＋a1x＋a0A[x而g(x)|a(x，故可令a(x)=顯然 反之， 可 其中axk若g(x) 則h(x)h(x)A的監(jiān)督多項(xiàng)式h(x)=hkxk＋hk－1xk—1＋…＋h1x＋h0,(h0hk000H

00 0 0

h k k因 grhk=grhk－1＋…＋g1hn－2＋g0hn－1=…grhi－r＋gr－1hi－r＋1＋…＋g1hi－1＋g0hi=…g1h0＋g0h1=g0h0=或簡(jiǎn)寫grhi－r＋gr－1hi－r＋1＋…＋g1hi－1＋g0hi=0 (i=1,2,…, 注意到h(x)也是(xn＋1)的一個(gè)因子，所以也可以把它看作某個(gè)循環(huán)碼A′的生成多項(xiàng) h0h00000 0hhhh0

kk

k

共有n－k行G′與H相比較，可A′與A的對(duì)偶碼A*是等價(jià)的因?yàn)閷′中所字都按照由右至左的次序倒寫出A*中的碼更進(jìn)一步，若令h(x)~h(x)~

hxh0

hk1x11k~A*.A*A′是等價(jià)的，所以有時(shí)我們也AA′互為對(duì)偶碼。5-17(73)循環(huán)碼的生成多項(xiàng)g(x)=x4＋x3＋x2＋1，那么h(x)=＋1，所以，它的監(jiān)督矩 0H 0 00

00 n－k411以h(x)為生成多項(xiàng)式的循環(huán)碼A陣 0G' 0 00

0 0 1 1′倒置之后恰A*(a0a1an－2－1)而以~(x)為生成多項(xiàng)式的循環(huán)碼A*的生成00G*00

0 0 1 1a，接b，錯(cuò)誤圖e的b(x)=bn－1xn－1＋bn－2xn－2＋…＋b1e(x)=en－1xn－1＋en－2xn－2＋…＋e1并且 b(x)=整除a(x),g(x)|a(x)，因而b(x)e(x)關(guān)于模g(x)同余，即b(x)≡e(x), (modg(x)) 現(xiàn)在我們來證明：接收多項(xiàng)式b(x)的伴隨式多項(xiàng)式就是用g(x)去除e(x)所得的余式證a(xb(xe(x)分別為發(fā)送向a，收b和錯(cuò)e的多項(xiàng)式。則b(x)=因 (h(x)·a(x))xn＋1=所以(h(x)·b(x))xn＋1=(h(x)·a(x))則有(h(x)·b(xxn＋1h(x)·e(x=(h(x)·Q(x)·g(x))xn＋1=其中h(xk,

nk1這個(gè)等式的展開式r后項(xiàng)的系數(shù)矩陣為HbT=HeT= 其

hk

00 HH1,H20

k 0 h

0 00

k k

n－k行n－k列 hk

k

k kH2經(jīng)有限步的行初等變換后可化為單位方陣。設(shè)此初等變換對(duì)應(yīng)矩陣為L(zhǎng)，用它去LHbT=LHeT=LH2(e′)T=LHH行等價(jià)LH仍然A監(jiān)督矩陣。于b(x)的伴隨式為eT= 2…即S=(r－1 －2… （證畢g(x)那么g(x)nk=r. g(x)=grxr＋gr－1xr－1＋…＋g1xgr

gr

g0

0G gr

r

0

0 g r 0那么GA的一個(gè)生成gr0G可化為典型G0IkQ其中Qk×r階矩陣，Ikk階單位陣。此時(shí)碼字的k位為信息位r位為監(jiān)督位。問題是如何由給出的信息位an－1,an－2,…an－k的值，唯ar－1ar－2,…,a0,使(an－1an－2…a1a0∈A根據(jù)帶余除法，可寫成：c(xq(x)·g＋s(x),s(x)0g(x)而且s(x)c(x)g(x)唯一確定。從而有g(shù)(x)|[c(x)＋s(x)]因 則多項(xiàng)式[c(x)＋r(x)]的系數(shù)序(an－1an－2…a1可見，監(jiān)督ar－1,ar－2,…,a0可以由帶實(shí)5-13g(x)grxr＋gr－1x＋g1x＋g0做除式的除法ggr=g…圖中共中r個(gè)移位寄存器，用方框表示而r 每個(gè)寄存器可以取0或1種狀態(tài)；⊕是模2加法器；○是乘法器；乘法器的設(shè)置取決于生成多項(xiàng)式各項(xiàng)系數(shù)的n個(gè)碼元：an－1an－2an－3,…a1a0a0電路r個(gè)寄存器的內(nèi)容就是用g(x)去除a(x)所得的余式s(x)的系數(shù)，從左至右依次是sr－1,sr－2,…,s1,s0.另一從第(r＋1)個(gè)脈沖開始直到第n這個(gè)除法電路左端的輸出,－2,…10次項(xiàng)的系數(shù)特別，當(dāng)給定以g(x)為生成多項(xiàng)式的循環(huán)碼Akan－1,an－2,…,an－k之后，輸入端輸入n個(gè)元素：an－1an－2,…an－k000…0ar－1,ar－2,…,a1,那么(an－1an－2…a1a0)就是A的一個(gè)碼字例5-18以g(x)=x3＋x＋1為生成多n7A，因?yàn)樵贔2[x]中(x3＋x＋1)|(x7＋1)A確實(shí)存它是個(gè)74)循環(huán)碼。A的編碼可用下面的圖圖5- (7,4)循環(huán)碼g(x)= 當(dāng)給定信息a6a5a4a33個(gè)次a6a5a4a300,0后，寄存器中的內(nèi)容自左至右依次a2a1,a0，而(a6a5a4a3a2a1a0)就是A的一個(gè)碼字。上述除法電路雖能用作編，但前r拍只是將信息位輸入移位寄k個(gè)信息r位間此可采取預(yù)先乘xr的k位信息位輸入時(shí)，圖中開K1斷，K2,K3通，這樣在直接輸出信息碼元的同時(shí)完成了除法運(yùn)算。然后，K1通，K2,K3斷，將移位寄存r個(gè)監(jiān)督碼元緊接在信息找碼長(zhǎng)為n的所有循環(huán)碼的問題就變?yōu)榍笏纳啥囗?xiàng)式g(x)的問題。g(x)|(xn＋1)xn＋1的所有因式即可就需要把xn＋1F2上分解成不可約多項(xiàng)式的上可以查xn＋1的因式分解表多項(xiàng)式a(X)都應(yīng)被生成多項(xiàng)式g(x)以在接收端可以將接收向量b送入一個(gè)以g(x)為除式的除法電路（和發(fā)送編中的無錯(cuò)，余式不為零接接收向b除法電緩存

&余式0,輸出余式≠0時(shí),輸

輸重發(fā)指圖圖5- 循環(huán)碼檢錯(cuò)框在接收端為了糾錯(cuò)而采用的譯碼方法自正的的錯(cuò)誤圖樣必須與特定的余式有一一對(duì)應(yīng)關(guān)系。原則上糾錯(cuò)可按下述步驟進(jìn)求出余式s(x)用生成多項(xiàng)式g(x)除b(x)得到：s(x)=(b(x))g(x)求錯(cuò)誤圖樣e(x)s(x)用查表的方法或通過某種運(yùn)算便可得到錯(cuò)誤圖樣e(x).求發(fā)送多項(xiàng)式a(x)a′(x)=是送碼多項(xiàng)式a(x).上述第（（3）步都比較簡(jiǎn)單。只是e(x)時(shí)，要把整個(gè)接收碼組暫時(shí)下組時(shí)間中進(jìn)行糾錯(cuò)。所以，實(shí)際的譯需要兩套除法電路配合一個(gè)緩沖寄存(5-17)74g(x)其中的除法電路與圖5-14相同了進(jìn)增加了一個(gè)7級(jí)緩存器和組合邏它們得到錯(cuò)誤圖樣e(x)，它一方面與緩存器送到D0的輸入端，用來消除該錯(cuò)誤對(duì)余式a(x)輸與非7圖圖5- (7,4)循環(huán)碼糾錯(cuò)圖5-18是一個(gè)（7，4）循環(huán)碼譯碼器。由兩套除法電路交替工作，K1K2K3K4是這兩套電路的切換開關(guān)。輸入輸入7輸出)上述譯碼方圖5-18(7,4

，此外還捕錯(cuò)譯碼和大數(shù)邏輯譯碼等方法捕錯(cuò)譯碼是梅吉特譯碼的一種變形，也環(huán)碼下面以定理的形式給出一些關(guān)于循環(huán)碼定理5-4由任何多于一項(xiàng)的生成多項(xiàng)式證：碼組中第i位上的單個(gè)錯(cuò)碼對(duì)應(yīng)于錯(cuò)碼多項(xiàng)式xi.要能檢測(cè)單個(gè)錯(cuò)碼，只需g(x)多項(xiàng)式能整除xi （證畢最簡(jiǎn)單的生成多項(xiàng)g(x1＋x定理5-5若生成多項(xiàng)g(x)具有偶數(shù)項(xiàng)，則由它產(chǎn)生的編碼就能檢測(cè)所有奇數(shù)個(gè)錯(cuò)證：當(dāng)錯(cuò)碼有奇數(shù)個(gè)時(shí)，錯(cuò)碼多項(xiàng)式e(x)整除e(x)，故能檢測(cè)所有奇數(shù)個(gè)錯(cuò)誤。令f(x)=(1x)·Q(x)=xaxbxc…將x=1代入上式得：f(1)=(1＋1)·Q(1)=1＋1＋1＋…=有偶數(shù)項(xiàng) （證畢因xm＋1=(x＋1)(xm－1＋xm－2＋…＋1)，何具(xm＋1)形式的多項(xiàng)式都含有(x＋1).從而可推g(x)含有(xm＋1)個(gè)錯(cuò)誤。(m=1,2,…)定義m是使g(x)xm＋1的最小整數(shù)，則稱m為多項(xiàng)g(x)定理5-6若碼長(zhǎng)n不大于生成多項(xiàng)式g(x)mn≤m，則g(x)產(chǎn)生的碼能夠檢測(cè)所有的單個(gè)和兩個(gè)錯(cuò)碼證：由于g(x)能整除(xm＋1)，它至少有兩項(xiàng)，故按定5-4，必能檢測(cè)出所有單個(gè)錯(cuò)若要檢測(cè)所有兩個(gè)錯(cuò)碼，則要求g(x)不能整除xi＋xj其中ij＜n；假設(shè)i＜j，則有：xi＋xj=xi(1＋xj－i)因已假定g(x)不能被x整除（即生成多項(xiàng)式常數(shù)項(xiàng)不應(yīng)為且多于一項(xiàng)的g(x)必定不能整除xi.故要求g(x)不能整除(1＋xj－i)就j－i＜n≤mm所以，g(x)必定不能整除(1＋xj－i).因此能檢測(cè)兩個(gè)錯(cuò)碼 （證畢定理5-7n不大于g1(x)的指數(shù)，則由生成多項(xiàng)g(x)=(x＋1)·g1(x)產(chǎn)生的證5-5可知g(x)中有因子1)，故能檢測(cè)單個(gè)和三個(gè)錯(cuò)誤。又由定5-6可知，錯(cuò)碼多項(xiàng)式(xi＋xj)不能被g1(x)除，故也不能被g(x)整除，所以能檢測(cè)個(gè)錯(cuò)誤（證畢個(gè)至最末一個(gè)之間的碼元數(shù)目b.例如圖樣00010110000,b4定理5-8r次多項(xiàng)式產(chǎn)生的任一循環(huán)碼，能檢測(cè)所有長(zhǎng)度不超過r的突誤證b的突發(fā)錯(cuò)誤可表示為=

xb－2＋…＋1)=xi式中e′(x)為不高于(b－1)次的多項(xiàng)式。g(x) e(x)r1可檢測(cè)出來g(x)不能有x作為因子，且多于一項(xiàng)的g(x)不能整xi，故只有它能整除e′(x)e(x).但 g(x)).度不超過r的突發(fā)錯(cuò)誤。 定理5-9長(zhǎng)度為b＞r的突發(fā)錯(cuò)誤中，若b=r＋1，則不能檢測(cè)部分占1/2(r－1)；若b=r＋1，則不能檢測(cè)部分1/2r證：設(shè)錯(cuò)誤圖樣為e(x)=xie′(x)，其中).－1項(xiàng)，故還應(yīng)有(b－2)個(gè)系01的項(xiàng)xj，0＜j＜b－1，所以共可2b－2種不同的多e′(x).僅當(dāng)e′(x)有因子g(x)時(shí)，此錯(cuò)誤才不能被檢測(cè)，這時(shí)e′(xg(x)·Q(xg(x)rQ(x)b－1－r次。r=b－1Q(x)=1.這時(shí)僅有一個(gè)錯(cuò)誤圖樣測(cè)的突發(fā)錯(cuò)誤總數(shù)1/2b－21/2r－1.b－1＞r,Q(x)應(yīng)含有x0xb－1－rb－2－r個(gè)系數(shù)01Q(x)有圖樣所占的比例為2b－2－(n－k)/2b－2=1/2r。定理5-10若由g(x)=(x＋1)·g1(x)產(chǎn)生此碼能檢測(cè)任何兩個(gè)長(zhǎng)度不大于2證：兩個(gè)長(zhǎng)度不大于2的突發(fā)錯(cuò)誤的組合（1）e(x)=xi＋xj（2）e(x)=(xi＋xi＋1)＋xj（3）e(x)=xi＋(xj＋xj＋1)和(3)由于g(x)中有因子(x＋1)根據(jù)定理5-5而(4)可改寫為：e(x)=(x＋1)(xi＋xj),被和(4)，為能檢測(cè)出錯(cuò)誤來,(xi＋xj)應(yīng)不能被g1(x)5-6中已得到證明，所以(1)和(4)這兩種錯(cuò)誤能被檢測(cè)。（證畢定理5-11g(xxq＋1)·g1(x)產(chǎn)生的循環(huán)碼能檢測(cè)如下兩個(gè)突發(fā)錯(cuò)誤的任何組e(x)=如果下列條件滿足q＋1錯(cuò)誤e1(x的突發(fā)長(zhǎng)度qg1(x)的指數(shù)m的最但由dmin與糾檢能力的關(guān)系定理易知當(dāng)碼的檢錯(cuò)能力t時(shí)，其檢錯(cuò)能力為[t/2].注:[]表示取整數(shù)部分。際的下面的5-10列出了一些有代表性的循截短循環(huán)碼這就把原(nk)碼中信息位刪去i位后構(gòu)成一(n－ik－i)碼，0＜i＜k.這個(gè)碼的最小碼距仍不會(huì)減小，故很信息kmax是指最大可能的5-10部分循環(huán)碼的參量和性定理不1所有奇數(shù)錯(cuò)5-兩個(gè)錯(cuò)碼：一個(gè)長(zhǎng)度≤45-4突發(fā)；88%5的突發(fā)5-94%更長(zhǎng)的突5-兩個(gè)錯(cuò)碼；一個(gè)長(zhǎng)度≤95-9突發(fā);99.6%長(zhǎng)為10的突5-發(fā);99.8%更長(zhǎng)的突5-5兩個(gè)長(zhǎng)度≤2的突發(fā)；任何的突發(fā)；93.8%6的突5-5-5-的突發(fā)；99.99996%的長(zhǎng)23的突發(fā);99.99998%更長(zhǎng)突5-5-5-.BCH碼BCH碼是一種特別重要的Bose-Chaudhuri-Hocguenghem命名的。BCH碼的重要性在于它解決了生成多項(xiàng)式mt2m－1BCHt個(gè)隨機(jī)錯(cuò)誤（或檢測(cè)2t個(gè)隨數(shù)，不大于mt.因此，這種碼的信息位數(shù)k5-11中給出BCH碼的參量爾(Fire)碼一些特定的循環(huán)碼常常以研究該碼的人命名。例如，定理5-中的碼常稱為費(fèi)爾碼5-11部分BCH碼的參mnktd37411337g1(x)=g3(x)=3g1(x)=457g3(x)=g2(x)(x2＋x＋1)g7(x)=g1(x)=g2(x)=5g3(x)=g2(x)g5(x)=g3(x)g7(x)=g15(x)=g7(x)3g1(x)=g3(x)=2(x)(x6＋x5＋x2＋x＋1)g4(x)=g3(x)(x6＋x3＋1)g5(x)=g4(x)g6(x)=g5(x)(x6＋x5＋x3＋x2＋1)g7(x)=g6(x)(x6＋x4＋x2＋x＋1)g11(x)=g10(x)(x2＋x＋1)g15(x)=g13(x)(x3＋x＋1)g31(x)=g15(x)57495667(Golay)碼戈萊碼是一種糾正g(x g(x)=.循環(huán)(CRC)循環(huán)碼具有很強(qiáng)情況外，還可檢測(cè)出與許用碼組距離小于CRC碼及其生成多項(xiàng)式如下：5-12用CRCCRCx11＋x10＋x8＋x7＋x5＋x4＋x2一.卷積碼的編、譯碼過程卷積碼是由伊利亞斯(P.Elias)提出來的。在分組碼中每個(gè)碼字中n個(gè)碼元僅與本k個(gè)信息位有關(guān)。而卷積碼中，編碼后產(chǎn)生n決于這段時(shí)間k個(gè)信息位，而且還取決于N－1N段時(shí)間內(nèi)的信息。N段時(shí)間內(nèi)的碼元數(shù)nN稱為這種碼的約束長(zhǎng)度。編碼圖5-19是一個(gè)卷積碼的編輸出；另一方面，還可以暫存于6級(jí)移存器中。每當(dāng)進(jìn)入編一個(gè)信息位，就立即息位之后發(fā)如下圖5-20器輸出端轉(zhuǎn)換開頭的功用即輪流將信息位bi和監(jiān)督ci5-20編的監(jiān)督位是由信息位6,3,2,1的21n2N6,nN12.常把卷積碼記作(n,k,N).編碼效率為R=k/n.bic1234565-19卷積碼圖圖5-20 譯碼一般說來，卷積碼有兩類譯碼法門限譯碼是一種二進(jìn)制的擇多邏輯譯碼碼破壞了的方程數(shù)目在方程組中是否占多數(shù)小于方程組中方程個(gè)數(shù)此方對(duì)錯(cuò)碼進(jìn)行5-21中給出了對(duì)應(yīng)于圖在譯中有一個(gè)和圖5-19相同的編碼的相應(yīng)監(jiān)督碼元在模2當(dāng)接收碼元無錯(cuò)時(shí)，譯中重新計(jì)算“由圖5-21當(dāng)信息位出現(xiàn)一個(gè)碼時(shí)，僅當(dāng)它位于信息移存器中6321才使1.時(shí)

門限電5-21卷積碼門限5-21所示電路連接，假b1以前中各級(jí)所寄存的校正子值S可以用下列邏輯 式 0E(b)

E(c)

當(dāng)c為錯(cuò)碼上式經(jīng)過簡(jiǎn)單線性變換，可以改寫成S1E(b1)E(c14E(b1)E(b4)5 (1)E(b2)

S2

E

這是一組正交于E(b1)的正交校驗(yàn)方每個(gè)方均包含一項(xiàng)E(b1)，而所有其他E(bi)和E(ci)整個(gè)方程組中至多出現(xiàn)一次因此在所的12個(gè)碼元中錯(cuò)誤不多于2個(gè)的條E(b1)=1b1錯(cuò)1所以在圖5-21中按式(5-62)4個(gè)結(jié)果≥3，即當(dāng)3個(gè)以上輸入等于“1”時(shí)，“器輸出端的一級(jí)移存器糾正輸出碼元b1的錯(cuò)b1影響的各級(jí)校正子此譯除了能糾正兩位在約束長(zhǎng)束長(zhǎng)度和在約束長(zhǎng)度中能糾正錯(cuò)誤的從上述例子可以看數(shù)學(xué)理論尚不象循碼。由§5-3可知，一個(gè)線性碼完全由一監(jiān)督H或生成矩陣G所確定。下面我們例定圖5-19在第一個(gè)信息位b1進(jìn)入編之前，各級(jí)移存器處于0狀態(tài)，c1b1c2b2c3b3c4b1c5b1c6

6 6

c7

b3b4b7 上式可以改b1c1b2c2b3c3b1b4b1b2b1

0

b2

用矩陣表示為

b

1 c112 2

b

c

2

1

b7

c7c

HAT0T11001010110000 在卷督矩陣H是一個(gè)現(xiàn)H中每?jī)闪卸寂c其前（或后兩列結(jié)0。由于這樣半無窮矩陣不便于研究，而且我們只要研究其前6行已能說明n的結(jié)構(gòu)形式如5-22所示H1的最左邊n列(n－k)·N行的一個(gè)子矩陣，向右的每nnn b1c11c12b2c21c22b3c31c32b4…dj1cj2cc

b

bj1 j j2由此可見k1n3N3，約束長(zhǎng)度nN=9.監(jiān)督方程為11bc 12bc c

或?qū)懗删仃囆问綖?001000110001010010 1100

0

1

陣為

1001010010011000101001001100000101 1

I

P

I

2

式中I22階單位陣，Pi——2×1階矩陣，O——2階全0方陣。仔細(xì)觀察可發(fā)現(xiàn)它與典型H0=[P,Ir]有 I

O

P

O

I N r式中Irr階單位陣，rn－kPir×kOr階全0方陣h=[PNOPN－1OPN－2O…P1Ir]給定了h，則H1或者h(yuǎn)不難H1.最后，我們來找卷積碼的生成矩陣G，在 b4=[b1b1b1b2(b1＋b2)b2b3(b2b3)(b1＋b3)b4…]12b12

(5-行比上一行向右退n列(現(xiàn)在n＝3).類似式(5-71)，也有截短

I1

Q3 010

Q

2I1 Q1式中I11Qi1×2階矩陣，iQi=P ，(i= i一般說來，截短生成矩陣具有如下形I

Q

QN G

N1

I

Q1

式中Ikk階單位方陣Qik(n－k)階矩陣Ok階全0方陣g.g=[IkQ1OQ2…OQN同樣，如果基本生成矩g已給出，就完全有可能從已知的信息位得到整個(gè)編碼序一.噪聲是指信息系統(tǒng)中導(dǎo)致有用信號(hào)失噪聲信道的轉(zhuǎn)移概率p(yj/xi)表示當(dāng)發(fā)送xiyj的概率的平錯(cuò)誤概率為 pe

p(xi)p(y

/xij

i二.信道編碼是對(duì)抗信道中加性干擾的的關(guān)系來自動(dòng)檢測(cè)或糾正傳輸中所發(fā)生的錯(cuò)三.分組碼是指新增加的監(jiān)督元僅與本傳輸時(shí)具有一定的能力把每個(gè)k長(zhǎng)的信息組n位長(zhǎng)的碼字(n＞k).這2kn位長(zhǎng)碼字的全體稱為碼長(zhǎng)為n，信息位為k的分組(nk)監(jiān)督元個(gè)數(shù)rn－k.衡量分組碼性能的基本參數(shù)編碼效率：Rk

i0,ai

二元碼時(shí)wa

i碼距d(ab)

1io,ai

二元碼時(shí)d(a,b) i

.A是碼長(zhǎng)n的分組的最小碼距為dmintt1t2使下列命題dmin≥t＋1時(shí)，A是檢t碼，可以檢測(cè)所有≤t重的錯(cuò)誤；dmin≥2t＋1時(shí)，A是糾t碼，可以糾正所有≤t重的錯(cuò)誤；(t1＋t2)碼，可以糾正所有≤t1重錯(cuò)并同測(cè)≤(t1＋t2)重錯(cuò) nnw 1Cinnwi

p)

Ciit1

p)五.若給定BSC（二元對(duì)稱信道）的平均錯(cuò)碼率p，則誤碼字率為；其中t為該編碼的糾檢能力，n為碼長(zhǎng)。六.若要糾正碼字中所有t重的錯(cuò)誤，則監(jiān)督元的數(shù)r必須滿t2r

Cnin漢明不等式中等號(hào)成立的糾錯(cuò)碼稱為完備碼 t M2/Cn i M為漢明界。它表示準(zhǔn)用碼組的個(gè)數(shù)不M.式中[]表示取整數(shù)部分。.信道容量為C的有錯(cuò)系統(tǒng)H＜C，總存