Retrospective Review of Perfect Ternary Sequences and Their Generators
https://doi.org/10.32603/1993-8985-2019-22-4-6-17
Abstract
Introduction. Perfect polyphase unimodular sequences, i.e. sequences with ideal periodic autocorrelation and single amplitude of symbols are widely used in modern radio communications and radars. Among them a special place is occupied by perfect ternary sequences (PTSs) with elements {–1, 0, 1}. PTSs are quite numerous and their length in comparison with perfect binary sequences is not limited from above. There is a well-known review of PTS families undertaken by Fan and Darnell in 1996. However, over the past two decades numerous new PTS families have been discovered. Connections between PTSs and circulant weighing matrices have been established and certain theorems on the existence of PTS existence for certain lengths have also been obtained. Therefore, there is a need for a new modern review of existing PTSs.
Objective. This review of existing PTSs is intended for developers of radio electronic systems using perfect sequences.
Materials and methods. Domestic and foreign sources of information (books, journal papers, conference proceedings, patents) were considered and analysed. A Web search was carried out based on keywords using resources of Yandex and Google, as well as in digital electronic libraries (Russian State Library (RSL), IEEE Xplore Digital Library), conference materials (Digital Signal Processing and its Application (DSPA), Sequences and their Applications (SETA), etc.).
Results. In addition to the matter of collating an informational bibliography, the review shows the relationship between PTSs obtained at different times and their connection with circulant weighing matrices. The review also describes the generators of known PTS families (Ipatov, Hoholdt-Justensen, etc.).
Conclusion. A retrospective review of PTSs is herein presented and the generators of certain known PTS families have been considered. The results of the study are relevant for use in modern radio communications and radar systems and in CW and LPI radars in particular.
About the Author
Evgeny I. Krengel
JSC "Modern wireless technologies" (JSC "SBT")
Russian Federation
Russian Federation
Cand. Sci. (Engineering) (2002), leading researcher
References
1. Ipatov V. P. Periodicheskie diskretnye signaly s optimal'nymi korrelyatsionnymi svoistvami [Periodic discrete signals with optimal properties]. Moscow, Radio i svyaz, 1992, 151 p. (in Russ.)
2. Fan P., Darnell M. Sequence Design for Communications Applications. London, Research Studies Press Ltd, 1996, 493 p.
3. Levanon N., Mozenson E. Radar Signals. New Jersey, John Wiley & Sons, 2004, 411 p.
4. Pace P. E. Detecting and Classifying Low Probability of Intercept Radar. London, Artech House, 2009, 893 p.
5. Lee C.E. Perfect q-ary Sequences from Multiplicative Characters over GF(p). Electronics Letters. 1992, vol. 28, no. 9, pp. 833–835. doi: 10.1049/el:19920527
6. Lüke H. D. BTP-transform and Perfect Sequences with Small Phase Alphabet. IEEE Trans. Aerosp. Electron. Syst. 1996, vol. AES-32, no. 1, pp. 497–499. doi:10.1109/7.481295
7. Schotten H. D., Lüke H. D. New Perfect and w-Cyclic-Perfect Sequences. Proc. 1996 IEEE Inter. Symp. on Information Theory. Victoria, British Columbia, Canada, 17– 20 September, 1996. Piscataway, IEEE, 1996, pp. 82–85.
8. Krengel E. I. New Perfect 4- and 8-Phase Sequences with Zeros. Radiotekhnika [Radioengineering]. 2007, no. 5, pp. 3–7. (in Russ.)
9. Levanon N., Freedman A. Periodic Ambiguity Function of CW Signals with Perfect Periodic Autocorrelation. IEEE Trans. on Aerospace and Electronic Systems. 1992, vol. AES-28, no. 2, pp. 387–395. doi:10.1109/7.144564
10. Chang J. A. Ternary Sequences with Zero-correlation. Proc. of the IEEE. 1997, vol. 55, no. 7, pp. 1211–1213. doi: 10.1109/PROC.1967.5793
11. Green D. H., Kelsch R. G. Ternary pseudonoise sequences. Electronics letters. 1972, vol. 8, no. 5, pp. 112–113. doi: 10.1049/el:19720081
12. Moharir P. S. Generalized PN sequences. IEEE Trans. on Information Theory. 1977, vol. IT-23, iss. 6, pp. 782–784. doi: 10.1109/TIT.1977.1055782
13. Sarwate D. V., Pursley M. B. Crosscorrelation of Pseudorandom and Related Sequences. Proc. of IEEE. 1980, vol. 68, iss. 5, pp. 593–619. doi: 10.1109/ PROC.1980.11697.
14. Gold R. Maximal Recursive Sequences with 3-valued Recursive Cross-Correlation Functions. IEEE Trans. Inform. Theory. 1968, vol. IT-14, iss. 1, pp. 154–156. doi: 10.1109/TIT.1968.1054106
15. Niho Y. Multivalued Cross-Correlation Functions between Two Maximal Linear Recursive Sequences: Ph. D. dissertation. Univ. Southern Calif. Los Angeles, 1972. 150 p. Available at: http://digitallibrary.usc.edu/cdm/ref/ collection/p15799coll37/id/51150 (accessed 30.07.2019)
16. Kasami T. The Weight Enumerators for Several Classes of Subcodes of the 2nd Order Binary Reed-Muller Codes. Information and Control. 1971, vol. 18, no. 4, pp. 369–394. doi: 10.1016/S0019-9958(71)90473-6
17. Helleseth T. Some Results about the Cross-Correlation Function between Two Maximal Linear Sequences. Discrete Mathematics. 1976, vol. 16, iss. 3, pp. 209–232. doi: 10.1016/0012-365X(76)90100-X
18. Shedd D. A., Sarwate D. V. Construction of Sequences with Good Correlation Properties. IEEE Trans. on Information Theory. 1979, vol. IT-25, iss. 1, pp. 94–97. doi: 10.1109/TIT.1979.1055998
19. Ipatov V. P. Troichnye posledovatel'nosti s ideal'nymi periodicheskimi avtokorreljacionnymi svojstvami [Ternary Sequences with Ideal Periodic Autocorrelation Properties]. Radio Eng. Electron. 1979, vol. 24, no. 10, pp. 2053–2057. (in Russ.)
20. Hoholdt T., Justesen J. Ternary sequences with perfect periodic autocorrelation (Corresp.). IEEE Trans. on Information Theory. 1983, vol. IT-29, iss. 4, pp. 597–600. doi: 10.1109/TIT.1983.1056707.
21. Ipatov V. P., Platonov V. D., Samoilov I. M. A New Class of Triple Sequences with Ideal Periodic Autocorrelation Properties. Izvestiya vyzov USSR. Mathematics. 1983, no. 3, pp 47–50. (in Russ.)
22. Kamaletdinov B. S. Troichnye posledovatel'nosti s ideal'nymi periodicheskimi avtokorreljacionnymi svojstvami [Ternary Sequences with Ideal Periodic Autocorrelation Properties]. Radio Eng. Electron. 1987, vol. 32, no. 1, pp. 77–82. (in Russ.)
23. Golomb S. W., Gong G. Signal Design for Good Correlation: for Wireless Communication, Cryptography, and Radar. Cambridge, Cambridge University Press, 2005, 455 p.
24. Games R. A. Crosscorrelation of m-Sequences and GMW Sequences with the Same Primitive Polynomial. Discrete Applied Mathematics. 1985, vol. 12, iss. 2, pp. 139–146. doi: 10.1016/0166-218X(85)90067-8
25. Antweiler M. Cross-correlation of p-ary GMW Sequences. IEEE Trans. on Information Theory. 1984, vol. IT-40, iss. 4, pp. 1253–1261. doi: 10.1109/18.335941
26. Cusick T. W., Dobbertin H. Some New Three-Valued Crosscorrelation Functions for Binary m-Sequences. IEEE Trans. on Information Theory. 1996, vol. 42, iss. 4, pp. 1238–1240. doi: 10.1109/18.508848
27. Canteaut A., Charpin P., Dobbertin H. Binary m-Sequences with Three-Valued Crosscorrelation: a Proof of Welch’s Conjecture. IEEE Trans. on Information Theory. 2000, vol. 46, iss. 1, pp. 4–8. doi: 10.1109/18.817504
28. Hollmann H. D. L., Xiang Q. A Proof of the Welch and Niho Conjectures on Crosscorrelations of Binary m-Sequences. Finite Fields and Their Applications. 2001, vol. 7, iss. 2, pp. 253–286. doi: 10.1006/ffta.2000.0281
29. Helleseth T. On the Crosscorrelation of m-Sequences and Related Sequences with Ideal Autocorrelation. Sequences and Their Applications – SETA’01. 2001, Bergen. London, Springer, 2002, pp. 34–45. doi: 10.1007/978-1-4471-0673-9_3
30. Hertel D. Cross-Correlation Properties of Perfect Binary Sequences. Proc. 2004 Inter. Conf. on Sequences and Their Applications – SETA’04. Seoul, Korea, 2004. Berlin, Springer, 2005, pp. 208–219. (LNCS, vol. 3486).
31. Yu N. Y., Gong G. Crosscorrelation Properties of Binary Sequences. Sequences and Their Applications – SETA 2006. Lecture Notes in Computer Science, 2006, vol. 4086. Berlin, Heidelberg, Springer, 2006, pp. 104– 118. (LNCS, vol. 4086). doi: 10.1007/11863854_9
32. Games R. A. The Geometry of Quadrics and Correlations of Sequences (Corresp.). IEEE Trans. on Information Theory, 1986, vol. 32, iss. 3, pp. 423–426. doi: 10.1109/TIT.1986.1057184
33. Jackson W.-A., Wild P. R. Relations between Two Perfect Ternary Sequence Constructions. Design, Codes and Cryptography. 1992, vol. 2, iss. 4, pp. 325–322. doi: 10.1007/BF00125201.
34. Arasu K. T., Dillon J. F., Jungnickel D., Pott A. The Solution of the Waterloo Problem. J. Combin. Theory. Ser. A. 1995, vol. 71, iss. 2, pp. 316–331. doi: 10.1016/0097-3165(95)90006-3
35. Jungnickel D., Pott A. Perfect and Almost Perfect Sequences. Discrete Appl. Math. 1999, vol. 95, iss. 1–3, pp. 331–359. doi: 10.1016/S0166-218X(99)00085-2
36. Boztas S., Parampalli U. Nonbinary sequences with perfect and nearly perfect autocorrelations. 2010 IEEE Inter. Symp. on Information Theory. 13–18 June 2010, Austin, TX, USA. Piscataway, IEEE, 2010, pp. 1300–1304. doi: 10.1109/ISIT.2010.5513729
37. Arasu K. T., Dillon J. F. Perfect Ternary Arrays. Difference Sets, Sequences and Their Correlation Properties (Bad Windsheim, 1998). Dordrecht, Kluwer Acad. Publ., 1999, pp. 1–15. (NATO ASIC, vol. 542). doi: 10.1007/978-94-011-4459-9_1
38. Arasu K. T. Sequences and Arrays with Desirable Correlation Properties. NATO Science for Peace and Security Series. D: Information and Communication Security. Vol. 29: Coding Theory and Related Combinatorics. 2011, pp. 136–171. doi: 10.3233/978-1-60750-663-8-136
39. Antweiler M., Bomer L., Luke H. D. Perfect Ternary Arrays. IEEE Trans. on Information Theory. 1990, vol. 36, iss. 3, pp. 696–705. doi: 10.1109/18.54895
40. Krengel E. I. New Polyphase Perfect Sequences with Small Alphabet. Electron. Lett. 2008, vol. 44, no. 17, pp. 1013–1014. doi: 10.1049/el:20081401
41. Krengel E. I. Construction of New Perfect Ternary Sequences. Proc. of 19th Intern. Conf. on Digital Signal Processing (DSPA-2017), 29–31 March, 2017, Moscow. Institute of Control Sciences RAS. M., 2017, pp. 61–65 (in Russ.)
42. Krengel E. I. Periodic Ideal Ternary Sequence Generator. Pat. RU 2665290 C1, Priority date 2017-08-17 (in Russ.)
43. Yang Y., Gong G., Tang X. H. Odd Perfect Sequences and Sets of Spreading Sequences with Zero or Low Odd Periodic Correlation Zone. Proc. 2010 Inter. Conf. on Sequences and Their Applications (SETA 2012). 4–8 June 2012, Waterloo, Canada. Berlin, Springer, 2012, pp. 1–12. (LNCS, vol. 7280). doi: 10.1007/978-3-642-30615-0_1
44. Yang Y., Tang X.H., Gong G. New Almost Perfect, Odd Perfect, and Perfect Sequences from Difference Balanced Functions with d-Form Property. Advances in mathematics on communication. 2017, vol. 11, no. 1, pp. 67–76. doi: 10.3934/amc.2017002
45. Ipatov V. P., Kornievskii V. I., Kornilov O. I., Platonov V. D. Device for Determining the Two-Digit Nature of the Elements of the Final Feld. Pat. SU 1244658 A1. Priority date 1984-01. (in Russ.)
Review
For citations:
Krengel E.I. Retrospective Review of Perfect Ternary Sequences and Their Generators. Journal of the Russian Universities. Radioelectronics. 2019;22(4):6-17. https://doi.org/10.32603/1993-8985-2019-22-4-6-17
Views:
1107
Email this article 