第六章編碼理論的基本知識（二）11/22/20221

第六章編碼理論的基本知識（二）11/21/20221第六章編碼理論的基本知識2本節(jié)主要介紹編碼理論的一些基本知識，主要內(nèi)容包括：編碼理論的基本問題置換碼碼的重量碼的界11/22/20222第六章編碼理論的基本知識2本節(jié)主要介紹編碼理論的一些基本知識第三節(jié)編碼理論的基本問題在上文中我們已經(jīng)給出，一個(q,n,M)碼的主要指標(biāo)是：碼率和最小距離d=d(C)。因此，編碼理論的基本問題是在以下條件下構(gòu)造q元的(n,M,d)碼：(1)在碼率R固定的條件下，使最小距離d盡量大。(2)在最小距離d固定的條件下，使碼率R盡量大。如果碼長n固定，那么以上編碼問題就化為：(3)在碼元數(shù)M固定的條件下，使最小距離d盡量大。(4)在最小距離d固定的條件下，使碼元數(shù)M盡量大。11/22/20223第三節(jié)編碼理論的基本問題在上文中我們已經(jīng)給出，一個(q,n,第三節(jié)編碼理論的基本問題這里d盡量大意味著可以糾正更多的差錯，而M盡量大意味著可以發(fā)送更多的信息。我們以下定義Aq(n,d)為d固定，M為最大的q元(n,M,d)碼。編碼理論的基本問題之一就是討論對Aq(n,d)的值的分析。對于d=1和d=n，有如下結(jié)果。定理6.3.1對于任意n>1,Aq(n,1)=q(n),Aq(n,n)=q.設(shè)A={a1,a2,…as}是任意有限集合，則從A到A的一個1-1映射σ，稱為A上的一個置換。11/22/20224第三節(jié)編碼理論的基本問題這里d盡量大意味著可以糾正更多的差第三節(jié)編碼理論的基本問題定義6.3.1關(guān)于碼的置換有兩種，一種是關(guān)于下標(biāo)集合的置換，另一種是關(guān)于信號字母表的置換。我們分別記之為我們分別稱這兩種類型的置換為σ1型與σ2型的置換，或簡稱換位型與換元型置換。11/22/20225第三節(jié)編碼理論的基本問題定義6.3.1關(guān)于碼的置換有兩種，第三節(jié)編碼理論的基本問題定義6.3.2由換位型與換元型的置換可產(chǎn)生換位型與換元型的碼，這就是對一個q元的(n,M)的碼C，對它可產(chǎn)生換位型與換元型的置換碼：(1)

換位型置換碼，也就是說對每個向量的坐標(biāo)進(jìn)行置換，如記為C中的任意碼元，它的坐標(biāo)位置上的置換為這時我們記并稱之為C的換位型置換碼。11/22/20226第三節(jié)編碼理論的基本問題定義6.3.2由換位型與換元型的置第三節(jié)編碼理論的基本問題(2)換元型置換碼，這時對每個坐標(biāo)位上的碼元符號進(jìn)行置換，我們記其中每個是換元型的置換。這時對每個它的碼元符號的置換為我們同樣記，并稱之為C的換元型置換碼。11/22/20227第三節(jié)編碼理論的基本問題(2)換元型置換碼，這時對每個坐標(biāo)位第三節(jié)編碼理論的基本問題如果把碼C按矩陣排列，每一個碼字為一行，那么C可排成一個的矩陣，我們記之為這時換位型置換等價于矩陣列的置換，而換元型置換等價于每一列中碼字符的置換。因此，在上述兩種運(yùn)算下，碼字之間距離保持不變。從而稱是C的等價碼，它們有相同的參數(shù)(n,M,d)以及可以糾正相同的錯誤。11/22/20228第三節(jié)編碼理論的基本問題如果把碼C按矩陣排列，每一個碼字為一第三節(jié)編碼理論的基本問題引理6.3.1如果0∈U，則U上任意一個q元(n,M,d)碼等價于一個包含零碼字0=0…0的q元(n,M,d)碼。例1三元碼

等價于碼長為3的三元重復(fù)碼，對此我們做換元置換為：是一個恒等變換，而取11/22/20229第三節(jié)編碼理論的基本問題引理6.3.1如果0∈U，則U上任第三節(jié)編碼理論的基本問題這時得到例2設(shè)二元(5,4,3)碼則C與C2等價11/22/202210第三節(jié)編碼理論的基本問題這時得到例2設(shè)二元(5,4,3)碼第三節(jié)編碼理論的基本問題此時在碼C的第三個位置上進(jìn)行置換，作其余的為恒等變換，那么然后把第三行和第四行交換，再把第二列和第四列交換，就得到碼C1。

11/22/202211第三節(jié)編碼理論的基本問題此時在碼C的第三個位置上進(jìn)行置換，作第三節(jié)編碼理論的基本問題現(xiàn)在確定Aq(5,3),設(shè)C為一個二元(5,M,3)碼，我們最大的M，易知C包含零碼字0=0…0，則其余碼字漢明勢必大于或等于3，漢明勢為4或5的碼字至多只有一個，分析知A2(5,3)≤3+1=4此時可以構(gòu)造C為11/22/202212第三節(jié)編碼理論的基本問題現(xiàn)在確定Aq(5,3),設(shè)C為一個二第三節(jié)編碼理論的基本問題由此可見，一般構(gòu)造Aq(n,d)的最優(yōu)碼是十分困難的，為此討論它的一些性質(zhì)。定義6.3.3設(shè)x∈V(n,q)，x的漢明勢又稱重量，這時記為w(x)，它們是x中非零位置的個數(shù)。碼的最小重量(簡稱為重量)定義為定義6.3.4設(shè)x=x1x2…xn和y=y1y2…yn

∈

V(n,2)，x和y的交定義為11/22/202213第三節(jié)編碼理論的基本問題由此可見，一般構(gòu)造Aq(n,d)的最第三節(jié)編碼理論的基本問題因此，中第i位置是非零的充分必要條件是x和y在第i個位置都是非零的。引理6.3.2

(1)對于所有的(2)對于所有的定理6.3.2設(shè)d為奇數(shù)，則二元(n,M,d)碼存在充分必要條件是二元(n+1,M,d+1)碼存在。11/22/202214第三節(jié)編碼理論的基本問題因此，中第i位置是非零的充分第三節(jié)編碼理論的基本問題推論6.3.1如果d是奇數(shù)，則。它等價于，如果d是偶數(shù)，則。例3由例2知，。因此。而且可由例2中的二元(5,4,3)碼構(gòu)造一個二元(6,4,4)碼:11/22/202215第三節(jié)編碼理論的基本問題推論6.3.1如果d是奇數(shù)，則第三節(jié)編碼理論的基本問題定義6.3.5設(shè)x∈V(n,q)，r為一非負(fù)整數(shù)，則中心在x、半徑為r的球定義為。引理6.3.3設(shè)x∈V(n,q)，則球中所含V(n,q)中向量的個數(shù)為11/22/202216第三節(jié)編碼理論的基本問題定義6.3.5設(shè)x∈V(n,q)第三節(jié)編碼理論的基本問題定理6.3.3(漢明界)q元(n,M,2t+1)碼滿足定義6.3.6設(shè)C是一個q元(n,M,2t+1)碼，如果則稱C為完備碼。11/22/202217第三節(jié)編碼理論的基本問題定理6.3.3(漢明界)q元(n第三節(jié)編碼理論的基本問題定理6.3.4(Gilbert-Varshamov界)存在的(n,M,d)碼，因此11/22/202218第三節(jié)編碼理論的基本問題定理6.3.4(Gilbert-Va第三節(jié)編碼理論的基本問題定理6.3.5(Singleton界)

Aq(n,d)≥qn-d+1。

11/22/202219第三節(jié)編碼理論的基本問題定理6.3.5(Singleton

第六章編碼理論的基本知識（二）11/22/202220

第六章編碼理論的基本知識（二）11/21/20221第六章編碼理論的基本知識2本節(jié)主要介紹編碼理論的一些基本知識，主要內(nèi)容包括：編碼理論的基本問題置換碼碼的重量碼的界11/22/202221第六章編碼理論的基本知識2本節(jié)主要介紹編碼理論的一些基本知識第三節(jié)編碼理論的基本問題在上文中我們已經(jīng)給出，一個(q,n,M)碼的主要指標(biāo)是：碼率和最小距離d=d(C)。因此，編碼理論的基本問題是在以下條件下構(gòu)造q元的(n,M,d)碼：(1)在碼率R固定的條件下，使最小距離d盡量大。(2)在最小距離d固定的條件下，使碼率R盡量大。如果碼長n固定，那么以上編碼問題就化為：(3)在碼元數(shù)M固定的條件下，使最小距離d盡量大。(4)在最小距離d固定的條件下，使碼元數(shù)M盡量大。11/22/202222第三節(jié)編碼理論的基本問題在上文中我們已經(jīng)給出，一個(q,n,第三節(jié)編碼理論的基本問題這里d盡量大意味著可以糾正更多的差錯，而M盡量大意味著可以發(fā)送更多的信息。我們以下定義Aq(n,d)為d固定，M為最大的q元(n,M,d)碼。編碼理論的基本問題之一就是討論對Aq(n,d)的值的分析。對于d=1和d=n，有如下結(jié)果。定理6.3.1對于任意n>1,Aq(n,1)=q(n),Aq(n,n)=q.設(shè)A={a1,a2,…as}是任意有限集合，則從A到A的一個1-1映射σ，稱為A上的一個置換。11/22/202223第三節(jié)編碼理論的基本問題這里d盡量大意味著可以糾正更多的差第三節(jié)編碼理論的基本問題定義6.3.1關(guān)于碼的置換有兩種，一種是關(guān)于下標(biāo)集合的置換，另一種是關(guān)于信號字母表的置換。我們分別記之為我們分別稱這兩種類型的置換為σ1型與σ2型的置換，或簡稱換位型與換元型置換。11/22/202224第三節(jié)編碼理論的基本問題定義6.3.1關(guān)于碼的置換有兩種，第三節(jié)編碼理論的基本問題定義6.3.2由換位型與換元型的置換可產(chǎn)生換位型與換元型的碼，這就是對一個q元的(n,M)的碼C，對它可產(chǎn)生換位型與換元型的置換碼：(1)

換位型置換碼，也就是說對每個向量的坐標(biāo)進(jìn)行置換，如記為C中的任意碼元，它的坐標(biāo)位置上的置換為這時我們記并稱之為C的換位型置換碼。11/22/202225第三節(jié)編碼理論的基本問題定義6.3.2由換位型與換元型的置第三節(jié)編碼理論的基本問題(2)換元型置換碼，這時對每個坐標(biāo)位上的碼元符號進(jìn)行置換，我們記其中每個是換元型的置換。這時對每個它的碼元符號的置換為我們同樣記，并稱之為C的換元型置換碼。11/22/202226第三節(jié)編碼理論的基本問題(2)換元型置換碼，這時對每個坐標(biāo)位第三節(jié)編碼理論的基本問題如果把碼C按矩陣排列，每一個碼字為一行，那么C可排成一個的矩陣，我們記之為這時換位型置換等價于矩陣列的置換，而換元型置換等價于每一列中碼字符的置換。因此，在上述兩種運(yùn)算下，碼字之間距離保持不變。從而稱是C的等價碼，它們有相同的參數(shù)(n,M,d)以及可以糾正相同的錯誤。11/22/202227第三節(jié)編碼理論的基本問題如果把碼C按矩陣排列，每一個碼字為一第三節(jié)編碼理論的基本問題引理6.3.1如果0∈U，則U上任意一個q元(n,M,d)碼等價于一個包含零碼字0=0…0的q元(n,M,d)碼。例1三元碼

等價于碼長為3的三元重復(fù)碼，對此我們做換元置換為：是一個恒等變換，而取11/22/202228第三節(jié)編碼理論的基本問題引理6.3.1如果0∈U，則U上任第三節(jié)編碼理論的基本問題這時得到例2設(shè)二元(5,4,3)碼則C與C2等價11/22/202229第三節(jié)編碼理論的基本問題這時得到例2設(shè)二元(5,4,3)碼第三節(jié)編碼理論的基本問題此時在碼C的第三個位置上進(jìn)行置換，作其余的為恒等變換，那么然后把第三行和第四行交換，再把第二列和第四列交換，就得到碼C1。

11/22/202230第三節(jié)編碼理論的基本問題此時在碼C的第三個位置上進(jìn)行置換，作第三節(jié)編碼理論的基本問題現(xiàn)在確定Aq(5,3),設(shè)C為一個二元(5,M,3)碼，我們最大的M，易知C包含零碼字0=0…0，則其余碼字漢明勢必大于或等于3，漢明勢為4或5的碼字至多只有一個，分析知A2(5,3)≤3+1=4此時可以構(gòu)造C為11/22/202231第三節(jié)編碼理論的基本問題現(xiàn)在確定Aq(5,3),設(shè)C為一個二第三節(jié)編碼理論的基本問題由此可見，一般構(gòu)造Aq(n,d)的最優(yōu)碼是十分困難的，為此討論它的一些性質(zhì)。定義6.3.3設(shè)x∈V(n,q)，x的漢明勢又稱重量，這時記為w(x)，它們是x中非零位置的個數(shù)。碼的最小重量(簡稱為重量)定義為定義6.3.4設(shè)x=x1x2…xn和y=y1y2…yn

∈

V(n,2)，x和y的交定義為11/22/202232第三節(jié)編碼理論的基本問題由此可見，一般構(gòu)造Aq(n,d)的最第三節(jié)編碼理論的基本問題因此，中第i位置是非零的充分必要條件是x和y在第i個位置都是非零的。引理6.3.2

(1)對于所有的(2)對于所有的定理6.3.2設(shè)d為奇數(shù)，則二元(n,M,d)碼存在充分必要條件是二元(n+1,M,d+1)碼存在。11/22/202233第三節(jié)編碼理論的基本問題因此，中第i位置是非零的充分第三節(jié)編碼理論的基本問題推論6.3.1如果d是奇數(shù)，則。它等價于，如果d是