8
$\begingroup$

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?

$\endgroup$
  • 16
    $\begingroup$ Are you familiar with the pigeonhole principle? Because it's trivial to reduce this question to that. $\endgroup$ – MSalters Jul 18 at 14:03
  • 11
    $\begingroup$ This doesn't seem to be at all about encryption $\endgroup$ – ilkkachu Jul 18 at 17:05
  • 1
    $\begingroup$ @ilkkachu It's about coding theory, which can be loosely considered to be in the field of cryptography. I would say questions on that topic can certainly be on-topic here. I'm on the fence whether this particular question is though... $\endgroup$ – marcelm Jul 19 at 1:11
  • 1
    $\begingroup$ @marcelm, no, look at the dictionary definition from e.g. Wiktionary: "encryption: The process of obscuring information to make it unreadable without special knowledge, key files, and/or passwords". Or the short snippet under the "encryption" tag on the site. $\endgroup$ – ilkkachu Jul 19 at 6:59
  • 3
    $\begingroup$ @ilkkachu Cryptology is far wider than just encryption. Quoting the wikipedia article on Coding Theory: "Codes are used for data compression, cryptography, ...", and the crypto.SE help center: "... and subsidiary topics that generally make up cryptology ...". I maintain that questions on coding theory are on-topic here. In fact, crypto.SE has a coding-theory tag. $\endgroup$ – marcelm Jul 19 at 9:11
25
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Not to challenge your statements, which are correct, but now you have me pondering whether you can correct something you can't detect in quantum cryptography. I'm thinking there may be situations where you have enough information to know how to correct a signal, but you disrupt the communication if you try to actually detect it. $\endgroup$ – Cort Ammon Jul 18 at 19:00
  • $\begingroup$ @CortAmmon It's the same idea. You can test (...somehow, don't ask me the specifics) whether a given qubit has been tested before, and know whether it was looked at -- but in doing so, you're 'sacrificing' that bit of information. You also can't check what it used to be without, again, sending more information somehow. That might be in the same qubit, of course, but then you're still using some transmitted information. This is a fundamental property of information in general, not of classical memory. $\endgroup$ – Nic Hartley Jul 18 at 21:57
9
$\begingroup$

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.)

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice points. Yes, the already available symbol places are not data and may be used for parity checks. Your last paragraph essentially indicates a higher layer protocol which uses information outside the defined channel. $\endgroup$ – kodlu Jul 19 at 4:38
  • $\begingroup$ Thank goodness. “In general”, for k bits where all 2^k encodings are USED and EQUIPROBABLE you need extra bits. But often many encodings are not used - e.g. in many computer instruction sets and datatypes. Even if all are used, if they are not equiprobable you may compress using a variable length code, and then add error checking bits to that. So the average number of bits may be less than or equal to k, although some low probability compressed encodings + error bits may be larger. This really amounts to distinguishing the k physical bits from the number of bits of information carried by them. $\endgroup$ – Krazy Glew Jul 26 at 5:07
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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