Mfcttrf

I have gone through error detection and correction techniques like hamming codes, BCH codes require extra parity bits for detection and correction. While sending data, we always seem to introduce error correction by adding parity and use parity while checking for errors.

Can error detection and correction be done without adding any extra bits?

In general, no. Let us say you have a data vector $x$ of $k$ bits and one bit is flipped by an error. There is no way of detecting, let alone correcting this, unless the errored data vector $x'$ is not another valid data vector.

If the errored vector $x'$ is not a valid data vector and you can do detection, then all $k$ bits cannot be used as arbitrary data bits, thus your data rate is less than $k$ bits, implying you are using parity in some sense.

More simply, if there are no parity bits, all $2^k$ data vectors are valid, and thus all errors result in another valid data vector, making all errors undetectable.

Since correction is harder than detection, the same argument rules out correction as well.You can't correct if you can't detect.

For the general case kodlus answer explained it is not possible. For detecting or correcting errors you need to have redundancy. But many kind of information have included redundancy:

• Some file formats have a fixed header


• Some file formats/protocols only use part of the available symbol space


• Some information only allow certain information in certain context


• ...

A typical way to detect errors in transmission in protocol that only allow 7-bit-ASCII codes was/is to use the 8th bit as parity bit. So you remove redundant information and substitute it with information that allow error-detection or even error-correction.

Or if you send request of type a and expect response of type A but get a response of type B, you know that something went wrong.

No, because of the Pigeonhole Principle.

Let's say you want to be able to send arbitrary $k$-bit messages. There are $2^k$ possible bit-patterns, and $2^k$ possible intended messages.

Now let's say you want to add error correction. This means that, on top of the $2^k$ correct messages that you want to be able to send, you also want to be able to send some number of incorrect messages (that will get detected and fixed at the other end). Each incorrect message must be distinguishable from every valid message, or else there'd be no way to correct it.

But there are only $2^k$ bit-patterns available; if you want to be able to distinguish $2^k$ correct messages, plus some additional number of incorrect messages, you'll need more than $k$ bits.

(Adding one bit for parity, for example, gives $2^k+1$ possible patterns, enough for $2^k$ correct messages and $2^k$ incorrect messages.)