SYNCHRONIZATION OF M-SEQUENCES AND GOLD PSEUDORANDOM SEQUENCES BASED ON THE FAST HADAMARD TRANSFORM

Sy. D. Vu
Le Quy Don Technical University, HaNoi, VietNam
daovs@viettel.com.vn

DOI: 10.36724/2664-066X-2026-12-3-2-29

SYNCHROINFO JOURNAL. Volume 12, Number 3 (2026). P. 2-29.

Abstract

Methods have been developed for constructing circulant matrices for any maximal-length sequence (MLS) based on the automorphic multiplicative groups of an extended Galois field – a field constructed using the same irreducible primitive polynomial that defines the original MLS. This approach reveals new ways to transform the circulant matrices of an MLS into a matrix of Walsh functions, ordered according to the powers of the field’s primitive element. It is demonstrated, for the first time, that – depending on the initial transformation conditions – any set of cyclic shifts of an MLS (where each shift is offset by a single symbol relative to the others) can be mapped to a sequence of consecutive rows within an ordered Walsh function matrix. This finding facilitates the simplification of MLS synchronization algorithms, particularly when the range of possible cyclic shifts is known – a significant advantage for sequences with long repetition periods. Furthermore, it reduces the computational complexity of processing algorithms when operating within a truncated Walsh-Hadamard basis. Based on an analysis of the structures of isomorphic multiplicative groups within extended Galois fields, it has been established that any cyclic shift of a Gold pseudorandom sequence can be transformed into a function belonging to the complete set of analogues of Rademacher functions for a given dimension. This insight has enabled the development of a new fast synchronization algorithm for Gold sequences, which relies on computing their discrete convolution via a fast spectral transform within a truncated Walsh-Hadamard basis.

Keywords:  noise-like signals, vector-matrix multiplication, Rademacher functions, periodic autocorrelation function, Galois field

References

[1] Wu Shi Dao, “Complex signal detection and vector-matrix multiplication algorithm,” Synchroinfo Journal 2026, vol. 12, no. 2, pp. 8-25.

[2] S.F. Gorgadze, Sh.D. Vu, A.V. Ermakova, “Synchronization of M-sequences based on the fast Hadamard transform,” Radio Engineering and Electronics. 2024. Vol. 69. No. 2, pp. 122-136.

[3] S. F. Gorgadze, Sh.D. Vu, A. V. Ermakova, “Synchronization of Gold Sequences Based on Fast Transformation in a Truncated Basis of Walsh-Hadamard Functions,” Radio Engineering and Electronics. 2024. Vol. 69. No. 2, pp. 137-145.

[4] Sh.D. Vu, S.F. Gorgadze, “A device for accelerated acquisition of a noise-like signal,” Information Society Technologies. Proceedings of the XVI International Industry-Specific Scientific and Technical Conference. Moscow, 2022, pp. 88-90.

[5] S.F. Gorgadze, Sh.D. Vu, “Certificate of State Registration of a Computer Program No. 2024663135 (Russian Federation). Program for constructing circulant matrices for M-sequences and Gold codes based on multiplicative groups of extended Galois fields,” applicant and copyright holder: MTUCI. No. 2024661989; filed May 28, 2024; published June 4, 2024.

[6] V. P. Ipatov, “Wideband Systems and Code Division Multiple Access: Principles and Applications,” Moscow: Tekhnosfera, 2007. 487 p.

[7] W. Peterson, E. Weldon, “Error-Correcting Codes,” Moscow: Mir, 1976. 593 p.

[8] M. B. Sverdlik, “Optimal Discrete Signals,” Moscow: Sovetskoye Radio, 1975. 200 p.

[9] V. M. Smolyaninov, “Discrete Multiplicative Group Signals and Their Connection to Group Codes,” Radio Engineering and Electronics. 1985. Vol. 30. No. 12, pp. 2391-2394.

[10] V.V. Losev, E.B. Brodskaya, V.I. Korzhik, “Search and Decoding of Complex Discrete Signals,”; ed. by V.I. Korzhik. Moscow: Radio i Svyaz, 1988. 224 p.

[11] V.V. Losev, V.D. Dvornikov, “Recognition of Address Sequences Using Fast Transforms,” Radio Engineering and Electronics. 1983. No. 8, pp. 15-40.

[12] A. M. Trakhtman, V. A. Trakhtman, “Fundamentals of the Theory of Discrete Signals on Finite Intervals,” Moscow: Sovetskoye Radio, 1975. 205 p.

[13] S. F. Gorgadze, “Asymmetric Modifications of the Generalized Fast Fourier and Fourier-Hadamard Transforms,” Radio Engineering and Electronics. 2005. Vol. 50. No. 3, pp. 302-308.

[14] Y. Be’ery, J. Snyders, “A recursive Hadamard transform optimal soft decoding algorithm,” Journal of Algebraic and Discrete Methods. 1987. Vol. 8. No. 4, pp. 778-789.

[15] V. M. Smolyaninov, L. E. Nazarov, “Specifics of spectral analysis in the recognition of discrete signals based on binary codes,” Radio Engineering and Electronics. 1988. Vol. 32. No. 11, pp. 2341-2347.

[16] V. M. Smolyaninov, L. E. Nazarov, “Optimization of the spectral analysis algorithm for the recognition of discrete multiplicative signals,” Radio Engineering and Electronics. 1989. Vol. 35. No. 12, pp. 2651-2653.

[17] V.Y. Mikhaylov, R.B. Mazepa, “Estimation of the Features of Application of the M-Sequences Subset with the Possibility of Joint Processing. DOI: 10.1109/SYNCHROINFO 51390.2021.9488414,” 2021 Systems of Signal Synchronization, Generating and Processing in Telecommunications (SYNCHROINFO). 2021. P. 1-6.

[18] V.S. Kuznetsov, I.V. Shevchenko, A.S. Volkov, A.V. Solodkov, “Generation of Gold code ensembles for direct-sequence spread-spectrum systems,” Proceedings of the Moscow Aviation Institute (MAI). 2017. No. 96. http://trudymai.ru/.

[19] V.S. Kuznetsov, K.A. Mordasov, “Fast decoding based on passive matched filtering of long pseudorandom codes,” Proceedings of Higher Educational Institutions. Electronics. 2010. No. 1 (81), pp. 57-62.

[20] L.E. Varakin, “Communication Systems Using Noise-Like Signals,” Moscow: Radio i Svyaz, 1985. 384 p.

[21] V.Y. Mikhaylov, R.B. Mazepa, “Using transformations in Galois fields for fast delay-based searching of Gold sequences,” T-Comm. 2018. Vol. 12, no. 4. P. 4-9.