信息與編碼編碼課件

第七章線性碼（二）9/27/20231第七章 線

性

碼（二）9/27/20232本節(jié)主要介紹線性碼理論的一些基本知識，主要內(nèi)容包括：線性碼的譯碼方法線性碼的重量分布第三節(jié)線性碼的譯碼方法第三節(jié)線性碼的譯碼方法應(yīng)用線性碼的校驗矩陣，我們可以獲得一種非常有

效的線性碼的譯碼方法。下面我們來介紹這種方法，即線性碼的標(biāo)準(zhǔn)陣譯碼方法。為此，我們首先介紹

一個概念。定義7.3.1

設(shè)L是一個q元[n,k]線性碼，H為它的校驗矩陣。對任意 ，稱

為x的伴隨式，記為S(x)。顯然，設(shè) 為H的行向量，則9/27/20233第三節(jié)線性碼的譯碼方法如果 是一個線性碼，則V(n,q)關(guān)于L的商空間定義為 。集合稱為L的陪集。商空間是Fq上的向量空間，它們的運算定義如下：a(x+L)=ax+L,(x+L)+(y+L)=(x+y)+L.而且x+L=y+L充分必要條件是

。10/21/20234第三節(jié)線性碼的譯碼方法定理7.3.1

設(shè)L是一個q元[n,k]線性碼，H是它的校驗矩陣，則 屬于同一個陪集的充分必要條件是它們的伴隨式相同。定理7.3.2

設(shè)L是一個線性碼，H是它的校驗矩陣，則最小距離譯碼等價于把收到的字x譯成碼字c=x-a，其中a是倍集x+L中具有最小重量的字，或a是與x具有相同伴隨式并且重量最小的字。10/21/20235第三節(jié)線性碼的譯碼方法上述譯碼方法可以用列表的形式描述如下：10/21/20236第三節(jié)線性碼的譯碼方法10/21/20237表中的第一行為L中的所有碼字，在V(n,q)選取一

個不在第一行且具有最小重量的字a1，與第一行的

每一個字相加得到第二行，它們構(gòu)成a1+L。一般地，選取一個不在前i行中且具有最小重量的字ai，與第

一行的每一個字相加得到i+1行，它們構(gòu)成ai

+L。此過程一直進行到表中包含V(n,q)中所有的字。上述列表稱為L的標(biāo)準(zhǔn)陣。第一列中的ai稱為陪集頭。如果收到的字x在表中的第j+1列，則x=cj+ai，對某個i。由于的ai取法，因此x譯成ci=x-ai，即是包含x的那一列中最上邊的碼字。這種譯碼方法稱為標(biāo)準(zhǔn)

陣譯碼。第三節(jié)線性碼的譯碼方法10/21/20238由于每一行可以由它的元素的伴隨式惟一決定，上述過程可以簡化。我們只需列出陪集頭和對應(yīng)的伴隨式。如果x是收到的字，計算它的伴隨式xHT，確定有相同伴隨式的陪集頭ai，則x被譯為c=x-ai。這種譯碼過程稱為伴隨式譯碼

.第三節(jié)線性碼的譯碼方法例7.3.1 設(shè)L是一個二元[4,2]線性碼，它的生成矩陣把G的第二行加到第一行，得到L的一個標(biāo)準(zhǔn)型的生成矩陣10/21/20239第三節(jié)線性碼的譯碼方法L的校驗矩陣為L的標(biāo)準(zhǔn)陣為10/21/202310第三節(jié)線性碼的譯碼方法如果x=1100是收到的字，查上表可知，1100譯成

1110。由陪集頭和它們的伴隨式列表如下：如果收到的字x=0001，計算它的伴隨式xHT=01查上表知，它的陪集頭為0100，因此，x被譯為0001-0100=0101。10/21/202311§7.4

線性碼的重量分布10/21/202312值得注意的是，對于一個q元[n,k]線性碼，當(dāng)n,k不是很大時，這種方法很有效。但當(dāng)

n,k很大時，工作量相當(dāng)大，這種譯碼方法的效率不很高?！?.4

線性碼的重量分布在本節(jié)里，我們將要討論線性碼的某種結(jié)構(gòu)，并對線性碼和它的對偶碼建立一種聯(lián)系，這

就是我們將要重點介紹的MacWilliams恒等式?！?.4

線性碼的重量分布設(shè)L是一個q元[n,k]

線性碼，Ai表示L中重量等于i的碼字個數(shù)，

我們稱

為L的重量分布，而稱多項式稱為L的重量分布多項式。顯然，10/21/202313§7.4

線性碼的重量分布例7.4.1

(1) 設(shè)L是二元[3,2] 線性碼，L={000,011,101,110}.其對偶碼L和 的重量分布多項式分別為(2)對于二元線性碼L={00,11},其對偶碼即L是自對偶的。因此，10/21/202314§7.4

線性碼的重量分布一般來講，對給定的碼確定它的重量分布是一件困難的事件，但是對于線性碼，MacWilliams恒等式使線性碼L和它的對偶的重量分布建立了一種特殊

的關(guān)系。我們下面主要介紹二元線性碼的

MacWilliams恒等式.引理7.4.1

設(shè)L是一個二元[n,k]線性碼，

但，則對于任意 ，碼L中使x·y等于0和1的碼字個數(shù)相等。10/21/202315§7.4

線性碼的重量分布引理7.4.2

設(shè)L是二元[n,k]線性碼，,則引理7.4.3設(shè)，則10/21/202316§7.4

線性碼的重量分布定理7.4.1(二元線性碼的MacWilliams恒等式)設(shè)L是一個二元[n,k]

線性碼， 是它的對偶碼，則定理7.4.2

(q元線性碼的MacWilliams恒等式)設(shè)L是一個二元[n,k]線性碼，是它的對偶碼,則10/21/202317§7.4

線性碼的重量分