馬天宇，蘇建春，楊 靜

(廣西民族大學a.人工智能學院；b.數(shù)學與物理學院，廣西 南寧 530006)

0 引言

Hadamard最大行列式問題最早由J.Hadamard在其1893年的論文中提出.[1]它旨在尋找元素為-1/+1的N×N階方陣，使其行列式的絕對值達到最大.該問題在過去一個多世紀中得到了廣泛研究，但至今仍未被完全解決.在組合設計中，人們常常用二值型-1/+1的互補差集(Supplementary Difference Set，簡稱SDS)構建二值向量和相應的循環(huán)矩陣，從而得到Hadamard最大行列式問題在某些特定條件下的解.[2]

利用二值型SDS求解Hadamard最大行列式問題的核心是計算循環(huán)矩陣的核，即對應的二值型SDS.令其為矩陣的第一個行向量，則第i個行向量可以通過將第(i-1)個行向量向右平移一位得到.矩陣的核如果通過窮舉法進行搜索，則復雜度會隨矩陣階數(shù)N的增加呈指數(shù)級增長.因此，計算二值型SDS的典型策略是根據(jù)二值型SDS需滿足的約束條件分析得到序列的若干性質(zhì)，再根據(jù)這些性質(zhì)逐步壓縮搜索空間，在有限的時間內(nèi)求得符合要求的二值序列.在文獻[3]中，Kotsireas等人發(fā)現(xiàn)二值型SDS進行壓縮后，所得序列的PSD互補性質(zhì)，從而提出了基于序列壓縮方法的組合設計算法.他們還基于群運算中的軌道方法提出了一些特殊二值型SDS的構造方法.近年來，Kotsireas和楊靜等人提出了二值型序列的游程編碼方法，發(fā)現(xiàn)了二值型SDS的若干組合性質(zhì)，并用于有效地構造求解組合設計中出現(xiàn)的特定類型的多項式方程組.[4-5]

本文采用的二值型SDS是廣義Legendre對，而構造出的循環(huán)矩陣為廣義Legendre循環(huán)矩陣.由廣義Legendre對求解Hadamard最大行列式問題的其主要思路可以描述如下：

1)設a=(a0，a1，…，an-1)，b=(b0，b1，…，bn-1)為兩個長度為n的二值序列，求解方程組

將滿足條件(1)的a和b稱為長度為n的廣義Legendre序列對.

2)分別以a和b為核構造兩個循環(huán)矩陣A和B.

3)構造如下形式的矩陣.

則所求出的矩陣即為2n+2階的Hadamard矩陣.

本文采用二值序列的游程編碼方式，將(1)的求解問題轉(zhuǎn)化為正整數(shù)n的有序拆分問題.這種編碼方式能夠有效地去除解空間中等價的冗余序列，從而可以極大地減少計算量，提高計算效率，計算得到非等價的廣義Legendre對.

1 設計方法的理論基礎

1.1 周期自相關函數(shù)

設x為長度為n的有限序列，則定義x的第k個周期自相關函數(shù)(Periodic Autocorrelation Function，簡稱PAF)為

性質(zhì)1設a=(a0，a1，…，an-1)為長度為n的二值序列，則PAF(A，k)≡n mod 4，其中k=1，2，…，n-1.[6]

性質(zhì)2如果x′可以通過對x做旋轉(zhuǎn)或逆向旋轉(zhuǎn)得到，則PAF(x，k)=PAF(x′，k)，

證明：

1)設x=(x0，x1，…，xn-1)，x′=(xm，xm+1，…，x(m+p-1)modn)，則x′i=x(x+m)modn且

2)設x=(x0，x1，…，xn-1)，x′=(xn-1，xn-2，…，x0)，則=x(n-1-i)modn，且

3)設x=(x0，x1，…，xn-1)，x′=(xi，xi-1，…，x(i-n+1)modn)，則x″=(xn-1，xn-2，…，x0)

由(1)，PAF(x′，k)=PAF(x″，k)

由(2)，PAF(x″，k)=PAF(x，k)

因此，PAF(x，k)=PAF(x′，k)，證畢.

由性質(zhì)2可知，在序列經(jīng)過旋轉(zhuǎn)或逆向旋轉(zhuǎn)后其PAF值保持不變.若x′可以通過對做旋轉(zhuǎn)或逆向旋轉(zhuǎn)得到，我們稱x和x′為等價序列.易知，如果x，y為引用(1)的解，且x′和y′分別為x和y的等價序列，則x′，y′也為(1)的解.因此，不失一般性，我們假設下文出現(xiàn)的二值序列x均以+1開始，-1結(jié)束.

1.2 游程與有序拆分

本文采用游程的概念來描述一個-1/+1的二值序列.設x為一個-1/+1的二值序列，則x的一個游程定義為該序列滿足下列條件的一個片段：

1)其元素只含+1或只含-1；

2)相鄰的片段中都具有相反的符號.

例如，給定a=(1，1，-1，1，1，-1，-1)，則a中有4個游程，即(1，1)，(-1)，(1，1)，(-1，-1).由于每個游程中元素均為+1或-1，因此我們可以將游程的信息表示為游程的長度.例如，上述序列x的游程可以表示為2，1，2，2.這樣我們就將一個-1/+1的二值序列重新編碼為正整數(shù)n的一個有序偶拆分.例如，給定a=(1，1，-1，1，-1，1，-1，-1，-1)，則a可以編碼為一個9的偶拆分為(2，1，1，1，1，3)；反之，如果給定一個9的偶拆分(2，1，1，1，1，3)，則可將其解碼得到一個長度為9的二值序列(1，1，-1，1，-1，1，-1，-1，-1).這兩個過程分別稱為二值序列的編碼和解碼.

