Ретроспективный обзор троичных последовательностей с идеальной периодической автокорреляцией и устройств их генерации

Введение. Идеальные многофазные унимодулярные последовательности, т. е. последовательности с идеальной периодической автокорреляцией и единичной амплитудой символов, широко используются в современной радиосвязи и радиолокации. Особое место среди них занимают идеальные троичные последовательности (ИТП) с элементами {–1, 0, 1}. ИТП достаточно многочисленны, а их длина в отличие от идеальных двоичных последовательностей не ограничена сверху. Известен обзор ИТП, сделанный Фаном и Дарнеллом в 1996 г. Однако за прошедшие два десятилетия были открыты новые многочисленные семейства ИТП, установлены связи между ИТП и циркулянтными взвешенными матрицами, получены теоремы о существовании ИТП с определенными параметрами. Поэтому возникла потребность в новом современном обзоре известных на сегодня ИТП.

Цель работы. Обзор современных ИТП предназначен для разработчиков радиоэлектронных систем, в которых используются идеальные последовательности.

Материалы и методы. Рассмотрены и проанализированы отечественные и зарубежные источники информации (книги, журнальные статьи, труды конференций, патенты). Поиск осуществлялся в сети Интернете по ключевым словам с использованием Интернет-ресурсов Yandex и Google, а также в цифровых электронных библиотеках (Российской Государственной библиотеке (РГБ), IEEE Xplore Digital Library), в материалах конференций (Цифровая Обработка Сигналов и ее Применение (DSPA), Sequences and Their Applica-tions (SETA), и др.).

Результаты. Наряду с решением информационно-библиографической задачи в обзоре показана взаимосвязь полученных в разное время ИТП, их эквивалентность циркулянтным взвешенным матрицам, а также рассмотрены устройства генерации известных семейств ИТП (Ипатова, Хохолдта-Джастесена и др.).

Заключение. Представлен ретроспективный обзор ИТП; рассмотрены генераторы известных семейств ИТП. Результаты исследования актуальны для применения в современных системах радиосвязи и радиолокации, в частности в CW- и LPI-радарах.

1. Ипатов В. П. Периодические дискретные сигналы с оптимальными корреляционными свойствами. М.: Радио и связь, 1992. 151 с.

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 Lett. 1992. Vol. 28, № 9. P. 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, № 1. P. 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 Sept., 1996. Piscataway: IEEE, 1996. P. 82–85.

8. Кренгель Е. И. Новые идеальные 4- и 8-фазные последовательности с нулями // Радиотехника. 2007. № 5. С. 3–7.

9. Levanon N., Freedman A. Periodic Ambiguity Function of CW Signals with Perfect Periodic Autocorrelation // IEEE Trans. on Aerosp. and Electron. Syst. 1992. Vol. AES-28, № 2. P. 387–395. doi:10.1109/7.144564

10. Chang J. A. Ternary Sequences with Zero-correlation // Proc. of the IEEE. 1997. Vol. 55, № 7. P. 1211–1213. doi: 10.1109/PROC.1967.5793

11. Green D. H., Kelsch R. G. Ternary pseudonoise sequences // Electronics Lett. 1972. Vol. 8, № 5. P. 112– 113. doi: 10.1049/el:19720081

12. Moharir P. S. Generalized PN sequences // IEEE Trans. on Inform. Theory. 1977. Vol. IT-23, iss. 6. P. 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. P. 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. P. 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. URL: http://digitallibrary.usc.edu/cdm/ref/collection /p15799coll37/id/51150 (дата обращения: 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, № 4. P. 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. P. 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 Inform. Theory. 1979. Vol. IT-25, iss. 1. P. 94–97. doi: 10.1109/TIT.1979.1055998

19. Ипатов В. П. Троичные последовательности с идеальными периодическими автокорреляционными свойствами // Радиотехника и электроника. 1979. Т. 24, № 10. С. 2053–2057

20. Hoholdt T., Justesen J. Ternary sequences with perfect periodic autocorrelation (Corresp.) // IEEE Trans. on Inform. Theory. 1983. Vol. IT-29, iss. 4. P. 597–600. doi: 10.1109/TIT.1983.1056707

21. Ипатов В. П., Платонов В. Д., Самойлов И. М.

22. Новый класс троичных последовательностей с идеальными периодическими автокорреляционными свойствами// Изв. вузов СССР. Сер. Математика. 1983. № 3. С. 47–50.

23. Камалетдинов Б. Ж. Троичные последовательности с идеальными периодическими автокорреляционными свойствами // Радиотехника и электроника. 1987. Т. 32, № 1. С. 77–82.

