Crosscorrelation of Rudin-Shapiro-like polynomials

DOI10.1016/J.ACHA.2018.07.003MaRDI QIDQ2300747zbMATH OpenOpenAlexWikidataFDO

Authors Daniel J. Katz, Sangman Lee, Stanislav A. Trunov

Publication date 28 February 2020

Published in Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.07697

zbMATH Keywords

autocorrelationcorrelationcrosscorrelationdemerit factorGolay-Rudin-Shapiro sequenceLittlewood polynomialmerit factorRudin-Shapiro-like polynomial

Mathematics Subject Classification ID

Special sequences and polynomials (11B83) Trigonometric polynomials, inequalities, extremal problems (42A05) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55)

Abstract: We consider the class of Rudin-Shapiro-like polynomials, whose $L^4$ norms on the complex unit circle were studied by Borwein and Mossinghoff. The polynomial $f(z)=f_0+f_{1}z+cdots+f_d{z}^d$ is identified with the sequence $(f_0,f_1,ldots,f_d)$ of its coefficients. From the $L^4$ norm of a polynomial, one can easily calculate the autocorrelation merit factor of its associated sequence, and conversely. In this paper, we study the crosscorrelation properties of pairs of sequences associated to Rudin-Shapiro-like polynomials. We find an explicit formula for the crosscorrelation merit factor. A computer search is then used to find pairs of Rudin-Shapiro-like polynomials whose autocorrelation and crosscorrelation merit factors are simultaneously high. Pursley and Sarwate proved a bound that limits how good this combined autocorrelation and crosscorrelation performance can be. We find infinite families of polynomials whose performance approaches quite close to this fundamental limit.

Review text

For two complex-valued sequences \(f = (f_0,f_1,\ldots,f_{l-1})\) and \(g = (g_0,g_1,\ldots,g_{l-1})\) of length \(l\) the crosscorrelation demerit factor of \(f\) and \(g\) (the reciprocal of the crosscorrelation merit factor) is defined as \[ \mathrm{CDF}(f,g) = \frac{\sum_{s\in\mathbb{Z}}|C_{f,g}(s)|^2}{|C_{f,f}(0)|\cdot |C_{g,g}(0)|}, \] where \[ C_{f,g}(s) = \sum_{j\in\mathbb{Z}}f_{j+s}\overline{g_j}, \quad f_j = g_j = 0\;\mbox{if}\;j\not\in\{0,1,\ldots,l-1\} \] is the aperiodic crosscorrelation of \(f\) and \(g\) at shift \(s\). The autocorrelation demerit factor of \(f\) is \(\mathrm{ADF}(f) = \mathrm{CDF}(f,f)-1\). Assigning to sequences \(f = (f_0,f_1,\ldots,f_{l-1})\) of length \(l\), polynomials \(f(z) = f_0+f_1z+\cdots+f_{l-1}z^{l-1}\) of degree \(l-1\), the authors consider Rudin-Shapiro-like sequences recursively defined as \[ f_{n+1}(z) = f_n(z) + \sigma_nz^{1+\deg f_n}f_n^*(-z), \] where \(\sigma_n\in\{-1,1\}\), and for \(a(z) = a_0+a_1z+\cdots+a_dz^d\) the polynomial \(a^*(z)\) is the conjugate reciprocal polynomial \(a^*(z) = \overline{a_d}+\overline{a_{d-1}}z+\cdots+\overline{a_0}z^d\). Differently from the Rudin-Shapiro-like sequences in [\textit{P. Borwein} and \textit{M. Mossinghoff}, Math. Comput. 69, No. 231, 1157--1166 (2000; Zbl 1042.11046)], where the ``seed \(f_0\) is always a Littlewood polynomial, in this article \(f_0\) may be any complex polynomial with a nonzero constant term. In Borwein, Mossinghoff [loc. cit.], a formula for the asymptotic behaviour of ADF(\(f_n\)) (where \(f_0\) is a Littlewood polynomial) is presented. \textit{M. B. Pursley} and \textit{D. V. Sarwate} [``Bounds on aperiodic cross-correlation for binary sequences , Electron. Lett. 12., 304--305 (1976)] proved the bound \(|\mathrm{CDF}(f,g) - 1| \le \sqrt{\mathrm{ADF}(f)\mathrm{ADF}(g)}\) which relates CDF and ADF. According to this, the authors of this article define the Pursley-Sarwate Criterion of \(f\) and \(g\) as PSC\((f,g) = \sqrt{\mathrm{ADF}(f)\mathrm{ADF}(g)} + \mathrm{CDF}(f,g)\), which then satisfies PSC\((f,g) \ge 1\). As a main result, the authors present a formula for the asymptotic behaviour of the crosscorrelation demerit factor CDF(\(f_n,g_n\)) of Rudin-Shapiro-like polynomials which also generalizes the formula for the asymptotic ADF result for seeds \(f_0\) other than Littlewood polynomials. The formula is then used to find families of pairs of Rudin-Shapiro-like polynomials whose Persley-Sarwate-Criterion is as low as 331/300.

Recommendations

• Rudin-Shapiro-like polynomials in $L_{4}$
• Bounds on autocorrelation coefficients of Rudin-Shapiro polynomials. II
• Dyadic representation of the Rudin-Shapiro coefficients with applications
• Bounds on autocorrelation coefficients of Rudin-Shapiro polynomials
• The asymptotic value of the Mahler measure of the Rudin-Shapiro polynomials

Cites work

• A class of finite binary sequences with alternate auto-correlation values equal to zero (Corresp.)
• Aperiodic Crosscorrelation of Sequences Derived From Characters
• Applied Algebra, Algebraic Algorithms and Error-Correcting Codes
• Determination of the merit factor of Legendre sequences
• Group characters: Sequences with good correlation properties
• scientific article; zbMATH DE number 3294856 (Why is no real title available?)
• scientific article; zbMATH DE number 2238187 (Why is no real title available?)
• Low Correlation Sequences From Linear Combinations of Characters
• Number theory in science and communication. With applications in cryptography, physics, digital information, computing, and self-similarity
• On Polynomials ∑±nzm,∑eαminzm,z=e0i
• Rudin-Shapiro-like polynomials in $L_{4}$
• Some Theorems on Fourier Coefficients

Cited in

(4)

• Bounds on autocorrelation coefficients of Rudin-Shapiro polynomials. II
• Asymptotic \(L^4\) norm of polynomials derived from characters
• On maximal autocorrelations of Rudin-Shapiro sequences
• Rudin-Shapiro-like polynomials in $L_{4}$

This page was built for publication: Crosscorrelation of Rudin-Shapiro-like polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2300747)