2

Hamming distance is said to be the number of bits that differ between two codewords. If two code words differ by a distance of d, then up to d-1 bit flips can be detected.

The example given for such an explanation is as follows:

Assume two codewords c1 and c2 where c1 = 10110 and c2 = 10011. Here, the Hamming distance d = 2. 
So I can detect up to 2 bit errors because flipping three bits **will result in another valid codeword, so an error can't be detected**

My question is, how do we even know what the list of possible codewords even are to begin with? Isn't the transmitter free to send any data it wants? How do we know in real time, what the codewords are? In the previous example, if I do a 2 bit flip, I get 11010 - what if this was a valid code word?

Here is an excerpt from the book Computer Networks Fifth Edition by Tanenbaum and Wetherall

How do we even know what the legal codewords are?

In most data transmission applications, all 2^m possible data messages are
legal, but due to the way the check bits are computed, not all of the 2^n possible
codewords are used. In fact, when there are r check bits, only the small fraction
of 2^m /2^n or 1/2^r of the possible messages will be legal codewords. It is the
sparseness with which the message is embedded in the space of codewords that allows
the receiver to detect and correct errors

1
  • 1
    "How do we even know what the legal codewords are?" Various layer-1 protocols use different encoding, and you need to know the specific encoding to know what are valid symbols for that encoding. For example 4B5B encoding has 16 valid symbols from 32 possible symbols. There is a dictionary that translates the four data bits to the five-bit symbols. There are many different encoding schemes.
    – Ron Maupin
    Feb 15, 2023 at 1:58

2 Answers 2

1

how do we even know what the list of possible codewords even are to begin with?

The valid codewords are defined by the line code implementation, they are agreed upon by all users. For Ethernet, encoding/decoding happens in the PCS sublayer and may be assisted by scrambling in the PMA sublayer.

  • 100BASE-X uses 22 valid symbols out of the 32 possible ones for 4b/5b as defined in 802.3 clause 24.2.2 (borrowed from FDDI).
  • 1000BASE-X uses 8b/10b (from ANSI INCITS 230-1994, borrowed from Fibre Channel) as defined in 802.3 clause 36.2.4.
  • And so on.

Obviously, the valid symbols are selected to leverage Hamming distances.

When an Ethernet physical layer variant uses forward error correction, the encoding is also defined in the IEEE 802.3 standard.

3

you have to design a code that defines what the valid list is (or how valid code words should be computed). This usually works by having your code insert some additional bits into the data, so that the desired hamming distance is achieved. It is usually called an error correcting code. An example of such code is Hamming code.

Basically the transmitter takes whatever should be sent, and then encodes it - i.e, it computes valid code words based on the definition of the code. The receiver then receives code words, validate/corrects errors and then decodes the original message.

3
  • A Hamming distance may be used for error detection as well, not only for error correction.
    – Zac67
    Feb 21, 2023 at 12:36
  • @Zac67 every error correcting code can do error detection of 2x as many errors as it can correct. if your hamming distance is short enough it can only do detection. AFAIK the math is the same, and it is just called ECC, not EDC.
    – Effie
    Feb 22, 2023 at 7:53
  • the very basic principle, one can correct an invalid code word if the hamming distance to one valid code word is smaller than to any other code word, and only detect error, if hamming distance to more than one valid code work is the same.
    – Effie
    Feb 22, 2023 at 7:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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