組合數(shù)學(xué)課件：組合設(shè)計(jì)及編碼

組合設(shè)計(jì)及編碼7.1相異代表組及公共代表組

7.2均衡不完全區(qū)組設(shè)計(jì)

7.3正交拉丁方

7.4Hadamard矩陣

7.5編碼理論基礎(chǔ)

7.6生成矩陣與校驗(yàn)矩陣

7.7一些譯碼法及編碼法7.1相異代表組及公共代表組

定義1設(shè)M(S)=(S1,S2,…,Sm)是集合S的m個(gè)子集所成集系。（對(duì)i,j∈{1,2,…,m},i≠j,不要求Si∩Sj=￠，也不要求Si≠Sj。）又假定(a1,a2,…,am)是S中m個(gè)元素所成的m元組。若對(duì)i,j∈{1,2,…,m},i≠j

ai≠aj且ai,ai∈Si（即元素ai代表了集合Si)，則稱(a1,a2,…,am)是集系M(S)=(S1,S2,…,Sm)的一個(gè)相異代表組（SystemofDistinctRepresentatives，簡(jiǎn)記為SDR）。

例1設(shè)S={1,2,3,4,5},S1={2,5},S2={2,5},S3={1,2,3,4},S4={1,2,5}，則4元組（2，5，3，1）是(S1,S2,S3,S4)的一個(gè)SDR。如將S4改為S4′

={2,5}，則（S1,S2,S3,S4′

）不再有SDR。因?yàn)檫@時(shí)S1∪S2∪S4′

={2,5}是一2元集，而按定義，至少必須有3個(gè)不同的元素才能代表S1,S2,S4′

。

與相異代表組SDR等價(jià)的問(wèn)題有如二部圖中求完全匹配的問(wèn)題。

由定義1及例1可知集系(S1,S2,…,Sm)有SDR的必要條件如下：設(shè)(a1,a2,…,am)是集系(S1,S2,…,Sm)的SDR。則從該集系中任取k個(gè)：于是 。即 中至少應(yīng)有k個(gè)不同元素。由于k的選取范圍為1,2,…,m，故這類限制條件可以有 個(gè)。條件 不但是集系(S1,S2,…,Sm)有SDR的必要條件，也是(S1,S2,…,Sm)有SDR的充分條件。而后者就不是那么容易理解。1935年，P.Hall的基本定理給出了子集系存在SDR的充分必要條件。

定理1（P.Hall定理）

S的子集所成集系(S1,S2,…,Sm)有SDR的充分必要條件是：對(duì)k,1≤k≤m，以及對(duì){1,2,…,m}的任一k元子集{i1,i2,…,ik}， 。

P.Hall定理的必要性是顯然的。事實(shí)上，下述定理2比定理1具有更強(qiáng)的結(jié)論，它同時(shí)還給出了SDR個(gè)數(shù)的一個(gè)下界，因此僅證定理2。

定理2

設(shè)集系M(S)=(S1,S2,…,Sm)滿足有SDR的必要條件，并設(shè)每個(gè)集合Si至少有t個(gè)元素，則當(dāng)t≤m時(shí)，集系M(S)至少有t！個(gè)SDR；當(dāng)t>m時(shí)，集系M(S)至少有t!/(t-m)!個(gè)SDR。

證明對(duì)m采用歸納法。當(dāng)m=1時(shí)，若t>1,則有t=t!/(t-1)!個(gè)SDR，它含有t個(gè)元素。若t=1，即有一個(gè)SDR，集系僅有S1一個(gè)集合，定理顯然成立。設(shè)對(duì)m′<m定理為真。下面證明對(duì)m′=m定理也為真，分兩種情況討論。

情況1設(shè)對(duì)k∈Z+(1≤k≤m-1)，及對(duì){1,2,…,m}的任一k組合{i1,i2,…,ik}， 。這時(shí)，先在S1中取定a1，并定義Sj′=Sj\{a1}(j=2,3,…,m)。不難驗(yàn)證M′(S)=(S2′,S3′

,…,Sm′

仍滿足有SDR的必要條件。若t≤m，則t-1≤m-1。根據(jù)歸納假設(shè)M′(S)至少有(t-1)！個(gè)SDR；如果t>m，則t-1>m-1。同樣根據(jù)歸納假設(shè)：M′(S)至少有(t-1)!/(t-m)!個(gè)SDR，但M′(S)的一個(gè)SDR連同代表S1的a1可形成M(S)=(S1,S2,…,Sm)的一個(gè)SDR，在S1中任取一個(gè)ai，以上結(jié)論都成立。由于S1至少有t個(gè)元素，故得M(S)的SDR的個(gè)數(shù)的估計(jì)。

情況2

假定對(duì)k∈Z+(1≤k≤m-1)，以及{1,2,…,m}的任一k組合{i1,i2,…,ik}， 。不妨設(shè)這k個(gè)集合就是前k個(gè)集合S1,S2,…,Sk，在這種情況下，有t≤k，因?yàn)閷?duì)每一個(gè)i=1,2,…,k，Si是 的子集。按照歸納假設(shè)，(S1,S2,…,Sk)至少有t！個(gè)SDR。其中,令一個(gè)SDR表示為D*={a1,a2,…,ak}。對(duì)集系Sk+1,Sk+2,…,Sm，令Sk+1*=Sk+1\D*,Sk+2*=Sk+2\D*,…,S*m=Sm\D*，則集系(S*k+1,S*k+2,…,S*m)包含m-k個(gè)集合，且滿足SDR存在的必要充分條件。因?yàn)榧僭O(shè) ，則 ，而這與假設(shè)矛盾，故由歸納假設(shè)，M*(S)至少有一個(gè)SDR，且它和D*一起組成(S1,S2,…,Sm)的一個(gè)SDR。但按歸納假設(shè),(S1,S2,…,Sk)至少有t！個(gè)SDR，因此M(S)至少有t！個(gè)SDR。

定義2設(shè)π={A1,A2,…,Am}及π′={B1,B2,…,Bm}是集合S的兩個(gè)具有m個(gè)類的劃分。令E

S∧|E|=m。若對(duì)i∈{1,2,…,m}，E∩Ai≠￠∧E∩Bi≠￠，則E∩Ai，E∩Bi都是單元素集，稱E為劃分π及π′的（相異）公共代表組（SystemofCommonRepresentatives,簡(jiǎn)記為SCR)。易知?jiǎng)澐枝屑唉小溆蠸CR的充分必要條件是存在π及π′中m個(gè)元素的重新編號(hào)，使在新編號(hào)下

定理3

劃分π及π′有SCR的充分必要條件是：對(duì)k∈Z+，1≤k≤m，以及對(duì){1,2,…,m}的任一k組合{i1,i2,…,ik}，至多包含π′中的k個(gè)元素。換言之，π中的k個(gè)子集的并，不能包含π′中多于k個(gè)子集的并。