性質(zhì)3設a為長度為n的二值序列，#run(a)表示a的游程數(shù)，#1-run(a)表示a中長度為1的游程數(shù)，則

1.3 廣義Legendre對的組合性質(zhì)

定理1設a和b為滿足(1)的廣義Legendre序列對，游程數(shù)量分別為#run(a)和#run(b)，“1”游程數(shù)量分別為#1-run(a)和#1-run(b).則

1)#run(a)與#run(b)為偶數(shù)；

2)#run(a)+#run(b)=n+1；

本文提出的設計方法的基本思想是將尋找二值序列x的問題轉(zhuǎn)化為尋找滿足特定條件的游程的問題.而該問題又等價于尋找n的一個有序偶拆分(即n=n1+n2+n3+…+ni，ni>1，i=1，2，…，t).我們利用廣義Legendre序列對編碼后的偶拆分信息，將序列的窮舉搜索問題簡化為正整數(shù)的有序偶拆分問題.計算結(jié)果表明，這些信息可以極大地縮小壓縮空間，解決規(guī)模較大的組合設計問題.

1.4 PSD檢測

PSD檢測在組合設計中常常被用于篩除不符合要求的廣義Legendre對.下面我們給出PSD的定義.給定一個長度為n的復序列x=(x0，x1，…，xn-1)，令ω=e2π/n表示n次本原單位根.則x的離散傅里葉變換(Discrete Fourier Transformation，以下簡稱“DFT”)定義為：

而x的第k個PSD值為

PSD(x，k)=|DFT(x，k)|2=DFT(x，k)·

定理2若a和b是一組廣義Legendre對，則序列a和b的PSD值滿足如下關系：

PSD(a，k)+PSD(b，k)=2n+2(1≤k≤n-1)

因為PSD的值大于等于0，因而PSD(a，k)≤2n+2.我們通常用廣義Legendre對的這個性質(zhì)來對其進行PSD檢測，從而過濾掉不必要的序列，有效地減少計算量.

2 實驗結(jié)果

我們基于上述理論，用C語言實現(xiàn)了一種新的尋找廣義Legendre對的組合設計方法.該方法可以有效地去除等價或冗余的序列，從而計算得到具有較大規(guī)模的廣義Legendre對.本節(jié)中我們列出了采用該方法計算出的若干廣義Legendre對.

2.1 長度為35的PAF序列

當n=35時，我們找到3833對符合條件的廣義Legendre序列對，以下僅列出其中一例.

a對應的有序拆分為(1，1，1，1，1，2，2，2，5，1，1，2，1，1，4，2，2，5)

b對應的有序拆分為(1，1，1，1，2，2，4，3，2，1，2，1，1，1，3，1，2，6)

解碼后的a序列為

(+-+-+--++--+++++-+--+-++++--++-----)

解碼后的b序列為

(+-+-++--++++---++-++-+-+++-++------)

a的PAF序列為 (-1，-1，-1，-1，-1，-1，-1，-1，-1，-1，3，-1，3，-13，-1)

b的PAF序列為 (-1，-1，-1，-1，-1，-1，-1，-1，-1，-1，-5，-1，-5，-1，-5，11，-1)

2.2 長度為41的PAF序列

當n=41時，我們找到3807對符合條件的廣義Legendre序列對，以下僅列出其中一例.

a對應的有序拆分為(1，1，1，1，1，2，2，2，1，1，1，2，1，5，5，1，6，3，2，2)

b對應的有序拆分為(1，1，1，1，1，1，2，1，3，2，3，4，2，1，2，1，1，5，3，1，2，2)

解碼后的a序列為(+-+-+--++--+-+--+-----+++++-++++++---++--)

解碼后的b序列為(+-+-+-++-+++--+++----++-++-+-----+++-++--)

a的PAF序列為(1，1，1，1，1，1，1，1，1，-11，-3，-3，-7，-7，5，1，1，-7，1，1)

b的PAF序列為(-3，-3，-3，-3，-3，-3，-3，-3，-3，9，1，1，5，5，-7，-3，-3，5，-3，-3)

2.3 長度為49的PAF序列

當n=49時，我們找到70對符合條件的廣義Legendre序列對，以下僅列出其中一例.

a對應的有序拆分為(1，1，1，1，1，1，4，1，2，1，2，5，2，2，1，3，3，2，1，2，1，5，5)

b對應的有序拆分為(1，1，1，1，1，1，1，4，2，1，4，3，2，4，1，4，2，1，2，2，3，1，2)

解碼后的a序列為

(+-+-+-+----+--+--+++++--++-+++---++-++-+++++-----)

解碼后的b序列為

(+-+-+-+--+-++++--+----+++--++++-++++--+--++---+--)

a的PAF序列為

(1，1，1，1，-11，1，1，1，1，1，-11，1，1，5，5，1，-3，-3，-3，-7，-7，1，1，-3)

b的PAF序列為

(-3，-3，-3，-3，9，-3，-3，-3，-3，-3，9，-3，-3，-7，-7，-3，1，1，1，5，5，-3，-3，1)

3 結(jié)論

本文通過對廣義Legendre對的組合性質(zhì)進行研究，將二值序列的搜索問題轉(zhuǎn)化為正整數(shù)的有序拆分問題，提出了一種新的二值自相關序列的設計方法.實驗結(jié)果表明：該方法可以有效地縮小搜索空間，去除不必要的冗余序列和等價序列，從而提高計算效率.由于該方法具有良好的并行性質(zhì)，今后可以通過MPI編程將其部署到多核服務器或大型計算集群，用以求解大規(guī)模的公開問題.此外，本文提出的算法也可借鑒到其他二值SDS序列、三值SDS序列的設計方法中，并與現(xiàn)有的設計方法相結(jié)合，求解類似的組合設計問題.