Discrete Signals with Special Correlation Properties

Abstract

The methods of synthesis of discrete signals are analyzed with the special cross-correlation properties: m- sequences, signals of Legendre, Barker, Paley-Plotkin, Gold, small and large set of Kasami. Comparative researches of properties of the formed discrete signals are conducted. Separate direction develops in development of methods of forming of discrete signals, that is based on the use of algebraic and structural properties of circular shifts of group codes. It is shown that offered approach allows forming the great numbers of discrete sequences, ensemble and cross-correlation properties of that are set by the properties of the corresponding group controlled from distance, structural and cyclic.

Keywords

• Discrete signals cross-correlation and ensemble properties group codes circular shifts

-

The effective functioning of digital communication networks with providing plural access on the technology of code channel separation directly depends on ensemble, cross-correlation and structural properties of the formed discrete signals [ 1-3 ]. It is special it is important at the construction of perspective digital communication of fifth (5G) and sixth (6G) generation networks [ 4 ].

The perspective direction of researches is the development of methods of synthesis

of discrete signals with the special correlation properties [ 5-30 ]. The values of lateral ejection of the function of correlation for such signals are determined by strict analytical correlations and directly related to structural and group properties of ensembles of discrete sequences [ 5-9 ]. In particular, such signals include [ 5–30 ]: m-sequences, Legendre, Barker, Paley-Plotkin, Gold signals, a small and large number of Kasami and many others. At the same time, the main disadvantage of such methods is the small power of the ensembles of the formed sequences. In this sense, the most promising methods are the synthesis of large ensembles of discrete signals with a multilevel auto- and cross-correlation function [ 16 ].

In this paper, the analysis and comparative studies of methods of synthesis of discrete signals with special correlation properties are carried out. Theoretically, synthesis methods based on the cross-section of circular shifts of the group code are justified, which allow forming a set of sequences with predetermined distance properties and algebraically construct large ensembles of discrete signals with a multilevel function of auto- and cross-correlation. 2

Analysis of the known methods of synthesis of discrete signals with the special correlation properties The most development to date was got by the methods of synthesis of discrete signals, based on the use of recurrent transformations and corresponding linear and nonlinear recurrent sequences [ 5-30 ]. Procedures of forming of such sequences easily will be realized with the use of the simplest switch charts with shift registers.

Linear recurrent sequences are formed with the use of shift registers with linear

feedback (LFSR) and at the corresponding choice of the function of feedback allow to provide the maximal period of the formed sequences [ 5-9 ]. In literature, such signals got the name of linear recurrent sequences of a maximal period (MLRS) or m- sequences. On their basis, many other classes of signals are formed: sequences of Legendre, Paley-Plotkin, a Barker signal and many other.

The results of a comparative analysis of some methods for synthesizing signals

with special correlation properties are given in Table 1. The comparison was made according to the following indicators: the period length n and the power М of discrete signals, the maximum value of the lateral lobe module of the correlation function  .

The analysis showed that the lateral ejections of the correlation function of the considered signals take finite, previously known values, which allows them to be used at various stages of digital communication, including for channel synchronization and in radio-location. The main disadvantage is the small capacity of the ensembles of the formed sequences. For example, the number of MLRS, Legendre, Paley-Plotkin and other sequences is determined by the number of irreducible polynomials (Euler function), which determine the rule for the formation of sequences. Improved ensemble properties are possessed by Gold's sequences, small and large sets of Kasami sequences. The power of the ensembles of such signals is significantly increased. The lateral lobes of the correlation function  for these sequences are also increased, but with an increase in the length of the sequences n the loss in the correlation properties is insignificant. Therefore, the construction of large ensembles of discrete signals is a promising direction for further research.

Ensemble and correlation characteristics of some discrete signals with special properties

Signal class m-sequences

Legendre Sequences

Legendre sequences with

m  2 , Barker signals

Legendre Sequences,

m  2

Paley-Plotkin signals

Gold signals

Gold signals

