组合数学课件：组合设计及编码

组合设计及编码7.1相异代表组及公共代表组

7.2均衡不完全区组设计

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具有更强的结论，它同时还给出了SDR个数的一个下界，因此仅证定理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。根据归纳假设M′(S)至少有(t-1)！个SDR；如果t>m，则t-1>m-1。同样根据归纳假设：M′(S)至少有(t-1)!/(t-m)!个SDR，但M′(S)的一个SDR连同代表S1的a1可形成M(S)=(S1,S2,…,Sm)的一个SDR，在S1中任取一个ai，以上结论都成立。由于S1至少有t个元素，故得M(S)的SDR的个数的估计。

情况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构造π的子集Si:Si={Aj|Aj∩Bi≠￠},i=1,2,…,m则子集系(S1,S2,…,Sm)满足有SDR的必要条件。如若不然，不妨设只含有π的k个元素：Ai1,Ai2,…,Aik，但由Si的构造知 已包含了π′中的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个整数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′中应该总共出现(n-m)k次；另一方面，这k′个元素在S1′,S2′,…,Sk′中又至多出现(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及函数Γ表示为X={x1,x2,…,xm},Y={y1,y2,…,yn}

Γ(xi)=Yi

Y(i=1,2,…,m),则G(X,Y,Γ)有完全匹配M(|M|=|X|=m)的充分必要条件是对 X′X，恒有关系式：|Γ(X′)|≥|X′|

定义4

设S={1,2,…,n}，S1,S2,…,Sm是S的m个子集。构造一m×n的(0,1)矩阵A=(aij),i=1,2,…,m,j=1,2,…,n,其中称矩阵A为n元集S关于它的m个子集S1,S2,…,Sm的关联矩阵。例如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的元素关于这些子集的一个关联矩阵。不用0，1于矩阵A

，而采用-1,1或x,y表示A中元素，也能反映相同的问题。事实上，取(0,1)-矩阵的好处之一是对元素运算方便，二是能够反映若干组合学性质。

定义5在(0,1)矩阵A中，若将行和列统称为线（或条），则将两两不在同一线上的1的最大个数称为“项秩”，记为P(A)。覆盖所有1的最小线数称为线秩，记为λ(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的个数大于覆盖1的线数，故必有一条线，其中1的个数大于1。这与P(A)为不在同一线上1的个数的定义相矛盾。再证P(A)=λ(A)。由于P(A)和λ(A)在交换A的行（或列）时保持不变。故可将覆盖1的r行和t列调换到前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条线即能实现这种覆盖。这与λ(A)的最小性定义矛盾。故知(Y1,Y2,…,Yr)必存在SDR，即A2中必有r个1，且两两不在同一线上。结论是A2的项秩λ(A2)=r。同理可证,A3的项秩λ(A3)=t。从而,λ(A)=λ(A2)+λ(A3)=r+t。但明显可见前r行及前t列已能覆盖A中的全部1，而P(A)仅是不在同一线上的1的最大个数，故P(A)≤λ(A)。最后有等式P(A)=λ(A)。7.2均衡不完全区组设计

定义1

设X={x1,x2,…,xv}为一v元集，B1,B2,…,Bb是X的b个不同的k元子集。若这些子集满足条件：（1）对x∈X，x恰好出现在B1,B2,…,Bb的r个中；（2）X的每个2元子集都恰好包含在子集组B1,B2,…,Bb的λ个中；（3）0<λ,k<v-1,

则称B1,B2,…,Bb为一均衡不完全区组设计（BalancedIncompleteBlockDesign,简记为BIBD）或根据其5个基本参数b,v,r,k和λ，称其为(b,v,r,k,λ)-设计。

区组（blocks）是统计学中对集合组的称谓。其中，不完全是指k<v-1。均衡体现在定义1中的（1）及（2）。这种设计被称为(b,v,r,k,λ)-组态，组态中的5个参数不是互相独立的，它们由如下定理中的等式联系。

定理1(b,v,r,k,λ)-设计必须满足bk=vr,r(k-1)=λ(v-1)。

证明由定义1的（1）知，X的v个变量的每个都恰好出现在子集B1,B2,…,Bb的r个中，故所有元素在子集组中共出现rv次；又每个子集都是X的k元子集，故b个子集使X中所有的元素共出现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恰好出现在b个子集组中的r个中，对这r个包含x1的子集，显见X\{x1}中的元素共出现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的关于Bi的关联矩阵称为(b,v,r,k,λ)-组态的关联矩阵或区组矩阵。定理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个列向量与自身的内积。由定义1的（1）知A的每个列恰有r个1，其余为0，故bii=r，i=1,2,…,v。又B的非对角元bij(i≠j)为A中第i列与第j列元素所成二不同向量的内积。由定义1的（2）知任二不同元素xi,xj同时在子集组的λ个中出现，因此A的任二列不同向量恰好有λ个对应分量同时为1（其余对应分量至少有一位是0）。故A中任意二不同列向量的内积均为λ，即B中非对角元bij=λ(i≠j)。从而有其中,I为v阶单位阵，J为v阶全1阵。

定理3(b,v,r,k,λ)-组态一定有b≥v。

证明设A是(b,v,r,k,λ)-组态的关联矩阵。假设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,λ)-组态中，当b=v时，称这一组态是对称的。因bk=vr，且b=v，又有k=r，(b,v,r,k,λ)-组态成为(b=v,v,r=k,λ)-组态，这时，常将其简记为(v,k,λ)-组态，称之为对称的BIBD。关于对称的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）整数v,k,λ满足0<λ<k<v-1，则称B1,B2,…,Bv为一(v,k,λ)-组态。

定理4对称的BIBD的关联矩阵A是正规的，从而有AAT=ATA=B。

证明设A为(v,k,λ)-组态的关联矩阵，则由定理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的关联矩阵是正规的。任意二子集恰有λ个共同元素。

又由定理2知，ATA=(k-λ)I+λJ。故AAT=ATA，即A为一正规方阵。

推论对称BIBD的任意二子集恰有λ个共同元素。

证明只需证相应阵A中任二不同行恰有λ个1。由定理4知，AAT的非对角元为λ，故可得证。

定理5设B1,B2,…,Bv是关于集合X={x1,x2，…,xv}的对称BIBD，A为其关联矩阵，则对其中任一Bi，1≤i≤v，v-1个集合组B1\Bi,B2\Bi,…,Bi-1\Bi,Bi+1\Bi,…,Bv\Bi

形成关于集合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-λ个元素。从而，该集合组构成一关于X\Bi的(v-1,v-k,k,k-λ,λ)-BIBD。定理的证明采用构造法，相对于关联矩阵，应删除第i行，并删除第i行元素为1的列。

定理6若B1,B2，…,Bv是关于X={x1,x2,…,xv}的对称BIBD。即为一(v,k,λ)-组态，A为其关联矩阵。则对Bi∈{B1,B2,…,Bv},v-1个子集Bj∩Bi，j≠i，1≤j≤v构成关于集合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)中同时出现。又B1∩Bi,B2∩Bi,…,Bi-1∩Bi,Bi+1∩Bi,…,Bv∩Bi都含有λ个元素。故这v-1个集合构成Bi的((v-1),k,(k-1),λ,(λ-1))-BIBD。例设有一(15,15,7,7,3)-BIBD的关联矩阵A如下：则关于X\B1的(14,8,7,4,3)-BIBD对应的关联矩阵为A1，而关于B1∩Bi(2≤i≤15)的(14,7,6,3,2)-BIBD对应的关联矩阵为A2:7.3正交拉丁方

