Question

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.

Was it helpful?

Solution

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.

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top