0
$\begingroup$

I have been struggling with the below question for quite some time, and I don't have a pointer to move forward.

A certain Error Control Coding scheme using block codes takes an input block (dataword) of 500 bits and appends a 50 bit code to produce a 550 bit codeword which is then transmitted across channel that causes individual bits to flip with a probability of 0.1 independently. The pairwise Hamming distances between all the codeword pairs is so large that the probability of an error occurring that converts one to the other can be neglected, except as follows: two codewords C 1 and C 2 have a Hamming distance of 10, and two codewords C 3 and C 4 have a Hamming distance of 6. Assuming no knowledge about what datawords may be more or less likely to be desired to transmit, what is the probability that a given block transmission will be corrupted by the channel but the error will go undetected by the receiver? You may answer with an expression, but the answer has to be completely numerical (no symbols).

My thought process about this question is that the probability needs to be calculated as such : Pr(Selecting either C1 or C2) * P(error in C1 or C2) + Pr(Selecting either C3 or C4) * P(error in C3 or C4).
I feel the Pr(error) is given by a binomial distribution of 55CX(0.1)^x(0.9)^550-x where X=10 or 6.

First, am I thinking about the problem correctly ? If yes , how do i derive the probability of selection of a particular codeword ?

Edit: I don't have the exact source per se, because this question is from a random uni final exam that I found on the internet. I am prepping for my own exam, and came across this question.

$\endgroup$
3
  • $\begingroup$ Please edit the question to credit the original source where you encountered this problem. $\endgroup$
    – D.W.
    Commented Dec 12, 2019 at 5:54
  • $\begingroup$ If you found the exam on the Internet, I encourage you to link to it. In academia, it is good to get into the habit of citing your sources. $\endgroup$
    – D.W.
    Commented Dec 12, 2019 at 17:33
  • $\begingroup$ @D.W., I honestly don't remember where I got it from. I will make sure to keep this in mind when I am posting the next question! $\endgroup$
    – NoNeural
    Commented Dec 12, 2019 at 17:40

1 Answer 1

1
$\begingroup$

I think your approach is fine, but the question is not fully well-defined (unless I'm missing something).

The general error probability is $$\sum_{i} \Pr(C_i\text{ is transmitted})\Pr(\text{error}\mid C_i\text{ is transmitted}).$$ The questions explicitly says that the error probability of all codewords except $C1,C2,C3,C4$ is negligible, so the error becomes:

$$\sum_{i\in\{1,2,3,4\}} \Pr(C_i\text{ is transmitted})\Pr(\text{error}\mid C_i\text{ is transmitted}).$$

Computing the error probability is easy: if the Hamming distance is $x$, it takes $\lfloor x/2\rfloor +1$ bit-flips (or more) to corrupt the codeword, and $x$ bit-flips (or more?) to be undetected by the receiver. You can easily compute that in a similar way to what you wrote, and get a reasonable bound. However, the question explicitly says that the terms $\Pr(C_i\text{ is transmitted})$ are unknown, yet it requires you to give an exact numerical answer. contradiction.

$\endgroup$
4
  • $\begingroup$ Thanks for your answer. Unfortunately, that's the whole question. So I am going to keep this thread alive in the hope that someone can figure the missing part out :) $\endgroup$
    – NoNeural
    Commented Dec 14, 2019 at 0:42
  • $\begingroup$ Without the distribution of datawords there is no answer. Maybe the question means for the "worst case" scenario, hence take the maximum over $i$ of $\Pr(\text{undetectable err} | C_i\text{ is transmitted})$. This upper bounds the probability of receiver error regardless of the data distribution. $\endgroup$
    – Ran G.
    Commented Dec 14, 2019 at 8:52
  • $\begingroup$ How could I calculate this upper bound ? Would this mean that the probability of transmitting any of these codewords is 1 ? $\endgroup$
    – NoNeural
    Commented Dec 14, 2019 at 14:01
  • $\begingroup$ Right, if the worst codeword is transmitted with probability 1, your failure probability is maximized. $\endgroup$
    – Ran G.
    Commented Dec 14, 2019 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.