Definition of achievable rate

Definition of achievable rate

by Yuxuan Wang -
Number of replies: 4

Hi, in the last week we talk about the achievable rate and there are two definitions about it, which seems to be contradictory:



Is there details that I did not notice? 

Thanks for your attention.

In reply to Yuxuan Wang

Re: Definition of achievable rate

by Reka Inovan -

Hi Yuxuan,

I am not sure which two definitions that you refer to?
Could you point me out to these definitions and why it seems contradictory?

Best,
Reka

In reply to Reka Inovan

Re: Definition of achievable rate

by Yuxuan Wang -

sorry, it seems the image has lost in my post. The first definition shows in Monday lecture note is:

R_1,R_2 is achievable if \forall \epsilon \exists enc_1, enc_2, dec, s.t.:
rate(enc_1)<=R_1
rate(enc_2)<=R_2
p_{error}<\epsilon

While in Tuesday, it is:

R_1,R_2 is achievable if \forall \epsilon \exists enc_1, enc_2, dec, s.t.:

rate(enc_1)>=R_1
rate(enc_2)>=R_2
p_{error}<\epsilon

I am not sure which one is correct.

In reply to Yuxuan Wang

Re: Definition of achievable rate

by Reka Inovan -

I see what you mean. The achievable rates differ because they corresponds to different problems.
But the problems are superficially similar, so I can see why it leads to confusion.

On Monday, we study the distributed source coding problem. In this setting, we have two user A and B.
They want to compress their source sequence so it can be recovered by a receiver. These users does not communicate with each other.
In this setting, we assume that the link between the users and the receiver are completely reliable.
Then the problem becomes "what's the minimum rate that needs to be send to the receiver by each users".
Now, you can see why the achievability theorem is expressed as a lower bound to these rates.
As it is rather obvious that if we can compress a message into rate R, then we can also do it with rate R', R' > R.
So in a sense, here we study a characteristic of the sources.

On Tuesday, we study the multiple-access problem. We still have two users and a receiver. But then we assume that the channel between them is not reliable.
So the question becomes, "what is the maximum rate that I can send reliably using this unreliable channel".
Then the achievability result becomes an upper bound to the rates. Because of course if you can send reliably with a rate R, sending a rate lower than R is easy.
So this differs from the previous setting, as here we study a characteristic of the communication channel.

I hope it helps,
Best,
Reka