李玉博，劉勝毅，張景景，賈冬艷

（1.燕山大學(xué)信息科學(xué)與工程學(xué)院，河北 秦皇島 066004；2.河北省信息傳輸與信號(hào)處理重點(diǎn)實(shí)驗(yàn)室，河北 秦皇島 066004；3.河北科技師范學(xué)院數(shù)學(xué)與信息科技學(xué)院，河北 秦皇島 066004）

1 引言

碼本是一類具有較低相關(guān)性的信號(hào)集，在同步碼分多址（CDMA,code division multiple access）通信系統(tǒng)[1]、量子編碼理論[2]以及壓縮感知領(lǐng)域具有重要應(yīng)用[3]。構(gòu)造參數(shù)達(dá)到理論界限的最優(yōu)碼本是現(xiàn)代通信理論的重要研究課題之一，因此碼本構(gòu)造方法的研究受到人們的廣泛關(guān)注。一般來說，碼本C 由2 個(gè)參數(shù)進(jìn)行表示，即(N,K)，其中，N 表示碼本的數(shù)量，K 表示碼本的長度。碼本的字符集是碼本中所有碼字的坐標(biāo)所采用的不同復(fù)數(shù)值的集合，字符集大小是字符集中元素的數(shù)量。在實(shí)際應(yīng)用中，字符集較小的碼本具有重要的意義。另外，碼本的最大互相關(guān)幅度值用 Ima（Cx）表示。在通信系統(tǒng)中，希望碼本的最大互相關(guān)幅度值 Ima（Cx）越小越好，以盡可能消除信號(hào)之間的干擾。在壓縮感知領(lǐng)域，具有低相關(guān)性的碼本可用于構(gòu)造測量矩陣。根據(jù)壓縮感知理論可知，碼本最大互相關(guān)幅度值Ima（Cx）越低，其對(duì)應(yīng)的測量矩陣RIP（restricted isometry property）性能越好[2]。除此之外，在量子信息領(lǐng)域中[3]，碼本還用于構(gòu)造SIC-POVM（symmetric informationally complete positive operator-valued measure）和無偏正交基（MUB,mutually unbiased base）。碼本的參數(shù)受到理論界限的制約，當(dāng)N ≥K時(shí)，稱最大互相關(guān)幅度值滿足Welch 界限的碼本為最優(yōu)碼本；當(dāng)N ＞K2時(shí)，稱最大互相關(guān)幅度值滿足Levenstein 界限的碼本為最優(yōu)碼本。近年來，研究人員提出了很多近似達(dá)到Welch 界或Levenstein 界的碼本構(gòu)造方法。文獻(xiàn)[4]首次利用差集構(gòu)造了最優(yōu)碼本。Ding 等[5-6]進(jìn)一步利用差集和幾乎差集構(gòu)造了參數(shù)達(dá)到Welch 界的最優(yōu)碼本。文獻(xiàn)[7-10]利用分圓類方法構(gòu)造了具有優(yōu)良參數(shù)的碼本。除此之外，還有一些利用bent 函數(shù)[11]、平坦函數(shù)[12]、有限域上的特征和理論[13-16]以及二元線性碼[17]來構(gòu)造碼本的方法。

近年來，文獻(xiàn)[18]提出一類基于二元序列與變換矩陣的碼本構(gòu)造框架。該框架包含了已有的許多碼本構(gòu)造方法，如文獻(xiàn)[4-6]的方法等。該類方法有2 個(gè)關(guān)鍵因素：1)滿足一定條件的變換矩陣的構(gòu)造；2)二元序列支撐集的選取。現(xiàn)有的碼本構(gòu)造方法大部分都是基于已有的變換矩陣如離散傅里葉逆變換（IDFT,inverse discrete Fourier transform）矩陣、Hadamard 矩陣，通過選取不同的二元序列支撐集來構(gòu)造碼本?；谕瑯拥乃枷?，文獻(xiàn)[19-20]通過選取一類新的二元序列構(gòu)造了一類新的最優(yōu)碼本。本文放寬了文獻(xiàn)[18]對(duì)初始變換矩陣的條件限制，構(gòu)造了一類新的變換矩陣，并結(jié)合現(xiàn)有的一些特殊的整數(shù)集合構(gòu)造了參數(shù)達(dá)到漸進(jìn)最優(yōu)的碼本。