證明

(1)利用反證法證明必要性。若π及π′存在SCR，記為E={a1,a2,…,am},并把劃分π及π′中的元素重新編號(hào)，使ai∈Ai∧ai∈Bi,i=1,2,…,m假設(shè) ，則{ai1,ai2，…,aik,aik+1}∪,即t,1≤t≤k使aik+1∈Ait,這導(dǎo)致aik+1∈Ait∧aik+1∈Aik+1，與π為劃分的假設(shè)不符。(2)再證充分性。令π={A1,A2,…,Am}，對(duì)所有Aj構(gòu)造π的子集Si:Si={Aj|Aj∩Bi≠￠},i=1,2,…,m則子集系(S1,S2,…,Sm)滿足有SDR的必要條件。如若不然，不妨設(shè)只含有π的k個(gè)元素：Ai1,Ai2,…,Aik，但由Si的構(gòu)造知 已包含了π′中的k+1個(gè)元素：B1,B2,…,Bk+1，這與定理的假設(shè)矛盾。

由Hall定理，S1,S2,…,Sm一定有一個(gè)SDR，設(shè)為(Sj1,Sj2,…,Sjm)。將劃分π={A1,A2,…,Am}的元素重新編號(hào)，使這個(gè)SDR在新的編號(hào)下成為D={A1,A2,…,Am}，即在新的標(biāo)號(hào)下，Ai∩Bi≠￠。充分性得證。注意到定理中的π及π′是對(duì)稱的，即當(dāng)π中的任何k項(xiàng)并至多包含π′中k個(gè)子集時(shí)，則π′中任何k項(xiàng)并也至多包含π中k個(gè)子集。

定理4設(shè)π={A1,A2,…,Am}及π′={B1,B2,…,Bm}為r×m元集S的兩個(gè)m類劃分。若對(duì)i∈Z+，1≤i≤m，|Ai|=|Bi|=r，則二劃分π及π′有SCR。

證明這是定理3的特殊情況，因π及π′的元素都是S的r元子集，所以對(duì){1,2,…,m}中的任意k組合i1,i2,…,ik，并集至多包含π′中的k個(gè)元素。從而劃分π與π′一定有SCR。

定理5設(shè)G為有限群，H為G的子群，又設(shè)G=Hx1∪Hx2∪…∪Hxm,G=y1H∪y2H∪…∪ymH分別是G對(duì)H的右陪集及左陪集分解，則G中必有m個(gè)元素z1,z2,…,zm，使G=Hz1∪Hz2∪…∪Hzm=z1H∪z2H∪…∪zmH

定義3(拉丁方)

一個(gè)m×n的拉丁長(zhǎng)方定義為m×n矩陣M=(mij)，其中mij滿足：（1）1≤mij≤n;

（2）j≠k

mij≠mik∧i≠k

mij≠mkj。若m=n，則拉丁長(zhǎng)方稱為拉丁方。

定理6n個(gè)整數(shù)1,2,…,n上的任一m×n拉丁長(zhǎng)方，必可擴(kuò)充為一n階拉丁方。

證明證明思路是每次必可擴(kuò)展一行使m×n拉丁長(zhǎng)方成一(m+1)×n拉丁長(zhǎng)方。反復(fù)操作，即可求得n階拉丁方。

設(shè)S={1,2,…,n}，記Sj為M中第j列元素所成之集，則|S∩Sj|=m。令Sj′=S\Sj，則|Sj′|=|S\Sj|=n-m(j=1,2,…,m)。斷言M(S)=(S1′,S2′,…,Sn′)必滿足有SDR的必要條件。如若不然，不妨設(shè) ,則一方面這k′個(gè)元素在S1′,S2′,…,Sk′中應(yīng)該總共出現(xiàn)(n-m)k次；另一方面，這k′個(gè)元素在S1′,S2′,…,Sk′中又至多出現(xiàn)(n-m)k′次，引起矛盾。所以M(S)一定有SDR。若記M(S)的一個(gè)SDR為D=(i1,i2,…,in)，則可將D作為第m+1行元素添加到原先給定的m×n拉丁長(zhǎng)方上，得一(m+1)×n拉丁長(zhǎng)方。這個(gè)過(guò)程可一直進(jìn)行下去，直到擴(kuò)充成n階拉丁方。

定理7至少存在n!(n-1)!…(n-m+1)!個(gè)m×n拉丁長(zhǎng)方，從而至少存在n!(n-1)!…1!個(gè)n階拉丁方。

證明顯見(jiàn)有n!個(gè)1×n拉丁長(zhǎng)方。又由定理6,每個(gè)1×n拉丁長(zhǎng)方至少可以擴(kuò)充為(n-1)!個(gè)2×n拉丁長(zhǎng)方。因而至少有n!(n-1)!個(gè)2×n拉丁長(zhǎng)方。如是而下，即證定理。

定理8設(shè)G(X,Y,Γ)為二部圖，其中點(diǎn)集X,Y及函數(shù)Γ表示為X={x1,x2,…,xm},Y={y1,y2,…,yn}

Γ(xi)=Yi

Y(i=1,2,…,m),則G(X,Y,Γ)有完全匹配M(|M|=|X|=m)的充分必要條件是對(duì) X′X，恒有關(guān)系式：|Γ(X′)|≥|X′|

定義4

設(shè)S={1,2,…,n}，S1,S2,…,Sm是S的m個(gè)子集。構(gòu)造一m×n的(0,1)矩陣A=(aij),i=1,2,…,m,j=1,2,…,n,其中稱矩陣A為n元集S關(guān)于它的m個(gè)子集S1,S2,…,Sm的關(guān)聯(lián)矩陣。例如S={1,2,3,4,5},S1={2,5},S2={2,5},S3={1,2,3,4},S4={1,4,5}則按定義可求得(0,1)-矩陣A:

A的第i行中的1指出屬于Si的元素，A的第j列的1指出包含元素j的子集。因此A是對(duì)S的子集S1,S2,…,Sm的一個(gè)全面刻畫(huà)。反之，若給定一個(gè)m×n的(0,1)-矩陣A，及任一n元集S，則一定可反寫(xiě)出S的m個(gè)子集S1,S2,…,Sm

，使A是S的元素關(guān)于這些子集的一個(gè)關(guān)聯(lián)矩陣。不用0，1于矩陣A

，而采用-1,1或x,y表示A中元素，也能反映相同的問(wèn)題。事實(shí)上，取(0,1)-矩陣的好處之一是對(duì)元素運(yùn)算方便，二是能夠反映若干組合學(xué)性質(zhì)。

