數(shù)字通信技術(shù)第10章

1、1信道編碼：信道編碼：p目的：提高信號(hào)傳輸?shù)目煽啃?。目的：提高信?hào)傳輸?shù)目煽啃?。p方法：增加多余比特，以發(fā)現(xiàn)或糾正錯(cuò)誤。方法：增加多余比特，以發(fā)現(xiàn)或糾正錯(cuò)誤。 差錯(cuò)控制差錯(cuò)控制：包括信道編碼在內(nèi)的一切糾正錯(cuò)誤手段。：包括信道編碼在內(nèi)的一切糾正錯(cuò)誤手段。產(chǎn)生錯(cuò)碼的原因：產(chǎn)生錯(cuò)碼的原因：p乘性干擾引起的碼間串?dāng)_乘性干擾引起的碼間串?dāng)_p加性干擾引起的信噪比降低加性干擾引起的信噪比降低 信道分類(lèi)：按照加性干擾造成錯(cuò)碼的統(tǒng)計(jì)特性不同劃分信道分類(lèi)：按照加性干擾造成錯(cuò)碼的統(tǒng)計(jì)特性不同劃分p隨機(jī)信道：錯(cuò)碼隨機(jī)出現(xiàn)，例如由白噪聲引起的錯(cuò)碼隨機(jī)信道：錯(cuò)碼隨機(jī)出現(xiàn)，例如由白噪聲引起的錯(cuò)碼 p突發(fā)信道：錯(cuò)碼相對(duì)集中出

2、現(xiàn)，例如由脈沖干擾引起的錯(cuò)突發(fā)信道：錯(cuò)碼相對(duì)集中出現(xiàn)，例如由脈沖干擾引起的錯(cuò)碼。碼。 p混合信道：既存在隨機(jī)錯(cuò)碼又存在突發(fā)錯(cuò)碼混合信道：既存在隨機(jī)錯(cuò)碼又存在突發(fā)錯(cuò)碼 2差錯(cuò)控制技術(shù)的種類(lèi)差錯(cuò)控制技術(shù)的種類(lèi)：p檢錯(cuò)重發(fā)檢錯(cuò)重發(fā)：u能發(fā)現(xiàn)錯(cuò)碼，但是不能確定錯(cuò)碼的位置。能發(fā)現(xiàn)錯(cuò)碼，但是不能確定錯(cuò)碼的位置。u通信系統(tǒng)需要有雙向信道。通信系統(tǒng)需要有雙向信道。 p前向糾錯(cuò)前向糾錯(cuò)(FEC)：利用加入的差錯(cuò)控制碼元，不但能夠發(fā)：利用加入的差錯(cuò)控制碼元，不但能夠發(fā)現(xiàn)錯(cuò)碼，還能糾正錯(cuò)碼?，F(xiàn)錯(cuò)碼，還能糾正錯(cuò)碼。p 反饋校驗(yàn)反饋校驗(yàn)：u將收到的碼元轉(zhuǎn)發(fā)回發(fā)送端，將它和原發(fā)送碼元比較。將收到的碼元轉(zhuǎn)發(fā)回發(fā)送端，將它和

3、原發(fā)送碼元比較。u缺點(diǎn)：需要雙向信道，傳輸效率也較低。缺點(diǎn)：需要雙向信道，傳輸效率也較低。p檢錯(cuò)刪除檢錯(cuò)刪除：u在接收端發(fā)現(xiàn)錯(cuò)碼后，立即將其刪除。在接收端發(fā)現(xiàn)錯(cuò)碼后，立即將其刪除。u適用在發(fā)送碼元中有大量多余度，刪除部分接收碼元不適用在發(fā)送碼元中有大量多余度，刪除部分接收碼元不影響應(yīng)用之處。影響應(yīng)用之處。 3p監(jiān)督碼元監(jiān)督碼元：上述：上述4種技術(shù)中除第種技術(shù)中除第3種外，都是在接收端種外，都是在接收端識(shí)別有無(wú)錯(cuò)碼。所以識(shí)別有無(wú)錯(cuò)碼。所以在發(fā)送端需要在信息碼元序列中在發(fā)送端需要在信息碼元序列中增加一些差錯(cuò)控制碼元，它們稱(chēng)為監(jiān)督碼元增加一些差錯(cuò)控制碼元，它們稱(chēng)為監(jiān)督碼元。p不同的編碼方法，有不同的

4、檢錯(cuò)或糾錯(cuò)能力。不同的編碼方法，有不同的檢錯(cuò)或糾錯(cuò)能力。p多余度多余度：就是：就是指增加的監(jiān)督碼元多少指增加的監(jiān)督碼元多少。例如例如，若編碼，若編碼序列中序列中平均每?jī)蓚€(gè)信息碼元就添加一個(gè)監(jiān)督碼元平均每?jī)蓚€(gè)信息碼元就添加一個(gè)監(jiān)督碼元，則，則這種編碼的這種編碼的多余度為多余度為1/3。p編碼效率編碼效率(簡(jiǎn)稱(chēng)碼率簡(jiǎn)稱(chēng)碼率) ：設(shè)編碼序列中：設(shè)編碼序列中信息碼元數(shù)量為信息碼元數(shù)量為k，總碼元數(shù)量為總碼元數(shù)量為n，則比值，則比值k/n 就是編碼效率就是編碼效率。p冗余度冗余度：監(jiān)督碼元數(shù)監(jiān)督碼元數(shù)(n-k) 和信息碼元數(shù)和信息碼元數(shù) k 之比之比。p理論上，差錯(cuò)控制以降低信息傳輸速率為代價(jià)換取提理論

5、上，差錯(cuò)控制以降低信息傳輸速率為代價(jià)換取提高傳輸可靠性。高傳輸可靠性。4編碼序列的參數(shù)編碼序列的參數(shù)un 編碼序列中總碼元數(shù)量編碼序列中總碼元數(shù)量uk 編碼序列中信息碼元數(shù)量編碼序列中信息碼元數(shù)量ur 編碼序列中差錯(cuò)控制碼元數(shù)量編碼序列中差錯(cuò)控制碼元數(shù)量 （差錯(cuò)控制碼元，以后稱(chēng)為監(jiān)督碼元或監(jiān)督位（差錯(cuò)控制碼元，以后稱(chēng)為監(jiān)督碼元或監(jiān)督位 ）uk/n 碼率（編碼效率）碼率（編碼效率）u(n - k) / k = r / k 冗余度冗余度ur / n 多余度多余度5自動(dòng)要求重發(fā)自動(dòng)要求重發(fā)(ARQ)系統(tǒng)（系統(tǒng)（Automatic Repeate Quest）p停止等待停止等待ARQ系統(tǒng)系統(tǒng) 停止等待

6、ARQ系統(tǒng)接收數(shù)據(jù)ACKACKNAKACKACKNAKACK1233455t發(fā)送數(shù)據(jù)12334556t有錯(cuò)碼組有錯(cuò)碼組u數(shù)據(jù)按分組發(fā)送。每發(fā)送一組數(shù)據(jù)后發(fā)送端等待接收端數(shù)據(jù)按分組發(fā)送。每發(fā)送一組數(shù)據(jù)后發(fā)送端等待接收端的確認(rèn)的確認(rèn)(ACK)答復(fù)，然后再發(fā)送下一組數(shù)據(jù)。答復(fù)，然后再發(fā)送下一組數(shù)據(jù)。u圖中的第圖中的第3組接收數(shù)據(jù)有誤，接收端發(fā)回一個(gè)否認(rèn)組接收數(shù)據(jù)有誤，接收端發(fā)回一個(gè)否認(rèn)(NAK)答復(fù)。這時(shí)，發(fā)送端將重發(fā)第答復(fù)。這時(shí)，發(fā)送端將重發(fā)第3組數(shù)據(jù)。組數(shù)據(jù)。u特點(diǎn)：特點(diǎn)：工作在半雙工狀態(tài)，時(shí)間沒(méi)有得到充分利用，傳工作在半雙工狀態(tài)，時(shí)間沒(méi)有得到充分利用，傳輸效率較低。輸效率較低。6p 拉后拉后A

