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.
ρ : FN → F[x] / xN −1 that ρ is an isomorphism. Let C ⊂ F N be cyclic block code. Then ρ(C) is a subspace of the F -vector space F[x] / xN − 1 . Now the added condition of being cyclic translates to the following: if
• negacyclic (skew-cyclic) codes[4-11]- ideal of the ring A lg N (F)[x] / xN + 1 , • constacyclic codes [12]- ideal of the ring A lg N (F)[x] / xN − λ ,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 =s1,..., (s0 , sN −2 , sN −1) ∈ FN , the s -clockwise and s -counterclockwise shifts of codeword C= =c1,..., (c0 , cN −2 , cN −1) ⊂ FN are the following correspondences
Rsc =Rs (c0 , c1,..., cN −1) =(0, c0 , c1,..., cN −2 ) + cN −1(s0 , s1, s2 ,..., sN −1) =
= (cN −1s0 , c0 + s1cN −1, c1 + s2cN −1,..., cN −2 + sN −1cN −1), L c =Ls (c0 , c1,..., cN −1) =(c1, c2 ,..., cN −1, 0) + c0 (s0 , s1, s2 ,..., sN −1) = s
=(c1 + s0c0 , c2 + s1c0 ,..., cN −1 + sN −2c0 , 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 + i0 20 =∑il 2l and i1 ∈{0,1} for l =0,1, 2,..., n −1. l=0 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 ) ⊕2 ( jn−1, jn−2 ,..., j1, j0 ) =
2 = (in−1 ⊕ jn−1,in−2 ⊕ jn−2 ,...,i1 ⊕ j1,i0 ⊕ j0 ) = (kn−1, kn−2 ,..., k1, k0 ) where kl =(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)⊕2 m ) .
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.
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 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 ) : =(t) { f 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
Axiom 1. For all functions f1(t), f2 (t) ∈ L (Ω, F ) and any constants a,b ∈ F the following relation holds
Tˆtτ [a ⋅ f1(t) + b ⋅ f2 (t)] = a ⋅ Tˆtτ [ f1(t)] + b ⋅ Tˆtτ [ f2 (t)] Axiom 2. For an arbitrary function f (t) ∈ L (Ω, F)) and arbitrary s,t, r ∈ Ω it holds
Tτr Ttτ [ f (t)] = Ttr Ttτ [ f (t)] , or f (t ( ( τ ( rr )) = f ((t ( rτ) ( r ), i.e., Ttτ( r = Tt(r τ .
(
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τr Ttτ [ f (t)] =Trτ Ttr [ f (t)] , or f (t ( ( τ ( rr )) =f (t ( ( r ( τr)), i.e., Tτ Tt r τ =TrτTtr
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 L (Ω, A lg (F)) : =(t) { f f (t) : Ω → A lg (F)} ≈ A lg Ω (F), *
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 (ω ) =Ff ( ) (ω ) =∑f (t)ϕω (t), t∈Ω f (t) =F-1F ( ) (t) =∑F (ω )ϕω (t).
ω∈Ω*
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 (ω −ν ).
For f (t) = e jωt and F (ω ) = e− jωt we have
Ttτ e jωt =ejω (t+τ ) =ejωτ e jωt =λω (τ )e jωt , Dων e jωt =e−j(ω +ν )t =e−jν te− jωt =λν(t)e− jωt ,
Ttτ e jωt =ejω (t−τ ) =e− jωτ e jωt =λω (τ )e jωt and Dων e jωt =e−j(ω −ν )t =jν e t e− jωt =λν(t)e− jωt , (
Definition 4. The following operators (with respect to which all basis functions are invariant eigenfunctions (Ttτϕω ) (t) := ϕω (τ) ⋅ ϕω (t) = λω (τ)ϕω (t), ∀τ ∈ Ω, (Tt τϕω ) (t) := ϕω (τ) ⋅ ϕω (t) = λω (τ)ϕω (t), ∀τ ∈ Ω ( Dωνϕω ) (t) := ϕν (t) ⋅ ϕω (t) = λν (t) ⋅ ϕω (t), ∀ν ∈ Ω* , ( Dωνϕω ) (t) := ϕν (t) ⋅ ϕω (t) = λν (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τ =Ttτ,σ and Dω ,α = Dων ,α , ν Dω ,α = Dων ,α , then
ν
and
and
(
The expressions (
Tt,τσ = ∑ ϕω (τ)ϕω (t)ϕω (σ), Tt,τσ = ∑ ϕω (τ)ϕω (t)ϕω (σ), ω∈Ω* ω∈Ω* Dω,α = ∑ ϕν (t)ϕω (t)ϕα (t), Dω,α = ∑ ϕν (t)ϕω (t)ϕα (t).
ν ν
t∈Ω t∈Ω
The expressions (
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 (
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 ϕω (x) ≡ 1 for all x ∈ Ω is fulfilled too, then
0
there exist the identity GSO in frequency domain. Indeed, the substitution of ω0 into the expressions
(
Dˆ ω0 =F ⋅ diag{ϕω (x)} ⋅ F −1 =F ⋅ diag{1} ⋅ F −1 =F ⋅ F −1 =I , ω 0 Dˆ ω0 =F ⋅ diag{ϕω (x)} ⋅ F −1 =F ⋅ diag{1} ⋅ F −1 =F ⋅ F −1 =I.
ω 0 We see also that two families of time and frequency GSOs form two hypergroups H G = {T τ} t t∈Ω and 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 Analogously, for a spectrum F (ω) ∈ L (Ω* , A lg (F)) f (t ( τ) =(Ttτ f ) (t) =Ttτ ∑ F (ω)ϕω (t) =∑ F (ω) (Ttτϕω )(t) =
ω∈Ω* ω∈Ω* =∑ F (ω)ϕω (τ)ϕω (t) =∑ ( F (ω)ϕω (τ)) ϕω (t), ω∈Ω* ω∈Ω*
f (t ' τ) =(Tt τ f ) (t) =Tt τ ∑ F (ω)ϕω (t) =∑ F (ω) (Tt τϕω )(t) =
ω∈Ω* ω∈Ω* =∑ F (ω)ϕω (τ)ϕω (t) =∑ ( F (ω)ϕω (τ)) ϕω (t).
ω∈Ω* ω∈Ω* F (ω ⊕ ν) =(Dων F ) (ω) =Dων ∑ f (t)ϕω (t) =∑ f (t) ( Dωνϕω ) (t) =
ω∈Ω* ω∈Ω* =∑ f (t)ϕν (t)ϕω (t) =∑ ( f (t)ϕν (t)) ϕω (t),
ω∈Ω* ω∈Ω* F (ω $ ν) =(Dων F ) (ω)
=Dων ∑ f (t)ϕω (t) =∑ f (t) ( Dωνϕω ) (t) =
ω∈Ω* ω∈Ω* =∑ f (t)ϕν (t)ϕω (t) =∑ ( f (t)ϕν (t)) ϕω (t).
ω∈Ω* ω∈Ω*
(
We will need in the following modulation operators: ( M tν f ) (t) : =(t),( ϕν (t) f M tν f ) (t) : =(t), ϕν (t) f ( 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 (ω)ϕω (τ), (Ttτ f ) (t) ←F→( M ωτ F ) (ω), (Tt τ f ) (t) ←F→( M ωτ F ) (ω) F (ω ⊕ ν) ←F→ f (t)ϕν (t),
F (ω $ ν) ←F→ f (t)ϕν (t) ( Dων F ) (ω) ←F→( M tν f ) (t), ( Dων F ) (ω) ←F→( M tν f ) (t). and and i.e., i.e.,
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 (ω $ ν)
τ∈Ω ν∈Ω* 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(ω ), X1(ω ) ∈ L (Ω*, A lg(F)) and Y2 (ω ), H2 (ω ), X 2 (ω ) ∈ L (Ω*, A lg(F)) . Let y1(t) =( h1◊x1 ) (t) =∑ h1(τ)x1 (t ' τ) and Y2 (ω) =( H2♥X 2 ) (ω) = ∑ H2 (ν) 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 {H2♥X 2} = F −1 {H2} ⋅ F −1 {X 2}, c1(τ) = ( f1♣g1 ) (τ) = ∑ f1(t)g1 (t ' τ), and C2 (ω) = ( F2♠G2 ) ( ν ) = ω∑∈Ω* F2 (ω) G2 (ω $ ν ), t∈Ω then generalized Fourier transforms F and F −1 map ♣ - and ♠ -correlations into the products of 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},
c1(τ) =( f1♣g1 )(τ) ←F→C1(ω) =F1(ω) ⋅ G1(ω), ), c2 (t) =f2 (t)g2 (t) ←F→C2 (ω) =( F2♥G2 )(ω) .
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) ∈ Cand C(ω) ∈ C* then
(Ttτc) (t) =c(t ' τ) ∈ C, ∀Ttτ ∈ H G and ( DωνC ) (ω) = C(ω $ ν) ∈ C, ∀Dων ∈ H G* , respectively.
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
Gand 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= =[N Cod , k | A lg(F)] ⊂ L (Ω, A lg(F))
m =,m1,..., (m0 mk−1) c(t) =(c(0), c(
=[N Cod * , k | A lg(F)] ⊂ L (Ω*, A lg(F))
m =m1,..., (m0 , mk−1) C(t) =(C(0),C(
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(
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
H (ω) =( F h) (ω) =( H (0), H (
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.
Let H N be a finite Abelian group of order N =N1N2 ⋅ ⋅ ⋅ Nn .The fundamental structure theorem for finite Abelian group implies that we may write as the direct sum of cyclic groups, H N H N = ZN1 × ZN2 × ...× ZNn , where ZNl identified with the ring of integers ZNl under with respect to modulo Nl 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 Z⊕N2 τ2 ,...,tn Z⊕Nn τn ) .
HN* ZN1 The Fourier transforms in the space of all functions, defined on the finite Abelian group n H N = ⊕l=1 ZNl , and with their values in the finite commutative ring (field) or some finite algebra A has a great interest for digital signal processing. Denote this space as L ( H N , A lg (F)). Let εNl a primitive Nl –th root in the algebra A lg (F) .
Let
us
construct
the
following
functions
χkl (tl ) =εkNltll , kl
of all characters of the group H N can be describe by the following way
=0,1,..., Nl −1. They form the set of characters of the cyclic group ZNl . Then theset
χk (t) = χ(k1,k2 ,...,kn ) (t1,t2 ,...,tn ) = εkN11t1 εkN22t2 ⋅ ⋅ ⋅ εkNnntn , (
H*N l =k ⊕ m =(l1,l2 ,...,ln ) =(k1 ⊕ m1, k2 Z⊕N2 m2 ,..., kn Z⊕Nn mn ) .
HN* ZN1 The following matrix F = [χ k (t)]t∈HN ,k∈H*N forms Fourier transform on H N .
The set H*N is called the dual group. It forms ”frequency” domain. If initial group has the structure H N = ZN1 ⊕ ZN2 ⊕ ... ⊕ ZNn then the dual group has the same structure H*N = H N .Let us embed finite groups H N and H*N into two discrete segments Ω =[0, N − 1] and Ω* =[0, N − 1]
H N → Ω =[0, N − 1], H*N → Ω* =[0, N − 1], (
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, N2 ,..., Nn , Nn+1, where Nn+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 =N1N2 ⋅ ⋅ ⋅ Nn , can be uniquely expressed as n−1 n−i+1 t =(t1,t2 ,...,tn ) =t1( N2 N3 ⋅ ⋅ ⋅ Nn−1Nn ) + ... + tn−2 ( Nn−1Nn ) + tn−1 ( Nn ) + 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, Nn−1 −1], tn ∈[0, Nn −1]. The weights of ti is ∏ N j . j= n+1 The weight of tn is unity (Nn+1 = 1) .The radix-2 representation is t =tn−1 2n−1 + tn−2 2n−1 + ... + t1 21 + t0 20 = n−1 * = ∑tn−i 2i . Let t =(t1,t2 ,...,tn ) ∈ HN and (ω1, ω2 ,..., ωn ) ∈ HN i=0
n−1 n−i+1
k = ∑ kn−i ∏ N j define the maps (
i=0 j= n+1
The following operators (with respect to which all characters are invariant eigenfunctions)
n−1 n−i+1
then expressions ω = ∑ωn−i ∏ N j ,
i=0 j= n+1
(
HN ( Dωνχω ) (t) := χν (t) ⋅ χω (t) = χω ⊕ ν (t), ∀ν ∈ Ω*,
H*N and ( Dωνχω ) (t) := χν (t) ⋅ χω (t) = χω $ ν (t), ∀ν ∈ Ω*
H*N (
HN 1 k ⊕* m =(k1 ⊕N1 m1, k2 ⊕N2 m2 ,..., kn ⊕Nn mn ) ∈ Ω* =[0, N −1].
HN
Instead of spaces L (HN , 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) | HN ) and L (Ω*N , A lg(F) | H*N ) .
and
H*N invariant block codes
C⊂ L (Ω,A lg(F) | HN ) and C* ⊂ L (Ω*N ,A lg(F) | H*N ) are linear block codes with the property that if c(t) ∈ Cand C(ω) ∈ C* then (Ttτc) (t) =c(t ⊕ τ) ∈ C, ∀τ ∈ Ω and ( DωνC ) (ω) =C(ω ⊕* ν) ∈ C, ∀ν ∈ Ω* ,
HN HN respectively
It means that HN - and H*N - invariant block codes have ordinarygroup symmetries HypSym{C} HN and HypSym{C*} H*N . The seclass of codes are called the abelian group codes [13, 14-16]. Special cases of abelian group codes are 1) a cyclic code, when HN = ZN1 × ZN2 × ...× ZNn ≡ ZN is a cyclic group, 2) a dyadic code, when H2n = Z2 × Z2 × ...× Z2. In the first case F = ε Ntω t∈ZN ,ω∈Z*N is the ordinary Fourier transform,where εN a primitive N –th root in the algebra A lg(F) and in the second one F = ( −1) t|ω t∈H2n ,ω∈H*2n n the scalar products oftwo vectors t =(t1,t2 ,...,tn ) ∈ HN and (ω1, ω2 ,..., ωn ) ∈ H*N : t |ω = ∑ tiωi . i=1 is the Walsh transform, where t |ω is
Let F = =2tNε ε Ntω tN,ω−10
==ε2t(N2ω +1) tN,ω−10 =Then .
F (ω ) =(Ff ) (ω ) =∑f (t)ε 2−Ntε N−tω , f (t) =(F-1F ) (t) t∈Ω =∑F (ω )ε 2tNε Ntω ω∈Ω* is direct and inverse modulation Fourier transform, where ε 2N is a primitive 2N –th root in the algebra A lg(F) . According to definition 4 for ϕω (t) = ε 2tNε Ntω we have
Tˆtτ {ϕω (t)} = ϕω (t ( τ) = ϕω (τ) ⋅ ϕω (t) = ε(22Nω+1)τε(22Nω+1)t = ε(22Nω+1)(t+τ) ,
τ
Tˆ n {ϕω (t)} = ϕω (t ' τ) = ϕω (τ) ⋅ ϕω (t) = ε2−(N2ω+1)τε(22Nω+1)t = ε(22Nω+1)(t−τ).
But ε(22Nω+1)(t+N ) =ε(22Nω+1)N ε(22Nω+1)t =ε(2ω+1)ε(22Nω+1)t 2 =(−1)(2ω+1) ε(22Nω+1)t
τ =−ε(22Nω+1)t . Hence, Tˆtτ and Tˆ n are negacyclic (skew-cyclic) GSOs:
Tˆtτ {c(t)} =c1( (c0( τ , τ ,..., c(N −1)( τ ) =cτ+1,..., (cτ , 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) ).
τ τ They generate negacyclic (skew-cyclic) codes. Let F = =mtNε ε Ntω tN,ω−10 ==m(mNω ε +1)t tN,ω−10 =Then .
F (ω ) =(Ff ) (ω ) =∑f (t)ε m−Ntε N−tω , f (t) =(F-1F ) (t) t∈Ω =∑F (ω )ε mtNε Ntω ω∈Ω* is direct and inverse ε m−Nt -modulation Fourier transform, where ε mN is a primitive mN –th root in the algebra A lg(F) . According to definition 4 for ϕω (t) = ε mtNε Ntω we have
Tˆtτ {ϕω (t)} = ϕω (t ( τ) = ϕω (τ) ⋅ ϕω (t) = ε(mmNω+1)τε(m2Nm+1)t = ε(mmNω+1)(t+τ) ,
τ
Tˆ n {ϕω (t)} = ϕω (t ' τ) = ϕω (τ) ⋅ ϕω (t) = εm−(Nmω+1)τε(mmNω+1)t = ε(mmNω+1)(t−τ).
But ε(mmNω+1)(t+N ) =ε(mmNω+1)N ε(mmNω+1)t =ε(mω+1)ε(22Nω+1)t m
τ =εmε(mmNω+1)t . Hence, Tˆtτ and Tˆ n are constacyclic GSOs:
Tˆtτ {c(t)} =,c1( (c0( τ τ ,..., c(N −1)( τ ) =cτ+1 (cτ , ,..., cN −2 , cN −1, εmc0 , εmc1,..., εmcτ−1), τ τ Tˆ n {c(t)} =(c0' τ , c1' τ ,..., c(N −1)' τ ) =(εmcN −τ,..., ε mcN−2, εmcN−1 , c0 , c1,..., cN −(τ−1) ).
τ They generate constacyclic codes codes.
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 GSOinvariant codes with fast code and encode procedures based on fast generalized Fouriertransforms.
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”.