編碼理論習習題

1、第1章 概述1.1：通信的主要目的是什么？通信: 采用某種方法，借助某種媒介將信息從甲地傳送到乙地的過程通信的目的：要把對方不知道的消息及時可靠地(有時秘密的)傳送給對方1.2：信道編碼的主要目的是什么信源編碼的主要作用是：在保證通信質(zhì)量的前提下，盡可能的通過對信源的壓縮，提高通信時的有效性。就是讓通信變得更加的有效率。以更少的符號來表示原始信息，所以減少了信源的剩余度。信道編碼的主要作用是：通過對做完信源編碼后的信息加入冗余信息，使得接收方在收到信號后，可通過信道編碼中的冗余信息，做前向糾錯。保證通信的可靠性。1.3：仙農(nóng)編碼定理的主要內(nèi)容是什么？仙農(nóng)編碼定理：如果系統(tǒng)的傳輸率小于信道容量，

2、那么適當選擇編碼技術(shù)就能實現(xiàn)可靠通信，即可以將差錯率減小到任意小的程度。更確切地，每個信道都具有固定的信道容量C，對任何小于C的信息傳輸率R，存在一個碼長為n碼率為R的分組碼，若用最大似然譯碼，則其譯碼錯誤概率為 。對于碼率為R約束長度為ne的卷積碼，其譯碼錯誤概率也有類似的關(guān)系，即 其中A和B都為大于0的數(shù)，Eb(R)和Ee(R)為正實函數(shù)，叫做誤差指數(shù)。1.4：請畫出數(shù)字通信系統(tǒng)模型的通用框圖。1.5：信源編碼擴張了數(shù)據(jù)么，為什么？信源編碼沒有擴張數(shù)據(jù)。信源編碼減少了數(shù)據(jù)的冗余。信源編碼器：將信源輸出變成二元數(shù)字(bit)序列，稱為信息序列，在信源連續(xù)的情況下，還需要進行模/數(shù)(A/D)轉(zhuǎn)

3、換。理想信源編碼器模型要滿足(1)為表示信源輸出所要求的單位時間的比特數(shù)要盡量小；(2)信源的輸出S可從信息序列U中確切的重新構(gòu)造1.6：信道編碼擴張了數(shù)據(jù)么，為什么？信道編碼擴張了數(shù)據(jù)。信道編碼器：將信息序列U變換成離散的有結(jié)構(gòu)的編碼序列X，這稱為碼字。即為了使傳輸有效，人為的增加一些冗余度，使其具有自動檢錯和糾錯的能力。碼字的結(jié)構(gòu)主要用以對付傳輸或存儲碼字的有擾信道，碼字的設計和實現(xiàn)是本課程的主題。1.7：為什么要用信源編碼器理想的信源編碼器應該滿足什么要求為了減少數(shù)據(jù)的冗余。信源編碼器：將信源輸出變成二元數(shù)字(bit)序列，稱為信息序列，在信源連續(xù)的情況下，還需要進行模/數(shù)(A/D)轉(zhuǎn)換

4、。理想信源編碼器模型要滿足(1)為表示信源輸出所要求的單位時間的比特數(shù)要盡量??；(2)信源的輸出S可從信息序列U中確切的重新構(gòu)造1.8：為什么要用信道編碼器？為了使傳輸有效信道編碼器：將信息序列U變換成離散的有結(jié)構(gòu)的編碼序列X，這稱為碼字。即為了使傳輸有效，人為的增加一些冗余度，使其具有自動檢錯和糾錯的能力。碼字的結(jié)構(gòu)主要用以對付傳輸或存儲碼字的有擾信道，碼字的設計和實現(xiàn)是本課程的主題。1.9：為什么要用調(diào)制器？離散符號不適合于在實際信道上傳輸或記錄在數(shù)字存儲媒質(zhì)上。調(diào)制器將信道編碼器的每個輸出的離散符號，通過調(diào)制變成適合傳輸(或存儲)的持續(xù)時間為T的波形，此波型進入信道(或存儲媒質(zhì))，并受噪

5、聲干擾1.10：有哪些典型的傳輸信道、存儲媒質(zhì)和信道干擾？典型的傳輸信道：有線信道、無線信道、電話線路、高頻無線線路、遙測線路、微波線路、衛(wèi)星線路、光纖信道、磁記錄信道、大氣光信道、水聲信道等典型的存儲煤質(zhì)：磁芯和半導體存儲器、磁帶、磁鼓、磁盤、光存儲器、光盤等典型的干擾：開關(guān)脈沖噪聲、熱噪聲、串音、閃電、磁涂層缺損、光盤劃痕等1.11：為什么要用解調(diào)器？解調(diào)器(或讀出單元) ：處理接收到的每個持續(xù)時間為T的波形，并產(chǎn)生一個可能是離散的（量化的）或連續(xù)的（未量化的）輸出。對應于編碼序列X的解調(diào)器的輸出序列Y稱為接收序列1.12：信道譯碼器的功能是什么？信道譯碼器：將接收序列Y變換成二元序列V，

6、稱為估值序列。在理想的情況下，V與信息序列U完全一致，但是噪聲會造成譯碼錯誤。譯碼方法根據(jù)信道編碼規(guī)則和信道（或存儲煤質(zhì)）的噪聲特性而定。但設計和實現(xiàn)譯碼錯誤概率最小的信道譯碼器也是本課程的主要論題之一1.13：為什么要用信源譯碼器？信源譯碼器：把估值序列V變成信源輸出的估值(原來消息的估值)，并將此估值傳送給用戶。如果信源是連續(xù)的，需要進行數(shù)/模轉(zhuǎn)換。在一個精心設計的系統(tǒng)中，除非信道(或存儲煤質(zhì))的干擾太強，否則這個估值將是信源輸出的準確重現(xiàn)1.14：請畫出數(shù)字通信系統(tǒng)模型的簡化框圖。1.15：簡述信道編碼的主要應用領(lǐng)域。通信系統(tǒng)：如衛(wèi)星、有線和無線的電話通信、軍事通信等，利用糾錯碼來實現(xiàn)可