Small set of Kasami Large set of Kasami

n 2m 1, m  Z  n  ( pm 1) , p, m  Z 

p 1 , р = 3, 5, 7, 11, 13

p 1 , p  Z  , р  3, 5, 7, 11, 13

p , p  Z  m  2 p  1, p  Z  m  2 p , p  Z  2m 1, 2m 1, 2m 1, 2m 1, m  2 p , p  Z  m  2 p , p  Z 

М  (2m 1) / 2m M   ( pm 1) / 2m p  1 ( p2 1) 8 8 p  1 ( p2 1)  ( p 1)  ( p 1) p 2m 1 2m 1 2m/2 2m/2 (2m/2 1)        

1 2m 1 pm1

n   1 / p   1 / p   1 / p       1  2(m1)/2

2m 1 1  2(m2)/2 2m 1 1  2m/2 2m 1 1  2(m2)/2 2m 1

The most important, in this sense, are methods based on the use of algebraic and structural properties of group codes. Thus, in [ 16, 29, 30 ], it was shown that the suborthogonal discrete signals, the three-level Gold signals are a special case of n-level discrete sequences formed by the section of cyclic orbits of a group binary code, and can be analytically formalized using the mathematical apparatus of the theory finite fields and, in particular, the theory of rings of polynomials. 3

Algebraic and structural properties of circular shifts of group codes The proposed approach to the formation of discrete signals with a multilevel correlation function is based on the use of the algebraic and structural properties of cyclic orbits of group codes over finite fields, as well as the procedure for selecting the corresponding discrete sequences [ 8, 16 ]. Consider the algebraic structure of a finite field and the cyclic orbits contained in it. We will research the algebraic and structural properties of cyclic orbits of group codes to form discrete sequences with special properties.

We fix a finite field GF q  , consider the vector space GF n q  as a set of n - sequences of elements from GF q  with component-wise addition and multiplication by a scalar. A linear n, k, d  code V is a subspace GF k  q in space GF n q  , i.e. nonempty set of n-sequences (code words) over GF q  , k is the dimension of a linear subspace, d is the minimum code distance (the minimum weight of a nonzero code word). A cyclic code is a special case of a subspace that has the additional property of cyclicity. Each vector from GF n q  can be represented by a polynomial in a formal variable х of degree not higher than n – 1. The components of the vector are identified with the coefficients of the polynomial. The set of polynomials has the structure of a vector space, identical to the structure of the space GF n q  , as well as the structure of the ring of polynomials GF  q x  xn 1 . In the ring of polynomials, the multiplication over polynomials is defined: p1  x  p2  x  Rxn 1  p1  x   p2  x , where Rb a is the remainder of the polynomial a divided by the polynomial b . The cyclic shift on  0,..., n 1 elements in terms of polynomial algebra can be written as: x  p  x  Rxn 1  x  p  x  . (1) iqs 

If the code words n, k, d  of a code over GF q  are given in the form of polynomials, then code V is a subset of the ring GF  q x  xn 1 . The code V is cyclic if, along with the code word С  x it also contains the polynomial x  С  x . The only nonzero given polynomial g  x of the smallest degree r  n  k uniquely defines n, k, d  the cyclic code over GF q  and is denoted by the generating polynomial, moreover g (x)   (x   i ) , where  i  GF  qm  . It is connected with the i check polynomial h  x

by the relation g  x  h  x  xn 1 , or, equivalently, Rxn 1  g  x   h  x  0 .

Consider the structure of a finite field GF  qm  , as a set of polynomials of degree  m with coefficients from GF q  , i.e.

polynomial ring structure GF  q  x /  xm 1 . This ring with modulo irreducible polynomial operations is an extended Galois field GF  qm  . Such a field consists of a set of classes of conjugate elements  , s  0,1,..., mi 1 , where mi is the smallest natural number, such that equality holds [ 8 ]:

iqmi  i mod qm 1 .