2 基本概念

一個(gè)參數(shù)為(N,K)的碼本是一個(gè)復(fù)向量集合C={ C0,C1,…,CN-1}，其中每個(gè)向量Cn=(cn,0,cn,1,…,cn,K-1)是長度為K 的單位復(fù)向量，其中0≤ n ≤N-1，。對(duì)于任意2 個(gè)向量Cn1,Cn2∈C，定義厄米特（Hermitian）內(nèi)積為，其中(·)H表示向量的共軛轉(zhuǎn)置。向量集合C 中最大互相關(guān)幅度值定義為

對(duì)于碼本的最大互相關(guān)幅度值，有以下界限成立。

引理1[4]對(duì)于一個(gè)參數(shù)為(N,K)的碼本C，其中N ≥ K，則有

式(2)中等號(hào)成立的條件是當(dāng)且僅當(dāng)對(duì)于任意的0≤n1≠n2≤N-1，有

當(dāng)式(3)成立時(shí)，則碼本最大互相關(guān)幅度值達(dá)到Welch 界限，稱為 MWBE（maximum-Welchbound-equality）碼本；當(dāng)N ＞K2時(shí)，不存在達(dá)到Welch 界的(N,K)碼本，此時(shí)Levenstein 界更緊。

引理2[11]對(duì)于任意參數(shù)為(N,K)的實(shí)碼本，若，則有

對(duì)于任意參數(shù)為(N,K)的復(fù)數(shù)碼本，若N ＞K2，則有

一般稱達(dá)到Welch 界或Levenstein 界的碼本為最優(yōu)碼本，對(duì)于最優(yōu)碼本的構(gòu)造方法研究具有重要的應(yīng)用價(jià)值。

設(shè)p 為素?cái)?shù)，F(xiàn)p表示包含有p 個(gè)元素的有限域，。令ZN={0,1,2,…,N-1}表示一個(gè)模N 的整數(shù)環(huán)。

定義1設(shè)q=pn是素?cái)?shù)冪，p 為素?cái)?shù)，令α 表示循環(huán)群的生成元，有限域上的乘法特征定義為

定義2設(shè)集合D={d0,d1,d2,…,dK-1}表示有限域Fp上一個(gè)子集，定義集合D 的差函數(shù)為，τ∈Fp。如果滿足當(dāng)τ 取遍 Fp上非0 元素時(shí)，差函數(shù) fD(τ)取值為λ 出現(xiàn)p-1次，則稱集合D 是有限域 Fp上的一個(gè)差集，參數(shù)表示為(p,K,λ)-DS。

顯 然，對(duì) 于 差 集(p,K,λ)-DS，有K(K-1)=(p-1)λ成立。

定義3設(shè)集合D={d0,d1,d2,…,dK-1}表示有限域Fp上一個(gè)子集，定義集合D 的差函數(shù)為，τ ∈Fp。如果滿足當(dāng)τ 取遍 Fp上非0 元素時(shí)，差函數(shù) fD(τ)取值為λ 出現(xiàn)t 次，取值為 λ +1出現(xiàn)p-1-t次，則稱集合D 是有限域 Fp上的一個(gè)幾乎差集，參數(shù)表示為(p,K,λ,t)-ADS。

定義4令D={d0,d1,d2,…,dK-1}表示整數(shù)環(huán)ZJ上一個(gè)含有K 個(gè)不同整數(shù)的集合，dk∈ZJ，0≤ k ≤K-1。集合D 的特征序列定義為一個(gè)二元序列a=(a0,a1,…,aJ-1)，其中有

則稱集合D 為序列a=(a0,a1,…,aJ-1)的支撐集。顯然，序列的漢明重量。

定義5設(shè)N,γ 是2 個(gè)互質(zhì)的正整數(shù)，則Zadoff-Chu 序列族的第γ 行序列可以表示為

其中，k=0,1,…,N-1，g 是一個(gè)整數(shù)。

