Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I have gone through error detection and correction techniques like Hamming codes, and 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.
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.)
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:
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.
It is not possible to implement error correction without adding parity bits. However, in some cases it may be possible to 'steal' some bits from some other part of the protocol. This is what is done with the FEC implementations for Ethernet.
Let's take 10GBASE-R Ethernet as an example. 10GBASE-R Ethernet without FEC is transferred using the 64b/66b line code - 64 bit data blocks are scrambled with an LFSR, then a 2 bit sync header is attached to each block, and the data is sent serially at 10.3125 Gbps. The 10GBASE-KR FEC is designed to add forward error correction while maintaining the same data rate of 10 Gbps before encoding and 10.3125 Gbps on the wire. This is done by taking 32 blocks 64b/66b encoded data, stripping off one of the sync bits on each block to free up 32 bits, adding 32 parity bits of shortened cyclic code (2112, 2080), scrambling the result, and then sending that on the wire at 10.3125 Gbps.
There are trade-offs to this approach, though: since the sync headers have been effectively removed, the block lock time is vastly increased (the PHY needs to check up to 2112 blocks at 2112 bits each instead of 66 blocks of 66 bits each), extending the time required to bring a link up by several orders of magnitude.
The newer Ethernet Reed-Solomon FEC does something similar, but with an even larger block size. 64b/66b data is transcoded four blocks at a time into 256b/257b, 20 257 bit blocks are broken up into 514 10 bit symbols, those are encoded with RS(528,514) to generate 14 10-bit parity symbols for 528 total symbols, which are then packed up and sent as a 5280 bit block. The original data, encoded with 64b/66b, would also take up 66*4*20 = 5280 bits.
This depends a lot on the data, if there are many symmetry groups, like in visual data, you can apply very useful Wavelet Transforms on it, compressing it by a very high degree without a loss of information, at the same time the Wafelet methods always use a scaling functions to only store a small fraction of information in lots of different scales, this way they are very robust, if for example some information got lost in some scales, they just recover that information from different scales with a minimum error on that information, if at all. At the same time, a you can build your own Wavelet, having a good encryption from not sharing the exact methods of your Wavelets, only you can decompose it.
