Sunday, August 5, 2018

Detection of k=7 r=1/2 convolutional codes

We start with a random binary sequence xi which is encoded using a k=7 r=1/2 convolutional decoder into
  yI = [u0,v0,u1,v1,...]  ,
  ui = ajxi+j and vi = bjxi+j  ,
where "+" denotes XOR and repeated indices are summed over from 1 to 7.

The property used to find a,b is the following:
  bjuj+i = ajvj+i  .   (*)

For this we start with the full state space of 127×127 values of a,b. For each pair (ui, vi) the property (*) is evaluated and states which fail it are pruned from the search space.

The screen shot below shows the output of a simple octave script demonstrating this approach where further details of this algorithm can be found. For an encoded random bit sequence, after consuming about 28 encoded bits yI, (i.e., 14 iterations), the correct a,b values are found.

Output of signal-analysis/m/test_conv.m

This method must be already known and I would be grateful if someone showed me a reference to it.