第7章-信道編碼技術(shù)(改1)

第7章_信道編碼技術(shù)(改1)第一頁，共139頁。7.1線性分組碼(1)線性分組碼的編碼：編碼過程分為兩步：把信息序列按一定長度分成若干信息碼組,每組由k位組成;編碼器按照預(yù)定的線性規(guī)則（由線性方程組規(guī)定），把信息碼組變換成n重（n>k）碼字，其中(n－k)個附加碼元是由信息碼元的線性運算產(chǎn)生的。(2)線性分組碼的碼字數(shù)：信息碼組長k位，有2k個不同的信息碼組，有2k個碼字與它們一一對應(yīng)。2023/4/172第二頁，共139頁。7.1線性分組碼(3)術(shù)語線性分組碼：通過預(yù)定的線性運算將長為k位的信息碼組變換成n重的碼字(n>k)。由2k個信息碼組所編成的2k個碼字集合，稱為線性分組碼。碼矢：一個n重的碼字可以用矢量來表示：C=(cn－1,cn－1,…,c1,c0)(n,k)線性碼：信息位長為k，碼字長為n的線性碼。編碼效率/編碼速率/碼率/傳信率：R=k/n。它說明了信道的利用效率，R是衡量碼性能的一個重要參數(shù)。2023/4/173第三頁，共139頁。7.1.1生成矩陣和校驗矩陣(1)校驗方程構(gòu)成碼字的方法：編碼是給已知信息碼組按預(yù)定規(guī)則添加監(jiān)督碼元，構(gòu)成碼字。在k個信息碼元之后附加r(r=n－k)個校驗（監(jiān)督）碼元，使每個校驗元是其中某些信息元的模2和。舉例：k=3,r=4，構(gòu)成(7,3)線性分組碼。設(shè)碼字為：(c6,c5,c4,c3,c2,c1,c0)c6,c5,c4為信息元，c3,c2,c1,c0為校驗元，每個碼元取“0”或“1”校驗元按下面方程組計算：1.線性分組碼的校驗矩陣2023/4/174第四頁，共139頁。(1)校驗方程監(jiān)督方程/校驗方程：確定信息元得到監(jiān)督元規(guī)則的一組方程稱為監(jiān)督方程/校驗方程。由于所有碼字都按同一規(guī)則確定，又稱為一致監(jiān)督方程/一致校驗方程。為什么叫線性分組碼？由于一致監(jiān)督方程是線性的，即監(jiān)督元和信息元之間是線性運算關(guān)系，所以由線性監(jiān)督方程所確定的分組碼是線性分組碼。1.線性分組碼的校驗矩陣7.1線性分組碼2023/4/175第五頁，共139頁。(2)舉例信息碼組(101)，即c6=1,c5=0,c4=1得：c3=0,c2=0,c1=1,c0=1由信息碼組(101)編出的碼字為(1010011)。其它7個碼字如表。1.線性分組碼的校驗矩陣7.1線性分組碼2023/4/176第六頁，共139頁。(3)一致監(jiān)督矩陣為了運算方便，將監(jiān)督方程寫成矩陣形式，得：H

·CT=0T或C·HT=0CT、HT、0T分別表示C、H、0的轉(zhuǎn)置矩陣。1.線性分組碼的校驗矩陣7.1線性分組碼2023/4/177第七頁，共139頁。(3)一致監(jiān)督矩陣系數(shù)矩陣H的后四列組成一個(4×4)階單位子陣，用I4表示，H的其余部分用P表示：推廣到一般情況：對(n,k)線性分組碼，每個碼字中的r(r=n－k)個監(jiān)督元與信息元之間的關(guān)系由下面的線性方程組確定：1.線性分組碼的校驗矩陣7.1線性分組碼2023/4/178第八頁，共139頁。(3)一致監(jiān)督矩陣令上式的系數(shù)矩陣為H，碼字行陣列為C：1.線性分組碼的校驗矩陣7.1線性分組碼2023/4/179第九頁，共139頁。(4)一致監(jiān)督矩陣特性對H各行實行初等變換，將后面r列化為單位子陣，得到下面矩陣，行變換所得方程組與原方程組同解。監(jiān)督矩陣H的標準形式：后面r列是一單位子陣的監(jiān)督矩陣H。1.線性分組碼的校驗矩陣7.1線性分組碼2023/4/1710第十頁，共139頁。(4)一致監(jiān)督矩陣特性

H陣的每一行都代表一個監(jiān)督方程，它表示與該行中“1”相對應(yīng)的碼元的模2和為0。

H的標準形式表明相應(yīng)的監(jiān)督元是由哪些信息元決定。例如(7,3)碼的H陣的第一行為(1011000)，說明第一個監(jiān)督元等于第一個和第三個信息元的模2和，依此類推。

H陣的r行代表了r個監(jiān)督方程，由H所確定的碼字有r個監(jiān)督元。為了得到確定的碼，r個監(jiān)督方程（或H陣的r行）必須是線性獨立的，即要求H陣的秩為r。若把H陣化成標準形式，只要檢查單位子陣的秩，就能方便地確定H陣本身的秩。1.線性分組碼的校驗矩陣7.1線性分組碼2023/4/1711第十一頁，共139頁。(1)線性碼的封閉性線性碼的封閉性：線性碼任意兩個碼字之和仍是一個碼字。定理：設(shè)二元線性分組碼CI(CI表示碼字集合)是由監(jiān)督矩陣H定義，若U和V為其中的任意兩個碼字，則U+V也是CI中的一個碼字。[證明]：由于U和V是碼CI中的兩個碼字，故有：HUT=0THVT=0T，那么H(U+V)T=H(UT+VT)=HUT+HVT=0T

即U+V滿足監(jiān)督方程，所以U+V一定是一個碼字。一個長為n的二元序列可以看作是GF(2)(二元域)上的n維線性空間中的一點。所有2n個矢量集合構(gòu)成了GF(2)上的n維線性空間Vn。把線性碼放入線性空間中進行研究，可使許多問題簡化而比較容易解決。(n,k)線性碼是n維線性空間Vn中的一個k維子空間Vk。2.

線性分組碼的生成矩陣7.1線性分組碼2023/4/1712第十二頁，共139頁。(2)線性分組碼的生成矩陣生成矩陣的來由：在由(n,k)線性碼構(gòu)成的線性空間Vn的k維子空間中，一定存在k個線性獨立的碼字：g1,g2,…,gk。碼CI中其它任何碼字C都可以表示為這k個碼字的一種線性組合，即：2.

線性分組碼的生成矩陣7.1線性分組碼2023/4/1713第十三頁，共139頁。(2)線性分組碼的生成矩陣生成矩陣定義：由于矩陣G生成了(n,k)線性碼，稱矩陣G為(n,k)線性碼的生成矩陣。生成矩陣G的特性

