×

On the Rudin-Shapiro transform. (English) Zbl 1143.42029

The Rudin-Shapiro polynomials are orthogonal polynomials discovered by Rudin and Shapiro in 1951 that have desirable time-frequency localization properties. The purpose of this work is to give a historical review of the problems addressed by the construction of these polynomials and variants and then to focus on some properties of the (symmetric) Rudin-Shapiro transform (RST). The historical introduction focuses on flat polynomials and includes interesting perspectives both on the mathematical challenges and signal processing motivation. The main technical innovation of this work is a recursive construction of a symmetric RST matrix whose rows are essentially the coefficients of the Rudin-Shapiro polynomials but which also form an orthogonal basis for the corresponding Euclidean space. The RST is defined as follows. Define \({\mathbf{P}}_{j,m}: \mathbb{R}^{2^j}\to \mathbb{R}^{2^j}\) by \[ \left( \begin{matrix} y_k \\ y_{k+2^{j-1}} \end{matrix} \right) = {(-1)^{mk}\over \sqrt{2}}\left( \begin{matrix} 1 & (-1)^k \\ (-1)^m & -(-1)^{k+m} \end{matrix} \right)\left(\begin{matrix} x_{2k} \\ x_{2k+1} \end{matrix} \right) \] and let \[ {\mathbf{P}}_{j}^{J}= \left( \begin{matrix} {\mathbf{P}}_{j,0} & {} & 0 \\ {} & \ddots & {} \\ 0 & {} & {\mathbf{P}}_{j,2^{J-j}-1} \end{matrix} \right). \] The RST is defined as \({\mathbf{P}}^{(J)}= \prod_{j=1}^J {\mathbf{P}}_j^{(J)}\). It is shown that the matrix \({\mathbf{P}}^{(J)}\) is orthogonal and symmetric and that the corresponding polynomials \(P_m^{(J)}(\xi)= \sum_{n=0}^{2^J-1} p_{m,n}^{(J)} \text{ e}^{2\pi i n\xi}\) with coefficients the entries of \({\mathbf{P}}^{(J)}\) are “near flat.” A fast \(O(N\log N)\) (\(N=2^J\)) implementation of the RST is also provided and the RST is compared to the Walsh packet transform.

MSC:

