D:\sbornik\...\transactions.DVI


Mathematical Problems of Computer Science 31, 28{39, 2008.

Lower B ound for E Capacity of Discr ete M emor yless

Channel with T wo-Sided State I nfor mation

Ma r ia m E . H a r o u t u n ia n a n d A r t h u r R . Mu r a d ya n

Institute for Informatics and Automation Problems of NAS of RA.
E-mail: armar@ipia.sci.am

Abstract

We study the channel with two-sided state information, a discrete memoryless chan-
nel with ¯nite input and output alphabets and random state sequence. Partial informa-
tion about the state sequence is available to the encoder and decoder. Applications of
this study include watermarking, data hiding, communication in presence of partially
known interferers. The capacity of this model was obtained by Cover and Chiang in [1].
In this paper the random coding bound of E-capacity is derived for considered model
which can be called also generalized channel with state information, as it includes four
possible situations of the channel with random parameter.

Refer ences

[1 ] T. M. Co ve r a n d M. Ch ia n g , \ D u a lit y b e t we e n c h a n n e l c a p a c it y a n d r a t e d is t o r t io n
wit h t wo -s id e d s t a t e in fo r m a t io n " , IE E E Transactions on Information Theory, vo l. 4 8 ,
n o . 6 , p p . 1 6 2 9 -1 6 3 8 , 2 0 0 2 .

[2 ] S . I. Ge l'fa n d a n d M. S . P in s ke r , \ Co d in g fo r c h a n n e l wit h r a n d o m p a r a m e t e r s " , P rob-
lems of Control and Information Theory, vo l. 9 , n o . 1 , p p . 1 9 -3 1 , 1 9 8 0 .

[3 ] C. E . S h a n n o n , \ Ch a n n e ls wit h s id e in fo r m a t io n a t t h e t r a n s m it t e r " , IB M J . R es,
D evelop, vo l. 2 , p p . 2 8 9 -2 9 3 , 1 9 5 8 .

[4 ] C. H e e g a r d a n d A . A . E l Ga m a l, \ On t h e c a p a c it y o f c o m p u t e r m e m o r y wit h d e fe c t s " ,
IE E E Transactions on Information Theory, vo l. IT-2 9 , n o . 5 , p p . 7 3 1 -7 3 9 , 1 9 8 3 .

[5 ] M. Co s t a , \ W r it in g o n d ir t y p a p e r " , IE E E Transactions on Information Theory, vo l.
2 9 , n o . 3 , p p . 4 3 9 -4 4 1 , 1 9 8 3 .

[6 ] P . Mo u lin a n d J.A . O'S u lliva n , \ In fo r m a t io n -t h e o r e t ic a n a lys is o f in fo r m a t io n h id in g " ,
IE E E Transactions on Information Theory, vo l. 4 9 , n o . 3 , p p . 5 6 3 -5 9 3 , Ma r . 2 0 0 3 .

[7 ] P . Mo u lin a n d Y . W a n g , \ Ca p a c it y a n d r a n d o m -c o d in g e xp o n e n t s fo r c h a n n e l c o d in g
wit h s id e in fo r m a t io n " , IE E E Transactions on Information Theory, vo l. 5 3 , n o . 4 , p p .
1 3 2 6 - 1 3 4 7 , 2 0 0 7 .

[8 ] E . A . H a r o u t u n ia n , \ On b o u n d s fo r E-c a p a c it y o f D MC" , IE E E Transactions on Infor-
mation Theory, vo l. 5 3 , n o . 1 1 , p p . 4 2 1 0 -4 2 2 0 , 2 0 0 7 .

[9 ] E . A . H a r o u t u n ia n , M. E . H a r o u t u n ia n a n d A . N . H a r u t yu n ya n , \ R e lia b ilit y c r it e r ia
in in fo r m a t io n t h e o r y a n d in s t a t is t ic a l h yp o t h e s is t e s t in g " , F oundations and Trends in
Communications and Information Theory, vo l. 4 , n o 2 -3 , p p . 9 7 -2 6 3 , 2 0 0 8 .

2 8



M. Haroutunian and A. Muradyan 2 9

[1 0 ] M. E . H a r o u t u n ia n , \ N e w b o u n d s fo r E -c a p a c it ie s o f a r b it r a r ily va r yin g c h a n n e l a n d
c h a n n e l wit h r a n d o m p a r a m e t e r " , Transactions of the Institute for Informatics and
Automation P roblems of the NAS of R A, M athematical P roblems of Computer Sciences,
vo l. 2 2 , p p . 4 4 -5 9 , 2 0 0 1 .

[1 1 ] M. E . H a r o u t u n ia n , \ E s t im a t e s o f E-c a p a c it y a n d c a p a c it y r e g io n s fo r m u lt ip le -a c c e s s
c h a n n e l wit h r a n d o m p a r a m e t e r " , L ecture Notes in Computer Science, vo l. 4 1 2 3 ,
S p r in g e r V e r la g , p p . 1 9 6 -2 1 7 , 2 0 0 6 .

[1 2 ] M. E . H a r o u t u n ia n a n d S . A . To n o ya n , \ R a n d o m c o d in g b o u n d o f in fo r m a t io n h id in g
E-c a p a c it y" , P roc. of IE E E International Symposium on Information Theory, p . 5 3 6 ,
U S A , Ch ic a g o , 2 0 0 4 .

[1 3 ] M. E . H a r o u t u n ia n a n d S . A . To n o ya n \ On e s t im a t e s o f r a t e -r e lia b ilit y d is t o r t io n fu n c -
t io n fo r in fo r m a t io n h id in g s ys t e m " , Transactions of the Institute for Informatics and
Automation P roblems of the NAS of R A, M athematical P roblems of Computer Science,
vo l. 2 3 , p p . 2 0 -3 1 , 2 0 0 4 .

[1 4 ] T. M. Co ve r a n d J. A . Th o m a s , E lements of Information Theory, W ile y, N e w Y o r k,
1 9 9 1 .

[1 5 ] I. Cs is z ¶a r a n d J. K Äo r n e r , Information Theory: Coding Theorems for D iscrete M emory-
less Systems, A c a d e m ic P r e s s , N e w Y o r k, 1 9 8 1 .

[1 6 ] I. Cs is z ¶a r , \ Th e m e t h o d o f t yp e s " , IE E E Transactions on Information Theory, vo l. 4 4 ,
n o . 6 , p p . 2 5 0 5 -2 5 2 3 , 1 9 9 8 .

ºñÏÏáÕÙ³ÝÇ íÇ׳ÏÝ»ñáí ÁÝ¹Ñ³ï ³é³Ýó ÑÇßáÕáõÃÛ³Ý Ï³åáõÕáõ
E-áõݳÏáõÃÛ³Ý ëïáñÇÝ ·Ý³Ñ³ï³Ï³ÝÁ

Ø. гñáõÃÛáõÝÛ³Ý ¨ ². Øáõñ³¹Û³Ý

²Ù÷á÷áõÙ

Ø»Ýù áõëáõÙݳëÇñáõÙ »Ýù »ñÏÏáÕÙ³ÝÇ íÇ׳ÏÝ»ñáí ϳåáõÕÇ, ³ÛÝ ¿ í»ñç³íáñ
ÙáõïùÇ ¨ »ÉùÇ ³Ûµáõµ»ÝÝ»ñáí ÁÝ¹Ñ³ï ³é³Ýó ÑÇßáÕáõÃÛ³Ý Ï³åáõÕÇ, áñÁ ϳËí³Í
¿ íÇ׳ÏÝ»ñÇ å³ï³Ñ³Ï³Ý ѳçáñ¹³Ï³ÝáõÃÛáõÝÇó: ìÇ׳ÏÝ»ñÇ Ñ³çáñ¹³Ï³ÝáõÃÛ³Ý
Ù³ëݳÏÇ ÇÝýáñÙ³óÇ³Ý Ñ³ë³Ý»ÉÇ ¿ Ïá¹³íáñÇãÇÝ ¨ ³å³Ïá¹³íáñÇãÇÝ: ²Ûë
áõëáõÙݳëÇñáõÃÛáõÝÝ»ñÁ ÏÇñ³éíáõÙ »Ý ÇÝýáñÙ³óÇ³Ý Ã³ùóÝáÕ, çñ³ÝßáÕ Ñ³Ù³Ï³ñ·»ñáõÙ:
²Ûë Ùá¹»ÉÇ áõݳÏáõÃÛáõÝÁ ëï³óí»É ¿ Îáí»ñÇ ¨ âÇ³Ý·Ç ÏáÕÙÇó: ²Ûë Ñá¹í³ÍáõÙ ¹áõñë ¿
µ»ñíáõÙ E-áõݳÏáõÃÛ³Ý å³ï³Ñ³Ï³Ý Ï»¹³íáñÙ³Ý ·Ý³Ñ³ï³Ï³ÝÁ ¹Çï³ñÏí³Í Ùá¹»ÉÇ
ѳٳñ, áñÁ ϳñ»ÉÇ ¿ ³Ýí³Ý»É ݳ¨ íÇ׳ÏÝ»ñáí ÁݹѳÝñ³óí³Í ϳåáõÕÇ, ù³ÝÇ áñ ³ÛÝ
Ý»ñ³éáõÙ ¿ å³ï³Ñ³Ï³Ý å³ñ³Ù»ïñ»ñáí ϳåáõÕáõÙ ãáñë Ñݳñ³íáñ Çñ³íÇ׳ÏÝ»ñÁ: