Polyphase filters and non data aided timing synchronization!

In case of no data aided synchronisation methods, Early/Late Gate clock recovery method is used to get an estimate of the offset between transmit and receive symbol timing. This method uses 3 samples per symbol – one at the optimal sample time, one that is 1 sample delayed and 1 that is one sample advanced. 

“This approach works by setting up two filterbanks; one filterbank contains the signal’s pulse shaping matched filter (such as a root raised cosine filter), where each branch of the filterbank contains a different phase of the filter. The second filterbank contains the derivatives of the filters in the first filterbank. Thinking of this in the time domain, the first filterbank contains filters that have a sinc shape to them. We want to align the output signal to be sampled at exactly the peak of the sinc shape. The derivative of the sinc contains a zero at the maximum point of the sinc (sinc(0) = 1, sinc(0)’ = 0). Furthermore, the region around the zero point is relatively linear. We make use of this fact to generate the error signal. If the signal out of the derivative filters is d_i[n] for the ith filter, and the output of the matched filter is x_i[n], the error is calculated as: e[n] = (Re{x_i[n]} * Re{d_i[n]} + Im{x_i[n]} * Im{d_i[n]}) / 2.0 This equation averages the error in the real and imaginary parts. There are two reasons we multiply by the signal itself. First, if the symbol could be positive or negative going, but we want the error term to always tell us to go in the same direction depending on which side of the zero point we are on. The sign of x_i[n] adjusts the error term to do this. Second, the magnitude of x_i[n] scales the error term depending on the symbol’s amplitude, so larger signals give us a stronger error term because we have more confidence in that symbol’s value. Using the magnitude of x_i[n] instead of just the sign is especially good for signals with low SNR. The error signal, e[n], gives us a value proportional to how far away from the zero point we are in the derivative signal. “

1. It is said that “the filters corresponding to the early and late gate filters are trivially the polyphase segments (k – 1) and (k + 1) when testing polyphase segment (k).”  what is theory behind this .

2. Suppose I have a 256:1 decimation filter with an input sampling frequency of 256 kHz with total of 256*8 taps (Or 256 filter banks with 8 tap each). These are linear phase FIR filters, each filter bank having a data rate of 1 khz. Consider following two scenario:

i) I start with Polyphase filter bank index 1 and carry on convolving input data and roll over polyphase bank index at 256.

ii) I start with Polyphase filter bank index 2 and roll over polyphase bank index at 256.How does this result in timing adjustment ?  

There are many parts to above questions and it will be good to understand them separately.

a) First to understand how early late gate works in terms of getting a timing estimate ?    At this stage ignore polyphase filters etc.
So you have a simple system which uses a matched filter to transmit a signal and a matched filter to receive a signal. Assume that you are using a matched filter which is box shaped.
Upon correlation you have a triangle like shape. The correct sampling time is the peak and the two samples to
 the left and right can be used to estimate the error.

b) Next concept to understand:    Using a regular filter (no polyphase), we can change the index of the filter and get a timing change.    How to see this:    Normally the sequence is like this:  

output1 =  x0*f0 + x1*f1 + x2*f2 + x3*f3 + x4*f4  

output2 = x1*f0 + x2*f1 + x3*f2 + x4*f3 + x5*f4 
How to make output2 almost same as output1? change the index of the filter:
 new_output2 = x1*f1 + x2*f2 + x3*f3 + x4*f4 +x5*f0

Only the last term is different from what we wanted in terms of timing change.
This error is small and will only last for the symbol where we made the timing correction.

c) Finally let us look at polyphase filters.    A polyphase filter is nothing but a filter. It only has a faster implementation.It is mostly used in decimation/interpolation. This is a extension of the above.

Now extend example above for timing correction using regular filter.

Divide normal filter into polyphase sub filters. So, normal filter { f0 f1 f2 f3 f4 f5} is divided into three polyphase sub filters as P0 ,P1,P2.

P0 = {f0, f3} P1 = {f1, f4} P3 = {f2, f5}. And applied same principle of changing filter bank index. You will get one term difference with timing corrected output. question now is shouldn’t output2 in this example be exactly same as ouput1 ? 

