信息論基礎(chǔ)理論與應(yīng)用第三版(傅祖蕓)-第9章-講義

1、第第9 9章章 信道的糾錯編碼信道的糾錯編碼 差錯控制的基本形式差錯控制的基本形式糾錯碼分類及其基本概念糾錯碼分類及其基本概念線性分組碼線性分組碼* *循環(huán)碼循環(huán)碼* *卷積碼卷積碼 香農(nóng)第二定理指出，只要信息傳輸率小于信道容量，通香農(nóng)第二定理指出，只要信息傳輸率小于信道容量，通過適當(dāng)?shù)木幾g碼方法，就能以任意小的錯誤概率傳輸信息。過適當(dāng)?shù)木幾g碼方法，就能以任意小的錯誤概率傳輸信息。但從實際工程看，并沒有指出具體的編譯碼方法。但從實際工程看，并沒有指出具體的編譯碼方法。 這正是這正是信道糾錯編碼信道糾錯編碼要解決的問題。要解決的問題。 香農(nóng)第二定理指出，在信道中以信息傳輸率香農(nóng)第二定理指出，在信

2、道中以信息傳輸率R R小于信道容量小于信道容量條件下，使差錯概率盡可能小的條件下，使差錯概率盡可能小的信道編譯碼原則信道編譯碼原則是：是：編碼原則編碼原則： 在在n n次擴(kuò)展信道輸入符號序列中選取次擴(kuò)展信道輸入符號序列中選取MM個作為碼字構(gòu)成一組個作為碼字構(gòu)成一組碼碼C C，并盡量使選取的，并盡量使選取的MM個碼字中兩兩不相同碼字的漢明距離盡個碼字中兩兩不相同碼字的漢明距離盡可能地大；可能地大；譯碼原則譯碼原則： 當(dāng)收到符號序列后，翻譯成與之漢明距離最近的碼字（最大當(dāng)收到符號序列后，翻譯成與之漢明距離最近的碼字（最大似然準(zhǔn)則）。似然準(zhǔn)則）。 幾十年來，基于香農(nóng)編碼定理和以上編譯碼原則，科技工作

3、幾十年來，基于香農(nóng)編碼定理和以上編譯碼原則，科技工作者們開發(fā)了很多具有者們開發(fā)了很多具有糾錯能力的信道編碼糾錯能力的信道編碼，如線性分組碼、循環(huán)，如線性分組碼、循環(huán)碼、碼、BCHBCH碼、卷積碼、碼、卷積碼、TCMTCM碼、碼、TuoboTuobo碼等，在通信系統(tǒng)中得到碼等，在通信系統(tǒng)中得到了廣泛應(yīng)用。了廣泛應(yīng)用。9 9.1 .1 差錯控制的基本形式差錯控制的基本形式 現(xiàn)代數(shù)字通信系統(tǒng)中，利用檢錯和糾錯的編碼技術(shù)，現(xiàn)代數(shù)字通信系統(tǒng)中，利用檢錯和糾錯的編碼技術(shù)，使得信道編譯碼具備一定的差錯控制能力。主要方式有：使得信道編譯碼具備一定的差錯控制能力。主要方式有：1 1、前向糾錯、前向糾錯(FEC)

4、(FEC)方式方式： 發(fā)送端信道編碼器將信息碼組編成具有一定發(fā)送端信道編碼器將信息碼組編成具有一定糾錯能力糾錯能力的碼。的碼。 接收端信道譯碼器對接收碼字譯碼，若傳輸中產(chǎn)生的差錯接收端信道譯碼器對接收碼字譯碼，若傳輸中產(chǎn)生的差錯數(shù)目在碼的糾錯能力之內(nèi)，譯碼器對差錯進(jìn)行數(shù)目在碼的糾錯能力之內(nèi)，譯碼器對差錯進(jìn)行定位定位并加以并加以糾正糾正。發(fā)送端發(fā)送端接收接收端端可檢錯糾錯的碼可檢錯糾錯的碼FECFEC檢錯、糾錯檢錯、糾錯nFEC FEC 特點特點單向控制，不需要反饋信道；時延小，實時性好。單向控制，不需要反饋信道；時延小，實時性好。為適應(yīng)較差信道，冗余碼元多，編碼效率低，譯碼設(shè)備復(fù)雜。為適應(yīng)較差

5、信道，冗余碼元多，編碼效率低，譯碼設(shè)備復(fù)雜。有一定的糾錯范圍限制。有一定的糾錯范圍限制。 適用于容錯能力強(qiáng)的語音、圖像傳輸；不適合容錯能力弱的適用于容錯能力強(qiáng)的語音、圖像傳輸；不適合容錯能力弱的數(shù)據(jù)通信網(wǎng)。數(shù)據(jù)通信網(wǎng)。2 2、反饋重發(fā)、反饋重發(fā)(ARQ)(ARQ)方式（檢錯重發(fā)方式）：方式（檢錯重發(fā)方式）： 發(fā)送端發(fā)送端發(fā)送的是能夠發(fā)送的是能夠發(fā)現(xiàn)（檢測）發(fā)現(xiàn)（檢測）錯誤的碼；錯誤的碼； 接收端接收端收到信道傳輸來的碼后，譯碼器依據(jù)該碼編碼規(guī)則，收到信道傳輸來的碼后，譯碼器依據(jù)該碼編碼規(guī)則，判決出當(dāng)前碼字傳輸是否出錯，并把判決出當(dāng)前碼字傳輸是否出錯，并把判決結(jié)果判決結(jié)果（應(yīng)答信號）反（應(yīng)答信號

6、）反饋至發(fā)送端。發(fā)送端把接收端認(rèn)為有錯的信息饋至發(fā)送端。發(fā)送端把接收端認(rèn)為有錯的信息重新發(fā)出重新發(fā)出，直到，直到接收端認(rèn)為正確為止。接收端認(rèn)為正確為止。發(fā)送端發(fā)送端接收端接收端可檢錯的碼可檢錯的碼ARQARQ應(yīng)答信號應(yīng)答信號檢錯、不糾錯檢錯、不糾錯nARQARQ特點特點需要雙向控制和反饋信道。需要雙向控制和反饋信道。系統(tǒng)的控制設(shè)備和存儲設(shè)備復(fù)雜，但編譯碼設(shè)備較簡單。系統(tǒng)的控制設(shè)備和存儲設(shè)備復(fù)雜，但編譯碼設(shè)備較簡單。接收端檢錯能力、系統(tǒng)糾錯能力強(qiáng)，可大大降低系統(tǒng)誤碼率。接收端檢錯能力、系統(tǒng)糾錯能力強(qiáng)，可大大降低系統(tǒng)誤碼率。具有自適應(yīng)性。但若重發(fā)頻繁，將使效率降低，甚至系統(tǒng)阻塞，具有自適應(yīng)性。但若