7、靠通信和敵人的惡意干擾計算機系統(tǒng)：如計算機存儲器、數(shù)字磁帶、磁盤、光盤、數(shù)字邏輯電路中商業(yè)領(lǐng)域：如條形碼，由黑白相間的不同寬度的條紋來代表不同的信息，包含了一定的糾錯信息，可以糾正由于條碼的模糊不清等原因造成的讀寫錯誤，因此條形碼在運輸、倉儲、超級市場管理等物流行業(yè)獲得了廣泛的應用1.16：簡述分組碼和卷積碼的相同點和不同點。分組碼編碼器：將信息序列分為長度為K比特的消息段U=u1,u2, ,uK,稱為消息,分組進行編碼,總共有2K個消息,將每個消息U獨立的變換成長度為N比特的碼字的序列V=v1,v2, ,vN(N, K)分組碼：所有個2K碼字的集合碼速率：比值R=K/N，可以理解為碼字含有信

8、息比特數(shù)量，為使編碼不沖突，R1糾錯機理：當R1時,碼字比消息多了n-k個比特, 稱為校驗位,可以抗干擾無記憶：每個N長的碼字V由相應的K長消息U唯一確定分組碼可用組合邏輯電路來實現(xiàn)卷積碼編碼器：也是接收長度K比特的信息序列U=u1,u2, ,uK,并產(chǎn)生一個長度為N比特的碼字的序列V=v1,v2, ,vN有記憶：每一編碼組不僅與同一時間單元上K比特消息有關(guān)，還與前m個輸入有關(guān)。因而編碼器的存儲器為m級(N, K, m)卷積碼：有K個輸入，N個輸出，存儲級為m的編碼器產(chǎn)生的序列集碼速率：比值R=K/N在K<N情況下，用來抗干擾的多余比特可添加到信息序列上。通常K,N都是較小的整數(shù)，當保持

9、K,N不變時，可通過增大存儲級來添加更多的冗余度卷積碼有記憶，必須用序列邏輯電路來實現(xiàn)1.17：硬判決和軟判決有什么不同？因為存在噪聲或干擾，信號在信道中傳輸，經(jīng)常會發(fā)生錯誤，所以接收端必須進行判決以確定發(fā)送端發(fā)送的是什么碼元：硬判決：當用二元碼時，調(diào)制器僅有二元輸入。類似的，解調(diào)器輸出采用二元量化時，譯碼器只有二元輸入，這種情況下，解調(diào)器采用硬判決軟判決：如解調(diào)器輸出未量化或者量化門限大于2，則解調(diào)器采用軟判決刪除信號：對沒有把握做出正確判決的信號，就暫時擱置起來不做判決，并用“×”表示，稱為刪除符號1.18：仙農(nóng)信息論的基本思想是什么？1948年，仙農(nóng)在一篇具有歷史意義的論文指出

10、證明了：對信息進行適當?shù)木幋a，在不犧牲信息傳輸和存儲速率的情況下，可以將有擾信道或存儲介質(zhì)引入的差錯減到任意低的程度仙農(nóng)編碼定理解決了糾錯碼的存在性問題，從此糾錯編碼的研究與應用開始了前所未有的發(fā)展，人們一直在不停的努力解決構(gòu)造性問題過程比結(jié)果更重要：為了接近信息傳輸率的上限，已經(jīng)提出了很多的糾錯編碼技術(shù)1.19：什么是正交振幅調(diào)制？QAM：Quadrature Amplitude Modulation數(shù)據(jù)信號：由相互正交的兩個載波的幅度變化表示幅度、相位聯(lián)合調(diào)制：在最小距離相同的條件下可實現(xiàn)更高的頻帶利用率QAM最高已達到1024-QAM(1024個樣點) ，樣點數(shù)目越多，傳輸效率越高舉例：

11、具有16個樣點的16-QAM信號，每個樣點表示一種矢量狀態(tài)，16-QAM有16態(tài)，每4位二進制數(shù)規(guī)定了16態(tài)中的一態(tài)，16-QAM中規(guī)定了16種載波和相位的組合，16-QAM的每個符號和周期傳送4比特調(diào)制的原理：發(fā)送數(shù)據(jù)在編碼器內(nèi)被分成兩路，各為原來兩路信號的1/2，然后分別與一對正交調(diào)制分量相乘，求和后輸出。接收端完成相反過程，正交解調(diào)出兩個相反碼流，均衡器補償由信道引起的失真，判決器識別復數(shù)信號并映射回原來的二進制信號1.20：最大后驗概率譯碼和最大似然譯碼之間的關(guān)系是什么？最大后驗概率譯碼：對于每個輸入Y，如果譯碼器能在碼字集合中選擇一個碼字，作為發(fā)送碼字的估值，并且使P(X/Y)最大，

12、則這種譯碼規(guī)則一定能使譯碼器輸出的錯誤概率最小最大似然譯碼定義：對于給定的Y，可選擇能使上式右邊最大的向量作為X的估計值如果所有碼字都是等可能的，即P(X)是常數(shù)，那么上式左邊最大，就推導出P(Y/X)最大P(Y/X)：似然函數(shù)，信道轉(zhuǎn)移概率若能在碼字集合選擇合適的碼字X，使得P(Y/X)最大，則這種譯碼規(guī)則被稱為最大似然譯碼1.21：最小距離譯碼準則和最大似然譯碼準則的關(guān)系。最大似然譯碼定義：對于給定的Y，可選擇能使上式右邊最大的向量作為X的估計值如果所有碼字都是等可能的，即P(X)是常數(shù)，那么上式左邊最大，就推導出P(Y/X)最大P(Y/X)：似然函數(shù)，信道轉(zhuǎn)移概率若能在碼字集合選擇合適的

13、碼字X，使得P(Y/X)最大，則這種譯碼規(guī)則被稱為最大似然譯碼定義：若能在碼字集合選擇合適的碼字X，使得P(Y/X)最大，則這種譯碼規(guī)則被稱為最大似然譯碼MLD：對應的譯碼器稱為最大似然譯碼器對數(shù)似然函數(shù)：由于lnx與x是單調(diào)關(guān)系，故有l(wèi)nP(Y/X)對于離散無記憶信道，所以最小距離譯碼器：在BSC中，MLD規(guī)則變成了選擇能使Y和X之間的漢明距離為最小的向量，作為碼字X的估計值1.22：列出2種典型傳輸錯誤并說明其不同點。隨機錯誤定義：接收序列中的傳輸錯誤是隨機出現(xiàn)的這樣的信道稱為隨機錯誤信道常見于無記憶信道中，因為噪聲隨機獨立的影響每個傳輸信號深空通信和衛(wèi)星通信信道都是典型的隨機錯誤信道為糾