The algebraic structure of a finite Galois field is given in table 2. Each class of conjugate elements specifies (through the roots) the minimal polynomial fi  x  . The product of all minimal polynomials fi  x  of a finite field GF  qm  defines the polynomial (xqm 1 1) , i.e. we have the equality: (xqm 1 1) 

 i{0,...,qm 1} fi  x 

 i{0,...,qm 1}  x  i  , where  is a primitive element of the field GF (qm ) , whence follows:    mj  g  x  LCM  j f j  x   LCM  j s0  x  jqs      ,    h  x   xn 1    mi  g  x  LCM  ij fi  x   LCM  ij s0    x  iqs      ,    where LCM is least common multiples.  (x  1)  (x  q )  (x  q2 )  (x  qm ) fi (x)  fiq (x)  fiq2 (x)  ...  fiqm (x)   (x  i )  (x  iq )  (x  iq2 )  (x  iqm )

Let us consider the structure of the group n, k, d  code V over GF q  from the

point of view of the cyclic properties of the sequences that form it. We will use the concept of a cyclic orbit V is a set of sequences with elements from GF q  , equivalent to each other with respect to the cyclic shift operation, i.e. many such:

Ci  c0i , c1i ,...cni1  , cvi  GF q  and C j  c0j , c1j ,...cnj1  , cvj  GF q  , that equality holds: c0i , c1i ,...cni1   cj modn , cj 1modn ,...cj n1modn  , (2) for any  0,..., n 1 .

Expression (1) using (2) is expressed in terms of polynomial algebra:

pi  x  x  p j  x  Rxn 1  x  p j  x , pi  x  c0i  c1i x  ...  cni1xn1 , p j  x  c0j  c1j x  ...  cnj1xn1 .

Consider the set W  GF n (q) of all n- sequences with elements from GF q  ,

which form the so-called "full code". The structure of a set is equivalent to a vector space GF q  with componential addition and multiplication by a scalar.

We divide the entire set W into subsets of orbits V0 ,V1,,VL , each of which con

tains a set of sequences equivalent to each other in relation to the cyclic shift operation. Thus, we obtain the decomposition of the vector space GF q  into sets of nonintersecting orbits (Fig. 1). In Fig. 1 Si, j  GF n (q), i  0,, L, j 1,, Zi is schematically denoted by n- sequences as elements of the set W . All Si, j are grouped on the basis of equivalence in relation to the cyclic shift operation. Each group is a set Vi , all elements of the set Vi form i orbit of a set. W . It is also obvious that each sequence Si, j can be represented in the form (2) as some sequence CL in the notations introduced above. The power of the set Vi (the number of elements of the i orbit of the set W) is equal to Zi . Obviously, for a set W formed by n- sequences with elements from GF n (q) , the power of the set Vi for an arbitrary i  0,..., L does not exceed n, i.e. Zi  n, i  0,..., L , the number of nonzero orbits L is bounded below by the following value:

L  .

Under the zero is understood the orbit V0 , consisting of one zero sequence So,z0 ( a

sequence consisting of only zero elements GF q  ), the corresponding number of sequences of the orbit Z0  1 . i.e. nonzero components of the weight spectrum A(w)  0 ( except for one zero sequence A(0)  1 ) are concentrated in the weight range W  d ,..., n .

Taking into account the above considerations, the diagram for decomposing the

vector space GF n (q) into sets of disjoint cyclic orbits Vi , i  0,..., L is represented as a diagram in Fig. 2.

V

S0,1

V0,w=0 S1,1 S1,2 S1,3 ... S1,z1 V1 S2,1 S2,2 S2,3 ... S2,z2 V2 S3,1 S3,2 S3,3 ... S3,z1 V3

w=d S4,1 S4,2 S4,3 ... S4,z2 V4

w=d+1 S5,1 S5,2 S5,3 ... S5,z2 V5

...

Si,1 Si,2 Si,3 ... Si,zi Vi w ≠ 0 Si+1,1 Si+1,2 Si+1,3 ... Szii++11, Vi+1 Si+2,1 Si+2,2 Si+2,3 ... Szi2++11, Vi+2