7、RQ系統(tǒng)系統(tǒng)拉后ARQ系統(tǒng)214365798接收數(shù)據(jù)有錯(cuò)碼組有錯(cuò)碼組910 1110 11 12576ACK1NAK5NAK9ACK55769521436798發(fā)送數(shù)據(jù)10 1110 11 12重發(fā)碼組重發(fā)碼組u發(fā)送端連續(xù)發(fā)送數(shù)據(jù)組，接收端對(duì)于每個(gè)接收到的數(shù)據(jù)發(fā)送端連續(xù)發(fā)送數(shù)據(jù)組，接收端對(duì)于每個(gè)接收到的數(shù)據(jù)組都發(fā)回確認(rèn)組都發(fā)回確認(rèn)(ACK)或否認(rèn)或否認(rèn)(NAK)答復(fù)。答復(fù)。u例如，圖中第例如，圖中第5組接收數(shù)據(jù)有誤，則在發(fā)送端收到第組接收數(shù)據(jù)有誤，則在發(fā)送端收到第5組接組接收的否認(rèn)答復(fù)后，從第收的否認(rèn)答復(fù)后，從第5組開(kāi)始重發(fā)數(shù)據(jù)組。組開(kāi)始重發(fā)數(shù)據(jù)組。u在這種系統(tǒng)中在這種系統(tǒng)中需要對(duì)發(fā)送的數(shù)據(jù)組

8、和答復(fù)進(jìn)行編號(hào)，以需要對(duì)發(fā)送的數(shù)據(jù)組和答復(fù)進(jìn)行編號(hào)，以便識(shí)別。顯然，這種系統(tǒng)需要雙工信道。便識(shí)別。顯然，這種系統(tǒng)需要雙工信道。7p 選擇重發(fā)選擇重發(fā)ARQ系統(tǒng)系統(tǒng)選擇重發(fā)ARQ系統(tǒng)9接收數(shù)據(jù)有錯(cuò)碼組有錯(cuò)碼組214365759810 11131412發(fā)送數(shù)據(jù)9958521436710 1113 1412重發(fā)碼組重發(fā)碼組NAK9ACK1NAK5ACK5ACK9u它只重發(fā)出錯(cuò)的數(shù)據(jù)組，因此進(jìn)一步提高了傳輸效率它只重發(fā)出錯(cuò)的數(shù)據(jù)組，因此進(jìn)一步提高了傳輸效率8 ARQ的主要特點(diǎn)：與前向糾錯(cuò)比較的主要特點(diǎn)：與前向糾錯(cuò)比較p優(yōu)點(diǎn)優(yōu)點(diǎn)u監(jiān)督碼元較少，即碼率較高監(jiān)督碼元較少，即碼率較高u檢錯(cuò)的計(jì)算復(fù)雜度較低檢錯(cuò)

9、的計(jì)算復(fù)雜度較低u能適應(yīng)不同特性的信道能適應(yīng)不同特性的信道p缺點(diǎn)缺點(diǎn)u需要雙向信道需要雙向信道u不適用于一點(diǎn)到多點(diǎn)的通信系統(tǒng)或廣播系統(tǒng)不適用于一點(diǎn)到多點(diǎn)的通信系統(tǒng)或廣播系統(tǒng)u傳輸效率降低，可能因反復(fù)重發(fā)而造成事實(shí)上的通傳輸效率降低，可能因反復(fù)重發(fā)而造成事實(shí)上的通信中斷信中斷u在要求實(shí)時(shí)通信的場(chǎng)合，例如電話通信，往往不允在要求實(shí)時(shí)通信的場(chǎng)合，例如電話通信，往往不允許使用許使用ARQ法法9ARQ系統(tǒng)的原理方框圖系統(tǒng)的原理方框圖p在發(fā)送端，輸入的信息碼元在編碼器中被分組編碼（加入在發(fā)送端，輸入的信息碼元在編碼器中被分組編碼（加入監(jiān)督碼元）后，除了立即發(fā)送外，還暫存于緩沖存儲(chǔ)器中。監(jiān)督碼元）后，除了立

10、即發(fā)送外，還暫存于緩沖存儲(chǔ)器中。若接收端解碼器檢出錯(cuò)碼，則由解碼器控制產(chǎn)生一個(gè)重發(fā)若接收端解碼器檢出錯(cuò)碼，則由解碼器控制產(chǎn)生一個(gè)重發(fā)指令。此指令經(jīng)過(guò)反向信道送到發(fā)送端。由發(fā)送端重發(fā)控指令。此指令經(jīng)過(guò)反向信道送到發(fā)送端。由發(fā)送端重發(fā)控制器控制緩沖存儲(chǔ)器重發(fā)一次。制器控制緩沖存儲(chǔ)器重發(fā)一次。p接收端僅當(dāng)解碼器認(rèn)為接收信息碼元正確時(shí)，才將信息碼接收端僅當(dāng)解碼器認(rèn)為接收信息碼元正確時(shí)，才將信息碼元送給收信者，否則在輸出緩沖存儲(chǔ)器中刪除接收碼元。元送給收信者，否則在輸出緩沖存儲(chǔ)器中刪除接收碼元。p當(dāng)解碼器未發(fā)現(xiàn)錯(cuò)碼時(shí)，經(jīng)過(guò)反向信道發(fā)出不需重發(fā)指令。當(dāng)解碼器未發(fā)現(xiàn)錯(cuò)碼時(shí)，經(jīng)過(guò)反向信道發(fā)出不需重發(fā)指令。發(fā)送

11、端收到此指令后，即繼續(xù)發(fā)送后一碼組，發(fā)送端的緩發(fā)送端收到此指令后，即繼續(xù)發(fā)送后一碼組，發(fā)送端的緩沖存儲(chǔ)器中的內(nèi)容也隨之更新。沖存儲(chǔ)器中的內(nèi)容也隨之更新。10分組碼舉例分組碼舉例p設(shè)：有一種由設(shè)：有一種由3位二進(jìn)制碼元構(gòu)成的編碼，它共有位二進(jìn)制碼元構(gòu)成的編碼，它共有23 = 8種種不同的可能碼組，可以表示不同的可能碼組，可以表示8種不同天氣：種不同天氣：000 晴晴 011 云云 101 陰陰 110 雨雨100 雪雪 001 霜霜 010 霧霧 111 雹雹 其中，若一個(gè)碼組中發(fā)生錯(cuò)碼，則將變成另一個(gè)信息碼組。其中，若一個(gè)碼組中發(fā)生錯(cuò)碼，則將變成另一個(gè)信息碼組。這時(shí)，接收端將無(wú)法發(fā)現(xiàn)錯(cuò)誤。這時(shí)

12、，接收端將無(wú)法發(fā)現(xiàn)錯(cuò)誤。 p若在此若在此8種碼組中僅允許使用種碼組中僅允許使用4種來(lái)傳送天氣，例如：種來(lái)傳送天氣，例如：000 晴晴 011 云云 101 陰陰 110 雨雨 為為許用碼組許用碼組，其他，其他4種不允許使用，稱(chēng)為種不允許使用，稱(chēng)為禁用碼組禁用碼組。 這時(shí)，接收端有可能發(fā)現(xiàn)（檢測(cè)到）碼組中的一個(gè)錯(cuò)碼。這時(shí)，接收端有可能發(fā)現(xiàn)（檢測(cè)到）碼組中的一個(gè)錯(cuò)碼。 例例: “000”（晴）中錯(cuò)了一位，變成（晴）中錯(cuò)了一位，變成“100”或或“010”或或“001” 這種編碼只能檢測(cè)錯(cuò)碼，不能糾正錯(cuò)碼這種編碼只能檢測(cè)錯(cuò)碼，不能糾正錯(cuò)碼。 p若規(guī)定只允許用兩個(gè)碼組：例如若規(guī)定只允許用兩個(gè)碼組：例如

13、000 晴晴 111 雨雨就能檢測(cè)兩個(gè)以下錯(cuò)碼，或糾正一個(gè)錯(cuò)碼。就能檢測(cè)兩個(gè)以下錯(cuò)碼，或糾正一個(gè)錯(cuò)碼。 11分組碼概念分組碼概念p 將信息碼分組，為每組信息碼附加若干監(jiān)督碼的編碼將信息碼分組，為每組信息碼附加若干監(jiān)督碼的編碼稱(chēng)為稱(chēng)為分組碼。分組碼。即即 分組碼分組碼 信息位信息位 監(jiān)督位監(jiān)督位 在分組碼中，監(jiān)督碼元僅監(jiān)督本碼組中的信息碼元。在分組碼中，監(jiān)督碼元僅監(jiān)督本碼組中的信息碼元。p 分組碼符號(hào)：分組碼符號(hào)：(n, k)其中，其中，n 碼組總長(zhǎng)度，碼組總長(zhǎng)度， k 信息碼元數(shù)目。信息碼元數(shù)目。 r = n k 監(jiān)督碼元數(shù)目。監(jiān)督碼元數(shù)目。下表中的碼組為下表中的碼組為(3, 2)碼。碼。信息