定義5在(0,1)矩陣A中，若將行和列統(tǒng)稱為線（或條），則將兩兩不在同一線上的1的最大個(gè)數(shù)稱為“項(xiàng)秩”，記為P(A)。覆蓋所有1的最小線數(shù)稱為線秩，記為λ(A)。對(duì)于上例中的(0,1)-矩陣A，其項(xiàng)秩P(A)=4，其線秩λ(A)=4。

定理9(Koning定理）設(shè)A是(0,1)-矩陣，則P(A)=λ(A)。

證明先證P(A)≤λ(A)。若P(A)=λ(A)，則A中1的個(gè)數(shù)大于覆蓋1的線數(shù)，故必有一條線，其中1的個(gè)數(shù)大于1。這與P(A)為不在同一線上1的個(gè)數(shù)的定義相矛盾。再證P(A)=λ(A)。由于P(A)和λ(A)在交換A的行（或列）時(shí)保持不變。故可將覆蓋1的r行和t列調(diào)換到前r行和前t列，這時(shí)A變換為分塊形式，即其中A1為r×t矩陣。

只證A2的項(xiàng)秩λ(A2)=r。為此可將A2看作n-t個(gè)元素：{t+1,t+2,…,n}的子集(Y1,Y2,…,Yr)的（0，1）-矩陣。(Y1,Y2,…,Yr)一定滿足有SDR的必要條件。若不然，假設(shè)對(duì)其某k個(gè)子集 有 ,假定這h個(gè)元素所在的列是j1,j2,…,jk。這時(shí)可用A的j1列，j2列，…,jh列代替h個(gè)元素所在的行，仍能覆蓋住A的全部1，但這樣做因h<k說(shuō)明要不了r+t條線即能實(shí)現(xiàn)這種覆蓋。這與λ(A)的最小性定義矛盾。故知(Y1,Y2,…,Yr)必存在SDR，即A2中必有r個(gè)1，且兩兩不在同一線上。結(jié)論是A2的項(xiàng)秩λ(A2)=r。同理可證,A3的項(xiàng)秩λ(A3)=t。從而,λ(A)=λ(A2)+λ(A3)=r+t。但明顯可見(jiàn)前r行及前t列已能覆蓋A中的全部1，而P(A)僅是不在同一線上的1的最大個(gè)數(shù)，故P(A)≤λ(A)。最后有等式P(A)=λ(A)。7.2均衡不完全區(qū)組設(shè)計(jì)

定義1

設(shè)X={x1,x2,…,xv}為一v元集，B1,B2,…,Bb是X的b個(gè)不同的k元子集。若這些子集滿足條件：（1）對(duì)x∈X，x恰好出現(xiàn)在B1,B2,…,Bb的r個(gè)中；（2）X的每個(gè)2元子集都恰好包含在子集組B1,B2,…,Bb的λ個(gè)中；（3）0<λ,k<v-1,

則稱B1,B2,…,Bb為一均衡不完全區(qū)組設(shè)計(jì)（BalancedIncompleteBlockDesign,簡(jiǎn)記為BIBD）或根據(jù)其5個(gè)基本參數(shù)b,v,r,k和λ，稱其為(b,v,r,k,λ)-設(shè)計(jì)。

區(qū)組（blocks）是統(tǒng)計(jì)學(xué)中對(duì)集合組的稱謂。其中，不完全是指k<v-1。均衡體現(xiàn)在定義1中的（1）及（2）。這種設(shè)計(jì)被稱為(b,v,r,k,λ)-組態(tài)，組態(tài)中的5個(gè)參數(shù)不是互相獨(dú)立的，它們由如下定理中的等式聯(lián)系。

定理1(b,v,r,k,λ)-設(shè)計(jì)必須滿足bk=vr,r(k-1)=λ(v-1)。

證明由定義1的（1）知，X的v個(gè)變量的每個(gè)都恰好出現(xiàn)在子集B1,B2,…,Bb的r個(gè)中，故所有元素在子集組中共出現(xiàn)rv次；又每個(gè)子集都是X的k元子集，故b個(gè)子集使X中所有的元素共出現(xiàn)kb次，從而rv=kb。對(duì)等式r(k-1)=λ(v-1)，考察X中含有元素x的2元子集，不妨設(shè)x=x1，對(duì)v-1個(gè)含x1的2元子集(x1,x2),(x1,x3),…,(x1,xv)

由定義1的（2），每個(gè)2元子集都恰包含在b個(gè)子集的λ個(gè)中，故(x1,x2),(x1,x3),…,(x1,xv)共被包含了λ(v-1)次。又由定義1的（1），x1恰好出現(xiàn)在b個(gè)子集組中的r個(gè)中，對(duì)這r個(gè)包含x1的子集，顯見(jiàn)X\{x1}中的元素共出現(xiàn)k-1次，故知子集組B1,B2,…,Bb共將含x1的所有v-1個(gè)2元子集組包含了r(k-1)次。從而r(k-1)=λ(v-1)。

定義2設(shè)X,Bi(i=1,2,…,b)如定義1，則X的關(guān)于Bi的關(guān)聯(lián)矩陣稱為(b,v,r,k,λ)-組態(tài)的關(guān)聯(lián)矩陣或區(qū)組矩陣。定理2對(duì)于(b,v,r,k,λ)-矩陣A有其中J為元素全1的v階方陣，J′為元素全1的b×v矩陣，I是v階單位陣。

證明由每個(gè)Bi(i=1,2,…,b)都是X的k元子集知，Ab×v=(aij)每行恰好有k個(gè)1，故AJ中每行中的元素為k，又Ab×vJv×v乘積為一b×v矩陣，提出因子k即得kJ′（其中J′為b×v矩陣）。

令 ，則顯見(jiàn)B為一v階方陣。B的對(duì)角元bii為A中第i個(gè)列向量與自身的內(nèi)積。由定義1的（1）知A的每個(gè)列恰有r個(gè)1，其余為0，故bii=r，i=1,2,…,v。又B的非對(duì)角元bij(i≠j)為A中第i列與第j列元素所成二不同向量的內(nèi)積。由定義1的（2）知任二不同元素xi,xj同時(shí)在子集組的λ個(gè)中出現(xiàn)，因此A的任二列不同向量恰好有λ個(gè)對(duì)應(yīng)分量同時(shí)為1（其余對(duì)應(yīng)分量至少有一位是0）。故A中任意二不同列向量的內(nèi)積均為λ，即B中非對(duì)角元bij=λ(i≠j)。從而有其中,I為v階單位陣，J為v階全1陣。

定理3(b,v,r,k,λ)-組態(tài)一定有b≥v。

證明設(shè)A是(b,v,r,k,λ)-組態(tài)的關(guān)聯(lián)矩陣。假設(shè)b<v，可添加v-b行0到A上，得到一v階（0，1）方陣A*。易知A*仍滿足A*TA*=(r-λ)I+λJ

這時(shí)，一方面因A*有一行全為0，所以det(A*

A*)=det(A*T)det(A*)=0另一方面，因(r-λ)I+λJ的原對(duì)角元全為r，其余元素全為λ，有det((r-λ)I+λJ)=(r+(r-1)λ)(r-λ)v-1≠0矛盾。所以b<v不可能，即一定有b≥v。

定義3（對(duì)稱BIBD）在(b,v,r,k,λ)-組態(tài)中，當(dāng)b=v時(shí)，稱這一組態(tài)是對(duì)稱的。因bk=vr，且b=v，又有k=r，(b,v,r,k,λ)-組態(tài)成為(b=v,v,r=k,λ)-組態(tài)，這時(shí)，常將其簡(jiǎn)記為(v,k,λ)-組態(tài)，稱之為對(duì)稱的BIBD。關(guān)于對(duì)稱的BIBD，也可化簡(jiǎn)定義1。

定義4設(shè)X={x1,x2,…,xv}為一v元集，B1,B2,…,Bv為X的v個(gè)k元子集。若滿足（1）對(duì)

i,j∈{1,2,…,v},i≠j時(shí)，|Bi∩Bj|=λ；（2）整數(shù)v,k,λ滿足0<λ<k<v-1，則稱B1,B2,…,Bv為一(v,k,λ)-組態(tài)。

定理4對(duì)稱的BIBD的關(guān)聯(lián)矩陣A是正規(guī)的，從而有AAT=ATA=B。

證明設(shè)A為(v,k,λ)-組態(tài)的關(guān)聯(lián)矩陣，則由定理3，有det(ATA)=det(AT)det(A)=(k+(r-1)λ)(k-1)v-1≠0

因此，det(A)≠0,A非奇且A-1存在。AAT=(AAT)(AA-1)=A(ATA)A-1=A((k-λ)I+λJ)A-1

=(k-λ)AA-1+λAJA-1=(k-λ)I+λAJA-1

由于k=r，矩陣A的每行每列都有k個(gè)是1，故AJ=JA=kJ

且AJA-1=(JA)A-1=J(AA-1)=J

從而AAT=(k-λ)I+λ(AJA-1)=(k-λ)I+λJ

其中，I為v階單位陣，J是元素全為1的v階方陣。這就證明了任意對(duì)稱BIBD的關(guān)聯(lián)矩陣是正規(guī)的。任意二子集恰有λ個(gè)共同元素。

又由定理2知，ATA=(k-λ)I+λJ。故AAT=ATA，即A為一正規(guī)方陣。

推論對(duì)稱BIBD的任意二子集恰有λ個(gè)共同元素。

證明只需證相應(yīng)陣A中任二不同行恰有λ個(gè)1。由定理4知，AAT的非對(duì)角元為λ，故可得證。

定理5設(shè)B1,B2,…,Bv是關(guān)于集合X={x1,x2，…,xv}的對(duì)稱BIBD，A為其關(guān)聯(lián)矩陣，則對(duì)其中任一Bi，1≤i≤v，v-1個(gè)集合組B1\Bi,B2\Bi,…,Bi-1\Bi,Bi+1\Bi,…,Bv\Bi

形成關(guān)于集合X\Bi的BIBD。

證明注意到|B1|=|B2|=…=|Bv|=k，|Bi∩Bj|=λ，|X\Bi|=v-k，集合組B1\Bi,B2\Bi,…,Bi-1

Bi,Bi+1\Bi,…,Bv\Bi

中的每一個(gè)都是X\Bi的子集；集合X\Bi的任一元素x仍包含在v-1個(gè)集合的k個(gè)中。由定理1，B1\Bi,B2\Bi,…,Bi-1\Bi,Bi+1\Bi,…,Bv\Bi均只有k-λ個(gè)元素。從而，該集合組構(gòu)成一關(guān)于X\Bi的(v-1,v-k,k,k-λ,λ)-BIBD。定理的證明采用構(gòu)造法，相對(duì)于關(guān)聯(lián)矩陣，應(yīng)刪除第i行，并刪除第i行元素為1的列。

定理6若B1,B2，…,Bv是關(guān)于X={x1,x2,…,xv}的對(duì)稱BIBD。即為一(v,k,λ)-組態(tài)，A為其關(guān)聯(lián)矩陣。則對(duì)Bi∈{B1,B2,…,Bv},v-1個(gè)子集Bj∩Bi，j≠i，1≤j≤v構(gòu)成關(guān)于集合Bi的BIBD。

證明注意到|B1|=|B2|=…=|Bv|=k，|Bj∩Bi|=λ,j≠i,1≤j≤v，而B(niǎo)j∩Bi

Bj,Bj中的元素僅包含在k-1個(gè)Bj∩Bi(j≠i)中，Bj中任意一對(duì)元素恰在λ-1個(gè)Bj∩Bi(j≠i)中同時(shí)出現(xiàn)。又B1∩Bi,B2∩Bi,…,Bi-1∩Bi,Bi+1∩Bi,…,Bv∩Bi都含有λ個(gè)元素。故這v-1個(gè)集合構(gòu)成Bi的((v-1),k,(k-1),λ,(λ-1))-BIBD。例設(shè)有一(15,15,7,7,3)-BIBD的關(guān)聯(lián)矩陣A如下：則關(guān)于X\B1的(14,8,7,4,3)-BIBD對(duì)應(yīng)的關(guān)聯(lián)矩陣為A1，而關(guān)于B1∩Bi(2≤i≤15)的(14,7,6,3,2)-BIBD對(duì)應(yīng)的關(guān)聯(lián)矩陣為A2:7.3正交拉丁方

一個(gè)n階拉丁方陣，是基于n元集X的n個(gè)元素構(gòu)成的一個(gè)n×n陣列，使得每行每列都是X中元素的一個(gè)置換。顯見(jiàn)，拉丁方陣的任一行或任一列都不會(huì)出現(xiàn)兩個(gè)相同的元素。分別基于{1,2}、{1,2,3}、{1,2,3,4}的拉丁方陣如下：

定義1

設(shè)矩陣A=(aij),B=(bij)為定義在集合S={1,2,…,n}上的兩個(gè)拉丁方(n≥3)。若存在n2個(gè)序偶(aij,bij)(i,j=1,2,…,n)使成n階方陣((aij,bij))，且其中元素兩兩互不相同，則稱拉丁方A與B正交，或稱A與B是互相正交的拉丁方。

正交拉丁方源于Euler的36名軍官問(wèn)題，該問(wèn)題簡(jiǎn)述如下：

來(lái)自6個(gè)團(tuán)隊(duì)且分屬6種軍銜的6名軍官，每個(gè)團(tuán)隊(duì)6名，每種軍銜6名，問(wèn)可否把這36名軍官排成6行6列方陣，使得每行每列的6名軍官既有不同軍銜，又來(lái)自不同團(tuán)隊(duì)？若用1，2，3，4，5，6對(duì)軍銜和軍官編號(hào)，則每位軍官可用二元組表示，其中，第一分量表示軍銜，第二分量表示團(tuán)隊(duì)。則Euler問(wèn)題歸結(jié)為能否構(gòu)做一6階方陣，其中的序偶元素兩兩互不相同。1782年，Euler猜想不存在一對(duì)為n≡2(mod4)的正交拉丁方。1900年左右，Tarry通過(guò)系統(tǒng)的枚舉，證實(shí)了對(duì)n=6，Euler猜想是正確的。但直到1960年左右，Bose等人的研究卻證實(shí)了對(duì)n>6∧n≡2(

mod4)必存在一對(duì)n階的正交拉丁方。例1

n=3時(shí)，2個(gè)3階拉丁方A，B給定如下：則因3階方陣中元素兩兩互不相同，故拉丁方A與B正交。n=4時(shí)，共有3個(gè)4階拉丁方陣，它們彼此都是正交的拉丁方陣，即稍作分析和嘗試，可以判定不存在一對(duì)2×2的正交拉丁方陣。

定理1設(shè)A=(aij)，B=(bij)(i,j=1,2,…,n)為兩個(gè)n階正交拉丁方。若對(duì)A中元素施以任一置換 ,得方陣A′=(aij′)，則A′與B仍保持正交。

證明采用反證法。若因施置換P于A所得A′與B不正交，即n階方陣（（aij′,bij））中有一元素至少重復(fù)出現(xiàn)了兩次，設(shè)其為（h′,b）?，F(xiàn)對(duì)A′施以置換P的逆置換,使A′再恢復(fù)到A，這時(shí)h′恢復(fù)到A中的h，則顯見(jiàn)（h,b）在n階方陣((aij,bij))中至少重復(fù)出現(xiàn)過(guò)兩次，這與A,B互相正交的假設(shè)不符，故A′與B仍正交。亦即置換不破壞拉丁方的正交性。

定義2設(shè)A1,A2,…,At是一組n階拉丁方，n≥3,t≥2。若對(duì)i,j∈{1,2,…,t},i≠j

Ai與Aj正交，則稱A1,A2,…,At互相正交，并稱它們?yōu)檎唬ɡ》剑┙M。