Shouldn’t Y(Advanced) to be exactly same as Y(1) in this example.

D1,D2,D3 are three delay lines.

State 1 : At Time t = -1

P0 = {f0, f3} D1 = {x2, x5} P1 = {f1, f4}D2 = {x1, x4} P3 = {f2, f5} D3 = {x0, x3}Output from each sub filter y0 = f0*x2 + f3*x5 y1 = f1*x1 + f4*x4 y2 = f2*x0 + f5*x3 Final ouputY(-1) = y0 + y1 +y2 = f0*x2 + f3*x5 + f1*x1 + f4*x4 + f2*x0 + f5*x3

State 2 : At Time t = 0

Next sample x6 goes into delay line and oldest sample is flushed out of delay line.

P0 = {f0, f3} D1 = {x1, x4} P1 = {f1, f4}D2 = {x0, x3}P2 = {f2, f5} D3 = {x6, x2}Output from each sub filter

y0 = f0*x1 + f3*x4 y1 = f1*x0 + f4*x3 y2 = f2*x6 + f5*x2 Final ouputY(0) = y0 + y1 +y2 = f0*x1 + f3*x4 + f1*x0 + f4*x3 +f2*x6 + f5*x2

State 3 : At Time t = 1

Next sample x7 goes into delay line and oldest sample is flushed out of delay line.

P0 = {f0, f3} D1 = {x0, x3}P1 = {f1, f4} D2 = {x6, x2}P2 = {f2, f5} D3 = {x7, x1} Output from each sub filter y0 = f0*x0 + f3*x3 y1 = f1*x6 + f4*x2 y2 = f2*x7 + f5*x1

Final ouput Y(1) = y0 + y1 +y2 = f0*x0 + f3*x3 + f1*x6 + f4*x2 + f2*x7 + f5*x1

Change filter bank index If you change filter index at State 2 , you will have following configuration.

P0 becomes P2, P1 becomes P0 and P2 becomes P1.

P0 = {f2, f5} D1 = {x1, x4}P1 = {f0, f3} D2 = {x0, x3} P2 = {f1, f4} D3 = {x6, x2}

Output from each sub filter y0 = f2*x1 + f5*x4 y1 = f0*x0 + f3*x3 y2 = f1*x6 + f4*x2

Final ouputY(Advanced) = y0 + y1 + y2 = f2*x1 + f5*x4 + f0*x0 + f3*x3 +f1*x6 + f4*x2

Y(Advanced) is same as Y(1) except one term is diffrent.

Now is the time to think about Interpolation. Let’s understand this.

You are receiving 10 samples .
After matched filtering you get output samples of y0,y1,y2…y9

When you receive a timing error you want to get samples y0+delta,y1+delta etc…y9+delta. The “delta” is less than a sample.

What are the methods:
A) Take y0,y1,y2,y3…y9. Upsample by a factor of 100 (say). That is put 99 zero’s between y0 and y1 and y2 etc.
Now use a perfect interpolation filter and generate samples between y0 and y1 and between y1 and y2…upto y9. So,you have z0,z1,z2… z900. Decimate this output by 100 at the ‘correct’ phase to get desired output with the timing change.

B) But the operation above is wasteful in that it is generating samples we will throw away.That is we are generating z0 to z900, but we will use only say z2,z102,z202 etc.So why not only generate z2,z102…z202.

Ignore polyphase, how can you do this?

Notice that z2 = some filter operating on y0,y1,y2…y9.The zeros in between do not effect the output. So, z2 = filter2 operating on y0,y1,y2…y9
z3 = filter3 operating on y1,y2,y2…y9
where the coefficients of filter2 and filter3 are different. At this time, there is no glitch.

So what does this mean in terms of an algorithm:
When there is a timing change use a different set of coefficients to generate the output.

When the timing change is so much that you have ‘drop’ an input sample, or ‘zero stuff’ and input sample you have a glitch.

C) finally you can use the matched nyquist filter as an interpolation filter and do the matched filtering and interpolation in one go instead of a two step process described here. And the process of using different filter coefficients is done using a polyphase filter.

~~ cheers ~~ Dheeraj