G中每一行g(shù)i=(gi1,gi2,…,gin)都是一個碼字；對每一個信息組m，由矩陣G都可以求得(n,k)線性碼對應(yīng)的碼字。

(n,k)線性碼的每一個碼字都是生成矩陣G的行矢量的線性組合，所以它的2k個碼字構(gòu)成了由G的行張成的n維空間的一個k維子空間Vk。2.

線性分組碼的生成矩陣7.1線性分組碼2023/4/1714第十四頁，共139頁。(2)線性分組碼的生成矩陣線性系統(tǒng)分組碼線性系統(tǒng)分組碼的構(gòu)成：通過行初等變換，將G化為前k列是單位子陣的標準形式。2.

線性分組碼的生成矩陣7.1線性分組碼2023/4/1715第十五頁，共139頁。(2)線性分組碼的生成矩陣線性系統(tǒng)分組碼線性系統(tǒng)分組碼定義：用標準生成矩陣Gk×n

編成的碼字，前面k位為信息位，后面r=n－k位為校驗位，這種信息位在前校驗位在后的線性分組碼稱為線性系統(tǒng)分組碼。當(dāng)生成矩陣G確定之后，(n,k)線性碼就完全被確定，只要找到碼的生成矩陣，編碼問題也同樣被解決。2.

線性分組碼的生成矩陣7.1線性分組碼2023/4/1716第十六頁，共139頁。(2)線性分組碼的生成矩陣舉例：(7,4)線性碼的生成矩陣為：2.

線性分組碼的生成矩陣7.1線性分組碼2023/4/1717第十七頁，共139頁。(3)生成矩陣與一致監(jiān)督矩陣的關(guān)系由于生成矩陣G的每一行都是一個碼字，所以G的每行都滿足：Hr×n(C1×n)T=(01×r)T，則有：Hr×n(Gk×n)T=(0k×r)T

或Gk×n(Hr×n)T=0k×r線性系統(tǒng)碼的監(jiān)督矩陣H和生成矩陣G之間可以直接互換。2.

線性分組碼的生成矩陣7.1線性分組碼2023/4/1718第十八頁，共139頁。(3)生成矩陣與一致監(jiān)督矩陣的關(guān)系舉例：已知(7,4)線性系統(tǒng)碼的監(jiān)督矩陣為：QQT2.

線性分組碼的生成矩陣7.1線性分組碼2023/4/1719第十九頁，共139頁。(4)對偶碼對偶碼：對一個(n,k)線性碼CI，由于Hr×n(Gk×n)T=(0k×r)T，如果以G作監(jiān)督矩陣，而以H作生成矩陣，可構(gòu)造另一個碼CId，CId是一個(n,n－k)線性碼，稱碼CId為原碼的對偶碼。

例如：

(7,4)線性碼的對偶碼是(7,3)碼：

(7,3)碼的生成矩陣G(7,3)是(7,4)碼監(jiān)督矩陣H(7,4)

2.

線性分組碼的生成矩陣7.1線性分組碼2023/4/1720第二十頁，共139頁。(n,k)線性碼的編碼：根據(jù)線性碼的監(jiān)督矩陣或生成矩陣，將長為k的信息組變換成長為n(n>k)的碼字。利用監(jiān)督矩陣構(gòu)造(7,3)線性分組碼的編碼電路設(shè)碼字為：C=(c6c5c4c3c2c1c0)

碼的監(jiān)督矩陣為：7.1.2線性分組碼的編碼7.1線性分組碼的編碼2023/4/1721第二十一頁，共139頁。

利用監(jiān)督矩陣構(gòu)造(7,3)線性分組碼的編碼電路：根據(jù)上面方程組可直接畫出(7,3)碼的并行編碼電路和串行編碼電路:7.1.2線性分組碼的編碼7.1線性分組碼的編碼2023/4/1722第二十二頁，共139頁。

利用監(jiān)督矩陣構(gòu)造(7,4)線性分組碼的編碼電路：根據(jù)上面方程組可直接畫出(7,4)碼的并行編碼電路和串行編碼電路:7.1.2線性分組碼的編碼7.1線性分組碼的編碼2023/4/1723第二十三頁，共139頁。(1)漢明距離、漢明重量和漢明球漢明距離（距離）：在(n,k)線性碼中，兩個碼字U、V之間對應(yīng)碼元位上符號取值不同的個數(shù)，稱為碼字U、V之間的漢明距離。線性分組碼的一個碼字對應(yīng)于n維線性空間中的一點，碼字間的距離即為空間中兩對應(yīng)點的距離。因此，碼字間的距離滿足一般距離公理：7.1.3線性分組碼的最小距離、檢錯和糾錯能力7.1線性分組碼2023/4/1724第二十四頁，共139頁。(1)漢明距離、漢明重量和漢明球

最小距離dmin：在(n,k)線性碼的碼字集合中，任意兩個碼字間距離的最小值，叫做碼的最小距離。若C(i)和C(j)

是任意兩個碼字，則碼的最小距離表示為：碼的最小距離是衡量碼抗干擾能力（檢、糾錯能力）的重要參數(shù)。碼的最小距離越大，碼抗干擾能力就越強。漢明球：以碼字C為中心，半徑為t的漢明球是與C的漢明距離≤t的向量全體SC(t)：任意兩個漢明球不相交最大程度取決于任意兩個碼字之間的最小漢明距離dmin。7.1.3線性分組碼的最小距離、檢錯和糾錯能力7.1線性分組碼2023/4/1725第二十五頁，共139頁。(1)漢明距離、漢明重量和漢明球漢明球：漢明重量（碼字重量）W：碼字中非0碼元符號的個數(shù)，稱為該碼字的漢明重量。在二元線性碼中，碼字重量就是碼字中含“1”的個數(shù)。最小重量Wmin：線性分組碼CI中，非0碼字重量最小值，叫做碼CI的最小重量：Wmin=min{W(V),V∈CI,V≠0}7.1.3線性分組碼的最小距離、檢錯和糾錯能力7.1線性分組碼2023/4/1726第二十六頁，共139頁。(1)漢明距離、漢明重量和漢明球

最小距離與最小重量的關(guān)系：線性分組碼的最小距離等于它的最小重量。檢錯能力：如果一個線性碼能檢出長度≤l個碼元的任何錯誤圖樣，稱碼的檢錯能力為l。糾錯能力：如果線性碼能糾正長度≤t個碼元的任意錯誤圖樣，稱碼的糾錯能力為t。最小距離與檢糾錯能力的關(guān)系：線性碼的最小距離越大，意味著任意碼字間的差別越大，則碼的檢、糾錯能力越強。7.1.3線性分組碼的最小距離、檢錯和糾錯能力7.1線性分組碼2023/4/1727第二十七頁，共139頁。(2)最小距離與檢、糾錯能力最小距離與糾錯能力：(n,k)線性碼能糾t個錯誤的充要條件是碼的最小距離為：dmin≥2t+1最小距離與檢錯能力：(n,k)線性碼能夠發(fā)現(xiàn)l個錯誤的充要條件是碼的最小距離為：dmin≥l+1最小距離與檢錯能力：