定理2互相正交的n階拉丁方陣的個(gè)數(shù)不超過(guò)n-1個(gè)。即設(shè)A1,A2,…,At是t個(gè)n階（n≥3）拉丁方的正交組，則t≤n-1。

證明由定理1，因?qū)》紸k(1≤k≤t)施以置換 得Ak′,Ak′仍與其它拉丁方互相正交。故可對(duì)所有拉丁方施以適當(dāng)置換，使元素序列1,2,…,n都排在第一行。顯見(jiàn)這組拉丁方的正交性并不受破壞，且兩兩構(gòu)成的正交的第一行都是序列(1,1)，(2,2)，…,(n,n)。現(xiàn)在考慮這t個(gè)拉丁方在（2,1）上的元素。由正交性知，這t個(gè)元素互不相同（若相同，則所成序偶必與第一行某序偶重復(fù)），且都不等于1（因1已在(1,1)位置出現(xiàn)了）。從而只能分別取2,3,…,n中的一個(gè)數(shù)，故t≤n-1。

第一行（或第一列）元素是1,2,…,n形式的n階拉丁方L，常稱為行標(biāo)準(zhǔn)形（或列標(biāo)準(zhǔn)形）。定理2中，當(dāng)t=n-1時(shí)，稱這個(gè)正交組是完備的。