14、正隨機錯誤而設計的碼稱為糾隨機錯誤碼突發(fā)錯誤定義：不同狀態(tài)特性下，錯誤出現(xiàn)的概率不一樣，這種錯誤為突發(fā)錯誤信道狀態(tài)特性變化較大，進而有突發(fā)錯誤信道的概念。常出現(xiàn)在有記憶信道中，此時噪聲對各次傳輸?shù)挠绊懯潜舜讼嚓P(guān)的突發(fā)錯誤的例子：無線通信(由多徑傳輸引起的信號衰落造成的錯誤)，有線和電纜傳輸(開關(guān)脈沖和串話的影響)，磁帶記錄(涂層缺損和灰塵引起的帶脫落)糾突發(fā)錯誤碼：為糾正突發(fā)錯誤而設計的碼不同點：隨機錯誤的特點是碼元間的錯誤相互獨立，及每個碼元的錯誤概率與它前后的錯誤無關(guān)。突發(fā)錯誤則不然，一個碼元的錯誤往往影響前后碼元的錯誤概率。即一個碼元產(chǎn)生錯誤則后面幾個碼元都可能發(fā)生錯誤。1.23：列出3

15、種差錯控制方式，比較傳輸效率。前向糾錯(FEC)：利用糾錯碼自動的糾正接收端檢查出的錯誤單向傳輸系統(tǒng)一般只能這樣差錯控制優(yōu)點：不需要反饋信道，譯碼實時性好，控制電路簡單，能進行一個用戶對多個用戶的同播通信缺點：譯碼設備較復雜，對信道適應性差，所選用的糾錯碼必須與信道的干擾情況相匹配，編碼效率低例子：磁帶存儲系統(tǒng)(記錄在磁帶上的信息很久以后再重讀)，深空通信系統(tǒng)(飛行體上的編碼設備很簡單，地面的譯碼設備可以很強大)，軍事通信自動要求重傳(ARQ)：當接收端檢查到錯誤時，就自動要求發(fā)送端重新傳送該消息優(yōu)點：易于實現(xiàn)，成本和復雜性低缺點：必須有反饋信道，實現(xiàn)控制較復雜，難以用于同播系統(tǒng)，通信效率低，

16、很難適合實時傳輸系統(tǒng)雙向傳輸系統(tǒng)可使用這種方法進行差錯控制混合差錯控制(HEC)：是FEC和ARQ方式的結(jié)合，具有FEC和ARQ方式的優(yōu)點發(fā)送端：發(fā)送有糾錯和檢錯能力的碼接收端：檢查錯誤情況，如果錯誤在該碼的糾錯能力范圍內(nèi)，則自動進行糾正；如果信道干擾很嚴重，錯誤超過糾錯能力，但是能檢測出來，則經(jīng)反饋信道請求發(fā)送端重發(fā)適用于環(huán)路時延大的高速傳輸系統(tǒng)中，如衛(wèi)星通信信息反饋方式(IRQ)接收端：把接收到數(shù)據(jù)，原封不動的通過反饋信道送回發(fā)送端發(fā)送端：比較發(fā)送數(shù)據(jù)和反饋數(shù)據(jù)，如發(fā)現(xiàn)錯誤，則重新發(fā)送出錯的消息，直到?jīng)]有發(fā)信錯誤為止優(yōu)點：不需要檢、糾錯、編、譯碼器，控制設備和檢錯設備較簡單缺點：需要反饋信

17、道，環(huán)路時延較大，發(fā)送端需要存儲器存儲已經(jīng)發(fā)送的碼組僅適用于傳輸效率較低，數(shù)據(jù)信道錯誤率較低，有雙向傳輸信道和控制簡單的系統(tǒng)中傳輸速率：自動要求重傳(ARQ)通信效率低，混合差錯控制(HEC)傳輸速率較高，信息反饋方式(IRQ)傳輸速率較低。1.24：對于如圖1.1所示的BSC信道，信源符號發(fā)生的概率為P(x1)=0.6,P(x2)=0.4, 求(1) 信源X中事件x1和x2分別的自信息(以比特為單位)；(2)接收符號yi(i=1,2)發(fā)生的概率；(3)求條件概率P(xi|yi)；(4)收到消息yi(i=1,2)后，獲得的關(guān)于xi(i=1,2)的信息量；(5)x和yi之間的互信息；(5)信源X