14、位監(jiān)督位晴000云011陰101雨11012p 分組碼的一般結(jié)構(gòu)：分組碼的一般結(jié)構(gòu)：p 分組碼的參數(shù)：分組碼的參數(shù)：u碼重：碼組內(nèi)碼重：碼組內(nèi)“1”的個(gè)數(shù)。例：的個(gè)數(shù)。例： “101”的碼重是的碼重是2u碼距：兩碼組中對(duì)應(yīng)位取值不同的位數(shù)，又稱(chēng)漢明距離。碼距：兩碼組中對(duì)應(yīng)位取值不同的位數(shù)，又稱(chēng)漢明距離。 例：例： “000”晴，晴，“011”云，云，“101”陰，陰，“110”雨，雨， 4個(gè)碼組之間，任意兩個(gè)的距離均為個(gè)碼組之間，任意兩個(gè)的距離均為2 u最小碼距最小碼距(d0) ：各碼組間的最小距離。：各碼組間的最小距離。k個(gè)信息位r個(gè)監(jiān)督位an-1an-2.arar-1an-2.a0t碼長(zhǎng)

15、n = k + r分組碼的結(jié)構(gòu)13p碼距的幾何意義：以碼距的幾何意義：以n = 3的編碼為例的編碼為例 u每個(gè)碼組的每個(gè)碼組的3個(gè)碼元值個(gè)碼元值(a1, a2, a3)就是此立方體各頂點(diǎn)的坐就是此立方體各頂點(diǎn)的坐標(biāo)。碼距是對(duì)應(yīng)于圖中各頂點(diǎn)之間沿立方體各邊行走的幾標(biāo)。碼距是對(duì)應(yīng)于圖中各頂點(diǎn)之間沿立方體各邊行走的幾何距離。何距離。例：例：“000”晴，晴，“011”云，云，“101”陰，陰，“110”雨，雨， 4個(gè)碼組之間，任意兩個(gè)的距離均為個(gè)碼組之間，任意兩個(gè)的距離均為2u一般而言，碼距是一般而言，碼距是 n 維空間中單位正多面體頂點(diǎn)之間的漢維空間中單位正多面體頂點(diǎn)之間的漢明距離。明距離。(0,

16、0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a114碼距和檢糾錯(cuò)能力的關(guān)系碼距和檢糾錯(cuò)能力的關(guān)系一種編碼的糾檢錯(cuò)能力：決定于最小碼距一種編碼的糾檢錯(cuò)能力：決定于最小碼距d0的值。的值。p為了能檢測(cè)為了能檢測(cè)e個(gè)錯(cuò)碼，要求個(gè)錯(cuò)碼，要求 最小碼距為最小碼距為p為了能糾正為了能糾正 t 個(gè)錯(cuò)個(gè)錯(cuò) 碼，要求最小碼距碼，要求最小碼距 10 ed0123BA漢明距離ed0碼距等于3的兩個(gè)碼組120 tdBtA漢明距離012345td0碼距等于5的兩個(gè)碼組15p為了能糾正為了能糾正t個(gè)錯(cuò)碼，同時(shí)檢測(cè)個(gè)錯(cuò)碼，同時(shí)檢測(cè)e個(gè)錯(cuò)碼，要求最小碼距個(gè)

17、錯(cuò)碼，要求最小碼距糾檢結(jié)合工作方式：糾檢結(jié)合工作方式：n當(dāng)錯(cuò)碼數(shù)量少時(shí)，系統(tǒng)按前向糾錯(cuò)方式工作，以節(jié)當(dāng)錯(cuò)碼數(shù)量少時(shí)，系統(tǒng)按前向糾錯(cuò)方式工作，以節(jié)省重發(fā)時(shí)間，提高傳輸效率；省重發(fā)時(shí)間，提高傳輸效率；n當(dāng)錯(cuò)碼數(shù)量多時(shí)，系統(tǒng)按反饋重發(fā)的糾錯(cuò)方式工作，當(dāng)錯(cuò)碼數(shù)量多時(shí)，系統(tǒng)按反饋重發(fā)的糾錯(cuò)方式工作，以降低系統(tǒng)的總誤碼率。以降低系統(tǒng)的總誤碼率。 AB1tt漢明距離e碼距等于(e+t+1)的兩個(gè)碼組)(10teted1610.3.1 誤碼率性能和帶寬的關(guān)系誤碼率性能和帶寬的關(guān)系 采用編碼降低誤碼率采用編碼降低誤碼率所付出的代價(jià)是帶寬的增大所付出的代價(jià)是帶寬的增大。10-610-510-410-310-210

18、-1編碼后Eb/n0 (dB)編碼和誤碼率關(guān)系PeCDEAB2PSKA與與B點(diǎn)：相同的接收信噪比下點(diǎn)：相同的接收信噪比下誤碼率降低約一個(gè)半數(shù)量級(jí)。誤碼率降低約一個(gè)半數(shù)量級(jí)。1710.3.2 功率和帶寬的關(guān)系功率和帶寬的關(guān)系采用編碼以節(jié)省功率，并保持采用編碼以節(jié)省功率，并保持誤碼率不變，付出的代價(jià)也是誤碼率不變，付出的代價(jià)也是帶寬增大。帶寬增大。 10-610-510-410-310-210-1編碼后Eb/n0 (dB)編碼和誤碼率關(guān)系PeCDEAB2PSKC與與D點(diǎn)：相同的誤碼率下，點(diǎn)：相同的誤碼率下，編碼后輸入信噪比可降低約編碼后輸入信噪比可降低約2dB，即可以節(jié)省功率，即可以節(jié)省功率2dB

19、。通常稱(chēng)這通常稱(chēng)這2 dB為為編碼增益。編碼增益。1810.3.3 傳輸速率和帶寬的關(guān)系傳輸速率和帶寬的關(guān)系對(duì)于給定的傳輸系統(tǒng)，其傳輸速率和對(duì)于給定的傳輸系統(tǒng)，其傳輸速率和Eb/n0的關(guān)系：的關(guān)系：式中，式中，RB 碼元速率。碼元速率。 提高傳輸速率，采用編提高傳輸速率，采用編碼以保持誤碼率不變；付出碼以保持誤碼率不變；付出的代價(jià)仍是帶寬增大的代價(jià)仍是帶寬增大。BsssbRnP)T/(nPnTPnE0000110-610-510-410-310-210-1編碼后Eb/n0 (dB)編碼和誤碼率關(guān)系PeCDEAB2PSK提高碼元速率后由提高碼元速率后由C點(diǎn)升到點(diǎn)升到E點(diǎn)（信噪比下降，誤碼率點(diǎn)（信

20、噪比下降，誤碼率增大），用糾錯(cuò)編碼后，將增大），用糾錯(cuò)編碼后，將誤碼率降到誤碼率降到D點(diǎn)。這時(shí)付出點(diǎn)。這時(shí)付出的代價(jià)仍是帶寬增大的代價(jià)仍是帶寬增大1910.3.4 編碼增益編碼增益定義：在保持誤碼率恒定條件下，采用糾錯(cuò)編碼所節(jié)省的信定義：在保持誤碼率恒定條件下，采用糾錯(cuò)編碼所節(jié)省的信 噪比噪比Eb/n0稱(chēng)為編碼增益：稱(chēng)為編碼增益： 式中，式中，(Eb/n0)u 未編碼時(shí)的信噪比未編碼時(shí)的信噪比(dB)； (Eb/n0)c 編碼后所需的信噪比編碼后所需的信噪比(dB)。)(/00dBnEnEGcbubdB2010.4.1 一維奇偶監(jiān)督碼一維奇偶監(jiān)督碼奇偶監(jiān)督碼奇偶監(jiān)督碼 分為奇數(shù)監(jiān)督碼和偶數(shù)監(jiān)督

21、碼兩類(lèi)。分為奇數(shù)監(jiān)督碼和偶數(shù)監(jiān)督碼兩類(lèi)。在奇偶監(jiān)督碼中，監(jiān)督位只有在奇偶監(jiān)督碼中，監(jiān)督位只有1位，故碼率等于位，故碼率等于k/(k+1)。偶數(shù)監(jiān)督碼中，此監(jiān)督位使碼組中偶數(shù)監(jiān)督碼中，此監(jiān)督位使碼組中“1”的個(gè)數(shù)為偶數(shù)的個(gè)數(shù)為偶數(shù)：式中，式中，a0為監(jiān)督位，其他位為信息位。為監(jiān)督位，其他位為信息位。奇數(shù)監(jiān)督碼中，此監(jiān)督位使碼組中奇數(shù)監(jiān)督碼中，此監(jiān)督位使碼組中“1”的個(gè)數(shù)為奇數(shù)：的個(gè)數(shù)為奇數(shù)：0021aaann1021aaann21檢錯(cuò)能力檢錯(cuò)能力 能夠檢測(cè)奇數(shù)個(gè)錯(cuò)碼。能夠檢測(cè)奇數(shù)個(gè)錯(cuò)碼。 n設(shè)：碼組長(zhǎng)度為設(shè)：碼組長(zhǎng)度為n， 碼組中各個(gè)錯(cuò)碼的發(fā)生是獨(dú)立的和等概率的，碼組中各個(gè)錯(cuò)碼的發(fā)生是獨(dú)立的和等

22、概率的， 則在一個(gè)碼組中出現(xiàn)則在一個(gè)碼組中出現(xiàn) j 個(gè)錯(cuò)碼的概率為個(gè)錯(cuò)碼的概率為 式中，式中， 為在為在n個(gè)碼元中有個(gè)碼元中有j個(gè)錯(cuò)碼的組合數(shù)。個(gè)錯(cuò)碼的組合數(shù)。n奇偶監(jiān)督碼不能檢測(cè)碼組中出現(xiàn)的偶數(shù)個(gè)錯(cuò)碼奇偶監(jiān)督碼不能檢測(cè)碼組中出現(xiàn)的偶數(shù)個(gè)錯(cuò)碼，所以在一，所以在一個(gè)碼組中有錯(cuò)碼而不能檢測(cè)的概率等于個(gè)碼組中有錯(cuò)碼而不能檢測(cè)的概率等于: 當(dāng)當(dāng)n為偶數(shù)時(shí)為偶數(shù)時(shí) 當(dāng)當(dāng)n為奇數(shù)時(shí)為奇數(shù)時(shí) jnjnj)p(pC)n, j(P1)!( !jnjnCnj2/1222)1 (njjnjnjuppCP2/ )1(1222)1 (njjnjnjuppCP22例：例：右表中的編碼是偶數(shù)監(jiān)督碼。右表中的編碼是偶數(shù)監(jiān)督碼

23、。 設(shè)信道的誤碼率為設(shè)信道的誤碼率為10-4，錯(cuò)碼，錯(cuò)碼 的出現(xiàn)是獨(dú)立的。試計(jì)算其不的出現(xiàn)是獨(dú)立的。試計(jì)算其不 能檢測(cè)的誤碼率。能檢測(cè)的誤碼率。將給定條件代入式將給定條件代入式計(jì)算得出計(jì)算得出由計(jì)算結(jié)果可見(jiàn)，此編碼可以將誤碼率從由計(jì)算結(jié)果可見(jiàn)，此編碼可以將誤碼率從10-4降低到降低到10-8量量級(jí)。效果非常明顯。級(jí)。效果非常明顯。信息位監(jiān)督位晴0000云0101陰1001雨11002/1222)1 (njjnjnjuppCP8244324220444224221242421066612616111pppppp)p(p)p(pC)p(pC)p(pCPjjjju2311na12na11a10a21

24、na22na21a20amna1mna2ma1ma01nc2nc1c0c10.4.2 二維奇偶監(jiān)督碼二維奇偶監(jiān)督碼n碼率等于碼率等于n有可能檢測(cè)偶數(shù)個(gè)錯(cuò)碼有可能檢測(cè)偶數(shù)個(gè)錯(cuò)碼n適合檢測(cè)突發(fā)錯(cuò)碼適合檢測(cè)突發(fā)錯(cuò)碼 n能夠糾正部分錯(cuò)碼。能夠糾正部分錯(cuò)碼。 例如：例如： 一行中有奇數(shù)個(gè)錯(cuò)碼一行中有奇數(shù)個(gè)錯(cuò)碼nmnmnk)1()1(只對(duì)構(gòu)成矩形四角的錯(cuò)碼無(wú)法檢測(cè)。只對(duì)構(gòu)成矩形四角的錯(cuò)碼無(wú)法檢測(cè)。24基本概念基本概念n代數(shù)碼代數(shù)碼 利用利用代數(shù)關(guān)系代數(shù)關(guān)系式產(chǎn)生監(jiān)督位的編碼式產(chǎn)生監(jiān)督位的編碼(不一定線性不一定線性)n線性分組碼線性分組碼 代數(shù)碼的一種，其監(jiān)督位和信息位的關(guān)系代數(shù)碼的一種，其監(jiān)督位和信息位的

25、關(guān)系 由由線性代數(shù)方程線性代數(shù)方程決定決定n漢明碼漢明碼 一種能夠糾正一個(gè)錯(cuò)碼的線性分組碼一種能夠糾正一個(gè)錯(cuò)碼的線性分組碼n校正子：校正子：在偶數(shù)監(jiān)督碼中，計(jì)算在偶數(shù)監(jiān)督碼中，計(jì)算實(shí)際上就是計(jì)算實(shí)際上就是計(jì)算并檢驗(yàn)并檢驗(yàn)S是否等于是否等于0。 S稱(chēng)為校正子稱(chēng)為校正子。n監(jiān)督關(guān)系式：監(jiān)督關(guān)系式：0021aaann021aaaSnn021aaaSnn25糾錯(cuò)基本原理糾錯(cuò)基本原理n 中，中，S只有兩種取值，故只能表示只有兩種取值，故只能表示有錯(cuò)和無(wú)錯(cuò)，而不能進(jìn)一步指明錯(cuò)碼的位置。有錯(cuò)和無(wú)錯(cuò)，而不能進(jìn)一步指明錯(cuò)碼的位置。 n若此若此碼組長(zhǎng)度增加一位碼組長(zhǎng)度增加一位，則能增加一個(gè)監(jiān)督關(guān)系式。這樣，則能增

26、加一個(gè)監(jiān)督關(guān)系式。這樣，就能就能得到兩個(gè)校正子得到兩個(gè)校正子。兩個(gè)校正子的可能取值有。兩個(gè)校正子的可能取值有4種組合，種組合，即即00，01，10，11，故，故能表示能表示4種不同的信息種不同的信息。若用其中。若用其中一一種組合表示無(wú)錯(cuò)碼種組合表示無(wú)錯(cuò)碼，則還有，則還有其它其它3種種組合組合可以用于可以用于指明一個(gè)指明一個(gè)錯(cuò)碼的錯(cuò)碼的3種不同位置。種不同位置。 從而可以有從而可以有糾錯(cuò)糾錯(cuò)能力。能力。n一般而言，一般而言，若有若有 r 個(gè)監(jiān)督關(guān)系式，則個(gè)監(jiān)督關(guān)系式，則 r 個(gè)校正子可以指明個(gè)校正子可以指明一個(gè)錯(cuò)碼的一個(gè)錯(cuò)碼的 (2r 1) 個(gè)不同位置。個(gè)不同位置。 n當(dāng)校正子可以指明的錯(cuò)碼位置

27、數(shù)目等于或大于碼組長(zhǎng)度當(dāng)校正子可以指明的錯(cuò)碼位置數(shù)目等于或大于碼組長(zhǎng)度n時(shí)，才能夠時(shí)，才能夠糾正碼組中任何一個(gè)位置上的錯(cuò)碼糾正碼組中任何一個(gè)位置上的錯(cuò)碼，即，即要求要求021aaaSnn1212rknrr或26漢明碼漢明碼n例例：要求設(shè)計(jì)一個(gè)能夠糾正：要求設(shè)計(jì)一個(gè)能夠糾正1個(gè)錯(cuò)碼的分組碼個(gè)錯(cuò)碼的分組碼(n, k)，給定，給定的碼組中有的碼組中有4個(gè)信息位，即個(gè)信息位，即k = 4。 p由由要求監(jiān)督位數(shù)要求監(jiān)督位數(shù)r 3。若取。若取r = 3，則，則n = k + r = 7?，F(xiàn)在用。現(xiàn)在用a6 a5 a4 a3 a2 a1 a0表示這表示這7個(gè)碼元，用個(gè)碼元，用S1 S2 S3表示校正子，表示

28、校正子，則這則這3個(gè)校正子恰好能夠指明個(gè)校正子恰好能夠指明23 1 = 7個(gè)錯(cuò)碼的位置。個(gè)錯(cuò)碼的位置。p若規(guī)定校正子和錯(cuò)碼位置的關(guān)系如下表，則僅當(dāng)在若規(guī)定校正子和錯(cuò)碼位置的關(guān)系如下表，則僅當(dāng)在a6 a5 a4 a2位置上有錯(cuò)碼時(shí)，校正子位置上有錯(cuò)碼時(shí)，校正子S1的值才等于的值才等于1；否則；否則S1的值為零。這就意味著的值為零。這就意味著a6 a5 a4 a2四個(gè)碼元構(gòu)成偶數(shù)監(jiān)督四個(gè)碼元構(gòu)成偶數(shù)監(jiān)督關(guān)系：關(guān)系：p同理，有同理，有S1 S2 S3錯(cuò)碼位置S1 S2 S3錯(cuò)碼位置001a0101a4010a1110a5100a2111a6011a3000無(wú)錯(cuò)碼1212rknrr或24561aaaa

29、S13562aaaaS03463aaaaS27p在編碼時(shí)，信息位在編碼時(shí)，信息位a6 a5 a4 a3的值由輸入信號(hào)決定，它們的值由輸入信號(hào)決定，它們是隨機(jī)的。監(jiān)督位是隨機(jī)的。監(jiān)督位a2 a1 a0是按監(jiān)督關(guān)系確定的，應(yīng)該保是按監(jiān)督關(guān)系確定的，應(yīng)該保證上列證上列3式中的式中的校正子等于校正子等于0，即有，即有給定信息位后，為了給定信息位后，為了計(jì)算監(jiān)督位計(jì)算監(jiān)督位，上式可，上式可以改寫(xiě)為以改寫(xiě)為按照上式計(jì)算結(jié)果如按照上式計(jì)算結(jié)果如 右表所示右表所示000034613562456aaaaaaaaaaaa346035614562aaaaaaaaaaaa信息位a6 a5 a4 a3監(jiān)督位a2 a1

30、a0信息位a6 a5 a4 a3監(jiān)督位a2 a1 a0000000010001110001011100110000101011010010001111010110010100110110000101011011101010011001111101000111000111111128p在接收端解碼時(shí)，對(duì)于每個(gè)接收碼組，先按式在接收端解碼時(shí)，對(duì)于每個(gè)接收碼組，先按式計(jì)算出校正子計(jì)算出校正子S1，S2和和S3，然后按照表，然后按照表判斷錯(cuò)碼的位置。判斷錯(cuò)碼的位置。 例：若接收碼組為例：若接收碼組為0000011，則按上三式計(jì)算得到：，則按上三式計(jì)算得到：S1 = 0，S2 = 1，S3 = 1。這樣

31、，由上表可知，錯(cuò)碼位置在。這樣，由上表可知，錯(cuò)碼位置在a3。正確的碼組是正確的碼組是000101124561aaaaS13562aaaaS03463aaaaSS1 S2 S3錯(cuò)碼位置S1 S2 S3錯(cuò)碼位置001a0101a4010a1110a5100a2111a6011a3000無(wú)錯(cuò)碼29p上例中的漢明碼是上例中的漢明碼是(7, 4)碼，其最小碼距碼，其最小碼距d0 = 3。 由式由式 可知，此碼能夠檢測(cè)可知，此碼能夠檢測(cè)2個(gè)錯(cuò)碼，或糾正個(gè)錯(cuò)碼，或糾正1個(gè)錯(cuò)碼。個(gè)錯(cuò)碼。n漢明碼的碼率：漢明碼的碼率：當(dāng)當(dāng)r (或或n)很大時(shí)，上式趨近于很大時(shí)，上式趨近于1。所以漢明碼是一種高效編。所以漢明碼是

32、一種高效編碼。碼。10 ed120 td1212rrrnk30分組碼的一般原理分組碼的一般原理n線性分組碼的監(jiān)督位和信息位的關(guān)系線性分組碼的監(jiān)督位和信息位的關(guān)系 可以改寫(xiě)為可以改寫(xiě)為上式中，已經(jīng)將上式中，已經(jīng)將“ ”簡(jiǎn)寫(xiě)成簡(jiǎn)寫(xiě)成“+”。 000034613562456aaaaaaaaaaaa010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa31n監(jiān)督矩陣監(jiān)督矩陣上式可以寫(xiě)成矩陣形式：上式可以寫(xiě)成矩陣形式： （模（模2） 將上式簡(jiǎn)寫(xiě)為將上式簡(jiǎn)寫(xiě)為HAT = 0T 或或AHT = 001001101001010110

33、0010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa0001011001110101011101000123456aaaaaaa32 HAT = 0T 式中，式中， 稱(chēng)為稱(chēng)為監(jiān)督矩陣監(jiān)督矩陣 n監(jiān)督矩陣的性質(zhì)監(jiān)督矩陣的性質(zhì)p監(jiān)督矩陣監(jiān)督矩陣H確定碼組中的信息位和監(jiān)督位的關(guān)系。確定碼組中的信息位和監(jiān)督位的關(guān)系。pH 的行數(shù)就是監(jiān)督關(guān)系式的數(shù)目，即監(jiān)督位數(shù)的行數(shù)就是監(jiān)督關(guān)系式的數(shù)目，即監(jiān)督位數(shù) r 。pH 的每行中的每行中“1”的位置表示相應(yīng)的碼元參與監(jiān)督關(guān)系。的位置表示相應(yīng)的碼元參與監(jiān)督關(guān)系。p H 可以分成兩部分，例如可以分成兩部分，例如 典型監(jiān)督

34、矩陣典型監(jiān)督矩陣 式中，式中，P 為為r k階矩陣，階矩陣，Ir為為 r r 階單位方陣。階單位方陣。 101100111010101110100HrPIH001101101011011001110A = a6 a5 a4 a3 a2 a1 a0 0 = 00033pH 矩陣的各行應(yīng)該是線性無(wú)關(guān)的，否則將得不到矩陣的各行應(yīng)該是線性無(wú)關(guān)的，否則將得不到 r 個(gè)線個(gè)線性無(wú)關(guān)的監(jiān)督關(guān)系式。性無(wú)關(guān)的監(jiān)督關(guān)系式。p若一個(gè)矩陣能寫(xiě)成典型陣形式若一個(gè)矩陣能寫(xiě)成典型陣形式P Ir，則其各行一定是，則其各行一定是線性無(wú)關(guān)的。線性無(wú)關(guān)的。n生成矩陣生成矩陣p例：例： 可以寫(xiě)為可以寫(xiě)為上式兩端分別轉(zhuǎn)置后，可以變成上

35、式兩端分別轉(zhuǎn)置后，可以變成式中，式中，Q為為k r 階矩陣，是階矩陣，是P的轉(zhuǎn)置，即的轉(zhuǎn)置，即 Q = PT3456012101111011110aaaaaaa346035614562aaaaaaaaaaaaQ34563456012011101110111aaaaaaaaaaa34將將Q的左邊加上一個(gè)的左邊加上一個(gè)k階單位方陣，稱(chēng)為生成矩陣：階單位方陣，稱(chēng)為生成矩陣： 生成矩陣生成矩陣 G稱(chēng)為生成矩陣，因?yàn)榭梢杂盟a(chǎn)生整個(gè)碼組稱(chēng)為生成矩陣，因?yàn)榭梢杂盟a(chǎn)生整個(gè)碼組A，即有，即有p生成矩陣的性質(zhì)生成矩陣的性質(zhì)n具有IkQ形式的生成矩陣稱(chēng)為典型生成矩陣典型生成矩陣。n由典型生成矩陣得出的碼組A中，

