基于有序分拆的二值自相關(guān)序列的設(shè)計(jì)方法研究*

馬天宇，蘇建春，楊 靜

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

0 引言

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

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

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

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

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

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

3)構(gòu)造如下形式的矩陣.

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

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

1 設(shè)計(jì)方法的理論基礎(chǔ)

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

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

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

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

證明：

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

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

3)設(shè)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′可以通過對(duì)做旋轉(zhuǎn)或逆向旋轉(zhuǎn)得到，我們稱x和x′為等價(jià)序列.易知，如果x，y為引用(1)的解，且x′和y′分別為x和y的等價(jià)序列，則x′，y′也為(1)的解.因此，不失一般性，我們假設(shè)下文出現(xiàn)的二值序列x均以+1開始，-1結(jié)束.

1.2 游程與有序拆分

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

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

2)相鄰的片段中都具有相反的符號(hào).

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

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

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

定理1設(shè)a和b為滿足(1)的廣義Legendre序列對(duì)，游程數(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；

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

1.4 PSD檢測(cè)

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

而x的第k個(gè)PSD值為

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

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

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

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

2 實(shí)驗(yàn)結(jié)果

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

2.1 長度為35的PAF序列

當(dāng)n=35時(shí)，我們找到3833對(duì)符合條件的廣義Legendre序列對(duì)，以下僅列出其中一例.

a對(duì)應(yīng)的有序拆分為(1，1，1，1，1，2，2，2，5，1，1，2，1，1，4，2，2，5)

b對(duì)應(yīng)的有序拆分為(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序列

當(dāng)n=41時(shí)，我們找到3807對(duì)符合條件的廣義Legendre序列對(duì)，以下僅列出其中一例.

a對(duì)應(yīng)的有序拆分為(1，1，1，1，1，2，2，2，1，1，1，2，1，5，5，1，6，3，2，2)

b對(duì)應(yīng)的有序拆分為(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序列

當(dāng)n=49時(shí)，我們找到70對(duì)符合條件的廣義Legendre序列對(duì)，以下僅列出其中一例.

a對(duì)應(yīng)的有序拆分為(1，1，1，1，1，1，4，1，2，1，2，5，2，2，1，3，3，2，1，2，1，5，5)

b對(duì)應(yīng)的有序拆分為(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é)論

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