42C05 Orthogonal functions and polynomials, general theory of nontrigonometric harmonic analysis
33C47 Other special orthogonal polynomials and functions
42-02 Research exposition (monographs, survey articles) pertaining to harmonic analysis on Euclidean spaces
65T60 Numerical methods for wavelets
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allouche, J.-P.; France, M. M., On an extremal property of the Rudin-Shapiro sequence, Mathematika, 32, 33-38 (1985) · Zbl 0561.10025
[2] Beck, J., Flat polynomials on the unit circle, Bull. London Math. Soc., 23, 269-277 (1991) · Zbl 0748.30006
[3] Beller, E., Polynomial extremal problems in \(L^p\), Proc. Amer. Math. Soc., 30, 2, 249-259 (1971) · Zbl 0236.30001
[4] Benke, G., Generalized Rudin-Shapiro systems, J. Fourier Anal. Appl., 1, 1, 87-101 (1994) · Zbl 0835.42014
[5] Brillhart, J., On the Rudin-Shapiro polynomials, Duke Math. J., 40, 335-353 (1973) · Zbl 0263.33012
[6] Brillhart, J.; Morton, P., Über Summen von Rudin-Shapiroschen Koeffizienten, Illinois J. Math., 22, 1, 126-148 (1978) · Zbl 0371.10009
[7] Byrnes, J. S., On polynomials with coefficients of modulus one, Bull. London Math. Soc., 9, 171-176 (1977) · Zbl 0364.30004
[8] Byrnes, J. S., Quadrature mirror filters, low crest factor arrays, functions achieving optimal uncertainty principle bounds, and complete orthonormal sequences—A unified approach, Appl. Comput. Harmon. Anal., 1, 261-266 (1994) · Zbl 0802.42023
[9] Byrnes, J. S., A low complexity energy spreading transform coder, (Zeevi, Y.; Corifman, R., Signal and Image Representations in Combined Spaces. Signal and Image Representations in Combined Spaces, Wavelet Analysis and Its Applications, vol. 7 (1998), Academic Press: Academic Press Haifa), 167-187
[10] J.S. Byrnes, I. Gertner, G. Ostheimer, M.A. Ramalho, Discrete one dimensional signal processing apparatus and method using energy spreading coding, June 15, 1999. U.S. Patent No. 5,913,186; J.S. Byrnes, I. Gertner, G. Ostheimer, M.A. Ramalho, Discrete one dimensional signal processing apparatus and method using energy spreading coding, June 15, 1999. U.S. Patent No. 5,913,186
[11] Byrnes, J. S.; Saffari, B.; Shapiro, H. S., Energy spreading and data compression using the Prometheus orthonormal set, (Lervik, J. M.; Waldemar, P., Digital Signal Processing Workshop Proceedings (1996), IEEE: IEEE Loen), 9-12
[12] Clunie, J. C., The minimum modulus of a polynomial on the unit circle, Quart. J. Math., 10, 2, 95-98 (1959) · Zbl 0088.28102
[13] Coifman, R.; Geshwind, F.; Meyer, Y., Noiselets, Appl. Comput. Harmon. Anal., 10, 27-44 (2001) · Zbl 1030.42027
[14] Erdös, P., Some unsolved problems, Michigan Math. J., 4, 291-300 (1957) · Zbl 0081.00102
[15] Fredman, M. L.; Saffari, B.; Smith, B., Polynômes réciproques : conjecture d’Erdös en norme \(L^4\), taille des autocorrélations et inexistence des codes de Barker, C. R. Acad. Sci. Paris Sér. I Math., 308, 15, 461-464 (1989) · Zbl 0679.42002
[16] Golay, M. J.E., Multislit spectrometry, J. Opt. Soc. Amer., 39, 437-444 (1949)
[17] Golay, M. J.E., Static multislit spectroscopy and its applications to the panoramic display of infrared spectra, J. Opt. Soc. Amer., 41, 468-472 (1951)
[18] Golay, M. J.E., Complementary series, IRE Trans., IT-7, 82-87 (1961)
[19] Hardy, G. H.; Littlewood, J. E., Some problems of Diophantine approximation: A remarkable trigonometrical series, Proc. Natl. Acad. Sci., 2, 583-586 (1916) · JFM 46.0443.02
[20] Jensen, A.; la Cour-Harbo, A., Ripples in Mathematics—The Discrete Wavelet Transform (2001), Springer: Springer Heidelberg/Berlin · Zbl 0989.42013
[21] Kahane, J.-P., Sur les polynomes a coefficients unimodulaires, Bull. London Math. Soc., 12, 321-342 (1980) · Zbl 0443.30005
[22] Körner, T. W., On a polynomial of Byrnes, Bull. London Math. Soc., 12, 219-224 (1980) · Zbl 0435.30004
[23] A. la Cour-Harbo, Robust and low-cost active sensors by means of signal processing algorithms, Ph.D. thesis, Aalborg University, 2002; A. la Cour-Harbo, Robust and low-cost active sensors by means of signal processing algorithms, Ph.D. thesis, Aalborg University, 2002
[24] la Cour-Harbo, A., The symmetric Rudin-Shapiro transform—An easy, stable, and fast construction of multiple orthogonal spread spectrum signals, IEEE Proc. Acoust. Speech Signal Process., 6, 397-400 (2003)
[25] Littlewood, J. E., On the mean values of certain trigonometric polynomials (ii), Illinois J. Math., 6, 1-39 (1962) · Zbl 0108.05802
[26] Littlewood, J. E., On polynomials \(\sum^n \pm z^m, \sum^n e^{\alpha_m i} z^m, z = e^{\theta i}\), J. London Math. Soc., 41, 367-376 (1966) · Zbl 0142.32603
[27] Mendès France, M.; Tenenbaum, G., Dimension des courbes planes, papiers pliés et suites de Rudin-Shapiro, Bull. Soc. Math. France, 109, 2, 207-215 (1981) · Zbl 0468.10033
[28] Nazarahty, M.; Newton, S. A.; Giffard, R. P.; Moberly, D. S.; Sischka, F.; Trutna, W. R., Real-time long range complementary correlation optical time domain reflectometer, IEEE J. Lightwave Technol., 7, 24-38 (1989)
[29] Newman, D. J., An \(l^1\) extremal problem for polynomials, Proc. Amer. Math. Soc., 16, 1287-1290 (1965) · Zbl 0151.08103
[30] No, J.-S.; Chung, H.; Yun, M.-S., Binary pseudorandom sequences of period \(2^m - 1\) with ideal autocorrelation generated by the polynomial \(z^d +(z + 1)^d\), IEEE Trans. Inform. Theory, 44, 3, 1278-1282 (1998) · Zbl 0912.94017
[31] No, J.-S.; Golomb, S. W.; Gong, G.; Lee, H.-K.; Gaal, P., Binary pseudorandom sequences of period \(2^n - 1\) with ideal autocorrelation, IEEE Trans. Inform. Theory, 44, 2, 814-817 (1998) · Zbl 0912.94016
[32] No, J.-S.; Kumar, P. V., A new family of binary pseudorandom sequences having optimal periodic correlation properties and larger linear span, IEEE Trans. Inform. Theory, 35, 2, 371-379 (1989) · Zbl 0678.94009
[33] Rudin, W., Some theorems on Fourier coefficients, Proc. Amer. Math. Soc., 10, 855-859 (1959) · Zbl 0091.05706
[34] Saffari, Bahman, Une fonction extrémale liée à la suite de Rudin-Shapiro, C. R. Acad. Sci. Paris Sér. I Math., 303, 4, 97-100 (1986) · Zbl 0608.10051
[35] Saffari, Bahman; Smith, Brent, Sur une note récente relative aux polynômes à coefficients ±1 et à la conjecture d’Erdös, C. R. Acad. Sci. Paris Sér. I Math., 310, 7, 541-544 (1990) · Zbl 0704.30006
[36] H.S. Shapiro, Extremal problems for polynomials and power series, Master’s thesis, Massachusetts Institute of Technology, 1951; H.S. Shapiro, Extremal problems for polynomials and power series, Master’s thesis, Massachusetts Institute of Technology, 1951
[37] Taghavi, M., An estimate on the correlation coefficients of the Rudin-Shapiro polynomials, Iranian J. Sci. Technol., 20, 2, Trans. A Sci., 235-240 (1996) · Zbl 0926.42003
[38] Taghavi, M., Upper bounds for the autocorrelation coefficients of the Rudin-Shapiro polynomials, Korean J. Comput. Appl. Math., 4, 1, 39-46 (1997) · Zbl 0921.11042
[39] Tseng, C.-C., Signal multiplexing in surface-wave delay lines using orthogonal pairs of golay’s complementary sequences, IEEE Trans. Sonics Ultrason., SU-18, 103-107 (1971)
[40] Zygmund, A., Trigonometrical Series (1935), Warsaw · JFM 61.0263.03
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.