幾何意義：7.1.3線性分組碼的最小距離、檢錯和糾錯能力7.1線性分組碼2023/4/1728第二十八頁，共139頁。(2)最小距離與檢、糾錯能力最小距離與檢、糾錯能力：(n,k)線性碼能糾t個錯誤，并能發(fā)現(xiàn)l個錯誤(l>t)的充要條件是碼的最小距離為：dmin≥t+l+1最小距離與檢、糾錯能力：幾何意義：7.1.3線性分組碼的最小距離、檢錯和糾錯能力7.1線性分組碼2023/4/1729第二十九頁，共139頁。(2)最小距離與檢、糾錯能力當(dāng)(n,k)線性碼的最小距離dmin

給定后，可按實際需要靈活安排糾錯的數(shù)目。：dmin≥t+l+1例如：對dmin=8的碼，可用來糾3檢4錯，或糾2檢5錯，或糾1檢6錯，或者只用于檢7個錯誤。7.1.3線性分組碼的最小距離、檢錯和糾錯能力7.1線性分組碼2023/4/1730第三十頁，共139頁。(3)線性碼的最小距離與監(jiān)督矩陣的關(guān)系定理1：設(shè)H為(n,k)線性碼的一致監(jiān)督矩陣，若H中任意S列線性無關(guān)，而H中存在(S+1)列線性相關(guān)，則碼的最小距離為(S+1)。定理2：若碼的最小距離為(S+1)，則該碼監(jiān)督矩陣的任意S列線性無關(guān)，而必存在有相關(guān)的(S+1)列。定理3：在二元線性碼的監(jiān)督矩陣H中，如果任一列都不是全“0”，且任兩列都不相等，則該碼能糾一個錯誤。（S=2，dmin=3）7.1.3線性分組碼的最小距離、檢錯和糾錯能力7.1線性分組碼2023/4/1731第三十一頁，共139頁。7.1.4線性分組碼的譯碼(1)如何譯碼？用監(jiān)督矩陣編碼，也用監(jiān)督矩陣譯碼：接收到一個碼字R后，校驗HRT=0T是否成立：若關(guān)系成立，則認為R是一個碼字；否則，判碼字在傳輸中發(fā)生了錯誤；HRT的值是否為0是校驗碼字出錯與否的依據(jù)。(2)伴隨式/監(jiān)督子/校驗子：S=RHT或ST=HRT1.伴隨式和錯誤檢測7.1線性分組碼2023/4/1732第三十二頁，共139頁。(3)伴隨式的計算

發(fā)送碼字：C=(cn－1,cn－2,…,c0)

信道錯誤圖樣：E=(en－1,en－2,…,e0)ei=0，表示第i位無錯；

ei=1，表示第i位有錯。i=n－1,n－2,…,0

接收字：R=(rn－1,rn－2,…,r0)=C+E=(cn－1+en－1,cn－2+en－2,…,c0+e0)

求接收字的伴隨式（接收字用監(jiān)督矩陣進行檢驗）

ST=HRT=H(C+E)T=HCT+HET

HCT=0T，所以ST=HET

設(shè)H=(h1,h2,…,hn)，（hi表示H的列）。代入上式得：ST=h1en－1+h2en－2+…+hn

e07.1線性分組碼的譯碼1.伴隨式和錯誤檢測2023/4/1733第三十三頁，共139頁。(4)伴隨式的特性伴隨式僅與錯誤圖樣有關(guān)，而與發(fā)送的具體碼字無關(guān)，即伴隨式僅由錯誤圖樣決定；伴隨式是錯誤的判別式：若S=0，則判為沒有出錯，接收字是一個碼字；若S≠0，則判為有錯。不同的錯誤圖樣具有不同的伴隨式，它們是一一對應(yīng)的。對二元碼，伴隨式是H陣中與錯誤碼元對應(yīng)列之和。7.1線性分組碼的譯碼1.伴隨式和錯誤檢測ST=h1en－1+h2en－2+…+hn

e02023/4/1734第三十四頁，共139頁。(5)舉例：(7,3)碼接收字R的伴隨式計算若接收字中沒有錯誤：設(shè)發(fā)送碼字C=1010011，接收碼字R＝，R與C相同：但接收端譯碼器并不知道就是發(fā)送的碼字；根據(jù)接收字R

計算伴隨式：ST=HRT=0T

因此，譯碼器判接收字無錯。7.1線性分組碼的譯碼1.伴隨式和錯誤檢測2023/4/1735第三十五頁，共139頁。(5)舉例：(7,3)碼接收矢量R的伴隨式計算若接收字中有1位錯誤：發(fā)送碼字C=1010011，接收碼字R=1110011，伴隨式為：

(7,3)碼是糾單個錯誤的碼，且ST

等于H

的第二列，因此判定接收字R

的第二位是錯的。由于接收字R

中錯誤碼元數(shù)與碼的糾錯能力相符，所以譯碼正確。7.1線性分組碼的譯碼1.伴隨式和錯誤檢測2023/4/1736第三十六頁，共139頁。1.伴隨式和錯誤檢測(5)舉例：(7,3)碼接收矢量R的伴隨式計算當(dāng)碼元錯誤多于1個時：發(fā)送碼字C=1010011，接收碼字R=0011011，伴隨式為：由于ST

是第一列和第四列之和，不等于0；但ST與H

陣中任何一列都不相同無法判定錯誤出在哪些位上，只是發(fā)現(xiàn)有錯。7.1線性分組碼的譯碼2023/4/1737第三十七頁，共139頁。(6)伴隨式計算電路伴隨式的計算可用電路來實現(xiàn)。(7,3)碼為例：接收字R=(r6r5r4r3r2r1r0)，伴隨式：7.1線性分組碼的譯碼1.伴隨式和錯誤檢測2023/4/1738第三十八頁，共139頁。(6)伴隨式計算電路7.1線性分組碼的譯碼1.伴隨式和錯誤檢測2023/4/1739第三十九頁，共139頁。(1)最佳譯碼準則（最大似然譯碼）

通信是一個統(tǒng)計過程，糾、檢錯能力最終要反映到差錯概率上。對于FEC方式，采用糾錯碼后的碼字差錯概率為pwe：

p(C)：發(fā)送碼字C的先驗概率

p(C/R)：后驗概率2.糾錯譯碼若碼字數(shù)為2k，對充分隨機的消息源有p(C)=1/2k，所以最小化的pwe等價為最小化p(C'

≠C/R)，又等價為最大化：p(C'

=C/R)；對于BSC信道：最大化的p(C'

=C/R)等價于最大化的p(R/C)，最大化的p(R/C)又等價于最小化d(R,C)，所以使差錯概率最小的譯碼是使接收向量R與輸出碼字C'距離最小的譯碼。7.1線性分組碼的譯碼2023/4/1740第四十頁，共139頁。(2)查表譯碼法