36、信息位的位置不變，監(jiān)督位附加于其后。這種形式的碼組稱(chēng)為系統(tǒng)系統(tǒng)碼碼。 n矩陣G的各行也必須是線性無(wú)關(guān)的。n如果已有k個(gè)線性無(wú)關(guān)的碼組，則可以將其用來(lái)作為生成矩陣G，并由它生成其余碼組。0110001101001011001001111000QGkI IG34560123456aaaaaaaaaaaA35n錯(cuò)誤圖樣錯(cuò)誤圖樣設(shè)：發(fā)送碼組設(shè)：發(fā)送碼組A是一個(gè)是一個(gè)n列的行矩陣：列的行矩陣：接收碼組是一個(gè)接收碼組是一個(gè)n列的行矩陣列的行矩陣B： 令接收碼組和發(fā)送碼組之差為令接收碼組和發(fā)送碼組之差為E就是錯(cuò)碼的行矩陣就是錯(cuò)碼的行矩陣 稱(chēng)為錯(cuò)誤圖樣稱(chēng)為錯(cuò)誤圖樣 式中，式中， (i = 0, 1, , n-

37、1)若若ei = 0，表示該碼元未錯(cuò)；若，表示該碼元未錯(cuò)；若ei = 1，表示該碼元為錯(cuò)碼。，表示該碼元為錯(cuò)碼。 0121aaaaAnn0121bbbbBnnB A = E (模2)0121eeeeEnniiiiiababe當(dāng)當(dāng), 1, 036n校正子矩陣校正子矩陣 B A = E 可以改寫(xiě)成可以改寫(xiě)成 B = A + E上式表示發(fā)送碼組上式表示發(fā)送碼組A與錯(cuò)碼矩陣與錯(cuò)碼矩陣E之和等于接收碼組之和等于接收碼組B。 例如，例如， 若發(fā)送碼組若發(fā)送碼組A = 1 0 0 0 1 1 1， 錯(cuò)碼矩陣錯(cuò)碼矩陣E = 0 0 0 0 1 0 0， 則則 接收碼組接收碼組B = 1 0 0 0 0 1 1

