1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Yes, inverting the bits changes things. For a better test of this, feed it all 0's and then feed it all 1's. $\endgroup$ – Jim Clay Mar 5 '13 at 15:08
  • $\begingroup$ @Jim Clay I might have asked my question wrong. Simply, does invert(viterbi(data)) produce the same result as viterbi(invert(data))? Thanks by the way, you saved my life many times. $\endgroup$ – groove Mar 5 '13 at 15:31
2
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • 3
    $\begingroup$ I don't think the argument about an all-ones input producing an all-ones output is correct. Consider, for example, the simple ad nauseam code with generator $$G(x) = [1 + x^2, 1 + x + x^2]$$ for which an all-ones input produces output $$11~ 10~ 01 ~01 ~01 \cdots $$ $\endgroup$ – Dilip Sarwate Mar 5 '13 at 19:01
  • $\begingroup$ @DilipSarwate You're right. I've edited the answer. $\endgroup$ – Jim Clay Mar 5 '13 at 19:13
  • $\begingroup$ "The generator polynomials that do produce an all 1's output have odd Hamming weights for both polynomials." The odd weight requirement might be necessary but is it sufficient? Consider the (systematic) code with $$G(x) = [1, 1+x+x^2]$$ where both polynomials have odd Hamming weight. The response to all-ones must be $$11~ 10~ 11 ~ 11 ~ 11 \cdots$$ right? $\endgroup$ – Dilip Sarwate Mar 5 '13 at 21:26
  • $\begingroup$ @DilipSarwate Yes, there is at the very beginning a blip when you are shifting out the initial zeros in the state memory. I was talking about the steady state behavior. $\endgroup$ – Jim Clay Mar 5 '13 at 22:08
  • 1
    $\begingroup$ @groove In the steady state your generator polynomials will produce all 1's, but Dilip makes a valid point that at the beginning they will produce some zeros, so the inversion equivalence does not hold at the beginning. $\endgroup$ – Jim Clay Mar 6 '13 at 13:40

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.