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

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

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

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

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

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

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

8、字含有信息比特?cái)?shù)量，為使編碼不沖突，R1糾錯(cuò)機(jī)理：當(dāng)R1時(shí),碼字比消息多了n-k個(gè)比特, 稱為校驗(yàn)位,可以抗干擾無(wú)記憶：每個(gè)N長(zhǎng)的碼字V由相應(yīng)的K長(zhǎng)消息U唯一確定分組碼可用組合邏輯電路來(lái)實(shí)現(xiàn)卷積碼編碼器：也是接收長(zhǎng)度K比特的信息序列U=u1,u2, ,uK,并產(chǎn)生一個(gè)長(zhǎng)度為N比特的碼字的序列V=v1,v2, ,vN有記憶：每一編碼組不僅與同一時(shí)間單元上K比特消息有關(guān)，還與前m個(gè)輸入有關(guān)。因而編碼器的存儲(chǔ)器為m級(jí)(N, K, m)卷積碼：有K個(gè)輸入，N個(gè)輸出，存儲(chǔ)級(jí)為m的編碼器產(chǎn)生的序列集碼速率：比值R=K/N在KH(X)，對(duì)于信源X，兩個(gè)輸出消息不是等概率的，事先大致可以猜測(cè)消息x1會(huì)出現(xiàn)，故

9、信源X的不確定性要小H(X)表示變量X的隨機(jī)性當(dāng)信源符號(hào)是等概率出現(xiàn)的時(shí)候，信息熵可以達(dá)到最大值1.26：簡(jiǎn)述等長(zhǎng)信源編碼定理的主要內(nèi)容。定理: 一個(gè)熵為H(X)的離散無(wú)記憶信源，若對(duì)信源長(zhǎng)為N的符號(hào)序列進(jìn)行等長(zhǎng)編碼，設(shè)碼字是從r個(gè)字母的碼符號(hào)集合中，選取l個(gè)碼元組成。對(duì)于任意的0，只要滿足則當(dāng)N足夠大時(shí)，可實(shí)現(xiàn)幾乎無(wú)失真編碼，即譯碼錯(cuò)誤概率可為任意小。1.27：簡(jiǎn)述前綴碼和惟一可譯碼之間的關(guān)系。前綴碼/前綴條件碼定義: 若碼C中，沒(méi)有任何完整的碼字是其他碼字的前綴，稱此碼為前綴碼，也稱即時(shí)碼或非延長(zhǎng)碼前綴碼和即時(shí)碼的定義是一致的：如果沒(méi)有一個(gè)碼字是其他碼字的前綴，則在譯碼過(guò)程中，當(dāng)收到一個(gè)完

10、整碼字的碼符號(hào)序列時(shí)，就能直接把它譯成對(duì)應(yīng)的信源符號(hào)，無(wú)需等待下一個(gè)信號(hào)到達(dá)后才作判斷，這就是即時(shí)碼關(guān)系：前綴碼是惟一可譯碼的一類子碼：即前綴碼一定是惟一可譯碼，但是惟一可譯碼不一定是前綴碼1.28：霍夫曼編碼唯一么？簡(jiǎn)述霍夫曼編碼的主要步驟。不唯一霍夫曼編碼的步驟：將信源符號(hào)按照概率遞減的順序進(jìn)行排序?qū)?和1符號(hào)分別分配給概率最小的兩個(gè)信源符號(hào)，并將這兩個(gè)概率最小的符號(hào)合并成一個(gè)新符號(hào)，用這兩個(gè)信源符號(hào)的概率之和作為這個(gè)新符號(hào)的概率以此類推繼續(xù)這個(gè)過(guò)程，直到只剩下2個(gè)符號(hào)為止，從而完成霍夫曼樹(shù)的構(gòu)造從樹(shù)的最后一個(gè)節(jié)點(diǎn)，依編碼路徑從后往前返回，讀出每個(gè)分支上對(duì)應(yīng)的符號(hào)標(biāo)示，即可得到對(duì)應(yīng)的碼字1