按最小距離譯碼，對有2k個碼字的(n,k)線性碼，為了找到與接收字R有最小距離的碼字，需將R分別和2k個碼字比較，求出最小距離。其中利用“標準陣列”譯碼是最典型的方法。(3)標準陣列①碼字參數(shù)：發(fā)送碼字：取自于2k個碼字集合{C}；接收碼字：可以是2n個n重中任一個矢量。②譯碼方法把2n個n重矢量劃分為2k個互不相交的子集，使得在每個子集中僅含一個碼字；根據(jù)碼字與子集間一一對應(yīng)的關(guān)系，若接收矢量Rl落在子集Dl中，就把Rl譯為子集Dl含有的碼字Cl；當(dāng)接收矢量R與實際發(fā)送碼字在同一子集中時，譯碼就是正確的。7.1線性分組碼的譯碼2.糾錯譯碼2023/4/1741第四十一頁，共139頁。(3)標準陣列③標準陣列構(gòu)造方法先將2k個碼字排成一行，作為標準陣列的第一行，并將全0碼字C1=(00…0)放在最左面的位置上；然后在剩下的(2n－2k)

個n重中選取一個重量最輕的n重E2放在全0碼字C1下面，再將E2分別和碼字相加，放在對應(yīng)碼字下面構(gòu)成陣列第二行；在第二次剩下的n重中，選取重量最輕的n重E3，放在E2下面，并將E3分別加到第一行各碼字上，得到第三行；…，繼續(xù)這樣做下去，直到全部n重用完為止。得到下表所示給定(n,k)線性碼的標準陣列。7.1線性分組碼的譯碼2.糾錯譯碼2023/4/1742第四十二頁，共139頁。(3)標準陣列③標準陣列構(gòu)造方法7.1線性分組碼的譯碼2.糾錯譯碼2023/4/1743第四十三頁，共139頁。(3)標準陣列④標準陣列的特性定理1：在標準陣列的同一行中沒有相同的矢量，而且2n個n重中任一個n重在陣列中出現(xiàn)一次且僅出現(xiàn)一次。定理2（線性碼糾錯極限定理）：二元(n,k)線性碼能糾2n－k個錯誤圖樣。這2n－k個可糾的錯誤圖樣，包括0矢量在內(nèi)，即把無錯的情況也看成一個可糾的錯誤圖樣。陪集：標準陣列的每一行叫做碼的一個陪集。陪集首：每個陪集的第一個元素叫做陪集首。(n,k)線性碼的標準陣列有2k列（和碼字數(shù)量相等），2n/2k=2n－k行，且任何兩列和兩行都沒有相同的元素。7.1線性分組碼的譯碼2.糾錯譯碼2023/4/1744第四十四頁，共139頁。(3)標準陣列④標準陣列的特性線性碼糾錯能力與監(jiān)督元數(shù)目的關(guān)系：一個可糾t個錯誤的線性碼必須滿足：上式中等式成立時的線性碼稱為完備碼。即：對于完備碼，由碼的糾錯能力所確定的伴隨式數(shù)恰好等于可糾的錯誤圖樣數(shù)，所以完備碼的(n－k)個監(jiān)督碼元得到了充分的利用。7.1線性分組碼的譯碼2.糾錯譯碼2023/4/1745第四十五頁，共139頁。(3)標準陣列④標準陣列的特性完備譯碼：(n,k)線性碼的所有2n－k個伴隨式，在譯碼過程中都用來糾正所有小于等于個隨機錯誤，以及部分大于t的錯誤圖樣。限定距離譯碼：任一個(n,k)線性碼，能糾正個隨機錯誤，如果在譯碼時僅糾正t'<t個錯誤，而當(dāng)錯誤個數(shù)大于t'時，譯碼器不進行糾錯而僅指出發(fā)生了錯誤。7.1線性分組碼的譯碼2.糾錯譯碼2023/4/1746第四十六頁，共139頁。(3)標準陣列④標準陣列的特性

從多維矢量空間的角度看完備碼假定圍繞每一個碼字Ci放置一個半徑為t

的球，每個球內(nèi)包含了與該碼字漢明距離小于等于t的所有接收碼字R的集合；在半徑為的球內(nèi)的接收碼字數(shù)是：因為有2k個可能發(fā)送的碼字，也就有2k個不相重疊的半徑為t的球。包含在2k個球中的碼字總數(shù)不會超過2n個可能的接收碼字。7.1線性分組碼的譯碼2.糾錯譯碼2023/4/1747第四十七頁，共139頁。(3)標準陣列④標準陣列的特性從多維矢量空間的角度看完備碼于是一個糾t個差錯的碼必然滿足不等式：如果上式中等號成立，表示所有的接收碼字都落在2k個球內(nèi)，而球外沒有一個碼，這就是完備碼。7.1線性分組碼的譯碼2.糾錯譯碼2023/4/1748第四十八頁，共139頁。(3)標準陣列④標準陣列的特性

從多維矢量空間的角度看完備碼

完備碼特性：圍繞2k

個碼字，漢明距離為t=INT[(dmin－1)/2]的所有球都是不相交的，每一個接收碼字都落在這些球中之一，因此接收碼與發(fā)送碼的距離至多為t，這時所有重量≤t的錯誤圖樣都能用最佳（最小距離）譯碼器得到糾正，而所有重量≥t+1的錯誤圖樣都不能糾正。7.1線性分組碼的譯碼2.糾錯譯碼2023/4/1749第四十九頁，共139頁。(3)標準陣列④標準陣列的特性

從多維矢量空間的角度看完備碼舉例：對糾一個錯誤的(7,4)漢明碼：(7,4)漢明碼是一個完備碼。所有漢明碼都是完備碼：（滿足2n－k=2r=n+1）。7.1線性分組碼的譯碼2.糾錯譯碼2023/4/1750第五十頁，共139頁。(3)標準陣列④標準陣列的特性

標準陣列譯碼=最小距離譯碼=最佳譯碼陪集首是可糾正的錯誤圖樣，為了使譯碼錯誤概率最小，應(yīng)選取出現(xiàn)概率最大的錯誤圖樣作陪集首；重量較輕的錯誤圖樣出現(xiàn)概率較大，所以在構(gòu)造標準陣列時是選取重量最輕的n重作陪集首；當(dāng)錯誤圖樣為陪集首時（可糾的錯誤圖樣），接收矢量與原發(fā)送碼字間的距離（等于陪集首）最?。灰虼?，選擇重量最輕的元素作陪集首，按標準陣列譯碼就是按最小距離譯碼；所以標準陣列譯碼法也是最佳譯碼法。7.1線性分組碼的譯碼2.糾錯譯碼2023/4/1751第五十一頁，共139頁。(3)標準陣列④標準陣列的特性定理3：在標準陣列中，一個陪集的所有2k個n重有相同的伴隨式，不同的陪集伴隨式互不相同。[證明]：設(shè)H為給定(n,k)線性碼的監(jiān)督矩陣，在陪集首為El的陪集中的任意矢量為：R=El+Ci,i=1,2,…,2k其伴隨式為：S=RHT=(El+Ci)HT=ElHT+CiHT=ElHT上式表明：陪集中任意矢量的伴隨式等于陪集首的伴隨式。即同一陪集中所有伴隨式相同。不同陪集中，由于陪集首不同所以伴隨式不同。7.1線性分組碼的譯碼2.糾錯譯碼2023/4/1752第五十二頁，共139頁。(3)標準陣列⑤標準陣列三種譯碼方法：直接在水平、垂直兩個方向?qū)ψg碼表進行二維搜索，然后沿著陣列的列找到對應(yīng)的編碼碼字，將其作為譯碼輸出。先計算伴隨式S=RHT，根據(jù)伴隨式的值確定接收碼字所在行，沿著該行逐個搜索各個元素，找到Y(jié)對應(yīng)的列，將該列的第1個元素作為譯碼輸出。計算伴隨式S=RHT的值，同時確定S所對應(yīng)的差錯圖樣，譯碼輸出為。7.1線性分組碼的譯碼2.糾錯譯碼2023/4/1753第五十三頁，共139頁。(4)舉例：一個(4,2)系統(tǒng)線性碼的生成矩陣是7.1線性分組碼的譯碼2.糾錯譯碼求:(1)構(gòu)造系統(tǒng)的標準陣列

(2)設(shè)收碼R=(1010)，錯誤圖樣E=(0100)，求對應(yīng)的碼字并判斷有無錯誤；若R=(1010)，錯誤圖樣E=(0110)，求對應(yīng)的碼字并判斷有無錯誤。0000100101111110100001000010000111110110110100111010101101011100（2）當(dāng)收到R=(1010)時，譯為m=(1110)，顯然位于第三行的陪集首(0100)是錯誤圖樣E，因此譯碼正確。當(dāng)收到R=(1010)時，譯為m=(1110)，顯然位于第三行的陪集首(0100)不是錯誤圖樣E，因此譯碼不正確。(1)分別以信息組m=(00).(01).(10).(11)及已知的G,由C=mG得系統(tǒng)碼組R的4個許用碼字為

0000，0111，1001，1110。解：構(gòu)造的標準陣列譯碼表如右示2023/4/1754第五十四頁，共139頁。(4)舉例：一個(5,2)系統(tǒng)線性碼的生成矩陣是7.1線性分組碼的譯碼2.糾錯譯碼2023/4/1755分別以信息組m=(00).(01).(10).(11)及已知的G求得4個許用碼字為C1=(00000),C2=(10111),C3=(01101),C4=(11010)。設(shè)收碼R=(10101)，構(gòu)造標準陣列譯碼表，譯出發(fā)碼的估值解：(1)構(gòu)造標準陣列譯碼表。求出校驗矩陣：H=[PT

I3]=列出方程組：2023/4/1755第五十五頁，共139頁。7.1線性分組碼的譯碼2.糾錯譯碼(2)譯碼表的構(gòu)成伴隨式有2n-k＝23＝8種組合，差錯圖案中代表無差錯的有一種，代表一個差錯的圖案有種，已有6種。代表兩個差錯的圖案有種。只需挑選其中的兩個，挑選方法可有若干種，不是唯一的。先將Ej=(00000)、(10000)、(01000)、(00100)、(00010)、(00001)代入上面的線性方程組。解得對應(yīng)的Sj分別是(000)、(111)、(101)、(100)、(010)、(001)。剩下的伴隨式中，(011)所對應(yīng)的差錯圖案是2k個即(00011)、(10100)、(01110)、(11001),其中(00011)和(10100)并列重量最輕，任選其中一個如(00011)。同樣可得伴隨式(110)所對應(yīng)的最輕差錯圖案之一是(00110)。

2023/4/1756第五十六頁，共139頁。7.1線性分組碼的譯碼2.糾錯譯碼S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=00110100010101111100標準陣列譯碼表2023/4/1757第五十七頁，共139頁。(4)舉例：將接收碼R＝10101譯碼7.1線性分組碼的譯碼2.糾錯譯碼

可選以下三種方法之一譯碼：直接搜索碼表，查得(10101)所在列的子集頭是(10111)，因此譯碼輸出取為(10111)。先求伴隨式RHT=(10101)

HT=(010)=S4，確定S4所在行，再沿著行對碼表作一維搜索找到(10101),最后順著所在列向上找出碼字(10111)。先求出伴隨式RHT=(010)=S4并確定S4所對應(yīng)的陪集首（差錯圖案）E4=(00010)，再將陪集首與收碼相加得到碼字C=R+E4=(10101)+(00010)=(10111)。上述三種方法由上而下，查表的時間下降而所需計算量增大，實際使用時可針對不同情況選用。2023/4/1758第五十八頁，共139頁。(4)舉例：該(5,2)碼的dmin=3,糾錯能力是t=int[(3-1)/2]=1。7.1線性分組碼的譯碼2.糾錯譯碼譯碼陣列中只有前6行具有唯一性、可靠性，真正體現(xiàn)了最大似然譯碼準則，而第7、8行的差錯圖案(00011)和(00110)中包含兩個“1”，譯碼已不可靠。如：當(dāng)收碼R＝(10100)時，根據(jù)碼表譯出的碼字是(10111)，與收碼R的漢明距離是2，然而收碼R與全零碼字(00000)的漢明距離也是2，為什么不能譯成(00000)呢？因為碼表的第7、8行本身就不是唯一的。

伴隨式(011)所對應(yīng)的4個差錯圖案中有兩個并列重量最輕，如果當(dāng)時選的不是(00011)而是(10100)，碼表第7行就不同了。伴隨式S對產(chǎn)生差錯位的判斷？2023/4/1759第五十九頁，共139頁。(4)舉例：(6,3)碼的標準陣列返回7.1線性分組碼的譯碼2.糾錯譯碼2023/4/1760第六十頁，共139頁。(5)結(jié)論任意n重的伴隨式?jīng)Q定于它在標準陣列中所在陪集的陪集首。

標準陣列的陪集首和伴隨式是一一對應(yīng)的，因而碼的可糾錯誤圖樣和伴隨式是一一對應(yīng)的，應(yīng)用此對應(yīng)關(guān)系可以構(gòu)成比標準陣列簡單得多的譯碼表，從而得到(n,k)線性碼的一般譯碼步驟。

(n,k)線性碼的一般譯碼步驟計算接收矢量R的伴隨式ST=HRT