一个n阶拉丁方阵，是基于n元集X的n个元素构成的一个n×n阵列，使得每行每列都是X中元素的一个置换。显见，拉丁方阵的任一行或任一列都不会出现两个相同的元素。分别基于{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问题归结为能否构做一6阶方阵，其中的序偶元素两两互不相同。1782年，Euler猜想不存在一对为n≡2(mod4)的正交拉丁方。1900年左右，Tarry通过系统的枚举，证实了对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））中有一元素至少重复出现了两次，设其为（h′,b）。现对A′施以置换P的逆置换,使A′再恢复到A，这时h′恢复到A中的h，则显见（h,b）在n阶方阵((aij,bij))中至少重复出现过两次，这与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互相正交，并称它们为正交（拉丁方）组。

定理2互相正交的n阶拉丁方阵的个数不超过n-1个。即设A1,A2,…,At是t个n阶（n≥3）拉丁方的正交组，则t≤n-1。

证明由定理1，因对拉丁方Ak(1≤k≤t)施以置换 得Ak′,Ak′仍与其它拉丁方互相正交。故可对所有拉丁方施以适当置换，使元素序列1,2,…,n都排在第一行。显见这组拉丁方的正交性并不受破坏，且两两构成的正交的第一行都是序列(1,1)，(2,2)，…,(n,n)。现在考虑这t个拉丁方在（2,1）上的元素。由正交性知，这t个元素互不相同（若相同，则所成序偶必与第一行某序偶重复），且都不等于1（因1已在(1,1)位置出现了）。从而只能分别取2,3,…,n中的一个数，故t≤n-1。

第一行（或第一列）元素是1,2,…,n形式的n阶拉丁方L，常称为行标准形（或列标准形）。定理2中，当t=n-1时，称这个正交组是完备的。

定义3

设|F|≥2，（F，+，·)称为域，如果（F，+)成Abel群，且(F\{0},·)也构成Abel群（0为“+”运算的幺元，也即“·”运算的零元），同时“·”对“+”有分配律。若F元素有限,则称其为有限域。

