Notes on M&M clock recovery

12.03.2015 8:48

M&M (Mueller and Müller) clock recovery is the name of one of the signal processing blocks in GNU Radio. Its task is to recover samples from a signal with the same frequency and phase as those used by the transmitter. This is necessary, for instance, when you want to extract symbols from an asynchronous digital signal. It allows you to synchronize your receiver with centers of ones and zeros present in the signal.

Searching the internet, the way this block works seems to be mostly regarded as black magic by users of GNU Radio. There's very little concrete information on how it works and more importantly, how to make it work in your particular use case since the block takes several parameters. The best I could find were some guesses and some suggestions on which values to try.

This is my attempt to clarify things a bit. I don't claim to completely understand the algorithm though. What's written bellow is my current understanding that I got foremost from studying the source. The academic paper that is cited by GNU Radio source points you to a trail of citations that leads all the way to the original 1976 paper describing the method. I have only read a small part of this literature. As it usually happens, it turned out to be a quite poor substitute for proper software documentation.

M&M Clock Recovery block from GNU Radio

The meat of the implementation is the following loop in general_work() method in clock_recovery_mm_ff_impl.cc. Note that I'm talking about the floating point implementation. There is also a complex number implementation, which should work in a very similar fashion, but I haven't looked into it.

while(oo < noutput_items && ii < ni ) {
  // produce output sample
  out[oo] = d_interp->interpolate(&in[ii], d_mu);
  mm_val = slice(d_last_sample) * out[oo] - slice(out[oo]) * d_last_sample;
  d_last_sample = out[oo];

  d_omega = d_omega + d_gain_omega * mm_val;
  d_omega = d_omega_mid + gr::branchless_clip(d_omega-d_omega_mid, d_omega_lim);
  d_mu = d_mu + d_omega + d_gain_mu * mm_val;

  ii += (int)floor(d_mu);
  d_mu = d_mu - floor(d_mu);
  oo++;
}

First of all, this code immediately shows some general characteristics of the algorithm, as it is implemented in GNU Radio. All this might seem very obvious to some, but none of it is clearly stated anywhere in the documentation:

  • This is a decimation block. It will output one sample per one or more input samples. Specifically, it will output a sample that it thinks is the center of the symbol. This can be the first source of confusion, since nothing in the name of the block suggests decimation.

  • The decimation rate is not constant. It varies with what the block thinks the current symbol clock is. This is important in context of GNU Radio since many things start behaving weirdly with streams that do not have a constant sample rate (like for instance the Scope instrument with multiple inputs).

  • The signal must have zero mean. The algorithm works by observing sign changes on the signal (the slice() method is basically a signum function).

  • There is some sample interpolation involved. d_interp->interpolate() is a FIR interpolator with 8 taps. This means that output can contain values not strictly present in the input.

The code also gives some insights into the meanings of the somewhat cryptically named parameters:

  • Omega is symbol period in samples per symbol. In other words, it is the inverse of the symbol rate or clock frequency. The value given as the block parameter is the initial guess.

  • The limits within which the omega can change during run time depend on the initial omega and the relative limit parameter. For instance, with omega = 10 and omega_relative_limit = 0.1, the block will allow the omega to change between 9 and 11. Note that until version 3.7.5.1, relative limit was actually absolute due to a bug.

  • Mu is the detected phase shift in samples between the receiver and transmitter. The initial value given as the block parameter doesn't matter in practice, since it's usually impossible to guess the phase in advance. Internally, phase is tracked between 0 to omega (corresponding to 0 and 2π). However, because of the way the code is implemented, you can only set the fractional part of the initial value (i.e. up to 1.0)

  • Mu gain and omega gain are gains in two feedback loops that adjust frequency and phase during run time. Their effect varies with the amplitude of the input signal. Values that are optimal for a signal that goes from -1 to +1 will not work for an identical signal that goes from -10 to +10.

Based on the code above, this is how the M&M clock recovery block samples the input signal. You can imagine that a sine wave on the picture below represents a digital signal of a series of binary ones (>0) and zeros (<0) that has been filtered through a filter. Mu is the distance between the first sample and time zero. Omega is the distance between two consecutive samples:

Illustration of M&M clock recovery algorithm variables.

