若干達到界的正交陣列

關鍵詞:正交陣列;極大無關組;Rao界;Griesmer界

中圖分類號:O157.4;TN918.1 文獻標識碼:A

Several Orthogonal Arrays Achieving Bounds

DONG Jun-wu1， 2，WANG Xue-li3

(1. College of Mathematics and Econometrics， Hunan Univ， Changsha， Hunan 410082， China;

2. College of Mathematics and Information Sciences， Guangzhou Univ， Guangzhou，Guangdong 510006， China;

3. School of Mathematical Sciences， South China Normal Univ， Guangzhou，Guangdong 510631，China )

Abstract:Three new classes of orthogonal arrays that meet the equality of Rao-bound and other two bounds proposed in [9] were constructed， and these resulting orthogonal arrays can construct linear codes that reach the equality of Griesmer bound in Error-Correct Code Theory.

Key words:orthogonal array;maximal linearly independent array;Rao-bound;Griesmer-bound

正交陣列最初應用在統計學和試驗設計中，例如醫學試驗、農業試驗以及化工試驗等.正交陣列也是區組設計中一個很重要的研究對象，可用來構造其他重要的區組設計.正交陣列在密碼學和糾錯碼理論中有很多應用:Stinson ^[1]利用正交陣列構造了一類認證碼，利用正交陣列構造了一類密鑰預分配方案^[2].裴定一^[3]利用特殊強部分平衡設計(即λt=1的強部分平衡設計)可以構造最優認證碼，而指標為1的正交陣列可以構造 λt=1的強部分平衡設計，因而可以構造最優認證碼.在流密碼的設計，性能良好的布爾函數起著非常重要的作用.為了抵抗流密碼的相關攻擊，Siegenthaler^[4]引入了布爾函數相關免疫度的概念，而Camion和Carlet等^[5]建立了正交陣列和相關免疫函數的關系，因此利用合適的正交陣列可以構造性能良好的相關免疫函數.另外，正交陣列還可以構造彈性函數和通用Hash函數等.

從歷史上看，糾錯碼理論和正交陣列是獨立發展的，兩者中有很多相似的結果，也都是先后獨立發現的.因此，利用正交陣列可以構造相應的糾錯碼，從而可以利用正交陣列的理論證明一些糾錯碼的存在性結果.反之，糾錯碼理論中的經典結果也有助于構造正交陣列.關于正交陣列比較系統的結果可參見文獻[6]，而Hedayat等^[7]文中包含了關于正交陣列的幾乎所有構造方法和最新結果，他們一直在維護著一個網站，記錄著正交陣列的最新結果:www./research.att.com/njas/oadir/.

和研究糾錯碼的方法相似，為了研究正交陣列的存在性，人們提出了若干界，即固定其中幾個參數，確定另外一個參數的取值范圍.從歷史上看關于正交陣列有幾個著名的界:Rao^[8]提出了著名的Rao界;Bierbrauer等^[9-10]利用線性規劃的方法提出了兩個界(見下面的定理3和定理4);Noda^[11-12]構造了幾類正交陣列，均達到了Rao界(見下面的定理2).

利用有限域Fq上的n元t無關組可以構造正交陣列.文獻[13]提出了極大n元t無關組的概念，并且在向量空間Vr(F2)中完全解決了下面的兩種情形:1) t=3的情形;2)平凡情形.本文作者在文獻[14]中構造了另外一類極大無關組.本文利用上面的結果構造了幾類正交陣列，而且這些正交陣列剛好達到上面提到的界.由于在文獻[7-8]以及Hedayat等人所維護的網站中并沒有找到我們構造的正交陣列，因此這些正交陣列是新的.

在糾錯碼理論中，關于線性碼的存在性問題，有一個很有名的界叫Griesmer界，Griesmer在文獻[15]中證明了二元線性碼的情形，后來由Solomon等^[16]推廣到一般的q元線性碼的情形.Hill等^[17-18]列舉了幾個達到Griesmer界的線性碼.以n元t無關組作為檢驗矩陣，可以構造線性碼，本文構造了一類線性碼，達到Griesmer界.

1 預備知識

首先引入正交陣列的概念:

定義1 由s個符號組成的N×k矩陣A稱為水平s，強度t (0 ≤ t≤k)和指標λ的正交陣列，如果在A的任一N×t子矩陣中，任一長為t的符號排列恰好在λ個行中出現，記為OA(N，k，s，t).

易知λ=N/st.下面是一個正交陣列OA(16，5，2，4)的例子(為了節約空間，這里寫出矩陣的轉置形式):

