This paper was converted on www.awesomepapers.org from LaTeX by an anonymous user.
Want to know more? Visit the Converter page.

Two-Dimensional Golay Complementary Array Sets from Generalized Boolean Functions

Cheng-Yu Pai and Chao-Yu Chen The material in this paper was presented in part at the IEEE International Symposium on Information Theory (ISIT), June 2020. This work was supported the Ministry of Science and Technology, Taiwan, R.O.C., under Grants MOST 109–2628–E–006–008–MY3.The authors are with the Department of Engineering Science, National Cheng Kung University, Tainan 701, Taiwan, R.O.C. (e-mail: {n98081505, super}@mail.ncku.edu.tw).
Abstract

The one-dimensional (1-D) Golay complementary set (GCS) has many well-known properties and has been widely employed in engineering. The concept of 1-D GCS can be extended to the two-dimensional (2-D) Golay complementary array set (GCAS) where the 2-D aperiodic autocorrelations of constituent arrays sum to zero except for the 2-D zero shift. The 2-D GCAS includes the 2-D Golay complementary array pair (GCAP) as a special case when the set size is 2. In this paper, 2-D generalized Boolean functions are introduced and novel constructions of 2-D GCAPs, 2-D GCASs, and 2-D Golay complementary array mates based on generalized Boolean functions are proposed. Explicit expressions of 2-D Boolean functions for 2-D GCAPs and 2-D GCASs are given. Therefore, they are all direct constructions without the aid of other existing 1-D or 2-D sequences. Moreover, for the column sequences and row sequences of the constructed 2-D GCAPs, their peak-to-average power ratio (PAPR) properties are also investigated.

Index Terms:
Golay complementary pair (GCP), Golay complementary array pair (GCAP), Golay complementary array mate, Golay complementary array set (GCAS), peak-to-average power ratio (PAPR).

I Introduction

One-dimensional (1-D) Golay complementary pair (GCP) [1] and its extension, Golay complementary set (GCS) [2], have zero autocorrelation sums for non-zero shifts and hence have been found many applications, such as channel estimation [3], synchronization [4], interference mitigation for multi-carrier code division multiple access (MC-CDMA) [5], and peak-to-average power ratio (PAPR) control in orthogonal frequency division multiplexing (OFDM) [6, 7, 8, 9]. Such special 1-D sequence pairs and sets can be extended to two-dimensional (2-D) array pairs and sets, called 2-D Golay complementary array pairs (GCAPs) [10, 11, 12, 13] and 2-D Golay complementary array sets (GCASs)[14, 15], respectively. For 2-D GCAPs and 2-D GCASs, the aperiodic autocorrelations of constituent arrays sum up to zero except for the 2-D zero shift. Owing to their good autocorrelation properties, they have applications in radar [16], synchronization [17],[18], multiple-input multiple-output (MIMO) [15], and can be used as spreading sequences in the 2-D MC-CDMA system [19], [20].

In 1999, Davis and Jedweb first proposed a direct construction of 1-D GCPs based on generalized Boolean functions [8]. The construction from generalized Boolean functions has algebraic structure and hence can be friendly for efficient hardware generations. Since then, there have been a number of literature investigating constructions of 1-D sequences from Boolean functions, including GCSs [9, 21, 22, 23, 24, 25], complete complementary codes (CCCs) [26, 27, 28, 29]. Z-complementary pairs (ZCPs) [30, 31, 32, 33, 34, 35], and Z-complementary sets (ZCSs)[36, 37].

In [10], 2-D binary GCAPs can be obtained from existing 1-D GCPs or 2-D GCAPs by using Kronecker product. Later in [13], Fiedler et al. applied the method given in [10] recursively to construct multi-dimensional GCAPs and then 2-D GCAPs can be obtained via projection. In [11], via concatenating existing 1-D GCPs or interleaving existing 2-D GCAPs, 2-D GCAPs can be constructed. In [14], Zeng and Zhang proposed a construction of 2-D GCASs based on 2-D perfect arrays and only periodic GCASs were considered. Recently, [15] provided constructions of 2-D GCASs from existing 1-D GCSs or 1-D CCCs. In addition to 2-D GCAPs and GCASs, 2-D CCCs were studied in [38, 19, 20, 39]. 2-D CCCs can be seen as a collection of 2-D GCASs, where any two different 2-D GCAS are mutually orthogonal. The existing constructions of 2-D CCCs need the help of special 1-D sequences, such as Welti codes [38] and 1-D CCCs [20].

So far, most constructions of 2-D GCAPs or GCASs still require existing sequences or arrays as kernels. Motivated by this, in this paper, novel constructions of 2-D GCAPs, 2-D GCASs, and 2-D Golay complementary array mate based on generalized Boolean functions are proposed. Our proposed constructions are direct constructions and do not require the aid of any existing arrays or specific 1-D sequences. The newly proposed 2-D GCAPs and Golay complementary array mates can include our previous results [40, Th.6] and [40, Th.7] as special cases***In our previous conference paper [40], we provided constructions of 2-D GCAPs and 2-D Golay complementary array mates from Boolean functions which can be found in [40, Th.6] and [40, Th.7], respectively. The result from [40, Th.6] will be described in Theorem 9 in this paper. Then, we provide more general constructions of 2-D GCAPs and Golay complementary array mates in Theorem 12 and Theorem 16, respectively.. Besides 2-D GCAPs and 2-D Golay complementary array mate, we further propose a construction of 2-D GCASs from Boolean functions as well. To the best of authors’ knowledge, this is the first work to directly construct GCASs without the aid of other special sequences. Furthermore, we analyze the column sequence PAPR and the row sequence PAPR for our proposed 2-D GCAPs and their PAPR upper bounds are derived, respectively, in this paper. Note that the column sequence PAPR is concerned in the MC-CDMA system [28, 41].

The rest of this paper is organized as follows. Section II gives some notations and definitions. New constructions of 2-D GCAPs, GCASs, and Golay complementary array mates are presented in Section III. The column sequence PAPRs and row sequence PAPRs are also discussed. Finally, we conclude our paper in Section IV.

II Preliminaries and Notations

The following notations will be used throughout this paper:

  • •

    (⋅)∗(\cdot)^{*} denotes the complex conjugation.

  • •

    (⋅)T(\cdot)^{T} denotes the transpose.

  • •

    𝟏1 is an all-one vector.

  • •

    ℤq={0,1,⋯,q−1}\mathbb{Z}_{q}=\{0,1,\cdots,q-1\} is the ring of integers modulo qq.

  • •

    Let ξ=e2​π​−1/q\xi=e^{2\pi\sqrt{-1}/q}.

  • •

    We consider even integer qq in this paper.

A complex-valued array 𝑪C of size L1×L2L_{1}\times L_{2} can be expressed as

𝑪=(Cg,i), 0≤g<L1,0≤i<L2.{\mbox{\boldmath$C$}}=(C_{g,i}),~{}\,0\leq g<L_{1},0\leq i<L_{2}. (1)
Definition 1

The 2-D aperiodic cross-correlation function of arrays 𝐂C and 𝐃D at shift (u1,u2)(u_{1},u_{2}) is defined as

ρ​(𝑪,𝑫;u1,u2)=∑g=0L1−1∑i=0L2−1Dg+u1,i+u2​Cg,i∗,\rho({\mbox{\boldmath$C$}},{\mbox{\boldmath$D$}};u_{1},u_{2})=\sum\limits_{g=0}^{L_{1}-1}\sum\limits_{i=0}^{L_{2}-1}{D}_{g+u_{1},i+u_{2}}{C}^{*}_{g,i}, (2)

where Dg+u1,i+u2=0{D}_{g+u_{1},i+u_{2}}=0 when (g+u1)∉{0,1,⋯,L1−1}(g+u_{1})\not\in\{0,1,\cdots,L_{1}-1\} or (i+u2)∉{0,1,⋯,L2−1}(i+u_{2})\not\in\{0,1,\cdots,L_{2}-1\}. When 𝐂=𝐃{\mbox{\boldmath$C$}}={\mbox{\boldmath$D$}}, ρ​(𝐂,𝐂;u1,u2)\rho({\mbox{\boldmath$C$}},{\mbox{\boldmath$C$}};u_{1},u_{2}) is called the 2-D aperiodic autocorrelation function of 𝐂C and denoted by ρ​(𝐂;u1,u2)\rho({\mbox{\boldmath$C$}};u_{1},u_{2}). Note that ρ​(𝐂;u1,−u2)=ρ∗​(𝐂;−u1,u2)\rho({\mbox{\boldmath$C$}};u_{1},-u_{2})=\rho^{*}({\mbox{\boldmath$C$}};-u_{1},u_{2}).

If we take L1=1L_{1}=1, then the array 𝑪C can be reduced to a 1-D sequence 𝑪=Ci{\mbox{\boldmath$C$}}=C_{i} for i=0,1,…,L2−1i=0,1,\ldots,L_{2}-1. Therefore, the corresponding 1-D autocorrelation can be given by

ρ​(𝑪;u)=∑i=0L2−1Ci+u​Ci∗,\rho({\mbox{\boldmath$C$}};u)=\sum\limits_{i=0}^{L_{2}-1}{C_{i+u}C^{*}_{i}}, (3)

where Ci+u=0C_{i+u}=0 when (i+u)∉{0,1,⋯,L2−1}(i+u)\not\in\{0,1,\cdots,L_{2}-1\}. In this paper, we only consider qq-PSK modulation. Thus, we define a qq-ary array 𝒄c and (1) can be rewritten as

𝒄=(cg,i)​ and 𝑪=(Cg,i)=(ξcg,i)=ξ𝒄,\displaystyle{\mbox{\boldmath$c$}}=(c_{g,i})\text{ and }{\mbox{\boldmath$C$}}=(C_{g,i})=(\xi^{c_{g,i}})=\xi^{\mbox{\boldmath$c$}}, (4)

where 0≤g<L10\leq g<L_{1} and 0≤i<L20\leq i<L_{2}. The 2-D aperiodic cross-correlation function given in (2) can also be expressed as

ρ​(𝑪,𝑫;u1,u2)=∑g=0L1−1∑i=0L2−1ξdg+u1,i+u2−cg,i.\rho({\mbox{\boldmath$C$}},{\mbox{\boldmath$D$}};u_{1},u_{2})=\sum\limits_{g=0}^{L_{1}-1}\sum\limits_{i=0}^{L_{2}-1}\xi^{d_{g+u_{1},i+u_{2}}-c_{g,i}}. (5)

If taking L1=1L_{1}=1, the corresponding 1-D autocorrelation can be modified as

ρ​(𝑪;u)=∑i=0L2−1ξci+u−ci.\rho({\mbox{\boldmath$C$}};u)=\sum\limits_{i=0}^{L_{2}-1}\xi^{c_{i+u}-c_{i}}. (6)
Definition 2 (Golay Complementary Set)

[2] A set of NN sequences 𝐂0,𝐂1,⋯,𝐂N−1{\mbox{\boldmath$C$}_{0}},{\mbox{\boldmath$C$}_{1}},\cdots,{\mbox{\boldmath$C$}_{N-1}} of length LL is a 1-D GCS, denoted by (N,L)(N,L)-GCS, if and only if