3 基于二元序列的碼本構(gòu)造框架

文獻(xiàn)[18]提出一類基于二元序列的碼本構(gòu)造框架，其構(gòu)造過程如下。

步驟1定義一個(gè)變換矩陣，令φi,l表示矩陣中任意元素，0≤i ≤J-1，0≤l ≤N-1。矩陣滿足以下性質(zhì)。

性質(zhì)1每個(gè)矩陣元素具有單位幅值，即。

性質(zhì)2任意2 個(gè)不同列向量滿足=φi,l，0 ≤l1≠l2，l ≤N-1，0≤i ≤J-1。

性質(zhì)3矩陣Φ 的第一列為全1 向量，即φi,0=1，0≤i ≤J-1。

性質(zhì)4對(duì)于任意0＜l≤N-1，有。

滿足上述性質(zhì)的變換矩陣已知的有N × N的Hadamard 矩陣和IDFT 矩陣。

步驟2取二元序列 a=(a0,a1,…,aJ-1)，序列的漢明重量wt(a)=K，設(shè)集合D={d0,d1,d2,…,dK-1}是序列a 的支撐集。構(gòu)造碼本CΦ(a)={C0,C1,…,CN-1}為

其中，Cl為構(gòu)造的碼本中的一個(gè)行向量，集合D 是變換矩陣Φ 的行索引集，即元素φdk,l(0≤ k ≤K-1)是矩陣中第 dk行、第l 列元素，則 CΦ(a)即為得到的(N,K)碼本，其最大互相關(guān)幅度值 Imax(CΦ(a))可以由變換矩陣與二元序列的支撐集計(jì)算得到。

文獻(xiàn)[18]構(gòu)造的框架包含了已有的一些碼本構(gòu)造方法作為特殊情況。例如，當(dāng)選取N × N階的IDFT 矩陣作為變換矩陣Φ 時(shí)，若選取的二元序列對(duì)應(yīng)的支撐集為差集時(shí)，得到的碼本 CΦ(a)即為文獻(xiàn)[4]的結(jié)果。若二元或復(fù)Hadamard 矩陣作為矩陣Φ，則選取的二元序列對(duì)應(yīng)支撐集為幾乎差集時(shí)，得到的碼本 CΦ(a)為文獻(xiàn)[5-6]的結(jié)果。該構(gòu)造框架有2 個(gè)關(guān)鍵因素：1)變換矩陣Φ 的選取；2)二元序列a 的支撐集選取?；谠摌?gòu)造框架，文獻(xiàn)[19]通過選取不同的二元序列構(gòu)造了參數(shù)幾乎最優(yōu)的碼本。同時(shí)文獻(xiàn)[19]也指出，可以通過構(gòu)造新的變換矩陣來構(gòu)造新的碼本，然而并沒有給出新的變換矩陣構(gòu)造方法。文獻(xiàn)[20]同樣采用Hadamard 矩陣作為變換矩陣，通過設(shè)計(jì)一類新的二元序列進(jìn)而構(gòu)造了一類最優(yōu)碼本。本文從另一個(gè)角度出發(fā)，通過設(shè)計(jì)新的變換矩陣來構(gòu)造新的碼本。

4 最優(yōu)碼本的構(gòu)造

本文提出的新的構(gòu)造方法介紹如下。

步驟1根據(jù)定義5，令g=0，γ =1，N 是偶數(shù)，得到Zadoff-Chu 矩陣的第一行。令，k=0,1,…,N-1，由此定義 Zadoff-Chu 矩陣為

其中，0≤ s,t ≤N-1。文獻(xiàn)[21]中令矩陣Φ 的N 為偶數(shù)來構(gòu)造測量矩陣，而本文取N 為奇數(shù)的情況來構(gòu)造碼本。

步驟2設(shè)D={d0,d1,d2,…,dK-1}表示整數(shù)環(huán)ZN上一個(gè)含有K 個(gè)不同整數(shù)的集合，dk∈ZN，0≤ k ≤K-1。構(gòu)造碼本CΦ={C0,C1,…,CN-1}為

則 CΦ即為得到的(N,K)碼本。