0 0 0 0 1 0 0 1 0 1 1 1 1 1 1 00 0 0 1 0 0 1 0 1 0 1 1 1 1 0 10 0 1 0 0 1 0 0 1 1 0 1 1 0 1 10 1 0 0 0 1 1 1 0 0 0 1 0 1 1 10 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1.

這個正交陣列有N=16行， k=5列，強度t=4，即任意選定4列所得到的16*4子矩陣中，任意有序四元組(a1，a2，a3，a4)∈V4(F2)都恰好出現=N /24=1次.

下面引入正交陣列的三個界.

定理1 (Rao界) 如果存在一個正交陣列OA(N， k， s， t)，則有下面的不等式成立:

N≥1+∑ui=1ki(s-1)i， t=2u，1+k-1u(s-1)u+1+∑ui=1ki(s-1)i， t=2u+1.

對于Rao界，Noda^[11-12]證明了如下結果.

定理2 在下面幾種情況，Rao界中的等號成立:

1) 如果t=3，則只有如下形式的正交陣列OA(8n，4n，2，3)和OA(q4，q+2，q，3)，其中q為偶數.

2) 如果t=4，則只有如下形式的正交陣列:OA(16，5，2，4)， OA(35，11，3，4)和OA(64，k，6，4).其中:

λ=a2(9a2-1)288，k=9a2+15，a≡21，69(mod 240).

3) 如果t=5，則只有兩個正交陣列OA(25，6，2， 5)和OA(36，12，3，5).

Bierbrauer等人^[9-10]提出了兩個關于正交陣列的界.

定理3 如果存在正交陣列OA(N， k， 2， t)，則有:

N≥2k-k2k-1t+1.

定理4 如果存在正交陣列OA(N， k， 2， t)，且t是奇數.則有:

N≥2k-2k-1(k+1)t+2.

下面介紹一種常用的構造正交陣列的方法:設Vr(F2)是有限域F2上的r維向量空間.即Vr(F2)={(a1， a2，…， ar)|ai F2={0，1}， 1≤i≤r}.首先，將r維向量空間Vr(F2)中的元素編號，編號的方法是所謂的“二進制編號法”，即將Vr(F2)中的向量看成r位二進制時，編號為它代表的十進制數.

湖南大學學報(自然科學版)2010年

第2期董軍武等:若干達到界的正交陣列

固定正整數r，考慮向量空間Vr(F2).約定，用編號α代表向量;用集合{1 2，…， n}表示向量組，有時也表示由這些向量為列向量構成的矩陣A;另外當用分量表示向量時，采用左高右低的編號方式α=(ir-1，ir-2，…，i0).向量α中1的個數稱為漢明重量，記為W().

定義2 設A是Vr(F2)的n元子集，如果A中任意t個元素線性無關，則稱A為n元t無關組.

固定向量空間的維數r，及給定t，滿足3 ≤t ≤r，對于什么樣的整數n，使得存在一個n元t無關組A這是一個很有意思的問題.這樣的n一定存在，例如取n=r+1即可，這時對于任意的1 ≤t≤r， A={1，2，22，…，2r-1，2r-1}就是一個r+1元t無關組.另一方面，滿足這些條件的n一定有最大值 (例如n ≤ 2r-1)，這個最大值與向量的維數r有關，也與t有關，記為M(r，t)， 稱M(r，t)元t無關組為極大(r，t)無關組.

定理5(參閱文獻[13])對于任意的整數r ≥3，有M(r，3)=2r-1.

文獻[13]中還給出了構造極大(r，3)無關組的方法.

定理6 (參閱文獻[13-14]) 設r ≥ 5， 則M(r， r-k) r+13k+2 ≤ r.

由于(r+1)元t無關組是可以顯然構造的，例如可任取向量空間Vr(F2)的一組基{α1，α2，…， αr}，令β=α1+α2+…+αr，則{α1，α2，…， αr，β}為所求，因此稱定理6為平凡情形.

定理7(參閱文獻[14]) 1) 對任意的k ≥2，有M(3k+1， 2k+1)=3k+3;2) 對任意的k≥ 2，有M(3k， 2k)=3k+2;3) 對任意的k≥4，有M(3k+2， 2k+1)=3k+4.

下面的定理說明如何由n元t無關組構造正交陣列，由于目前找不到定理的出處，故證明如下.

定理8 設

是向量空間Vr(F2)上的n元t無關組，則存在一個正交陣列OA(2r，n，2，t).

為了證明這個定理，先證明兩個引理，由于證明是顯然的，證明從略.

