信息論與編碼民大循環(huán)碼1第1頁，共18頁，2023年，2月20日，星期日 循環(huán)碼的概念： 循環(huán)性是指任一碼組字循環(huán)一位后仍然是該編碼中的一個碼字。例：一種(7,3)循環(huán)碼的全部碼字如下 表中第2碼字向右移一位即得到第5碼字；第5碼字向右移一位即得到第7碼字。碼組編號信息位監(jiān)督位碼組編號信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a010000000510010112001011161011100301011107110010140111001811100102第2頁，共18頁，2023年，2月20日，星期日一般情況 若(an-1

an-2…a0)是循環(huán)碼的一個碼字，則循環(huán)移位后的碼字： (an-2

an-3…a0

an-1) (an-3

an-4…an-1

an-2) …… (a0

an-1…a2

a1)仍然是該編碼中的碼字。多項式表示法 一個長度為n的碼字(an-1

an-2…a0)可以表示成

上式中x的值沒有任何意義，僅用它的冪代表碼元的位置。 例：碼字1100101可以表示為3第3頁，共18頁，2023年，2月20日，星期日循環(huán)碼的運算整數(shù)的按模運算 在整數(shù)運算中，有模n運算。例如，在模2運算中，有 1+1=20(模2)， 1+2=31(模2)，23=60(模2)等等。 一般說來，若一個整數(shù)m可以表示為 式中，Q為整數(shù)，則在模n運算下，有

m

p(模n) 所以，在模n運算下，一個整數(shù)m等于它被n除得的余數(shù)。4第4頁，共18頁，2023年，2月20日，星期日碼多項式的按模運算 若任意一個多項式F(x)被一個n次多項式N(x)除，得到商式Q(x)和一個次數(shù)小于n的余式R(x)，即 則在按模N(x)運算下，有 這時，碼多項式系數(shù)仍按模2運算。 例1：x3被(x3+1)除，得到余項1，即 例2： 因為

x

x3+1x4+x2+1

x4+x

x2+x+1 在模2運算中加法和減法一樣。5第5頁，共18頁，2023年，2月20日，星期日循環(huán)碼的數(shù)學表示法 在循環(huán)碼中，設T(x)是一個長度為n的碼字，若 則T(x)也是該編碼中的一個碼字。 [證]設一循環(huán)碼為 則有 上式中的T(x)正是碼組T(x)向左循環(huán)移位i次的結果。 例：一循環(huán)碼為1100101，即 若給定i=3，則有 上式對應的碼組為0101110，它正是T(x)向左移3位的結果。結論：一個長為n的循環(huán)碼必定為按模(xn+1)運算的一個余式。6第6頁，共18頁，2023年，2月20日，星期日循環(huán)碼的生成如果有了生成矩陣G，就可以由k個信息位得出整個碼字A： 例:(7,4)碼 式中， 生成矩陣G的每一行都是一個碼組。因此，若能找到k個已知的碼字，就能構成矩陣G。如前所述，這k個已知碼組必須是線性不相關的。在循環(huán)碼中，一個(n,k)碼有2k個不同的碼字。若用g(x)表示其中前(k-1)位皆為“0”的碼字，則g(x)，xg(x)，x2g(x)，，xk-1g(x)都是碼組，而且這k個碼組是線性無關的。因此它們可以用來構成此循環(huán)碼的生成矩陣G。7第7頁，共18頁，2023年，2月20日，星期日在循環(huán)碼中除全“0”碼組外，再沒有連續(xù)k位均為“0”的碼組。否則，在經(jīng)過若干次循環(huán)移位后將得到k位信息位全為“0”，但監(jiān)督位不全為“0”的一個碼組。這在線性碼中顯然是不可能的。因此，g(x)必須是一個常數(shù)項不為“0”的(n-k)次多項式，而且這個g(x)還是這種(n,k)碼中次數(shù)為(n–k)的唯一一個多項式。因為如果有兩個，則由碼的封閉性，把這兩個相加也應該是一個碼組，且此碼組多項式的次數(shù)將小于(n–k)，即連續(xù)“0”的個數(shù)多于(k–1)。顯然，這是與前面的結論矛盾的。我們稱這唯一的(n–k)次多項式g(x)為碼的生成多項式。一旦確定了g(x)，則整個(n,k)循環(huán)碼就被確定了。8第8頁，共18頁，2023年，2月20日，星期日因此，循環(huán)碼的生成矩陣G可以寫成例：

上表中的編碼為(7,3)循環(huán)碼，n=7,k=3,n–k=4，其中唯一的一個(n–k)=4次碼多項式，且前(k-1)=2位皆為“0”的碼字是第二碼字0010111，與它對應的碼多項式，即生成多項式，為