；根據(jù)伴隨式和錯誤圖樣一一對應(yīng)的關(guān)系，利用伴隨式譯碼表，由伴隨式譯出R的錯誤圖樣E；將接收字減錯誤圖樣，得發(fā)送碼字的估值：C'=R－E

。見表7.1線性分組碼的譯碼2.糾錯譯碼2023/4/1761第六十一頁，共139頁。(5)結(jié)論線性分組碼一般譯碼器（伴隨式譯碼法/查表譯碼法）譯碼器如下圖。這種查表譯碼法具有最小的譯碼延遲和最小的譯碼錯誤概率，原則上可用于任何(n,k)線性碼。7.1線性分組碼的譯碼2.糾錯譯碼2023/4/1762第六十二頁，共139頁。(5)結(jié)論舉例：求(7,4)漢明碼的編碼電路和譯碼電路。其系統(tǒng)碼形式：編碼電路：7.1線性分組碼的譯碼2.糾錯譯碼2023/4/1763第六十三頁，共139頁。(5)結(jié)論舉例：求(7,4)漢明碼的編碼電路和譯碼電路。編碼電路：7.1線性分組碼的譯碼2.糾錯譯碼2023/4/1764第六十四頁，共139頁。(5)結(jié)論舉例：求(7,4)漢明碼的編碼電路和譯碼電路。譯碼電路：7.1線性分組碼的譯碼2.糾錯譯碼2023/4/1765第六十五頁，共139頁。7.1.5漢明碼

漢明碼的來由：漢明碼是漢明于1950年提出的糾一個錯誤的線性碼，也是第一個糾錯碼。由于它編碼簡單，因而是在通信系統(tǒng)和數(shù)據(jù)存儲系統(tǒng)中得到廣泛應(yīng)用的一類線性碼。

漢明碼的結(jié)構(gòu)參數(shù)：糾一個錯誤的線性碼，其最小距離dmin=3；監(jiān)督矩陣任意兩列線性無關(guān)／H的任兩列互不相同；沒有全0的列。監(jiān)督元個數(shù)r=n－k；H陣中每列有r個元素，至多可構(gòu)成2r－1種互不相同的非0列。對于任意正整數(shù)m≥3，漢明碼的結(jié)構(gòu)參數(shù)為：碼長：

n=2m－1

信息位數(shù)：

k=2m－m－1

監(jiān)督位數(shù)：

n－k=m

碼的最小距離：dmin=3(t=1)2023/4/1766第六十六頁，共139頁。

漢明碼監(jiān)督矩陣構(gòu)成的兩種方式

H陣的標準形式：H=[QIr]，Ir為r階單位子陣，子陣Q是構(gòu)造Ir后剩下的列任意排列。用這種形式的H陣編出的漢明碼是系統(tǒng)碼。按r重表示的二進制順序排列：按這種形式H陣編出的碼是非系統(tǒng)碼。當(dāng)發(fā)生可糾的單個錯誤時，伴隨式為H陣中對應(yīng)的列，所以伴隨式的二進制數(shù)值就是錯誤位置號，這種碼譯碼比較方便。例如：7.1.5漢明碼由于漢明碼可糾的錯誤圖樣數(shù)為：滿足式因此漢明碼是完備碼。2023/4/1767第六十七頁，共139頁。7.1.6循環(huán)碼1.循環(huán)碼的多項式描述(1)循環(huán)碼的性質(zhì)循環(huán)碼是線性分組碼的一個重要子類；由于循環(huán)碼具有優(yōu)良的代數(shù)結(jié)構(gòu)，可用簡單的反饋移位寄存器實現(xiàn)編碼和伴隨式計算，并可使用多種簡單而有效的譯碼方法；循環(huán)碼是研究最深入、理論最成熟、應(yīng)用最廣泛的一類線性分組碼。7.1循環(huán)碼(2)循環(huán)碼的定義

循環(huán)碼：如果(n,k)線性分組碼的任意碼字：C=(cn－1,cn－2,…,c0)

的i次循環(huán)移位，所得矢量：C(i)=(cn－1－i,cn－2－i,…,c0,cn－1,…,cn－i)

仍是一個碼字，則稱此線性碼為(n,k)循環(huán)碼。2023/4/1768第六十八頁，共139頁。1.循環(huán)碼的多項式描述7.1循環(huán)碼(3)碼多項式碼多項式：為了運算的方便，將碼字的各分量作為多項式的系數(shù)，把碼字表示成多項式，稱為碼多項式。其一般表示式為：C(x)=cn－1xn－1+cn－2xn－2+…+c0

碼多項式i次循環(huán)移位的表示方法碼多項式C(x)的一次左移循環(huán)為C(1)(x)

，i次左移循環(huán)為C(i)(x)2023/4/1769第六十九頁，共139頁。1.循環(huán)碼的多項式描述(3)碼多項式碼多項式的模(xn+1)運算

0和1兩個元素模2運算下構(gòu)成域。若p為素數(shù)，則整數(shù)全體在模p運算下的剩余類全體在模p下構(gòu)成域。7.1循環(huán)碼2023/4/1770第七十頁，共139頁。1.循環(huán)碼的多項式描述(3)碼多項式碼多項式的模(xn+1)運算碼字C循環(huán)i次所得碼字的碼多項式：

C(x)乘以x，再除以(xn+1)，得：7.1循環(huán)碼2023/4/1771第七十一頁，共139頁。1.循環(huán)碼的多項式描述(3)碼多項式碼多項式的模(xn+1)運算上式表明：碼字循環(huán)一次的碼多項式C(1)(x)是原碼多項式C(x)乘以x除以(xn+1)的余式。寫作：

C(x)的i次循環(huán)移位C(i)(x)是C(x)乘以xi除以(xn+1)的余式，即：結(jié)論：循環(huán)碼的碼字的i次循環(huán)移位等效于將碼多項式乘xi后再模(xn+1)。7.1循環(huán)碼2023/4/1772第七十二頁，共139頁。1.循環(huán)碼的多項式描述(4)舉例：(7,3)循環(huán)碼可由任一個碼字，比如(0011101)經(jīng)過循環(huán)移位，得到其它6個非0碼字；由相應(yīng)的碼多項式(x4+x3+x2+1)，乘以xi(i=1,2,…,6)，再模(x7+1)運算得到其它6個非0碼多項式。移位過程和相應(yīng)的多項式運算如表所示。7.1循環(huán)碼2023/4/1773第七十三頁，共139頁。2.循環(huán)碼的生成多項式7.1循環(huán)碼(1)循環(huán)碼的生成矩陣循環(huán)碼的循環(huán)特性：可由一個碼字的循環(huán)移位得到其它的非0碼字。在(n,k)循環(huán)碼的2k個碼字中，取前(k－1)位皆為0的碼字g(x)（次數(shù)r=n－k），再經(jīng)(k－1)次循環(huán)移位，共得到k個碼字：g(x),xg(x),…,xk－1g(x)

