線性分組編碼第一頁，共四十六頁，2022年，8月28日內(nèi)容提要線性分組碼概述校正子最小距離檢測和糾錯能力標準陣BSC上的漏檢誤碼率SPC，重復(fù)碼，對偶碼第二頁，共四十六頁，2022年，8月28日線性分組碼概述假設(shè)信源輸出的信息比特是一串二進制0和1分組碼將其分割為固定長度為k的消息分組（messageblock）每個分組記作u，故共有2k個不同的消息分組編碼規(guī)則按照一定的規(guī)則將輸入u映射為二進制n維向量v，n>k，v是u的碼字或碼向量，有2k種不同的碼字，這些碼字的集合叫做一個分組碼v和u之間是一一對應(yīng)的當n和k很大時，編碼器要存儲這種對應(yīng)關(guān)系代價很高，除非這種對應(yīng)關(guān)系有規(guī)律利用（線性？）第三頁，共四十六頁，2022年，8月28日線性分組碼，linearblockcodes定義：（n,k）分組碼，當且僅當其全部碼字構(gòu)成域GF(2)上所有n維向量組成的向量空間的一個k維子空間時被稱為(n,k)線性碼一個二進制分組碼是線性的充要條件是任意兩個碼字的模2和仍是該分組碼中的一個碼字（模2和運算封閉）一個(n,k)線性碼C是所有二進制n為向量構(gòu)成的向量空間Vn的一個k維子空間，故可在Vn中找到k個獨立的碼字g1,g2,…,gk-1做為基，用來表示C中任意一個碼字第四頁，共四十六頁，2022年，8月28日線性分組碼用這k個基為行向量構(gòu)成矩陣Gkxn(1)設(shè)是帶編碼的信息序列，則對應(yīng)的碼字為：

G的行生成或張成（span）線性碼C，故G稱為生成矩陣。線性分組碼C的任何k個基都可以獲得一個生成矩陣G，故編碼器只需要存儲一組基就可以依據(jù)輸入的信息序列得到碼字第五頁，共四十六頁，2022年，8月28日(7,4)線性分組碼例子u=(1101)是帶編碼的信息序列，其對應(yīng)碼字為：第六頁，共四十六頁，2022年，8月28日具有系統(tǒng)結(jié)構(gòu)的線性分組碼下圖顯示分組碼的系統(tǒng)結(jié)構(gòu)，包括冗余校驗部分和消息部分消息部分包括k個未經(jīng)改變的原始消息冗余校驗部分包括n-k個奇偶校驗位，這些位是信息位的線性和稱為線性系統(tǒng)分組碼第七頁，共四十六頁，2022年，8月28日線性系統(tǒng)分組碼

(2)一個線性系統(tǒng)分組碼可由上述kxn的矩陣G來描述，若記k階單位陣為Ik，則有G=[P

Ik]，則的碼字為：，v的分量：碼字v的右邊就是待編碼信息序列u碼字v的左邊就是待編碼信息序列u的線性和第八頁，共四十六頁，2022年，8月28日奇偶校驗矩陣對任何由k個線性獨立的行向量組成的kxn矩陣G，都存在一個有n-k個線性獨立的行向量組成的(n-k)xn矩陣H，使得G的行空間的任意向量與H的行向量正交，且任何與H正交的向量都在G的行空間內(nèi)。故：一個n維向量v是G生成的碼C中的一個碼字，當且僅當碼C稱為H的零空間，H稱為碼的奇偶校驗矩陣矩陣H的行向量有2n-k中組合方式，構(gòu)成(n,n-k)線性碼Cd，這個碼是G的零空間Cd是C的對偶碼，dualcode一個線性碼的奇偶校驗矩陣是其對偶碼的生成矩陣第九頁，共四十六頁，2022年，8月28日奇偶校驗矩陣若(n,k)線性碼的生成矩陣公式(2)所示，則其奇偶校驗矩陣為公式(3)(3)令hi表示H的任意一行向量，可以證明公式(2)中的行向量gj與hi的內(nèi)積為0，即也就是第十頁，共四十六頁，2022年，8月28日小結(jié)對任何一個(n,k)線性碼C，存在一個生成矩陣Gkxn，其行空間為碼C存在一個矩陣H(n-k)xn使得當是，n維向量v是C中的碼字第十一頁，共四十六頁，2022年，8月28日校正子與差錯檢測考慮一個(n,k)線性碼C，其生成矩陣Gkxn，奇偶校驗矩陣H，令表示要通過有噪聲信道傳輸?shù)拇a字，表示信道輸出端接收到得碼字，由于噪聲的存在，v和r可能不一樣。向量和是一個n維向量，e被稱為差錯向量或錯誤模式，它直接指出了接收向量r不同于傳輸碼字v的位置，e中分量1表示信道噪聲引起的傳輸錯誤第十二頁，共四十六頁，2022年，8月28日接收端的處理

