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.
Answer

Interview Answer

8 Answers

0

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.

1

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
0

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
0

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
0

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
0

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
0

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.