Linear codes invariant with respect to generalized shift operators V G Labunets1 and E Ostheimer2 1 Ural State Forest Engineering University, Sibirsky trakt 37, Ekaterinburg, Russia, 620100 2 Capricat LLC, Pompano Beach, Florida, US Abstract. The purpose of this paper is to introduce new linear codes with generalized symmetry. We extend cyclic and group codes in the following way. We introduce codes, invariant with respect to a family of generalized shift operators (GSO). In particle case when this family is a group (cyclic or Abelian), these codes are ordinary cyclic and group codes. They are invariant with respect to this group. We deal with GSO-invariant codes with fast code and encode procedures based on fast generalized Fourier transforms. The hope is that thesemore general structures will lead to larger classes of useful codes “good” properties. 1. Introduction Let F be a finite field. A block code of length N is a subset Cof F N , i.e., a collection of N length vectors with components from F . Most of the literature on block codes pertains to block codes over finite fields F = GF (q ) or finite rings F = GR (q ) , where q = p s and p is a prime. Although any subset forms a code, there are codes with more structure that are very useful and compose the majority of block codes in practice. A linear block code is a block code that is an F -subspace of the F -vector space F N . In addition to linearity, there are many structural properties that make for good codes. One of the most prevalent such structural properties is symmetry of code, that is described as invariance with respect to a group. Invariance (code symmetry), in many circumstances, leads to some nice encoding and decoding algorithms yet it is a very simple structure to describe. For these reasons, it is one of the most studied structural properties in coding theory. Definition 1 [1,2]. A cyclic block code C ⊂ F N of length N over a finite field F is a linear block code with the property that if (c0 , c1 ,..., cN − 2 , cN −1 ) ∈ C then (cN −1 , c0 ,..., cN −3 , cN − 2 ) ∈ C. It means that group of code symmetry of a cyclic code C ⊂ F N is . Cyclic codes are studied from many points of view. One way is to view them as ideals of an algebra. Define ρ : F N → F[ x] / x N − 1 via ρ : (c0 , c1 ,..., cN − 2 , cN −1 )  c0 + c1 x + ... + cN − 2 x N − 2 + cN −1 x N −1 . It can be shown that ρ is an isomorphism. Let C ⊂ F N be cyclic block code. Then ρ ( C) is a subspace of the F -vector space F[ x] / x N − 1 . Now the added condition of being cyclic translates to the following: if ( ) ( ) ρ(c) ∈ρ(C) then x ⋅ ρ(c) = x ⋅ c0 + c1 x + ... + cN − 2 x N − 2 + cN −1 x N −1 = cN −1 + c0 x + c1 x 2 + ... + cN − 2 x N −1 ∈ρ(C). With this extra condition, ρ(C)  F[ x] / x − 1 . N There are many generalizations of cyclic codes, some of which may be viewed as ideals of particular rings [3]: IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) Data Science V G Labunets and E Ostheimer • negacyclic (skew-cyclic) codes[4-11]- ideal of the ring A lg N (F)[ x] / x N + 1 , • constacyclic codes [12]- ideal of the ring A lg N (F)[ x] / x N − λ ,where λ ∈ A lg (F) , • polycyclic codes [3]- ideal of the ring A lg N (F)[ x] / f ( x) ,where f ( x) ∈ A lg (F)[ x] . The terminology of the cyclic codes theory may be extended to define a larger family ofcodes. We start by introducing vector-induced clockwise and counterclockwise shifts. Given a vector s ( s0 , s1 ,..., sN − 2 , sN −1 ) ∈ F N , the s -clockwise and s -counterclockwise shifts of codeword C= (c0 , c1 ,..., cN − 2 , cN −1 ) ⊂ F N are the following correspondences Rsc = R s (c0 , c1 ,..., cN −1 ) = (0, c0 , c1 ,..., cN − 2 ) + cN −1 ( s0 , s1 , s2 ,..., sN −1 ) = = (cN −1s0 , c0 + s1cN −1 , c1 + s2 cN −1 ,..., cN − 2 + sN −1cN −1 ), Lc = s Ls (c0 , c1 ,..., cN −1 ) = (c1 , c2 ,..., cN −1 ,0) + c0 ( s0 , s1 , s2 ,..., sN −1 ) = = (c1 + s0 c0 , c2 + s1c0 ,..., cN −1 + sN − 2 c0 , sN −1c0 ). Dyadic codes are defined only for length N , a power of 2, say N = 2n , as follows. Definition 2. For any integer i ∈ {0,1, 2,..., N − 1} , let i = ( in −1 , in − 2 ,..., i1 , i0 ) . Denote its radix-2 n −1 representation, where=i in −1 2n −1 + in − 2 2n −1 + ... + i1 21 + i= 02 0 ∑ i 2 and i1 ∈{0,1 l =0 l l = } for l 0,1, 2,..., n − 1 . Dyadic addition of two numbers i and j denoted by i⊕ j is defined by 2 k =i ⊕ j =( in −1 , in − 2 ,..., i1 , i0 ) ⊕ ( jn −1 , jn − 2 ,..., j1 , j0 ) = 2 2 = ( in −1 ⊕ jn −1 , in − 2 ⊕ jn − 2 ,..., i1 ⊕ j1 , i0 ⊕ j0 ) = ( kn −1 , kn − 2 ,..., k1 , k0 ) where k= l ( il ⊕ jl ) mod 2= , for l 0,1, 2,..., n − 1 . The dyadic = shift, m 0,1, 2,..., N − 1 , of a vector ( ( c0 , c1 ,..., cN −1 ) is the vector c0 ⊕ m , c1⊕ m ,..., c( N −1) ⊕ m . 2 2 2 ) Definition 3. Linear code of length N = 2n is called dyadic code if the m -dyadic shift of every codeword is also a codeword = for all m 0,1, 2,..., N − 1 . The class of dyadic codes is a special case of abelian group codes [13, 14-16] which is briefly discussed in the third. In this paper, we would like tointroduce new linear codes with generalized symmetry. We extend cyclic and group codes in the following way. We introduce codes, invariant with respect to a family of generalized shift operators (GSO). In particle case when this family is a group (cyclic or Abelian), these codes are ordinary cyclic and group codes. They are invariant with respect to this group. We deal with GSO-invariant codes with fast code and encode procedures based on fast generalized Fouriertransforms.The hope is that these more general structures will lead to larger classes of useful codes “good” properties. The rest of the paper isorganized as follows: in Section 2 and 3, the proposed method based on families of generalized shift operators (GSO) is explained. 2. Methods 2.1. Generalized shift operator The purpose of this subsection is to introduce the mathematical representations of generalized shift operators associated with arbitrary orthogonal (or unitary) Fourier transforms ( F -transforms). For illustration, we also particularize our results for many transforms popular in coding and signal theories. The ordinary group shift operators (Tt τ f ) (= t ) f (t + τ ) play the leading role in all the properties and tools of the Fourier transform mentioned above. In order to develop for each orthogonal transform a similar wide set of tools and properties as the Fourier transform has, we associate a family of commutative generalized shift operators (GSO) with each orthogonal (unitary) transform. Such families form hypergroups. In 1934 F. Marty [17,18] and H.S. Wall [19,20] independently introduced IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 339 Data Science V G Labunets and E Ostheimer the notion of hypergroup. Only in particular cases these families are Abelian groups and hyperharmonic analysis is the classical Fourier harmonic analysis on groups. Let f (t ) : Ω → F be a F -valued signal, where F be a finite field. Usually, = Ω [0, N − 1]d in coding theory and digital signal processing, where d is the dimension of Ω : d = dim(Ω). Let L ( Ω, F ) : { f (t ) f (t ) : Ω → F)} ≈ F , Ω = be vector space of F -valued functions, where = Ω card (=Ω ) N d . The theory of generalized shift operators was initiated by Levitan [21]–[22]. According to Levitan the family of generalized shift operators (GSOs) Tt τ [ f= (t ) ] : f (t ( τ) depending on τ ∈ Ω as a parameter is defined in signal space L ( Ω, F ) by the following axioms. Axiom 1. For all functions f1 (t ), f 2 (t ) ∈ L ( Ω, F ) and any constants a, b ∈ F the following relation holds Tˆt τ [ a ⋅ f1 (t ) + b ⋅ f 2 (t ) ] = a ⋅ Tˆt τ [ f1 (t ) ] + b ⋅ Tˆt τ [ f 2 (t ) ] (1) Axiom 2. For an arbitrary function f (t ) ∈ L ( Ω, F) ) and arbitrary s, t , r ∈ Ω it holds Tτr Tt τ [ f (t ) ] = Tt r Tt τ [ f (t ) ] , or f ( t ( ( τ ( rr ) ) = f ( ( t ( rτ ) ( r ) , i.e., Tt τ( r = Tt (r τ . (2) i. e., the GSOs are associative. Axiom 3. There exists an element τ0 ∈ Ω with Txτ0 [ f (t ) ] ≡ f (t ) for all t ∈ Ω and for all f (t ) ∈ L ( Ω, F ) . This means that the family of GSOs contains identity operator. If moreover the following axiom is fulfilled, then the GSOs are called commutative. Axiom 4. For any elements τ,t ∈ Ω and arbitrary f (t ) ∈ L ( Ω, F ) holds t ) ] Trτ Tt r [ f (t ) ] , or f ( t ( ( τ ( = Tτr Tt τ [ f (= rr ) ) f ( t ( ( r ( τ r) ) , i.e., Tτ= r τ Tt TrτTt r (3) We expand notion GSOs on the more complex signal space. Let f (t ) : Ω → A lg (F ) be a A lg (F ) - valued signal. The set Ω of the values of the variable t constitutes the domain of the signal. Usually, = Ω [0, N − 1]d in coding theory and digital signal processing, where d is the dimension of Ω : d = dim(Ω). The set A lg (F ) of values of the signal f (t ) is the range of the signal. About the range of the signal we assume, that A lg (F) is a commutative algebra with aninvolution operation a → a , ∀a ∈ A lg (F ) . In particular, if A lg (F ) is the complex field then the involution operation is complex conjugate. Let Ω* be the space dual to Ω . The first one will be called the spectral domain, the second one be called signal domain keeping the original notion of t ∈ Ω as «time» and ω∈ Ω* as «frequency». Let , A lg (F ) ) : { f (t ) f (t ) : Ω → A lg (F )} ≈ A lg Ω (F ), L ( Ω= L ( Ω= * , A lg (F ) ) : {F (ω ) F (ω ) : Ω → A lg (F)} ≈ A lg (F) * Ω* be two vector spaces of A lg (F ) -valued functions. Here Ω = Ω* = N d . Let {ϕω ( x)}ω∈Ω* be an orthonormal system of functions in L ( Ω, A lg (F ) ) . Then for any function f (t ) ∈ L ( Ω, A lg (F) ) there exists such a function F (ω ) ∈ L ( Ω* , A lg (F ) ) , for which the following equations hold: F (ω ) = (= f (t ) ( F= F f ) (ω ) ∑ f (t )ϕω (t ),= -1 F ) (t ) ∑ F (ω )ϕω (t ). t∈Ω ω∈Ω* (4) The function F (ω ) ∈ L ( Ω , A lg (F ) ) is called the Fourier spectrum ( F -spectrum) of the A lg (F ) - * valued signal f (t ) ∈ L ( Ω, A lg (F) ) and expressions (1)-(2) are called the pair of generalized Fourier transforms (or F -transforms). In the following we will use the notation f (t ) ← F → F (ω) in order to indicate F -transforms pair. IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 340 Data Science V G Labunets and E Ostheimer A fundamental and important tool of coding and signal theories are shift operators in the «time» and «frequency» domains. They are defined as (Ttτ f ) (= t ) : f (t + τ ), ( Dων F ) (= ω ) : F (ω + ν ) ,    τ and  (Tt f ) (= t ) : f (t − τ ) ( Dω F ) (=ω ) : F (ω − ν ) . ν  jωt − jωt For f (t ) = e and F (ω ) = e we have jω ( t +τ ) − j (ω +ν )t  T= τ jωt t e e= ωτ jωt e j= e λω (τ )e jωt , =Dων e jωt e= e −=jν t − jωt e λν (t )e − jωt ,  τ jωt jω ( t −τ ) ωτ jωt and  − j (ω −ν )t (5) T= t e e= e − j= e λω (τ )e jωt Dων e jωt e=  = e= jν t − jωt e λν (t )e − jωt , i.e., harmonic signals e jωt and e − jωt are eigenfunctions of «time»-shift and «frequency»-shift operators Ttτ , Tt τ and Dων , Dων , corresponding to eigenvalues = λω (τ ) e= jωτ , λω (τ ) e − jωτ and − jν t λν (t ) e= = , λν (t ) e jν t , respectively. Definition 4. The following operators (with respect to which all basis functions are invariant eigenfunctions (Tt τϕω ) (t ) := ϕω (τ) ⋅ ϕω (t ) = λω (τ)ϕω (t ), ∀τ∈ Ω, (T ϕ ) (t ) := ϕ (τ) ⋅ ϕ (t ) = λ (τ)ϕ (t ), ∀τ∈ Ω t τ ω ω ω ω ω (6) and ( D ϕ ) (t ) := ϕ (t ) ⋅ ϕ (t ) = λ (t ) ⋅ ϕ (t ), ∀ν ∈ Ω , ν ω ω ν ω ν ω * ( D ϕ ) (t ) := ϕ (t ) ⋅ ϕ (t ) = λ (t ) ⋅ ϕ (t ), ∀ν ∈ Ω ν ω ω ν ω ν ω (7) * are called commutative F –generalized "time"–shift and "frequency"–shift operators (GSO’s), respectively, where λ ω (τ) =ϕω (τ), λ ω (τ) =ϕω (τ) and λ ν (t ) = ϕν (t ), λ ν (t ) = ϕν (t ) are eigenvalues of GSO’s Tt τ , Tt τ and Dων , Dων , respectively. For these operators we introduce the following designations: ϕω (t ( τ), (Tt τ ϕω ) (t ) := (Tt τϕω ) (t ) := ϕω (t ' τ), ∀τ∈ Ω, ( D ϕ ) (t ) := ν ω ω ϕ (t ), ( D ϕ ) (t ) := ω⊕ν ν ϕ (t ), ∀ν ∈ Ω , ω ω ω$ ν * here, symbols “ ( , ⊕ ”,“ ' , $ ” denote quasi-sums and quasi-differences, respectively. If Ttτ,σ , Tt τ,σ and Dων ,α , Dων ,α are matrix elements of operators = Ttτ,σ  , Tt τ Tt ,τσ  and Dων ,α =  Dων ,α  , Ttτ = Dων ,α =  Dων ,α  , then (T ϕ ) (t ) = ϕ (t ( τ) = ϕ (τ) ⋅ ϕ (t ) = ∑ T ϕ (σ), t τ ω ω ω ω τ t ,σ ω σ∈Ω (8) (T ϕ ) (t ) = ϕ (t ' τ) = ϕ (τ) ⋅ ϕ (t ) = ∑ T ϕ (σ), t τ ω ω ω ω τ t ,σ σ σ∈Ω and ( D ϕ ) (t ) = ϕ ν ω ω ω⊕ν (t ) = ϕν (t ) ⋅ ϕω (t ) = ∑ Dων,α ϕα (t ), α∈Ω* (9) ( D ϕ ) (t ) = ϕ ν ω ω ω$ ν (t ) = ϕν (t ) ⋅ ϕω (t ) = ∑ D ϕα (t ) ν ω, α α∈Ω* The expressions (8)–(9) are called multiplication formulae for basis functions {ϕω (t )}ω∈Ω* ∈ L ( Ω, A lg (F) ) and {ϕω (t )}t∈Ω ∈ L ( Ω* , A lg (F) ) . They show that the set of basis functions form two hypergroups with respect to multiplication rules (8) and (9), respectively. Consequently, two IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 341 Data Science V G Labunets and E Ostheimer spaces L ( Ω, A lg (F ) ) and L ( Ω* , A lg (F ) ) form time and frequency algebras with structure constants Tt ,τσ and Dων,α , respectively. From (8) and (9) we easily obtain the matrix elements of the GSOs in time and frequency domains τ Tt = ,σ ∑ ϕω (τ)ϕω (t )ϕω (σ), Tt= τ ,σ ∑ ϕω (τ)ϕω (t )ϕω (σ), (10) ω∈Ω* ω∈Ω* D ν ω, α = ∑ ϕν (t )ϕω (t )ϕα (t ), Dων,α = ∑ ϕν (t )ϕω (t )ϕα (t ). (11) t∈Ω t∈Ω The expressions (10)–(11) can be compactly written on the operator language Txτ= F −1 ⋅ diag {ϕω (τ)} ⋅ F , Tt τ= F −1 ⋅ diag {ϕω (τ)} ⋅ F , (12) Dων =F ⋅ diag {ϕν (t )} ⋅ F −1 , Dων =F ⋅ diag {ϕν (t )} ⋅ F −1 , where diag {ϕ} denotes a diagonal matrix which entries consist of values of the function ϕ . If there exist such element t0 that the equation ϕω (t0 ) ≡ 1 for all ω∈ Ω* is fulfilled, then there exist the identity GSO in time domain. Indeed, the substitution of t0 into the expressions (12) gives Tt t0= F −1 ⋅ diag {ϕω (t0 )} ⋅ F== F −1 ⋅ diag {1} ⋅ F== F −1 ⋅ F== I , (13) Tt t0= F −1 ⋅ diag {ϕω (t0 )} ⋅ F== F −1 ⋅ diag {1} ⋅ F== F −1 ⋅ F== I . If there exist such an element ω0 that the equation ϕω0 ( x) ≡ 1 for all x ∈Ω is fulfilled too, then there exist the identity GSO in frequency domain. Indeed, the substitution of ω0 into the expressions (12) gives { } Dˆ ωω0 =F ⋅ diag ϕω0 ( x) ⋅ F −1 =F ⋅ diag {1} ⋅ F −1 =F ⋅ F −1 =I , Dˆ =F ⋅ diag {ϕ ( x)} ⋅ F ω0 ω ω0 −1 =F ⋅ diag {1} ⋅ F −1 =F ⋅ F −1 =I . We see also that two families of time and frequency GSOs form two hypergroups H G = {Tt τ } and t∈Ω { } H G* = Dων ν∈Ω . By definition, functions {ϕω (t )}ω∈Ω* and {ϕω (t )}t∈Ω are eigenfunctions of GSOs. For this reason we can call them hypercharacters of hypergroups. For a signal f (t ) ∈ L ( Ω, A lg (F) ) we define its shifted copies by   ( τ) (Tt τ f= f (t = ) (t ) Tt τ  ∑* F (ω)ϕω= (t )  ∑ F (ω) (Tt τ ϕω= )(t )  ω∈Ω  ω∈Ω* = ∑ F (ω)ϕ (τ)ϕ= ω (t ) ∑ ( F (ω)ϕ (τ) ) ϕ (t ), ω ω ω ω∈Ω* ω∈Ω* (14)   f (t = ' τ) ( ) (t ) Tt τ  ∑ F (ω)ϕω= Tt τ f= (t )  ∑ F (ω) (T ϕ = )(t ) t τ ω  ω∈Ω*  ω∈Ω * = ∑ F (ω)ϕ (τ)ϕ= ω (t ) ∑ ( F (ω)ϕ (τ) ) ϕ (t ). ω ω ω ω∈Ω* ω∈Ω* Analogously, for a spectrum F (ω) ∈ L ( Ω* , A lg (F ) )   F (ω= ⊕ ν) ( D F=ν ω ν ω (t )  ∑ f (t ) ( D ϕ= ) (ω) D  ∑ f (t )ϕ= ) (t ) ω ν ω ω  ω∈Ω *  ω∈Ω * = ∑ f (t )ϕν (t )ϕω=(t ) ∑ ( f (t )ϕν (t ) ) ϕω (t ), ω∈Ω* ω∈Ω* (15)   $ ν) Dων F= F (ω= ( ) (ω) Dων  ∑ f (t )ϕ=ω (t )  ∑* f (t ) Dων ϕ= ω (t ) ( )  ω∈Ω *  ω∈Ω = ∑ f (t )ϕν (t )ϕω=(t ) ∑ ( f (t )ϕν (t ) ) ϕω (t ). ω∈Ω* ω∈Ω* IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 342 Data Science V G Labunets and E Ostheimer We will need in the following modulation operators: ( M tν f ) (t ) := ϕν (t ) f (t ), ( M tν f ) (t ) := ϕν (t ) f (t ), ( M F ) (ω) :=ϕ (τ) F (ω), ( M F ) (ω) :=ϕ (τ) F (ω). τ ω ω τ ω ω From the GSOs definition it follows the following result (two theorems about shifts and modulations). Shifts and modulations are connected as follows: f (t ( τ) ← F → F (ω)ϕω (τ), f (t ' τ) ← F → F (ω)ϕω (τ), (T f ) (t ) ←→ ( M F ) (ω), (T f ) (t ) ←→ ( M F ) (ω) t τ F τ ω t τ F τ ω and F (ω ⊕ ν) ← F → f (t )ϕν (t ), F (ω $ ν) ← F → f (t )ϕν (t ) ( D F ) (ω) ←→ ( M f ) (t ), ( D F ) (ω) ←→ ( M f ) (t ). ν ω F t ν ν ω F t ν 2.2. Generalized convolutions and correlations Using the notion GSO, we can formally generalize the definitions of convolution and correlation. Definition 5. The following functions y (t ) := ( h◊x ) (t ) = ∑ h(τ) x ( t ' τ ) , Y ( ω) := ( H♥F )( ω) = ∑ H ( ν ) F ( ω $ ν ) τ∈Ω ν∈Ω* and c(τ) = ( f ♣g ) (τ) := ∑ f (t ) g ( t ' τ ), C (ν) = ( F♠G )( ν ) := ∑ F ( ω) G ( ω $ ν ) t∈Ω ω∈Ω* are called the ◊ - and ♥ - convolutions and the cross ♣ - and ♠ - correlation functions, respectively, associated with a classical Fourier transform F. If f = g and F = G then cross correlation functions are called the ♣ - and ♠ - autocorrelation functions. The spaces L ( Ω, A lg (F ) ) and L ( Ω* , A lg (F ) ) equipped multiplications ◊ and ♥ form commutative signal and spectral convolution algebras L ( Ω, A lg (F ) ) , ◊ and L ( Ω* , A lg (F ) ) ,♥ , respectively. Theorem 1. Let us take two triplets y1 (t ), h1 (t ), x1 (t ) ∈ L ( Ω, A lg (F) ) and y2 (t ), h2 (t ), x2 (t ) ∈ L ( Ω, A lg (F) ) . Obviously, Y1 (ω ), H1 (ω ), X 1 (ω ) ∈ L ( Ω* , A lg (F) ) and Y2 (ω ), H 2 (ω ), X 2 (ω ) ∈ L ( Ω* , A lg (F) ) . Let y1 (t ) = ∑ h1 (τ) x1 ( t ' τ ) and Y2 (ω=) ( h1◊x1 ) (t ) = τ∈Ω ( H 2♥X 2 ) (ω=) ∑ H 2 ( ν ) F2 ( ω $ ν ) ν∈Ω* then generalized Fourier transforms F and F −1 map ◊ -and ♥ -convolutions into the products of spectra and signals, respectively, F { y1}= F {h1◊x1}= F {h1} ⋅ F { x1} , F −1 {Y2 }=: F −1 {H 2♥X 2 }= F −1 {H 2 } ⋅ F −1 { X 2 } , i.e., t ) ( h1◊x1 ) (t ) ← y1 (= F → Y1 (ω= ) H1 (ω) ⋅ X 1 (ω), y2 (= t ) h2 (t ) x2 (t ) ← F ) ( H 2♥X 2 ) (ω) . → Y2 (ω= Theorem 2. Let us take four triplets c1 (t ), f1 (t ), g1 (t ) ∈ L ( Ω, A lg (F) ) , c2 (t ), f 2 (t ), g 2 (t ) ∈ L ( Ω, A lg (F) ) and C1 (ω ), F1 (ω ), G1 (ω ) ∈ L ( Ω* , A lg (F) ) , C2 (ω ), F2 (ω ), G2 (ω ) ∈ L ( Ω , A lg (F) ) . Let * c1 (τ)= ( f1♣g1 ) (τ)= ∑ f1 (t ) g1 ( t ' τ ), and C2 (ω)= ( F2♠G2 )( ν )= ∑ F2 ( ω) G2 ( ω $ ν ), t∈Ω ω∈Ω* then generalized Fourier transforms F and F map ♣ - and ♠ -correlations into the products of −1 spectra and signals, respectively, F {c1}= F { f1◊g1}= F { f1} ⋅ F { g1} , F −1 {C2 }=: F −1 {F2♥G2 }= F −1 {F2 } ⋅ F −1 {G2 } , i.e., IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 343 Data Science V G Labunets and E Ostheimer τ) ( f1♣g1 ) (τ) ← c1 (= F → C1 (ω =) F1 (ω) ⋅ G1 (ω), ), c2 (= t ) f 2 (t ) g 2 (t ) ← F → C2 ( ω =) ( F2♥G2 ) (ω) . 2.3. Codes invariant with respect to GSOs We are going to consider block codes of length N as subsets C ⊂ L ( Ω, A lg (F) ) and ( ) C* ⊂ L Ω* , A lg (F) , i.e., a collections of N length vectors with components from Alg (F ) . Let {ϕω (t )}t∈Ω and {ϕω (t )}ω∈Ω be orthonormal systems of functions for L ( Ω, A lg (F) ) and L ( Ω* , A lg (F) ) , * respectively. They generate two hypergroups H G- and H G* . Definition 6. H G- and H G* - invariant block codes C ⊂ L ( Ω, A lg (F) ) and C* ⊂ L ( Ω* , A lg (F) ) are linear block codes with the property that if c(t ) ∈ C and C (ω) ∈ C* then (T c )= t (t ) c(t ' τ) ∈ C, ∀T ∈ H G and ( D C ) (ω)= C (ω $ ν) ∈ C, ∀D ∈ H G , respectively. τ t τ ν ω ν ω * It means that H G- and H G - invariant block codes C ⊂ L ( Ω, A lg (F) ) and C ⊂ L ( Ω , A lg (F) ) have * * * hypergroup symmetries . Reed-Solomon (RS) codes are nonbinary cyclic codes [23]. The most natural definition of H G- and H G* - invariant RS codesare in terms of a certain evaluation maps from the subspace A lg k (F ) of all k -tuples m = (m0 , m1 ,..., mk −1 ) (information symbols = massage) over A lg (F ) to the set of codewords C= Cod [ N , k | A lg (F ) ] ⊂ L ( Ω, A lg (F ) ) = =m (m0 , m1 ,...,= mk −1 )  c(t ) (c(0), c(1),..., c( N − 1)), A lg k (F ) → L ( Ω, A lg (F ) ) (16) = or to the set of codewords C Cod [ N , k | A lg (F )] ⊂ L ( Ω , A lg (F ) ) * * * = = m (m0 , m1 ,..., mk −1 )  C (t ) (C (0), C (1),..., C ( N − 1)), A lg k (F ) → L ( Ω* , A lg (F ) ) Definition 7. We define an encoding function for H G- and H G* - invariant Reed-Solomon codes as H G-RS: A lg k (F ) → L ( Ω, A lg (F ) ) , H G* -RS: A lg k (F ) → L ( Ω* , A lg (F ) ) in the following forms. A message m = (m0 , m1 ,..., mk −1 ) with mi ∈ A lg (F ) are transformed by F and F −1 :  C (0)   m0   c(0)   m0   C (1)  m   c(1)  m     1     1   C (2)   ...   c(2)   ...        −1   =  ....  F=  mk −1  ,  ....  F  mk −1  ,  ...   0   ...   0          C ( N − 2)   ...  c( N − 2)   ...   C ( N − 1)   00   c( N − 1)   00          * Hence, generator matrices for H G- and H G - invariant Reed-Solomon codesare the generalized Fourier matrices F and F −1 . Convolutional cyclic codes (CC’s, for short) form an important class of error-correcting codes in engineering practice. The mathematical theory of these codes has been set off by theseminal papers of Forney [24] and Massey et al. [25]. Definition 8. H G- and H G* - invariant convolutional codes of length N and dimension k are ideals gh(t ) , G (ω) of L ( Ω, A lg (F ) ) , ◊ and L ( Ω* , A lg (F) ) ,♥ having the following forms c(t ) =( h◊m ) (t ) =∑ h(t ' τ)m ( τ ) and C (ω) = ( G♥m ) (ω) = ∑ G ( ω $ ν ) m ( ν ) τ∈Ω ν∈Ω* where IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 344 Data Science V G Labunets and E Ostheimer ( F h)=(ω) ( H (0), H (1),..., H (k − 1),0,...,0 ) ∈ A lg k (F ), H= (ω) = g (ω) ( F= −1 G ) (t ) ( g (0), g (1),..., g (k − 1),0,...,0 ) ∈ A lg k (F ). We call matrices G= G ( ω $ ν )  ω,ν∈Ω and = H [ h(t ' τ) ]t , τ∈Ω encoders. * It is easy to see that cyclic convolutional codes and group convolutional codes are particular cases of H G- and H G* - invariant convolutional codes. 3. Examples Let H N be a finite Abelian group of order= N N1 N 2 ⋅ ⋅ ⋅ N n .The fundamental structure theorem for finite Abelian group implies that we may write H N as the direct sum of cyclic groups, H N = Z N × Z N × ... × Z N , where Z Nl identified with the ring of integers Z Nl under with respect to 1 2 n modulo N l and an element t ∈ H N is identified with a point t = ( t1 , t2 ,..., tn ) of n D discrete torus. The addition of two elements t , τ ∈ H N is defined as σ = t ⊕* τ = (σ1 , σ 2 ,..., σ n ) = (t1 ⊕ τ1 , t2 ⊕ τ2 ,..., tn ⊕ τn ) . HN Z N1 Z N2 Z Nn The Fourier transforms in the space of all functions, defined on the finite Abelian group n H N = ⊕ Z Nl , and with their values in the finite commutative ring (field) or some finite algebra A has l =1 a great interest for digital signal processing. Denote this space as L ( H N , A lg (F ) ) . Let ε Nl a primitive N l –th root in the algebra A lg (F ) . Let us construct the following functions χ kl (tl ) = ε , kl tl Nl kl = 0,1,..., N l − 1. They form the set of characters of the cyclic group Z Nl . Then theset of all characters of the group H N can be describe by the following way χ k (t ) = χ( k1 , k2 ,..., kn ) (t1 , t2 ,..., tn ) = ε kN11t1 ε kN22t2 ⋅⋅⋅ ε kNnntn , (16) where k = (k1 , k2 ,..., kn ) .The set of all characters {χ k (t )}k∈H * and the set of all indexes H * N forms N isomorphic multiplicative and additive groups, respectively, with respect to multiplication of characters and addition of indexes χ k (t )χ m (t ) = χ k m (t ) = χl (t ), where ⊕* HN l =k ⊕* m =(l1 , l2 ,..., ln ) =(k1 ⊕ m1 , k2 ⊕ m2 ,..., kn ⊕ mn ) . HN Z N1 Z N2 Z Nn = [ χ k (t ) ]t∈H , k∈H* forms Fourier transform on H N . The following matrix F = N N * The set H is called the dual group. It forms ”frequency” domain. If initial group has the structure N H N = Z N1 ⊕ Z N2 ⊕ ... ⊕ Z Nn then the dual group has the same structure H*N = H N .Let us embed finite Ω [0, N − 1] and Ω groups H N and H*N into two discrete segments= = * [0, N − 1] H N →= Ω [0, N − 1], H*N →= Ω* [0, N − 1], (17) respectively. For this aim we briefly describe a mixed–radix number system now. A number system is called a weighted number system if any number t can be uniquely expressed in the following form t = ∑ ti wi for some set of integers ti , called digits, and wi ’s, called weights. If the i weights are successive powers of the same number (for example, 2 or 10), the number system is called a fixed–radix number system (for example, 10–radix or 2–radix). Any number t in mixed–radix n  n +1  number system can be expressed in the form t = ∑ ti  ∏ N j  . Let N1 , N 2 ,..., N n , N n +1 , where N n +1 ≡ 1 i =1  j = i +1  be a finite set of positive integers. Then, with respect to the mixed radixes above, any nonnegative integer t ∈ [0, N − 1] , where= N N1 N 2 ⋅ ⋅ ⋅ N n , can be uniquely expressed as IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 345 Data Science V G Labunets and E Ostheimer n −1  n −i +1  =t ( t1 , t2= ,..., tn ) t1 ( N 2 N 3 ⋅⋅⋅ N n −1 N n ) + ... + tn − 2 ( N n −1 N n ) + tn −1 ( N= n ) + tn ∑ tn − i  ∏ N j  , i =0  j= n +1  n − i +1 where t1 ∈ [0, N1 − 1], t2 ∈ [0, N1 − 1], ..., tn −1 ∈ [0, N n −1 − 1], tn ∈ [0, N n − 1]. The weights of ti is ∏ N j . j= n +1 The weight of tn is unity ( N n +1 = 1) .The radix-2 representation= is t tn −1 2 n −1 + tn − 2 2 n −1 + ... + t1 2 + t=1 02 0 n −1 n −1  n −i +1  = ∑ t n −= i i2 . Let t ( t1 , t2 ,..., tn ) ∈ H N and (ω1 , ω2 ,..., ωn ) ∈ H*N then expressions ω= ∑ ωn −i  ∏ N j  , i =0 i =0  j= n +1  n −1  n −i +1  k = ∑ kn −i  ∏ N j  define the maps (17). i =0  j= n +1  The following operators (with respect to which all characters are invariant eigenfunctions) (Tt τχω ) (t ) := χω (τ) ⋅ χω (t ) = χω (t ⊕ τ), ∀τ∈ Ω, HN (T χ ) (t ) := χ (τ) ⋅ χ (t ) = χ (t $ τ), ∀τ∈ Ω t τ ω ω ω ω HN (18) and ( D χ ) (t ) := χ (t ) ⋅ χ (t ) = χ ν ω ω ν ω ω⊕ν H*N (t ), ∀ν ∈ Ω* , ( D χ ) (t ) := χ (t ) ⋅ χ (t ) = χ ν ω ω ν ω (19) ω$ ν H*N (t ), ∀ν ∈ Ω* are called commutative F H –generalized "time"–shift and "frequency"–shift operators, induced an N abelian group H N . Itinduces ”exotic” shifts in segments H N →= Ω [0, N − 1], H*N →= Ω* [0, N − 1] too, which we will denote as t ⊕ τ= (t1 ⊕ τ1 , t2 ⊕ τ2 ,..., tn ⊕ τn ) ∈ Ω= [0, N − 1], HN N1 N2 Nn k ⊕* m = (k1 ⊕ m1 , k2 ⊕ m2 ,..., kn ⊕ mn ) ∈ Ω= * [0, N − 1]. HN N1 N2 Nn Instead of spaces L ( H N , A lg (F ) ) and L H*N , A lg (F ) ( ) we will speak aboutspaces L ( Ω, A lg (F) ) ( ) and L Ω*N , A lg (F ) and if necessary, in this designations we will distinguish groups, acting in ( ) intervals: L Ω, A lg (F ) | H N and L Ω*N , A lg (F ) | H*N . ( ) Definition 9. HN - and H*N - invariant block codes ( C ⊂ L Ω, A lg (F) | H N and ) ( ) C* ⊂ L Ω*N , A lg (F) | H*N are linear block codes with the property that if c(t ) ∈ C and C (ω) ∈ C* then (T c ) (= t t ) c(t ⊕ τ) ∈ C, ∀τ∈ Ω and ( D C ) (ω= τ HN ) C (ω ⊕ ν) ∈ C, ∀ν ∈ Ω , ν ω H*N * respectively It means that H N - and H*N - invariant block codes have ordinarygroup symmetries HypSym {C}  H N and HypSym {C }  H . The seclass of codes are called the abelian group codes * * N [13, 14-16]. Special cases of abelian group codes are 1) a cyclic code, when H N = Z N1 × Z N2 × ... × Z Nn ≡ Z N is a cyclic group, 2) a dyadic code, when H 2n = Z 2 × Z 2 × ... × Z 2 . In the = ε Ntω  first case F = is the ordinary Fourier transform,where ε N a primitive N –th root in the t∈Z N ,ω∈Z*N algebra A lg (F ) and in the second one F== ( −1)  t |ω is the Walsh transform, where t | ω is   t∈H 2n ,ω∈H*2n n the scalar products oftwo= vectors t ( t1 , t2 ,..., tn ) ∈ H N and (ω1 , ω2 ,..., ωn ) ∈ H*N : t | ω = ∑ tiωi . i =1 IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 346 Data Science V G Labunets and E Ostheimer N −1 N −1 =Let F= ε 2t N ε Ntω  t ,ω 0= = = ε 2t (2N ω +1)  t ,ω 0 . Then F (ω ) = (= , f (t ) ( F= F f ) (ω ) ∑ f (t )ε 2−Nt ε N− tω= -1 F ) (t ) ∑ F (ω )ε 2t N ε Ntω t∈Ω ω∈Ω* is direct and inverse modulation Fourier transform, where ε 2 N is a primitive 2N –th root in the algebra A lg (F ) . According to definition 4 for ϕω (t ) = ε 2t N ε Ntω we have Tˆ τ {ϕ (t )} = ϕ (t ( τ) = ϕ (τ) ⋅ ϕ (t ) = ε( ) ε( ) = ε( )( ) , 2 ω+1 τ 2 ω+1 t 2 ω+1 t +τ t ω ω ω ω 2N 2N 2N τ Tˆ n {ϕω (t )} = ϕω (t ' τ) = ϕω (τ) ⋅ ϕω (t ) = ε 2 (N ) ε(2 N ) = ε(2 N )( ) . − 2 ω+1 τ 2 ω+1 t 2 ω+1 t −τ τ But ε(2 N )( ) = ε(2 N ) ε(2 N ) = ε(2 ) ε(2 N ) = (−1)( ) ε(2 N ) = −ε(2 N ) . Hence, Tˆt τ and Tˆ n 2 ω+1 t + N 2 ω+1 N 2 ω+1 t 2 ω+1 2 ω+1 t 2 ω+1 2 ω+1 t 2 ω+1 t are negacyclic (skew-cyclic) GSOs: = Tˆt τ {c(t )} (c0( = τ , c1( τ ,..., c( N −1)( τ ) (cτ , cτ+1 ,..., cN − 2 , cN −1 , −c0 , −c1 ,..., −cτ−1 ),  τ τ Tˆ n {c(t )} = (c0' τ , c1' τ ,..., c( N −1)' τ ) = (−cN −τ ,..., −cN − 2 , −cN −1 , c0 , c1 ,..., cN −( τ−1) ).  τ N −1 N −1 = They generate negacyclic (skew-cyclic) codes. ε mN Let F = = t ε Ntω  ( mω +1) t ε mN  =t ,ω 0=t ,ω 0 . Then F (ω ) = F f ) (ω ) ∑ f (t )ε mN (= −t , f (t ) ( F= ε N− tω= -1 F ) (t ) ∑ F (ω )ε mN t ε Ntω t∈Ω ω∈Ω* is direct and inverse ε −t mN -modulation Fourier transform, where ε mN is a primitive mN –th root in the algebra A lg (F ) . According to definition 4 for ϕω (t ) = ε mN t ε Ntω we have Tˆ τ {ϕ (t )} = ϕ (t ( τ) = ϕ (τ) ⋅ ϕ (t ) = ε( ) ε( ) = ε( )( ) , mω+1 τ 2 m +1 t mω+1 t +τ t ω ω ω ω mN mN mN τ Tˆ n {ϕω (t )} = ϕω (t ' τ) = ϕω (τ) ⋅ ϕω (t ) = ε mN( ) ε(mN ) = ε(mN )( ) . − mω+1 τ mω+1 t mω+1 t −τ τ But ε(mN )( ) = ε(mN ) ε(mN ) = ε(m ) ε(2 N ) = ε m ε(mN ) . Hence, Tˆt τ and Tˆ n are constacyclic mω+1 t + N mω+1 N mω+1 t mω+1 2 ω+1 t mω+1 t GSOs: = Tˆt τ {c(t )} (c0( τ ,= c1( τ ,..., c( N −1)( τ ) (cτ , cτ+1 ,..., cN − 2 , cN −1 , ε m c0 , ε m c1 ,..., ε m cτ−1 ),    τ τ Tˆ n {c(t )} = (c0' τ , c1' τ ,..., c( N −1)' τ ) = (ε m cN −τ ,..., ε m cN − 2 , ε m cN −1 , c0 , c1 ,..., cN −( τ−1) ).   τ They generate constacyclic codes codes. 4. Conclusion In this paper we studied a new class of codes with generalized symmetry. They are invariant with respect to a family of generalized shift operators H Gor H G* . In particle case when this family is a group (cyclic or Abelian), these codes are ordinary cyclic and group codes.We deal with GSO- invariant codes with fast code and encode procedures based on fast generalized Fouriertransforms. 5. References [1] Berlekamp E R 1969 Negacyclic codes for the Lee metric Combinatorial Mathematics and its Applications 298-316 [2] Berlekamp E R 1984 Algebraic coding theory (New York: Aegean Park Press) [3] Sergio R L P and Benigno R 2009 Dual generalizations of the concept of cyclicity of codes Adv. Math. Commun. 3(3) 227-234 IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 347 Data Science V G Labunets and E Ostheimer [4] Boucher D, Geiselmann W and Ulmer F 2007 Skew-cyclic codes Appl. Algebra Eng.Comm. Comput. 184 379-389 [5] Delphine B, Patrick S and Felix U 2008 Skew constacyclic codes over Galois rings Adv. Math. Commun. 23 273-292 [6] Delphine B and Felix U 2008 Coding with skew polynomial rings Adv. Math. Commun. 33 254- 276 [7] Hai Q D 2005 Negacyclic codes of length 2s over Galois rings IEEE Trans. Inform. Theory IT 51(12) 4252-4262 [8] Hai Q D 2008 On the linear ordering of some classes of negacyclic and cyclic codes and their distance distributions Finite Fields Appl. 141 22-40 [9] Hai Q D, Sergio R L and Szabo S On the structure of cyclic and negacyclic codes over finite chain rings Codes over rings 6 [10] Hai QD and Sergio R L 2004 Cyclic and negacyclic codes over finite chain rings IEEE Trans. Inform. Theory 50(8) 1728-1744 [11] Hakan O and Ferruh O 2009 A note on negacyclic and cyclic codes of length p^s over a finite field of characteristic Adv. Math. Commun. 3(3) 265-271 [12] Hai Q 2006 Structure of some classes of repeated-root constacyclic codes over integers modulo 2m Groups, rings and group rings Lect. Notes Pure Appl. Math. 248 105-117 [13] Sundar R B and Siddigi M U 1994 Transform Domain Characterization of Abelian codes IEEE Trans. Inform. Theory 40 2082-2090 [14] Berman S D 1967 Semi-simple cyclic and abelian codes Kibernetica 3 20-30 [15] Camion P 1970 Abelian codes Tech. Rep. 1059 [16] MacWilliams F J 1970 Binary codes which are ideals in the group algebra of an abelian group BSTJ 49 987-1011 [17] Marty F 1934 Sur une generalization de la notion de groupe Sartryckur Forhandlingar Via Altonde Skandinavioka Matematiker kongresseni 45-49 [18] Marty F 1937 Role de la notion d’hypergroupedansl’etude des groupes non abelians Computes Rendus de l’Academie des Sciences 201 636-638 [19] Wall H S 1934 Hypergroups Bulletin of the American Mathematical Socity 41 36-40 [20] Wall H S 1937 Hypergroups American Journal of Mathematics 59 77-98 [21] Levitan B M 1949 The application of generalized displacement operators to linear differential equations of second order Uspechi Math. Nauk 4(1) 3-112 [22] Levitan B M 1964 Generalized translation operators Israel Program for Scientific Translations [23] Reed I S and Solomon G 1960 Polynomial Codes Over Certain Finite Fields SIAM Journal of Applied Math 3 300-304 [24] Forney G D 1970 Convolutional codes Part I: Algebraic structure IEEE Trans. Inform. Theory. It 16 720-738 [25] Massey J L and Sain M K 1967 Codes, automata, and continuous systems: Explicit Interconnections IEEE Trans. Aut. Contr. AC 12 644-650 Acknowledgments This work was supported by grants the RFBR № 17-07-00886 and by Ural State Forest Engineering’s Center of Excellence in “Quantum and Classical Information Technologies for Remote Sensing Systems”. IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 348