接收端接收到r，但是不知道e，也不知道v譯碼器必須先確定r是否包含傳輸差錯若檢測出錯誤，則采取措施FEC或ARQ第十三頁，共四十六頁，2022年，8月28日校正子syndrome接收到r之后，譯碼器計算校正子s：

(4)當且僅當r是碼字時，s=0；當且僅當r不是碼字時，；故當時，r不是碼字，檢測出存在錯誤；s=0時，認為r就是傳輸碼字v也有可能發(fā)生s=0時，傳輸發(fā)生錯誤，此時錯誤模式e和某個非零碼字相同，此時r是兩個碼字的和，依然是個碼字；這類錯誤稱為漏檢錯誤模式，譯碼器產(chǎn)生譯碼差錯第十四頁，共四十六頁，2022年，8月28日校正子依據(jù)公式(3)(4)可以得到：從上述式子看出，校正子s就是接收到的消息位重新計算校驗位和接收到的校驗位的向量和第十五頁，共四十六頁，2022年，8月28日校正子上式子給出了校正子s和錯誤模式e的關(guān)系，若H的表示如公式(3)所示系統(tǒng)形式，則有校正子為錯誤模式的線性組合：第十六頁，共四十六頁，2022年，8月28日小結(jié)找到錯誤模式e，利用v=r+e就可將v視為實際傳輸?shù)拇a字，但是錯誤模式e不容易找到，需要在2k個錯誤模式（待證明）中找到唯一正確的錯誤模式第十七頁，共四十六頁，2022年，8月28日例子:(7,4)線性分組碼H如右，設(shè)v=(1001011),r=(1001001)接收到r后，計算校正子s=r·HT=(111)接下來確定差錯向量e，由s=e·HT，三個線性方程，7個變量ei，共有24個解作為錯誤模式e，選擇具有最少非零分量（即最有可能）的錯誤模式e=(0000010)，從而得到v=r+e=(1001011)(7,4)線性分組碼能糾正7位范圍內(nèi)任意單個差錯，即若傳輸過程中一個碼字最多只有一位被噪聲改變，則接收端能確定真正的錯誤模式并糾錯第十八頁，共四十六頁，2022年，8月28日分組碼的最小距離刻畫分組碼的重要參數(shù)，最小距離，決定了碼檢測隨機錯誤和糾正隨機錯誤的能力設(shè)v是二進制n維向量，則v的漢明重量或重量就是值為1的分量的個數(shù)，用w(v)表示若v1和v2是兩個二進制n維向量，其漢明距離或距離就是兩個不同位數(shù)的個數(shù)，記作d(v1,v2)漢明距離滿足三角不等式，即漢明距離滿足給定分組碼C，可計算任意兩個不同碼字之間的漢明距離，這些距離中的最小值稱為碼C的最小距離dmin第十九頁，共四十六頁，2022年，8月28日另一種描述：故有結(jié)論1：線性分組碼的最小距離就是其非零碼的最小重量分組碼的最小距離第二十頁，共四十六頁，2022年，8月28日分組碼的最小距離(n,k)線性碼C，其奇偶校驗矩陣H，對任意重量為l的碼字，存在H的l個列向量，滿足這l個列向量的和為0；反之，若存在H的l個列向量其和為0，則存在重量為l的碼字。證明：記H=[h0,h1,…,hn-1],v=(v0,v1,…,vn-1)的重量為l，中有l(wèi)項非零，其和為0。定理前半部分得證，后半部分略。不可能有重量為2的碼字？？若H中少于d個列向量的和不等于0，則碼的最小重量至少為dH中列向量相加之和為0所需要的最小列向量個數(shù)就是碼的最小重量第二十一頁，共四十六頁，2022年，8月28日分組碼的檢錯能力設(shè)錯誤模式e的重量，即接收碼字和傳輸碼字的距離為d(r,v)=l分組碼C的最小距離為dmin，C中任意兩個不同碼字至少有dmin處不同當l<dmin時，我們說這種錯誤能檢測出來，即之多dmin-1個差錯可以檢測出來對于等于或多于dmin個錯誤的錯誤模式，無法檢測，故稱最小距離為dmin的分組碼錯誤檢測能力是dmin-1第二十二頁，共四十六頁，2022年，8月28日分組碼的檢錯能力事實上，(n,k)線性分組碼除了2k個碼字，其它的2n-2k個向量都是錯誤模式，都可被檢測出來若傳輸過程中噪聲把一個碼字變成另一個不同的碼字，此時檢測不出錯誤來，出現(xiàn)漏檢，只有2k-1個非零碼字可能被漏檢第二十三頁，共四十六頁，2022年，8月28日分組碼的檢錯能力(n,k)線性碼C，Ai表示C中重量為i的碼字個數(shù)，A0,A1,…,An稱為C的重量分布求BSC的漏檢率：漏檢的錯誤模式就是非零碼字，碼字中的分量1表示出錯，概率為p第二十四頁，共四十六頁，2022年，8月28日分組碼的糾錯能力(n,k)線性分組碼C，最小距離為dmin，其隨機差錯糾正能力為證明：設(shè)v和r分別是傳輸碼字和接受向量，x為任意C中其它碼字，有三角不等式成立：設(shè)傳輸時發(fā)生l個錯誤，即d(v,r)=l,而故得到,若即任意碼字和接收向量的距離大于t