7、重發(fā)頻繁，將使效率降低，甚至系統(tǒng)阻塞，使得連續(xù)性和實時性變差。使得連續(xù)性和實時性變差。 在短波、有線干擾情況復(fù)雜的信道，在計算機(jī)網(wǎng)絡(luò)、分組在短波、有線干擾情況復(fù)雜的信道，在計算機(jī)網(wǎng)絡(luò)、分組交換網(wǎng)、衛(wèi)星通信、移動通信中廣泛應(yīng)用。交換網(wǎng)、衛(wèi)星通信、移動通信中廣泛應(yīng)用。3 3、混合糾錯、混合糾錯(HEC)(HEC)方式：方式：n 前向糾錯前向糾錯FEC+FEC+反饋重發(fā)反饋重發(fā)ARQARQ 發(fā)送端發(fā)送的是兼有發(fā)送端發(fā)送的是兼有檢錯和糾錯能力檢錯和糾錯能力的碼；接收端收到碼的碼；接收端收到碼字后，首先檢測錯誤情況。當(dāng)差錯在碼的糾錯能力范圍內(nèi)，就字后，首先檢測錯誤情況。當(dāng)差錯在碼的糾錯能力范圍內(nèi)，就自動

8、糾錯；當(dāng)差錯很多已經(jīng)超出了糾錯能力，但能夠檢測到錯自動糾錯；當(dāng)差錯很多已經(jīng)超出了糾錯能力，但能夠檢測到錯誤，接收端就通過反饋信道，請求重發(fā)。誤，接收端就通過反饋信道，請求重發(fā)。發(fā)送端發(fā)送端接收端接收端可檢錯和糾錯的碼可檢錯和糾錯的碼HECHEC應(yīng)答信號應(yīng)答信號檢錯、糾錯檢錯、糾錯nHECHEC的特點的特點總體性能介于總體性能介于FECFEC和和ARQARQ之間，誤碼率低，但需要反饋信道。之間，誤碼率低，但需要反饋信道。實時性和連續(xù)性好。實時性和連續(xù)性好。設(shè)備不太復(fù)雜，應(yīng)用廣泛。設(shè)備不太復(fù)雜，應(yīng)用廣泛。4 4、信息反饋、信息反饋(IRQ)(IRQ)方式方式( (回程校驗方式回程校驗方式) ):

9、: 接收端接收端收到信道傳輸來的碼后，全部由反饋信道發(fā)回發(fā)送端；收到信道傳輸來的碼后，全部由反饋信道發(fā)回發(fā)送端；發(fā)送端發(fā)送端將發(fā)送的碼與反饋回的碼進(jìn)行比較，發(fā)現(xiàn)錯誤后，把出將發(fā)送的碼與反饋回的碼進(jìn)行比較，發(fā)現(xiàn)錯誤后，把出錯的碼再次重發(fā)，直到接收端認(rèn)為正確為止。錯的碼再次重發(fā)，直到接收端認(rèn)為正確為止。發(fā)送端發(fā)送端接收端接收端消息（不編碼）消息（不編碼）IRQIRQ消息消息不檢錯、糾錯不檢錯、糾錯nIRQIRQ特點：特點：需要雙向控制，需要反饋信道。需要雙向控制，需要反饋信道。系統(tǒng)的控制設(shè)備和存儲設(shè)備相對復(fù)雜。系統(tǒng)的控制設(shè)備和存儲設(shè)備相對復(fù)雜。無需編譯碼設(shè)備，接收端不具備檢、糾錯能力強(qiáng)，整體系統(tǒng)糾

10、無需編譯碼設(shè)備，接收端不具備檢、糾錯能力強(qiáng)，整體系統(tǒng)糾錯能力強(qiáng)，可大大降低整個系統(tǒng)誤碼率。錯能力強(qiáng)，可大大降低整個系統(tǒng)誤碼率。具有自適應(yīng)性，但若重發(fā)頻繁，將使傳輸效率降低，甚至系統(tǒng)具有自適應(yīng)性，但若重發(fā)頻繁，將使傳輸效率降低，甚至系統(tǒng)阻塞，使得連續(xù)性和實時性變差。阻塞，使得連續(xù)性和實時性變差。5 5、檢錯刪除：、檢錯刪除： 接收端接收端發(fā)現(xiàn)錯碼后，立即將其刪除。發(fā)現(xiàn)錯碼后，立即將其刪除。 適用在發(fā)送碼元中有大量多余度，刪除部分接收碼元不影響應(yīng)適用在發(fā)送碼元中有大量多余度，刪除部分接收碼元不影響應(yīng)用之處。用之處。 6 6、差錯隱藏：、差錯隱藏： 在某些應(yīng)用領(lǐng)域，如音樂、語音、圖像、視頻等領(lǐng)域，在

11、某些應(yīng)用領(lǐng)域，如音樂、語音、圖像、視頻等領(lǐng)域，有差錯或損失的部分?jǐn)?shù)據(jù)對人的主觀感受影響不大，此時，可有差錯或損失的部分?jǐn)?shù)據(jù)對人的主觀感受影響不大，此時，可根據(jù)已接收的數(shù)據(jù)采用內(nèi)插或外推的技術(shù)，得到滿足應(yīng)用的輸根據(jù)已接收的數(shù)據(jù)采用內(nèi)插或外推的技術(shù)，得到滿足應(yīng)用的輸出數(shù)據(jù)。出數(shù)據(jù)。9 9.2 .2 糾錯碼分類糾錯碼分類1 1、糾錯碼的分類：、糾錯碼的分類：n按糾正錯誤的類型分類：按糾正錯誤的類型分類：糾隨機(jī)差錯碼：糾隨機(jī)差錯碼：無記憶信道中，噪聲隨機(jī)獨立地影響每個無記憶信道中，噪聲隨機(jī)獨立地影響每個碼元，造成了隨機(jī)差錯；碼元，造成了隨機(jī)差錯；糾突發(fā)差錯碼：糾突發(fā)差錯碼：有記憶信道中，突發(fā)噪聲可造成

12、突發(fā)性的有記憶信道中，突發(fā)噪聲可造成突發(fā)性的成群差錯（如太陽黑子、雷電等引起）成群差錯（如太陽黑子、雷電等引起）。糾混合差錯碼糾混合差錯碼n按應(yīng)用目的分類：按應(yīng)用目的分類：檢錯碼檢錯碼只能檢測錯誤是否存在。只能檢測錯誤是否存在。糾錯碼糾錯碼能夠檢測錯誤，并能夠自動糾正錯誤。能夠檢測錯誤，并能夠自動糾正錯誤。糾刪碼糾刪碼能夠糾正刪除（丟失）了的信息。能夠糾正刪除（丟失）了的信息。n按碼元取值分類：按碼元取值分類：二元糾錯碼二元糾錯碼目前最常用模式目前最常用模式多元糾錯碼多元糾錯碼n按碼的結(jié)構(gòu)中對信息序列的處理方式分類：按碼的結(jié)構(gòu)中對信息序列的處理方式分類：分組碼（分組碼（n,kn,k）將信息序列

