Abstract
Perfect sequences find application in many areas including synchronisation techniques, channel estimation, fast start-up equalization, pulse compression radars and CDMA systems. This paper will first discuss the necessary and sufficient condition for, and some useful properties of, perfect sequences. Then, a comprehensive description of various perfect sequences is given. The emphasis will be on the synthesis of different perfect sequences, including two-valued perfect sequences, ternary perfect sequences, polyphase perfect sequences and modulatable perfect sequences. The perfect array and other related topics are also discussed briefly.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
H. Rohling and W. Plagge, “Mismatched-filter design for periodical binary phased signals”, IEEE Trans. on Aerospace and Electronic Systems, vol. AES-25, no. 6, pp. 890–897, November 1989.
H. D. Lüke, “Sequences and arrays with perfect periodic correlation”, IEEE Trans. on Aerospace and Electron. Systems, vol. AES-24, no. 3, pp. 287–294, May 1988.
S. U. H. Qureshi, “Fast start-up equalization with periodic training sequences”, IEEE Trans. on Information Theory, vol. IT-23, pp. 553–563, 1977.
A. Milewski, “Periodic sequences with optimal properties for channel estimation and fast start-up equalization”, IBM J. RES. DEVELOP., vol. 27, no. 5, pp. 426–431, Sept. 1983.
K. R. Godfrey, “Three-level m sequences”, Electron. Lett., vol. 2, no. 7, pp. 241–243, July 1966.
N. Levanon and A. Freedman, “Periodic ambiguity function of CW signals with perfect periodic autocorrelation”, IEEE Trans. on Aerospace and Electronic Systems, vol. AES-28, no. 2, pp. 387–395, April 1992.
F. F. Kretschmer Jr. and K. Gerlach, “Low sidelobe radar waveforms derived from orthogonal matrices”, IEEE Trans. on AES, vol. AES-27, no. 1, pp. 92–101, Jan. 1991.
N. Suehiro and M. Hatori, “Modulatable orthogonal sequences and their application to SSMA systems”, IEEE Trans. on Information Theory, vol. IT-34, pp. 93–100, Jan. 1988.
D. V. Sarwate, “Bounds on crosscorrelation and autocorrelation of sequences”, IEEE Transactions on Information Theory, vol. 25, pp. 720–724, 1979.
S. W. Golomb, “Two-valued sequences with perfect periodic autocorrelation”, IEEE Trans. on Aerospace and Electronic Systems, vol. AES-28, no. 2, pp. 383–386, April 1992.
J. A. Chang, “Ternary sequence with zero correlation”, Proceedings of the IEEE, Vol. 55, no. 7, pp. 1211–1213, July 1967.
P. S. Moharir, “Generalized PN sequences”, IEEE Trans. on Inform. Theory, vol. IT-23, no. 6, pp. 782–784, Nov. 1977.
V. P. Ipatov, “Ternary sequences with ideal autocorrelation properties”, Radio Eng. Electron. Phys., vol. 24, pp. 75–79, October 1979.
V. P. Ipatov, “Contribution to the theory of sequences with perfect periodic autocorrelation properties”, Radio Eng. Electron. Phys., vol. 25, pp. 31–34, April 1980.
D. A. Shedd and D. V. Sarwate, “Construction of sequences with good correlation properties”, IEEE Transactions on Information Theory, vol. 25, no. 1, pp. 94–97, January 1979.
T. Hoholdt and J. Justesen, “Ternary sequences with perfect periodic autocorrelation”, IEEE Trans. on IT, vol. 29, no. 4, pp. 597–600, July 1983.
L. Bomer and M. Antweiler, “New perfect threelevel and threephase sequences”, in IEEE Int. Symp. Inform. Theory, Budapest, Hungary, June 24–28 1991, p. 280.
P. Z. Fan and M. Darnell, “Maximal length sequences over Gaussian integers”, Electron. Lett., vol. 30, no. 16, pp. 1286–1287, August 1994.
M. Darnell, P. Z. Fan, and F. Jin, “New classes of perfect sequences derived from m-sequences”, 1995 IEEE International Symposium on Information Theory, Whistler, Canada, Sept 17–22 1994.
R. C. Heimiller, “Phase shift pulse codes with good periodic correlation properties”, IRE Trans. on IT, vol. IT-7, pp. 254–257, 1961.
R. L. Frank and S. A. Zadoff, “Phase shift pulse codes with good periodic correlation properties”, IRE Trans. on Information Theory, vol. IT-8, pp. 381–382, October 1962.
R. L. Frank, “Polyphase codes with good nonperiodic correlation properties”, IEEE Trans. on Information Theory, vol. IT-9, pp. 43–45, January 1963.
R. C. Heimiller, “Author's comment”, IRE Trans. on IT, vol. IT-8, pp. 382, Oct. 1962.
D. C. Chu, “Polyphase codes with good periodic correlation properties”, IEEE Trans. on Information Theory, vol. IT-18, pp. 531–533, July 1972.
R. L. Frank, “Comments on Polyphase codes with good correlation properties”, IEEE Trans. on Information Theory, vol. IT-19, pp. 244, March 1973.
B. M. Popović, “Generalized chirp-like polyphase sequences with optimum correlation properties”, IEEE Trans. on Information Theory, vol. IT-38, no. 4, pp. 1406–1409, July 1992.
W. O. Alltop, “Complex sequences with low periodic correlations”, IEEE Trans. Inform. Theory, vol. IT-26, no. 3, pp. 350–354, May 1980.
V. P. Ipatov, “Multiphase sequences spectrums”, Izvestiya VUZ. Radioelektronika (Radioelectronics and Communications Systems), vol. 22, no. 9, pp. 80–82, 1979.
H. Chung and P. V. Kumar, “A new general construction for generalized bent functions”, IEEE Trans. on Information Theory, vol. IT-35, no. 1, pp. 206–209, Jan. 1989.
P.V. Kumar, R. A. Scholtz, and L. R. Welch, “Generalized bent functions and their properties”, J. Combinat. Theory, series A, vol. 40, no. 1, pp. 90–107, 1985.
B. L. Lewis and F. F. Kretschmer, “Linear frequency modulation derived polyphase pulse compression”, IEEE Trans. on AES, vol. AES-18, no. 5, pp. 637–641, Sept. 1982.
B. M. Popović, “Efficient matched filter for the generalized chirp-like polyphase sequences”, IEEE Trans. on Aerospace and Electronic Systems, vol. 30, no. 3, pp. 769–777, July 1994.
N. Zhang and S. W. Golomb, “Polyphase sequence with low autocorrelations”, IEEE Trans. on Information Theory, vol. IT-39, pp. 1085–1089, May 1993.
P. Z. Fan, M. Darnell, and B. Honary, “Crosscorrelations of frank sequences and chu sequences”, Electron. Lett., vol. 30, no. 6, pp. 477–478, March 1994.
E. M. Gabidulin, “Non-binary sequences with the perfect periodic auto-correlation and with optimal periodic cross-correlation”, in Proc. IEEE Int. Symp. Inform. Theory, San Antonio, USA, January 1993, p. 412.
W. H. Mow, “A unified construction of perfect polyphase sequences”, in Proc. IEEE Int. Symp. Inform. Theory, Whistler, B.C. Canada, Sept 17–22 1995.
E. M. Gabidulin, “Partial classification of sequences with perfect auto-correlation and bent functions”, in Proc. IEEE Int. Symp. Inform. Theory, Whistler, B.C. Canada, Sept 17–22 1995.
B. M. Popović, “GCL polyphase sequences with minimum alphabets”, Electron. Lett., vol. 30, no. 2, pp. 106–107, January 1994.
D. Calabro and J.K. Wolf, “On the synthesis of two-dimensional arrays with desirable correlation properties”, Information and Control, vol. 11, pp. 537–560, 1968.
L. Bömer and M. Antweiler, “Two-dimensional perfect binary arrays with 64 elements”, IEEE Trans. on IT, vol. IT-36, pp. 411–414, 1990.
H. D. Lüke, “Perfect ternary arrays”, IEEE Trans. on Information Theory, vol. IT-36, no. 3, pp. 696–705, May 1990.
L. Bömer and M. Antweiler, “Perfect N-phase sequences and arrays”, IEEE Journal on Selected Areas in Communications, vol. 10, pp. 782–789, 1992.
E. M. Gabidulin, “There are only finitely many perfect auto-correlation polyphase sequences of prime length”, in Proc. IEEE Int. Symp. Inform. Theory, Trondheim, Norway, June 27–July 1 1994, p. 282.
P. Z. Fan and M. Darnell, “Aperiodic autocorrelation of Frank sequences”, IEE Proceedings on Communications, vol. 142, no. 4, pp. 210–215, 1995.
E. M. Gabidulin, P. Z. Fan, and M. Darnell, “On the autocorrelation of Golomb sequences”, IEE Proceedings on Communications, vol. 143, no. 1, 1996.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fan, P.Z., Darnell, M. (1995). The synthesis of perfect sequences. In: Boyd, C. (eds) Cryptography and Coding. Cryptography and Coding 1995. Lecture Notes in Computer Science, vol 1025. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60693-9_9
Download citation
DOI: https://doi.org/10.1007/3-540-60693-9_9
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60693-2
Online ISBN: 978-3-540-49280-1
eBook Packages: Springer Book Archive