上述證明表明當

時，，即接收向量與任意碼字的距離大于接收向量與傳輸向量的距離與之相反l>t時，存在其它碼字較傳輸碼字與接收向量更接近，糾錯時會出錯第二十五頁，共四十六頁，2022年，8月28日分組碼的檢錯和糾錯能力分組碼的檢錯和糾錯能力由碼的最小距離決定構(gòu)造碼時盡可能使得最小距離大可將(n,k)線性分組碼記為(n,k,dmin)第二十六頁，共四十六頁，2022年，8月28日標準陣和校正子譯碼(n,k)線性碼C，任何碼字通過有噪信道傳輸，接收向量r必然是GF(2)上2n個n維向量中一個接收端的任何譯碼方法都是一種劃分規(guī)則，該規(guī)則將2n個可能的接收向量劃分為2k個互不相交的子集D1,D2,…,D2k,一個碼字對應(yīng)一個子集若接收向量位于與傳輸碼字對應(yīng)的子集Di中，則可正確譯碼如何構(gòu)造這種一個子集對應(yīng)且僅對應(yīng)一個碼字的子集劃分方法？第二十七頁，共四十六頁，2022年，8月28日標準陣的構(gòu)造將所有2k個碼字排成一行，全零碼排在第一個從2n-2k個非碼向量構(gòu)成的集合E中取出一個e2置于全零碼正下方，對任意一個碼字v，將v+e2置于v的正下方，這樣構(gòu)造出第二行；從E中刪除第二行出現(xiàn)的向量，得到更新的E重復(fù)步驟2、3，構(gòu)造第3，4，…，行，直到集合E為空同一行中任意兩個向量之和是C的碼字，因為：第二十八頁，共四十六頁，2022年，8月28日標準陣的性質(zhì)標準陣中同一行任意兩個n維向量互不相同，每個n維向量在標準陣中出現(xiàn)且僅出現(xiàn)一次證明:反證法證明第一部分，若有則，這不可能。第二部分證明（反證）：假設(shè)在l和m(l<m)行出現(xiàn)了同一個向量，即有這表明向量em在l行就已經(jīng)出現(xiàn)，并從E中刪除，故不可能在m行做為第一個出現(xiàn)，與標準陣構(gòu)造矛盾。第二十九頁，共四十六頁，2022年，8月28日標準陣與陪集標準陣有2n-k個互不相交的行，每行2k個元素，一行構(gòu)成碼C的一個陪集(coset)，每個陪集的第一個元素ei稱為陪集首或陪集代表元陪集中任何元素都可以為陪集首，陪集中元素不會改變，改變的只是次序二進制n維向量構(gòu)成的2n階群G，一個(n,k)線性分組碼是其2k階子群C，子群C的所有陪集構(gòu)成了G的一個劃分，如標準陣第三十頁，共四十六頁，2022年，8月28日標準陣：例子(6,3)線性碼令Dj表示標準陣的第j列，vj是碼字，ei是陪集首第三十一頁，共四十六頁，2022年，8月28日標準陣碼字vj通過有噪信道傳輸，若信道引起的錯誤模式是陪集首，則接收向量r在Dj中，此時接收向量可被正確譯碼為vj若錯誤模式?jīng)]有在陪集首中出現(xiàn)，則譯碼有誤假設(shè)錯誤模式x在第l行而非陪集首，不妨設(shè)在第i>1列，則x=el+vi，接收向量為r=vj+x=el+(vi+vj)=el+vs，接收向量出現(xiàn)在Ds中，r被譯碼為vs，出現(xiàn)譯碼錯誤故當且僅當錯誤模式是陪集首時譯碼是正確的，這些陪集首稱為可糾正錯誤模式第三十二頁，共四十六頁，2022年，8月28日每個(n,k)線性分組碼有糾正2n-k個錯誤模式的能力為使譯碼差錯最小，對給定信道，選擇最有可能出現(xiàn)的錯誤模式作為陪集首。對于BSC，重量小的錯誤模式比重量大的錯誤模式更容易發(fā)生若采用這種方式選擇陪集首，則每個陪集中，陪集首的重量最小在構(gòu)造標準陣時，在E中選擇陪集首時，選擇E中重量最小的，故能保證每個陪集中陪集首重量最小基于標準陣的譯碼就是最小距離譯碼，即最大似然譯碼第三十三頁，共四十六頁，2022年，8月28日陪集首的重量分布令表示重量為i的陪集首的個數(shù)，則稱為陪集首的重量分布若陪集首的重量分布已知，當且僅當錯誤模式不是陪集首時，會發(fā)生譯碼錯誤，故對轉(zhuǎn)移概率為p的BSC信道，誤碼率為：第三十四頁，共四十六頁，2022年，8月28日例子(6,3)線性分組碼陪集首的重量分布為（161000），故P(E)=1-(1-p)6-6p(1-p)5-p2(1-p)4當p=10-2時，P(E)=1.37x10-3線性碼能檢測出2n-2k中錯誤模式，但是僅能夠糾正2n-k種錯誤模式，在n較大時，能糾正的錯誤比能檢測到得錯誤少很多第三十五頁，共四十六頁，2022年，8月28日(n,k,dmin)線性分組碼C，所有重量不超過t的n維向量可用作碼C的標準陣的陪集首。若所有重量不超過t的n維向量都被用作碼C標準陣的陪集首，則至少有一個重量t+1的n維向量無法用于陪集首。其中證明：令x和y表示重量不大于t的兩個n維向量，有w(x+y)<=w(x)+w(y)<=2t<dmin,若x和y在同一陪集中（標準陣的同一行），則x+y就是碼字，其重量小于dmin，矛盾，故x和y不在同一陪集中。因此重量不大于t的n維向量均可做陪集首。設(shè)v是具有dmin的碼字，則存在x和y，滿足x+y=v及w(x)+w(y)=w(v)=dmin,若w(y)=t+1，則w(x)=t或t+1，取x為陪集首，則y就不能作為陪集首了，因為x和y在同一陪集中第三十六頁，共四十六頁，2022年，8月28日同一陪集的2k個n維向量有相同的校正子，不同的陪集有不同的校正子證明：標準陣第l行陪集，陪集首為el，則陪集中任意向量vi+el的校正子s=(vi+el)·HT=el·HT，這表明陪集中任何一個向量的校正子都等于陪集首的校正子。

