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