13、每將信息序列每k k位分組，再增加入位分組，再增加入r=n-r=n-k k 個冗余碼元（校驗元），校驗元只由本組個冗余碼元（校驗元），校驗元只由本組k k個信息元按個信息元按照一定規(guī)律產(chǎn)生，與其他信息組無關(guān)。照一定規(guī)律產(chǎn)生，與其他信息組無關(guān)。卷積碼（卷積碼（n,kn,k0 0,L ,L）將信息序列每將信息序列每 k k0 0 位分組，編碼器輸位分組，編碼器輸出該段的出該段的r=n-kr=n-k0 0個與本組和前個與本組和前L L組信息元相關(guān)的校驗元，組信息元相關(guān)的校驗元，得到得到n n長的碼字。長的碼字。n按碼的數(shù)學(xué)結(jié)構(gòu)中校驗元與信息元關(guān)系分類：按碼的數(shù)學(xué)結(jié)構(gòu)中校驗元與信息元關(guān)系分類：線性碼線

14、性碼線性關(guān)系，如線性方程組線性關(guān)系，如線性方程組非線性碼非線性碼非線性關(guān)系非線性關(guān)系n按碼的是否具有循環(huán)性分類：按碼的是否具有循環(huán)性分類：循環(huán)碼循環(huán)碼分組碼中任一碼字的碼元經(jīng)過循環(huán)移位后，分組碼中任一碼字的碼元經(jīng)過循環(huán)移位后，仍是本碼中的碼字。仍是本碼中的碼字。非循環(huán)碼非循環(huán)碼至少有一個碼字經(jīng)循環(huán)移位后，不再是本至少有一個碼字經(jīng)循環(huán)移位后，不再是本碼中的碼字。碼中的碼字。n按構(gòu)造碼的數(shù)學(xué)理論分類：按構(gòu)造碼的數(shù)學(xué)理論分類：代數(shù)碼代數(shù)碼近世代數(shù)，比較完善，如線性分組碼。近世代數(shù)，比較完善，如線性分組碼。幾何碼幾何碼投影幾何學(xué)投影幾何學(xué)算術(shù)碼算術(shù)碼數(shù)論，高等算術(shù)數(shù)論，高等算術(shù)組合碼組合碼排列組合，數(shù)

15、論排列組合，數(shù)論 實際的碼可能同時分別具備以上某些特征，比如：某一糾錯碼實際的碼可能同時分別具備以上某些特征，比如：某一糾錯碼可以同時是線性碼、分組碼、循環(huán)碼、糾隨機(jī)差錯碼、二元碼、代可以同時是線性碼、分組碼、循環(huán)碼、糾隨機(jī)差錯碼、二元碼、代數(shù)碼等。數(shù)碼等。9 9.3 .3 糾錯碼的概念及其糾錯能力糾錯碼的概念及其糾錯能力信息序列信息序列碼字序列碼字序列接收序列接收序列譯碼后信息序列譯碼后信息序列噪聲源噪聲源E E 錯誤圖樣錯誤圖樣 對編碼器的輸入信息序列，每對編碼器的輸入信息序列，每k k個信息符號分成個信息符號分成信息組信息組： m m= =（m mk-1k-1, ,m mk-2k-2,m

16、 m0 0），），m mi i為為信息元信息元（i=0,1,k-1i=0,1,k-1）。）。（在（在q q元數(shù)字通信系統(tǒng)中，共有元數(shù)字通信系統(tǒng)中，共有 種信息組。）種信息組。）碼字碼字： 為了糾錯，編碼器按一定規(guī)則增加產(chǎn)生為了糾錯，編碼器按一定規(guī)則增加產(chǎn)生r r個多余符個多余符號，形成長度為號，形成長度為 n=k+r n=k+r 的序列的序列： C=(cC=(cn-1n-1,c ,cn-2n-2,c,c0 0), ), c ci i為為碼元碼元（i=0,1,n-1i=0,1,n-1） 校驗元校驗元：增加的增加的 r=n-k r=n-k 位碼元位碼元。 n n：碼長；：碼長；k k：信息組長度；

17、：信息組長度； r r：校驗元的位長。：校驗元的位長。kqn1 1、信息元、校驗元、碼字：、信息元、校驗元、碼字：n碼碼C C中的碼字個數(shù)（中的碼字個數(shù)（k k為信息位數(shù)）：為信息位數(shù)）：n（n,kn,k）分組碼：）分組碼：編碼器輸出為編碼器輸出為 個碼字組成的序列；個碼字組成的序列；許用碼字許用碼字： 種碼符號序列中，取出種碼符號序列中，取出 個作為分組碼個作為分組碼的碼字。的碼字。禁用碼字禁用碼字：其余：其余 種碼符號序列。種碼符號序列。n卷積碼（卷積碼（n,kn,k0 0,L ,L）: :編碼器輸出的校驗元不僅由本組信息元有關(guān)，編碼器輸出的校驗元不僅由本組信息元有關(guān)，也與其前面若干段的信

18、息組所確定。也與其前面若干段的信息組所確定。kqkqnqkqknqq k k個信息位個信息位r r個監(jiān)督位個監(jiān)督位a an n-1 -1a an n-2 -2. .a ar ra ar r-1 -1a an n-2 -2. .a a0 0t t碼長碼長 n n = = k k + + r r分組碼的結(jié)構(gòu)分組碼的結(jié)構(gòu)n2 2、碼字的漢明重量：、碼字的漢明重量：漢明距離漢明距離D(CD(C1 1,C,C2 2) )：對應(yīng)位置上不同碼元的個數(shù)。：對應(yīng)位置上不同碼元的個數(shù)。碼的最小距離碼的最小距離：d dminmin, d(C), d(C)漢明重量（漢明勢）漢明重量（漢明勢）：碼字中非零碼元的個數(shù)：碼

