1
$\begingroup$

I am trying to understand code distance, but I am not sure regarding the following scenario:

Assume that you have an information word M with m bits, that You code into a coding word using the following procedure:

  1. You take M and code it using a code you know nothing about. But you do know that its distance(code's distance) is k, and that k>2.
  2. You add to the word obtained in the last step a parity bit.

If you know that k is odd, does it necessarily mean that the distance of the code constructed by those two steps is necessarily k+1?

Well, I am not sure here. Code distance is basically the number of different bits, and the meaning of the second step in the procedure(adding a parity bit) is, according to my understanding, allowing the detection of any odd number of errors. Does it necessarily mean that the code constructed by those two steps is necessarily k+1?

$\endgroup$
  • $\begingroup$ After adding a parity bit, all codewords have even weight. In particular, the minimum distance is even. $\endgroup$ – Yuval Filmus Jan 21 '20 at 1:46
0
$\begingroup$

Normally a code's hamming distance is limited to some maximum message length. For example in the case of a 32 bit CRC, for Hamming distance = 3 (2 bit error detection), the maximum length for a message is 2^32-1 bits (including the 32 bits of CRC), depending on the CRC used. With a larger message, a 2 bit error can fail. For a parity check or Hamming distance = 2 (1 bit error detection), there is no maximum length limit.

If the message length is <= maximum message length for that Hamming distance, and k is odd (maximum # of error bits detected is even), then adding a parity check in addition to the CRC should increase Hamming distance to k+1.

For example, CRC16 based on polynomial x^16 + x^12 + x^5 + 1 (0x11021) is the product of 2 irreducible polynomials : (x^15 + x^14 + x^13 + x^12 + x^4 + x^3 + x^2 + x + 1) (0xf01f) and (x + 1) (0x3). For message length (including CRC bits) CRC poly (x^15 + x^14 + x^13 + x^12 + x^4 + x^3 + x^2 + x + 1) Hamming distance is 3 for message length up to 32767 (2^15-1) bits, and the (x + 1) term increases this to Hamming distance 4. As mentioned above, it can detect any odd number of bit errors for any length message.

$\endgroup$
0
$\begingroup$

Let $m_1,m_2$ be any two different codewords of $M$, and let $m'_1,m'_2$ be the codewords after adding a parity bit. Since $M$ has minimum distance $k$, the distance between $m_1,m_2$ is at least $k$. If their distance is at least $k+1$, then $m'_1,m'_2$ are at distance at least $k+1$. If the distance between $m_1,m_2$ is exactly $k$, then they have different parities (since $k$ is odd), hence the distance between $m'_1,m'_2$ is exactly $k+1$. This shows that the minimum distance of the new code is exactly $k+1$.

$\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.