38、。 在在接收端解碼時(shí)接收端解碼時(shí)，將接收碼組，將接收碼組B代入式代入式AHT = 0中中A的位置進(jìn)行計(jì)算。若接收碼組中無(wú)錯(cuò)碼，則的位置進(jìn)行計(jì)算。若接收碼組中無(wú)錯(cuò)碼，則B = A。代。代入后，該式仍成立，即有入后，該式仍成立，即有BH T = 0 （無(wú)錯(cuò)）（無(wú)錯(cuò)）只有當(dāng)錯(cuò)碼未超出檢測(cè)能力時(shí)，上式才不成立。只有當(dāng)錯(cuò)碼未超出檢測(cè)能力時(shí)，上式才不成立。 假設(shè)，這時(shí)該式的右端等于假設(shè)，這時(shí)該式的右端等于S，即有，即有BH T = S將將B = A + E 代入上式，得到代入上式，得到:S = (A + E) H T = AH T + EH T37S = (A + E) H T = AH T + EH T

39、上式右端第一項(xiàng)等于上式右端第一項(xiàng)等于0，所以，所以 S = EH T 校正子矩陣校正子矩陣當(dāng)當(dāng)H 確定后，上式中確定后，上式中S只與只與E 有關(guān)，而與有關(guān)，而與A 無(wú)關(guān)。無(wú)關(guān)。 這意味著，這意味著，S 和錯(cuò)碼和錯(cuò)碼E 之間有確定的線性變換關(guān)系。之間有確定的線性變換關(guān)系。 若若S 和和E 有一一對(duì)應(yīng)關(guān)系，有一一對(duì)應(yīng)關(guān)系，則則S 將能代表錯(cuò)碼位置將能代表錯(cuò)碼位置。例：例：38n線性碼的封閉性：線性碼的封閉性：若若A1和和A2是一種線性編碼中的兩個(gè)碼組，是一種線性編碼中的兩個(gè)碼組，則則(A1+A2)仍是其中一個(gè)碼組仍是其中一個(gè)碼組。 證若證若A1和和A2是兩個(gè)碼組，則有：是兩個(gè)碼組，則有：A1HT