19、字中非零碼元的個數(shù) W(C)W(C)。 對對2 2元碼，漢明重量為碼字中的元碼，漢明重量為碼字中的“1”1”的個數(shù)。因此，二的個數(shù)。因此，二元碼字的漢明重量和漢明距離為：元碼字的漢明重量和漢明距離為： 1 , 0)(10iniiccCW)(),(jijiCCWCCD模模2 2加，若對應(yīng)位不同加，若對應(yīng)位不同則為則為1 1；相同則為；相同則為0 0。其重量即為不相同的其重量即為不相同的總位數(shù)，也就是兩個總位數(shù)，也就是兩個碼字的漢明距離。碼字的漢明距離。n3 3、錯誤圖樣：、錯誤圖樣： 碼字序列通過信道傳輸送入譯碼器之前，由于信道的碼字序列通過信道傳輸送入譯碼器之前，由于信道的 噪聲干擾，使得接收

20、序列中某些碼元發(fā)生差錯，可用噪聲干擾，使得接收序列中某些碼元發(fā)生差錯，可用錯誤錯誤圖樣圖樣（差錯圖樣差錯圖樣）定量描述：）定量描述： E=(eE=(en-1n-1e en-2n-2ee1 1e e0 0)=C)=CR R 二元數(shù)字通信系統(tǒng)中，碼元傳輸錯誤圖樣：二元數(shù)字通信系統(tǒng)中，碼元傳輸錯誤圖樣： E=(eE=(en-1n-1e en-2n-2ee1 1e e0 0), e), ei i =0,1 ,i=0,1,n-1=0,1 ,i=0,1,n-1 若若 e ei i =0 =0 ， 第第i i位碼元無差錯；位碼元無差錯； 若若 e ei i =1 =1 ， 第第i i位碼元發(fā)生差錯；位碼元發(fā)

21、生差錯； 差錯關(guān)系差錯關(guān)系： 接收序列接收序列 = = 許用碼字許用碼字 + + 錯誤圖樣錯誤圖樣 R=(rR=(rn-1n-1r rn-2n-2rr1 1r r0 0), r), ri i =0,1 ,i=0,1,n-1=0,1 ,i=0,1,n-1 接收序列長度接收序列長度 = = 碼字長度碼字長度 = = 錯誤圖樣長度錯誤圖樣長度 = n= n差錯類型：差錯類型：n隨機(jī)差錯隨機(jī)差錯是相互獨立的、不相關(guān)，存在這種差錯是相互獨立的、不相關(guān)，存在這種差錯的信道是無記憶信道或隨機(jī)信道；的信道是無記憶信道或隨機(jī)信道；n突發(fā)差錯突發(fā)差錯指成串出現(xiàn)的錯誤指成串出現(xiàn)的錯誤, ,錯誤與錯誤間有相關(guān)錯誤與錯

22、誤間有相關(guān)性性, ,一個差錯往往要影響到后面一串碼元。一個差錯往往要影響到后面一串碼元。RCEERCECR,例例 發(fā)送碼字發(fā)送碼字 C= 010110111, C= 010110111, 接收序列接收序列 R= 001110011,R= 001110011,錯誤圖樣錯誤圖樣 E=C+R= 011000100E=C+R= 011000100 若為若為隨機(jī)差錯隨機(jī)差錯，錯誤碼元為：，錯誤碼元為： 2 2，3 3，7 7，錯誤數(shù)量，錯誤數(shù)量=W(E)=3=W(E)=3； 若為若為突發(fā)差錯突發(fā)差錯，錯誤碼元串長度為：，錯誤碼元串長度為：6 6； 出錯范圍：從錯誤圖樣出錯范圍：從錯誤圖樣E E中的第一個

23、中的第一個1 1到最后一個到最后一個1 1， 其其錯誤串中的錯誤串中的0 0表示該位碼元未發(fā)生錯誤。表示該位碼元未發(fā)生錯誤。 nBSCBSC（二元無記憶對稱信道）的錯誤圖樣的出現(xiàn)概率（二元無記憶對稱信道）的錯誤圖樣的出現(xiàn)概率 設(shè)設(shè)p p為錯誤概率為錯誤概率(1),(1),則則n n次無記憶擴(kuò)展信道中，次無記憶擴(kuò)展信道中，隨機(jī)差錯隨機(jī)差錯的某錯誤圖樣的某錯誤圖樣E E的出現(xiàn)概率為：的出現(xiàn)概率為： )()()(EWEWnppEP0 0位差錯（全對）：位差錯（全對）： W(EW(E0 0)=0)=0，1 1位隨機(jī)差錯：位隨機(jī)差錯： W(EW(E1 1)=1, )=1, 2 2位隨機(jī)差錯：位隨機(jī)差錯：

24、 W(EW(E2 2)=2,)=2,e e位隨機(jī)差錯：位隨機(jī)差錯： W(EW(Ee e)=e,)=e,n n位差錯（全錯）位差錯（全錯） W(EW(En n)=n,)=n,0nC1nC2nCenCnnCppEPn 11)(npEP)(0222)(ppEPneeneppEP)(nnpEP)(差錯圖樣數(shù)差錯圖樣數(shù)概率概率錯誤圖樣的錯誤圖樣的總數(shù)總數(shù)：nnnnnnnCCCCC2.e210nnnnpppppp.221)(.)(.)()()(210neEPEPEPEPEP 發(fā)生發(fā)生多位錯誤的概率多位錯誤的概率小于小于較少位數(shù)較少位數(shù)隨機(jī)錯誤的概率。隨機(jī)錯誤的概率。因此，因此，無記憶信道無記憶信道中，一般

25、優(yōu)先糾正較少位數(shù)的隨機(jī)錯中，一般優(yōu)先糾正較少位數(shù)的隨機(jī)錯誤，如誤，如1-21-2位，此時的誤碼率就可下降幾個數(shù)量級。位，此時的誤碼率就可下降幾個數(shù)量級。錯誤圖樣出現(xiàn)的錯誤圖樣出現(xiàn)的概率關(guān)系概率關(guān)系（p1p1）：）：n4 4、分組碼的糾錯能力與碼最小距離的關(guān)系、分組碼的糾錯能力與碼最小距離的關(guān)系 一般地，分組碼的碼間最小距離一般地，分組碼的碼間最小距離 dmin dmin 越大，意味著任越大，意味著任意碼字間的差別越大，則碼的檢、糾錯能力越強(qiáng)。意碼字間的差別越大，則碼的檢、糾錯能力越強(qiáng)。檢錯能力檢錯能力： 如果一個分組碼能檢出如果一個分組碼能檢出總位數(shù)總位數(shù)e e 個碼元個碼元的任何錯誤的任何錯

26、誤圖樣，稱碼的圖樣，稱碼的檢錯能力為檢錯能力為 e e。糾錯能力糾錯能力： 如果分組碼能糾正如果分組碼能糾正總位數(shù)總位數(shù)t t 個碼元個碼元的任意錯誤圖樣，的任意錯誤圖樣，稱碼的稱碼的糾錯能力為糾錯能力為 t t。例例 重復(fù)碼（重復(fù)碼（3 3，1 1）為：（）為：（000000，111111），最小碼間距為），最小碼間距為3 3。 兩個碼字在傳輸后發(fā)生兩個碼字在傳輸后發(fā)生1 1位錯誤的接收序列形成兩個互不相交位錯誤的接收序列形成兩個互不相交的子集，按照的子集，按照最小距離譯碼準(zhǔn)則最小距離譯碼準(zhǔn)則，就能糾正，就能糾正1 1位隨機(jī)錯誤。若發(fā)位隨機(jī)錯誤。若發(fā)生生2-32-3位錯誤，則接收序列進(jìn)入另一

27、個子集內(nèi)，無法糾正。位錯誤，則接收序列進(jìn)入另一個子集內(nèi)，無法糾正。(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a1n定理定理：對于一個（：對于一個（n,kn,k）分組碼）分組碼C C，最小距離為，最小距離為d dminmin，則：，則：若能檢測（發(fā)現(xiàn)）若能檢測（發(fā)現(xiàn)）e e個隨機(jī)錯誤，則要求個隨機(jī)錯誤，則要求 d dminmin e+1e+1 ; ; 或：可檢測出任意小于等于或：可檢測出任意小于等于 e = d e = dminmin1 1個隨機(jī)差錯；個隨機(jī)差錯； 若能糾正若能糾正 t t 個隨機(jī)錯誤，則要求個隨機(jī)錯誤

28、，則要求 d dminmin 2t+12t+1 ; ; 或：可糾正任意小于等于或：可糾正任意小于等于 t= INT (d t= INT (dminmin-1) / 2-1) / 2個隨機(jī)差錯；個隨機(jī)差錯； 若能糾正若能糾正 t t 個隨機(jī)錯誤，同時能檢測個隨機(jī)錯誤，同時能檢測e t e t 個隨機(jī)錯誤，則個隨機(jī)錯誤，則要求：要求： d dminmin t+e+1t+e+1 。 設(shè)設(shè)V,UV,U為距離最小的兩個許用碼字。若某碼字傳輸發(fā)生錯誤，按為距離最小的兩個許用碼字。若某碼字傳輸發(fā)生錯誤，按最小距離準(zhǔn)則譯碼，為了檢測最小距離準(zhǔn)則譯碼，為了檢測 R=U+ER=U+E： 須須d dminmin e

29、+1 e+1，否則，會發(fā)生碼字譯碼混淆，如，否則，會發(fā)生碼字譯碼混淆，如 R+E =V R+E =V 。eVUdmin dmin=4,碼距和檢錯能力關(guān)系示意圖t tVUdmin圖 dmin=5,碼距和糾錯能力關(guān)系示意圖 設(shè)設(shè)V,UV,U為距離最小的兩個許用碼字。若某碼字傳輸發(fā)生錯誤，按為距離最小的兩個許用碼字。若某碼字傳輸發(fā)生錯誤，按最小距離準(zhǔn)則譯碼最小距離準(zhǔn)則譯碼. . 若若 R=V+ER=V+E，WW（E E）= t= t，則若，則若 dmin 2t+1 , dmin 2t+1 , 則可能譯碼為則可能譯碼為 U U。錯誤！錯誤！ 當(dāng)當(dāng) dmin 2t+1dmin 2t+1，D D（R R，

30、V V） D k k) ) 碼字，其中碼字，其中 ( (n nk k) ) 個附加碼元是由信息碼個附加碼元是由信息碼元的元的線性運算線性運算產(chǎn)生的。產(chǎn)生的。n對于二元碼，信息碼組長對于二元碼，信息碼組長 k k 位，有位，有 2 2k k 個不同的信息碼組，則有個不同的信息碼組，則有 2 2k k 個個碼字與它們一一對應(yīng)。碼字與它們一一對應(yīng)。2 2、 一致監(jiān)督（校驗）方程一致監(jiān)督（校驗）方程n編碼方法：已知信息碼組編碼方法：已知信息碼組k k位信息位，按預(yù)定規(guī)則生成位信息位，按預(yù)定規(guī)則生成 r r 個監(jiān)督個監(jiān)督（校驗）碼元，與信息位一起構(gòu)成碼字。（校驗）碼元，與信息位一起構(gòu)成碼字。n要求：每個

