Source-linked AI summary
Constructions of Polyphase Golay Complementary Arrays
Cheng Du, Yi Jiang
TL;DR
Finding construction methods for arbitrary lengths is challenging, while GCA precoding is an important application. The paper generalizes GCM to multidimensional GCA and proposes constructions based on commutative-ring identities, establishing feasible-size results for quaternary pairs and binary and quaternary quads.
Problem
Construction methods for Golay complementary arrays at arbitrary lengths are challenging, despite their applications including GCA precoding.
Method
The paper generalizes GCM to polyphase GCA pairs and quads and proposes construction methods using identities over a commutative ring.
Results
Quaternary GCA pairs have feasible sizes under a specified factorization form and constraint; binary GCM quads cover sizes within 78 × 78, while quaternary GCM quads cover all positive integers within 1000 in one dimension.
Takeaways & Limitations
The constructions provide feasible-size coverage for polyphase GCA pairs and quads, including broad verified ranges for binary and quaternary quads.
Abstract
from arXiv · showhide
Golay complementary matrices (GCM) have recently drawn considerable attentions owing to its potential applications in omnidirectional precoding. In this paper we generalize the GCM to multi-dimensional Golay complementary arrays (GCA) and propose new constructions of GCA pairs and GCA quads. These constructions are facilitated by introducing a set of identities over a commutative ring. We prove that a quaternary GCA pair is feasible if the product of the array sizes in all dimensions is a quaternary Golay number with an additional constraint on the factorization of the product. For the binary GCM quads, we conjecture that the feasible sizes are arbitrary, and verify for sizes within 78 $\times$ 78 and other less densely distributed sizes. For the quaternary GCM quads, all the positive integers within 1000 can be covered for the size in one dimension.
I. INTRODUCTION
The paper motivates polyphase Golay complementary arrays as multidimensional generalizations with applications in precoding and flexible-size antenna arrays. It develops commutative-ring constructions that expand feasible sizes for GCA pairs and quads.
- Motivation and background: 28 quaternary Golay lengths within 28 were verified by exhaustive computational search.These lengths are part of a denser existence pattern than the binary counterpart.
- Motivation and background: Polyphase GCA sets generalize Golay sequence pairs and matrices to multiple dimensions using arrays whose autocorrelations sum to a delta-function.Binary GCA pairs have array sizes in each dimension given by binary Golay numbers.
- Applications and challenges: GCA precoding can reduce OFDM peak-to-average power ratio, but the code rate is restricted by the number of sequences obtained by projecting high-dimensional arrays.The paper also identifies omnidirectional transmission with massive MIMO antenna arrays as an application of GCM sets.
- Contributions: The paper establishes commutative-ring identities and uses them to construct polyphase GCA pairs and quads with more feasible sizes.The identities support the constructions developed in later theorems.
- Contributions: 78×78 binary GCM-quad sizes are covered, while all positive integers within 1000 are covered for the one-dimensional size of quaternary GCM quads.The paper conjectures that binary GCM quads exist for arbitrary sizes.
II. PRELIMINARIES: POLYNOMIALS OF GOLAY COMPLEMENTARY ARRAYS AND COMMUTATIVE
This section defines GCAs through autocorrelation, polynomial, and commutative-ring viewpoints. It relates array operations to polynomial convolution and uses involutive automorphisms to unify these descriptions.
- Polynomial and ring viewpoints: The commutative-ring framework treats multivariable polynomials as entities, allowing their properties to support recursive GCA constructions.The paper introduces the ring operations, identity elements, and additive inverses needed for this framework.
- GCA definitions: A GCA set consists of arrays with unimodular or zero entries whose multidimensional autocorrelation functions sum to a unit pulse.The unit pulse has zeros except for a central entry equal to 1.
- GCA definitions: Polyphase arrays use N-th unit roots as entries, with binary and quaternary arrays defined by {1, −1} and {1, −1, j, −j}, respectively.A GCA set reduces to a Golay sequence set when r = 1 and a GCM set when r = 2.
- Polynomial representation: The polynomial representation of an array uses multivariable indeterminates, and polynomial multiplication corresponds to array convolution.In signal processing, this polynomial is the signal’s Z-transform.
- Polynomial and ring viewpoints: The flipped-and-conjugated array operation defines an involutive automorphism, enabling a polynomial formulation equivalent to the autocorrelation definition.The array and polynomial rings are isomorphic under element-wise addition and convolution.
III. FOUR LEMMAS
Four commutative-ring identities provide the algebraic foundation for recursive Golay-array constructions. The paper illustrates their use in binary GCA pairs while preserving complementarity and polyphase entries.
- Ring identities: Four identities over a commutative ring with an involutive automorphism form the cornerstone of the paper’s GCA constructions.The framework replaces tedious polynomial expansions with algebraic manipulation of entities.
- Identity limitations: The quad identity is related to the quaternion and octonion norm identities, but no eight-component Lagrange identity exists because only four normed division algebras exist.This algebraic boundary limits direct extension of the identity to eight components.
- Binary GCA-pair construction: Theorem III.1 combines binary GCA pairs of sizes s1×···×sr and t1×···×tr into a pair of size s1t1×···×srtr.The construction uses the Kronecker product and polynomial identities.
- Binary GCA-pair construction: Kronecker products preserve the polyphase property by using sparse polynomial substitutions that avoid coefficient summation during convolution.This explains why ordinary polynomial multiplication alone is insufficient for the construction.
- Binary GCA-pair construction: The constructed arrays remain binary because combinations of binary arrays produce entries constrained to binary values under the stated transformation.The proof verifies both autocorrelation complementarity and binary entries.
IV. CONSTRUCTIONS OF POLYPHASE GCA PAIRS
The paper develops multi-dimensional polyphase GCA-pair constructions, including concatenation and zero-assignment methods, and derives broader feasible-size conditions for quaternary pairs.
- Polyphase constructions: Theorem IV.2 generalizes concatenation to polyphase, multi-dimensional GCA pairs and produces a denser feasible set than Theorem IV.1.Its construction concatenates arrays in one dimension and preserves polyphase entries.
- Theorem IV.3: Theorem IV.3 uses a binary GCA pair with two polyphase GCA pairs to construct a new polyphase pair with dimensions s1t1u1 × ··· × srtrur.The binary pair acts as a binder, while recursive use of Lemma 1 establishes autocorrelation complementarity.
- Feasible sizes: Quaternary GCA-pair sizes have product 2^(a+u)3^b5^c11^d13^e subject to b+c+d+e ≤ a+2u+1 and u ≤ c+e.Each of the u factors 10 or 26 must not be factorized into different dimensions.
- Feasible sizes: The factorization constraint distinguishes feasible examples: a quaternary GCM pair of size 9 × 10 exists, whereas one of size 18 × 5 cannot be constructed.The paper explicitly presents these as consequences of the additional factorization constraint.
V. CONSTRUCTIONS OF POLYPHASE GCA QUADS
The paper develops polyphase GCA quad constructions by combining array sets through commutative-ring identities, zero placement, and dimension-wise composition. These constructions expand feasible size patterns, including binary quads within 78 × 78 and quaternary one-dimensional sizes covering nearly all positive integers within 1000.
- Composition constructions: Theorem V.2 combines two polyphase GCA sets to produce a polyphase GCA set whose dimensions are multiplied coordinatewise.The resulting size is s1t1 × s2t2 × · · · × srtr.
- Quaternary results: 3 × 6 pairs yield a quaternary GCM quad of size 9 × 36, although 9 is not a quaternary Golay number.This demonstrates that Theorem V.2 constructs sizes unavailable through Theorem V.1.
- Quad constructions: Theorem V.4 combines a polyphase GCA quad with a disjoint GCA pair to construct another polyphase GCA quad without requiring the same intermediate size expansion.The output size is s1t1 × s2t2 × · · · × srtr, and disjointness preserves polyphase entries.
VI. CONCLUSIONS
The paper develops polyphase GCA pair and quad constructions using commutative-ring identities, deriving feasibility conditions and covering broad size ranges for binary and quaternary cases.
- Constructions: The constructions produce polyphase GCA pairs and quads from four identities over a commutative ring.These identities are presented as the basis for the construction methods.
- Quaternary GCA pairs: Quaternary GCA pair sizes are characterized by products of array dimensions that satisfy a specified quaternary Golay-number factorization condition.The product has form 2^a+u3^b5^c11^d13^e, with constraints on the exponents and on factorization across dimensions.
- Binary GCM quads: Binary GCM quad sizes are expressed through binary Golay numbers, and all sizes within 78 × 78 are covered while arbitrary existence remains conjectured.The conclusion distinguishes verified coverage from the conjecture of existence for arbitrary sizes.
- Quaternary GCM quads: For quaternary GCM quads of size s1 × s2, all positive integers within 1000 can be covered for the size in one dimension.Additional quad sizes are obtained from feasible quaternary GCM-pair dimensions through the stated construction.
- Implementation: Matlab codes for generating GCMs of the known feasible sizes are available online.The codes cover the sizes described in Corollaries IV.3, V.3, and V.6.