Finally, if you look at how the code adjusts the omega and mu during run time (through the mm_val value), you can see that:

  • Feedback loop doesn't work on square signals. The method depends on the fact that the center of the symbol is the crest. With a square signal there is no difference between the edge of a symbol and its center and hence the feedback loop has no means of positioning the sampling point.

  • The algorithm will not track phase on perfectly symmetrical input. Consider the sine input above: if the frequency (omega) is perfectly adjusted, the error term will always be zero, regardless of the sampling phase (mu). This is important for instance when constructing artificial test cases for debugging, but it might also cause problems for cases where you want to synchronize on a periodic header (e.g. many packet-based transmissions prefix data with such a synchronization header).

In conclusion, this block is tricky to get right. In fact, after a lot of experimenting, I have failed to make it consistently work better than a straight-forward blind decimator. Note that with an accurate enough estimate of the symbol rate and a low-pass filter in front that matches the symbol rate, an ordinary non-synchronized decimator will do reasonably well. For instance in short packet-based transmissions, you might lose some packets if they arrive with a particularly unfavorable phase difference, but overall the results will look passable.

I suspect many reports of successful usage of the M&M clock recovery block are due to this fact and not because the algorithm worked particularly well. In my experience, a heuristical approach to clock recovery works better (for instance like the one implemented in the capture process in am433 and ec3k receivers). While not as scientific and more computationally complex, its performance is more consistent and hence easier to debug and write unit tests against.

Finally, I also suspect the algorithm in GNU Radio is plagued by some practical implementation problems. It looks very much like the interpolator doesn't work as it should (there was no answer yet to my my question on discuss-gnuradio regarding that). While I haven't investigated it thoroughly, I also think that the code might lose phase tracking between consecutive calls to the general_work() method (only fractional part of the phase is retained between calls). These might happen more or less often depending on how the block is placed in the flow chart and might cause intermittent desynchronizations.

Posted by Tomaž | Categories: Code

Comments

Thanks a lot for this info!
I'm just getting started with GNU Radio and have been playing around with the various blocks in the companion GUI trying to demodulate FSK transmissions.
Some of the implementations I've seen (one you've linked in this article) recommended using the clock recovery block.
I've been stunned by the lack of documentation for GNU Radio in general. It's like you're just meant to know automatically what module will do. Is it really that hard to write a one sentence description of the general block function, and, if you're feeling generous, one for each input, output and parameter?!
Combine that with the mysteries behind this specific block, and sometimes I'm absolutely lost.

Now that you've explained the issues associated with C_R_MM, I'm going to experiment with the parameters and see if I can get some cleaner outputs.

Posted by Rowan

"This means that output can contain values not strictly present in the input."

This may be just what I was looking for! My decoder is seeing extra symbols that I can't visually account for in the signal and it's been driving me nuts for a while now. I don't know if you're up for re-visiting this blog post but can you confirm that you're simply saying that there may be extra symbols in the MM block output that aren't actually in the signal?

This is a fantastic post. Thanks!

Posted by Butterworth

Butterworth, what I mean with "output can contain values not strictly present in the input" is that, for example, if you feed the M&M block with an input stream that contains only values -1.0 and 1.0, you can get values other than -1.0 and 1.0 in the output stream.

This is because the block uses a FIR interpolator to estimate signal values between individual samples. It does not choose the sample closest to the estimated clock edge.

Also, the FIR interpolator uses 8 past samples of the signal for estimation. It is not a simple linear interpolation. This means that if you have a -1.0 to 1.0 square wave on the input, the interpolator might even produce values outside of the -1.0 to 1.0 range.

Posted by Tomaž

The two commits here:

https://github.com/awalls-cx18/gnuradio/tree/symbol_sync

add two symbol_sync_mm blocks to GNURadio which fix the implementation
problems in the existing clock_recovery_mm blocks.

The loop gains are now expressed in damping factor ( < 1 is underdamped,
= 1 is critically damped, > 1 is overdamped) and normalized loop bandwidth
(ranges between 0.0 and 0.5, but numbers close to 0.0 are what you want).
For symbol clock recovery, one probably want something overdamped,
with the damping factor at say 1.0, 1.5, or 2.0.

A pull request has been issued:

https://github.com/gnuradio/gnuradio/pull/1157

Regards,
Andy

Posted by Andy

Excellent write-up, Tomaž: thanks! I don't suppose you'd like to cover all the other GNU Radio blocks? :D

Add a new comment


(No HTML tags allowed. Separate paragraphs with a blank line.)