18、和信源Y的信息熵；(6)條件熵H(X|Y)和H(Y|X)（1） X1的自信息I(x1)=-log0.6= I(x2)=-log0.4=（2） P(y1)=0.6*（5/6）+0.4*（3/4）=0.8 P(y2)=0.6*（1/6）+0.4*（1/4）=0.2（3） P(x1|y1)=P(x1y1)/P(y1)=P(y1|x1)P(x1)/P(y1)=5/8P(x1|y2)=P(x1y2)/P(y2)=P(y2|x1)P(x1)/P(y2)=1/2P(x2|y1)=P(x2y1)/P(y1)=P(y1|x2)P(x2)/P(y1)=3/8P(x2|y2)=P(x2y2)/P(y2)=P(y2|

19、x2)P(x2)/P(y2)=1/2（4） 但是（5） I(x1;y1)=log(P(x1|y1)/P(x1)=log(5/8/0.6)=log(25/24)I(x1;y2)=log(P(x1|y2)/P(x1)=log(1/2/0.6)=log(5/6)I(x2;y1)=log(P(x2|y1)/P(x2)=log(3/8/0.4)=log(15/16)I(x2;y2)=log(P(x2|y2)/P(x2)=log(1/2/0.4)=log(5/4)（6） H(X)=-(P(x1)logP(x1)+P(x2)logP(x2)=-(0.6log0.6+0.4log0.4)=H(Y)=-(P(y

20、1)logP(y1)+P(y2)logP(y2)=-(0.8log0.8+0.2log0.2)=（7） H(X|Y)=-( P(x1y1)log(P(x1|y1) + P(x2y1)log(P(x2|y1) + P(x1y2)log(P(x1|y2) + P(x2y2)log(P(x2|y2) )=-( 0.5log0.5+ 0.3log0.3+0.1log0.1+0.1log0.1)1.25：信息熵和消息的平均信息量、信源的平均不確定性之間有什么關(guān)系？平均自信息量(信息熵)定義：離散隨機變量X的平均自信息定義為，其樣本空間為xi, i=1, 2,n，則事件X=xi的平均自信息量的定義為H(X

21、)表示每個信源符號的平均信息量舉例：變量X，P(X=x1)=0.99, P(X=x2)=0.01, 變量Y，P(Y=y1)=0.5, P(Y=y2)=0.5, 則信息熵為H(X)=-0.99log0.99-0.01log0.01=0.08(比特/符號)H(Y)=-0.5log0.5-0.5log0.5=1(比特/符號)信息熵的物理含義H(X)表示信源輸出后，每個消息(或符號)提供的平均信息量H(X)表示信源輸出前，信源的平均不確定性例如：上頁例子中， H(Y)>H(X)，對于信源X，兩個輸出消息不是等概率的，事先大致可以猜測消息x1會出現(xiàn)，故信源X的不確定性要小H(X)表示變量X的隨機性

22、當信源符號是等概率出現(xiàn)的時候，信息熵可以達到最大值1.26：簡述等長信源編碼定理的主要內(nèi)容。定理: 一個熵為H(X)的離散無記憶信源，若對信源長為N的符號序列進行等長編碼，設碼字是從r個字母的碼符號集合中，選取l個碼元組成。對于任意的>0，只要滿足則當N足夠大時，可實現(xiàn)幾乎無失真編碼，即譯碼錯誤概率可為任意小。1.27：簡述前綴碼和惟一可譯碼之間的關(guān)系。前綴碼/前綴條件碼定義: 若碼C中，沒有任何完整的碼字是其他碼字的前綴，稱此碼為前綴碼，也稱即時碼或非延長碼前綴碼和即時碼的定義是一致的：如果沒有一個碼字是其他碼字的前綴，則在譯碼過程中，當收到一個完整碼字的碼符號序列時，就能直接把它譯成

23、對應的信源符號，無需等待下一個信號到達后才作判斷，這就是即時碼關(guān)系：前綴碼是惟一可譯碼的一類子碼：即前綴碼一定是惟一可譯碼，但是惟一可譯碼不一定是前綴碼1.28：霍夫曼編碼唯一么？簡述霍夫曼編碼的主要步驟。不唯一霍夫曼編碼的步驟：將信源符號按照概率遞減的順序進行排序?qū)?和1符號分別分配給概率最小的兩個信源符號，并將這兩個概率最小的符號合并成一個新符號，用這兩個信源符號的概率之和作為這個新符號的概率以此類推繼續(xù)這個過程，直到只剩下2個符號為止，從而完成霍夫曼樹的構(gòu)造從樹的最后一個節(jié)點，依編碼路徑從后往前返回，讀出每個分支上對應的符號標示，即可得到對應的碼字1.29：考慮比特流0000000111

24、111，如果對之用游程編碼方案進行壓縮編碼，那么壓縮率為多少？游程編碼定義：游程指的是信源輸出的字符序列中，各種字符連續(xù)的重復出現(xiàn)的字符串的個數(shù)游程編碼：就是將這種字符序列映射成字符串的長度和字符串的位置的標志序列考慮比特序列0000000111111，可以被表示成(15,1),(18,0),(6,1)，字符最長的重復的數(shù)目為18，因此把該比特序列編碼為(01111,1), (10010,0), (00110,1)，此時壓縮率為15:39=1:1.30：簡述LZ編碼的分段方法和編碼方法。LZ編碼分段的方法為：(1)游程先取第一個符號作為第一段，然后再繼續(xù)分段(2)若有出現(xiàn)與前面符號一樣時，就再

25、添加緊跟后面的一個符號一起組成一段(3)盡可能取最少個連著的符號并保證各段都不相同(4)以此類推，直至信源符號序列結(jié)束編碼方法為：首先去掉最后一個符號，然后看剩下的字符串在字典中的排序，這個排序值轉(zhuǎn)換成二進制數(shù)作為指針K的值，最后一個信源符號作為碼字第2項d的值，即得到碼字(X, d)1.31：考慮比特序列0101011，如果用LZ編碼，那么其分段是什么，編碼后的碼字又是什么？0,1,01,011,00,11,010,10,101,1(000,0),( 000,1), (001,1), (011,1), (001,0), (010,1), (011,0), (010,0),( 1000,1),

26、( 000,1) 001- 11PP1-P1-P1.32：考慮一個如圖1.2所示的BSC信道，其信道轉(zhuǎn)移概率為P(0|1)=P(1|0)=p，求該信道的容量。如果=0.5，用信道容量的公式，可以獲得BSC的信道容量為C=1+plog2p+(1-p)log2(1-p)，熵函數(shù)為H(p)=-plog2p-(1-p)log2(1-p)，因此得到C=1-H(p)1.33：求具有如下信道傳遞矩陣的信道的容量。1.34：簡述信道編碼定理的內(nèi)容。定理：假設DMS有信源字符集X，熵為每信源符號H(X)比特，而且信源每Ts秒產(chǎn)生一個符號，那么信源的平均信息率為每秒H(X)/ Ts比特，假設信道可以每Tc秒使用一

27、次，而信道容量為每次信道使用C比特，那么每單位時間的信道容量為每秒鐘C/Tc比特。如果H(X)/ Ts C/Tc ，那么就存在編碼方案使得在有噪聲的信道上傳輸?shù)男旁聪?，能夠以任意小的錯誤概率進行恢復。1.35：什么是無記憶信道和二元對稱信道？無記憶信道：如果在給定時間間隔上，檢測器的輸出只與在該時間間隔上傳送的信號有關(guān)，而與任何前面時間的傳送的信號無關(guān)，稱此信道為無記憶信道離散無記憶信道：是一種M元輸入、Q元輸出的信道模型二元對稱信道: M=2,Q=2二元對稱信道: 是一種2元輸入、2元輸出的信道模型1.36：仙農(nóng)的信息定義是什么信息量的多少跟事件發(fā)生的不確定性之間有什么關(guān)系仙農(nóng)對于信息的定

28、義：信息是事物運動狀態(tài)或存在方式不確定性的描述一個句子中所含信息的多少，同句子中所表達的事件出現(xiàn)的概率有關(guān)：呈現(xiàn)相反的關(guān)系信息量的多少，同事件發(fā)生的不確定性有關(guān)：呈現(xiàn)相反的關(guān)系第二章2.1：某些域中元素有大小之分，另一些域中的元素無大小之分，各舉一個例子。2.2：交換律、分配律、結(jié)合律在群上成立么在環(huán)上成立么在域上成立么結(jié)合律在群上成立，交換律在交換群上成立，分配律群上不成立結(jié)合律在環(huán)上成立，交換律（乘法）在交換環(huán)上成立，加法和乘法在環(huán)上滿足分配律結(jié)合律、交換律、分配律在域上成立2.3：簡述群、環(huán)、域三者之間的關(guān)系？定義：一個集合G，在其上定義了一個二元運算*，若它滿足以下條件稱為群滿足封閉性

29、，即對G中任意兩個元素a,b,有a*bG二元運算*滿足結(jié)合律G中存在一個元素e，稱為恒元或單位元，使得G中任何元素，有a*e=e*a=a對于G中任何一個元素a，G中存在另一個元素 ，稱作a的逆元，使得定義：非空元素集合R中，定義了兩種二元運算，稱作加法和乘法，這樣的代數(shù)系統(tǒng)(R,+,·)稱為一個環(huán)，若它滿足以下條件R中全體元素在加法下構(gòu)成交換群，單位元為0，逆元記為-a乘法運算滿足封閉性滿足乘法結(jié)合率，即 (a·b)·c=a·(b·c) ，加法和乘法之間滿足分配律 a·(b+c)=a·b+a·c, (b+c)

30、83;a=b·a+c·a, 定義：非空元素集合F中，定義了兩種二元運算，稱作加法和乘法，這樣的代數(shù)系統(tǒng)(F,+,·)稱為一個域，若它滿足以下條件F中全體元素在加法下構(gòu)成交換群，恒元為0F中非零元素在乘法下為交換群，恒元為1加法和乘法之間滿足分配律 (a+b)·c=a·c+b·c環(huán)中全體元素在加法下構(gòu)成交換群，單位元為0，逆元記為-a域中全體元素在加法下構(gòu)成交換群，恒元為0域中非零元素在乘法下為交換群，恒元為12.4：存在含有256個元素的有限域么為什么不是由有限域的性質(zhì)可知：定理1：有限域的特征q是素數(shù)256不是素數(shù)2.5：構(gòu)造一個含

31、13個元素的有限域。在該域中，3的逆元和負元是什么？1/3 -32.6：全體整數(shù)的集合對普通減法是否構(gòu)成一個群為什么不不滿足結(jié)合律 3-(2-1)與(3-2)-1不等2.7：全體非負整數(shù)的集合在加法和乘法下是否構(gòu)成群為什么全體非負整數(shù)集合在實數(shù)加法運算下構(gòu)成可交換群，整數(shù)0為恒元，整數(shù)-a是整數(shù)a的逆元。全體非負整數(shù)集合對乘法不構(gòu)成群，因為不存在乘法逆元2.8：證明群的性質(zhì)定理1-4。定理1：群G的恒元是唯一的 證明：假定G中有兩個恒元e和，則有 證畢定理2：任何一個群元素的逆元是唯一的 證明：假定元素a有兩個逆元 ，則 證畢定理3：若a,bG，則 證明： 所以a*b和 互為逆元定理4：給定G

32、中任意兩個元素a和b，則方程a*x=b和y*a=b在G中有唯一解 證明：方程a*x=b的解是x=a-1*b，這是因為 a*a-1*b=e*b=b，同理，y*a=b的解是y=b*a-1。 下面證明解的唯一性。如果在方程a*x=b中， 除了x=a-1*b，還有另外一個解x1，使a*x1=b,則把該式兩邊左乘以a的逆元a-1，則有a-1*a*x1=a-1*b，由此可得e*x1=x1=a-1*b。同理，可證方程y*a=b的解的唯一性2.9：簡述循環(huán)群的定義，什么是生成元？定義：一個集合G，在其上定義了一個二元運算*，若它滿足以下條件稱為群滿足封閉性，即對G中任意兩個元素a,b,有a*bG二元運算*滿足

33、結(jié)合律G中存在一個元素e，稱為恒元或單位元，使得G中任何元素，有a*e=e*a=a對于G中任何一個元素a，G中存在另一個元素 ，稱作a的逆元，使得循環(huán)群定義：若存在aG是一個集合，使得G中的每個元素都是a的某次冪，即an(n是整數(shù))，則稱G是循環(huán)群生成元：該循環(huán)群由a生成，a是該群的生成元2.10：什么是有限域什么是擴域什么是域的特征有限域：階為有限的域，也稱為Galois(伽羅華)域從域的例子2可看出，對任何素數(shù)q都存在一個q階有限域擴域的定義：對任何正整數(shù)m，可以將素域GF(q)擴展為有qm個元素的域，稱為GF(q)的擴域，記為GF(qm)。稱GF(q)為GF(qm)的基域。此外已經(jīng)證明，

34、任何有限域的階都是素數(shù)的冪次有限域的特征：設F是域，0和e是加法和乘法的單位元，若對任意正整數(shù)n，都有ne0，則稱域F的特征是0；若有正整數(shù)n，使ne=0，則稱使ne=0成立的最小正整數(shù)n為域F的特征。域的特征或是0，或是有限的素數(shù)。2.11：證明有限域的性質(zhì)定理1-3。定理1：在特征為q的域中，若a是域中的任意元素，則均有qa=0證明：若a0，則qa=a+a+a=1·a+1·a+1·a=(1+1+1)·a =q· 1·a=0·a=0，定理成立；若a=0，定理顯然成立。證畢定理1：有限域的特征q是素數(shù)證明：設q0，假設q不是

35、素數(shù)，即q=q1q2,1<q1<q,1<q2<q,于是0=qe=(q1q2)e=(q1e)(q2e), 因此q1e=0或者q2e=0，但這與q的最小性相矛盾，所以q只能是素數(shù)。對于任意有限域，由于其只有有限個元素，所以其特征不可能為0，從而其特征一定為素數(shù)。定理2：設a是有限域GF(q)的非零元素，則aq-1=1。證明：令b1,b2,bq-1為GF(q)的q-1個非零元素，顯然q-1個非零元素ab1,ab2,abq-1非零且互不相同，因此 (ab1)·(ab2) ··(abq-1)=b1·b2··bq-1 所以

36、aq-1(b1·b2··bq-1)= b1·b2··bq-1 即有aq-1=1。定理3：設a是有限域GF(q)的非零元素，令n是a的階，則q-1能被n整除，即n|(q-1) 證明：假設q-1不能被n整除，則q-1=kn+r,其中0<r<n，于是aq-1=akn+r=aknar=(an)kar=ar, 根據(jù)aq-1=1，an=1，推出ar=1，這與n的定義里的最小性矛盾，所以q-1必能被n整除。證畢。2.12：證明有限域的特征定理1-3。2.13：簡述本原元的定義，并且會用該定義判斷當給定q時有限域GF(q)上的本原元。本原

37、元：在有限域GF(q)中，若非零元素a的階為q-1，則稱之為本原元。2.14：什么是多項式什么是首一多項式多項式定義：二元域GF(2)中表達式f(x)=f0+f1x+fnxn，其中fi=0或1。若fn0，則稱f(x)是n次多項式，記為deg(f(x)=n， fn稱為多項式的首項系數(shù)。GF(2)中共有2n個多項式首一多項式：首項系數(shù)為1的多項式2.15：掌握根據(jù)本原多項式和本原元生成GF(2)的擴域GF(2m)的方法。p(x)=1+x+x4是GF(2)上的本原多項式，假設a是本原元，則a4=a+1,由此可以構(gòu)造GF(24)2.16：什么是最高公因式什么是公倍式什么是最低公倍式最高公因式：若f(x

38、)為a(x)與b(x)的所有公因式中次數(shù)最高的，并且首項系數(shù)為1，記為gcd(a(x), b(x)f(x)為a(x)與b(x)的公倍式：當a(x)0, b(x)0，并且a(x)| f(x)，b(x)|f(x)最低公倍式：若f(x)為a(x)與b(x)的所有公倍式中次數(shù)最低的，并且首項系數(shù)為1，記為LCM(a(x), b(x)2.17：什么是本原多項式？本原多項式的定義：若m次既約多項式p(x)可以除盡xn+1的最小整數(shù)n滿足n=2m-1，則稱p(x)是本原多項式2.18： 證明GF(2)上的多項式f(x)滿足f(x)2= f(x2) 。2.19： GF(2)上的多項式的根的特點是什么。定理：若

39、f(x)為GF(2)上的一個m次既約多項式，則其擴域GF(2m)含有f(x)的m個根；進一步的，若m|d，則任何GF(2d)含有f(x)的根定理：若f(x)是系數(shù)取自GF(2)的多項式，令b是GF(2)擴域中的元素，若b是f(x)的根，則對任意的l0，b2l也是f(x)的根2.20：什么是域元素的共軛元。注：元素b2l稱為b的共軛元，以上定理說明若是b是多項式f(x)的根，則b的所有共軛元b2l也是f(x)的根2.21：什么是最小多項式？定義：令m(x)是使得m(b)=0成立的次數(shù)最低的多項式，則稱m(x)是b的最小多項式2.22：什么是矢量空間？定義：令V是元素的集合，在其上定義了一個稱作是

40、加法(+)的二元運算。令F是域。在域F中的元素和V中的元素之間還定義了一個數(shù)乘運算(·)。若集合V滿足下述條件，就稱它為域F上的矢量空間或線性空間：條件1：V是加法下的可交換群條件2：對F中的任意元素a和V中的任意元素v，a·v是V中的元素條件3：分配率。對任意u,vV和a,bF，有a·(u+v)=a·u+a·v, (a+b)·v=a·v+b·v條件4：結(jié)合率。對任意vV和a,bF，有(a·b)·v=a·(b·v)條件5：令1是F的單位元，則對任意vV ，有1· v

41、= v2.23：矢量空間有哪些性質(zhì)？性質(zhì)1：令0是域F中的零元，對任意的vV，有0·v=0性質(zhì)2：對任意cF，有c·0=0性質(zhì)3：對任意cF和vV ，有 (-c)·v=c·(-v)=-(c·v)性質(zhì)4：如果c·v=0,則c=0或者v=0 2.24：簡述n重的定義。n重：GF(2)上的n個分量的有序序列(a1,a2,an)稱作n重,共有2n個不同的n重，令Vn表示所有n重的集合2.25： 什么是線性組合什么是線性相關(guān)令v1,v2,vkV是k個矢量，a1,a2,akF是k個標量，稱ai vi為線性組合定義：域F上矢量空間V的一組矢量v1,

42、v2,vk稱作是線性相關(guān)的，當且僅當存在不全為0的標量a1,a2,ak，使得 。否則稱v1,v2,vk是線性獨立的第三章3.1：簡述線性(n,k)分組碼的定義。定義：長為n，有2k個碼字的分組碼，當且僅當其2k個碼字構(gòu)成GF(2)上所有n重矢量空間的一個k維子空間時，稱作線性(n,k)分組碼3.2：什么是生成矩陣？請具體構(gòu)造幾個線性(n,k)分組碼的生成矩陣。因為線性(n,k)分組碼C是一個k維子空間，所以在碼C中能找到k個線性獨立的碼字g0, g1, gk-1,使得C中的每個碼字v都是這k個碼字的一種線性組合，即v=u0g0+u1g1+uk-1gk-1將這k個線性獨立的碼字作為行，得到k&#

43、215;n階矩陣此矩陣稱為碼C的生成矩陣。線性(n,k)分組碼任何k個線性獨立的碼字都可以用來構(gòu)成碼C的生成矩陣舉例: (7,4)線性分組碼如果表格所表示的線性分組碼，有如下的生成矩陣若u=(1101)，則3.3：什么是線性系統(tǒng)(n,k)分組碼？線性系統(tǒng)分組碼：若(n,k)線性分組碼C的生成矩陣形如G=P Ik(或G=Ik P)，此時稱C為線性系統(tǒng)分組碼。此時，每個碼字都可以被分成兩個部分，即消息部分和冗余部分3.4：什么是一致校驗方程什么是一致校驗矩陣什么是對偶碼關(guān)于線性系統(tǒng)分組碼，對應于消息u=(u0, u1, uk-1)的碼字是v=(v0, v1, vn-1)=u·G=u

44、83;P Ik，即 vn-k+i=ui , 0ik-1, vj=u0P0j+u1P1j+uk-1Pk-1j, 0jn-k-1 上面兩個式子正好反映系統(tǒng)的組成特性，最后這n-k個方程稱為碼C的一致校驗方程定義：與(n,k)線性分組碼C的生成矩陣G相對應有一個(n-k)×n階矩陣H，它的n-k個行是碼C的對偶空間的一組基底，該矩陣H稱為碼C的一致校驗矩陣對偶碼：以H為生成矩陣得到的(n,n-k)碼稱為碼C的對偶碼，記為Cd3.5：什么是伴隨式伴隨式糾錯的原理是什么伴隨式：當接收到r后，譯碼器計算下述n-k重S=r·HT =(s0, s1, sn-k-1)，稱S為r的伴隨式根據(jù)伴

45、隨式定義， S=r·HT =(v+e)·HT=v·HT+e·HT=e·HT，展開后，有從上式容易看出，伴隨式是錯誤圖樣的組合，即伴隨式包含了一定程度的錯誤圖樣信息，因而可以用來糾錯伴隨式糾錯3.6：什么是漢明重量什么是漢明距離漢明距離的性質(zhì)是什么漢明重量：令v=(v0, v1, vn-1)是二元n重，v的漢明重量w(v)定義為v中非零分量的個數(shù)漢明距離：令u=(u0, u1, un-1)和v=(v0, v1, vn-1)是兩個二元n重，u和v之間的漢明距離d(u, v)定義為u+v的漢明重量。漢明距離的性質(zhì)：1)非負性，d(u, v)0；2)

46、d(u, v)=0，當且僅當u=v的時候；3)對稱性： d(u, v) =d(v, u) ；4)三角不等式： d(u, v)+d(v, w)d(u, w)3.7：簡述線性(n,k)分組碼的定義。3.8：什么是生成矩陣？請具體構(gòu)造幾個線性(n,k)分組碼的生成矩陣。3.9：什么是線性系統(tǒng)(n,k)分組碼？3.10：什么是一致校驗方程什么是一致校驗矩陣什么是對偶碼3.11：什么是伴隨式伴隨式糾錯的原理是什么3.12：什么是漢明重量什么是漢明距離漢明距離的性質(zhì)是什么3.13：重量分布和距離分布的定義是什么？簡述二者之間的聯(lián)系。重量分布：對于一個分組碼而言，每個碼字都有一個漢明重量，不同的碼字可能具有

47、相同的漢明重量，若記Ai為碼中漢明重量為i的碼字個數(shù)，則稱A0, A1, An是該碼的重量分布，其中n是碼長定義：在(n,k)碼中，任意兩個碼字之間都有一個漢明距離，兩組不同碼字之間可能有相同的漢明距離。若記Di(0in)為距離為i的碼字組數(shù)，那么稱D0, D1, Dn為此分組碼的距離分布，并且稱能夠使Di0的那個最小整數(shù)i為該碼的最小碼間距離。對線性分組碼而言，重量分布與距離分布是一回事。特別的，有如下定理定理：(n,k)線性碼的最小碼間距離等于非零碼字的最小漢明重量3.14：如何計算線性分組碼的檢錯糾錯能力？定理：設(n,k)線性碼C的最小碼間距離為d，則1)若dt+1，則碼C能檢測t個隨

48、機錯誤；2)若d2t+1，則碼C能糾正t個隨機錯誤；3)若dt+e+1，則碼C能糾正t(te)個隨機錯誤，同時還能檢測e個隨機錯誤。因此，若碼C的最小漢明距離d越大，則該碼的糾錯和檢錯能力就越強3.15：什么是最大距離可分碼？定理： (n,k)線性碼C的最小碼間距離d滿足dn-k+1。該定理給出了d的上界。最大距離可分碼：若(n,k)線性碼的最小碼間距離d滿足d=n-k+1 ，那么稱此種碼為最大距離可分碼，簡稱MDS碼。3.16：簡述標準陣的構(gòu)造步驟？步驟1：在第一行寫下所有合法的2k個碼字v=v1, v2k，第一個碼字為全零碼字；步驟2：選擇一個第一行沒有出現(xiàn)的矢量作為e2，標準陣第2行寫e

49、2+v；步驟3：繼續(xù)選擇一個第一行和第二行都沒有出現(xiàn)的矢量e3 ，標準陣第3行寫e3+v；步驟4：依次類推，直到GF(2n)中所有的矢量都被列出來一次。3.17：標準陣的性質(zhì)是什么？證明標準陣的性質(zhì)2。性質(zhì)1：同一行中任意兩個n重之和為一個碼字性質(zhì)2：在標準陣中，同一行沒有兩個n重是相同的，每個n重在且僅在一行中出現(xiàn)性質(zhì)2的證明：1)假設第l行有2個n重是相同的，如對ij有el+vi=el+vj，即vi=vj，這與標準陣的構(gòu)造相矛盾，故性質(zhì)2的第一行得證。2)首先由定義知每個n重至少出現(xiàn)一次，假設一個n重在第l行和第m行(l<m)都出現(xiàn)，則必存在i，使得該n重等于el+vi，且存在j，使

50、得該n重等于em+vj，即有em=el+(vi+vj)=el+vs，這意味著em在第l行，這與標準陣的構(gòu)造定義相矛盾。3.18：什么是陪集和陪集首？陪集：標準陣中共有2n-k行，它們稱為碼C的陪集陪集首：每個陪集中的第一個n重ei稱為陪集首。陪集中的任何一個元素都可以作為陪集首，需要做置換操作3.19：簡述基于標準陣的譯碼策略和最小距離譯碼策略的內(nèi)容?；跇藴赎嚨淖g碼策略：如果接收矢量r落在標準陣中的第i行第j列，那么就將r譯碼為vj，同時錯誤圖樣為ei，即r=ei+vj最小距離譯碼策略：如果出現(xiàn)了不可糾正錯誤圖樣，就出現(xiàn)了譯碼錯誤。對BSC信道，為了使譯碼錯誤概率最小，可以選擇漢明重量最小的

51、n重做為陪集首，由此導出了最小距離譯碼策略，即將接收矢量r譯碼為與r的漢明距離最小的那個碼字3.20：證明陪集的性質(zhì)定理1-4。定理：若C是GF(q)上的一個(n,k)線性碼，則1)長度為n的矢量b一定在碼C的某個陪集中；2)每個陪集都包含qk個矢量；3)兩個陪集要么是不相交的要么就是重合的(即相互部分重疊是不可能的)；4)如果a+C是碼C的一個陪集，且有ba+C，那么一定有b+C=a+C證明：1) b=b+0b+C；2) 對于所有的xC,由xa+x定義的映射Ca+C是個一一映射，所以陪集a+C中矢量的個數(shù)和碼集中碼矢的個數(shù)相等，即qk3.21：簡述伴隨式譯碼方法的步驟。步驟1：計算接收矢量r