定義3

設(shè)|F|≥2，（F，+，·)稱為域，如果（F，+)成Abel群，且(F\{0},·)也構(gòu)成Abel群（0為“+”運(yùn)算的幺元，也即“·”運(yùn)算的零元），同時(shí)“·”對(duì)“+”有分配律。若F元素有限,則稱其為有限域。

例2（Z,+,·)，（R,+,·)，（C,+,·)分別是整數(shù)、實(shí)數(shù)及復(fù)數(shù)的全體關(guān)于普通的加法“+”及乘法“·”運(yùn)算所成的無(wú)限域。

例3

設(shè)p為素?cái)?shù)，則F={0,1,2,…,p-1}在模p意義下，關(guān)于加法“+”，乘法“·”構(gòu)成域。（F,+）為Abel群，顯然。關(guān)于(F\{0},·)，顯見(jiàn)1為幺元，又因p為素?cái)?shù)，故對(duì)a∈F\{0}，(a,p)=1。因此，b,s∈Z，使ab+ps=1，即ab≡1(modp)，亦即b為a的逆元。“·”對(duì)“+”的分配律是已知的，故（F,+,·)為域。若p不為素?cái)?shù)，不難驗(yàn)證F={0,1,2,…,p-1}關(guān)于+,·不能構(gòu)成域。

事實(shí)上，設(shè)p=a·b，則因a≠0∧b≠0但a·b≡0(modp)，這說(shuō)明F關(guān)于“·”含有0因子。故F不構(gòu)成域。特別地，當(dāng)p為素?cái)?shù)時(shí)，記(F,+,0)為GF(p)，視其為Galois域的特殊情形。其中GF(p)的元素取modp的剩余組{0,1,2,…,p-1}。設(shè)p為素?cái)?shù)，系數(shù)取自GF(p)的多項(xiàng)式集合用GF(p,x)表示（其中多項(xiàng)式的形式為 。對(duì)p(x),q(x)∈GF(p,x)，當(dāng)p(x)次數(shù)高于q(x)的次數(shù)時(shí)，如果s(x),t(x)∈GF(p,x)，使得p(x)=s(x)q(x)+r(x)，其中r(x)的次數(shù)小于q(x)的次數(shù)，稱r(x)為q(x)除p(x)的余式。

如果p(x)不能表示為GF(p,x)中兩個(gè)次數(shù)更低的多項(xiàng)式s(x),q(x)之積，則稱p(x)在GF(p,x)上是不可化約的。若對(duì)p(x),s(x),q(x)∈GF(p,x)，有等式p(x)=s(x),q(x)成立，則稱s(x),q(x)是多項(xiàng)式p(x)的因式。若(p(x),q(x))=1，即p(x),q(x)不存在除1以外的公因式，則必a(x),b(x)∈GF(p,x)使得a(x)p(x)+b(x)q(x)=1。

定義4設(shè)m(x)是系數(shù)取自GF(p)的，在GF(p,x)不可化約的α次（α∈Z+）多項(xiàng)式，則GF(p,x)的modm(x)意義下分成若干個(gè)同余類。將這些同余類所成的集合記為GF(p,m(x))，則在通常意義的多項(xiàng)式“+”和“·”運(yùn)算下（必須注意對(duì)同次冪系數(shù)相加要modp），（GF(p,m(x)),+,·)構(gòu)成有限域，因|GF(p,m(x))|=pα，故常用GF(pα)表示，并稱GF(pα)所成域?yàn)镚alois域。