例2（Z,+,·)，（R,+,·)，（C,+,·)分别是整数、实数及复数的全体关于普通的加法“+”及乘法“·”运算所成的无限域。

例3

设p为素数，则F={0,1,2,…,p-1}在模p意义下，关于加法“+”，乘法“·”构成域。（F,+）为Abel群，显然。关于(F\{0},·)，显见1为幺元，又因p为素数，故对a∈F\{0}，(a,p)=1。因此，b,s∈Z，使ab+ps=1，即ab≡1(modp)，亦即b为a的逆元。“·”对“+”的分配律是已知的，故（F,+,·)为域。若p不为素数，不难验证F={0,1,2,…,p-1}关于+,·不能构成域。

事实上，设p=a·b，则因a≠0∧b≠0但a·b≡0(modp)，这说明F关于“·”含有0因子。故F不构成域。特别地，当p为素数时，记(F,+,0)为GF(p)，视其为Galois域的特殊情形。其中GF(p)的元素取modp的剩余组{0,1,2,…,p-1}。设p为素数，系数取自GF(p)的多项式集合用GF(p,x)表示（其中多项式的形式为 。对p(x),q(x)∈GF(p,x)，当p(x)次数高于q(x)的次数时，如果s(x),t(x)∈GF(p,x)，使得p(x)=s(x)q(x)+r(x)，其中r(x)的次数小于q(x)的次数，称r(x)为q(x)除p(x)的余式。

如果p(x)不能表示为GF(p,x)中两个次数更低的多项式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)是系数取自GF(p)的，在GF(p,x)不可化约的α次（α∈Z+）多项式，则GF(p,x)的modm(x)意义下分成若干个同余类。将这些同余类所成的集合记为GF(p,m(x))，则在通常意义的多项式“+”和“·”运算下（必须注意对同次幂系数相加要modp），（GF(p,m(x)),+,·)构成有限域，因|GF(p,m(x))|=pα，故常用GF(pα)表示，并称GF(pα)所成域为Galois域。