w ≠ 0 Si+3,1 Si+3,2 Si+3,3 ... Szi3++11, Vi+3 Si+4,1 Si+4,2 Si+4,3 ... Szi4++11, Vi+4

...

Sj,1 Sj,2 Sj,3 ... Sj,zj Vj

...

SL,1 SL,2 SL,3 ... SL,z1 VL w ≠ 0 w ≠ 0

W

Obviously, the «complete code» W is represented as a union of a finite number of

disjoint orbit-sequences of fixed weight, equivalent to each other with respect to the cyclic shift operation. The code V as a subset of the space GF n (q) is the union of a finite number of orbits, and the weights of the sequences of the orbits are determined exclusively by the weight spectrum, i.e. relevant w  0 .

The number of orbits of a fixed weight is also determined by the weight spectrum

of the code, i.e. the number of sequences in these orbits. Thus, the number of orbits of a weight w  0 of a code V with a weight spectrum (4) is bounded below by an expression (by analogy with (3)):

L(w) 

A(w) n .

(5)

So, the group code is uniquely defined by the leaders (representatives) of its cyclic orbits.

4

Conclusions The efficiency of functioning of digital communication systems with the provision of multiple access on the technology of code division of channels directly depends on ensemble, correlation and structural properties of used discrete signals. Promising in this sense are methods for the synthesis of discrete signals with special correlation properties, the magnitudes of lateral ejections of the correlation function of which are determined by strict analytical relations and are directly related to the structural properties of ensembles of discrete sequences.

The analysis of methods of synthesis of discrete signals with special correlation properties has shown that application of formed sequences allows providing the set level of noise immunity of communication The lateral ejections of function of correlation of discrete signals with the special properties take on final beforehand known values, that allows to use them on the different stages of digital communication At the same time, the main disadvantage of such methods is the low power of the ensembles of formed sequences. So, for example, the number of MLRS, sequences of Legendre, Paley-Plotkin of and other is determined by the number of irreducible polynomials that define the rule for the formation of sequences. The improved ensemble properties are possessed by sequences Golda, small and large set of sequences of Kasami. Their construction is based on the use of the developed mathematical vehicle of the theory of the finite fields and, in particular, the theory of polynomial rings, which allows us to connect the correlation properties of the formed sequences with the group and structural properties of signal ensembles. The most perspective in this sense are the methods of synthesis based on the cross-section of circular shifts of the group codes.

Research of cyclic properties of group codes and presentation of them through the combination of circular shifts allowed to ground the rule of forming of discrete signals as leaders of corresponding circular shifts. Due to the cross-section of circular shifts, it is possible to form a set of sequences, the ensemble and correlation properties of which are determined by the distance, structural and cyclic properties of the corresponding group codes. The further researches can be focused on using in some different other areas [ 31-34 ]. 34. Kavun, S., Zamula, A., Mikheev, I.: Calculation of expense for local computer networks.

In: Scientific-Practical Conference Problems of Infocommunications. Science and Tech

nology (PIC S&T), 2017 4th International, Kharkiv, Ukraine, 2017, pp. 146–151. (2017) doi:10.1109/INFOCOMMST.2017.8246369

References

1. Popoff , A. : Fundamentals of Signal Processing in Metric Spaces with Lattice Properties: Algebraic Approach . CRC Press ( 2017 )

2. Benedetto , S. , Biglieri , E.: Principles of Digital Transmission: With Wireless Applications" , Springer ( 2002 )

3. Miao , G. , Zander , J. , Sung , K.W. , Slimane , B. : Fundamentals of Mobile Data Networks . Cambridge University Press ( 2016 )

4. David , K. , Berndt , H.: 6G Vision and Requirements: Is There Any Need for Beyond 5G? IEEE Vehicular Technology Magazine . ( 2018 ) doi:10.1109/mvt. 2018 .2848498

5. Barker , R.H.: Group Synchronizing of Binary Digital Systems" . Communication Theory. London: Butterworth ( 1953 )