例4令F=GF(2)={0,1}，系數(shù)取自GF(2)的m(x)=x3+x+1在GF(2,x)上是不可化約的。GF(2,x)關(guān)于modm(x)的同余類為GF(2,m(x))={0,1,x,1+x,x2,1+x2,x+x2,1+x+x2}=GF(23)則（GF(23)，+，·)構(gòu)成域。首先注意封閉性不難驗(yàn)證，例如：(x+x2)+(1+x+x2)=1+(1+1)x+(1+1)x2=1+0·x+0x2

=1∈GF(23)結(jié)合律,交換律由多項(xiàng)式加法運(yùn)算可得。又0為“+”的幺元，每個(gè)元素是其自身的逆元。即（GF(23)，+)為Abel群。對(duì)（GF(23)\{0},·)可構(gòu)造運(yùn)算表，并表明其為Abel群的過(guò)程讀者不難給出。又由多項(xiàng)式運(yùn)算可知，多項(xiàng)式乘法“·”對(duì)加法“+”具有分配律,從而GF(23)為域。

定理3設(shè)n=pα，其中p為素?cái)?shù)，α∈Z+，則當(dāng)n≥3時(shí)，一定存在n-1個(gè)n階拉丁方所成的完備正交組。

證明設(shè)a0=0,a1=1,a2,a3,…,an-1為Galois域GF(pα)的不同元素。定義n-1個(gè)n階方陣:其中，令 ，式中的“+”，“·”為GF(pα)中的modp加與modp乘。

先證e,e∈{1,2,…,n-1}，Ae都是拉丁方。如果Ae在第i行上有兩個(gè)元素相同，即有j和j′使aeai+aj=aeai+aj′,因此，aj=aj′，因最初就選取了GF(pα)中的n個(gè)不同元素，故只能是j=j′。同理可證第j列中元素也必不相同。故Ae都是拉丁方（e=1,2,…,n-1）。再證對(duì)e,f∈{1,2,…,n-1}，e≠f,Ae與Af正交。設(shè)對(duì)j≠j′有 ，則同時(shí)有aeai+aj=aeai′+aj′afai+aj=afai′+aj′

二式相加得ai(ae+af)=ai′(ae+af)

由于ae≠af知二者不同時(shí)為0,即ae+af≠0，因此ai=ai′，代入aeai+aj=aeai′+aj′中又得aj=aj′，即i=i′且j=j′，從而Ae與Af正交。由e,f的任意性知n-1個(gè)拉丁方構(gòu)成完備正交組。

定理4設(shè)A1,A2,…,At為t個(gè)n階的正交拉丁方組，B1,B2,…,Bt為t個(gè)n′階的正交拉丁方組，則用這兩個(gè)正交拉丁方可構(gòu)造出t個(gè)nn′階的正交拉丁方組。

證明構(gòu)造拉丁方組C1,C2,…,Ct，使其兩兩正交。令 為Ak的元素，i,j=1,2,…,n,k=1,2,…,t。其中每個(gè)元素又可展為一n′×n′方陣，故 為t個(gè)nn′階方陣，其中，為Bk的元素，r,s=1,2,…,n′;i,j=1,2,…,n，k=1,2,…,t。

對(duì)上述構(gòu)造過(guò)程先證C1,C2,…,Ct均為拉丁方。根據(jù)Ck的構(gòu)造過(guò)程知，Ck的（x,y）處的元素不是第一個(gè)分量不同，就是第二個(gè)分量不同，因此，每行每列的元素都不相同，且都是其它行或列的置換，這表明對(duì)每個(gè)k（k=1,2,…,t）,Ck都是拉丁方。下面證明對(duì)e,f,e,f∈{1,2,…,t},e≠f，Ce與Cf正交，采用反證法。如果Ce

，Cf不正交，則必存在i,j,p,q,i′,j′,p′,q′使即這導(dǎo)致

但由Ae，Af互為正交拉丁方知，不同位置的二元素不得相同，于是有即二者至少必居其一。故（7.3.1）式中只能是i=i′∧j=j′同理可得p=p′∧q=q′

例5令正交拉丁方組A1,A2（3階）及B1,B2（4階）如下所示:構(gòu)造一12階正交拉丁方組C1,C2。首先由定理4的構(gòu)造法有其中C1中元素（3,B1）與C2中元素（3,B2）分別展為

其余序偶展開(kāi)類似。若分別對(duì)12個(gè)序偶標(biāo)以1到12的標(biāo)號(hào)，即可得兩個(gè)12×12拉丁方。

定理5若z是GF(p,m(x))的非零元素，則zpα-1

=1。

證明設(shè)GF(p,m(x))的互不相同的非零元素所成之集為T(mén)={z1,z2,…,zpα-1}，任取z∈T，注意到1為乘法群（T,·)的幺元，及|T|=pα-1，可得zpα-1=1。

定理6若GF(p,m(x))={0,x1=1,x2,…,

xpα-1}，則z∈GF(p,m(x))，使zpα-z=z(z-z1)(z-z2)…(z-zpα-1)

證明由定理5，等式左端為zpα-z=z·(zpα-1-1)=z·(zpα-1+(-1))=z·(1+(-1))=z·0=0其中，-1為1的加法逆元,又0為乘法“·”的零元。此時(shí)，若z=0，則定理顯然已真；若z≠0，則z必為z1,z2,…,zpα-1

中的一員，即k∈{1,2,…,pα-1}，使z=zk，這時(shí)等式右端因有z-zk=zk-zk=zk+(-zk)=0，表明定理為真。7.4Hadamard矩陣

定義1一個(gè)n階方陣Hn=(hij)，若滿足（1）hij=1或hij=-1,i,j=1,2,…,n;

（2）HnHTn=nI,其中I為n階單位陣，則稱Hn為一Hadamard矩陣。注意到用-1乘Hadamard矩陣的某一行或某一列，仍為Hadamard矩陣，因此總可以用此法使任一Hadamard矩陣的第一行及第一列變?yōu)?1。

若一個(gè)Hadamard矩陣的第一行和第一列全是+1，則稱Hadamard矩陣是規(guī)范的。

1階、2階的規(guī)范Hadamard矩陣如下所示：

由定義1易知det(H)的絕對(duì)值是 從而，即Hn是正規(guī)矩陣。

定理1對(duì)n>2，若Hn是Hadamard矩陣，則n≡0(mod4)。

證明設(shè)Hn=(hij)n×n，由定義1，HnHT=nI知取1≤α<β<γ≤n，則

由于Hn中元素非+1即-1， 中hαk+hβk與hαk+hγk取值只能是0，+2，-2，其乘積也只取0，4，-4，故總和為4的倍數(shù)，即n≡0(mod4)。一種猜想是n>2，n≡0(mod4)是Hadamard矩陣存在的充分條件，但尚未證明。