這k個碼字是相互獨立的，可作為碼生成矩陣的k行，得到循環(huán)碼的生成矩陣G(x)。矩陣中的元素是多項式：2023/4/1774第七十四頁，共139頁。2.循環(huán)碼的生成多項式7.1循環(huán)碼(1)循環(huán)碼的生成矩陣將矩陣中的多項式改寫成對應(yīng)的n重矢量形式：碼的生成矩陣一旦確定，碼就確定了；(n,k)循環(huán)碼可由它的一個(n－k)次碼多項式g(x)來確定；g(x)生成了(n,k)循環(huán)碼，稱g(x)為碼的生成多項式。

g(x)是一個(n－k)次首1多項式2023/4/1775第七十五頁，共139頁。2.循環(huán)碼的生成多項式7.1循環(huán)碼(3)生成多項式和碼多項式的關(guān)系定理1：在(n,k)循環(huán)碼中，生成多項式g(x)是惟一的(n－k)次碼多項式,且次數(shù)是最低的。定理2：在(n,k)循環(huán)碼中，每個碼多項式C(x)都是g(x)的倍式；而每個為g(x)倍式且次數(shù)小于或等于(n－1)的多項式，必是一個碼多項式。定理3(定理8.2.2的逆定理)：在一個(n,k)線性碼中，如果全部碼多項式都是最低次的(n－k)次碼多項式的倍式，則此線性碼為一個(n,k)循環(huán)碼。2023/4/1776第七十六頁，共139頁。2.循環(huán)碼的生成多項式7.1循環(huán)碼(3)生成多項式和碼多項式的關(guān)系碼字循環(huán)關(guān)系圖單純循環(huán)碼的碼字循環(huán)圖：(7,3)循環(huán)碼2023/4/1777第七十七頁，共139頁。2.循環(huán)碼的生成多項式7.1循環(huán)碼(3)生成多項式和碼多項式的關(guān)系碼字循環(huán)關(guān)系圖推廣循環(huán)碼的碼字循環(huán)圖：

(6,3)循環(huán)碼2023/4/1778第七十八頁，共139頁。2.循環(huán)碼的生成多項式7.1循環(huán)碼(4)如何尋找一個合適的生成多項式循環(huán)碼的碼多項式等于信息多項式乘以生成多項式：對一個循環(huán)碼只要生成多項式一旦確定，碼就確定了，編碼問題就解決了。作一循環(huán)碼的關(guān)鍵，就在于尋找一個適當(dāng)?shù)纳啥囗検健?023/4/1779第七十九頁，共139頁。2.循環(huán)碼的生成多項式7.1循環(huán)碼(4)如何尋找一個合適的生成多項式定理4：

(n,k)循環(huán)碼的生成多項式g(x)是(xn+1)的因式，即：

xn+1=h(x)g(x)。定理5：若g(x)是一個(n－k)次多項式，且為(xn+1)的因式，則g(x)生成一個(n,k)循環(huán)碼。結(jié)論：求作一個(n,k)循環(huán)碼時，只要分解多項式(xn+1)，從中取出(n－k)次因式作生成多項式即可。例：求(7,3)循環(huán)碼的生成多項式。[解]：分解多項式x7+1，取其4次因式作生成多項式：x7+1=(x+1)(x3+x2+1)(x3+x+1)

可將一次和任一個三次因式的乘積作為生成多項式，可?。篻1(x)=(x+1)(x3+x2+1)=x4+x2+x+1或g2(x)=(x+1)(x3+x+1)=x4+x3+x2+12023/4/1780第八十頁，共139頁。2.循環(huán)碼的生成多項式7.1循環(huán)碼(5)循環(huán)碼的監(jiān)督多項式和監(jiān)督矩陣循環(huán)碼的監(jiān)督多項式：設(shè)g(x)為(n,k)循環(huán)碼的生成多項式，必為(xn+1)的因式，則有：xn+1=h(x)g(x)，式中h(x)為k次多項式，稱為(n,k)循環(huán)碼的監(jiān)督多項式。

(n,k)循環(huán)碼也可由其監(jiān)督多項式完全確定。舉例：(7,3)循環(huán)碼：x7+1=(x3+x+1)(x4+x2+x+1)4次多項式為生成多項式：g(x)=x4+x2+x+1=g4x4+g3x3+g2x2+g1x+g03次多項式是監(jiān)督多項式：h(x)=x3+x+1=h3x3+h2x2+h1x+h02023/4/1781第八十一頁，共139頁。2.循環(huán)碼的生成多項式7.1循環(huán)碼(5)循環(huán)碼的監(jiān)督多項式和監(jiān)督矩陣循環(huán)碼的監(jiān)督矩陣由等式x7+1=h(x)g(x)兩端同次項系數(shù)相等得：將上面的方程組寫成矩陣形式：2023/4/1782第八十二頁，共139頁。2.循環(huán)碼的生成多項式7.1循環(huán)碼(5)循環(huán)碼的監(jiān)督多項式和監(jiān)督矩陣循環(huán)碼的監(jiān)督矩陣上式中，列陣的元素是生成多項式g(x)的系數(shù)，是一個碼字，那么第一個矩陣則為(7,3)循環(huán)碼的監(jiān)督矩陣，即：2023/4/1783第八十三頁，共139頁。2.循環(huán)碼的生成多項式7.1循環(huán)碼(5)循環(huán)碼的監(jiān)督多項式和監(jiān)督矩陣循環(huán)碼監(jiān)督矩陣的構(gòu)成由前式可見，監(jiān)督矩陣的第一行是碼的監(jiān)督多項式h(x)的系數(shù)的反序排列，第二、三、四行是第一行的移位；用監(jiān)督多項式的系數(shù)來構(gòu)成監(jiān)督矩陣：

其中h*(x)表示h(x)的反多項式2023/4/1784第八十四頁，共139頁。2.循環(huán)碼的生成多項式7.1循環(huán)碼(5)循環(huán)碼的監(jiān)督多項式和監(jiān)督矩陣循環(huán)碼監(jiān)督矩陣的構(gòu)成(n,k)循環(huán)碼的監(jiān)督矩陣：對偶問題如果xn+1=h(x)g(x)，其中g(shù)(x)為(n－k)

次多項式，以g(x)為生成多項式，則生成一個(n,k)循環(huán)碼；以h(x)為生成多項式，則生成(n,n－k)循環(huán)碼；這兩個循環(huán)碼互為對偶碼。2023/4/1785第八十五頁，共139頁。3.構(gòu)造循環(huán)碼的步驟7.1循環(huán)碼將多項式xn+1進行因式分解，找出其n-k次因式；以n-k次因式為生成多項式g(x)，與信息多項式m(x)相乘，得碼多項式C(x)=m(x)g(x)因m(x)不高于(k-1)次，所以C(x)的次數(shù)不會高于(k-1)+(n-k)=(n-1)次。2023/4/1786第八十六頁，共139頁。3.構(gòu)造循環(huán)碼的步驟7.1循環(huán)碼研究一個長度n=7的循環(huán)碼的構(gòu)成方法(1)