52、的伴隨式r·HT步驟2：確定伴隨式等于r·HT對應的陪集首ei，然后假定ei是信道引起的錯誤圖樣步驟3：將接收矢量r譯碼為碼字v=r+ei3.22：請構(gòu)造一種線性分組碼，給出具體的生成矩陣，一致校驗矩陣，以及譯碼方法等。(7,4)線性分組碼如果表格所表示的線性分組碼，有如下的生成矩陣，一致校驗矩陣第四章4.1：什么是循環(huán)右移什么是循環(huán)碼循環(huán)移位: 將n重v=(v0,v1,vn-1)的分量循環(huán)右移一位，得到另一個n重v(1)=(vn-1,v0,v1,vn-2)，稱為v的循環(huán)移位。若v的分量循環(huán)右移i位，得到v(i)=(vn-i,vn-1, v0,v1,vn-i-1)循環(huán)碼的定

53、義：一個(n,k)線性碼C，若它的每個碼字的任何循環(huán)移位都仍然是一個碼字，則稱此碼為循環(huán)碼4.2：什么是碼字多項式？證明碼字多項式v(i)(x)就是xiv(0)(x)/(xn+1)的余式。碼字多項式：為研究循環(huán)碼的代數(shù)特性，將碼字v=(v0,v1,vn-1)的各個分量看成是多項式 的系數(shù)，此多項式稱為v的碼字多項式碼字v(0)=(v0,v1,vn-1)右移一位，得到v(1)=(vn-1, v0,vn-2)，類似的v(2)=(vn-2,vn-1,vn-3) v(0)(x)=vn-1xn-1+vn-2xn-2 +v1 x+v0 v(1)(x)=vn-2xn-1+vn-3xn-2+v0 x+vn-1

