D:\sbornik\...\doc.DVI


Mathematical Problems of Computer Science 33, 41{47, 2010.

On Computation of Lower B ound of E Capacity for

the Channel with T wo-Sided State I nfor mation

A r t h u r R . Mu r a d ya n

Institute for Informatics and Automation Problems of NAS RA

Abstract

In this paper a discrete memoryless channel (DMC) with 2 sided state information
is examined in the sense of computations of capacity formulas and random-coding
exponents. It is shown that computation of channel capacity and lower bound of E
capacity requires a huge amount of computational resources and is rather slow when
implemented with traditional methods. Techniques are described how to massively
parallelize the computations by means of GPGPU and obtain substantial acceleration.

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 ] M. H a r o u t u n ia n , A . Mu r a d ya n , \ L o we r b o u n d fo r E c a p a c it y o f d is c r e t e m e m o r yle s s
c h a n n e l wit h t wo -s id e d s t a t e in fo r m a t io n " , 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. 3 1 , p p . 2 8 -3 9 , 2 0 0 8 .

[3 ] D . L u e b ke , G. H u m p h r e ys , \ H o w GP U s wo r k" , IE E E Computer, 2 0 0 7

[4 ] R . W a n g , N . Go o d n ig h t , G. H u m p h r e ys , \ Co m p u t a t io n o n p r o g r a m m a b le g r a p h ic s
h a r d wa r e " , IE E E Computer Graphics and Applications, 2 0 0 5 .

[5 ] J. H e n n e s s y; D . P a t t e r s o n , \ Co m p u t e r a r c h it e c t u r e : a qu a n t it a t ive a p p r o a c h " , IS B N
1 -5 5 8 6 0 -7 2 4 -2 , 3 r d e d it io n , 2 0 0 3 .

[6 ] G. Mo o r e , \ Cr a m m in g m o r e c o m p o n e n t s o n t o in t e g r a t e d c ir c u it s " , E lectronics, vo l. 3 8 ,
n o 8 , 1 9 6 5 .

[7 ] J. Owe n s , D . L u e b ke , \ A s u r ve y o f g e n e r a l-p u r p o s e c o m p u t a t io n o n g r a p h ic s h a r d wa r e " ,
Computer Graphics F orum, vo l. 2 6 , n o 1 , p p . 8 0 -1 1 3 , 2 0 0 7 .

[8 ] M. H a r r is , \ Ma p p in g c o m p u t a t io n a l c o n c e p t s t o GP U s " , International Conference on
Computer Graphics and Interactive Techniques, n o 5 0 , 2 0 0 5 .

[9 ] D . Ib a r o u d e n e , \ P a r a lle l p r o c e s s in g " , Ch a p t e r 1 , Mo t iva t io n a n d H is t o r y. S t Ma r y's
U n ive r s it y, S a n A n t o n io , 2 0 0 8 .

[1 0 ] T. Co r m e n , C. L e is e r s o n , R . R ive s t , C. S t e in , \ In t r o d u c t io n t o a lg o r it h m s " , IS B N 9 7 8 -
0 -2 6 2 -0 3 2 9 3 -3 , MIT P r e s s , 2 0 0 1

4 1



4 2 On Computation of Lower Bound of E Capacity for the Channel with Two-Sided State Information

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

²ñÃáõñ Øáõñ³¹Û³Ý

²Ù÷á÷áõÙ

²ß˳ï³ÝùÁ ÝíÇñí³Í ¿ ÁÝ¹Ñ³ï ³é³Ýó ÑÇßáÕáõÃÛ³Ý »ñÏÏáÕÙ³ÝÇ íÇ׳ÏÝ»ñáí
ϳåáõÕáõ ѳٳñ ݳËÏÇÝáõÙ ëï³óí³Í ³ñ¹ÛáõÝùÝ»ñÇ Ñ³ßí³ñÏÙ³ÝÁ: гÛïÝÇ
áõݳÏáõÃÛ³Ý µ³Ý³Ó¨Ç ¨ E-áõݳÏáõÃÛ³Ý å³ï³Ñ³Ï³Ý Ïá¹³íáñÙ³Ý ·Ý³Ñ³ï³Ï³ÝÇ
ѳßí³ñÏÙ³Ý Ñ³Ù³ñ å³Ñ³ÝçíáõÙ ¿ ϳï³ñ»É ÑëÏ³Û³Ï³Ý ù³Ý³Ïáí ·áñÍáÕáõÃÛáõÝÝ»ñ:
гßí³ñÏÝ»ñÇ Å³Ù³Ý³ÏÁ ¿³å»ë Ïñ׳ï»Éáõ Ýå³ï³Ïáí ѻﳽáïí»É »Ý ï³ñµ»ñ
ÙÇç³í³Ûñ»ñ ¨ ³é³ç³ñÏí»É ¿ Ù»Ãá¹ ·áñÍáÕáõÃÛáõÝÝ»ñÁ Ñݳñ³íáñÇÝë ½áõ·³Ñ»é³óÝ»Éáõ
ѳٳñ: òáõÛó ¿ ïñí»É, áñ ÝٳݳïÇå ѳßí³ñÏÝ»ñÇ Ñ³Ù³ñ ·ñ³ýÇÏ³Ï³Ý ë³ñù»ñÇ
û·ï³·áñÍáõÙÁ ï³ÉÇë ¿ ³é³íáÉáõÃÛáõÝ ³ÛÉ ÙÇçáóÝ»ñÇ Ýϳïٳٵ: гٻٳïáõÃÛáõÝÝ»ñÁ
ϳï³ñí»É »Ý ûñÇݳÏÇ íñ³ ¨ ѳßí³ñÏÝ»ñÁ ·ñ³ýÇÏáñ»Ý å³ïÏ»ñí»É »Ý: