信息與編碼編碼13課件

第七章線性碼（二）7/6/20231第七章線性碼（二）本節(jié)主要介紹線性碼理論的一些基本知識(shí)，主要內(nèi)容包括：線性碼的譯碼方法線性碼的重量分布7/6/20232第三節(jié)線性碼的譯碼方法第三節(jié)線性碼的譯碼方法應(yīng)用線性碼的校驗(yàn)矩陣，我們可以獲得一種非常有效的線性碼的譯碼方法。下面我們來介紹這種方法，即線性碼的標(biāo)準(zhǔn)陣譯碼方法。為此，我們首先介紹一個(gè)概念。定義7.3.1

設(shè)L是一個(gè)q元[n,k]線性碼，H為它的校驗(yàn)矩陣。對(duì)任意，稱為x的伴隨式，記為S(x)。顯然，設(shè)為H的行向量，則7/6/20233第三節(jié)線性碼的譯碼方法如果是一個(gè)線性碼，則V(n,q)關(guān)于L的商空間定義為。集合稱為L的陪集。商空間是Fq上的向量空間，它們的運(yùn)算定義如下：

a(x+L)=ax+L,(x+L)+(y+L)=(x+y)+L.而且x+L=y+L充分必要條件是。7/6/20234第三節(jié)線性碼的譯碼方法定理7.3.1

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

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

7/6/20236第三節(jié)線性碼的譯碼方法表中的第一行為L中的所有碼字，在V(n,q)選取一個(gè)不在第一行且具有最小重量的字a1，與第一行的每一個(gè)字相加得到第二行，它們構(gòu)成a1+L。一般地，選取一個(gè)不在前i行中且具有最小重量的字ai，與第一行的每一個(gè)字相加得到i+1行，它們構(gòu)成ai

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

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

.7/6/20238第三節(jié)線性碼的譯碼方法例7.3.1設(shè)L是一個(gè)二元[4,2]線性碼，它的生成矩陣把G的第二行加到第一行，得到L的一個(gè)標(biāo)準(zhǔn)型的生成矩陣7/6/20239第三節(jié)線性碼的譯碼方法L的校驗(yàn)矩陣為L的標(biāo)準(zhǔn)陣為7/6/202310第三節(jié)線性碼的譯碼方法如果x=1100是收到的字，查上表可知，1100譯成1110。由陪集頭和它們的伴隨式列表如下：如果收到的字x=0001，計(jì)算它的伴隨式xHT=01查上表知，它的陪集頭為0100，因此，x被譯為

0001-0100=0101。

7/6/202311§7.4線性碼的重量分布值得注意的是，對(duì)于一個(gè)q元[n,k]線性碼，當(dāng)n,k不是很大時(shí)，這種方法很有效。但當(dāng)n,k很大時(shí)，工作量相當(dāng)大，這種譯碼方法的效率不很高?！?.4線性碼的重量分布

在本節(jié)里，我們將要討論線性碼的某種結(jié)構(gòu)，并對(duì)線性碼和它的對(duì)偶碼建立一種聯(lián)系，這就是我們將要重點(diǎn)介紹的MacWilliams恒等式。

7/6/202312§7.4線性碼的重量分布設(shè)L是一個(gè)q元[n,k]線性碼，Ai表示L中重量等于i的碼字個(gè)數(shù)，我們稱為L的重量分布，而稱多項(xiàng)式稱為L的重量分布多項(xiàng)式。顯然，7/6/202313§7.4線性碼的重量分布例7.4.1(1)設(shè)L是二元[3,2]線性碼，

L={000,011,101,110}.其對(duì)偶碼

L和的重量分布多項(xiàng)式分別為(2)對(duì)于二元線性碼L={00,11},其對(duì)偶碼即L是自對(duì)偶的。因此，7/6/202314§7.4線性碼的重量分布一般來講，對(duì)給定的碼確定它的重量分布是一件困難的事件，但是對(duì)于線性碼，MacWilliams恒等式使線性碼L和它的對(duì)偶的重量分布建立了一種特殊的關(guān)系。我們下面主要介紹二元線性碼的MacWilliams恒等式.引理7.4.1

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

但，則對(duì)于任意，碼L中使x·y等于0和1的碼字個(gè)數(shù)相等。7/6/202315§7.4線性碼的重量分布引理7.4.2

設(shè)L是二元[n,k]線性碼，,則引理7.4.3

設(shè)，則7/6/202316§7.4線性碼的重量分布定理7.4.1(二元線性碼的MacWilliams恒等式)設(shè)L是一個(gè)二元[n,k]線性碼，是它的對(duì)偶碼，則定理7.4.2(q元線性碼的MacWilliams恒等式)設(shè)L是一個(gè)二元[n,k]線性碼，是它的對(duì)偶碼,則7/6/202317§7.4線性碼的重量分布例7.4.2把定理7.4.1應(yīng)用到例7.