定義2設(shè)A=(aij),B=(bij)分別是m階和n階方陣，定義mn階方陣A×A′=(aij

A′)

,i,j=1,2,…,m。為A與B的直積。

定理2設(shè)Hm和Hn′為m階和n階Hadamard矩陣，則Hm×Hn′為一mn階的Hadamard矩陣。

證明其中，Im,In,Im×n分別為m階,n階及m×n單位陣。推論若Hn是Hadamard矩陣，則也是Hadamard矩陣。

定理3

一個(gè)階數(shù)n=4t≥8的規(guī)范化Hadamard矩陣Hn等價(jià)于一個(gè)參數(shù)為v=4t-1,k=2t-1,λ=t-1的(v,k,λ)-組態(tài)。

證明設(shè)Hn為一規(guī)范化Hadamard矩陣，n=4t≥8，刪除Hn的第一行及第一列，并將剩下的元素為-1者全改為0。這時(shí)得一4t-1階(0,1)陣A。不難依Hn的規(guī)范化驗(yàn)證A（A中每行有2t-1個(gè)1，2t個(gè)0，每行與自身的內(nèi)積為2t-1，不同行內(nèi)積為t-1）滿足方程AAT=tI+(t-1)J

其中I為4t-1階單位陣，J為元素全1的4t-1階方陣。從而A是一個(gè)參數(shù)為v=4t-1,k=2t-1,λ=t-1的(v,k,λ)-組態(tài)的關(guān)聯(lián)矩陣。

以上證明是可逆的，即可由一參數(shù)為v=4t-1,k=2t-1,λ=t-1的(v,k,λ)-組態(tài)的關(guān)聯(lián)矩陣A出發(fā)構(gòu)造一個(gè)n=4t≥8階的規(guī)范化Hadamard矩陣。這種組態(tài)及其補(bǔ)(4t-1,2t,t)常稱為Hadamard組態(tài)。

定理4設(shè)p為常數(shù)，p+1≡0(mod4)，GF(p)為Galois域，若

g∈GF(p)使GF(p)\{0}={g1,g2,g3,…,gp-1≡1}，則αp-1/2≡-1(modp)。

證明令GF(p)={0,1,2,…,p-1}，GF(p)\{0}={g1,g2,g3,…,gp-1≡1}。因g是乘法“·”的生成元，|GF(p)\{0}|=p-1，則gp-1≡1(modp)，于是(g(p-1)/2+1)(g(p-1)/2-1)≡0(modp)此時(shí)若g(p-1)/2-1≡0(modp)，有g(shù)(p-1)/2≡1(modp)，知g不是GF(p)\{0}的乘法“·”的生成元。故只能是g(p-1)/2+1≡0(modp)，即g(p-1)/2≡-1(modp)。

例GF(19)={0,1,2,…,18}，有g(shù)=2∈GF(19)，在mod19意義下，有21=2,22=4,23=8,24=16,25=13,26=7,27=1428=9,29=18,210=17,211=15,212=11,213=3,214=6,

215=12,216=5,217=10,218=17.5編碼理論基礎(chǔ)

大到借助衛(wèi)星的信息傳輸，小到在計(jì)算機(jī)內(nèi)部的數(shù)據(jù)交流，數(shù)字通信的目的就是要將信息正確、高效地由發(fā)送端（信源）經(jīng)過(guò)傳輸信道傳輸給接收端（信宿）。由二進(jìn)制數(shù)字序列表示的信息，因傳輸信道所受的各種噪聲干擾，常會(huì)產(chǎn)生失真或誤碼現(xiàn)象，即傳輸過(guò)程可能把“0”誤傳為“1”，或把“1”誤傳為“0”。編碼理論的主要任務(wù)就是研究若干編碼技術(shù)，提供具有檢錯(cuò)、糾錯(cuò)能力且高效的編碼，從理論和軟件方面來(lái)解決這些問(wèn)題。

為了提高信道的抗干擾能力，對(duì)一個(gè)表示信息的定長(zhǎng)數(shù)字信號(hào)序列b，在傳輸之前，先人為地按一定規(guī)則加進(jìn)一些冗余數(shù)字序列，以構(gòu)成一個(gè)碼字c，這一過(guò)程稱為編碼；c經(jīng)信道傳輸后被記為r（r可能仍為c，也可能有誤差）；對(duì)r經(jīng)過(guò)一定審查，并設(shè)法將其恢復(fù)為c，經(jīng)c反解出原先發(fā)送的信息b（這一過(guò)程稱譯碼）,再送給接收端。（編碼,譯碼技術(shù)統(tǒng)歸編碼理論研究?jī)?nèi)容。）編碼—傳輸—譯碼過(guò)程參見(jiàn)圖7.5.1。圖7.5.1編碼—傳輸—譯碼過(guò)程示意圖

定義1

設(shè)Bm,Bn分別為m位及n位(n>m)的二進(jìn)制序列集合，則編碼(Encoding)過(guò)程可定義為Bm到Bn的特殊映射（要求單射）。記為E:Bm→Bn,稱為Bm到Bn的編碼函數(shù)。對(duì)b∈Bm

，稱b=b1,b2,…,bm為信息，若E(b)=c,稱c=c1c2…cmcm+1…cn為碼字（或碼矢量），ci(i=1~n)為碼元，n為碼長(zhǎng)，c中的前m位ci=bi為信息位。由冗余符號(hào)cm+1cm+2…cn對(duì)傳輸誤差提供一種檢錯(cuò)糾錯(cuò)方法。這n-m個(gè)碼元稱為校驗(yàn)元或監(jiān)督元，每個(gè)碼字的n-m個(gè)校驗(yàn)元僅與碼字c有關(guān)而與別的碼字無(wú)關(guān)。

定義2對(duì)應(yīng)于定義1給出的編碼函數(shù)E，譯碼D(Decoding)過(guò)程是指從Bn到Bm的特殊映射。記為D:Bn→Bm,稱為Bn到Bm的（與E關(guān)聯(lián)的）譯碼函數(shù)。設(shè)c=c1c2…cn為碼字，經(jīng)傳輸后為r，r=r1r2…rn，則r=c

e=(c1+e1,c2+e2,…,cn+en)其中，e為傳輸誤差:“+”為按位加（丟棄進(jìn)位值）或模2加。即0+0=1+1=0，1+0=0+1=1，運(yùn)算符“”為二操作對(duì)象須按分量進(jìn)行“+”運(yùn)算的總體表示。在按位（或模2）加運(yùn)算下，若r=c

e，則c=r

e,e=r

c。

定義3設(shè)a,b為碼字，則a中非零碼元的個(gè)數(shù)稱為a的權(quán)（weight），記為|a|。a