∑l=0N−1ρ​(𝑪l;u)={0,u≠0N​L,u=0.\sum_{l=0}^{N-1}{\rho}({\mbox{\boldmath$C$}_{l}};u)=\begin{cases}0,&u\neq 0\\ NL,&u=0.\end{cases} (7)

Note that a GCS is reduced to a GCP by taking N=2N=2 and each sequence in a GCP is a Golay sequence.

Definition 3 (Golay Complementary Mate)

[2] For a GCP (𝐂0,𝐂1)({\mbox{\boldmath$C$}_{0}},{\mbox{\boldmath$C$}_{1}}), if another GCP (𝐃0,𝐃1)({\mbox{\boldmath$D$}_{0}},{\mbox{\boldmath$D$}_{1}}) meets the following condition:

ρ​(𝑪0,𝑫0;u)+ρ​(𝑪1,𝑫1;u)=0​for all​u,{\rho}({\mbox{\boldmath$C$}_{0}},{\mbox{\boldmath$D$}_{0}};u)+{\rho}({\mbox{\boldmath$C$}_{1}},{\mbox{\boldmath$D$}_{1}};u)=0~{}~{}\text{for all}~{}u, (8)

then they are called the Golay complementary mate of each other.

Definition 4 (Golay Complementary Array Pair)

A pair of arrays 𝐂C and 𝐃D of size L1×L2L_{1}\times L_{2} is called a GCAP, if

ρ​(𝑪;u1,u2)+ρ​(𝑫;u1,u2)={2​L1​L2,(u1,u2)=(0,0)0,(u1,u2)≠(0,0).{\rho}({{\mbox{\boldmath$C$}}};u_{1},u_{2})+{\rho}({{\mbox{\boldmath$D$}}};u_{1},u_{2})=\begin{cases}2L_{1}L_{2},&(u_{1},u_{2})=(0,0)\\ 0,&(u_{1},u_{2})\neq(0,0).\\ \end{cases} (9)

If 𝐂=(ξcg,i)\mbox{\boldmath$C$}=(\xi^{c_{g,i}}) and 𝐃=(ξdg,i)\mbox{\boldmath$D$}=(\xi^{d_{g,i}}) where 𝐜=(cg,i)\mbox{\boldmath$c$}=(c_{g,i}) and 𝐝=(dg,i)\mbox{\boldmath$d$}=(d_{g,i}) over ℤq{\mathbb{Z}}_{q} for 0≤g<L1,0≤i<L20\leq g<L_{1},0\leq i<L_{2}, then we also call this array pair (𝐜,𝐝)(\mbox{\boldmath$c$},\mbox{\boldmath$d$}) a qq-ary GCAP.

Definition 5 (Golay Complementary Array Mate)

Given two GCAPs (𝐀,𝐁)({\mbox{\boldmath$A$}},{\mbox{\boldmath$B$}}) and (𝐂,𝐃)({\mbox{\boldmath$C$},\mbox{\boldmath$D$}}), they are called the Golay complementary array mate of each other if

ρ​(𝑨,𝑪;u1,u2)+ρ​(𝑩,𝑫;u1,u2)=0​for all​(u1,u2).{\rho}({\mbox{\boldmath$A$}},{\mbox{\boldmath$C$}};u_{1},u_{2})+{\rho}({\mbox{\boldmath$B$}},{\mbox{\boldmath$D$}};u_{1},u_{2})=0~{}~{}\text{for all}~{}(u_{1},u_{2}). (10)
Definition 6 (Golay Complementary Array Set)

Given a set of array G={𝐂l|l=0,⋯,N−1}G=\{{\mbox{\boldmath$C$}}_{l}|~{}l=0,\cdots,N-1\}, where each array 𝐂l{\mbox{\boldmath$C$}}_{l} is of size L1×L2L_{1}\times L_{2}, GG is called an (N,L1,L2)(N,L_{1},L_{2})-GCAS if

∑l=0N−1ρ​(𝑪l;u1,u2)={N​L1​L2,(u1,u2)=(0,0)0,(u1,u2)≠(0,0).\displaystyle\sum_{l=0}^{N-1}\rho({\mbox{\boldmath$C$}}_{l};u_{1},u_{2})=\begin{cases}NL_{1}L_{2},~{}~{}~{}(u_{1},u_{2})=(0,0)\\ 0,~{}~{}~{}(u_{1},u_{2})\neq(0,0).\end{cases} (11)

If 𝐂l=(ξ𝐜l){\mbox{\boldmath$C$}}_{l}=(\xi^{{\bf c}_{l}}) where 𝐜l{\mbox{\boldmath$c$}}_{l} is a qq-ary array over ℤq{\mathbb{Z}}_{q} for l=0,1,⋯,N−1l=0,1,\cdots,N-1, then we call the array set {𝐜0,𝐜1,⋯,𝐜N−1}\{{\mbox{\boldmath$c$}}_{0},{\mbox{\boldmath$c$}}_{1},\cdots,{\mbox{\boldmath$c$}}_{N-1}\} a qq-ary GCAS. Actually, a GCAP is a (2,L1,L2)(2,L_{1},L_{2})-GCAS.

II-A Peak-to-Average Power Ratio

For a qq-PSK modulated array 𝑪C given in (4), we define 𝑪g{\mbox{\boldmath$C$}}_{g} and 𝑪iT{\mbox{\boldmath$C$}}^{T}_{i} as the gg-th row sequence and the ii-th column sequence, respectively. That is,

𝑪g=(Cg,0,Cg,1,⋯,Cg,L2−1),𝑪iT=(C0,i,C1,i,⋯,CL1−1,i)T.{\mbox{\boldmath$C$}}_{g}=(C_{g,0},C_{g,1},\cdots,C_{g,L_{2}-1}),~{}~{}{\mbox{\boldmath$C$}}^{T}_{i}=(C_{0,i},C_{1,i},\cdots,C_{L_{1}-1,i})^{T}. (12)

For the row sequence 𝑪g{\mbox{\boldmath$C$}}_{g}, the complex baseband OFDM signal is given by

S𝑪g​(t)=∑i=0L2−1Cg,i​e2​π​−1​i​t=∑i=0L2−1ξcg,i​e2​π​−1​i​t,0≤t≤1S_{{\mbox{\tiny\boldmath$C$}}_{g}}(t)=\sum_{i=0}^{L_{2}-1}C_{g,i}e^{2\pi\sqrt{-1}it}=\sum_{i=0}^{L_{2}-1}\xi^{c_{g,i}}e^{2\pi\sqrt{-1}it},~{}~{}0\leq t\leq 1 (13)

where L2L_{2} equals to the number of subcarriers. The PAPR of a row sequence 𝑪g{\mbox{\boldmath$C$}}_{g} is defined as

PAPR​(𝑪g)=max0≤t≤1⁡|S𝑪g​(t)|2L2\mbox{PAPR}({\mbox{\boldmath$C$}}_{g})=\max_{0\leq t\leq 1}\frac{|S_{{\mbox{\tiny\boldmath$C$}}_{g}}(t)|^{2}}{L_{2}} (14)

where L2L_{2} is the average power for qq-PSK modulated sequences. Similarly, the PAPR of a column sequence 𝑪iT{\mbox{\boldmath$C$}}^{T}_{i} can also be given by

PAPR​(𝑪iT)=max0≤t≤1⁡|S𝑪iT​(t)|2L1,\mbox{PAPR}({\mbox{\boldmath$C$}}^{T}_{i})=\max_{0\leq t\leq 1}\frac{|S_{{\mbox{\tiny\boldmath$C$}}^{T}_{i}}(t)|^{2}}{L_{1}}, (15)

where

S𝑪iT​(t)=∑g=0L1−1Cg,i​e2​π​−1​g​t=∑g=0L1−1ξcg,i​e2​π​−1​g​t,0≤t≤1.S_{{\mbox{\tiny\boldmath$C$}}^{T}_{i}}(t)=\sum_{g=0}^{L_{1}-1}C_{g,i}e^{2\pi\sqrt{-1}gt}=\sum_{g=0}^{L_{1}-1}\xi^{c_{g,i}}e^{2\pi\sqrt{-1}gt},~{}~{}0\leq t\leq 1. (16)

Note that for an MC-CDMA system, the column PAPR of 𝑪iT{\mbox{\boldmath$C$}}^{T}_{i} is concerned since 𝑪iT{\mbox{\boldmath$C$}}^{T}_{i} is spread in the ii-th chip-slot over the L1L_{1} subcarriers [28].

II-B Generalized Boolean Functions

Here, we will introduce the 2-D generalized Boolean function. A 2-D generalized Boolean function f:ℤ2n+m→ℤqf:\mathbb{Z}_{2}^{n+m}\rightarrow\mathbb{Z}_{q} comprises n+mn+m variables y1,y2,…,yn,x1,x2,…,xmy_{1},y_{2},\ldots,y_{n},x_{1},x_{2},\ldots,x_{m}, where xi,yg∈{0,1}x_{i},y_{g}\in\{0,1\} for g=1,2,…,ng=1,2,\ldots,n and i=1,2,…,mi=1,2,\ldots,m. We define the monomial of degree rr as a product of rr distinct variables. For example, x1​x2​x3x_{1}x_{2}x_{3} is a monomial of degree 3 and x1​x2​x3​y1​y2x_{1}x_{2}x_{3}y_{1}y_{2} is a monomial of degree 5. For simplicity, we define the variables z1,z2,⋯,zn+mz_{1},z_{2},\cdots,z_{n+m} as

zl={ylfor​1≤l≤n;xl−nfor​n<l≤m+n,z_{l}=\begin{cases}y_{l}&\text{for}~{}1\leq l\leq n;\\ x_{l-n}&\text{for}~{}n<l\leq m+n,\end{cases} (17)

which will be very useful in our proposed construction methods. For a qq-ary generalized Boolean function with n+mn+m variables, we define the associated array as

𝒇=(f0,0f0,1⋯f0,2m−1f1,0f1,1⋯f1,2m−1⋮⋮⋱⋮f2n−1,0f2n−1,1⋯f2n−1,2m−1){\mbox{\boldmath$f$}}=\begin{pmatrix}f_{0,0}&f_{0,1}&\cdots&f_{0,2^{m}-1}\\ f_{1,0}&f_{1,1}&\cdots&f_{1,2^{m}-1}\\ \vdots&\vdots&\ddots&\vdots\\ f_{2^{n}-1,0}&f_{2^{n}-1,1}&\cdots&f_{2^{n}-1,2^{m}-1}\end{pmatrix} (18)

by letting

fg,i=f​((g1,g2,⋯,gn),(i1,i2,⋯,im))f_{g,i}=f((g_{1},g_{2},\cdots,g_{n}),(i_{1},i_{2},\cdots,i_{m})) (19)

where (g1,g2,⋯,gn)(g_{1},g_{2},\cdots,g_{n}) and (i1,i2,⋯,im)(i_{1},i_{2},\cdots,i_{m}) are binary representations of the integers g=∑h=1ngh​2h−1g=\sum_{h=1}^{n}g_{h}2^{h-1} and i=∑j=1mij​2j−1i=\sum_{j=1}^{m}i_{j}2^{j-1}, respectively.

Example 1

If q=4,n=2q=4,n=2, and m=3m=3, the associated array to the generalized Boolean function f=2​z1+z2+3​z3​z5+2​z4f=2z_{1}+z_{2}+3z_{3}z_{5}+2z_{4} is given by

𝒇=(00220321220021031133103233113210).{\mbox{\boldmath$f$}}=\begin{pmatrix}0&0&2&2&0&3&2&1\\ 2&2&0&0&2&1&0&3\\ 1&1&3&3&1&0&3&2\\ 3&3&1&1&3&2&1&0\end{pmatrix}.

This generalized Boolean function ff can also be stated as f=2​y1+y2+3​x1​x3+2​x2f=2y_{1}+y_{2}+3x_{1}x_{3}+2x_{2} according to (17).

III Constructions of GCAPs and GCASs

In this section, constructions of 2-D GCAPs and 2-D GCASs based on generalized Boolean functions will be proposed by each subsection. In addition, a construction of 2-D Golay complementary array mates will be provided as well. Based on our proposed 2-D GCAPs, the column sequence PAPR and row sequence PAPR will be investigated and their upper bounds on PAPRs will also be given, respectively.

III-A GCAPs Based on Generalized Boolean Functions

In this subsection, we will first restate a basic construction of 2-D GCAPs in [40, Th. 6] and then extend it to new constructions of 2-D GCAPs and 2-D Golay complementary array mates. The proposed constructions can include [40, Th. 6] and [40, Th. 7] as special cases.

Let us first introduce the well-known constructions of 1-D GCPs [8] and 1-D GCSs [27] in the following Lemmas, which will be used hereinafter.

Lemma 7

[8, 9] For any integer m≥2m\geq 2, let π\pi be a permutation of the set {1,2,⋯,m}\{1,2,\cdots,m\}. Let the generalized Boolean function be given by

f=\displaystyle f= q2​∑l=1m−1xπ1​(l)​xπ1​(l+1)+∑l=1mpl​xl+p0\displaystyle\frac{q}{2}\sum_{l=1}^{m-1}x_{\pi_{1}(l)}x_{\pi_{1}(l+1)}+\sum_{l=1}^{m}p_{l}x_{l}+p_{0} (20)

where pl∈ℤqp_{l}\in\mathbb{Z}_{q} for l=0,1,⋯,ml=0,1,\cdots,m. The pair

(𝒇,𝒇′)=(𝒇,𝒇+q2​𝒙π​(1))(\mbox{\boldmath$f$},\mbox{\boldmath$f$}^{\prime})=\left({\mbox{\boldmath$f$}},{\mbox{\boldmath$f$}}+\frac{q}{2}{\mbox{\boldmath$x$}}_{\pi(1)}\right) (21)

is a qq-ary GCP of length 2m2^{m}. Note that such constructed GCP is also called a Golay-Davis-Jedwab (GDJ) pair and its PAPR is at most 2.

Lemma 8

[27] For any integer m≥2m\geq 2 and any positive integer k≤mk\leq m, let {1,2,⋯,m}\{1,2,\cdots,m\} be divided into a partition I1,I2,⋯,IkI_{1},I_{2},\cdots,I_{k} and πα\pi_{\alpha} be a bijection mapping from {1,2,⋯,mα}\{1,2,\cdots,m_{\alpha}\} to IαI_{\alpha} where mα=|Iα|m_{\alpha}=|I_{\alpha}| for α=1,2,⋯,k\alpha=1,2,\cdots,k. For the generalized Boolean function given by

f=q2​∑α=1k∑β=1mα−1xπα​(β)​xπα​(β+1)+∑l=1mpl​xl+p0\displaystyle f=\frac{q}{2}\sum_{\alpha=1}^{k}\sum_{\beta=1}^{m_{\alpha}-1}x_{\pi_{\alpha}(\beta)}x_{\pi_{\alpha}(\beta+1)}+\sum_{l=1}^{m}p_{l}x_{l}+p_{0} (22)

where pl​’s∈ℤqp_{l}\text{'s}\in\mathbb{Z}_{q}, the set

G={𝒇+q2​∑α=1kλα​𝒙πα​(1):λα∈{0,1}}\displaystyle G=\left\{{\mbox{\boldmath$f$}}+\frac{q}{2}\sum_{\alpha=1}^{k}\lambda_{\alpha}{\mbox{\boldmath$x$}}_{\pi_{\alpha}(1)}:\lambda_{\alpha}\in\{0,1\}\right\} (23)

is a (2k,2m)(2^{k},2^{m})-GCS. It has been proved that a GCS of size 2k2^{k} has PAPR at most 2k2^{k} [9].

In what follows, we will provide a theorem to construct 2-D GCAPs based on generalized Boolean functions.

Theorem 9

[40, Th. 6] For a qq-ary array 𝐜c, let π1\pi_{1} be a permutation of {1,2,⋯,m}\{1,2,\cdots,m\} and π2\pi_{2} be a permutation of {1,2,⋯,n}\{1,2,\cdots,n\}. Let the generalized Boolean function

f=\displaystyle f= q2​(∑l=1m−1xπ1​(l)​xπ1​(l+1)+∑s=1n−1yπ2​(s)​yπ2​(s+1)+xπ1​(m)​yπ2​(1))\displaystyle\frac{q}{2}\left(\sum_{l=1}^{m-1}x_{\pi_{1}(l)}x_{\pi_{1}(l+1)}+\sum_{s=1}^{n-1}y_{\pi_{2}(s)}y_{\pi_{2}(s+1)}+x_{\pi_{1}(m)}y_{\pi_{2}(1)}\right) (24)
+∑l=1mpl​xl+∑s=1nλs​ys+p0\displaystyle+\sum_{l=1}^{m}p_{l}x_{l}+\sum_{s=1}^{n}\lambda_{s}y_{s}+p_{0}

where pl,λs∈ℤqp_{l},\lambda_{s}\in\mathbb{Z}_{q}. Then, the array pair

(𝒄,𝒅)=(𝒇,𝒇+q2​𝒙π1​(1))({\mbox{\boldmath$c$}},{\mbox{\boldmath$d$}})=\left({\mbox{\boldmath$f$}},{\mbox{\boldmath$f$}}+\frac{q}{2}{\mbox{\boldmath$x$}}_{\pi_{1}(1)}\right) (25)

is a qq-ary GCAP of size 2n×2m2^{n}\times 2^{m}.

Proof:

Taking a 2-D GCAP (𝑪,𝑫)(\mbox{\boldmath$C$},\mbox{\boldmath$D$}) of size 2n×2m2^{n}\times 2^{m}, we need to show that

ρ​(𝑪;u1,u2)+ρ​(𝑫;u1,u2)=0,for​(u1,u2)≠(0,0).\rho({\mbox{\boldmath$C$}};u_{1},u_{2})+\rho({\mbox{\boldmath$D$}};u_{1},u_{2})=0,~{}\text{for}~{}(u_{1},u_{2})\neq(0,0). (26)

Let the array

𝑪=ξ𝒄=(ξc0,0ξc0,1⋯ξc0,2m−1ξc1,0ξc1,1⋯ξc1,2m−1⋮⋮⋱⋮ξc2n−1,0ξc2n−1,1⋯ξc2n−1,2m−1),{\mbox{\boldmath$C$}}=\xi^{\mbox{\boldmath$c$}}=\begin{pmatrix}\xi^{c_{0,0}}&\xi^{c_{0,1}}&\cdots&\xi^{c_{0,2^{m}-1}}\\ \xi^{c_{1,0}}&\xi^{c_{1,1}}&\cdots&\xi^{c_{1,2^{m}-1}}\\ \vdots&\vdots&\ddots&\vdots\\ \xi^{c_{2^{n}-1,0}}&\xi^{c_{2^{n}-1,1}}&\cdots&\xi^{c_{2^{n}-1,2^{m}-1}}\end{pmatrix}, (27)

where 𝒄c is expressed as

𝒄=\displaystyle{\mbox{\boldmath$c$}}= q2​(∑l=1m−1𝒙π1​(l)​𝒙π1​(l+1)+∑s=1n−1𝒚π2​(s)​𝒚π2​(s+1)+q2​𝒙π1​(m)​𝒚π2​(1))\displaystyle\frac{q}{2}\left(\sum_{l=1}^{m-1}{\mbox{\boldmath$x$}}_{\pi_{1}(l)}{\mbox{\boldmath$x$}}_{\pi_{1}(l+1)}+\sum_{s=1}^{n-1}{\mbox{\boldmath$y$}}_{\pi_{2}(s)}{\mbox{\boldmath$y$}}_{\pi_{2}(s+1)}+\frac{q}{2}{\mbox{\boldmath$x$}}_{\pi_{1}(m)}{\mbox{\boldmath$y$}}_{\pi_{2}(1)}\right) (28)
+∑l=1mpl​𝒙l+∑s=1nλs​𝒚s+p0⋅𝟏.\displaystyle+\sum_{l=1}^{m}p_{l}{\mbox{\boldmath$x$}}_{l}+\sum_{s=1}^{n}\lambda_{s}{\mbox{\boldmath$y$}}_{s}+p_{0}\cdot{\mbox{\boldmath$1$}}.

Therefore, (26) is equivalent to

ρ​(𝑪;u1,u2)+ρ​(𝑫;u1,u2)\displaystyle\rho({\mbox{\boldmath$C$}};u_{1},u_{2})+\rho({\mbox{\boldmath$D$}};u_{1},u_{2}) =∑g=02n−1∑i=02m−1(ξcg+u1,i+u2−cg,i+ξdg+u1,i+u2−dg,i)\displaystyle=\sum\limits_{g=0}^{2^{n}-1}\sum\limits_{i=0}^{2^{m}-1}\left(\xi^{c_{g+u_{1},{i+u_{2}}}-c_{g,i}}+\xi^{d_{g+u_{1},{i+u_{2}}}-d_{g,i}}\right) (29)
=∑i=02m−1∑g=02n−1(ξcg+u1,i+u2−cg,i+ξdg+u1,i+u2−dg,i)\displaystyle=\sum\limits_{i=0}^{2^{m}-1}\sum\limits_{g=0}^{2^{n}-1}\left(\xi^{c_{g+u_{1},{i+u_{2}}}-c_{g,i}}+\xi^{d_{g+u_{1},{i+u_{2}}}-d_{g,i}}\right)
=0\displaystyle=0

for −2n<u1<2n,−2m<u2<2m-2^{n}<u_{1}<2^{n},-2^{m}<u_{2}<2^{m} and (u1,u2)≠(0,0)(u_{1},u_{2})\neq(0,0). For given integers g,ig,i, let h=g+u1,j=i+u2h=g+u_{1},j=i+u_{2}. We also let (g1,g2,⋯,gn),(h1,h2,⋯,hn),(i1,i2,⋯,im)(g_{1},g_{2},\cdots,g_{n}),(h_{1},h_{2},\cdots,h_{n}),(i_{1},i_{2},\cdots,i_{m}), and (j1,j2,⋯,jm)(j_{1},j_{2},\cdots,j_{m}) be the binary representations of g,h,ig,h,i, and jj, respectively. Then, four cases are considered as follows to prove (29).

Case 1: We suppose iπ1​(1)≠jπ1​(1)i_{\pi_{1}(1)}\neq j_{\pi_{1}(1)} and u2≠0u_{2}\neq 0. We can obtain

ch,j−cg,i−dh,j+dg,i=q2​(iπ1​(1)−jπ1​(1))≡q2(modq)\displaystyle c_{h,j}-c_{g,i}-d_{h,j}+d_{g,i}=\frac{q}{2}(i_{\pi_{1}(1)}-j_{\pi_{1}(1)})\equiv\frac{q}{2}\pmod{q} (30)

implying ξch,j−cg,i/ξdh,j−dg,i=−1\xi^{c_{h,j}-c_{g,i}}/\xi^{d_{h,j}-d_{g,i}}=-1 for all g=0,1,⋯,2n−1g=0,1,\cdots,2^{n-1}. Therefore,

∑g=02n−1(ξch,j−cg,i+ξdh,j−dg,i)=0.\sum\limits_{g=0}^{2^{n}-1}\left(\xi^{c_{h,j}-c_{g,i}}+\xi^{d_{h,j}-d_{g,i}}\right)=0. (31)

Case 2: Suppose iπ1​(1)=jπ1​(1)i_{\pi_{1}(1)}=j_{\pi_{1}(1)} and u2≠0u_{2}\neq 0. We assume tt is the smallest number such that iπ1​(t)≠jπ1​(t)i_{\pi_{1}(t)}\neq j_{\pi_{1}(t)}. Then, we let i′i^{\prime} and j′j^{\prime} be integers different from ii and jj, respectively, only in one position, i.e., iπ1​(t−1)′=1−iπ1​(t−1),jπ​(t−1)′=1−jπ1​(t−1)i^{\prime}_{\pi_{1}(t-1)}=1-i_{\pi_{1}(t-1)},~{}j^{\prime}_{\pi(t-1)}=1-j_{\pi_{1}(t-1)}. Hence, we have

cg,i′−cg,i\displaystyle{c}_{g,i^{\prime}}-{c}_{g,i} =q2(iπ1​(t−2)iπ1​(t−1)′−iπ1​(t−2)iπ1​(t−1)+iπ1​(t−1)′iπ1​(t)\displaystyle=\frac{q}{2}\left({i}_{\pi_{1}(t-2)}i^{\prime}_{\pi_{1}(t-1)}-{i}_{\pi_{1}(t-2)}{i}_{\pi_{1}(t-1)}+i^{\prime}_{\pi_{1}(t-1)}{i}_{\pi_{1}(t)}\right. (32)
−iπ1​(t−1)iπ1​(t))+pπ1​(t−1)i′π1​(t−1)−pπ1​(t−1)iπ1​(t−1)\displaystyle~{}~{}~{}~{}~{}~{}\left.-{i}_{\pi_{1}(t-1)}{i}_{\pi_{1}(t)}\right)+p_{\pi_{1}(t-1)}i^{\prime}_{\pi_{1}(t-1)}-p_{\pi_{1}(t-1)}i_{\pi_{1}(t-1)}
≡q2​(iπ1​(t−2)+iπ1​(t))+pπ1​(t−1)​(1−2​iπ1​(t−1))(modq).\displaystyle\equiv\frac{q}{2}\left({i}_{\pi_{1}(t-2)}+{i}_{\pi_{1}(t)}\right)+p_{\pi_{1}(t-1)}(1-2i_{\pi_{1}(t-1)})\pmod{q}.

Due to the fact that iπ​(t−1)=jπ​(t−1)i_{\pi(t-1)}=j_{\pi(t-1)} and iπ​(t−2)=iπ​(t−2)i_{\pi(t-2)}=i_{\pi(t-2)}, we have

ch,j−cg,i−ch,j′+cg,i′\displaystyle c_{h,j}-c_{g,i}-c_{h,j^{\prime}}+c_{g,i^{\prime}} ≡q2​(iπ1​(t−2)−jπ1​(t−2)+iπ1​(t)−jπ1​(t))\displaystyle\equiv\frac{q}{2}\left({i}_{\pi_{1}(t-2)}-j_{\pi_{1}(t-2)}+{i}_{\pi_{1}(t)}-{j}_{\pi_{1}(t)}\right) (33)
+pπ1​(t−1)​(2​jπ1​(t−1)−2​iπ1​(t−1))\displaystyle+p_{\pi_{1}(t-1)}(2j_{\pi_{1}(t-1)}-2i_{\pi_{1}(t-1)})
≡q2​(iπ1​(t)−jπ1​(t))≡q2(modq)\displaystyle\equiv\frac{q}{2}\left({i}_{\pi_{1}(t)}-{j}_{\pi_{1}(t)}\right)\equiv\frac{q}{2}\pmod{q}

which means ξch,j−cg,i+ξch,j′−cg,i′=0.\xi^{c_{h,j}-c_{g,i}}+\xi^{c_{h,j^{\prime}}-c_{g,i^{\prime}}}=0. Similarly, we can also obtain ξdh,j−dg,i+ξdh,j′−dg,i′=0\xi^{d_{h,j}-d_{g,i}}+\xi^{d_{h,j^{\prime}}-d_{g,i^{\prime}}}=0 implying

∑g=02n−1(ξch,j−cg,i+ξch,j′−cg,i′+ξdh,j−dg,i+ξdh,j′−dg,i′)=0.\displaystyle\sum\limits_{g=0}^{2^{n}-1}\left(\xi^{c_{h,j}-c_{g,i}}+\xi^{c_{h,j^{\prime}}-c_{g,i^{\prime}}}+\xi^{d_{h,j}-d_{g,i}}+\xi^{d_{h,j^{\prime}}-d_{g,i^{\prime}}}\right)=0. (34)

Case 3: We suppose hπ2​(1)≠gπ2​(1)h_{\pi_{2}(1)}\neq g_{\pi_{2}(1)} and u2=0u_{2}=0 implying j=ij=i. For simplicity, we let

𝒂=q2​∑l=1m−1𝒙π1​(l)​𝒙π1​(l+1)​and​𝒃=q2​∑s=1n−1𝒚π2​(s)​𝒚π2​(s+1).{\mbox{\boldmath$a$}}=\frac{q}{2}\sum_{l=1}^{m-1}{\mbox{\boldmath$x$}}_{\pi_{1}(l)}{\mbox{\boldmath$x$}}_{\pi_{1}(l+1)}~{}\text{and}~{}{\mbox{\boldmath$b$}}=\frac{q}{2}\sum_{s=1}^{n-1}{\mbox{\boldmath$y$}}_{\pi_{2}(s)}{\mbox{\boldmath$y$}}_{\pi_{2}(s+1)}. (35)

Then, (28) can be rewritten as

𝒄=𝒂+𝒃+q2​𝒙π1​(m)​𝒚π2​(1)+∑l=1mpl​𝒙l+∑s=1nλs​𝒚s+p0⋅𝟏.{\mbox{\boldmath$c$}}={\mbox{\boldmath$a$}}+{\mbox{\boldmath$b$}}+\frac{q}{2}{\mbox{\boldmath$x$}}_{\pi_{1}(m)}{\mbox{\boldmath$y$}}_{\pi_{2}(1)}+\sum_{l=1}^{m}p_{l}{\mbox{\boldmath$x$}}_{l}+\sum_{s=1}^{n}\lambda_{s}{\mbox{\boldmath$y$}}_{s}+p_{0}\cdot{\mbox{\boldmath$1$}}. (36)

Thus, we have

∑i=02m−1ξch,i−cg,i\displaystyle\sum\limits_{i=0}^{2^{m}-1}\xi^{c_{h,i}-c_{g,i}} =∑i=02m−1(ξbh−bg+q2​iπ1​(m)+∑s=1nλs​(hs−gs))\displaystyle=\sum\limits_{i=0}^{2^{m}-1}\left(\xi^{b_{h}-b_{g}+\frac{q}{2}i_{\pi_{1}(m)}+\sum\limits_{s=1}^{n}\lambda_{s}(h_{s}-g_{s})}\right) (37)
=(ξbh−bg+∑s=1nλs​(hs−gs))​∑i=02m−1ξq2​iπ1​(m)=0\displaystyle=\left(\xi^{b_{h}-b_{g}+\sum\limits_{s=1}^{n}\lambda_{s}(h_{s}-g_{s})}\right)\sum\limits_{i=0}^{2^{m}-1}\xi^{\frac{q}{2}i_{\pi_{1}(m)}}=0

where the last equality comes from ∑i=02m−1ξq2​iπ1​(m)=0\sum\limits_{i=0}^{2^{m}-1}\xi^{\frac{q}{2}i_{\pi_{1}(m)}}=0. Similarly, we can also obtain ∑i=02m−1ξdh,i−dg,i=0\sum\limits_{i=0}^{2^{m}-1}\xi^{d_{h,i}-d_{g,i}}=0 which means

∑i=02m−1(ξch,i−cg,i+ξdh,i−dg,i)=0.\sum\limits_{i=0}^{2^{m}-1}\left(\xi^{c_{h,i}-c_{g,i}}+\xi^{d_{h,i}-d_{g,i}}\right)=0. (38)

Case 4: Suppose hπ2​(1)=gπ2​(1)h_{\pi_{2}(1)}=g_{\pi_{2}(1)} and u2=0u_{2}=0. Assuming tt is the smallest integer with gπ2​(t)≠hπ2​(t)g_{\pi_{2}(t)}\neq h_{\pi_{2}(t)}, we let g′g^{\prime} and h′h^{\prime} be the integers different from gg and hh, respectively, only in position π2​(t−1)\pi_{2}(t-1). That is, gπ2​(t−1)′=1−gπ2​(t−1),hπ2​(t−1)′=1−hπ2​(t−1)g^{\prime}_{\pi_{2}(t-1)}=1-g_{\pi_{2}(t-1)},~{}h^{\prime}_{\pi_{2}(t-1)}=1-h_{\pi_{2}(t-1)}. Using a similar argument as in Case 2, we can obtain

∑i=02m−1(ξch,i−cg,i+ξch′,i−cg′,i+ξdh,i−dg,i+ξdh′,i−dg′,i)=0.\sum\limits_{i=0}^{2^{m}-1}\left(\xi^{{c}_{h,i}-{c}_{g,i}}+\xi^{{c}_{h^{\prime},i}-{c}_{g^{\prime},i}}+\xi^{{d}_{h,i}-{d}_{g,i}}+\xi^{{d}_{h^{\prime},i}-{d}_{g^{\prime},i}}\right)=0. (39)

Combining these four cases, we can prove that (𝑪,𝑫)(\mbox{\boldmath$C$},\mbox{\boldmath$D$}) is a 2-D GCAP of size 2n×2m2^{n}\times 2^{m}. ∎

Corollary 10

The PAPR of any row sequence of the constructed 2-D GCAPs from Theorem 9 is upper bounded by 2.

Proof:

We let 𝒄g{\mbox{\boldmath$c$}}_{g} be the gg-th row sequence of the array 𝒄c in (28). For a given gg, 𝒄g{\mbox{\boldmath$c$}}_{g} can be expressed as

𝒄g=q2​∑l=1m−1𝒙π1​(l)​𝒙π1​(l+1)+∑l=1mpl​𝒙l+q2​𝒙π1​(m)​gπ2​(1)+(p0+κ)​𝟏{\mbox{\boldmath$c$}}_{g}=\frac{q}{2}\sum_{l=1}^{m-1}{\mbox{\boldmath$x$}}_{\pi_{1}(l)}{\mbox{\boldmath$x$}}_{\pi_{1}(l+1)}+\sum_{l=1}^{m}p_{l}{\mbox{\boldmath$x$}}_{l}+\frac{q}{2}{\mbox{\boldmath$x$}}_{\pi_{1}(m)}g_{\pi_{2}(1)}+(p_{0}+\kappa){\mbox{\boldmath$1$}} (40)

where

κ=q2​∑s=1n−1gπ2​(s)​gπ2​(s+1)+∑s=1nλs​gs\kappa=\frac{q}{2}\sum_{s=1}^{n-1}g_{\pi_{2}(s)}g_{\pi_{2}(s+1)}+\sum_{s=1}^{n}\lambda_{s}g_{s} (41)

and g=∑s=1ngs​2s−1g=\sum_{s=1}^{n}g_{s}2^{s-1}. It can be seen that 𝒄g{\mbox{\boldmath$c$}}_{g} is a sequence of a GDJ pair by Lemma 7; hence its PAPR is at most 2. ∎

Corollary 11

The constructed 2-D GCAPs from Theorem 9 also have column sequence PAPRs at most 2.

Proof:

Similar to the proof of Corollary 10, the ii-th column sequence 𝒄iT{\mbox{\boldmath$c$}}^{T}_{i} is shown as

𝒄iT=q2​∑s=1n−1𝒚π2​(s)​𝒚π2​(s+1)+∑s=1nλs​𝒚s+q2​iπ1​(m)​𝒚π2​(1)+(p0+κ′)​𝟏{\mbox{\boldmath$c$}}^{T}_{i}=\frac{q}{2}\sum_{s=1}^{n-1}{\mbox{\boldmath$y$}}_{\pi_{2}(s)}{\mbox{\boldmath$y$}}_{\pi_{2}(s+1)}+\sum_{s=1}^{n}\lambda_{s}{\mbox{\boldmath$y$}}_{s}+\frac{q}{2}{i}_{\pi_{1}(m)}{\mbox{\boldmath$y$}}_{\pi_{2}(1)}+(p_{0}+\kappa^{\prime}){\mbox{\boldmath$1$}} (42)

where

κ′=q2​∑l=1m−1iπ1​(l)​iπ1​(l+1)+∑l=1mpl​il\kappa^{\prime}=\frac{q}{2}\sum_{l=1}^{m-1}i_{\pi_{1}(l)}i_{\pi_{1}(l+1)}+\sum_{l=1}^{m}p_{l}i_{l} (43)

and i=∑l=1mil​2l−1i=\sum_{l=1}^{m}i_{l}2^{l-1}. Clearly, each column sequence can be viewed as a sequence of a GDJ pair and therefore has PAPR upper bounded by 2. ∎

Example 2

For q=4,m=3q=4,~{}m=3, and n=2n=2, we let π1=(3,1,2),π2=(1,2)\pi_{1}=(3,1,2),~{}\pi_{2}=(1,2), and the generalized Boolean function f=2​(x3​x1+x1​x2+y1​y2+x2​y1)+x1f=2(x_{3}x_{1}+x_{1}x_{2}+y_{1}y_{2}+x_{2}y_{1})+x_{1} by taking p1=1p_{1}=1. The array pair (𝐜,𝐝)=(𝐟,𝐟+2​𝐱3)(\mbox{\boldmath$c$},\mbox{\boldmath$d$})=(\mbox{\boldmath$f$},\mbox{\boldmath$f$}+2{\mbox{\boldmath$x$}_{3}}) given by

𝒄=(01030301012103230103030123032101)​and​𝒅=(01032123012121010103212323030323){\mbox{\boldmath$c$}}=\begin{pmatrix}0&1&0&3&0&3&0&1\\ 0&1&2&1&0&3&2&3\\ 0&1&0&3&0&3&0&1\\ 2&3&0&3&2&1&0&1\\ \end{pmatrix}~{}\text{and}~{}{\mbox{\boldmath$d$}}=\begin{pmatrix}0&1&0&3&2&1&2&3\\ 0&1&2&1&2&1&0&1\\ 0&1&0&3&2&1&2&3\\ 2&3&0&3&0&3&2&3\\ \end{pmatrix}

is a GCAP of size 4×84\times 8. According to Corollary 10 and Corollary 11, we know that both the maximum row sequence PAPR and the maximum column sequence PAPR are bounded by 2. Actually, each row sequence PAPR of 𝐜c and 𝐝d is exact 2 and each column sequence PAPR of 𝐜c and 𝐝d is 1.7698.

Next, we extend Theorem 9 to a general construction of 2-D GCAPs.

Theorem 12

Let π\pi be a permutation of {1,2,⋯,n+m}\{1,2,\cdots,n+m\} and the generalized Boolean function can be given by

f=\displaystyle f= q2​∑l=1n+m−1zπ​(l)​zπ​(l+1)+∑l=1n+mpl​zl+p0\displaystyle\frac{q}{2}\sum_{l=1}^{n+m-1}z_{\pi(l)}z_{\pi(l+1)}+\sum_{l=1}^{n+m}p_{l}z_{l}+p_{0} (44)

where zz is defined in (17) and pl,p0∈ℤqp_{l},p_{0}\in\mathbb{Z}_{q}. The array pair

(𝒄,𝒅)=(𝒇,𝒇+q2​𝒛π​(1))({\mbox{\boldmath$c$}},{\mbox{\boldmath$d$}})=\left({\mbox{\boldmath$f$}},{\mbox{\boldmath$f$}}+\frac{q}{2}{\mbox{\boldmath$z$}}_{\pi(1)}\right) (45)

forms a qq-ary GCAP of size 2n×2m2^{n}\times 2^{m}.

Proof:

Similarly, we need to prove that

ρ​(𝑪;u1,u2)+ρ​(𝑫;u1,u2)=∑g=02n−1∑i=02m−1(ξcg+u1,i+u2−cg,i+ξdg+u1,i+u2−dg,i)=0\displaystyle\rho({\mbox{\boldmath$C$}};u_{1},u_{2})+\rho({\mbox{\boldmath$D$}};u_{1},u_{2})=\sum\limits_{g=0}^{2^{n}-1}\sum\limits_{i=0}^{2^{m}-1}\left(\xi^{c_{g+u_{1},{i+u_{2}}}-c_{g,i}}+\xi^{d_{g+u_{1},{i+u_{2}}}-d_{g,i}}\right)=0 (46)

for −2n<u1<2n,−2m<u2<2m-2^{n}<u_{1}<2^{n},-2^{m}<u_{2}<2^{m} and (u1,u2)≠(0,0)(u_{1},u_{2})\neq(0,0). From (4), we know that 𝑪=ξ𝒄\mbox{\boldmath$C$}=\xi^{\mbox{\boldmath$c$}}, where 𝒄c is expressed as

𝒄=\displaystyle{\mbox{\boldmath$c$}}= q2​∑l=1m+n−1𝒛π​(l)​𝒛π​(l+1)+∑l=1n+mpl​𝒛l+p0⋅𝟏.\displaystyle\frac{q}{2}\sum_{l=1}^{m+n-1}{\mbox{\boldmath$z$}}_{\pi(l)}{\mbox{\boldmath$z$}}_{\pi(l+1)}+\sum_{l=1}^{n+m}p_{l}{\mbox{\boldmath$z$}}_{l}+p_{0}\cdot{\mbox{\boldmath$1$}}. (47)

Then we let h=g+u1,j=i+u2h=g+u_{1},j=i+u_{2} for any integers gg and ii. For the sake of easy presentation, we define

al={glfor​1≤l≤n;il−nfor​n<l≤m+n,\displaystyle a_{l}=\begin{cases}g_{l}&\text{for}~{}1\leq l\leq n;\\ i_{l-n}&\text{for}~{}n<l\leq m+n,\end{cases} (48)
bl={hlfor​1≤l≤n;jl−nfor​n<l≤m+n.\displaystyle b_{l}=\begin{cases}h_{l}&\text{for}~{}1\leq l\leq n;\\ j_{l-n}&\text{for}~{}n<l\leq m+n.\end{cases}

Therefore, (19) can be rewritten as

fg,i=f​(a1,a2,⋯​am+n)​and​fh,j=f​(b1,b2,⋯​bm+n),\displaystyle f_{g,i}=f(a_{1},a_{2},\cdots a_{m+n})~{}~{}\text{and}~{}~{}f_{h,j}=f(b_{1},b_{2},\cdots b_{m+n}), (49)

respectively. Then, we consider two cases to show that (46) holds.

Case 1: Suppose aπ​(1)≠bπ​(1)a_{\pi(1)}\neq b_{\pi(1)}. We can obtain

ch,j−cg,i−dh,j+dg,i=q2​(aπ​(1)−bπ​(1))≡q2(modq)c_{h,j}-c_{g,i}-d_{h,j}+d_{g,i}=\frac{q}{2}(a_{\pi(1)}-b_{\pi(1)})\equiv\frac{q}{2}\pmod{q} (50)

implying

ξch,j−cg,i+ξdh,j−dg,i=0.\xi^{c_{h,j}-c_{g,i}}+\xi^{d_{h,j}-d_{g,i}}=0. (51)

Case 2: Suppose aπ​(1)=bπ​(1)a_{\pi(1)}=b_{\pi(1)}. We assume tt is the smallest number such that aπ​(t)≠bπ​(t)a_{\pi(t)}\neq b_{\pi(t)}. Let a′a^{\prime} and b′b^{\prime} be integers different from aa and bb, respectively, only in one position. That is, aπ​(t−1)′=1−aπ​(t−1),bπ​(t−1)′=1−bπ​(t−1)a^{\prime}_{\pi(t-1)}=1-a_{\pi(t-1)},~{}b^{\prime}_{\pi(t-1)}=1-b_{\pi(t-1)}. If 1≤π​(t−1)≤n1\leq\pi(t-1)\leq n, by using (48), we have

cg′,i−cg,i=\displaystyle{c}_{g^{\prime},i}-{c}_{g,i}= q2(aπ​(t−2)gπ​(t−1)′−aπ​(t−2)gπ​(t−1)+gπ​(t−1)′aπ​(t)\displaystyle\frac{q}{2}\left(a_{\pi(t-2)}g^{\prime}_{\pi(t-1)}-a_{\pi(t-2)}g_{\pi(t-1)}+g^{\prime}_{\pi(t-1)}a_{\pi(t)}\right. (52)
−gπ​(t−1)aπ​(t))+pπ​(t−1)g′π​(t−1)−pπ​(t−1)gπ​(t−1)\displaystyle\left.-g_{\pi(t-1)}a_{\pi(t)}\right)+p_{\pi(t-1)}g^{\prime}_{\pi(t-1)}-p_{\pi(t-1)}g_{\pi(t-1)}
≡\displaystyle\equiv q2​(aπ​(t−2)+aπ​(t))+pπ​(t−1)​(1−2​gπ​(t−1))(modq)\displaystyle\frac{q}{2}\left(a_{\pi(t-2)}+a_{\pi(t)}\right)+p_{\pi(t-1)}(1-2g_{\pi(t-1)})\pmod{q}

where aπ​(t−1)′=gπ​(t−1)′a^{\prime}_{\pi(t-1)}=g^{\prime}_{\pi(t-1)} and aπ​(t−1)=gπ​(t−1)a_{\pi(t-1)}=g_{\pi(t-1)}. Since aπ​(t−2)=bπ​(t−2)a_{\pi(t-2)}=b_{\pi(t-2)} and aπ​(t−1)=bπ​(t−1)a_{\pi(t-1)}=b_{\pi(t-1)}, from (48), we can obtain

ch,j−cg,i−ch′,j+cg′,i\displaystyle c_{h,j}-c_{g,i}-c_{h^{\prime},j}+c_{g^{\prime},i} ≡q2​(aπ​(t−2)−bπ​(t−2)+aπ​(t)−bπ​(t))\displaystyle\equiv\frac{q}{2}\left({a}_{\pi(t-2)}-b_{\pi(t-2)}+{a}_{\pi(t)}-{b}_{\pi(t)}\right) (53)
+pπ​(t−1)​(2​hπ​(t−1)−2​gπ​(t−1))\displaystyle+p_{\pi(t-1)}(2h_{\pi(t-1)}-2g_{\pi(t-1)})
≡q2​(aπ​(t)−bπ​(t))≡q2(modq)\displaystyle\equiv\frac{q}{2}\left({a}_{\pi(t)}-{b}_{\pi(t)}\right)\equiv\frac{q}{2}\pmod{q}

implying ξch,j−cg,i+ξch′,j−cg′,i=0.\xi^{c_{h,j}-c_{g,i}}+\xi^{c_{h^{\prime},j}-c_{g^{\prime},i}}=0. Similarly, we can also obtain ξdh,j−dg,i+ξdh′,j−dg′,i=0.\xi^{d_{h,j}-d_{g,i}}+\xi^{d_{h^{\prime},j}-d_{g^{\prime},i}}=0. If n<π​(t−1)≤n+mn<\pi(t-1)\leq n+m, note that aπ​(t−1)′=iπ​(t−1)−n′a^{\prime}_{\pi(t-1)}=i^{\prime}_{\pi(t-1)-n} and aπ​(t−1)=iπ​(t−1)−na_{\pi(t-1)}=i_{\pi(t-1)-n} according to (48). By following the similar argument as mentioned above, we can get

ξch,j−cg,i+ξch,j′−cg,i′+ξdh,j−dg,i+ξdh,j′−dg,i′=0.\xi^{{c}_{h,j}-{c}_{g,i}}+\xi^{{c}_{h,j^{\prime}}-{c}_{g,i^{\prime}}}+\xi^{{d}_{h,j}-{d}_{g,i}}+\xi^{{d}_{h,j^{\prime}}-{d}_{g,i^{\prime}}}=0. (54)

From Case 1 and Case 2, we can say that the array pair (𝑪,𝑫)({\mbox{\boldmath$C$}},{\mbox{\boldmath$D$}}) is indeed a 2-D GCAP. ∎

Remark 1

By setting {π​(1),π​(2),⋯,π​(n)}={1,2,⋯,n}\{\pi(1),\pi(2),\cdots,\pi(n)\}=\{1,2,\cdots,n\} and {π​(n+1),π​(n+2),⋯,π​(n+m)}={n+1,n+2,⋯,n+m}\{\pi(n+1),\pi(n+2),\cdots,\pi(n+m)\}=\{n+1,n+2,\cdots,n+m\} in Theorem 12, (44) can be rewritten as

f=\displaystyle f= q2​(∑l=1n−1yπ​(l)​yπ​(l+1)+∑l=n+1n+m−1xπ​(l)−n​xπ​(l+1)−n+yπ​(n)​xπ​(n+1)−n)\displaystyle\frac{q}{2}\left(\sum_{l=1}^{n-1}y_{\pi(l)}y_{\pi(l+1)}+\sum_{l=n+1}^{n+m-1}x_{\pi(l)-n}x_{\pi(l+1)-n+y_{\pi(n)}x_{\pi(n+1)-n}}\right) (55)
+∑l=1npl​yl+∑l=n+1n+mpl​xl−n+p0\displaystyle+\sum_{l=1}^{n}p_{l}y_{l}+\sum_{l=n+1}^{n+m}p_{l}x_{l-n}+p_{0}

according to (17). It can be observed that (55) is in the form of (24) and, therefore, Theorem 12 includes Theorem 9 as a special case.

Remark 2

When comparing (44) and (20), it can be found that Theorem 12 is a generalization of 1-D GDJ pairs to 2-D GCAPs by applying the proper mapping in (17). Theorem 12 provides an explicit expression of 2-D Boolean functions for 2-D GCAPs.

Like Corollaries 10 and 11, the PAPR properties for the constructed 2-D GCAPs from Theorem 12 are described in the following Corollaries.

Corollary 13

For a qq-ary array pair (𝐜,𝐝)(\mbox{\boldmath$c$},\mbox{\boldmath$d$}) from Theorem 12, we define an index set W={l|π​(l)>n,l=1,2,⋯,n+m}W=\{l|\pi(l)>n,~{}l=1,2,\cdots,n+m\}. If there exists an integer vv and nonempty sets W1,W2,⋯,WvW_{1},W_{2},\cdots,W_{v} satisfying the following conditions, then the row sequences of 𝐜​(or​𝐝)\mbox{\boldmath$c$}~{}(\text{or}~{}\mbox{\boldmath$d$}) have PAPRs at most 2v2^{v}.

  • (C1)

    {W1,W2,⋯,Wv}\{W_{1},W_{2},\cdots,W_{v}\} is a partition of the set WW;

  • (C2)

    the elements in each WαW_{\alpha} are consecutive integers for 1≤α≤v1\leq\alpha\leq v.

Proof:

We let 𝒄g{\mbox{\boldmath$c$}}_{g} be the gg-th row sequence of the array 𝒄c. For the ease of presentation, we consider the case for 𝒄0{\mbox{\boldmath$c$}}_{0} and the other cases can be obtained by following the similar argument. For simplicity, we let σα\sigma_{\alpha} be a bijection from {1,2,⋯,mα}\{1,2,\cdots,m_{\alpha}\} to the set {π​(l)−n|l∈Wα}\{\pi(l)-n|l\in W_{\alpha}\} with mα=|Wα|m_{\alpha}=|W_{\alpha}| and σα​(i)=π​(min⁡{Wα}+i−1)−n\sigma_{\alpha}(i)=\pi(\min\{W_{\alpha}\}+i-1)-n for α=1,2,⋯,v\alpha=1,2,\cdots,v and i=1,2,⋯,mαi=1,2,\cdots,m_{\alpha}. The sequence 𝒄0{\mbox{\boldmath$c$}}_{0} can be written as

𝒄0=q2​∑α=1v∑β=1mα−1𝒙σα​(β)​𝒙σα​(β+1)+∑l=1mpl​𝒙l+p0⋅𝟏,pl∈ℤq\displaystyle{\mbox{\boldmath$c$}}_{0}=\frac{q}{2}\sum_{\alpha=1}^{v}\sum_{\beta=1}^{m_{\alpha}-1}{\mbox{\boldmath$x$}}_{\sigma_{\alpha}(\beta)}{\mbox{\boldmath$x$}}_{\sigma_{\alpha}(\beta+1)}+\sum_{l=1}^{m}p_{l}{\mbox{\boldmath$x$}}_{l}+p_{0}\cdot{\mbox{\boldmath$1$}},~{}~{}~{}p_{l}\in\mathbb{Z}_{q} (56)

which lies in a GCS in (23). Therefore, from Lemma 8, we can conclude that the maximum row sequence PAPR of 𝒄c and 𝒅d is at most 2v2^{v}. ∎

Corollary 14

Let W′={l|1≤π​(l)≤n,l=1,2,⋯,n+m}W^{\prime}=\{l|1\leq\pi(l)\leq n,~{}l=1,2,\cdots,n+m\} and follow the similar conditions (C1) and (C2) in Corollary 13 with WW replaced by W′W^{\prime}. Then, the array 𝐜​(or​𝐝)\mbox{\boldmath$c$}~{}(\text{or}~{}\mbox{\boldmath$d$}) from Theorem 12 has column sequence PAPR upper bounded by 2v2^{v}.

Proof:

Similarly, we let σα\sigma_{\alpha} be a bijection from {1,2,⋯,nα}\{1,2,\cdots,n_{\alpha}\} to the set {π​(l)|l∈Wα′}\{\pi(l)|l\in W^{\prime}_{\alpha}\} with nα=|Wα′|n_{\alpha}=|W^{\prime}_{\alpha}| and σα​(l)=π​(min⁡{Wα′}+l−1)\sigma_{\alpha}(l)=\pi(\min\{W^{\prime}_{\alpha}\}+l-1) for α=1,2,⋯,v\alpha=1,2,\cdots,v and l=1,2,⋯,nαl=1,2,\cdots,n_{\alpha}. The column sequences can be represented as

q2​∑α=1v∑β=1nα−1𝒚σα​(β)​𝒚σα​(β+1)+∑l=1npl′​𝒚l+p0′⋅𝟏,pl′∈ℤq\frac{q}{2}\sum_{\alpha=1}^{v}\sum_{\beta=1}^{n_{\alpha}-1}{\mbox{\boldmath$y$}}_{\sigma_{\alpha}(\beta)}{\mbox{\boldmath$y$}}_{\sigma_{\alpha}(\beta+1)}+\sum_{l=1}^{n}p^{\prime}_{l}{\mbox{\boldmath$y$}}_{l}+p^{\prime}_{0}\cdot{\mbox{\boldmath$1$}},~{}~{}~{}p^{\prime}_{l}\in\mathbb{Z}_{q} (57)

implying that the maximum column sequence PAPR is bounded by 2v2^{v}. ∎

Corollary 15

The number of distinct 2n×2m2^{n}\times 2^{m} array 𝐜c obtained from Theorem 12 is

(n+m)!2⋅qn+m+1.\frac{(n+m)!}{2}\cdot q^{n+m+1}. (58)
Proof:

For a constructed array 𝒄c from Theorem 12, it can be expressed as

𝒄=q2​∑l=1n+m−1𝒛π​(l)​𝒛π​(l+1)+∑l=1n+mpl​𝒛l+p0⋅𝟏.{\mbox{\boldmath$c$}}=\frac{q}{2}\sum_{l=1}^{n+m-1}{\mbox{\boldmath$z$}}_{\pi(l)}{\mbox{\boldmath$z$}}_{\pi(l+1)}+\sum_{l=1}^{n+m}p_{l}{\mbox{\boldmath$z$}}_{l}+p_{0}\cdot{\mbox{\boldmath$1$}}. (59)

We first calculate the number of the quadratic forms

q2​∑l=1n+m−1𝒛π​(l)​𝒛π​(l+1).\frac{q}{2}\sum_{l=1}^{n+m-1}{\mbox{\boldmath$z$}}_{\pi(l)}{\mbox{\boldmath$z$}}_{\pi(l+1)}. (60)

Since π\pi is a permutation of the set {1,2,⋯,n+m}\{1,2,\cdots,n+m\}, there exist (n+m)!2\frac{(n+m)!}{2} distinct quadratic forms in (60). Then, we have pl∈ℤqp_{l}\in\mathbb{Z}_{q} for l=0,1,⋯,n+ml=0,1,\cdots,n+m and hence we can determine

(n+m)!2⋅qn+m+1\frac{(n+m)!}{2}\cdot q^{n+m+1} (61)

different arrays 𝒄c of size 2n×2m2^{n}\times 2^{m} of the form in (59). ∎

Example 3

Taking q=2,m=3q=2,~{}m=3, and n=2n=2, we let (π​(1),π​(2),π​(3),π​(4),π​(5))=(3,4,2,1,5)(\pi(1),\pi(2),\pi(3),\pi(4),\pi(5))=(3,4,2,1,5). Then, the generalized Boolean function is f=z3​z4+z4​z2+z2​z1+z1​z5f=z_{3}z_{4}+z_{4}z_{2}+z_{2}z_{1}+z_{1}z_{5} by setting pl=0p_{l}=0 for all ll in (44). Note that ff can also be expressed as f=x1​x2+x2​y2+y2​y1+y1​x3f=x_{1}x_{2}+x_{2}y_{2}+y_{2}y_{1}+y_{1}x_{3} according to (17). Then, the array pair (𝐜,𝐝)=(𝐟,𝐟+𝐳3)(\mbox{\boldmath$c$},\mbox{\boldmath$d$})=(\mbox{\boldmath$f$},\mbox{\boldmath$f$}+{\mbox{\boldmath$z$}}_{3}) is a GCAP from Theorem 12 where

𝒄=(00010001000111100010001011010010)​and​𝒅=(01000100010010110111011110000111).{\mbox{\boldmath$c$}}=\begin{pmatrix}0&0&0&1&0&0&0&1\\ 0&0&0&1&1&1&1&0\\ 0&0&1&0&0&0&1&0\\ 1&1&0&1&0&0&1&0\\ \end{pmatrix}~{}\text{and}~{}{\mbox{\boldmath$d$}}=\begin{pmatrix}0&1&0&0&0&1&0&0\\ 0&1&0&0&1&0&1&1\\ 0&1&1&1&0&1&1&1\\ 1&0&0&0&0&1&1&1\\ \end{pmatrix}.

For 𝐂=(ξcg,i)\mbox{\boldmath$C$}=(\xi^{c_{g,i}}) and 𝐃=(ξdg,i)​with​0≤g<L1,0≤i<L2\mbox{\boldmath$D$}=(\xi^{d_{g,i}})~{}\text{with}~{}0\leq g<L_{1},~{}0\leq i<L_{2}, the aperiodic autocorrelation values of 𝐂C and 𝐃D are given in (62) and (63).

(ρ​(𝑪;u1,u2))u1=−3∼3,u2=−7∼7\displaystyle(\rho(\mbox{\boldmath$C$};u_{1},u_{2}))_{u_{1}=-3\sim 3,u_{2}=-7\sim 7} (62)
=(101030−10−10−10−301202060−20202060−230−101010−3010−10−10000000320000000−10−1010−301010−103−20602020−206020210−30−10−10−1030101),\displaystyle=\left({\begin{array}[]{ccccccccccccccc}1&0&1&0&3&0&-1&0&-1&0&-1&0&-3&0&1\\ 2&0&2&0&6&0&-2&0&2&0&2&0&6&0&-2\\ 3&0&-1&0&1&0&1&0&-3&0&1&0&-1&0&-1\\ 0&0&0&0&0&0&0&32&0&0&0&0&0&0&0\\ -1&0&-1&0&1&0&-3&0&1&0&1&0&-1&0&3\\ -2&0&6&0&2&0&2&0&-2&0&6&0&2&0&2\\ 1&0&-3&0&-1&0&-1&0&-1&0&3&0&1&0&1\\ \end{array}}\right),
(ρ​(𝑫;u1,u2))u1=−3∼3,u2=−7∼7\displaystyle(\rho(\mbox{\boldmath$D$};u_{1},u_{2}))_{u_{1}=-3\sim 3,u_{2}=-7\sim 7} (63)
=(−10−10−3010101030−1−20−20−6020−20−20−602−3010−10−1030−1010100000003200000001010−1030−10−1010−320−60−20−2020−60−20−2−1030101010−30−10−1).\displaystyle=\left({\begin{array}[]{ccccccccccccccc}-1&0&-1&0&-3&0&1&0&1&0&1&0&3&0&-1\\ -2&0&-2&0&-6&0&2&0&-2&0&-2&0&-6&0&2\\ -3&0&1&0&-1&0&-1&0&3&0&-1&0&1&0&1\\ 0&0&0&0&0&0&0&32&0&0&0&0&0&0&0\\ 1&0&1&0&-1&0&3&0&-1&0&-1&0&1&0&-3\\ 2&0&-6&0&-2&0&-2&0&2&0&-6&0&-2&0&-2\\ -1&0&3&0&1&0&1&0&1&0&-3&0&-1&0&-1\\ \end{array}}\right).

We can see that their aperiodic autocorrelations sum to zero except for (u1,u2)=(0,0)(u_{1},u_{2})=(0,0). From Corollary 13, we have W={l|π​(l)>2}={1,2,5}W=\{l|\pi(l)>2\}=\{1,2,5\} and let W1={1,2},W2={5}W_{1}=\{1,2\},W_{2}=\{5\} be a partition of WW with v=2v=2 implying that the row sequence PAPRs of 𝐜c and 𝐝d are at most 2v=42^{v}=4. Actually, the maximum row sequence PAPR of 𝐜c and 𝐝d is 3.4427. Also, we let W′={l|1≤π​(l)≤2}={3,4}W^{\prime}=\{l|1\leq\pi(l)\leq 2\}=\{3,4\} which yields v=1v=1 and the column sequence PAPR is at most 2 according to Corollary 14. In fact, the column sequence PAPR of each column of 𝐜c and 𝐝d is 1.7698.

Next, a construction of Golay complementary array mates is provided based on Theorem 12.

Theorem 16

The array pair (𝐜′,𝐝′)({\mbox{\boldmath$c$}^{\prime}},{\mbox{\boldmath$d$}^{\prime}}) is a Golay complementary array mate of the GCAP (𝐜,𝐝)(\mbox{\boldmath$c$},\mbox{\boldmath$d$}) given in (45) where

(𝒄′,𝒅′)=(𝒇+q2​𝒛π​(n+m),𝒇+q2​𝒛π​(1)+q2​𝒛π​(n+m))({\mbox{\boldmath$c$}^{\prime}},{\mbox{\boldmath$d$}^{\prime}})=\left({\mbox{\boldmath$f$}}+\frac{q}{2}{\mbox{\boldmath$z$}}_{\pi(n+m)},{\mbox{\boldmath$f$}}+\frac{q}{2}{\mbox{\boldmath$z$}}_{\pi(1)}+\frac{q}{2}{\mbox{\boldmath$z$}}_{\pi(n+m)}\right) (64)

and 𝐟f is the associated array to the Boolean function ff in (44).

Proof:

For the 2-D GCAPs (𝑪,𝑫)=(ξ𝒄,ξ𝒅)(\mbox{\boldmath$C$},\mbox{\boldmath$D$})=(\xi^{\mbox{\boldmath$c$}},\xi^{\mbox{\boldmath$d$}}) and (𝑪′,𝑫′)=(ξ𝒄′,ξ𝒅′)({\mbox{\boldmath$C$}^{\prime}},{\mbox{\boldmath$D$}^{\prime}})=(\xi^{\mbox{\boldmath$c$}^{\prime}},\xi^{\mbox{\boldmath$d$}^{\prime}}) of size 2n×2m2^{n}\times 2^{m}, we would like to show that

ρ​(𝑪,𝑪′;u1,u2)+ρ​(𝑫,𝑫′;u1,u2)=∑g=02n−1∑i=02m−1(ξcg+u1,i+u2′−cg,i+ξdg+u1,i+u2′−dg,i)=0\displaystyle\rho({\mbox{\boldmath$C$}},{\mbox{\boldmath$C$}^{\prime}};u_{1},u_{2})+\rho({\mbox{\boldmath$D$}},{\mbox{\boldmath$D$}^{\prime}};u_{1},u_{2})=\sum\limits_{g=0}^{2^{n}-1}\sum\limits_{i=0}^{2^{m}-1}\left(\xi^{c^{\prime}_{g+u_{1},{i+u_{2}}}-c_{g,i}}+\xi^{d^{\prime}_{g+u_{1},{i+u_{2}}}-d_{g,i}}\right)=0 (65)

for −2n<u1<2n-2^{n}<u_{1}<2^{n} and −2m<u2<2m-2^{m}<u_{2}<2^{m}. It is noted that 𝑪=ξ𝒄{\mbox{\boldmath$C$}}={\xi^{\mbox{\boldmath$c$}}} where 𝒄c can be obtained from (47). We follow the same notations given in (48) in the proof of Theorem 12 and consider three cases below.

Case 1: Assume aπ​(1)≠bπ​(1)a_{\pi(1)}\neq b_{\pi(1)}. Following a similar derivation in Case 1 in the proof of Theorem 12, we can have

ξcg+u1,i+u2′−cg,i+ξdg+u1,i+u2′−dg,i=0.\xi^{c^{\prime}_{g+u_{1},{i+u_{2}}}-c_{g,i}}+\xi^{d^{\prime}_{g+u_{1},{i+u_{2}}}-d_{g,i}}=0. (66)

Case 2: We assume aπ​(1)=bπ​(1)a_{\pi(1)}=b_{\pi(1)} and let tt be the smallest integer with aπ​(t)≠bπ​(t)a_{\pi(t)}\neq b_{\pi(t)}. The similar results can be obtained as provided in Case 2 in the proof of Theorem 12. When 1≤π​(t−1)≤n1\leq\pi(t-1)\leq n, we have

ξch,j′−cg,i+ξch′,j′−cg′,i+ξdh,j′−dg,i+ξdh′,j′−dg′,i=0,\xi^{c^{\prime}_{h,j}-c_{g,i}}+\xi^{c^{\prime}_{h^{\prime},j}-c_{g^{\prime},i}}+\xi^{d^{\prime}_{h,j}-d_{g,i}}+\xi^{d^{\prime}_{h^{\prime},j}-d_{g^{\prime},i}}=0, (67)

and when n<π​(t−1)≤n+mn<\pi(t-1)\leq n+m, we also have

ξch,j′−cg,i+ξch,j′′−cg,i′+ξdh,j′−dg,i+ξdh,j′′−dg,i′=0.\xi^{c^{\prime}_{h,j}-c_{g,i}}+\xi^{c^{\prime}_{h,j^{\prime}}-c_{g,i^{\prime}}}+\xi^{d^{\prime}_{h,j}-d_{g,i}}+\xi^{d^{\prime}_{h,j^{\prime}}-d_{g,i^{\prime}}}=0. (68)

Case 3: Lastly, it only suffices to show that

ρ​(𝑪,𝑪′;0,0)+ρ​(𝑫,𝑫′;0,0)=0.\rho({\mbox{\boldmath$C$}},{\mbox{\boldmath$C$}^{\prime}};0,0)+\rho({\mbox{\boldmath$D$}},{\mbox{\boldmath$D$}^{\prime}};0,0)=0. (69)

For 1≤π​(n+m)≤n1\leq\pi(n+m)\leq n, we have

∑g=02n−1(ξcg,i′−cg,i+ξdg,i′−dg,i)=2​∑g=02n−1ξq2​gπ​(n+m)=0\displaystyle\sum\limits_{g=0}^{2^{n}-1}\left(\xi^{c^{\prime}_{g,i}-c_{g,i}}+\xi^{d^{\prime}_{g,i}-d_{g,i}}\right)=2\sum\limits_{g=0}^{2^{n}-1}\xi^{\frac{q}{2}g_{\pi(n+m)}}=0 (70)

where gπ​(n+m)g_{\pi(n+m)} is the π​(n+m)\pi(n+m)-th bit of the binary representation vector (g1,g2,⋯,gn)(g_{1},g_{2},\cdots,g_{n}) of gg. For n<π​(n+m)≤m+nn<\pi(n+m)\leq m+n, we can also obtain

∑i=02m−1(ξcg,i′−cg,i+ξdg,i′−dg,i)=2​∑i=02m−1ξq2​iπ​(n+m)−n=0\sum\limits_{i=0}^{2^{m}-1}\left(\xi^{c^{\prime}_{g,i}-c_{g,i}}+\xi^{d^{\prime}_{g,i}-d_{g,i}}\right)=2\sum\limits_{i=0}^{2^{m}-1}\xi^{\frac{q}{2}i_{\pi(n+m)-n}}=0 (71)

where iπ​(n+m)−ni_{\pi(n+m)-n} is the (π​(n+m)−n)(\pi(n+m)-n)-th bit of the binary representation vector of ii.

Combining Case 1 to Case 3, we complete the proof. ∎

Remark 3

Theorem 16 includes the results in [40, Th.7] by letting {π​(l),π​(2),⋯,π​(n)}={1,2,⋯,n}\{\pi(l),\pi(2),\cdots,\pi(n)\}=\{1,2,\cdots,n\} and {π​(n+1),π​(n+2),⋯,π​(n+m)}={n+1,n+2,⋯,n+m}\{\pi(n+1),\pi(n+2),\cdots,\pi(n+m)\}=\{n+1,n+2,\cdots,n+m\}. Therefore, [40, Th. 7] is a special case of Theorem 16.

Example 4

Let us follow the same notations given in Example 3. Based on Theorem 16, we have an array pair (𝐜′,𝐝′)=(𝐟+𝐳5,𝐟+𝐳3+𝐳5)(\mbox{\boldmath$c$}^{\prime},\mbox{\boldmath$d$}^{\prime})=({\mbox{\boldmath$f$}}+{\mbox{\boldmath$z$}}_{5},{\mbox{\boldmath$f$}}+{\mbox{\boldmath$z$}}_{3}+{\mbox{\boldmath$z$}}_{5}) given by

𝒄′=(00011110000100010010110111011101)​and​𝒅′=(01001011010001000111100010001000).{\mbox{\boldmath$c$}^{\prime}}=\begin{pmatrix}0&0&0&1&1&1&1&0\\ 0&0&0&1&0&0&0&1\\ 0&0&1&0&1&1&0&1\\ 1&1&0&1&1&1&0&1\\ \end{pmatrix}~{}\text{and}~{}{\mbox{\boldmath$d$}^{\prime}}=\begin{pmatrix}0&1&0&0&1&0&1&1\\ 0&1&0&0&0&1&0&0\\ 0&1&1&1&1&0&0&0\\ 1&0&0&0&1&0&0&0\\ \end{pmatrix}.

Let 𝐂′=(ξcg,i′)​and​𝐃′=(ξdg,i′)​with​0≤g<4​and​0≤i<8\mbox{\boldmath$C$}^{\prime}=(\xi^{c_{g,i}^{\prime}})~{}\text{and}~{}\mbox{\boldmath$D$}^{\prime}=(\xi^{d_{g,i}^{\prime}})~{}\text{with}~{}0\leq g<4~{}\text{and}~{}0\leq i<8. Then, we list the aperiodic cross-correlations of (𝐂,𝐂′)(\mbox{\boldmath$C$},\mbox{\boldmath$C$}^{\prime}) and (𝐃,𝐃′)(\mbox{\boldmath$D$},\mbox{\boldmath$D$}^{\prime}) in (72) and (73). By observing the sum of the cross-correlations, (𝐂,𝐃)(\mbox{\boldmath$C$},{\mbox{\boldmath$D$}}) and (𝐂′,𝐃′)({\mbox{\boldmath$C$}^{\prime}},{\mbox{\boldmath$D$}^{\prime}}) are indeed Golay complementary array mates of each other.

(ρ​(𝑪,𝑪′;u1,u2))u1=−3∼3,u2=−7∼7\displaystyle(\rho(\mbox{\boldmath$C$},{\mbox{\boldmath$C$}^{\prime}};u_{1},u_{2}))_{u_{1}=-3\sim 3,u_{2}=-7\sim 7} (72)
=(−10−10−50−10−7010−301−20−20−6020202060−2−3010−305070−50−10−100000000000000010−10−7013070−10−10320−60−20−20−2060202−103030−50−3010101),\displaystyle=\left({\begin{array}[]{ccccccccccccccc}-1&0&-1&0&-5&0&-1&0&-7&0&1&0&-3&0&1\\ -2&0&-2&0&-6&0&2&0&2&0&2&0&6&0&-2\\ -3&0&1&0&-3&0&5&0&7&0&-5&0&-1&0&-1\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 1&0&-1&0&-7&0&13&0&7&0&-1&0&-1&0&3\\ 2&0&-6&0&-2&0&-2&0&-2&0&6&0&2&0&2\\ -1&0&3&0&3&0&-5&0&-3&0&1&0&1&0&1\\ \end{array}}\right),
(ρ​(𝑫,𝑫′;u1,u2))u1=−3∼3,u2=−7∼7\displaystyle(\rho(\mbox{\boldmath$D$},{\mbox{\boldmath$D$}^{\prime}};u_{1},u_{2}))_{u_{1}=-3\sim 3,u_{2}=-7\sim 7} (73)
=(1010501070−1030−1202060−20−20−20−60230−1030−50−7050101000000000000000−101070−130−701010−3−2060202020−60−20−210−30−305030−10−10−1).\displaystyle=\left({\begin{array}[]{ccccccccccccccc}1&0&1&0&5&0&1&0&7&0&-1&0&3&0&-1\\ 2&0&2&0&6&0&-2&0&-2&0&-2&0&-6&0&2\\ 3&0&-1&0&3&0&-5&0&-7&0&5&0&1&0&1\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ -1&0&1&0&7&0&-13&0&-7&0&1&0&1&0&-3\\ -2&0&6&0&2&0&2&0&2&0&-6&0&-2&0&-2\\ 1&0&-3&0&-3&0&5&0&3&0&-1&0&-1&0&-1\\ \end{array}}\right).

III-B GCASs Based on Generalized Boolean Functions

In this subsection, we extend Theorem 12 to propose a construction of (N,L1,L2)(N,L_{1},L_{2})-GCAS with various set size N≥2N\geq 2.

Theorem 17

Considering nonnegative integers n,m,kn,m,k with n+m≥2n+m\geq 2 and k≤n+mk\leq n+m, we let nonempty sets I1,I2,⋯,IkI_{1},I_{2},\cdots,I_{k} be a partition of {1,2,⋯,n+m}\{1,2,\cdots,n+m\}. Let tαt_{\alpha} be the order of IαI_{\alpha} and πα\pi_{\alpha} be a bijection from {1,2,⋯,tα}\{1,2,\cdots,t_{\alpha}\} to IαI_{\alpha} for α=1,2,⋯,k\alpha=1,2,\cdots,k. If the generalized Boolean function is given by

f=q2​∑α=1k∑β=1tα−1zπα​(β)​zπα​(β+1)+∑l=1n+mpl​zl+p0\displaystyle f=\frac{q}{2}\sum_{\alpha=1}^{k}\sum_{\beta=1}^{t_{\alpha}-1}z_{\pi_{\alpha}(\beta)}z_{\pi_{\alpha}(\beta+1)}+\sum_{l=1}^{n+m}p_{l}z_{l}+p_{0} (74)

where pl​’s∈ℤqp_{l}\text{'s}\in\mathbb{Z}_{q}, then the array set

G={𝒇+q2​∑α=1kλα​𝒛πα​(1):λα∈{0,1}}\displaystyle G=\left\{{\mbox{\boldmath$f$}}+\frac{q}{2}\sum_{\alpha=1}^{k}\lambda_{\alpha}{\mbox{\boldmath$z$}}_{\pi_{\alpha}(1)}:\lambda_{\alpha}\in\{0,1\}\right\} (75)

forms a qq-ary (2k,2n,2m)(2^{k},2^{n},2^{m})-GCAS.

Proof:

For any array 𝒄∈G\mbox{\boldmath$c$}\in G, we need to demonstrate that

∑𝐜∈G∑g=02n−1∑i=02m−1(ξcg+u1,i+u2−cg,i)\displaystyle\sum_{{\bf c}\in G}\sum\limits_{g=0}^{2^{n}-1}\sum\limits_{i=0}^{2^{m}-1}\left(\xi^{c_{g+u_{1},{i+u_{2}}}-c_{g,i}}\right) =∑g=02n−1∑i=02m−1∑𝐜∈G(ξcg+u1,i+u2−cg,i)\displaystyle=\sum\limits_{g=0}^{2^{n}-1}\sum\limits_{i=0}^{2^{m}-1}\sum_{{\bf c}\in G}\left(\xi^{c_{g+u_{1},{i+u_{2}}}-c_{g,i}}\right) (76)
=0\displaystyle=0

for (u1,u2)≠(0,0)(u_{1},u_{2})\neq(0,0). Here, we let h=g+u1,j=i+u2h=g+u_{1},~{}j=i+u_{2} and also let (g1,g2,⋯,gn),(h1,h2,⋯,hn),(g_{1},g_{2},\cdots,g_{n}),~{}(h_{1},h_{2},\cdots,h_{n}), (i1,i2,⋯,im)(i_{1},i_{2},\cdots,i_{m}), and (j1,j2,⋯,jm)(j_{1},j_{2},\cdots,j_{m}) be the binary representation vectors of g,h,ig,~{}h,~{}i, and jj, respectively. By combining the binary representations of g,h,ig,~{}h,~{}i, and jj as follows:

al={glfor​1≤l≤n;il−nfor​n<l≤m+n,\displaystyle a_{l}=\begin{cases}g_{l}&\text{for}~{}1\leq l\leq n;\\ i_{l-n}&\text{for}~{}n<l\leq m+n,\end{cases} (77)
bl={hlfor​1≤l≤n;jl−nfor​n<l≤m+n,\displaystyle b_{l}=\begin{cases}h_{l}&\text{for}~{}1\leq l\leq n;\\ j_{l-n}&\text{for}~{}n<l\leq m+n,\end{cases}

the proof of (76) will be concise and two cases are taken into account.

Case 1: If aπα​(1)≠bπα​(1)a_{\pi_{\alpha}(1)}\neq b_{\pi_{\alpha}(1)} for some α∈{1,2,⋯,k}\alpha\in\{1,2,\cdots,k\}, then for any array 𝒄∈G\mbox{\boldmath$c$}\in G, we can find an array 𝒄′=𝒄+(q/2)​𝒛πα​(1)∈G{\mbox{\boldmath$c$}}^{\prime}={\mbox{\boldmath$c$}}+(q/2){\mbox{\boldmath$z$}}_{\pi_{\alpha}(1)}\in G satisfying

ch,j−cg,i−ch,j′+cg,i′=q2​(aπα​(1)−bπα​(1))≡q2(modq).c_{h,j}-c_{g,i}-c^{\prime}_{h,j}+c^{\prime}_{g,i}=\frac{q}{2}(a_{\pi_{\alpha}(1)}-b_{\pi_{\alpha}(1)})\equiv\frac{q}{2}\pmod{q}. (78)

Therefore, we have

∑𝐜∈Gξch,j−cg,i=0.\sum_{{\bf c}\in G}\xi^{c_{h,j}-c_{g,i}}=0. (79)

Case 2: Suppose that aπα​(1)=bπα​(1)a_{\pi_{\alpha}(1)}=b_{\pi_{\alpha}(1)} for all α=1,2,⋯,k\alpha=1,2,\cdots,k. We assume aπα​(β)=bπα​(β)a_{\pi_{\alpha}(\beta)}=b_{\pi_{\alpha}(\beta)} for α=1,⋯,α^−1\alpha=1,\cdots,\hat{\alpha}-1 and β=1,2,⋯,mα\beta=1,2,\cdots,m_{\alpha}. Besides, we assume that β^\hat{\beta} is the smallest number satisfying aπα^​(β^−1)≠bπα^​(β^−1)a_{\pi_{\hat{\alpha}}(\hat{\beta}-1)}\neq b_{\pi_{\hat{\alpha}}(\hat{\beta}-1)}. Let aπα^​(β^−1)′=1−aπα^​(β^−1)a^{\prime}_{\pi_{\hat{\alpha}}(\hat{\beta}-1)}=1-a_{\pi_{\hat{\alpha}}(\hat{\beta}-1)} and bπα^​(β^−1)′=1−bπα^​(β^−1)b^{\prime}_{\pi_{\hat{\alpha}}(\hat{\beta}-1)}=1-b_{\pi_{\hat{\alpha}}(\hat{\beta}-1)}. Following the similar argument as mentioned in Case 2 in the proof of Theorem 12, we have

∑𝐜∈Gξch,j−cg,i+ξch′,j−cg′,i=0,\sum_{{\bf c}\in G}\xi^{c_{h,j}-c_{g,i}}+\xi^{c_{h^{\prime},j}-c_{g^{\prime},i}}=0, (80)

for 1≤πα^​(β^−1)≤n1\leq\pi_{\hat{\alpha}}(\hat{\beta}-1)\leq n and

∑𝐜∈Gξch,j−cg,i+ξch,j′−cg,i′=0.\sum_{{\bf c}\in G}\xi^{c_{h,j}-c_{g,i}}+\xi^{c_{h,j^{\prime}}-c_{g,i^{\prime}}}=0. (81)

for n<πα^​(β^−1)≤n+mn<\pi_{\hat{\alpha}}(\hat{\beta}-1)\leq n+m.

According to the above two cases, the equality in (76) holds. ∎

Example 5

Let us take q=2,n=2,q=2,~{}n=2, and m=3m=3 for example. According to Theorem 17, we let I1={4,2,5},I2={1,3},π1​(1)=4,π1​(2)=2,π1​(3)=5,π2​(1)=1,π2​(2)=3I_{1}=\{4,2,5\},~{}I_{2}=\{1,3\},~{}\pi_{1}(1)=4,~{}\pi_{1}(2)=2,~{}\pi_{1}(3)=5,\pi_{2}(1)=1,~{}\pi_{2}(2)=3, and the Boolean function f=z4​z2+z2​z5+z1​z3f=z_{4}z_{2}+z_{2}z_{5}+z_{1}z_{3}, which can be represented by f=x2​y2+y2​x3+y1​x1f=x_{2}y_{2}+y_{2}x_{3}+y_{1}x_{1} according to (17). The set G={𝐟,𝐟+𝐳4,𝐟+𝐳1,𝐟+𝐳4+𝐳1}G=\{\mbox{\boldmath$f$},\mbox{\boldmath$f$}+{\mbox{\boldmath$z$}}_{4},\mbox{\boldmath$f$}+{\mbox{\boldmath$z$}}_{1},{\mbox{\boldmath$f$}}+{\mbox{\boldmath$z$}}_{4}+{\mbox{\boldmath$z$}}_{1}\} forms a qq-ary (4,4,8)(4,4,8)-GCAS where

𝒇=(00000000010101010011110001101001),𝒇+𝒛4=(00110011011001100000111101011010),{\mbox{\boldmath$f$}}=\begin{pmatrix}0&0&0&0&0&0&0&0\\ 0&1&0&1&0&1&0&1\\ 0&0&1&1&1&1&0&0\\ 0&1&1&0&1&0&0&1\\ \end{pmatrix},~{}{\mbox{\boldmath$f$}+{\mbox{\boldmath$z$}}_{4}}=\begin{pmatrix}0&0&1&1&0&0&1&1\\ 0&1&1&0&0&1&1&0\\ 0&0&0&0&1&1&1&1\\ 0&1&0&1&1&0&1&0\\ \end{pmatrix},
𝒇+𝒛1=(00000000101010100011110010010110),𝒇+𝒛4+𝒛1=(00110011100110010000111110100101).{\mbox{\boldmath$f$}+{\mbox{\boldmath$z$}}_{1}}=\begin{pmatrix}0&0&0&0&0&0&0&0\\ 1&0&1&0&1&0&1&0\\ 0&0&1&1&1&1&0&0\\ 1&0&0&1&0&1&1&0\\ \end{pmatrix},~{}{\mbox{\boldmath$f$}+{\mbox{\boldmath$z$}}_{4}+{\mbox{\boldmath$z$}}_{1}}=\begin{pmatrix}0&0&1&1&0&0&1&1\\ 1&0&0&1&1&0&0&1\\ 0&0&0&0&1&1&1&1\\ 1&0&1&0&0&1&0&1\\ \end{pmatrix}.

According to the mapping in (17), we have z1=x1,z2=x2,z3=y1,z4=y2z_{1}=x_{1},~{}z_{2}=x_{2},~{}z_{3}=y_{1},~{}z_{4}=y_{2}, and z5=y3z_{5}=y_{3}. Therefore, we have 𝐅1=ξ𝐟=(ξfg,i),𝐅2=ξ𝐟+𝐳4=(ξfg,i+i2),𝐅3=ξ𝐟+𝐳1=(ξfg,i+g1),and​𝐅4=ξ𝐟+𝐳4+𝐳1=(ξfg,i+i2+g1){\mbox{\boldmath$F$}}_{1}=\xi^{\mbox{\footnotesize\boldmath$f$}}=(\xi^{f_{g,i}}),~{}{\mbox{\boldmath$F$}}_{2}=\xi^{\mbox{\footnotesize\boldmath$f$}+{\mbox{\footnotesize\boldmath$z$}_{4}}}=(\xi^{f_{g,i}+i_{2}}),~{}{\mbox{\boldmath$F$}}_{3}=\xi^{\mbox{\footnotesize\boldmath$f$}+{\mbox{\footnotesize\boldmath$z$}_{1}}}=(\xi^{f_{g,i}+g_{1}}),~{}\text{and}~{}{\mbox{\boldmath$F$}}_{4}=\xi^{\mbox{\footnotesize\boldmath$f$}+{\mbox{\footnotesize\boldmath$z$}_{4}}+{\mbox{\footnotesize\boldmath$z$}_{1}}}=(\xi^{f_{g,i}+i_{2}+g_{1}}), where 0≤g<4,0≤i<80\leq g<4,~{}0\leq i<8 and g=∑s=12gs​2s−1,i=∑l=13il​2l−1g=\sum_{s=1}^{2}g_{s}2^{s-1},~{}i=\sum_{l=1}^{3}i_{l}2^{l-1}. Their aperiodic autocorrelations are given, respectively, in (82) to (85). We can observe that the sums of their autocorrelations are all zero for (u1,u2)≠(0,0)(u_{1},u_{2})\neq(0,0).

(ρ​(𝑭1;u1,u2))u1=−3∼3,u2=−7∼7\displaystyle(\rho(\mbox{\boldmath$F$}_{1};u_{1},u_{2}))_{u_{1}=-3\sim 3,u_{2}=-7\sim 7} (82)
=(−101010−1010−10−10104000−4000−400040−1010−30−505030−101080008032080008010−103050−50−3010−104000−4000−40004010−10−1010−101010−1),\displaystyle=\left({\begin{array}[]{ccccccccccccccc}-1&0&1&0&1&0&-1&0&1&0&-1&0&-1&0&1\\ 0&4&0&0&0&-4&0&0&0&-4&0&0&0&4&0\\ -1&0&1&0&-3&0&-5&0&5&0&3&0&-1&0&1\\ 0&8&0&0&0&8&0&32&0&8&0&0&0&8&0\\ 1&0&-1&0&3&0&5&0&-5&0&-3&0&1&0&-1\\ 0&4&0&0&0&-4&0&0&0&-4&0&0&0&4&0\\ 1&0&-1&0&-1&0&1&0&-1&0&1&0&1&0&-1\end{array}}\right),
(ρ​(𝑭2;u1,u2))u1=−3∼3,u2=−7∼7\displaystyle(\rho(\mbox{\boldmath$F$}_{2};u_{1},u_{2}))_{u_{1}=-3\sim 3,u_{2}=-7\sim 7} (83)
=(10−10−1010−101010−10−400040004000−4010−1030−110110−3010−10−8000−80320−8000−80−1010−30110−11030−1010−400040004000−40−101010−1010−10−101),\displaystyle=\left({\begin{array}[]{ccccccccccccccc}1&0&-1&0&-1&0&1&0&-1&0&1&0&1&0&-1\\ 0&-4&0&0&0&4&0&0&0&4&0&0&0&-4&0\\ 1&0&-1&0&3&0&-11&0&11&0&-3&0&1&0&-1\\ 0&-8&0&0&0&-8&0&32&0&-8&0&0&0&-8&0\\ -1&0&1&0&-3&0&11&0&-11&0&3&0&-1&0&1\\ 0&-4&0&0&0&4&0&0&0&4&0&0&0&-4&0\\ -1&0&1&0&1&0&-1&0&1&0&-1&0&-1&0&1\end{array}}\right),
(ρ​(𝑭3;u1,u2))u1=−3∼3,u2=−7∼7\displaystyle(\rho(\mbox{\boldmath$F$}_{3};u_{1},u_{2}))_{u_{1}=-3\sim 3,u_{2}=-7\sim 7} (84)
=(10−10−1010−101010−104000−4000−40004010−103050−50−3010−10800080320800080−1010−30−505030−10104000−4000−400040−101010−1010−10−101),\displaystyle=\left({\begin{array}[]{ccccccccccccccc}1&0&-1&0&-1&0&1&0&-1&0&1&0&1&0&-1\\ 0&4&0&0&0&-4&0&0&0&-4&0&0&0&4&0\\ 1&0&-1&0&3&0&5&0&-5&0&-3&0&1&0&-1\\ 0&8&0&0&0&8&0&32&0&8&0&0&0&8&0\\ -1&0&1&0&-3&0&-5&0&5&0&3&0&-1&0&1\\ 0&4&0&0&0&-4&0&0&0&-4&0&0&0&4&0\\ -1&0&1&0&1&0&-1&0&1&0&-1&0&-1&0&1\end{array}}\right),
(ρ​(𝑭4;u1,u2))u1=−3∼3,u2=−7∼7\displaystyle(\rho(\mbox{\boldmath$F$}_{4};u_{1},u_{2}))_{u_{1}=-3\sim 3,u_{2}=-7\sim 7} (85)
=(−101010−1010−10−1010−400040004000−40−1010−30110−11030−1010−8000−80320−8000−8010−1030−110110−3010−10−400040004000−4010−10−1010−101010−1).\displaystyle=\left({\begin{array}[]{ccccccccccccccc}-1&0&1&0&1&0&-1&0&1&0&-1&0&-1&0&1\\ 0&-4&0&0&0&4&0&0&0&4&0&0&0&-4&0\\ -1&0&1&0&-3&0&11&0&-11&0&3&0&-1&0&1\\ 0&-8&0&0&0&-8&0&32&0&-8&0&0&0&-8&0\\ 1&0&-1&0&3&0&-11&0&11&0&-3&0&1&0&-1\\ 0&-4&0&0&0&4&0&0&0&4&0&0&0&-4&0\\ 1&0&-1&0&-1&0&1&0&-1&0&1&0&1&0&-1\end{array}}\right).

Compared to [14], Theorem 17 constructs aperiodic GCASs and does not require any perfect array as a kernel. 2-D GCASs can be generated directly from generalized Boolean functions.

IV Conclusion

In this paper, novel constructions of 2-D GCAPs, 2-D GCASs, and 2-D Golay complementary array mates based on 2-D generalized Boolean functions have been proposed. First, we give the basic construction of 2-D GCAPs of size 2n×2m2^{n}\times 2^{m} from Boolean functions in Theorem 9. Then, we propose extended constructions of 2-D GCAPs and 2-D Golay complementary array mates, respectively, in Theorem 12 and Theorem 16, which can include the results in [40, Th.6] and [40, Th.7] as special cases. By adopting the proper mapping given in (17), Theorem 12 presents an elegant and explicit expression for 2-D GCAPs in terms of 2-D Boolean functions. In addition, the upper bounds on row sequence PAPR and column sequence PAPR of the proposed 2-D GCAPs are derived in Corollary 13 and Corollary 14. Moreover, we further propose (2k,2n,2m)(2^{k},2^{n},2^{m})-GCASs based on generalized Boolean functions from Theorem 17. This is, to the authors’ knowledge, the first construction method of 2-D GCASs based on Boolean functions. The proposed constructions are all direct constructions without using other existing 1-D sequences or 2-D arrays as kernels.

Although Theorem 17 can provide a direct construction of 2-D GCASs, the array sizes of each constituent array are limited to 2n×2m2^{n}\times 2^{m}. Therefore, possible future research is to investigate the construction of 2-D GCASs with various array sizes. Besides, an extension to 2-D CCCs and 2-D Z-Complementary array pairs/sets [42, 43, 44] based on generalized Boolean functions is also an interesting topic.

References

  • [1] M. J. E. Golay, “Complementary series,” IRE Trans. Inf. Theory, vol. IT-7, pp. 82–87, Apr. 1961.
  • [2] C.-C. Tseng and C. L. Liu, “Complementary sets of sequences,” IEEE Trans. Inf. Theory, vol. IT-18, pp. 644–652, Sep. 1972.
  • [3] P. Spasojevic and C. N. Georghiades, “Complementary sequences for ISI channel estimation,” IEEE Trans. Inf. Theory, vol. 47, no. 3, pp. 1145–1152, Mar. 2001.
  • [4] J. M. Groenewald and B. T. Maharaj, “MIMO channel synchronization using Golay complementary pairs,” in Proc. AFRICON 2007, Windhoek, South Africa, Sep. 2007, pp. 1–5.
  • [5] H.-H. Chen, J.-F. Yeh, and N. Suehiro, “A multicarrier CDMA architecture based on orthogonal complete complementary codes for new generations of wideband wireless communications,” IEEE Commun. Mag., vol. 39, pp. 126–134, Oct. 2001.
  • [6] S. Boyd, “Multitone signals with low crest factor,” IEEE Trans. Circuits Syst., vol. CAS-33, no. 10, pp. 1018–1022, Oct. 1986.
  • [7] R. van Nee, “OFDM codes for peak-to-average power reduction and error correction,” in Proc. IEEE Global Telecommun. Conf., London, U.K., Nov. 1996, pp. 740–744.
  • [8] J. A. Davis and J. Jedwab, “Peak-to-mean power control in OFDM, Golay complementary sequences, and Reed-Muller codes,” IEEE Trans. Inf. Theory, vol. 45, no. 7, pp. 2397–2417, Nov. 1999.
  • [9] K. G. Paterson, “Generalized Reed-Muller codes and power control in OFDM modulation,” IEEE Trans. Inf. Theory, vol. 46, no. 1, pp. 104–120, Jan. 2000.
  • [10] M. Dymond, “Barker arrays: existence, generalization and alternatives,” Ph.D. thesis, University of London, 1992.
  • [11] S. Matsufuji, R. Shigemitsu, Y. Tanada, and N. Kuroyanagi, “Construction of complementary arrays,” in Proc. Joint IST Workshop on Mobile Future and Symp. on Trends in Commun., Bratislava, Slovakia, Oct. 2004, pp. 78–81.
  • [12] J. Jedwab and M. G. Parker, “Golay complementary array pairs,” Designs, Codes and Cryptography, vol. 44, no. 1-3, p. 209–216, Sep. 2007.
  • [13] F. Fiedler, J. Jedwab, and M. G. Parker, “A multi-dimensional approach for the construction and enumeration of Golay complementary sequences,” J. Combinatorial Theory (Series A), vol. 115, no. 5, pp. 753–776, Jul. 2008.
  • [14] F. Zeng and Z. Zhang, “Two dimensional periodic complementary array sets,” in Proc. IEEE Int. Conf. on Wireless Commun., Netw. and Mobile Comput., Chengdu, China, Sep. 2010, pp. 1–4.
  • [15] Y. Jiang, F. Li, X. Wang, and J. Li, “Autocorrelation complementary matrices,” in Proc. 53rd Asilomar Conf. on Signals, Systems, and Computers, Pacific Grove, CA, Nov. 2019, pp. 1–5.
  • [16] G. Weathers and E. M. Holliday, “Group-complementary array coding for radar clutter rejection,” IEEE Trans. Aerospace and Electronic Systems, vol. AES-19, no. 3, pp. 369–379, May 1983.
  • [17] S. W. Golomb and H. Taylor, “Two-dimensional synchronization patterns for minimum ambiguity,” IEEE Trans. Inf. Theory, vol. 28, no. 4, pp. 600–604, Jul. 1982.
  • [18] J. E. Hershey and R. Yarlagadda, “Two-dimensional synchronisation,” Electronics Letters, vol. 19, no. 19, pp. 801 – 803, Sep. 1983.
  • [19] M. Turcsány and P. Farkaš, “New 2D-MC-DS-SS-CDMA techniques based on two-dimensional orthogonal complete complementary codes,” in Proc. Multi-Carrier Spread-Spectrum, Dordrecht, Netherlands, Jan. 2004, pp. 49–56.
  • [20] P. Farkaš and M. Turcsány, “Two-dimensional orthogonal complete complementary codes,” in Proc. Joint IST Workshop on Mobile Future and Symp. on Trends in Commun., Bratislava, Slovakia, Oct. 2003, pp. 1–5.
  • [21] C.-Y. Chen, C.-H. Wang, and C.-C. Chao, “Complementary sets and Reed-Muller codes for peak-to-average power ratio reduction in OFDM,” in Proc. 16th Int. Symp. AAECC, LNCS 3857, Las Vegas, NV, Feb. 2006, pp. 317–327.
  • [22] C.-Y. Chen, “Complementary sets of non-power-of-two length for peak-to-average power ratio reduction in OFDM,” IEEE Trans. Inf. Theory, vol. 62, no. 12, pp. 7538–7545, Dec. 2016.
  • [23] ——, “A new construction of Golay complementary sets of non-power-of-two length based on Boolean functions,” in Proc. IEEE Wireless Commun. and Netw. Conf., San Francisco, CA, Mar. 2017, pp. 1–6.
  • [24] ——, “A novel construction of complementary sets with flexible lengths based on Boolean functions,” IEEE Commun. Lett., vol. 22, no. 2, pp. 260–263, Feb. 2018.
  • [25] K.-U. Schmidt, “Complementary sets, generalized Reed-Muller codes, and power control for OFDM,” IEEE Trans. Inf. Theory, vol. 53, no. 2, pp. 808–814, Feb. 2007.
  • [26] A. Rathinakumar and A. K. Chaturvedi, “Complete mutually orthogonal Golay complementary sets from Reed-Muller codes,” IEEE Trans. Inf. Theory, vol. 54, pp. 1339–1346, Mar. 2008.
  • [27] C.-Y. Chen, C.-H. Wang, and C.-C. Chao, “Complete complementary codes and generalized Reed-Muller codes,” IEEE Commun. Lett., vol. 12, pp. 849–851, Nov. 2008.
  • [28] Z. Liu, Y. L. Guan, and U. Parampalli, “New complete complementary codes for peak-to-mean power control in multi-carrier CDMA,” IEEE Trans. Commun., vol. 62, pp. 1105–1113, Mar. 2014.
  • [29] S.-W. Wu, C.-Y. Chen, and Z. Liu, “How to construct mutually orthogonal complementary sets with non-power-of-two lengths?” IEEE Trans. Inf. Theory, 2020, Early Access.
  • [30] C.-Y. Pai, S.-W. Wu, and C.-Y. Chen, “Z-complementary pairs with flexible lengths from generalized Boolean functions,” IEEE Commun. Lett., vol. 24, no. 6, pp. 1183 – 1187, Jun. 2020.
  • [31] Z. Liu, U. Parampalli, and Y. L. Guan, “Optimal odd-length binary Z-complementary pairs,” IEEE Trans. Inf. Theory, vol. 60, no. 9, pp. 5768–5781, Sep. 2014.
  • [32] ——, “On even-period binary Z-complementary pairs with large ZCZs,” IEEE Signal Process. Lett., vol. 21, no. 3, pp. 284–287, Mar. 2014.
  • [33] C. Xie and Y. Sun, “Constructions of even-period binary Z-complementary pairs with large ZCZs,” IEEE Signal Process. Lett., vol. 25, no. 8, pp. 1141–1145, Aug. 2018.
  • [34] A. R. Adhikary, P. Sarkar, and S. Majhi, “A direct construction of qq-ary even length Z-complementary pairs using generalized Boolean functions,” IEEE Signal Process. Lett., vol. 27, pp. 146 – 150, 2020.
  • [35] B. Shen, Y. Yang, Z. Zhou, P. Fan, and Y. L. Guan, “New optimal binary Z-complementary pairs of odd length 2m+32^{m}+3,” IEEE Signal Process. Lett., vol. 26, no. 12, pp. 1931–1934, Dec. 2019.
  • [36] S.-W. Wu and C.-Y. Chen, “Optimal Z-complementary sequence sets with good peak-to-average power-ratio property,” IEEE Signal Process. Lett., vol. 25, no. 10, pp. 1500–1504, Oct. 2018.
  • [37] P. Sarkar, S. Majhi, and Z. Liu, “Optimal Z-complementary code set from generalized Reed-Muller codes,” IEEE Trans. Commun., vol. 67, no. 3, pp. 1783–1796, Mar. 2019.
  • [38] H. D. Lüke, “Sets of one and higher dimensional Welti codes and complementary codes,” IEEE Trans. Aerosp. Electron. Syst., vol. AES-21, no. 2, pp. 170–179, Apr. 1985.
  • [39] P. Farkaš, M. Turcsány, and H. Bali, “Application of 2D complete complementary orthogonal codes in 2D-MC-SS-CDMA,” in Proc. Int. Symp. Wireless Personal Multimedia Commun., Abano Terme, Italy, Sep. 2004, pp. 1–5.
  • [40] C.-Y. Pai and C.-Y. Chen, “Constructions of two-dimensional Golay complementary array pairs based on generalized Boolean functions,” in Proc. IEEE Int. Symp. Inf. Theory, Los Angeles, CA, Jun. 2020, pp. 2931–2935.
  • [41] Y. Li and C. Xu, “ZCZ aperiodic complementary sequence sets with low column sequence PMEPR,” IEEE Commun. Lett., vol. 19, no. 8, pp. 1303–1306, Aug. 2015.
  • [42] C.-Y. Pai, Y.-T. Ni, Y.-C. Liu, M.-H. Kuo, and C.-Y. Chen, “Constructions of two-dimensional binary Z-complementary array pairs,” in Proc. IEEE Int. Symp. Inf. Theory, Paris, France, Jul. 2019, pp. 2264–2268.
  • [43] S. Das and S. Majhi, “Two-dimensional Z-complementary array code sets based on matrices of generating polynomials,” IEEE Trans. Signal Process., Early Access.
  • [44] C.-Y. Pai, Y.-T. Ni, and C.-Y. Chen, “Two-dimensional binary Z-complementary array pairs,” IEEE Trans. Inf. Theory, accepted for publication.