Effects of parity bit on odd code length regarding its size after alternation

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

You know that two different valid codes have a distance of at least three bits, so you need at least three bit changes to turn a valid code into a different valid code.

But making exactly 3 changes gives a different parity. 4 changes = same parity, 5 changes = different parity etc. So if you add the parity bit, the code + parity has a minimum distance of 4 bits, not 3. This means you can either detect all three bit changes instead of all two bit changes, or you can correct all single bit changes and at the same time detect all double bit changes (risking that a triple error is “corrected” in the wrong way) instead of correcting all single bit changes (and risking that a double bit change is “fixed” incorrectly).

If you had started with a code with even Hamming distance then I can’t quite see how adding a parity bit would be very useful.