對(x7+1)作分解，找出n-k次因式。

x7+1＝(x+1)(x3+x2+1)(x3+x+1)

n-k因式g(x)對偶式h(x) 循環(huán)碼

1(x+1) (x3+x2+1)(x3+x+1) (7,6)3(x3+x2+1)(x+1)(x3+x+1)(7,4)3(x3+x+1)(x+1)(x3+x2+1) (7,4)4(x+1)(x3+x2+1)(x3+x+1) (7,3)4(x+1)(x3+x+1)(x3+x2+1) (7,3)6(x3+x2+1)(x3+x+1)

(x+1) (7,1)2023/4/1787第八十七頁，共139頁。3.構(gòu)造循環(huán)碼的步驟7.1循環(huán)碼構(gòu)成(7,3)循環(huán)碼： 選g(x)=(x+1)(x3+x+1)=(x4+x3+x2+1)，則C(x)=m(x)g(x)=(m2x2+m1x+m0)(x4+x3+x2+1)。當(dāng)輸入信息m=(011)時，m(x)=(x+1)，C(x)=(x+

1)(x4＋x3＋x2＋1)=x5+x2+x1+

1， 對應(yīng)碼矢C=(0100111)。信息矢量m(m2

m1

m0)碼矢C(c6c5c4c3c2c1c0)0000010100111001011101112023/4/1788第八十八頁，共139頁。4.系統(tǒng)循環(huán)碼7.1循環(huán)碼(1)系統(tǒng)循環(huán)碼構(gòu)成信息向量：m=(mk－1,mk－2,…,m0)信息多項式：m(x)=mk－1xk－1+mk－2xk－2+…+m0

碼多項式的高次冪部分等于m(x)，即：

C(x)=cn－1xn－1+…+cn－kxn－k+cn－k－1xn－k－1…+c1x+c0

=xn－km(x)+q(x)（q(x)的次數(shù)<n－k）校驗位多項式：q(x)由于碼多項式是生成多項式的倍式，所以：C(x)=xn－km(x)+q(x)=a(x)g(x)≡0（modg(x)）q(x)=C(x)+xn－km(x)≡xn－km(x)（modg(x)）2023/4/1789第八十九頁，共139頁。4.系統(tǒng)循環(huán)碼7.1循環(huán)碼(1)系統(tǒng)循環(huán)碼構(gòu)成循環(huán)碼的系統(tǒng)碼形式為：C(x)=xn－km(x)+

(xn－km(x)modg(x))

系統(tǒng)循環(huán)碼構(gòu)造過程步驟信息多項式乘xn－k：

xn－km(x)

對xn－km(x)求余式：q(x)≡xn－km(x)(modg(x))

求碼多項式：C(x)=xn－km(x)+(xn－km(x)modg(x))=xn－km(x)+q(x)(2)舉例在由g(x)=x4+x3+x2+1生成的(7,3)循環(huán)碼中，求信息組m=(101)的對應(yīng)碼多項式。2023/4/1790第九十頁，共139頁。4.系統(tǒng)循環(huán)碼7.1循環(huán)碼例：(7,3)循環(huán)碼生成多項式是g(x)=x4+x3+x2+1，用式

C(x)=xn-km(x)+q(x)產(chǎn)生系統(tǒng)循環(huán)碼。解：先以輸入信息m=(011)即m(x)=(x+1)為例，①.xn-km(x)=x4(x+1)=x5+x4

②.(x5+x4)除以(x4+x3+x2+

1)，得余式(x3+x)③.C(x)=xn-km(x)

+q(x)＝(x5+x4)+(x3+x),對應(yīng)碼矢(0111010)。依次將(000)…(111)代入，可得全部碼矢如表2。信息矢量m(m2,m1,m0)碼矢量(c6c5c4c3c2c1c0)000001010011100101110111表1(7,3)循環(huán)碼碼集表2(7,3)系統(tǒng)循環(huán)碼信息矢量m(m2,m1,m0)碼矢量(c6c5c4c3c2c1c0)00000101001110010111011101001112023/4/1791第九十一頁，共139頁。5.多項式的運算電路7.1循環(huán)碼(1)多項式加法電路多項式a(x)=anxn+an－1xn－1+…+a1x+a0表示的是時間序列a=(an,an－1,…,a1,a0)，因此多項式的計算表現(xiàn)為對時間序列的操作；對二進制多項式系數(shù)的基本操作為模2加和模2乘；電路圖運算符號的意義：2023/4/1792第九十二頁，共139頁。7.1循環(huán)碼5.多項式的運算電路(1)多項式加法電路

A(x)與B(x)的相加電路2023/4/1793第九十三頁，共139頁。7.1循環(huán)碼5.多項式的運算電路(2)多項式乘法電路多項式乘以x等價為時間序列a

延遲一位；多項式a(x)與多項式

g(x)的乘等價為a(x)的不同位移后的相加：a(x)g(x)=a(x)(g1(x)+g2(x))=a(x)g1(x)+a(x)g2(x)多項式乘法電路：設(shè)多項式的低位在前，電路中所有寄存器初態(tài)為0。2023/4/1794第九十四頁，共139頁。7.1循環(huán)碼5.多項式的運算電路(2)多項式乘法電路2023/4/1795第九十五頁，共139頁。7.1循環(huán)碼5.多項式的運算電路(3)多項式除法電路當(dāng)g(x)=1，多項式a(x)模g(x)的余式為0，電路如圖所示。2023/4/1796第九十六頁，共139頁。7.1循環(huán)碼5.多項式的運算電路(3)多項式除法電路當(dāng)g(x)是單向式g(x)=xk，a(x)模g(x)余式的次數(shù)小于k，進入電路的輸入順序為an,an－1,…,a1,a0。a(x)≡ak－1xk－1+ak－2xk－2+…+a1x+a0(modxk)

運算電路如圖所示。2023/4/1797第九十七頁，共139頁。7.1循環(huán)碼5.多項式的運算電路(3)多項式除法電路由于xk≡1

mod(x+1),k=0,1,2,…。若a(x)的次數(shù)為n，則：a(x)=

an－1+an－2+…+a1+a0（mod(x+1)）≡q0（mod2）運算電路如圖所示：2023/4/1798第九十八頁，共139頁。7.1循環(huán)碼5.多項式的運算電路(3)多項式除法電路同樣由長除法得：

運算電路如圖所示：2023/4/1799第九十九頁，共139頁。7.1循環(huán)碼5.多項式的運算電路(3)多項式除法電路一般的多項式模g(x)=grxr+g