11、.29：考慮比特流111111111111111000000000000000000111111，如果對(duì)之用游程編碼方案進(jìn)行壓縮編碼，那么壓縮率為多少？游程編碼定義：游程指的是信源輸出的字符序列中，各種字符連續(xù)的重復(fù)出現(xiàn)的字符串的個(gè)數(shù)游程編碼：就是將這種字符序列映射成字符串的長(zhǎng)度和字符串的位置的標(biāo)志序列考慮比特序列111111111111111000000000000000000111111，可以被表示成(15,1),(18,0),(6,1)，字符最長(zhǎng)的重復(fù)的數(shù)目為18，因此把該比特序列編碼為(01111,1), (10010,0), (00110,1)，此時(shí)壓縮率為15:39=1:1.30：

12、簡(jiǎn)述LZ編碼的分段方法和編碼方法。LZ編碼分段的方法為：(1)游程先取第一個(gè)符號(hào)作為第一段，然后再繼續(xù)分段(2)若有出現(xiàn)與前面符號(hào)一樣時(shí)，就再添加緊跟后面的一個(gè)符號(hào)一起組成一段(3)盡可能取最少個(gè)連著的符號(hào)并保證各段都不相同(4)以此類推，直至信源符號(hào)序列結(jié)束編碼方法為：首先去掉最后一個(gè)符號(hào)，然后看剩下的字符串在字典中的排序，這個(gè)排序值轉(zhuǎn)換成二進(jìn)制數(shù)作為指針K的值，最后一個(gè)信源符號(hào)作為碼字第2項(xiàng)d的值，即得到碼字(X, d)1.31：考慮比特序列01010110011010101011，如果用LZ編碼，那么其分段是什么，編碼后的碼字又是什么？0,1,01,011,00,11,010,10,10

13、1,1(000,0),( 000,1), (001,1), (011,1), (001,0), (010,1), (011,0), (010,0),( 1000,1),( 000,1)1.32：考慮一個(gè)如圖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：簡(jiǎn)述信道編碼定理的內(nèi)容。定理：假設(shè)DMS有信源字符集

14、X，熵為每信源符號(hào)H(X)比特，而且信源每Ts秒產(chǎn)生一個(gè)符號(hào)，那么信源的平均信息率為每秒H(X)/ Ts比特，假設(shè)信道可以每Tc秒使用一次，而信道容量為每次信道使用C比特，那么每單位時(shí)間的信道容量為每秒鐘C/Tc比特。如果H(X)/ Ts C/Tc ，那么就存在編碼方案使得在有噪聲的信道上傳輸?shù)男旁聪?，能夠以任意小的錯(cuò)誤概率進(jìn)行恢復(fù)。1.35：什么是無(wú)記憶信道和二元對(duì)稱信道？無(wú)記憶信道：如果在給定時(shí)間間隔上，檢測(cè)器的輸出只與在該時(shí)間間隔上傳送的信號(hào)有關(guān)，而與任何前面時(shí)間的傳送的信號(hào)無(wú)關(guān)，稱此信道為無(wú)記憶信道離散無(wú)記憶信道：是一種M元輸入、Q元輸出的信道模型二元對(duì)稱信道: M=2,Q=2二元對(duì)

15、稱信道: 是一種2元輸入、2元輸出的信道模型1.36：仙農(nóng)的信息定義是什么？信息量的多少跟事件發(fā)生的不確定性之間有什么關(guān)系？仙農(nóng)對(duì)于信息的定義：信息是事物運(yùn)動(dòng)狀態(tài)或存在方式不確定性的描述一個(gè)句子中所含信息的多少，同句子中所表達(dá)的事件出現(xiàn)的概率有關(guān)：呈現(xiàn)相反的關(guān)系信息量的多少，同事件發(fā)生的不確定性有關(guān)：呈現(xiàn)相反的關(guān)系第二章2.1：某些域中元素有大小之分，另一些域中的元素?zé)o大小之分，各舉一個(gè)例子。2.2：交換律、分配律、結(jié)合律在群上成立么？在環(huán)上成立么？在域上成立么？結(jié)合律在群上成立，交換律在交換群上成立，分配律群上不成立結(jié)合律在環(huán)上成立，交換律（乘法）在交換環(huán)上成立，加法和乘法在環(huán)上滿足分配律結(jié)

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

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

