第五章 区组设计与编码1.拉丁方与正交拉丁方拉丁方：由1，2，…，n 构成n ×n 方阵n n ij a ⨯)(，如果每行每列中1，2，…，n 各出现一次，则称此方阵为拉丁方。
如： ⎪⎪⎭⎫ ⎝⎛=12212n ⎪⎪⎪⎭⎫ ⎝⎛⎪⎪⎪⎭⎫ ⎝⎛=1233122312131323213n 正交换丁方：设()()nn ijnn ij a A a A ⨯⨯==)2(2)1(1是两个n ×n 的拉丁方，如果矩阵()()nn ijija a⨯)2()1(,中2n 个数偶())2()1(,ijij a a 互不相同，n j i ,,2,1, =，则称1A 和2A 正交，或称1A 和2A 是互相正交的拉丁方。
如：⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎭⎫ ⎝⎛=123312231,21313232121A A 由于⎪⎪⎪⎭⎫⎝⎛)1,2()2,1()3,3()3,1()1,3()2,2()2,3()3,2()1,1(中元素两两不同，故21A A ⊥ 36名军官问题：ij a 表示军官的军衔为i ，军官所在的团为j ，()66),(⨯j i 要求第一个数字构成拉丁方，第二个数字也构成拉丁方，并且正交。
定理：两两相互正交的n 阶拉丁方的个数不超过n-1个pf ：设k A A A ,,,21 是两两相互正交的n 阶拉丁方，往证1-≤n k 。
设n a a a 21是1，2，…，n 的一个全排列，(),,,2,1,)(k l a A nn l ijl ==⨯对1A 作如下置换⎪⎪⎭⎫ ⎝⎛n a a a n2121，得一方阵()nn ij a A ⨯=)1(1，则1A 与k A A ,2正交。
事实上，如果1A 不与2A 正交，则()()nn ijija a⨯)2()1(,中至少有一对数偶出现次数超过1次，设该对数偶为),(m l a a ，则),(m a l 在())2()1(,ijij a a 中至少出现2次，与21,AA 正交矛盾，由此不妨设k A A A ,,,21 的第一行均为),,2,1(n ，任取,1k m l ≤<≤则方阵()()nn m ijija a⨯)()1(,的第一行均是),,(),2,1(),1,1((r n 从而1不能出现在k A A A ,,,21 的第2行第1列元素，故这些元素只能取2，3，…, n 中一个，而且取法不能相同，故n k ≤。
2.域与有限域 域：),(,:)1(,+→⨯+≠V V V V V φ Abel 群b a b a +→),( （2） ),(:***∙→⨯∙V VVV Abel 群ab b a →),( }0/{*V V=（3）分配律成立 ac ab c b a +=+)( ca ba a c b +=+)( 则称),,(⋅+V 为域例： Q ，R ，C ， {}Q b a bi a i Q ∈+=,|)( 二元域}1,0{2=F ， p 元域}1,,2,1,0{-=p F p 有限域：元素个数有限的域叫做有限域比如： },,2,1,0{p F p =模p 的剩余类域， 取)(x f 是][x F p 中n 次不可约多项式，则{}p i n n p q F a xa x a a x f x F F ∈+++==-110))((][}{110p i n n F a a a a ∈+++=-αα 为n p q =元域如：,1)(},1,0{22++==x x x f F 则)(x f 在][2x F 中不可约， },|{))((][2101024F a a x a a x f x F F ∈+==}1,,1,0{x x +=4F 中元素的加法与乘法取模)(x f 的运算11)1(2=++=+=+x x xx x x可以证明：有限域中元素的个数必为素数的方幂。
定理：p p n ,α=为素数，3,1≥≥n α，则存在n-1个互相正交的n 阶拉丁方。
Pf ：取n 阶有限域},,,{110-==n p n F F αααα ，其中 1,010==-n αα令 ()1,,2,1)(-==⨯n k a A nn k ij k其中.1,,2,1,0,)(-=+⋅=n j i a ji k k ijααα则121,,,-k A A A 是正交拉丁方。
k A 是拉丁方否则k A 中必存在某行（列）有两个元素相同，不妨设 情形1： )()(k ih k ija a =则 k i k ji k αααααα+=+，,h jαα=h j =情形2： )()(k ij k hj a a = j i k jh k αααααα+=+，i k h k αααα=，i h αα=h i = i A 与)(j i A j ≠相互正交否则存在g A 与h A 不相互正交，即存在 ()())()()()(h fkg fkh ijg ij a aa a =则k j f i ==,部分非素数幂的正文拉丁方的构造设k A A A ,,,21 是一组1n 阶正文拉丁方，k B B B ,,,21 是另一组2n 阶的正文拉丁方，构造一组k 个21n n 阶矩阵如下：()()()()()()()()()⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡=Br a BraBra Br a Br aBr a Br a B a B a C r mn r m r m r n r r r n r r r r r )()()()(2)(22)21)(1)(12)(11112111k r ,,2,1 =则 k C C C ,,,21 是正文拉丁方 如：⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎭⎫⎝⎛=32113221323131212321A A ⎪⎪⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎪⎪⎭⎫⎝⎛=2431134242133124432134122143123421B B 则 ⎪⎪⎪⎪⎪⎭⎫⎝⎛=)43()33()23()13()33()43()13()23()23()13()43()33()13()23()33()43(),3(1B ⎪⎪⎪⎪⎪⎭⎫⎝⎛=)23()43()33()13()13()33()43()23()43()23()13()33()33()13()23()43(),3(2B3. 均衡不完全的区组设计（BIBD ）定义：设b v B B B x x x X ,,,},,,,{2121 =是X 的非空子集 如果满足：（1）v k kB B B b <==== 21（2）X 中每一个元素在b B B B ,,,21 中恰出现r 次， （3）X 中任一对元素在b B B B ,,,21 中正好同时出现λ次， 则称{b B B B ,,,21 }为均衡不完全区组设律（BIBD ） ),,,,(λk r v b例 },,,,,,,,,{987654321x x x x x x x x x X =一个（12，9，4，31）设计如下：},,{3211x x x B =，},,,{5442x x x B =},,,{9873x x x B =},,{7414x x x B = },,{8525x x x B =，},,{9636x x x B =，},,{9517x x x B =，},,{7628x x x B = },,{8439x x x B =,},,{86110x x x B =，},,{94211x x x B =，},,{75312x x x B =定理：),,,,(λk r v b －设计必满足（1）vr bk = （2）)1()1(-=-v k r λ 对于一个),,,,(λk r v b －设计，构造如下矩阵 1B 2B … b B→⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⨯bv vb v v bb v b b b b b b b b b x x x A21222211121121区组矩阵 其中⎩⎨⎧∉∈=ji j i ij B x B x b 01则（1）J I r AATλλ+-=)(其中I 为单位阵，J 为全1矩阵（2）v b ≥，如果v b =，则称BIBD 为对称的，这时r k = 例：},,,,,,{7654321x x x x x x x X =},,{4211x x x B =， },,{5322x x x B =，},,{6433x x x B =， },,{7544x x x B = ，},,{1655x x x B =， },,{2766x x x B =， },,{3177x x x B =。
则（7，7，3，3，1）－对称设计 对称BIBD 的性质对称BIBD 中任意两组都正好有λ个共同元素 只须证 ⎪⎪⎪⎪⎪⎭⎫⎝⎛=λλλλλλλλλλk k A A T 事实上 A AA A A A A A A A T T T )()(11--==A J I k A))(1λλ+-=-JA AI k 1)(-+-=λλ⎪⎪⎪⎭⎫⎝⎛=+-=k kkJ I kλλλλλλλλλλλ)( 如果v B B B ,,,21 是关于},,,{21v x x x X =的对称BIBD ，任取,i B 则 i v i i i i i i B B B B B B B B B B \,\,\,\,\111 +-是关于i B X \的BIBD 。
i v i i i i i i B B B B B B B B B B ,,,,,1121+-是关于i B 的BIBD4. Hadamard 矩阵定义：设,)(n n ij n h H ⨯=其中,11-=or h ij 如果n Tn n nI H H =则称n H 为n 阶Hadamard矩阵。
例：⎪⎪⎪⎪⎪⎭⎫ ⎝⎛------=⎪⎪⎭⎫ ⎝⎛-==1111111111111111,1111),1(421H H H性质如果2>n ，并且n H 为Hadamard 矩阵，则4mod 0≡n如果()()n n n ij n m m m ij m a H a H ⨯⨯==)()(,是Hadamard 矩阵，则()n n ij mn H a H )(=是m 阶的Hadamad 矩阵如果n H 是Hadamard 矩阵，则⎪⎪⎭⎫⎝⎛-n nn n H HH H 也是Hadamad 矩阵 规范Hadamard 矩阵↔n H 对称BIBD ⎪⎭⎫⎝⎛---14,12,1n n n。