31、監(jiān)督元是其中某些信息元的運算結(jié)果。要求：每個監(jiān)督元是其中某些信息元的運算結(jié)果。 （以下僅討論二元碼）（以下僅討論二元碼）例例：k k=3, =3, r r=4=4，構(gòu)成，構(gòu)成 (7,3) (7,3) 線性分組碼線性分組碼。設(shè)碼字為。設(shè)碼字為( (C C6 6, ,C C5 5, ,C C4 4, ,C C3 3, ,C C2 2, ,C C1 1, ,C C0 0) )其中，其中，C C6 6, ,C C5 5, ,C C4 4為信息元，為信息元，C C3 3, ,C C2 2, ,C C1 1, ,C C0 0為監(jiān)督元，碼元取為監(jiān)督元，碼元取0 0或或1 1。監(jiān)督元可按下面方程組計算監(jiān)督元可

32、按下面方程組計算3642654165054(6.2.1)CCCCCCCCCCCCCn一致監(jiān)督（校驗）方程一致監(jiān)督（校驗）方程 由確定信息元得到監(jiān)督元規(guī)則的一組方程。由于所有碼字都按由確定信息元得到監(jiān)督元規(guī)則的一組方程。由于所有碼字都按同一規(guī)則同一規(guī)則確定，又稱為一致監(jiān)督（校驗）方程。確定，又稱為一致監(jiān)督（校驗）方程。n線性分組碼線性分組碼 若一致監(jiān)督方程是若一致監(jiān)督方程是線性線性的，監(jiān)督元和信息元之間是線性運算關(guān)的，監(jiān)督元和信息元之間是線性運算關(guān)系，所以由監(jiān)督方程所確定的分組碼是系，所以由監(jiān)督方程所確定的分組碼是線性分組碼線性分組碼。3642654165054CCCCCCCCCCCCC0000