18、3的逆元和負(fù)元是什么？1/3 -32.6：全體整數(shù)的集合對(duì)普通減法是否構(gòu)成一個(gè)群？為什么？不不滿足結(jié)合律 3-(2-1)與(3-2)-1不等2.7：全體非負(fù)整數(shù)的集合在加法和乘法下是否構(gòu)成群？為什么？全體非負(fù)整數(shù)集合在實(shí)數(shù)加法運(yùn)算下構(gòu)成可交換群，整數(shù)0為恒元，整數(shù)-a是整數(shù)a的逆元。全體非負(fù)整數(shù)集合對(duì)乘法不構(gòu)成群，因?yàn)椴淮嬖诔朔嬖?.8：證明群的性質(zhì)定理1-4。定理1：群G的恒元是唯一的 證明：假定G中有兩個(gè)恒元e和，則有 證畢定理2：任何一個(gè)群元素的逆元是唯一的 證明：假定元素a有兩個(gè)逆元 ，則 證畢定理3：若a,bG，則 證明： 所以a*b和 互為逆元定理4：給定G中任意兩個(gè)元素a和b，

19、則方程a*x=b和y*a=b在G中有唯一解 證明：方程a*x=b的解是x=a-1*b，這是因?yàn)?a*a-1*b=e*b=b，同理，y*a=b的解是y=b*a-1。 下面證明解的唯一性。如果在方程a*x=b中， 除了x=a-1*b，還有另外一個(gè)解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：簡(jiǎn)述循環(huán)群的定義，什么是生成元？定義：一個(gè)集合G，在其上定義了一個(gè)二元運(yùn)算*，若它滿足以下條件稱為群滿足封閉性，即對(duì)G中任意兩個(gè)元素a,b,有a*bG二元運(yùn)算*滿足結(jié)合律G中存在一個(gè)元素

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

21、是素?cái)?shù)的冪次有限域的特征：設(shè)F是域，0和e是加法和乘法的單位元，若對(duì)任意正整數(shù)n，都有ne0，則稱域F的特征是0；若有正整數(shù)n，使ne=0，則稱使ne=0成立的最小正整數(shù)n為域F的特征。域的特征或是0，或是有限的素?cái)?shù)。2.11：證明有限域的性質(zhì)定理1-3。定理1：在特征為q的域中，若a是域中的任意元素，則均有qa=0證明：若a0，則qa=a+a+a=1a+1a+1a=(1+1+1)a =q 1a=0a=0，定理成立；若a=0，定理顯然成立。證畢定理1：有限域的特征q是素?cái)?shù)證明：設(shè)q0，假設(shè)q不是素?cái)?shù)，即q=q1q2,1q1q,1q2q,于是0=qe=(q1q2)e=(q1e)(q2e), 因此

22、q1e=0或者q2e=0，但這與q的最小性相矛盾，所以q只能是素?cái)?shù)。對(duì)于任意有限域，由于其只有有限個(gè)元素，所以其特征不可能為0，從而其特征一定為素?cái)?shù)。定理2：設(shè)a是有限域GF(q)的非零元素，則aq-1=1。證明：令b1,b2,bq-1為GF(q)的q-1個(gè)非零元素，顯然q-1個(gè)非零元素ab1,ab2,abq-1非零且互不相同，因此 (ab1)(ab2) (abq-1)=b1b2bq-1 所以aq-1(b1b2bq-1)= b1b2bq-1 即有aq-1=1。定理3：設(shè)a是有限域GF(q)的非零元素，令n是a的階，則q-1能被n整除，即n|(q-1) 證明：假設(shè)q-1不能被n整除，則q-1=k