例4令F=GF(2)={0,1}，系数取自GF(2)的m(x)=x3+x+1在GF(2,x)上是不可化约的。GF(2,x)关于modm(x)的同余类为GF(2,m(x))={0,1,x,1+x,x2,1+x2,x+x2,1+x+x2}=GF(23)则（GF(23)，+，·)构成域。首先注意封闭性不难验证，例如：(x+x2)+(1+x+x2)=1+(1+1)x+(1+1)x2=1+0·x+0x2

=1∈GF(23)结合律,交换律由多项式加法运算可得。又0为“+”的幺元，每个元素是其自身的逆元。即（GF(23)，+)为Abel群。对（GF(23)\{0},·)可构造运算表，并表明其为Abel群的过程读者不难给出。又由多项式运算可知，多项式乘法“·”对加法“+”具有分配律,从而GF(23)为域。

定理3设n=pα，其中p为素数，α∈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个拉丁方构成完备正交组。

定理4设A1,A2,…,At为t个n阶的正交拉丁方组，B1,B2,…,Bt为t个n′阶的正交拉丁方组，则用这两个正交拉丁方可构造出t个nn′阶的正交拉丁方组。

证明构造拉丁方组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。

对上述构造过程先证C1,C2,…,Ct均为拉丁方。根据Ck的构造过程知，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阶）如下所示:构造一12阶正交拉丁方组C1,C2。首先由定理4的构造法有其中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矩阵的第一行及第一列变为+1。

若一个Hadamard矩阵的第一行和第一列全是+1，则称Hadamard矩阵是规范的。

1阶、2阶的规范Hadamard矩阵如下所示：

由定义1易知det(H)的绝对值是 从而，即Hn是正规矩阵。

定理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的倍数，即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

一个阶数n=4t≥8的规范化Hadamard矩阵Hn等价于一个参数为v=4t-1,k=2t-1,λ=t-1的(v,k,λ)-组态。

证明设Hn为一规范化Hadamard矩阵，n=4t≥8，删除Hn的第一行及第一列，并将剩下的元素为-1者全改为0。这时得一4t-1阶(0,1)阵A。不难依Hn的规范化验证A（A中每行有2t-1个1，2t个0，每行与自身的内积为2t-1，不同行内积为t-1）满足方程AAT=tI+(t-1)J

其中I为4t-1阶单位阵，J为元素全1的4t-1阶方阵。从而A是一个参数为v=4t-1,k=2t-1,λ=t-1的(v,k,λ)-组态的关联矩阵。

以上证明是可逆的，即可由一参数为v=4t-1,k=2t-1,λ=t-1的(v,k,λ)-组态的关联矩阵A出发构造一个n=4t≥8阶的规范化Hadamard矩阵。这种组态及其补(4t-1,2t,t)常称为Hadamard组态。