引理1 對任意向量α∈Vt(F2)，有

α+Vt(F2)={α+β|β∈Vt(F2)}=Vt(F2).

引理2 若向量α1，α2，…，αt∈Vt(F2)，且線性無關，則

{a1

1+a22+…+att|ai∈F2，1≤ I ≤t}=Vt(F2).

定理8的證明 設矩陣

是向量空間Vr(F2)中的一個n元t無關組.將向量組中的向量當作列向量， SymboleC@ 中的n個向量按照任意順序排成一行得到一個r ×n矩陣，仍將這個矩陣記為

SymboleC@ .將

SymboleC@ 的所有行向量的線性組合放在一起得到一個2r ×n矩陣A.下面證明矩陣A就是所求的正交陣列OA(2r， n，2， t).任意選擇矩陣A的t列，不妨記為第s1，s2，…，st列，令矩陣B是由矩陣A的第s1，s2，…，st個列向量所構成.下證:對于任意的(a1，a2，…，at)∈Vt(F2)， (a1， a2，…，at)作為行向量，在矩陣B中恰好出現2r-t次.

用α1，α2，…， αn來表示矩陣

SymboleC@ 的n個列向量，由n元t無關組的定義可知，列向量αs1，αs2，…，αst在有限域F2上線性無關.令N表示這t個列向量所構成的矩陣.再以β1， β2，…，βr表示矩陣N的r個行向量，那么這r個行向量的所有線性組合就是上面所說的矩陣B.

由于矩陣B的秩為t，因此一定存在t個線性無關的行向量，不妨記為β1，β2，…，βt，由引理2知它們的所有線性組合構成t維向量空間Vt(F2).因此向量(a1，a2，…，at)在Vt(F2)中恰好出現一次.記β為βt+1， βt+2，…，βr的任一線性組合，根據引理1可知β+Vt(F2)=Vt(F2)，所以向量(a1，a2，…，at)在β+Vt(F2)中也恰好出現一次.而這樣的β有2r-t個，并且所有這樣的β+Vt(F2)恰好構成矩陣B的所有行向量.因此向量(a1，a2，…，at)在矩陣B中出現2r-t次，從而A為一個正交陣列OA(2r， n， 2， t).

證畢.

2 幾類達到下界的正交陣列

有了上節的準備工作，我們有如下定理.

定理9對任意的r ≥ 3，可構造一類正交陣列OA(2r， 2r-1， 2， 3)，而且該正交陣列達到了Rao界.

證由定理5知，對任意的r ≥ 3，可以構造一類2r-1元3無關組A，由定理8知，可以構造一類正交陣列OA(2r， 2r-1， 2， 3).

定理的后半部分是定理2中1)的特例.也可以證明如下:將

SymbollA@ =2r-3， s=2， t=3， n=2r-1代入Rao界的奇數形式，得

右邊=1+C12r-1-1+C12r-1=2r=N.

因此正交陣列OA(2r， 2r-1， 2， 3)達到Rao界.

證畢.

例1 令r=5，由定理5知M(5，3)=16，易知.

M={1，2，4，7，8，11，13，14，16，19，21， 22，25，26，28，31}=0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 10 0 0 0 1 1 1 1 0 0 0 0 1 1 1 10 0 1 1 0 0 1 1 0 0 1 1 0 0 1 10 1 0 1 0 1 0 1 0 1 0 1 0 1 0 11 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1.

是一個極大(5，3)無關組，由定理5可得到一個正交陣列OA(32， 16， 2， 3).

定理10對任意的r ≥ 3，可以構造一類正交陣列OA(2r， r+1， 2， r)，而且該正交陣列達到Rao界.

證對任意的r ≥3，任取向量空間Vr(F2)的一組基{

SymbolaA@ 1，

SymbolaA@ 2，…，

SymbolaA@ r}，令

SymbolbA@ =

SymbolaA@ 1+

SymbolaA@ 2+…+

SymbolaA@ r，則{

SymbolaA@ 1，

SymbolaA@ 2，…，

SymbolaA@ r，

SymbolbA@ }是r+1元r無關組.由定理8，可構造正交陣列OA(2r， r+1， 2， r).下面證明該正交陣列達到Rao界.

如果r為偶數，記r=2k，代入Rao界偶數形式的右端得(其中用到了組合恒等式Ci2k+1=C2k+1-i2k+1，且當i從1變到k時，j=2k+1-i從2k變到k+1):

右端=1+∑ki=1Cir+1=

12C02k+1+∑ki=1Ci2k+1+∑ki=1Ci2k+1+C2k+12k+1=

