Viterbi Decoder - How does inverting the input bits affect the result?

Question

Does converting zeros into ones and ones into zeros in the input stream affect the decoding result? Empirically I have seen that it does not affect, decoding $[0 1 0 1 \ldots]$ and $[1 0 1 0 \ldots]$ produce the same output stream. But I am not sure if it is true or not, and I am looking for a theoretical proof.

Why I am doing this is because the convolutionally encoded stream (rate $\frac{1}{2}$ and constraint length 7) is received without the phase information, thus a conversion is needed. I am trying to determine in which step I should convert the data.

I would appreciate if you could share any knowledge.

Answer 1

Convolutional codes are linear in the Galois{2} (i.e. binary) field. We know this because the convolution operation is linear. The fact that Viterbi codes are linear has a few implications. First, if you input all 0's you will get all 0's out. Second, if you add two inputs together the output will be the sum of their individual outputs.

The last piece of information that we need for a very informal "proof" is that when you input all 1's the output is all 1's (EDIT: this is not always true- see the edit at the bottom of the answer). We see that this must be so because the encoder state is constant (you are, after all, inputting all 1's) so the output must be constant. The output cannot be 0's because that would match the all 0's case which would make the code non-linear (other than in the trivial case where the encoder always outputs 0 no matter what the input is).

Now that we've established that inputting all 1's causes the output to be all 1's we can prove that yes, inverting the input is equivalent to inverting the output.

$$ Input => Output\\ Input + Ones => Output + Ones $$

If we assume the first statement then the second statement follows due to linearity and all 1's producing all 1's, with the understanding that binary inversion is equivalent to adding 1. 0 + 1 = 1, 1 + 1 = 2 = 0.

EDIT: Dilip is correct. For some generator polynomials an all 1's input will produce an all 1's output and so inverting the input is equivalent to inverting the output. For some generator polynomials, though, an all 1's input will not produce an all 1's output, so inverting the input is not equivalent to inverting the output. The generator polynomials that do produce an all 1's output have odd Hamming weights for both polynomials. The reason that Dilip's polynomial does not meet the criteria is that one of the polynomials ($1 + x^2$) has an even Hamming weight.

EDIT 2: Dilip makes a valid point that even polynomials with odd Hamming weights will produce some zeros at the beginning while the zeros in the state memory are shifted out and replaced with ones. This is relatively brief, but it does mean that the inversion equivalence does not hold during that time. It does hold during the "steady state" behavior.