Thursday, August 23, 2018

New ideas for TDoA multi-lateration

(1) Finding the common propagation mode

Let's consider the case of three receivers receiving the same signal.
  • Each receiver receives the signal at times t1, t2, t3.
  • The cross-correlations produce time differences Δt1,2, Δt1,3, Δt2,3.
  • Trivially, Δt1,2 = Δt1,3 - Δt2,3 (and cyclically) (*)
This situation is illustrated in the plot below.

Common propagation mode

As a second step let's consider the situation when one of the three receivers receives the common signal via two propagation paths, and the cross-correlations to the signals received at the two other receivers have approximately the same magnitude.

Currently the TDoA software performs for each cross-correlation a clustering algorithm, and in the situation shown in the plot below it may well be that the following time differences are obtained: Δt1,2 = -50, Δt1,3 = -100, Δt2,3 = -140. Note that these do not fulfill the identity (*).

Two propagation modes for one receiver

As a consequence, a trivial stage of pre-processing is given by selecting those cross-correlation peaks which are consistent according to (*).

Update 9/22/2018

(2) Using constraints (number of degrees of freedom)

Now let us count the number of degrees of freedom for the case of N receivers receiving the same signal: there are
  • 2 unknowns, (lat,lon), for the most likely position
  • N unknown virtual heights of which only (N-1) are observable in the time differences (adding a common time offset does not change Δti,j)
  • N(N-1)/2 hyperbolæ (=constraints)
Note that instead of virtual heights we might as well add time offsets δt to the time differences, Δti,j+δtj, j≠1, and in this way become agnostic w.r.t. the specifics of ionospheric propagation.

As a summary there are N+1 unknowns and N(N-1)/2 constraints:

#receivers #unknowns #constraints #constraints-#unknowns
3 2(pos)+2(δtj, j≠1) 3 hyperbolæ -1
4 2(pos)+3(δtj, j≠1) 6 hyperbolæ 1
N 2(pos)+(N-1)(δtj, j≠1) N(N-1)/2 hyperbolæ N(N-1)/2-N-1

So for 3 receivers there is a 1-dimensional family of solutions while for N≥4 receivers the system of equations is overdetermined.  This sounds good enough to make me suspicious if it is indeed true.

It will be interesting to try these ideas on real data obtained from KiwiSDRs. If anyone spots an error in the logic above please do let me know.

When using N stations there are N-1 independent measurements contained in the time differences δtij, j>i. Two of these are needed to determine the likely position, so N-3 out of the N-1 δti, i≠1, can be found:

#receivers #unknowns #measurements #fixed/total δtj
3 2(pos)+2(δtj, j≠1) 2 time differences 0/2
4 2(pos)+3(δtj, j≠1) 3 time differences 1/3
5 2(pos)+4(δtj, j≠1) 4 time differences 2/4
6 2(pos)+5(δtj, j≠1) 5 time differences 3/5
N 2(pos)+(N-1)(δtj, j≠1) (N-1) time differences (N-3)/(N-1)

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.