12C02k+1+∑ki=1Ci2k+1+∑2kj=k+1Cj2k+1+C2k+12k+1=

22k+1/2=2r=左端.

如果r為奇數，記r=2k+1，代入Rao界的奇數形式的右端得(其中用到了組合恒等式Ci2k+2 =C2k+2-i2k+2，Ck2k+1+Ck2k+1=Ck2k+1+Ck+12k+1=Ck+12k+2， 且當i從1變到k時，j=2k+2-i從2k+1變到2k+2):

右端=1+Ckr+∑ki=1Cir+1=

12C02k+2+Ck2k+1+∑ki=1Ci2k+2+∑ki=1Ci2k+2+Ck2k+1+C2k+22k+2=

12C02k+2+∑ki=1Ci2k+2+∑2k+1j=k+2Cj2k+2+Ck+12k+2+C2k+22k+2=

22k+2/2=2r=左端.

因此該正交陣列OA(2r， r+1， 2， r)達到Rao界.

證畢.

定理11對任意的k ≥2，可構造一類正交陣列OA(23k+1， 3k+3， 2， 2k+1)，達到定理3中的界.

證 由定理7的1)知，對任意的k ≥ 2，在向量空間V3k+1(F2)中，存在(3k+3)元(2k+1)無關組，文獻[14]中給出了這種無關組的構造方法.由定理8知，存在正交陣列OA(23k+1， 3k+3， 2， 2k+1).將n= 3k+3， t=2k+1代入定理3的右端得:

2n-n2n-1t+1=23k+3-(3k+3)23k+22k+2=

23k+3-3#8226;23k+1=23k+1=N.

即該正交陣列達到定理3中的界.

證畢.

定理12對任意的k ≥2，可構造一類正交陣列OA(23k， 3k+2， 2， 2k)，達到定理4中的界.

證 由定理7的2)知，對任意的k ≥2，在向量空間V3k (F2)中，存在(3k+2)元(2k)無關組，文獻[14]中給出了這種無關組的構造方法.由定理8知，存在正交陣列OA(23k， 3k+2， 2， 2k).將n= 3k+2， t=2k代入定理3的右端得:

2n-2n-1(n+1)t+2=23k+2-23k+1(3k+3)2k+2=

23k+2-3#8226;23k=23k=N.

即該正交陣列達到定理4中的界.

證畢.

例2 令k=2，考慮F2上的r=3k=6維向量空間V6(F2)，易知

M=000001100000101000010011001000110100000110000001

是V6(F2)中的一個8元4無關組，由定理8知，存在一個正交陣列OA(64， 8， 2， 4)如下:

AT=0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 0 1 0 1 1 0 1 1 1 0 0 1 0 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 10 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 0 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 1 0 1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 1 0 1 1 1 1 1 0 1 1 10 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 1 1 1 0 0 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 10 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 1 0 1 1 1 1 10 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 10 1 1 1 1 0 0 0 0 0 1 1 0 0 1 1 0 1 1 1 1 0 1 1 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 0 1 1 0 0 1 1 0 0 0 0 1 1 1 0 1 00 0 0 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 0.

3 達到Griesmer界的線性碼

設C為[n，k，d]q線性碼，即C是有限域Fq上n維向量空間Vn(Fq)中的k維線性子空間，其中n為碼長，k為維數，d為最小碼距.關于線性碼的基本知識，可參閱標準的糾錯碼方面的教材和專著，例如文獻[19]等.對于[n，k，d]q線性碼C，定義:

gq(k，d)=∑k=1i=0[dqi].

其中[x]表示不小于x的最小整數.則有如下定理.

定理13 (Griesmer界)n ≥ gq(k，d).

對任意的s≥2，由定理7的1)知M(3s+1， 2s+1)=3s+3.因此在r=3s+1維向量空間Vr(F2)中，存在(3s+3)元(2s+1)無關組H，其中H可以看做F2上的(3s+1)

SymboltB@ (3s+3)矩陣.以H為校驗矩陣可以構造一個參數為[3s+3， 22， 2s+2]2的線性碼C.此時有:

g2(2，2s+2)=2s+2+[(2s+2)/2]=3s+3=n.

因此所構造的線性碼達到Griesmer界.

同樣，對于任意的s2，由定理7的2)知M(3s， 2s)=3s+2.利用上述的方法可以構造一個[3s+2， 22， 2s+1]2線性碼C.此時有:

g2(2，2s+1)=2s+1+[(2s+1)/2]=3s+2=n.

因此所構造的線性碼達到Griesmer界.