6. Zierler , N.: Legiendre sequences . Armed Services Technical Information Agency Arlington Hall Station, Achusetts Institute of Technology Lincoln Laboratory, Group Report 34- 71 ( 1958 )

7. Plotkin , M. : Binary codes with specified minimum distance . IRE Transactions on Information Theory , 1960 , vol. 6 , pp. 445 - 450 . ( 1960 ) doi:10.1109/TIT. 1960 .1057584

8. MacWilliams , F.J. , Sloane , N.J.A. : The Theory of Error-Correcting Codes . North Holland Publishing Co. ( 1977 )

9. Matter , F. , Sloane , N.J.A. : A Handbook of Integer Sequences , Academic Press ( 1973 )

10. Borwein , P. , Mossinghoff , M.J.: Barker sequences and flat polynomials . In James McKee; Chris Smyth. Number Theory and Polynomials. LMS Lecture Notes . 352 . Cambridge University Press ( 2008 )

11. Naumenko , N.I. , Stasev , Y.V. , Kuznetsov , A.A. : Methods of synthesis of signals with prescribed properties . Cybernetics and Systems Analysis , 2007 , vol. 43 ( 3 ), pp. 321 - 326 . ( 2007 ) doi:10.1007/s10559-007-0052-8

12. Stasev , Y.V. , Kuznetsov , A.A. , Nosik , A.M.: Formation of pseudorandom sequences with improved autocorrelation properties . Cybernetics and Systems Analysis , 2007 , vol. 43 ( 1 ), pp. 1 - 11 . ( 2007 ) doi:10.1007/s10559-007-0021-2

13. Leung , K.H. , Schmidt , B. : The Field Descent Method . Designs, Codes and Cryptography, 2005 , vol. 36 ( 2 ), pp. 171 - 188 . ( 2005 ) doi:10.1007/s10623-004-1703-7

14. Hedayat , A.S. , Sloane , N.J.A. , Stufken , J.: Orthogonal Arrays. Theory and Applications . Springer-Verlag New York ( 1999 )

15. Sloane , N.J.A. , Plouffe , S.: The Encyclopedia of Integer Sequences . Academic Press, San Diego ( 1995 )

16. Karpenko , O. , Kuznetsov , A. , Sai , V. , Stasev , Y. : Discrete Signals with Multi-Level Correlation Function . Telecommunications and Radio Engineering , 2012 , vol. 71 ( 1 ), pp. 91 - 98 . ( 2012 ) doi:10.1615/TelecomRadEng.v71. i1 . 100

17. Amadei , M. , Manzoli , U. , Merani , M.L. : On the assignment of Walsh and quasiorthogonal codes in a multicarrier DS-CDMA system with multiple classes of users . Global Telecommunications Conference. GLOBECOM '02 . IEEE, Taipei, Taiwan, 2002 , vol. 1 , pp. 841 - 845 . ( 2002 ) doi:10.1109/GLOCOM. 2002 .1188196

18. Arambepola , B. , Partington , K.C. : Walsh-Hadamard transform for complex-valued signals . Electronics Letters , 1992 , vol. 28 ( 3 ), pp. 259 - 261 . ( 1992 ) doi:10.1049/el:19920160

19. Zulfikar , Abbasi, S.A. , Alamoud , A.R.M. : A Novel Complete Set of Walsh and Inverse Walsh Transforms for Signal Processing . In: 2011 International Conference on Communication Systems and Network Technologies , Katra, Jammu, 2011 , pp. 504 - 509 . ( 2011 ) doi:10.1109/CSNT. 2011 .108

20. Gold , R.: Optimal binary sequences for spread spectrum multiplexing (Corresp.) . IEEE Transactions on Information Theory , 1967 , vol. 13 ( 4 ), pp. 619 - 621 . ( 1967 ) doi:10.1109/TIT. 1967 .1054048

