D:\User\sbornik_38_pdf\31.DVI


Mathematical Problems of Computer Science 38, 74{75, 2012.

P ar tition and Color ing in Design of Quasigr oup

E quipped E r r or -detecting Codes

G. Ma r g a r o v, Y . A la ve r d ya n

State Engineering University in Armenia

gmargarov@gmail.com, ealaverdjan@gmail.com

N o wa d a ys a d va n c e s in c o m m u n ic a t io n s a n d c o d in g t h e o r y r e s u lt in n e w c o d in g c o n c e p t s
r e in fo r c e d wit h m o r e e ± c ie n t d a t a s t r u c t u r e s , s u c h a s c o d e s o n g r a p h s . Cla s s e s o f e qu iv-
a le n c ie s o n g r a p h s g e n e r a t in g a s p e c ia l c la s s o f p e r m u t a t io n s , s o c a lle d c yc le s , m a y b e a
r e s e a r c h a r e a o f g r e a t c u r r e n t in t e r e s t b e s id e lo w-d e n s it y p a r it y c h e c k ( L D P C) c o d e s a n d
t u r b o c o d e s . In t h is p a p e r g r a p h p a r t it io n a n d c o lo r in g b a s e d g e n e r a t io n o f qu a s ig r o u p s fo r
d e s ig n in g e r r o r -d e t e c t io n c o d e s is p r o p o s e d . Th e m e t h o d m a ke s it p o s s ib le t o in t r o d u c e a
c la s s o f c o d e s , g e n e r a t e d b y qu a s ig r o u p s t r in g t r a n s fo r m a t io n s , wh ic h a r e e ± c ie n t a n d a lm o s t
r a n d o m .

L e t A d e n o t e t h e ¯ n it e s e t o f a g r a p h wit h n ve r t ic e s , a n d Sn is a g r o u p o f p e r m u t a t io n s
o n t h e s e t A c o n t a in in g n! n u m b e r o f d is t in c t p e r m u t a t io n s . L e t t h e s e r ie s o f 1 ; 2 ; :::; n
d e n o t e s t h e e le m e n t s o f A a n d a b in a r y r e la t io n R o n t h e s e t A, aRb, b e d e ¯ n e d fo r a ¯ xe d
p e r m u t a t io n ¾ if b = ¾k ( a ) fo r a n o n n e g a t ive in t e g e r k. Ob vio u s ly, R p r e s e n t s a n e qu iva le n c e
r e la t io n .

A s R is a r e la t io n o f e qu iva le n c y, it p a r t it io n s t h e s e t A in t o c la s s e s o f e qu iva le n c y. Fo r
e xa m p le , le t A = 1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 7 ; 8 p r e s e n t s t h e s e t o f ve r t ic e s o f s o m e s im p le g r a p h a n d

¾ =

Ã
1 2 3 4 5 6 7 8
4 3 2 7 8 6 1 5

!
.

Ob vio u s ly, t h e s e t o f c la s s e s o f e qu iva le n c y is ff1 ; 4 ; 7 g, f2 ; 3 g, f5 ; 8 g, f6 gg a c c o r d in g
t o r e ° e xivit y, s ym m e t r y a n d t r a n s it ivit y o f o r d e r e d p a ir s in t h e r e la t io n . Th e s e t o f c la s s e s
o f e qu iva le n c y is c a lle d a ls o t h e o r b it o f t h e p e r m u t a t io n Sn. A n e le m e n t a r y c la s s o f s u c h a
r e la t io n m a y b e in t r o d u c e d o n t h e b a s is o f b ip a r t it e g r a p h s wh ic h a r e b ic h r o m a t ic . S u c h a
c o lo r in g p a r t it io n s t h e g ive n g r a p h in t o t wo n o n in t e r s e c t e d s u b s e t s o f ve r t ic e s . To d e s ig n a n
e r r o r -d e t e c t io n c o d e a n d a qu a s ig r o u p o f a n a p p r o p r ia t e o r d e r , a s p e c ia l c la s s o f p e r m u t a t io n ,
a c yc le , is in t r o d u c e d a s fo llo ws : ¾c = ( a1; a2; a3; :::; ak ) is a c yc le , wh e r e ¾c ( ai ) = ai+1 fo r
i < k a n d ¾c ( ak ) = a1. Fo r e xa m p le , if ¾c = ( 1 ; 4 ; 6 ; 8 ) is a c yc le in S8, t h e n

¾c =

Ã
1 2 3 4 5 6 7 8
4 2 3 6 5 8 7 1

!
: ( 1 )

Th e p e r m u t a t io n g ive n in ( 1 ) m a y b e p r e s e n t e d a s a p r o d u c t o f c yc le s , wh ic h h a ve n o
c o m m o n e le m e n t s . Fo r t h a t p u r p o s e , ¯ r s t ly, t h e s e t A is p a r t it io n e d t o c la s s e s o f e qu iva le n c y.
Th e n we c h o o s e a n e le m e n t a a n d fo r m a c yc le a s fo llo ws : ( a; ¾ ( a) ; ¾2 ( a ) ; ¾3 ( a) ; :::; ¾k ( a) ) ,

7 4



G. Margarov, Y. Alaverdyan 7 5

wh e r e ¾k+1 = a. Th e s e c yc le s d o n o t c o n t a in c o m m o n e le m e n t s , a s c la s s e s o f e qu iva le n c ie s
d o n o t in t e r s e c t . E a c h e le m e n t in a c la s s m o ve s o n ly t h e it e m s in t h e g ive n c yc le . E ve n m o r e ,
t h e o r d e r o f c yc le s d o e s n 't a ®e c t t h e p e r m u t a t io n s o d e s ig n e d . Cyc le s wit h o n e e le m e n t a ls o
d o n o t a lt e r t h e p e r m u t a t io n a n d a r e s u b je c t t o fu r t h e r in ve s t ig a t io n , a s t h e y h a ve t o b e
t e s t e d fo r c a p a b ilit y t o d e t e c t e r r o r s .

Cyc le s s t a n d fo r a g o o d s t r u c t u r a l b a c kg r o u n d t o d e s ig n qu a s ig r o u p s o f a p p r o p r ia t e
o r d e r . Fo r t h e g ive n b ip a r t it e g r a p h G4;4 p a r t it io n e d t o c la s s e s ff1 ; 3 ; 5 ; 7 g; f2 ; 4 ; 6 ; 8 gg,
a qu a s ig r o u p o f o r d e r 8 c a n b e g e n e r a t e d a s fo llo ws :

Ta b le 1 : A Qu a s ig r o u p o f o r d e r 8
* 1 2 3 4 5 6 7 8
1 1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 1 2
3 5 6 7 8 1 2 3 4
4 7 8 1 2 3 4 5 6
5 8 7 6 5 4 3 2 1
6 2 1 4 3 6 5 8 7
7 4 3 8 7 2 1 6 5
8 6 3 2 1 8 7 4 3

Th e p e r m u t a t io n s o ve r ¯ n it e s e t s a r e c lo s e d a n d a s s o c ia t ive wit h r e s p e c t t o t h e b in a r y
o p e r a t io n o f c o m p o s it io n . Th e r e fo r e , t h e s e t o f a ll t h e p e r m u t a t io n s o ve r a ¯ xe d ¯ n it e s e t s
fo r m a g r o u p o ve r t h e o p e r a t io n o f c o m p o s it io n . Th u s , t h e c o m p o s it io n o f t h e t wo g ive n p e r -
m u t a t io n s r e s u lt s in n e w p e r m u t a t io n s a n d c yc le s a n d in t r o d u c e s n e w c la s s e s o f e qu iva le n c y.
Fo r e xa m p le , g ive n t wo c yc le s , ¾ = ff1 ; 3 ; 4 g; f2 ; 5 gg a n d ¿ = ff1 ; 2 g; f3 ; 4 g; f5 gg,t h e ir
c o m p o s it io n is a s fo llo ws :

¾ ± ¿ = ff1 ; 5 ; 2 ; 3 g; f4 gg:
Th is , in t u r n , p o in t s o u t t o t h e p o s s ib ilit y o f n o t o n ly in ve r t in g , b u t a ls o fa c t o r in g

p e r m u t a t io n s b y d e s ig n in g a h o m o m o r p h is m . Give n ( G; ²) a n d ( H; ¤) , wh e r e ² a n d ¤
a r e o p e r a t io n s o ve r g r o u p s G a n d H r e s p e c t ive ly, f : G ¡! H is a h o m o m o r p h is m , if
f ( g ² g0 ) = f ( g ) ¤ f ( g0 ) fo r a ll g; g0 in G. D e p e n d in g o n t h e t yp e o f t h e fu n c t io n f , we d e r ive
p a r t ic u la r t yp e s o f h o m o m o r p h is m . E r r o r -d e t e c t io n c o d e s u s in g qu a s ig r o u p s s o g e n e r a t e d ,
will e xp lo it t h e qu a s ig r o u p o p e r a t io n ¤ o n t h e s e t A. In o r d e r t o d e t e c t e r r o r s , we e xt e n d t h e
in p u t m e s s a g e a1 a2 a3 ::: an t o b lo c k a1 a2 a3 ::: an d1 d2 d3 ::: dn, wh e r e di = ai ¤ai+1 mod n,
i = 1 ; 2 ; 3 ; :::; n. A fu t u r e wo r k will b e d e d ic a t e d t o a s s e s s m e n t o f e ± c ie n c y o f t h e p r o p o s e d
m e t h o d ve r s u s e xis t in g r e s o lu t io n s .

R e fe r e n c e s

[1 ] Y u .M. Mo vs is ya n , Hyperidentities in algebras and varieties, U s p e kh i Ma t e m a t ic h e s kikh
N a u k, V o l.5 3 , N o . 1 ( 3 1 9 ) , 6 1 { 1 1 4 , 1 9 9 8 . E n g lis h t r a n s la t io n in R u s s ia n Ma t h e m a t ic a l
S u r ve ys 5 3 , 1 , 5 7 { 1 0 8 , 1 9 9 8 .

[2 ] I. A n d e r s o n , A ¯rst course in discrete mathematics, S p r in g e r -V e r la g , L o n d o n , 2 0 0 1 .

[3 ] J. Co o p e r , D . D o n o va n a n d J. S e b e r r y, Secret sharing schemes arising from L atin squares,
B u ll. In s t . Co m b in . A p p l., 12, 1 9 9 4 , 3 3 -4 3 .