33、0000000000000000451562456346CCCCCCCCCCCCC前例前例3 3、 一致監(jiān)督（校驗）矩陣一致監(jiān)督（校驗）矩陣 為了運算方便，為了運算方便，可可將監(jiān)督方程寫將監(jiān)督方程寫成矩陣形式。成矩陣形式。前例前例：6543210654321010110000111010001100010001100010C0000010110001110100H11000100110001CCCCCCCCCCCCCC 令00TTTCHHCor00000000000000000000451562456346CCCCCCCCCCCCC推廣：推廣：一般情況，對一般情況，對 ( (n n, ,k k

34、) ) 線性分組碼，每個碼字中的線性分組碼，每個碼字中的 r r( (r r= =n nk k) ) 個個監(jiān)督元與信息元之間的關(guān)系可由如下監(jiān)督元與信息元之間的關(guān)系可由如下r r * * n n 階階線性方程組確定：線性方程組確定：) 6 . 2 . 6(000022110222212101212111ChChChChChChChChChrnnrnrnnnnnnrnrrnnhhhhhhhhhH.212212111211則：則：00TTTCHorHC021.cccCnnT令：令：.0121hhhhHnnn若用若用h hi i (i=n-1,n-2,1,0) (i=n-1,n-2,1,0) 表示表示

35、H H矩陣中的矩陣中的列矢量列矢量，則，則H H可寫為：可寫為：0.00111111hchchchcnnnnnH H矩陣的矩陣的每一行元素每一行元素是線性方程組中一個方程的系數(shù)，由它來是線性方程組中一個方程的系數(shù)，由它來唯一確定每一個校驗元。因此，唯一確定每一個校驗元。因此，H H中中每一行必須是線性無關(guān)每一行必須是線性無關(guān)的，的，且必定有：且必定有：r =nr =nk k 行。行。0TCH4 4、 生成矩陣生成矩陣 根據(jù)（根據(jù)（n,kn,k）線性分組碼的一致監(jiān)督方程出發(fā)，將）線性分組碼的一致監(jiān)督方程出發(fā)，將信息組信信息組信息位息位與與生成的碼字生成的碼字之間的生成關(guān)系用矩陣來表示，就可得到之

36、間的生成關(guān)系用矩陣來表示，就可得到生生成矩陣。成矩陣。例例 前例中，前例中，3642654165054(6.2.1)CCCCCCCCCCCCC041526,mcmcmc0101210122023041526mmcmmcmmmcmmcmcmcmc0120123456110011111101100010001mmmccccccc1011100111001001110010120123456mmmccccccc生成矩陣生成矩陣G G1 1其各行為碼字，互不相關(guān)。其各行為碼字，互不相關(guān)。其他碼字為此三個碼字的線性其他碼字為此三個碼字的線性組合方式生成。組合方式生成。n推廣推廣：對一般：對一般 ( (n

37、 n, ,k k) ) 線性分組碼，設(shè)有一組線性分組碼，設(shè)有一組k k個個線性獨立的碼字，線性獨立的碼字，由此一組線性獨立的碼字以行向量構(gòu)成的矩陣，稱為線性分組由此一組線性獨立的碼字以行向量構(gòu)成的矩陣，稱為線性分組碼的碼的生成矩陣生成矩陣G G（k k* *n n階）：階）：kkkknknknnnngggggCgggggCgggggC).(.).().(0121220212212211011211110121202122121011211121.kkknknnnnnkgggggggggggggggG滿足：滿足：)2,.,2 , 1 (,),(kiiiiknCGmC碼nG G中每一行及其線性組合

38、都是中每一行及其線性組合都是許用碼字許用碼字，故有：，故有：階階零零矩矩陣陣。為為)(, 0,0knkGHorHGTTT0 線性分組碼的所有碼字都可由其生成矩陣或一致校驗矩陣求線性分組碼的所有碼字都可由其生成矩陣或一致校驗矩陣求得。當(dāng)已知得。當(dāng)已知G G、H H中的一個，就可求另一個。中的一個，就可求另一個。n系統(tǒng)碼：系統(tǒng)碼： 信息元以不變形式出現(xiàn)在碼字的任意信息元以不變形式出現(xiàn)在碼字的任意k k位上。位上。n標(biāo)準(zhǔn)生成矩陣：標(biāo)準(zhǔn)生成矩陣： 生成矩陣能把信息元保留在各碼字的生成矩陣能把信息元保留在各碼字的最左邊最左邊k k位位上。上。|)(knkkPIG|)(knTknkIPH0TGH 因此，因

39、此，標(biāo)準(zhǔn)系統(tǒng)生成矩陣標(biāo)準(zhǔn)系統(tǒng)生成矩陣G G應(yīng)滿足如下形式：應(yīng)滿足如下形式：其與其與H H矩陣之間的轉(zhuǎn)換關(guān)系：矩陣之間的轉(zhuǎn)換關(guān)系：若非標(biāo)準(zhǔn)系統(tǒng)碼，則若非標(biāo)準(zhǔn)系統(tǒng)碼，則G G與與H H之間元素需要由方程組確定。之間元素需要由方程組確定。( (略略) )生成矩陣之間的關(guān)系生成矩陣之間的關(guān)系 對于二元（對于二元（n,kn,k）分組碼，在）分組碼，在2 2k k個碼字中，個碼字中，k k個個獨立碼字組獨立碼字組不不止一個。對于同一碼，選擇不同的獨立碼字組構(gòu)成生成矩陣止一個。對于同一碼，選擇不同的獨立碼字組構(gòu)成生成矩陣G G也也不相同。但經(jīng)過若干次不相同。但經(jīng)過若干次初等變換初等變換，可變成等價的，可變成

40、等價的標(biāo)準(zhǔn)生成矩陣標(biāo)準(zhǔn)生成矩陣。例例 一個二元（一個二元（7 7，3 3）碼）碼, ,生成矩陣為：生成矩陣為：0010111110010101110012G生成的碼字為：生成的碼字為：碼字集合完全相同。碼字集合完全相同。 但生成矩陣但生成矩陣G1G1、G2G2選取了不同的獨立碼字構(gòu)成。選取了不同的獨立碼字構(gòu)成。生成矩陣生成矩陣可以經(jīng)過初等行變換可以經(jīng)過初等行變換得到其得到其標(biāo)準(zhǔn)標(biāo)準(zhǔn)生成矩陣生成矩陣。比較：生成矩陣比較：生成矩陣G G2 2產(chǎn)生的碼（非系統(tǒng)碼）產(chǎn)生的碼（非系統(tǒng)碼）比較：生成矩陣比較：生成矩陣G G1 1產(chǎn)生的碼（系統(tǒng)碼）產(chǎn)生的碼（系統(tǒng)碼）101110011100100111001

41、1G0010111110010101110012G2 2行行+3+3行行=2 2行行1 1行行+2+2行行=3 3行行14332|101110011100100111001GPIG標(biāo)準(zhǔn)生成矩陣標(biāo)準(zhǔn)生成矩陣5 5、線性分組碼性質(zhì)與糾錯能力、線性分組碼性質(zhì)與糾錯能力1 1）（）（n,kn,k）線性分組碼由生成矩陣）線性分組碼由生成矩陣G G或校驗矩陣或校驗矩陣H H確定。確定。 它們滿足：它們滿足：階矩陣。階矩陣。為為或或)(0,0knkGHHGTTT0 ; 2 2）封閉性。（）封閉性。（n,kn,k）碼中任意兩個碼字之和仍為許用碼字，）碼中任意兩個碼字之和仍為許用碼字，即：即：),(,),(,k

42、nCCCknCCkjiji則若字。）線性分組碼的許用碼為（即knCHCHCHCHCHCCHCHCTTjTiTkTjiTjTi,00)(, 0, 0kk3 3）含有零碼字。）含有零碼字。 n n位長的零矢量為（位長的零矢量為（n,kn,k）線性分組碼的許用碼字。）線性分組碼的許用碼字。（因為滿足（因為滿足 ）00TTHCH4 4）所有許用碼字可由其中）所有許用碼字可由其中k k個獨立碼字（基底）線性組合而成。個獨立碼字（基底）線性組合而成。 在在 個許用碼字中，個許用碼字中，k k個獨立許用碼字不止一組。它們可個獨立許用碼字不止一組。它們可構(gòu)成生成矩陣構(gòu)成生成矩陣G G。k25 5）碼的最小距離

43、等于非零碼字的最小重量。即：）碼的最小距離等于非零碼字的最小重量。即：0),(, )(minminiiiCknCCWd因為：因為：),(, 0)(min),(, )(min),(, ),(minminknCCCWknCCCCCCWknCCCCCCDdkkkjijijijijiji，封閉性定理定理 設(shè)（設(shè)（n,kn,k）線性分組碼）線性分組碼C C的校驗矩陣為的校驗矩陣為H H，則碼的最小距離為，則碼的最小距離為d d的的充要條件充要條件為：為：H H中任意中任意d-1d-1個列向量線性無關(guān)，且有個列向量線性無關(guān)，且有d d個列向量個列向量線性相關(guān)。線性相關(guān)。（提供了構(gòu)造最小距離為（提供了構(gòu)造最

44、小距離為d d的線性分組碼的思路。）的線性分組碼的思路。）1000110010001100101110001101Hn任何任何3 3列相加均非列相加均非0 0，n而最少的相關(guān)列數(shù)為而最少的相關(guān)列數(shù)為4 4：如：從右向左第如：從右向左第0 0，1 1，2 2，5 5之和為之和為0 0，相關(guān)。相關(guān)。故，碼最小距離為：故，碼最小距離為：4 4由此可知：由此可知：u當(dāng)所有當(dāng)所有列向量相同列向量相同，而排列位置不同的，而排列位置不同的H H 矩陣所對應(yīng)的分組碼，矩陣所對應(yīng)的分組碼，具有相同的具有相同的最小距離最小距離，則它們在糾錯能力和碼率上等價。，則它們在糾錯能力和碼率上等價。u對于分組碼來說，由于可

45、以進(jìn)行對于分組碼來說，由于可以進(jìn)行初等變換初等變換進(jìn)行等價變換，進(jìn)行等價變換，系統(tǒng)碼系統(tǒng)碼和和非系統(tǒng)碼非系統(tǒng)碼的糾錯能力是相同的，而系統(tǒng)碼的編譯碼比非系統(tǒng)碼簡的糾錯能力是相同的，而系統(tǒng)碼的編譯碼比非系統(tǒng)碼簡單，且單，且G G、H H矩陣可方便互求，因此，一般只需討論系統(tǒng)碼。矩陣可方便互求，因此，一般只需討論系統(tǒng)碼。例例6 6、線性分組碼的糾錯與伴隨式、線性分組碼的糾錯與伴隨式：接收到一個序列接收到一個序列 R R 后，校驗后，校驗 H H R RT T=0=0T T 是否成立：是否成立：n若關(guān)系成立，則認(rèn)為若關(guān)系成立，則認(rèn)為 R R 是一個碼字；是一個碼字；n否則判為碼字在傳輸中發(fā)生了錯誤；否

46、則判為碼字在傳輸中發(fā)生了錯誤； 伴隨式（伴隨式（/ /監(jiān)督子監(jiān)督子/ /校驗子）校驗子）： S=RS=R H HT T 或或 S ST T=H=H R RT T 如何糾錯？如何糾錯？n設(shè)發(fā)送碼矢設(shè)發(fā)送碼矢 C=(cC=(cn n1 1,c ,cn n2 2,c,c0 0) )n信道錯誤圖樣為信道錯誤圖樣為 E=(eE=(en n1 1,e ,en n2 2,e,e0 0) ) ，其中其中e ei i=0=0，表示第，表示第i i位無錯；位無錯；e ei i=1=1，表示第，表示第i i 位有錯。位有錯。 i=ni=n1,n1,n2,02,0。接收序列接收序列 R R ：R R=(=(r rn

47、n1 1, ,r rn n2 2,r r0 0)=)=C C + +E E =( =(c cn n1 1+e+en n1 1, ,c cn n2 2+ +e en n2 2,c c0 0 + +e e0 0) )接收序列的伴隨式（接收字用監(jiān)督矩陣進(jìn)行檢驗）接收序列的伴隨式（接收字用監(jiān)督矩陣進(jìn)行檢驗） S ST T=H=H R RT T=H=H (C+E)(C+E)T T=H=H C CT T+H+H E ET T 由于由于H H C CT T=0=0T T，所以，所以 S ST T=H=H E ET T 或或 S=ES=E H HT T 即：即：分析分析：0011221101210121.eh

48、eheheheeeehhhhHESnnnnnnnnTTn對于對于2 2元碼，元碼， e ei i=0=0，1 1，伴隨式是，伴隨式是H H矩陣中對應(yīng)矩陣中對應(yīng)若干列向量之和若干列向量之和。（1 1位錯，多位錯）位錯，多位錯）例例：已知：已知 (7,3)(7,3)碼的一致校驗矩陣。碼的一致校驗矩陣。1000110010001100101110001101H 設(shè)發(fā)送碼矢設(shè)發(fā)送碼矢C C=1010011=1010011。若傳輸時沒有差錯，若傳輸時沒有差錯，E E0 0 = =（00000000000000），）， 則接收碼字則接收碼字 R R1010011=C1010011=C，R R 與與C C

49、相同：相同： S S0 0 = =E E0 0 H HT T = = （00000000） 沒有錯誤；沒有錯誤； 若傳輸時差錯圖樣為若傳輸時差錯圖樣為 E E00 00 = C = 1010011= C = 1010011， 則則 R R00000000000000， S S00 00 = =E E0000 H HT T = = （00000000），無法發(fā)現(xiàn)此錯誤；），無法發(fā)現(xiàn)此錯誤； 若若發(fā)送碼矢發(fā)送碼矢C C1 1=0100111=0100111，C C2 2=1101001=1101001， 錯誤圖樣錯誤圖樣 E E1 1= =（10000001000000），）， 接收碼字接收碼字

50、R R1 111001111100111， R R2 20101001 0101001 ； 伴隨式伴隨式 S S1 1 = R= R1 1 H HT T = E = E1 1 H HT T = = （11101110），）， S S2 2= R= R2 2 H HT T = E = E2 2 H HT T = = （11101110），）， 可見：可見： S S1 1 = S= S2 2 0 0 ；不為；不為0 0，譯碼器判斷有錯誤；，譯碼器判斷有錯誤； 第第1 1位錯誤，剛好對應(yīng)于位錯誤，剛好對應(yīng)于H H矩陣的第矩陣的第1 1列向量；列向量； 伴隨式與發(fā)送碼字無關(guān)，只與錯誤圖樣有關(guān)。伴隨式與

51、發(fā)送碼字無關(guān)，只與錯誤圖樣有關(guān)。 01110000001100011001000110010111000110111TTHES00112211.ehehehehHESnnnnTT 當(dāng)當(dāng)錯誤圖樣錯誤圖樣 E E3 3 = =（00100000010000），），可得：可得： S S3 3= E= E3 3 H HT T = =（11011101），），剛好為剛好為H H矩陣的第矩陣的第3 3列向量。列向量。 依此類推：依此類推：當(dāng)發(fā)生當(dāng)發(fā)生1 1位錯誤時，當(dāng)位錯誤時，當(dāng)i i位錯誤發(fā)生在第位錯誤發(fā)生在第i i位，其伴隨式位，其伴隨式正好是正好是H H矩陣中的第矩陣中的第i i列向量。列向量。若傳

52、送時發(fā)送若傳送時發(fā)送2 2位碼元錯誤，設(shè)位碼元錯誤，設(shè) E E= =（10100001010000）= = E E1 1 + + E E3 3 ， 伴隨式伴隨式 S S = E= E H HT T= = （ E E1 + 1 + E E3 3） H HT T = = E E1 1 H HT T +E +E3 3 H HT T = = （00110011），）， 可見：可見： S S不同于不同于H H中的任何一列，說明發(fā)生了不止一位錯誤；中的任何一列，說明發(fā)生了不止一位錯誤； 可能是第可能是第1 1、第、第3 3位錯誤；位錯誤； 但若錯誤圖樣但若錯誤圖樣 E E= =（0100100010010

53、0）或（）或（00000110000011），）， 其伴隨式仍為（其伴隨式仍為（00110011），譯碼器無法判斷錯誤的位置，故無法糾），譯碼器無法判斷錯誤的位置，故無法糾正正2 2位的隨機(jī)差錯。位的隨機(jī)差錯。 若若錯誤圖樣錯誤圖樣 E E= =（01101000110100），可得：），可得： S= ES= E H HT T = =（11101110）= S= S1 1 ，剛好，剛好為為H H矩陣的第矩陣的第1 1列向量。列向量。由此：由此：此（此（7 7，3 3）碼可發(fā)現(xiàn)）碼可發(fā)現(xiàn)3 3位隨機(jī)錯誤，但當(dāng)發(fā)生位隨機(jī)錯誤，但當(dāng)發(fā)生1 1位錯誤時，無法糾位錯誤時，無法糾正；或者相反。正；或者相反

54、。011100101101000110010001100101110001101TTHESH H矩陣：任意小于等于矩陣：任意小于等于3 3列線性無關(guān)，而最少列線性無關(guān)，而最少4 4列就線性相關(guān)，故其列就線性相關(guān)，故其最小最小碼距碼距d dminmin=4, =4, 故可糾正故可糾正1 1位錯誤的同時檢測出位錯誤的同時檢測出2 2位錯誤，或檢測位錯誤，或檢測3 3位錯誤。位錯誤。本章習(xí)題 9-1 9-3 9-47、 標(biāo)準(zhǔn)陣列譯碼標(biāo)準(zhǔn)陣列譯碼u傳輸中錯誤圖樣傳輸中錯誤圖樣E不同時，有可能對應(yīng)相同的伴隨式。不同時，有可能對應(yīng)相同的伴隨式。 當(dāng)信道譯碼器接收到接收序列當(dāng)信道譯碼器接收到接收序列R后，由

55、下式求解后，由下式求解E： S = R HT = E HT 但是，此式中對應(yīng)的錯誤圖樣可以有但是，此式中對應(yīng)的錯誤圖樣可以有2k個解。個解。u一般采用一般采用最大似然準(zhǔn)則譯碼最大似然準(zhǔn)則譯碼（輸入碼元等概分布），其譯碼錯誤概率（輸入碼元等概分布），其譯碼錯誤概率最小，正確譯碼概率最大。最小，正確譯碼概率最大。 在在BSC信道中，重量最小的信道中，重量最小的E*，其發(fā)生的概率最大，則：，其發(fā)生的概率最大，則：P(C+ E*|C)=P(E*) P(C+ E|C), EE* 因此，用伴隨式譯碼時就采用最大似然準(zhǔn)則（最小距離譯碼準(zhǔn)因此，用伴隨式譯碼時就采用最大似然準(zhǔn)則（最小距離譯碼準(zhǔn)則），選取重量最輕

56、的則），選取重量最輕的E作為譯碼的錯誤圖樣。作為譯碼的錯誤圖樣。 實際譯碼中，根據(jù)實際譯碼中，根據(jù) R HT = S = E HT找出重量最輕的找出重量最輕的E的譯碼的譯碼方法及其繁瑣。一般采用標(biāo)準(zhǔn)陣列譯碼方法。方法及其繁瑣。一般采用標(biāo)準(zhǔn)陣列譯碼方法。u標(biāo)準(zhǔn)陣列譯碼方法：標(biāo)準(zhǔn)陣列譯碼方法：n發(fā)送碼字：取自由發(fā)送碼字：取自由 2k 個碼字構(gòu)成的集合個碼字構(gòu)成的集合C ；n接收序列：可以是接收序列：可以是 2n 個個 n 長序列中任一個矢量；長序列中任一個矢量；n把把 2n 個個 n 長序列劃分為長序列劃分為 2k 個互不相交的子集個互不相交的子集 ，并，并按照最大似然譯碼準(zhǔn)則，使得在每個子集對應(yīng)

57、一個許用碼字；按照最大似然譯碼準(zhǔn)則，使得在每個子集對應(yīng)一個許用碼字；n根據(jù)碼字和子集間一一對應(yīng)關(guān)系，若接收矢量根據(jù)碼字和子集間一一對應(yīng)關(guān)系，若接收矢量 R落在子集落在子集 Dl中，中，就把就把 Rl 譯為子集譯為子集 Dl 對應(yīng)的碼字對應(yīng)的碼字 Cl 。因此因此 當(dāng)接收序列當(dāng)接收序列 R 與實際發(fā)送碼字在同一子集中時，譯碼就是正確與實際發(fā)送碼字在同一子集中時，譯碼就是正確的。的。k221,DDDu標(biāo)準(zhǔn)陣列表的構(gòu)造：標(biāo)準(zhǔn)陣列表的構(gòu)造：n先將先將 2k 個許用碼字排成一行，作為個許用碼字排成一行，作為標(biāo)準(zhǔn)陣列標(biāo)準(zhǔn)陣列的第一行，并將全的第一行，并將全0碼矢碼矢C0=(000)放在最左面的位置上；放在

58、最左面的位置上；n然后在剩下的然后在剩下的 (2n2k) 個個 n 長序列中選取一個重量最輕的重長序列中選取一個重量最輕的重 E1 放在全放在全0碼矢碼矢 C 0下面，即第下面，即第2行首位；再將行首位；再將 E1 分別和所有許用分別和所有許用碼字相加：碼字相加：Ci + E1，放在對應(yīng)碼字下構(gòu)成陣列第二行；，放在對應(yīng)碼字下構(gòu)成陣列第二行；n在第二次剩下的在第二次剩下的 n長序列中，選取重量最輕的長序列中，選取重量最輕的 n 重重 E2，放在，放在 E1 下面，并將下面，并將 E2 分別加到第一行各許用碼字上分別加到第一行各許用碼字上Ci + E2 ，得到第三，得到第三行；行；n，繼續(xù)這樣做下

59、去，直到全部，繼續(xù)這樣做下去，直到全部 n 重用完為止。得到重用完為止。得到 (n,k) 線性線性碼的標(biāo)準(zhǔn)陣列。碼的標(biāo)準(zhǔn)陣列。k221,DDDk2C22ECk32ECkknk22ECkni2ECkn22ECkn2E標(biāo)準(zhǔn)陣列表結(jié)構(gòu)標(biāo)準(zhǔn)陣列表結(jié)構(gòu)伴隨式伴隨式陪集首（表中每一行稱為陪集）陪集首（表中每一行稱為陪集）u標(biāo)準(zhǔn)陣列表的特點：標(biāo)準(zhǔn)陣列表的特點：n表中每一行稱為表中每一行稱為陪集陪集，該行的首位元素，該行的首位元素Ei 在為在為陪集首陪集首，各行元，各行元素都不同；素都不同；n如果把如果把錯誤圖樣錯誤圖樣作為陪集首，則同一個陪集中所有的元素都隊作為陪集首，則同一個陪集中所有的元素都隊?wèi)?yīng)相同的伴

60、隨式；應(yīng)相同的伴隨式；n表中表中各列各列以同一組許用碼字為基礎(chǔ)，將以同一組許用碼字為基礎(chǔ)，將2n個接收序列劃分成不個接收序列劃分成不相交的子集合相交的子集合D0, D1, D2, D2k-1. 每個子集合每個子集合Dj對應(yīng)同一個許用對應(yīng)同一個許用碼字碼字Cj ，它是每列子集的，它是每列子集的子集首子集首。u標(biāo)準(zhǔn)陣列的譯碼：標(biāo)準(zhǔn)陣列的譯碼：n列子集列子集Dj各元素是同一許用碼字各元素是同一許用碼字Cj在信道中發(fā)生若干錯誤得到。在信道中發(fā)生若干錯誤得到。同列中各元素對應(yīng)的是不同的錯誤圖樣。同列中各元素對應(yīng)的是不同的錯誤圖樣。n而列子集而列子集Dj各元素是與許用碼字各元素是與許用碼字Cj距離最近的，