40、= 0, A2HT = 0 將上兩式相加，得出將上兩式相加，得出A1HT + A2HT = (A1 + A2 ) HT = 0 所以所以(A1 + A2)也是一個(gè)碼組。也是一個(gè)碼組。 由于線性碼具有封閉性，所以由于線性碼具有封閉性，所以?xún)蓚€(gè)碼組兩個(gè)碼組(A1和和A2)之間之間的距離（即對(duì)應(yīng)位不同的數(shù)目）必定是另一個(gè)碼組的距離（即對(duì)應(yīng)位不同的數(shù)目）必定是另一個(gè)碼組(A1 + A2)的重量（即的重量（即“1”的數(shù)目）。的數(shù)目）。因此，因此，碼的最小距離就是碼的碼的最小距離就是碼的最小重量最小重量（除全（除全“0”碼組外）。碼組外）。3910.6.1 循環(huán)碼的概念：循環(huán)碼的概念： 循環(huán)性是指任一碼組

41、循環(huán)一位后仍然是該編碼中的一個(gè)碼組。循環(huán)性是指任一碼組循環(huán)一位后仍然是該編碼中的一個(gè)碼組。例：一種例：一種(7, 3)循環(huán)碼的全部碼組如下循環(huán)碼的全部碼組如下 表中第表中第2碼組向右移一位即得到第碼組向右移一位即得到第5碼組；第碼組；第5碼組向右移碼組向右移一位即得到第一位即得到第7碼組。碼組。 碼組編號(hào)信息位監(jiān)督位碼組編號(hào)信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4A3a2a1a0100000005100101120010111610111003010111071100101401110018111001040一般情況一般情況 若若(an-1 an-2 a0)是循環(huán)碼的一個(gè)碼組，則循

