Suppose that we want to send a time signal over a noisy channel with a poor signal to noise ratio. We assume white Gaussian noise here and no processing power limit at the receiver. We also make the normal assumption that the power is the square of the signal strength. We also assume that there are very good clocks at either end and that there are no doppler effects, or that such effects are precisely known. We assume no multi-path transmission thru the channel. We want merely to synchronize the two good clocks and latency due to processing in the receiver is not important. Latency in the channel is assumed known or perhaps discovering that channel latency is the whole purpose of the exercise.

Some function much like this is necessary for any data channel since transmitting data requires bit level synchronization. For data synchronization there is the additional conundrum of the receiver knowing that now is the time to synchronize, and the transmitter problem of knowing that the receiver needs to synchronize. We ignore those problems here.

GPS is fundamentally a time transmitting application. The transmitted data are largely in support of synchronization.

A transmit power limit is not the same as a transmit energy limit. Perhaps a powerful spike would achieve synchronization, violate a power limit yet conform to an energy limit. I would like to know.

Sending a single spike, whose repetition would conform to the power (signal strength) limit, would be unrecognizable at the receiver since frequent noise spikes would exceed it. Sending a train of equally spaced spikes can conform to the power limit but the receiver will be unable to discriminate between these spikes and the spike interval exceeds the desired synchronization error.

Sending a random pattern of D 0’s and 1’s known to the receiver may do the trick using correlation at the receiver. This also provides selective access. A passive attack is thwarted if the pattern is otherwise unknown, but interception of many transmissions may reveal the secret. For this sort of security the pattern must be changed each time. See garage.

Some Math

We quantize time with the integral subscript n. Nn is the real valued noise which we take to be independent random normal deviates with 0 mean and unit variance. Sn is the real valued signal. Since we want to finish synchronizing we will assume that Sn = 0 unless 0≤n<D in which case |Sn|=1. D is some positive integer which is the duration of the time signal. The input to the receiver algorithm is Rn = s∙Sn + Nn for some range that includes the range 0≤n<D. s2 is the signal to noise ratio.

There is a terminology problem—perhaps it more accurate to say that this code, so far, assumes bit level synchronization and attempts to identify the bit. I.e. we deal for now only in integer values of the subscripts.

For independent random variables, the variance of the sum is the sum of the variances. When the clocks are not synchronized (j≠k) Sj and Sk are independent. Let Vn = Σ[0≤j<D]Rn+jSj be the correlation of Rn with Sn. In the following the expectation operator E is over the space of possible noises, not the space of possible signals. Indeed we have postulated no distribution over the possible signals we might use. Note that E(Nn+jSj) = 0.
E(Vn) = E(Σ[0≤j<D]Rn+jSj)
= Σ[0≤j<D]E(Rn+jSj)
= Σ[0≤j<D]E((s∙Sn+j + Nn+j)Sj)
= Σ[0≤j<D]E(s∙Sn+jSj + Nn+jSj)
= Σ[0≤j<D](s∙E(Sn+jSj) + E(Nn+jSj))
= Σ[0≤j<D](s∙E(Sn+jSj))
= s∙Σ[0≤j<D]E(Sn+jSj)

E(Sn+jSj) = Sn+jSj since S does not depend on the noise and thus
E(Vn) = s∙Σ[0≤j<D](Sn+jSj) = s∙Cj
where Cj = Σ[0≤j<D](Sn+jSj).

E(V0) = D∙s and for n≠0 E(Vn) = s∙Σ[0≤j<D](Sn+jSj) is determined by our choice of signal. I think that we can do better than random, even though most synthetic choices are worse than random. I would guess that choosing Sk to minimize max[n≠0]Cn would be optimal because the threshold test looks for the maximum value of Vj.
Averaged over possible choices of signal, E(Vn) = 0 for n≠0, but E(max[n≠0]Cn) is much greater.

C0 = D and Cj = 0 for |j|>D. C is small for most randomly chosen signals but not for periodic signals.
Choosing S to minimize max[n≠0]Cn is a curious problem.

Some Code

Plan: Do long overlapping correlations on the input with pattern. Size of overlap is length of pattern. We copy code from Fast Fourier Transform (fft); and random normal deviate.

Here is the code. We assume a shared secret noise burst sk of length D. We consider rp time intervals each of length CS beginning at multiples of CS−D. CS is a power of 2. The noise plus signal therein is R[i] with 0≤i<rp*(CS−D)+D. We place the signal beginning at ro which is a number we know but the receive code tries to discover (note restricted scope of ro). P is the signal strength which is less than the noise level which is 1.


M is where we put the pattern and examine the signal for diagnostics. Routine cc is only for diagnostics and simply computes the correlation between the pattern and the signal at some particular point of interest. This corroborates the more complex general calculation.