定理1令CΦ為本文新的構(gòu)造法得到(N,K)碼本，則最大相關(guān)幅度值為

證明設(shè) Cl,Ct∈ CΦ，0≤t≠l ≤N-1，則有

證畢。

4.1 基于差集的最優(yōu)碼本

引理3[5]令集合D={d0,d1,d2,…,dK-1}表示有限域 Fp上的一個(gè)差集(p,K,λ)-DS，則對(duì)于任意γ≠0(mod p)有

根據(jù)引理3，可以得到下面結(jié)論。

定理2令N=p為素?cái)?shù)，若集合D={d0,d1,d2,…,dK-1}為有限域 Fp上的一個(gè)差集(p,K,λ)-DS，則式(9)定義的碼本參數(shù)為(p,K)，碼本的字符集大小為2p，最大相關(guān)幅度值為，該碼本達(dá)到Welch 界。

證明碼本的最大相關(guān)幅度值可以由定理1 和引理3 直接得到。根據(jù)引理1 可知，該碼本最大相關(guān)幅度值等于Welch 界，是一類最優(yōu)的碼本。

證畢。

例1令p=7，取集合 D={1,2,4}，可知其是一個(gè)差集(7,3,1)-DS，得到(7,3)碼本為

定理2 得到的碼本與文獻(xiàn)[4,18]具有相同的參數(shù)和相同的最大相關(guān)幅值，但不是同一類碼本。由于變換矩陣的選擇不同，2 類碼本內(nèi)部的元素也不相同。文獻(xiàn)[4,18]的碼本選取的變換矩陣是IDFT 矩陣，字符集更?。欢ɡ? 構(gòu)造的碼本的變換矩陣是Zadoff-Chu 矩陣，限制條件更少，構(gòu)造更靈活。例如，選取同樣的差集 D={1,2,4}，文獻(xiàn)[4,18]得到的碼本為

4.2 基于幾乎差集的最優(yōu)碼本

引理4[5]令p=1(mod4)，則2階分圓類是有限域Fp上的幾乎差集，參數(shù)為,-ADS。對(duì)于該幾乎差集，Δ≠0，有

根據(jù)引理4，可以得到下面結(jié)論。

定理3令N=p為素?cái)?shù)，若集合D={ d0,d1,d2,…,dK-1}為有限域Fp上的幾乎差集,-ADS，即，則式(9)定義的碼本參數(shù)為，碼本的字符集大小為2p，最大相關(guān)幅度值為。該碼本漸進(jìn)達(dá)到Welch 界。

證明根據(jù)構(gòu)造過程可知向量數(shù)目N=p，向量長度，計(jì)算其互相關(guān)幅度如下。由引理4可知，對(duì)于幾乎差集，有≤。又由定理1 可得，碼本最大相關(guān)幅度值為

可以看出，當(dāng)p 增大時(shí)，該碼本漸進(jìn)達(dá)到Welch 界。

證畢。

4.3 基于特征和的最優(yōu)碼本

令 ξK表示K 維希爾伯特空間的標(biāo)準(zhǔn)正交基所構(gòu)成的集合，即由下面K 個(gè)長度為K 的向量ei(1≤i ≤K)組成的集合為

其中，e1=(1,0,···,0)，e2=(0,1,···,0)，·· ·，eK=(0,0,···,1)。

設(shè)q=pn是素?cái)?shù)的冪，其中p 為素?cái)?shù)。令a∈Fq，定義集合。有限域上的艾森斯坦和（Eisenstein sum）定義為

引理5[22]令χ 表示有限域上的非平凡乘法特征，對(duì)于任意，有

定理4令s=2，N=q2-1，a 是有限域的本原元，。選取集合D={d0,d1,d2,…,dK-1}為dk=logax，

設(shè)CΦ表示式(9)定義的碼本，則CΦ∪ξK是(q2+q-1,q)碼本，碼本的字符集大小為2p+1，其最大互相關(guān)幅度為。

證明由上述構(gòu)造過程可知向量長度K==qs-1=q，向量數(shù)目為N=q2+q-1。其互相關(guān)幅度值計(jì)算如下。