42、環(huán)移位后的碼是循環(huán)碼的一個(gè)碼組，則循環(huán)移位后的碼組：組： (an-2 an-3 a0 an-1)(an-3 an-4 an-1 an-2) (a0 an-1 a2 a1) 仍然是該編碼中的碼組。仍然是該編碼中的碼組。多項(xiàng)式表示法多項(xiàng)式表示法一個(gè)長(zhǎng)度為一個(gè)長(zhǎng)度為n的碼組的碼組(an-1 an-2 a0)可以表示成可以表示成 上式中上式中x 的值沒(méi)有任何意義，僅用它的冪代表碼元的位置。的值沒(méi)有任何意義，僅用它的冪代表碼元的位置。例例：碼組：碼組1 1 0 0 1 0 1可以表示為可以表示為 012211)(axaxaxaxTnnnn11010011)(25623456xxxxxxxxxxT4110

43、.6.2 循環(huán)碼的運(yùn)算循環(huán)碼的運(yùn)算 整數(shù)的按模運(yùn)算整數(shù)的按模運(yùn)算在整數(shù)運(yùn)算中，有模在整數(shù)運(yùn)算中，有模n運(yùn)算。例如，在模運(yùn)算。例如，在模2運(yùn)算中，有運(yùn)算中，有1 + 1 = 2 0 (模模2)， 1 + 2 = 3 1 (模模2)， 2 3 = 6 0 (模模2) 等等。等等。 一般說(shuō)來(lái)，若一個(gè)一般說(shuō)來(lái)，若一個(gè)整數(shù)整數(shù)m可以表示為可以表示為式中，式中，Q為整數(shù)，則為整數(shù)，則在模在模n運(yùn)算下，有運(yùn)算下，有m p (模模n) 所以，在模所以，在模n運(yùn)算下，一個(gè)整數(shù)運(yùn)算下，一個(gè)整數(shù)m等于它被等于它被n除得的余數(shù)。除得的余數(shù)。npnpQnm,42碼多項(xiàng)式的按模運(yùn)算碼多項(xiàng)式的按模運(yùn)算 若任意一個(gè)多項(xiàng)式若任

44、意一個(gè)多項(xiàng)式F(x)被一個(gè)被一個(gè)n次多項(xiàng)式次多項(xiàng)式N(x)除，得到商除，得到商式式Q(x)和一個(gè)次數(shù)小于和一個(gè)次數(shù)小于n的余式的余式R(x)，即，即則在按模則在按模N(x)運(yùn)算下，有運(yùn)算下，有這時(shí)，這時(shí)，碼多項(xiàng)式系數(shù)仍按模碼多項(xiàng)式系數(shù)仍按模2運(yùn)算運(yùn)算。 例例1：x3被被(x3 + 1)除，得到余項(xiàng)除，得到余項(xiàng)1，即，即 例例2：因?yàn)橐驗(yàn)閤x3 + 1 x4 +x2 + 1x4 + x x2 +x +1 在模在模2運(yùn)算中加法和減法一樣。運(yùn)算中加法和減法一樣。)()()()(xRxQxNxF）（模)()()(xNxRxF）（模)x(x1 133）（模) 1(113224xxxxx43循環(huán)碼的數(shù)學(xué)表

45、示法循環(huán)碼的數(shù)學(xué)表示法 在循環(huán)碼中，設(shè)在循環(huán)碼中，設(shè)T(x)是一個(gè)長(zhǎng)度為是一個(gè)長(zhǎng)度為n的碼組，若的碼組，若則則T (x)也是該編碼中的一個(gè)碼組。也是該編碼中的一個(gè)碼組。 證證 設(shè)一循環(huán)碼為設(shè)一循環(huán)碼為 （略）（略） 則有則有 上式中的上式中的T (x) 正是碼組正是碼組T (x)向左循環(huán)移位向左循環(huán)移位 i 次的結(jié)果。次的結(jié)果。例例： 一循環(huán)碼為一循環(huán)碼為1100101，即，即 若給定若給定 i = 3，則有，則有 上式對(duì)應(yīng)的碼組為上式對(duì)應(yīng)的碼組為0101110，它正是，它正是T(x)向左移向左移3位的結(jié)果。位的結(jié)果。結(jié)論：一個(gè)長(zhǎng)為結(jié)論：一個(gè)長(zhǎng)為n的循環(huán)碼必定為按模的循環(huán)碼必定為按模(xn +

46、 1)運(yùn)算的一個(gè)余式運(yùn)算的一個(gè)余式。 ）（模) 1()()(nixxTxTx012211)(axaxaxaxTnnnn)()(1102211011112211xTaxaxaxaxaxaxaxaxaxaxTxininininniniinininninni1)(256xxxxT）（模)x(xxxxxxxx)x(Tx172353589344循環(huán)碼的生成循環(huán)碼的生成 n有了生成矩陣有了生成矩陣G，就可以由，就可以由k個(gè)信息位得出整個(gè)碼組：個(gè)信息位得出整個(gè)碼組：例：例：式中，式中，生成矩陣生成矩陣G的每一行都是一個(gè)碼組。的每一行都是一個(gè)碼組。n因此，若能找到因此，若能找到 k 個(gè)已知的碼組，就能構(gòu)成矩陣

47、個(gè)已知的碼組，就能構(gòu)成矩陣G。如前。如前所述，這所述，這k個(gè)已知碼組必須是線性不相關(guān)的。個(gè)已知碼組必須是線性不相關(guān)的。n在循環(huán)碼中，一個(gè)在循環(huán)碼中，一個(gè)(n, k)碼有碼有2k個(gè)不同的碼組。若個(gè)不同的碼組。若用用g(x)表表示其中前示其中前(k-1)位皆為位皆為“0”的碼組，則的碼組，則g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是碼組，而且這都是碼組，而且這k個(gè)碼組是線性無(wú)關(guān)的。個(gè)碼組是線性無(wú)關(guān)的。因因此它們可以用來(lái)構(gòu)成此循環(huán)碼的生成矩陣此它們可以用來(lái)構(gòu)成此循環(huán)碼的生成矩陣G。G34560123456aaaaaaaaaaaA01100011010010110010011110

48、00QGkI I45n在循環(huán)碼中在循環(huán)碼中除全除全“0”碼組外，再?zèng)]有連續(xù)碼組外，再?zèng)]有連續(xù)k位均為位均為“0”的碼的碼組組。否則，在經(jīng)過(guò)若干次循環(huán)移位后將得到。否則，在經(jīng)過(guò)若干次循環(huán)移位后將得到k位信息位全為位信息位全為“0”，但監(jiān)督位不全為，但監(jiān)督位不全為“0”的一個(gè)碼組。這在線性碼中顯的一個(gè)碼組。這在線性碼中顯然是不可能的。然是不可能的。n因此，因此，g(x)必須是一個(gè)常數(shù)項(xiàng)不為必須是一個(gè)常數(shù)項(xiàng)不為“0”的的(n - k)次多項(xiàng)式次多項(xiàng)式，而且這個(gè)而且這個(gè)g(x)還是這種還是這種(n, k)碼中碼中次數(shù)為次數(shù)為(n k)的唯一一個(gè)的唯一一個(gè)多項(xiàng)式。多項(xiàng)式。因?yàn)槿绻袃蓚€(gè)，則由碼的封閉性，

49、把這兩個(gè)相因?yàn)槿绻袃蓚€(gè)，則由碼的封閉性，把這兩個(gè)相加也應(yīng)該是一個(gè)碼組，且此碼組多項(xiàng)式的次數(shù)將小于加也應(yīng)該是一個(gè)碼組，且此碼組多項(xiàng)式的次數(shù)將小于(n k)，即連續(xù)，即連續(xù)“0”的個(gè)數(shù)多于的個(gè)數(shù)多于(k 1)。顯然，這是與前面的結(jié)。顯然，這是與前面的結(jié)論矛盾的。論矛盾的。n我們我們稱(chēng)這唯一的稱(chēng)這唯一的(n k)次多項(xiàng)式次多項(xiàng)式g(x)為碼的生成多項(xiàng)式為碼的生成多項(xiàng)式。一。一旦確定了旦確定了g(x)，則整個(gè)，則整個(gè)(n, k)循環(huán)碼就被確定了。循環(huán)碼就被確定了。46n因此，因此，循環(huán)碼的生成矩陣循環(huán)碼的生成矩陣G可以寫(xiě)成可以寫(xiě)成n例：例：上表中的編碼為上表中的編碼為(7, 3)循環(huán)碼，循環(huán)碼，n

