組合數(shù)學課件：組合設計及編碼

組合設計及編碼7.1相異代表組及公共代表組

7.2均衡不完全區(qū)組設計

7.3正交拉丁方

7.4Hadamard矩陣

7.5編碼理論基礎

7.6生成矩陣與校驗矩陣

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

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

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

例1設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)的一個SDR。如將S4改為S4′

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

）不再有SDR。因為這時S1∪S2∪S4′

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

。

與相異代表組SDR等價的問題有如二部圖中求完全匹配的問題。

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

定理1（P.Hall定理）

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

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

定理2

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

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

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

,…,Sm′

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

情況2

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

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

S∧|E|=m。若對i∈{1,2,…,m}，E∩Ai≠￠∧E∩Bi≠￠，則E∩Ai，E∩Bi都是單元素集，稱E為劃分π及π′的（相異）公共代表組（SystemofCommonRepresentatives,簡記為SCR)。易知劃分π及π′有SCR的充分必要條件是存在π及π′中m個元素的重新編號，使在新編號下

定理3

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

證明

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

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

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

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

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

定義3(拉丁方)

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

（2）j≠k

mij≠mik∧i≠k

mij≠mkj。若m=n，則拉丁長方稱為拉丁方。

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

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

設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的必要條件。如若不然，不妨設 ,則一方面這k′個元素在S1′,S2′,…,Sk′中應該總共出現(xiàn)(n-m)k次；另一方面，這k′個元素在S1′,S2′,…,Sk′中又至多出現(xiàn)(n-m)k′次，引起矛盾。所以M(S)一定有SDR。若記M(S)的一個SDR為D=(i1,i2,…,in)，則可將D作為第m+1行元素添加到原先給定的m×n拉丁長方上，得一(m+1)×n拉丁長方。這個過程可一直進行下去，直到擴充成n階拉丁方。

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

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

定理8設G(X,Y,Γ)為二部圖，其中點集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)的充分必要條件是對 X′X，恒有關(guān)系式：|Γ(X′)|≥|X′|

定義4

設S={1,2,…,n}，S1,S2,…,Sm是S的m個子集。構(gòu)造一m×n的(0,1)矩陣A=(aij),i=1,2,…,m,j=1,2,…,n,其中稱矩陣A為n元集S關(guān)于它的m個子集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是對S的子集S1,S2,…,Sm的一個全面刻畫。反之，若給定一個m×n的(0,1)-矩陣A，及任一n元集S，則一定可反寫出S的m個子集S1,S2,…,Sm

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

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

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

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

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

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

定義1

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

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

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

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

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

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

定義2設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對于(b,v,r,k,λ)-矩陣A有其中J為元素全1的v階方陣，J′為元素全1的b×v矩陣，I是v階單位陣。

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

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

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

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

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

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

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

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

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

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

證明設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個是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階方陣。這就證明了任意對稱BIBD的關(guān)聯(lián)矩陣是正規(guī)的。任意二子集恰有λ個共同元素。

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

推論對稱BIBD的任意二子集恰有λ個共同元素。

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

定理5設B1,B2,…,Bv是關(guān)于集合X={x1,x2，…,xv}的對稱BIBD，A為其關(guān)聯(lián)矩陣，則對其中任一Bi，1≤i≤v，v-1個集合組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

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

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

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

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

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

定義1

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

正交拉丁方源于Euler的36名軍官問題，該問題簡述如下：

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

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

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

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

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

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

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

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

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

第一行（或第一列）元素是1,2,…,n形式的n階拉丁方L，常稱為行標準形（或列標準形）。定理2中，當t=n-1時，稱這個正交組是完備的。

定義3

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

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

例3

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

事實上，設p=a·b，則因a≠0∧b≠0但a·b≡0(modp)，這說明F關(guān)于“·”含有0因子。故F不構(gòu)成域。特別地，當p為素數(shù)時，記(F,+,0)為GF(p)，視其為Galois域的特殊情形。其中GF(p)的元素取modp的剩余組{0,1,2,…,p-1}。設p為素數(shù)，系數(shù)取自GF(p)的多項式集合用GF(p,x)表示（其中多項式的形式為 。對p(x),q(x)∈GF(p,x)，當p(x)次數(shù)高于q(x)的次數(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)中兩個次數(shù)更低的多項式s(x),q(x)之積，則稱p(x)在GF(p,x)上是不可化約的。若對p(x),s(x),q(x)∈GF(p,x)，有等式p(x)=s(x),q(x)成立，則稱s(x),q(x)是多項式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設m(x)是系數(shù)取自GF(p)的，在GF(p,x)不可化約的α次（α∈Z+）多項式，則GF(p,x)的modm(x)意義下分成若干個同余類。將這些同余類所成的集合記為GF(p,m(x))，則在通常意義的多項式“+”和“·”運算下（必須注意對同次冪系數(shù)相加要modp），（GF(p,m(x)),+,·)構(gòu)成有限域，因|GF(p,m(x))|=pα，故常用GF(pα)表示，并稱GF(pα)所成域為Galois域。

例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)成域。首先注意封閉性不難驗證，例如：(x+x2)+(1+x+x2)=1+(1+1)x+(1+1)x2=1+0·x+0x2

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

定理3設n=pα，其中p為素數(shù)，α∈Z+，則當n≥3時，一定存在n-1個n階拉丁方所成的完備正交組。

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

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

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

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

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

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

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

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

但由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）分別展為

其余序偶展開類似。若分別對12個序偶標以1到12的標號，即可得兩個12×12拉丁方。

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

=1。

證明設GF(p,m(x))的互不相同的非零元素所成之集為T={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為乘法“·”的零元。此時，若z=0，則定理顯然已真；若z≠0，則z必為z1,z2,…,zpα-1

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

定義1一個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。

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

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

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

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

證明設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設A=(aij),B=(bij)分別是m階和n階方陣，定義mn階方陣A×A′=(aij

A′)

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

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

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

定理3

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

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

其中I為4t-1階單位陣，J為元素全1的4t-1階方陣。從而A是一個參數(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)造一個n=4t≥8階的規(guī)范化Hadamard矩陣。這種組態(tài)及其補(4t-1,2t,t)常稱為Hadamard組態(tài)。

定理4設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)此時若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編碼理論基礎

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

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

定義1

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

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

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

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

e，則c=r

e,e=r

c。

定義3設a,b為碼字，則a中非零碼元的個數(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ì)）設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）。對任意碼字a,c,

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

c|≤|a|+|c|

又對任一碼字b，b

b=0,于是

定義4

設用編碼函數(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通過計算所有3+2+1=6對不同編碼字的距離，并選取最小值知E的最短距離為2。

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

奇偶校驗碼也可設為奇校驗。相應地，與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。例如，對m=4，有D(10010)=1001,D(11001)=1100。

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

b1b2…bm∈B3m

即函數(shù)E僅使Bm中的每個元素重復三次以產(chǎn)生一個碼字。作為一個具體的例子，令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

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

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

定理2

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

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

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

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

E(001)=10111000

E(010)=00101101

E(011)=1001010