b的權(quán)|a

b|稱為碼字a與b的距離（distance）,記為d(a,b)。

例1|1011|=3,|1101|=3,|0000|=0,|0001|=1

d(1101,1011)=|1101

1011|=|0110|=2

d(1101,1101)=|1101

1101|=|0000|=0

定理1（距離函數(shù)的性質(zhì)）設(shè)x,y,z為碼字，則(1)d(x,y)=d(y,x);;(2)d(x,y)≥0;

(3)d(x,y)=0

iff

x=y;

(4)d(x,y)≤d(x,y)+d(y,z)。

證明（1），（2），（3）較明顯，只證（4）。對(duì)任意碼字a,c,

由于a,c無(wú)論在哪一位不同必有一方在該位碼元為1。所以|a

c|≤|a|+|c|

又對(duì)任一碼字b，b

b=0,于是

定義4

設(shè)用編碼函數(shù)E:Bm→Bn產(chǎn)生的一組碼字X={x1,x2,…,xk}，稱編碼函數(shù)E的最小距離dmin(E)是指所有二不同碼字距離的最小者。即dmin(E)=min{d(xi,xj)|xi,xj∈X,xi≠xj}編碼函數(shù)的最短距離也稱編碼字組的最短距離。

例2考察E:B2→B5,有E(00)=00000,E(10)=10101,E(01)=01110,E(11)=11111通過(guò)計(jì)算所有3+2+1=6對(duì)不同編碼字的距離，并選取最小值知E的最短距離為2。

例3(奇偶校驗(yàn)碼）如下定義的編碼函數(shù)E:Bm→Bm+1稱為奇偶校驗(yàn)碼（實(shí)為其中的偶校驗(yàn)）：設(shè)b=b1b2…bm∈Bm，則E(b)=b1b2…bmbm+1，其中若|b|為偶數(shù)若|b|為奇數(shù)顯見(jiàn)bm+1為0當(dāng)且僅當(dāng)b中非零碼元的個(gè)數(shù)為偶數(shù)。這種編碼函數(shù)將使每個(gè)碼字E(b)的權(quán)為偶數(shù)。碼字傳輸過(guò)程僅出現(xiàn)一位錯(cuò)，將使傳輸結(jié)果的權(quán)值為奇數(shù)，且由此可被檢出。以同樣的方法，顯見(jiàn)任意奇數(shù)個(gè)數(shù)位出錯(cuò)均可被檢出。值得注意的是：這一編碼函數(shù)E對(duì)偶數(shù)個(gè)差錯(cuò)卻無(wú)法判定。盡管有這種局限性，奇偶校驗(yàn)碼還是被廣泛使用。此外，若令上述定義中若|b|為奇數(shù)若|b|為偶數(shù)

奇偶校驗(yàn)碼也可設(shè)為奇校驗(yàn)。相應(yīng)地，與E:Bm→Bm+1關(guān)聯(lián)的譯碼函數(shù)D:Bm+1→Bm可定義為：若c=c1c2…cm+1∈Bm+1,則D(c)=c1c2…cm。注意到若b=b1b2…bm∈Bm，則(D°E)(b)=D(E(b))=D(c)=b

由此D°E=1Bm。例如，對(duì)m=4，有D(10010)=1001,D(11001)=1100。

例4考慮如下定義的編碼函數(shù)E:Bm→B3m，設(shè)b=b1b2…bm∈Bm，則E(b)=b1b2…bmb1b2…bm

b1b2…bm∈B3m

即函數(shù)E僅使Bm中的每個(gè)元素重復(fù)三次以產(chǎn)生一個(gè)碼字。作為一個(gè)具體的例子，令m=3,則E(000)=000000000,E(001)=001001001

E(010)=010010010,E(011)=011011011

E(100)=100100100,E(101)=101101101

E(110)=110110110,E(111)=111111111

設(shè)若b=011，則E(b)=011011011，假定傳輸信道在碼字E(b)的第4位出錯(cuò)，且傳輸結(jié)果為011111011，因其不符合編碼函數(shù)對(duì)每個(gè)信息重復(fù)三次構(gòu)成碼字的規(guī)則，故知其不是碼字。由此，可檢驗(yàn)出這個(gè)差錯(cuò)。不難看出，任何1個(gè)或2個(gè)差錯(cuò)均能被檢出。與E:Bm→B3m相關(guān)聯(lián)的譯碼函數(shù)D:B3m→Bm可定義為：對(duì)c=c1c2…cmcm+1…c2mc2m+1…c3m∈B3m,，有D(c)=x1x2…xm。其中，若xi,xi+m,xi+2m至少有2個(gè)為1若xi,xi+m,xi+2m至少有2個(gè)為0，i=1,2,…,m。

亦即譯碼函數(shù)D要檢查傳輸結(jié)果中的三個(gè)區(qū)段每組的第i位。當(dāng)譯第i位碼時(shí)，三個(gè)區(qū)段中的相應(yīng)位至少有2個(gè)相同。例如，令m=3，則E(100)=100100100,E(011)=011011011,E(001)=001001001?，F(xiàn)設(shè)b=011，而E(b)的傳輸結(jié)果為011111011，即在第二區(qū)段的第一位出錯(cuò)。但因第一區(qū)段和第三區(qū)段的第一位均為1，故D(E(b))=D(011111011)=011。

定理2

設(shè)E：Bm→Bn為一編碼函數(shù)，則E能檢出k個(gè)或更少個(gè)錯(cuò)，當(dāng)且僅當(dāng)E的最小距離為k+1。

證明先證充分性。假定任意兩個(gè)不同碼字之間的距離至少為k+1。令信息b∈Bm，令c=E(b)∈bn為b對(duì)應(yīng)的碼字，且c傳輸為r。若r≠c但r仍是一碼字，則d(c,r)≥k+1。這表明c在傳輸過(guò)程中產(chǎn)生了k+1個(gè)或更多個(gè)差錯(cuò)。因此，若c在傳輸中產(chǎn)生了k個(gè)或更少的差錯(cuò)而傳輸結(jié)果為r，則r必不是碼字。這意味著E可檢出k個(gè)或更少的差錯(cuò)。

再證必要性。設(shè)E能檢出k個(gè)或更少差錯(cuò)，且E的最小距離dmin(E)≤k。并設(shè)碼字c,x的距離d(c,x)滿足d(c,x)=dmin(E)。若r=x，亦即若c被誤傳輸為x，則傳輸過(guò)程出現(xiàn)了dmin(E)≤(k)個(gè)差錯(cuò)，卻因r=x是一碼字而不認(rèn)為出錯(cuò)。故E檢不出k個(gè)或更少差錯(cuò)。例5

考察如下定義的編碼函數(shù)E:B3→B8,有E(000)=00000000

E(001)=10111000

E(010)=00101101

E(011)=1001010