GO Classes | CSE Course | Computer Networks

Question

Let $k$ be minimum number of bits needed to correct all possible $t$ bits error then which of the following condition must satisfy?

 

• A. $2^{n-k} \geq \dbinom{n}{1} + \dbinom{n}{2} + \cdots + \dbinom{n}{t}$
   
• B. $2^{n} \geq 1 + \dbinom{n}{1} + \dbinom{n}{2} + \cdots + \dbinom{n}{t}$
   
• C. $2^{n-k} \geq 1 + \dbinom{n}{1} + \dbinom{n}{2} + \cdots + \dbinom{n}{t}$
   
• D. $2^{k} \geq 1 + \dbinom{n}{1} + \dbinom{n}{2} + \cdots + \dbinom{n}{t}$
   

Comments

Simply the number of binary strings that can be generated by using parity bits should address all the possible combinations of errors!!

Answer 1

Think of it as we have $t$ bits of error, and as the question is saying that we have to correct all $t$-bit errors, then in that case the parity bits (denoted here as $k$)

should be able to produce all possible combinations so as to signal uniquely which bit (or set of bits) is faulty in the codeword.  

The total different signals that can be generated is:  

\[
2^k
\]

Now this should be able to cover all the possible error signals. The types of error signals we can have are:  

- Error in none of the bits: $1$ signal for this case.  
- Error in exactly $1$ bit: $\binom{n}{1}$, where $n$ is the length of the codeword.  
- Error in exactly $2$ bits: $\binom{n}{2}$  
- Error in exactly $3$ bits: $\binom{n}{3}$  
- $\;\;\vdots$  
- Error in exactly $t$ bits: $\binom{n}{t}$  

Hence, all of them should be uniquely signaled with the help of the parity bits. Therefore, the condition becomes:  

\[
2^k \;\;\geq\;\; 1 + \binom{n}{1} + \binom{n}{2} + \binom{n}{3} + \cdots + \binom{n}{t}
\]