24. Golomb S. W., Gong G. Signal Design for Good Correlation: for Wireless Communication, Cryptography, and Radar. Cambridge: Cambridge University Press, 2005. 455 p.

25. Games R. A. Crosscorrelation of m-Sequences and GMW Sequences with the Same Primitive Polynomial // Discrete Applied Mathematics. 1985. Vol. 12, iss. 2. P. 139–146. doi: 10.1016/0166-218X(85)90067-8

26. Antweiler M. Cross-correlation of p-ary GMW Sequences // IEEE Trans. on Inform. Theory. 1984. Vol. IT-40, iss. 4. P. 1253–1261. doi: 10.1109/18.335941

27. Cusick T. W., Dobbertin H. Some New Three-Valued Crosscorrelation Functions for Binary m-Sequences // IEEE Trans. on Inform. Theory. 1996. Vol. 42, iss. 4. P. 1238–1240. doi: 10.1109/18.508848

28. Canteaut A., Charpin P., Dobbertin H. Binary m-Sequences with Three-Valued Crosscorrelation: a Proof of Welch’s Conjecture // IEEE Trans. on Inform. Theory. 2000. Vol. 46, iss. 1. P. 4–8. doi: 10.1109/18.817504

29. 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. P. 253–286. doi: 10.1006/ffta.2000.0281

30. 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. P. 34–45. doi: 10.1007/978-1-4471-0673-9_3

31. 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. P. 208–219. (LNCS, vol. 3486).

32. 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. P. 104–118. (LNCS, vol. 4086). doi: 10.1007/11863854_9

33. Games R. A. The Geometry of Quadrics and Correlations of Sequences (Corresp.) // IEEE Trans. on Inform. Theory. 1986. Vol. 32, iss. 3. P. 423–426. doi: 10.1109/TIT.1986.1057184

34. Jackson W.-A., Wild P. R. Relations between Two Perfect Ternary Sequence Constructions // Design, Codes and Cryptography. 1992. Vol. 2, iss. 4. P. 325–322. doi: 10.1007/BF00125201

35. The Solution of the Waterloo Problem / K. T. Arasu, J. F. Dillon, D. Jungnickel, A. Pott // J. Combin. Theory. Ser. A. 1995. Vol. 71, iss. 2. P. 316–331. doi: 10.1016/0097-3165(95)90006-3

36. Jungnickel D., Pott A. Perfect and Almost Perfect Sequences // Discrete Appl. Math. 1999. Vol. 95, iss. 1–3. P. 331–359. doi: 10.1016/S0166-218X(99)00085-2

37. Boztas S., Parampalli U. Nonbinary sequences with perfect and nearly perfect autocorrelations // 2010 IEEE Inter. Symp. on Inform. Theory. 13–18 June 2010, Austin, TX, USA. Piscataway: IEEE, 2010. P. 1300–1304. doi: 10.1109/ISIT.2010.5513729

38. Arasu K. T., Dillon J. F. Perfect Ternary Arrays // Difference Sets, Sequences and Their Correlation Properties (Bad Windsheim, 1998). Dordrecht: Kluwer Acad. Publ., 1999. P. 1–15. (NATO ASIC, vol. 542). doi: 10.1007/978-94-011-4459-9_1

39. 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. P. 136–171. doi: 10.3233/978-1-60750-663-8-136

40. Antweiler M., Bomer L., Luke H. D. Perfect Ternary Arrays // IEEE Trans. on Inform. Theory. 1990. Vol. 36, iss. 3. P. 696–705. doi: 10.1109/18.54895

41. Krengel E. I. New Polyphase Perfect Sequences with Small Alphabet // Electron. Lett. 2008. Vol. 44, № 17. P. 1013–1014. doi: 10.1049/el:20081401

42. Кренгель Е. И. Построение новых идеальных троичных последовательностей // Сб. докл. 19-й междунар. конф. "Цифровая обработка сигналов и ее применение". 29–31 марта 2017, Москва / ИПУ РАН. М., 2017. С. 61–65.

43. Пат. RU 2665290 C1 МПК G06F 7/58 (2006.01). Генератор периодических идеальных троичных последовательностей / Е. И. Кренгель; опубл. 28.08.2018. Бюл. № 25.

44. 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. P. 1–12. (LNCS, vol. 7280). doi: 10.1007/978-3-642-30615-0_1

45. 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, № 1. P. 67–76. doi: 10.3934/amc.2017002

46. Пат. SU 1244658 A1 G06F 7/00 (2000.01). Устройство для определения двузначного характера элементов конечного поля/ В. П. Ипатов, В. И. Корниевский, О. И. Корнилов, В. Д. Платонов; опубл. 15.07.1986. Бюл. № 26.