Qualcomm Interview Question: Given a wireless channel with... | Glassdoor

Interview Question

Senior Systems Engineer Interview San Diego, CA

Given a wireless channel with loss rate 0.1, what's the

  throughput one can get with retransmission.

Interview Answer

8 Answers


It can modeled as binary symmetric channel.
As to my understanding, channel capacity can be acheived with perfect feedback and simple retransmission scheme, so i guess the answer is 1-H(0.1).

Jun on Apr 29, 2012

This post has been removed.
Please see our Community Guidelines or Terms of Service for more information.


Interviewer was correct. With probability 0.1 you have one retransmission, with probability (0.1)^2 you have two, etc., since you can also lose the retransmitted packets, reducing the throughput to approximately 0.89.

aa on Aug 2, 2012

It is equivalent to simply a binary erasure channel with erasure probability 0.1, whose capacity is 1-0.1 = 0.9.

aa should re-learn information theory and stochastic process

chris on Aug 8, 2012

First of all I don't think it has anything to do with the capacity of BSC. Note that h(0.1) = 0.46 and that means 1 - h(0.1) is roughly 0.5. If the packet error rate is 10% then BER is in the order of 0.1 / N where N is the length of the packet in bits. For that, the capacity of BSC is almost 1.

In any case, in the non-ergodic case I believe the throughput is less than 0.9.

Assume you want to send packets p_1, p_2, ..., p_k and each one takes N_1, N_2, ..., N_k time slots. Then, define the k-Packet Throughput (I made it up) as follows

k-packet Throughput = (k / (N_1 + N_2 + ... + N_k)).

Note that this throughput is a random variable. We can define the throughput based on this as the expected value of k-packet Throughput with respect to random variables N_1 , N_2, ...

E[k-packet throughput] = E[ k / (N_1 + N_2 + ... +N_k)] 8' from the law of large numbers we have N_1 + N_2 + ... + N_k -> k E[N] = 1 / 0.9 * k.

This suggests that k-packet throughput is a random variable which converges to its mean for large k, but for a finite k, its average is less than 0.9

All in all, I would have answered the question the way you did. In the long run, out of N transmissions you have 0.9 received and therefore the throughput should be 0.9

Anonymous on Dec 17, 2012

Model the problem based on the average number of transmissions it takes to deliver a packet. Let N be the number of transmissions. Then:

Pr[N=1] = 0.9
Pr[N=2] = 0.1*0.9
Pr[N=3] = 0.1*0.1*0.9

and so on. The expected number of transmissions per packet is:

E[N] = Sum{ k*Pr[N=k] }
   = 1*Pr[N=1] + 2*Pr[N=2] + 3*Pr[N=3] + ...

where the summation index k goes from 1 to infinity.

Then the throughput is 1/E[N] packets per transmission, which is 0.896...

Eric on Jul 16, 2014

In the last solution, the number is calculated incorrectly. Accurate calculation gives the expected number of transmissions per packet E[N] = 1.11111, so that 1/E(N)=0.9, which corresponds to the reduction of transmission rate by exactly 10%, as suggested earlier.

Dmytro on Mar 9, 2015

p=0.1 - probability of a packet transmission failure
If we transmit a sequence of N packets with retransmission then an expected number of successfully transmitted packets will be E[N]=p*E[N-1]+(1-p)*(E[N-1]+1)=(1-p)+E[N-1], and as E[0]=0 it easy to solve the recursion: E[N]=N*(1-p)
Expected number of successfully transmitted packets per one transmitted packet will be C[N]=E[N]/N=(1-p).
The channel capacity is limit of C[N] as N approaching to infinity that is clearly equal to 1-p=0.9

Eugene on Sep 23, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.