但是，當s≥4時，由定理7的3)知M(3s+2， 2s+1)=3s+4.利用上述方法可以構造一個[3s+4， 22， 2s+2]2線性碼，由于

g2(2，2s+2)=2s+2+[(2s+2)/2]=3s+3

因此這個線性碼就達不到Griesmer界.

例3 令s=2， r=3s=6.由定理8的2)可知矩陣

H=100000010100000100100010000100100000101100000111

的任意四個列向量線性無關.利用矩陣H做為校驗矩陣，可以構造一個線性碼C，該線性碼的碼長n=8， 維數k=2，因此只有四個碼字，最小碼距為d=5.C的四個碼字分別為:

C=(0，0，0，0，0，0，0，0)， (0，0，1，1，1，1，1，0)(1，1，0，0，1，1，0，1)， (1，1，1，1，0，0，1，1).

4 結 論

正交陣列在理論研究和生產實踐中都有著廣泛的應用.本文利用極大(r，t)無關組構造了兩類新的正交陣列(即定理11和定理12中所構造的正交陣列)，這些正交陣列能夠達到某些界.之所以說這些正交陣列是新的，是因為在文獻[7-8]以及由Hedayat等人所維護的網站中并沒有找到我們構造的正交陣列.

參考文獻

[1] STINSON D R. Some constructions and bounds for authentication codes [J]. Journal of Cryptology， 1988， 1(1): 37-51.

[2] STINSON D R. Some new results on key distribution patterns and broadcast encryption [J]. Designs， Codes and Cryptography，1998，14(3): 261-279.

[3] PEI Ding-yi. A problem of combinatorial designs related to authentication codes [J]. Journal of Combinatorial Designs， 1998，6(6): 417-429.

[4] SIEGENTHALER T. Correlation-immunity of nonlinear combining functions for cryptographics applications [J]. IEEE Trans on Info Theo， 1984， 30(5): 776-780.

[5] CAMION P，CARLETC，CHARPINP，et al. On correlation-immune functions[C]//Advances in Cryptology-Crypto'91.Berlin Heidelberg:Springer-Verlag， 1992:86-100.

[6] CHARLES C J，DINITZ H J. The CRC handbook of combin-atorial designs [M]. Chapman Hall: CRC Press， 1995.

[7] HEDAYAT A S，SLOANE N J A，STUFKEN J. Orthogonal arrays: theory and applications [M]. New York:Springer-Verlag， 1999.

[8] RAO C R. Factorial experiments derivable from combin-atorial arrangements of arrays [J]. Journal of theRoyal StatisticalSociety， 1947， 9(1): 128-139.

[9] BIERBRAUER J，GOPALAKRISHNAN K，STINSON D R. Orthogonal arrays， resilient functions， error correcting codes and linear programming bounds [J]. SIAM Journal on Discrete Mathematics， 1996， 9(3): 424-452.

[10]BIERBRAUER J，GOPALAKRISHNANK，STINSON D R. Bounds for resilient functions and orthogonal arrays [C]//Advances in Cryptology-Crypto '94.London UK:Springer-Verlag， 1994:247-256.

[11]NODA R. On orthogonal arrays of strength 4 achieving Rao's bound [J]. Journal of the London Mathematical Society， 1979， 19(3): 385-390.

[12]NODA R. On orthogonal arrays of strength 3 and 5 achieving Rao's bound [J]. Graphs and Combinatorics， 1986， 2(1): 277-282.

[13]董軍武， 裴定一. 一類強部分平衡設計的構造 [J]. 應用數學學報， 2005， 28(1): 167-177.

DONG Jun-wu， PEI Ding-yi. A construction of strong partial balanced design [J]. Acta Mathematicae Applicatae Sinica， 2005， 28(1): 167-177.(In Chinese)

[14]DONG Jun-wu， WANG Xue-li. A construction of maximal linearly independent array [J]. Acta Mathematica Sinica (Accepted).

[15]GRIESMER J H. A bound for error-correcting codes [J]. IMB Journal of Research and Development， 1960， 4(5): 532-542.

[16]SOLOMON G，STIFFLERJ J. Algebraically punctured cyclic codes [J]. Informationand Control， 1965，8(2): 170-179.

[17]HILL R. Optimal linear codes [J]. Cryptography and Coding， 1992， 11: 41-70.

[18]HILL R，KOLEVE. A survey of recent results on optimal linear codes [J]. Combinatorial Designs and Their Appli-Cations， 1999， 403: 127-152.

[19]BERLEKAMP E R. Algebraic coding theory [M]. New York: McGraw-Hill， 1968.