23、n+r,其中0rn，于是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：簡(jiǎn)述本原元的定義，并且會(huì)用該定義判斷當(dāng)給定q時(shí)有限域GF(q)上的本原元。本原元：在有限域GF(q)中，若非零元素a的階為q-1，則稱之為本原元。2.14：什么是多項(xiàng)式？什么是首一多項(xiàng)式？多項(xiàng)式定義：二元域GF(2)中表達(dá)式f(x)=f0+f1x+fnxn，其中fi=0或1。若fn0，則稱f(x)是n次多項(xiàng)式，記為deg(f(x)=n， fn稱為多項(xiàng)式的首項(xiàng)系數(shù)。GF

24、(2)中共有2n個(gè)多項(xiàng)式首一多項(xiàng)式：首項(xiàng)系數(shù)為1的多項(xiàng)式2.15：掌握根據(jù)本原多項(xiàng)式和本原元生成GF(2)的擴(kuò)域GF(2m)的方法。p(x)=1+x+x4是GF(2)上的本原多項(xiàng)式，假設(shè)a是本原元，則a4=a+1,由此可以構(gòu)造GF(24)2.16：什么是最高公因式？什么是公倍式？什么是最低公倍式？最高公因式：若f(x)為a(x)與b(x)的所有公因式中次數(shù)最高的，并且首項(xiàng)系數(shù)為1，記為gcd(a(x), b(x)f(x)為a(x)與b(x)的公倍式：當(dāng)a(x)0, b(x)0，并且a(x)| f(x)，b(x)|f(x)最低公倍式：若f(x)為a(x)與b(x)的所有公倍式中次數(shù)最低的，并且首

25、項(xiàng)系數(shù)為1，記為L(zhǎng)CM(a(x), b(x)2.17：什么是本原多項(xiàng)式？本原多項(xiàng)式的定義：若m次既約多項(xiàng)式p(x)可以除盡xn+1的最小整數(shù)n滿足n=2m-1，則稱p(x)是本原多項(xiàng)式2.18： 證明GF(2)上的多項(xiàng)式f(x)滿足f(x)2= f(x2) 。2.19： GF(2)上的多項(xiàng)式的根的特點(diǎn)是什么。定理：若f(x)為GF(2)上的一個(gè)m次既約多項(xiàng)式，則其擴(kuò)域GF(2m)含有f(x)的m個(gè)根；進(jìn)一步的，若m|d，則任何GF(2d)含有f(x)的根定理：若f(x)是系數(shù)取自GF(2)的多項(xiàng)式，令b是GF(2)擴(kuò)域中的元素，若b是f(x)的根，則對(duì)任意的l0，b2l也是f(x)的根2.20

26、：什么是域元素的共軛元。注：元素b2l稱為b的共軛元，以上定理說(shuō)明若是b是多項(xiàng)式f(x)的根，則b的所有共軛元b2l也是f(x)的根2.21：什么是最小多項(xiàng)式？定義：令m(x)是使得m(b)=0成立的次數(shù)最低的多項(xiàng)式，則稱m(x)是b的最小多項(xiàng)式2.22：什么是矢量空間？定義：令V是元素的集合，在其上定義了一個(gè)稱作是加法(+)的二元運(yùn)算。令F是域。在域F中的元素和V中的元素之間還定義了一個(gè)數(shù)乘運(yùn)算()。若集合V滿足下述條件，就稱它為域F上的矢量空間或線性空間：條件1：V是加法下的可交換群條件2：對(duì)F中的任意元素a和V中的任意元素v，av是V中的元素條件3：分配率。對(duì)任意u,vV和a,bF，有a

27、(u+v)=au+av, (a+b)v=av+bv條件4：結(jié)合率。對(duì)任意vV和a,bF，有(ab)v=a(bv)條件5：令1是F的單位元，則對(duì)任意vV ，有1 v= v2.23：矢量空間有哪些性質(zhì)？性質(zhì)1：令0是域F中的零元，對(duì)任意的vV，有0v=0性質(zhì)2：對(duì)任意cF，有c0=0性質(zhì)3：對(duì)任意cF和vV ，有 (-c)v=c(-v)=-(cv)性質(zhì)4：如果cv=0,則c=0或者v=0 2.24：簡(jiǎn)述n重的定義。n重：GF(2)上的n個(gè)分量的有序序列(a1,a2,an)稱作n重,共有2n個(gè)不同的n重，令Vn表示所有n重的集合2.25： 什么是線性組合？什么是線性相關(guān)？令v1,v2,vkV是k個(gè)矢

28、量，a1,a2,akF是k個(gè)標(biāo)量，稱ai vi為線性組合定義：域F上矢量空間V的一組矢量v1,v2,vk稱作是線性相關(guān)的，當(dāng)且僅當(dāng)存在不全為0的標(biāo)量a1,a2,ak，使得 。否則稱v1,v2,vk是線性獨(dú)立的第三章3.1：簡(jiǎn)述線性(n,k)分組碼的定義。定義：長(zhǎng)為n，有2k個(gè)碼字的分組碼，當(dāng)且僅當(dāng)其2k個(gè)碼字構(gòu)成GF(2)上所有n重矢量空間的一個(gè)k維子空間時(shí)，稱作線性(n,k)分組碼3.2：什么是生成矩陣？請(qǐng)具體構(gòu)造幾個(gè)線性(n,k)分組碼的生成矩陣。因?yàn)榫€性(n,k)分組碼C是一個(gè)k維子空間，所以在碼C中能找到k個(gè)線性獨(dú)立的碼字g0, g1, gk-1,使得C中的每個(gè)碼字v都是這k個(gè)碼字的一

29、種線性組合，即v=u0g0+u1g1+uk-1gk-1將這k個(gè)線性獨(dú)立的碼字作為行，得到kn階矩陣此矩陣稱為碼C的生成矩陣。線性(n,k)分組碼任何k個(gè)線性獨(dú)立的碼字都可以用來(lái)構(gòu)成碼C的生成矩陣舉例: (7,4)線性分組碼如果表格所表示的線性分組碼，有如下的生成矩陣若u=(1101)，則3.3：什么是線性系統(tǒng)(n,k)分組碼？線性系統(tǒng)分組碼：若(n,k)線性分組碼C的生成矩陣形如G=P Ik(或G=Ik P)，此時(shí)稱C為線性系統(tǒng)分組碼。此時(shí)，每個(gè)碼字都可以被分成兩個(gè)部分，即消息部分和冗余部分3.4：什么是一致校驗(yàn)方程？什么是一致校驗(yàn)矩陣？什么是對(duì)偶碼？關(guān)于線性系統(tǒng)分組碼，對(duì)應(yīng)于消息u=(u0,

30、 u1, uk-1)的碼字是v=(v0, v1, vn-1)=uG=uP Ik，即 vn-k+i=ui , 0ik-1, vj=u0P0j+u1P1j+uk-1Pk-1j, 0jn-k-1 上面兩個(gè)式子正好反映系統(tǒng)的組成特性，最后這n-k個(gè)方程稱為碼C的一致校驗(yàn)方程定義：與(n,k)線性分組碼C的生成矩陣G相對(duì)應(yīng)有一個(gè)(n-k)n階矩陣H，它的n-k個(gè)行是碼C的對(duì)偶空間的一組基底，該矩陣H稱為碼C的一致校驗(yàn)矩陣對(duì)偶碼：以H為生成矩陣得到的(n,n-k)碼稱為碼C的對(duì)偶碼，記為Cd3.5：什么是伴隨式？伴隨式糾錯(cuò)的原理是什么？伴隨式：當(dāng)接收到r后，譯碼器計(jì)算下述n-k重S=rHT =(s0, s

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

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

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

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

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

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

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

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

39、碼C，若它的每個(gè)碼字的任何循環(huán)移位都仍然是一個(gè)碼字，則稱此碼為循環(huán)碼4.2：什么是碼字多項(xiàng)式？證明碼字多項(xiàng)式v(i)(x)就是xiv(0)(x)/(xn+1)的余式。碼字多項(xiàng)式：為研究循環(huán)碼的代數(shù)特性，將碼字v=(v0,v1,vn-1)的各個(gè)分量看成是多項(xiàng)式 的系數(shù)，此多項(xiàng)式稱為v的碼字多項(xiàng)式碼字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 v(2)(x)=vn

40、-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)=q(x)(xn+1)+

41、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ù)最低的非零碼字多項(xiàng)式是唯一的證明：令 是C中次數(shù)最低的碼字多項(xiàng)式，若g(x)不唯一，則存在另一個(gè)碼字多項(xiàng)式 ，由線性性質(zhì)可知，g(x)+g*(x)也是一個(gè)碼字多項(xiàng)式，但它的次數(shù)小于r，和前提矛盾，所以循環(huán)碼C中次數(shù)最低的非零碼字多項(xiàng)式是唯一的。證畢。定理2：若g(x)=g0+g1x+gr-1xr-1+xr是(n.k)循環(huán)碼C中次數(shù)最低的非零碼字多項(xiàng)式，則必有g(shù)0=1證明：若g0=0，則g(x)=x(g1+g2x+gr-1xr-2+xr-1)，將g(x)循環(huán)右

42、移n-1位之后，可以得到一個(gè)次數(shù)更低的碼字多項(xiàng)式，其次數(shù)為r-1，和前提矛盾，則必有g(shù)0=1。證畢。結(jié)合定理1和定理2，知在(n,k)循環(huán)碼中，次數(shù)最低的非零碼字多項(xiàng)式形如g(x)=1+g1x+g2x2+gr-1xr-1+xr定理3：若g(x)是(n.k)循環(huán)碼C中次數(shù)最低的非零碼字多項(xiàng)式，一個(gè)次數(shù)小于或等于n-1的二元多項(xiàng)式f(x)是碼字多項(xiàng)式當(dāng)且僅當(dāng)f(x)是g(x)的倍式證明：反證法。設(shè)f(x)是碼字多項(xiàng)式并且其次數(shù)小于或等于n-1，假設(shè)f(x)=a(x)g(x)+b(x), deg(b(x)r，由線性性質(zhì)可知b(x)=f(x)+a(x)g(x)也是一個(gè)碼字多項(xiàng)式，而deg(b(x)de

43、g(g(x)，這和前提矛盾，則只能當(dāng)f(x)是g(x)的倍式的時(shí)候，f(x)是碼字多項(xiàng)式。證畢。4.4：簡(jiǎn)述系統(tǒng)循環(huán)碼的編碼原理和編碼步驟？編碼原理給定循環(huán)碼的生成多項(xiàng)式g(x)，可以使該碼成為系統(tǒng)形式。假定待編碼的消息是u=(u0, u1, uk-1)，則對(duì)應(yīng)的消息多項(xiàng)式為u(x)=u0+u1x+u2x2+ uk-1xk-1從而有，xn-ku(x)=u0xn-k+u1xn-k+1+ uk-1xn-1用生成多項(xiàng)式g(x)除xn-ku(x)，得到xn-ku(x)= a(x)g(x)+b(x)，deg(b(x)n-k調(diào)整上式得到xn-ku(x)+b(x)=a(x)g(x)，即xn-ku(x)+ b(x)是g(x)的倍式，因而是C的碼字多項(xiàng)式， xn-ku(x)+b(x)=b0+b1x+b2x2+ bn-k-1xn-k-1+ u0xn-k+u1xn-k+1+ uk-1xn-1 ，這對(duì)應(yīng)碼矢(b0,b1,bn-k-1, u0, u1,uk-1)，此即為系統(tǒng)形式編碼步驟第一步：先用xn-k乘以消息多項(xiàng)式u(x)=u0+u1x+u2x2+ uk-1xk-1第二步：用生成多項(xiàng)式g(x)