定理4设p为常数，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(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=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编码理论基础

大到借助卫星的信息传输，小到在计算机内部的数据交流，数字通信的目的就是要将信息正确、高效地由发送端（信源）经过传输信道传输给接收端（信宿）。由二进制数字序列表示的信息，因传输信道所受的各种噪声干扰，常会产生失真或误码现象，即传输过程可能把“0”误传为“1”，或把“1”误传为“0”。编码理论的主要任务就是研究若干编码技术，提供具有检错、纠错能力且高效的编码，从理论和软件方面来解决这些问题。

为了提高信道的抗干扰能力，对一个表示信息的定长数字信号序列b，在传输之前，先人为地按一定规则加进一些冗余数字序列，以构成一个码字c，这一过程称为编码；c经信道传输后被记为r（r可能仍为c，也可能有误差）；对r经过一定审查，并设法将其恢复为c，经c反解出原先发送的信息b（这一过程称译码）,再送给接收端。（编码,译码技术统归编码理论研究内容。）编码—传输—译码过程参见图7.5.1。图7.5.1编码—传输—译码过程示意图

定义1

设Bm,Bn分别为m位及n位(n>m)的二进制序列集合，则编码(Encoding)过程可定义为Bm到Bn的特殊映射（要求单射）。记为E:Bm→Bn,称为Bm到Bn的编码函数。对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个码元称为校验元或监督元，每个码字的n-m个校验元仅与码字c有关而与别的码字无关。

定义2对应于定义1给出的编码函数E，译码D(Decoding)过程是指从Bn到Bm的特殊映射。记为D:Bn→Bm,称为Bn到Bm的（与E关联的）译码函数。设c=c1c2…cn为码字，经传输后为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中非零码元的个数称为a的权（weight），记为|a|。a

b的权|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（距离函数的性质）设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

设用编码函数E:Bm→Bn产生的一组码字X={x1,x2,…,xk}，称编码函数E的最小距离dmin(E)是指所有二不同码字距离的最小者。即dmin(E)=min{d(xi,xj)|xi,xj∈X,xi≠xj}编码函数的最短距离也称编码字组的最短距离。

例2考察E:B2→B5,有E(00)=00000,E(10)=10101,E(01)=01110,E(11)=11111通过计算所有3+2+1=6对不同编码字的距离，并选取最小值知E的最短距离为2。

例3(奇偶校验码）如下定义的编码函数E:Bm→Bm+1称为奇偶校验码（实为其中的偶校验）：设b=b1b2…bm∈Bm，则E(b)=b1b2…bmbm+1，其中若|b|为偶数若|b|为奇数显见bm+1为0当且仅当b中非零码元的个数为偶数。这种编码函数将使每个码字E(b)的权为偶数。码字传输过程仅出现一位错，将使传输结果的权值为奇数，且由此可被检出。以同样的方法，显见任意奇数个数位出错均可被检出。值得注意的是：这一编码函数E对偶数个差错却无法判定。尽管有这种局限性，奇偶校验码还是被广泛使用。此外，若令上述定义中若|b|为奇数若|b|为偶数

奇偶校验码也可设为奇校验。相应地，与E:Bm→Bm+1关联的译码函数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考虑如下定义的编码函数E:Bm→B3m，设b=b1b2…bm∈Bm，则E(b)=b1b2…bmb1b2…bm

b1b2…bm∈B3m

即函数E仅使Bm中的每个元素重复三次以产生一个码字。作为一个具体的例子，令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位出错，且传输结果为011111011，因其不符合编码函数对每个信息重复三次构成码字的规则，故知其不是码字。由此，可检验出这个差错。不难看出，任何1个或2个差错均能被检出。与E:Bm→B3m相关联的译码函数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。

亦即译码函数D要检查传输结果中的三个区段每组的第i位。当译第i位码时，三个区段中的相应位至少有2个相同。例如，令m=3，则E(100)=100100100,E(011)=011011011,E(001)=001001001。现设b=011，而E(b)的传输结果为011111011，即在第二区段的第一位出错。但因第一区段和第三区段的第一位均为1，故D(E(b))=D(011111011)=011。

定理2

设E：Bm→Bn为一编码函数，则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在传输过程中产生了k+1个或更多个差错。因此，若c在传输中产生了k个或更少的差错而传输结果为r，则r必不是码字。这意味着E可检出k个或更少的差错。

再证必要性。设E能检出k个或更少差错，且E的最小距离dmin(E)≤k。并设码字c,x的距离d(c,x)满足d(c,x)=dmin(E)。若r=x，亦即若c被误传输为x，则传输过程出现了dmin(E)≤(k)个差错，却因r=x是一码字而不认为出错。故E检不出k个或更少差错。例5

考察如下定义的编码函数E:B3→B8,有E(000)=00000000

E(001)=10111000

E(010)=00101101

E(011)=1001010