當(dāng) Cl,Ct∈ξK時(shí)，很容易得。

當(dāng) Cl∈ξK，Ct∈CΦ時(shí)，有。

當(dāng) Cl,Ct∈ CΦ時(shí)，根據(jù)定理1 有

定理5碼本CΦ∪ξK依照Levenstein界是漸進(jìn)最優(yōu)的。

證明對(duì)于參數(shù)為(q2+q-1,q)的復(fù)數(shù)碼本CΦ∪ξK，其中N ＞K2，根據(jù)引理2 可得，最大互相關(guān)幅度值的Levenstein 界為式(5)，即

進(jìn)一步可得

證畢。

5 最優(yōu)碼本構(gòu)造方法的對(duì)比分析

對(duì)基于文獻(xiàn)[18]的框架思想提出的幾類最優(yōu)碼本構(gòu)造方法進(jìn)行比較，如表1 所示。

表1 幾類最優(yōu)碼本的構(gòu)造方法

由表1 可以看出，根據(jù)文獻(xiàn)[18]提出的碼本構(gòu)造框架，可以通過選取不同的變換矩陣和集合來構(gòu)造不同參數(shù)的碼本。已有的方法都是基于IDFT 矩陣或Hadamard 矩陣，利用不同的集合來構(gòu)造碼本。本文提出了一類新的變換矩陣，利用已有的差集、幾乎差集和有限域上的艾森斯坦和定義的一個(gè)集合構(gòu)造了參數(shù)最優(yōu)和漸進(jìn)最優(yōu)的碼本。定理2 和定理3 與已有的文獻(xiàn)[4,18]和文獻(xiàn)[5]中的最優(yōu)碼本具有相同的參數(shù)和最大相關(guān)幅度值，因此可以為通信系統(tǒng)或信息處理提供更多的選擇。定理4 構(gòu)造出一類新的碼本，依照Levenstein 界漸進(jìn)最優(yōu)，相比較依照Welch 界漸進(jìn)最優(yōu)的碼本，最大互相關(guān)幅度值更小。雖然新變換矩陣放寬了限制條件使得字符集變大，但是在構(gòu)造相同參數(shù)的碼本時(shí)，變換矩陣在選取上具有了更強(qiáng)的靈活性。在構(gòu)造壓縮感知確定性測量矩陣等不要求字符集的應(yīng)用中，本文構(gòu)造的碼本是更好的選擇。

圖1 稀疏度隨重建概率變化曲線

由圖1(a)可以看出，由本文定理2 中的碼本構(gòu)造的確定性測量矩陣在相同稀疏度時(shí)，重建信號(hào)的概率明顯高于隨機(jī)DFT 矩陣和隨機(jī)復(fù)高斯矩陣。利用定理2 構(gòu)造出的確定性測量矩陣與利用文獻(xiàn)[4,18]構(gòu)造的測量矩陣具有相同的參數(shù)，在重建信號(hào)的概率上甚至略高于文獻(xiàn)[4,18]中的方法。同理，利用本文定理3 中的碼本構(gòu)造的確定性測量矩陣在重建信號(hào)的概率上明顯高于隨機(jī)測量矩陣。

6 結(jié)束語

基于文獻(xiàn)[18]的碼本構(gòu)造思想，本文放松了變換矩陣的限制條件，提出了一類新的Zadoff-Chu 矩陣，并利用差集、幾乎差集和有限域上的特征和構(gòu)造了3 類碼本，參數(shù)分別為(p,K)、和(q2+q-1,q)。本文構(gòu)造的碼本與已有碼本的參數(shù)和最大互相關(guān)幅度值相同并且可以達(dá)到最優(yōu)或漸進(jìn)最優(yōu)。本文方法可以為同步CDMA 通信系統(tǒng)提供大量可用碼本，并且可以通過文獻(xiàn)[3]的方法將本文得到的碼本應(yīng)用于壓縮感知領(lǐng)域中確定性測量矩陣的構(gòu)造，得到的確定性測量矩陣在重構(gòu)信號(hào)的概率上明顯優(yōu)于隨機(jī)測量矩陣。