若有el和ei是不同的兩個陪集首，若el·HT和ei·HT相等，即校正子相同，則有el·HT+ei·HT=0,即(el+ei)·HT=0，說明el+ei是碼字，矛盾。故兩個不同的陪集中不可能有相同的校正子。第三十七頁，共四十六頁，2022年，8月28日查表譯碼，校正子譯碼校正子是n-k維向量，從標準陣中知道有2n-k個不同的校正子，陪集和校正子之間有一一對應(yīng)關(guān)系。或者說陪集首（可糾正錯誤模式）和校正子之間有一一對應(yīng)關(guān)系。故可構(gòu)建一個由陪集首（可糾正錯誤模式）和校正子構(gòu)成的簡單譯碼表，在接收端存儲或電路實現(xiàn)之。接收端譯碼步驟：計算r的校正子s=r·HT確定于校正子s對應(yīng)的陪集首el，并假定el就是錯誤模式將接受碼字確定為v’=el+r適用于n-k較小第三十八頁，共四十六頁，2022年，8月28日例子:(7,4)線性碼若傳輸碼字v=1001011,接收向量r=1001111計算s=r·HT=011查表得到陪集首為e5=0000100計算v’=r+e5=1001011譯碼正確若v=0000000,r=1000100,出現(xiàn)兩個錯誤，計算s=111，譯碼結(jié)果為0000010，譯碼錯誤第三十九頁，共四十六頁，2022年，8月28日BSC上漏檢誤碼率(n,k)線性碼C，Ai表示C中重量為i的碼字個數(shù)，A0,A1,…,An稱為C的重量分布BSC的漏檢率：漏檢的錯誤模式就是碼字，碼字中的分量1表示出錯，概率為p線性碼C的重量分布與其對偶碼Cd的重量分布之間存在的關(guān)系可以計算Pu(E)的計算設(shè)B0,B1,…,Bn是其對偶碼Cd的重量分布分布的多項式表示為：（重量枚舉式）存在恒等式：(5)可選擇利用對偶碼的重量分布計算碼的重量分布第四十頁，共四十六頁，2022年，8月28日BSC上漏檢誤碼率

將z=p/(1-p)帶入碼C的重量枚舉式，有即(6)第四十一頁