50、= 7, k = 3, n k = 4，其中唯一的一個(gè)其中唯一的一個(gè)(n k) = 4次碼多項(xiàng)式代表的碼組是第二碼次碼多項(xiàng)式代表的碼組是第二碼組組0010111，與它對(duì)應(yīng)的碼多項(xiàng)式，即生成多項(xiàng)式，為，與它對(duì)應(yīng)的碼多項(xiàng)式，即生成多項(xiàng)式，為g(x) = x4 + x2 + x + 1。 )()()()()(21xgxxgxgxxgxxkkG碼組編號(hào)信息位監(jiān)督位碼組編號(hào)信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4A3a2a1a0100000005100101120010111610111003010111071100101401110018111001047g(x) = x4 + x2 +

51、x + 1 即即 “1 0 1 1 1”將此將此g(x)代入前面的矩陣，得到代入前面的矩陣，得到 或或上式不符合上式不符合G = IkQ形式，所以它不是典型生成矩陣。但形式，所以它不是典型生成矩陣。但它經(jīng)過(guò)線性變換后，不難化成典型陣。它經(jīng)過(guò)線性變換后，不難化成典型陣。此此循環(huán)碼組的多項(xiàng)式循環(huán)碼組的多項(xiàng)式表示式表示式T(x)： 上式表明，上式表明，所有碼多項(xiàng)式所有碼多項(xiàng)式T(x)都能夠被都能夠被g(x)整除整除，而且，而且任意一個(gè)次數(shù)不大于任意一個(gè)次數(shù)不大于(k 1)的多項(xiàng)式乘的多項(xiàng)式乘g(x)都是碼多項(xiàng)式。都是碼多項(xiàng)式。 )()()()(2xgxxgxgxxG00101110101110101

52、1100)(xG)()()()()()()()()()(452645262456456xgaxaxaxgaxxgaxgxaxgxxgxgxaaaxaaaxTG48尋求尋求碼生成多項(xiàng)式碼生成多項(xiàng)式 因?yàn)槿我庖粋€(gè)循環(huán)碼因?yàn)槿我庖粋€(gè)循環(huán)碼T(x)都是都是g(x)的倍式，故它可以寫(xiě)成的倍式，故它可以寫(xiě)成T(x) = h(x) g(x)而生成多項(xiàng)式而生成多項(xiàng)式g(x)本身也是一個(gè)碼組，即有本身也是一個(gè)碼組，即有 T (x) = g(x)由于碼組由于碼組T (x)是一個(gè)是一個(gè)(n k)次多項(xiàng)式，故次多項(xiàng)式，故xk T (x)是一個(gè)是一個(gè)n次次多項(xiàng)式。由多項(xiàng)式。由可知，可知，xk T (x)在模在模(xn

53、+ 1)運(yùn)算下也是一個(gè)碼組，所以有運(yùn)算下也是一個(gè)碼組，所以有上式左端分子和分母都是上式左端分子和分母都是n次多項(xiàng)式，故相除的商式次多項(xiàng)式，故相除的商式Q(x) = 1。因此，上式可以寫(xiě)成因此，上式可以寫(xiě)成）（模) 1()()(nixxTxTx1)()(1)(nnkxxTxQxxTx)() 1()(xTxxTxnk49將將 T(x) = h(x) g(x) 和和 T (x) = g(x) 代入代入化簡(jiǎn)后，得到化簡(jiǎn)后，得到上式表明，上式表明，生成多項(xiàng)式生成多項(xiàng)式g(x)應(yīng)該是應(yīng)該是(xn + 1)的一個(gè)因子的一個(gè)因子。例例：(x7 + 1)可以分解為可以分解為為了求出為了求出(7, 3)循環(huán)碼的生

54、成多項(xiàng)式循環(huán)碼的生成多項(xiàng)式 g(x)，需要從上式，需要從上式中找到一個(gè)中找到一個(gè)(n k) = 4次的因子。這樣的因子有兩個(gè)，即次的因子。這樣的因子有兩個(gè)，即以上兩式都可以作為生成多項(xiàng)式。以上兩式都可以作為生成多項(xiàng)式。 選用的生成多項(xiàng)式不同，產(chǎn)生出的循環(huán)碼碼組也不同。選用的生成多項(xiàng)式不同，產(chǎn)生出的循環(huán)碼碼組也不同。 )() 1()(xTxxTxnk)()(1xhxxgxkn) 1)(1)(1(13237xxxxxx1) 1)(1(2423xxxxxx1) 1)(1(2343xxxxxx5010.6.3 循環(huán)碼的編碼方法循環(huán)碼的編碼方法用用xn-k乘乘m(x)。這一運(yùn)算實(shí)際上是在信息碼后附加上。

55、這一運(yùn)算實(shí)際上是在信息碼后附加上(n k)個(gè)個(gè)“0”。例如，信息碼為。例如，信息碼為110，它寫(xiě)成多項(xiàng)式為，它寫(xiě)成多項(xiàng)式為m(x) = x2 + x。當(dāng)當(dāng)n k = 7 3 =4時(shí)，時(shí)，xn-k m(x) = x4 (x2 +x) = x6 +x5，它表示，它表示碼組碼組1100000。用用g(x)除除xn-k m(x)，得到商，得到商Q(x)和余式和余式r(x)，即有，即有例：若選定例：若選定g(x) = x4 + x2 + x + 1，則有，則有 上式是用碼多項(xiàng)式表示的運(yùn)算。它和下式等效：上式是用碼多項(xiàng)式表示的運(yùn)算。它和下式等效：編出的碼組編出的碼組T(x)為：為：T(x) = xn-k

56、m(x) +r(x)在上例中，在上例中，T(x) = 1100000 + 101 = 1100101 )()()()()(xgxrxQxgxmxkn11) 1(1)()(24222456xxxxxxxxxxxxgxmxkn101111011111011111000005110.6.4 循環(huán)碼的解碼方法循環(huán)碼的解碼方法在檢錯(cuò)時(shí)：當(dāng)在檢錯(cuò)時(shí)：當(dāng)接收碼組沒(méi)有錯(cuò)碼時(shí)接收碼組沒(méi)有錯(cuò)碼時(shí)，接收碼組，接收碼組R(x)必定能被必定能被g(x)整除，即下式整除，即下式中中余項(xiàng)余項(xiàng)r(x)應(yīng)為零應(yīng)為零；否則，有誤碼否則，有誤碼。n當(dāng)接收碼組中的錯(cuò)碼數(shù)量過(guò)多，超出了編碼的檢錯(cuò)能力當(dāng)接收碼組中的錯(cuò)碼數(shù)量過(guò)多，超出了編

57、碼的檢錯(cuò)能力時(shí)，有錯(cuò)碼的接收碼組也可能被時(shí)，有錯(cuò)碼的接收碼組也可能被g(x)整除。這時(shí)，錯(cuò)碼就整除。這時(shí)，錯(cuò)碼就不能檢出了。不能檢出了。 在糾錯(cuò)時(shí)：在糾錯(cuò)時(shí)：n用生成多項(xiàng)式用生成多項(xiàng)式g(x)除接收碼組除接收碼組R(x)，得出余式，得出余式r(x)。n按照余式按照余式r(x)，用查表的方法或計(jì)算方法得出錯(cuò)誤圖樣用查表的方法或計(jì)算方法得出錯(cuò)誤圖樣E(x)。n從從R(x)中減去中減去E(x)，便得到已經(jīng)糾正錯(cuò)碼的原發(fā)送碼組，便得到已經(jīng)糾正錯(cuò)碼的原發(fā)送碼組T(x)。)(/)()()(/)(xgxrxQxgxR5210.6.5 截短循環(huán)碼截短循環(huán)碼截短目的：截短目的： 在設(shè)計(jì)時(shí)，通常信息位數(shù)在設(shè)計(jì)時(shí)，

58、通常信息位數(shù)k、碼長(zhǎng)、碼長(zhǎng)n和糾錯(cuò)能力都是預(yù)先和糾錯(cuò)能力都是預(yù)先給定的。但是，并不一定有恰好滿足這些條件的循環(huán)碼存在。給定的。但是，并不一定有恰好滿足這些條件的循環(huán)碼存在。故采用截短碼長(zhǎng)，得出滿足要求的編碼。故采用截短碼長(zhǎng)，得出滿足要求的編碼。截短方法截短方法： 一個(gè)給定的一個(gè)給定的(n, k)循環(huán)碼，共有循環(huán)碼，共有2k種碼組，將其中前種碼組，將其中前i (0 i k) 個(gè)信息位全為個(gè)信息位全為“0”的碼組取出，它變成僅有的碼組取出，它變成僅有2k-i種碼組。種碼組。然后刪去這然后刪去這 i 位全位全“0”的信息位，最終得到一個(gè)的信息位，最終得到一個(gè) (n i，k i)的線性碼。將這種碼稱(chēng)為

59、截短循環(huán)碼。的線性碼。將這種碼稱(chēng)為截短循環(huán)碼。 截短循環(huán)碼與截短前的循環(huán)碼至少具有相同的糾錯(cuò)能力，并截短循環(huán)碼與截短前的循環(huán)碼至少具有相同的糾錯(cuò)能力，并且截短循環(huán)碼的編解碼方法仍和截短前的方法一樣。且截短循環(huán)碼的編解碼方法仍和截短前的方法一樣。 例：要求構(gòu)造一個(gè)能夠糾正例：要求構(gòu)造一個(gè)能夠糾正1位錯(cuò)碼的位錯(cuò)碼的(13, 9)碼。碼。 這時(shí)可以由這時(shí)可以由(15, 11)循環(huán)碼的循環(huán)碼的211種碼組中選出前兩個(gè)信息種碼組中選出前兩個(gè)信息位均為位均為“0”的碼組，構(gòu)成一個(gè)新的碼組集合。然后在發(fā)送時(shí)的碼組，構(gòu)成一個(gè)新的碼組集合。然后在發(fā)送時(shí)不發(fā)送這兩位不發(fā)送這兩位“0”。于是發(fā)送碼組成為。于是發(fā)送碼

60、組成為(13, 9)截短循環(huán)碼。截短循環(huán)碼。 5310.6.6 BCH碼碼BCH碼是能夠糾正多個(gè)隨機(jī)錯(cuò)碼的循環(huán)碼。碼是能夠糾正多個(gè)隨機(jī)錯(cuò)碼的循環(huán)碼。 BCH碼分為兩類(lèi)：本原碼分為兩類(lèi)：本原BCH碼和非本原碼和非本原BCH碼。碼。 n本原本原BCH碼：碼長(zhǎng)碼：碼長(zhǎng)n = 2m 1 (m 3，任意正整數(shù)，任意正整數(shù))，它的生，它的生成多項(xiàng)式成多項(xiàng)式g(x)中含有最高次數(shù)為中含有最高次數(shù)為m次的本原多項(xiàng)式；次的本原多項(xiàng)式；n非本原非本原BCH碼：碼長(zhǎng)碼：碼長(zhǎng)n是是(2m 1)的一個(gè)因子，它的生成多的一個(gè)因子，它的生成多項(xiàng)式項(xiàng)式g(x)中不含有最高次數(shù)為中不含有最高次數(shù)為m的本原多項(xiàng)式。的本原多項(xiàng)式。