54、 v(2)(x)=vn-3xn-1+vn-4xn-2+vn-1 x+vn-2 v(i)(x)= vn-i-1xn-1 + vn-i-2xn-2+vn-i+1x+vn-i因而有v(1)(x)= xv(0)(x) mod (xn+1) v(2)(x)= xv(1)(x)=x2v(0)(x) mod (xn+1) xiv(0)(x)=vn-1xn+i-1+vn-2xn+i-2 +vn-i-1xn-1+v1xi+1+v0xi= vn-i+vn-i+1x+vn-1xi-1+v0xi+v1xi+1 +vn-i-1xn-1+ vn-i (xn+1)+vn-i+1x(xn+1)+vn-1xi-1(xn+1)=

55、q(x)(xn+1)+v(i)(x) 其中q(x)= vn-i +vn-i+1x+vn-1xi-14.3：證明循環(huán)碼的代數(shù)性質(zhì)定理1-3定理1：循環(huán)碼C中次數(shù)最低的非零碼字多項式是唯一的證明：令 是C中次數(shù)最低的碼字多項式，若g(x)不唯一，則存在另一個碼字多項式 ，由線性性質(zhì)可知，g(x)+g*(x)也是一個碼字多項式，但它的次數(shù)小于r，和前提矛盾，所以循環(huán)碼C中次數(shù)最低的非零碼字多項式是唯一的。證畢。定理2：若g(x)=g0+g1x+gr-1xr-1+xr是(n.k)循環(huán)碼C中次數(shù)最低的非零碼字多項式，則必有g(shù)0=1證明：若g0=0，則g(x)=x(g1+g2x+gr-1xr-2+xr-1

56、)，將g(x)循環(huán)右移n-1位之后，可以得到一個次數(shù)更低的碼字多項式，其次數(shù)為r-1，和前提矛盾，則必有g(shù)0=1。證畢。結(jié)合定理1和定理2，知在(n,k)循環(huán)碼中，次數(shù)最低的非零碼字多項式形如g(x)=1+g1x+g2x2+gr-1xr-1+xr定理3：若g(x)是(n.k)循環(huán)碼C中次數(shù)最低的非零碼字多項式，一個次數(shù)小于或等于n-1的二元多項式f(x)是碼字多項式當且僅當f(x)是g(x)的倍式證明：反證法。設f(x)是碼字多項式并且其次數(shù)小于或等于n-1，假設f(x)=a(x)g(x)+b(x), deg(b(x)<r，由線性性質(zhì)可知b(x)=f(x)+a(x)g(x)也是一個碼字多項式，而deg(b(x)<deg(g(x)，這和前提矛盾，則只能當f(x)是g(x)的倍式的時候，f(x)是碼字多項式。證畢。4.4：簡述系統(tǒng)循環(huán)碼的編碼原理和編碼步驟？編碼原理給定循環(huán)碼的生成多項式g(x)，可以使該碼成為系統(tǒng)形式。假定待編碼的消息是u=(u0, u1, uk-1)，則對應的消息多項式為u