21. Wojuola , O.B. : Cross-correlation index and multiple-access performance of Gold codes in a spread-spectrum system . In: 2018 20th International Conference on Advanced Communication Technology (ICACT) , Chuncheon-si Gangwon-do , Korea (South) , 2018 , pp. 764 - 768 . ( 2018 ) doi:10.23919/ICACT. 2018 .8323914

22. Gouda , M. , El-Hennawy , A. , Mohamed , A.E. : Detection of Gold Codes Using HigherOrder Statistics . In: 2011 First International Conference on Informatics and Computational Intelligence , Bandung, 2011 , pp. 361 - 364 . ( 2011 ) doi:10.1109/ICI. 2011 .65

23. Pereira , J.S. , da Silva , A.J.H.: M-ary mutually orthogonal complementary gold codes . In: 2009 17th European Signal Processing Conference , Glasgow, 2009 , pp. 1636 - 1640 . ( 2009 )

24. Huda , T.M.N. , Islam , S.F. : Correlation analysis of the gold codes and Walsh codes in CDMA technology . In: 2009 First Asian Himalayas International Conference on Internet, Kathmandu , 2009 , pp. 1 - 4 . ( 2009 ) doi:10.1109/AHICI. 2009 .5340345

25. Kasami , T. , Lin , S. , Peterson , W.W.: Some Results on Cyclic Codes Which Are Invariant under the Affine Group and Their Applications . INFORMATION AND CONTROL , 1968 , vol. 11 ( 5-6 ), pp. 475 - 496 . ( 1968 ) doi:10.1016/S0019- 9958 ( 67 ) 90691 - 2

26. Chandra , A. , Chattopadhyay , S. : Small Set Orthogonal Kasami codes for CDMA system . In: 2009 4th International Conference on Computers and Devices for Communication (CODEC) , Kolkata , 2009 , pp. 1 - 4 . ( 2009 )

27. Tsai , Y. , Li , X. : Kasami Code-Shift-Keying Modulation for Ultra-Wideband Communication Systems . IEEE Transactions on Communications , 2007 , vol. 55 ( 6 ), pp. 1242 - 1252 . ( 2007 ) doi:10.1109/TCOMM. 2007 .898859

28. Choi , J.H. , Chung , H.K. , Lee , H. , Cha , J. , Lee , H. : Code-Division Multiplexing Based MIMO Channel Sounder with Loosely Synchronous Codes and Kasami Codes . In: IEEE Vehicular Technology Conference , Montreal, Que., 2006 , pp. 1 - 5 . ( 2006 ) doi:10.1109/VTCF. 2006 .33

29. Kuznetsov , A.A. , Smirnov , A.A. , Sai , V.N. : Formation of discrete signals with a multilevel correlation function (in Russian) . Processing Systems Information, Kharkiv , 2011 , vol. 5 ( 95 ), pp. 50 - 60 . ( 2011 )

30. Stasev , Y. , Kuznetsov , A. , Sai , V. , Karpenko , O. : Discrete Signals with Multi-Level Correlation Function . Telecommunications and Radio Engineering , 2010 , vol. 71 ( 1 ), pp. 91 - 98 . ( 2010 ) doi:10.1615/TelecomRadEng.v71. i1 . 100

31. Kavun , S. : Conceptual fundamentals of a theory of mathematical interpretation . Int. J. Computing Science and Mathematics , 2015 , vol. 6 ( 2 ), pp. 107 - 121 . ( 2015 ) doi:10.1504/IJCSM. 2015 .069459

32. Kavun , S. : Indicative-geometric method for estimation of any business entity . Int. J. Data Analysis Techniques and Strategies , 2016 , vol. 8 ( 2 ), pp. 87 - 107 . ( 2016 ) doi: 10.1504/IJDATS. 2016 .077486

33. Zamula , A. , Kavun , S. : Complex systems modeling with intelligent control elements . Int. J. Model. Simul. Sci. Comput ., 2017 , vol. 08 ( 01 ). ( 2017 ) doi:10.1142/S179396231750009X