g(x)=x4+x2+x+1。碼組編號信息位監(jiān)督位碼組編號信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a010000000510010112001011161011100301011107110010140111001811100109第9頁，共18頁，2023年，2月20日，星期日 g(x)=x4+x2+x+1即“10111” 將此g(x)代入上矩陣，得到 或 上式不符合G=[IkQ]形式，所以它不是標準生成矩陣。但它經(jīng)過線性變換后，不難化成標準陣。 此循環(huán)碼的碼字多項式表示式T(x)： 上式表明，所有碼字多項式T(x)都能夠被g(x)整除，而且任意一個次數(shù)不大于(k–1)的多項式乘g(x)都是碼多項式。10第10頁，共18頁，2023年，2月20日，星期日尋求碼生成多項式因為任意一個循環(huán)碼T(x)都是g(x)的倍式，故它可以寫成 T(x)=h(x)g(x) 而生成多項式g(x)本身也是一個碼組，即有

T

(x)=g(x) 由于碼字T

(x)是一個(n–k)次多項式，故xkT

(x)是一個n次多項式。由 可知，xk

T

(x)在模(xn+1)運算下也是一個碼組，所以有 上式左端分子和分母都是n次多項式，故相除的商式Q(x)=1。因此，上式可以寫成11第11頁，共18頁，2023年，2月20日，星期日將T(x)=h(x)g(x)和T

(x)=g(x)代入 化簡后，得到上式表明，生成多項式g(x)應該是(xn+1)的一個因子。例：(x7+1)可以分解為 為了求出(7,3)循環(huán)碼的生成多項式g(x)，需要從上式中找到一個(n–k)=4次的因子。這樣的因子有兩個，即 以上兩式都可以作為生成多項式。 選用的生成多項式不同，產(chǎn)生出的循環(huán)碼碼字也不同。12第12頁，共18頁，2023年，2月20日，星期日循環(huán)碼的編碼方法用xn-k乘m(x)。這一運算實際上是在信息碼后附加上(n–k)個“0”。例如，信息碼為110，它寫成多項式為m(x)=x2+x。當n–k=7–3=4時，xn-km(x)=x4(x2+x)=x6+x5，它表示碼組1100000。用g(x)除xn-km(x)，得到商Q(x)和余式r(x)，即有 例：若選定g(x)=x4+x2+x+1，則有 上式是用碼多項式表示的運算。它和下式等效：編出的碼字T(x)為：T(x)=xn-km(x)+r(x) 在上例中，T(x)=1100000+101=1100101 13第13頁，共18頁，2023年，2月20日，星期日循環(huán)碼的解碼方法在檢錯時：當接收碼字沒有錯碼時，接收碼組R(x)必定能被g(x)整除，即下式 中余項r(x)應為零；否則，有誤碼。當接收碼組中的錯碼數(shù)量過多，超出了編碼的檢錯能力時，有錯碼的接收碼組也可能被g(x)整除。這時，錯碼就不能檢出了。在糾錯時：用生成多項式g(x)除接收碼組R(x)，得出余式r(x)。按照余式r(x)，用查表的方法或計算方法得出錯誤圖樣E(x)。從R(x)中減去E(x)，便得到已經(jīng)糾正錯碼的原發(fā)送碼組T(x)。14第14頁，共18頁，2023年，2月20日，星期日BCH碼BCH碼是能夠糾正多個隨機錯碼的循環(huán)碼。BCH碼分為兩類：本原BCH碼和非本原BCH碼。本原BCH碼：碼長n=2m–1(m

3，任意正整數(shù))，它的生成多項式g(x)中含有最高次數(shù)為m次的本原多項式；非本原BCH碼：碼長n是(2m–1)的一個因子，它的生成多項式g(x)中不含有最高次數(shù)為m的本原多項式。BCH碼的工程設計：可以用查表法找到所需的生成多項式。 例：二進制非本原BCH碼的生成多項式系數(shù) 表中g(x)是用8進制數(shù)字表示的；t為糾錯能力。nktg(x)nktg(x)1721233341912122221223247271663534351456647133476565732453404652444307335710761354300067171777353715第15頁，共18頁，2023年，2月20日，星期日常用BCH碼：戈萊(Golay)碼：(23,12)非本原BCH碼，它能糾正3個隨機錯碼，并且容易解碼。擴展BCH碼(n+1,k)：BCH碼的長度為奇數(shù)。在應用中，為了得到偶數(shù)長度的碼，并增大檢錯能力，可以在BCH碼生成多項式中乘上一個因式(x+1)，從而得到擴展BCH碼(n+1,k)。擴展BCH碼已經(jīng)不再具有循環(huán)性。擴展戈萊碼(24,12)：其最小碼距為8，碼率為1/2，能夠糾正3個錯碼和檢測4個錯碼。16第16頁，共18頁，2023年，2月20日，星期日幾種二進制分組碼的性能比較2PSK漢明碼(7,4)t=1漢明碼(31,26)t=1擴展戈萊碼(24,12)t=3BCH碼(127,64)t=10Eb/n0(dB)Pe17第17頁，共18頁，2023年，2月20日，星期日RS碼RS碼：是q進制BCH碼的一個特殊子類，并且具有很強的糾錯能力。RS碼的參數(shù)：碼長n=q–1=m(2m