Clocks are ubiquitous in digital communications systems; real-life clocks are noisy, i.e., their signals are not perfectly periodic, which often leads to a significant degradation of the performance of communications systems. In the early days of communications, this source of degradation was only of secondary concern. Communications systems used to operate far from the ultimate performance bound, i.e., channel capacity. The main concern was therefore to develop error-correcting techniques that could close the gap between the performance of practical communications systems and channel capacity.

 

With the recent advent of iterative decoding techniques, communications systems nowadays most often operate close to the ultimate performance limits; issues such as synchronization, which were earlier only of secondary importance, have now become the mayor (remaining) bottlenecks in the design of communications systems.

 

In this dissertation, we focus on carrier-phase synchronization, i.e., the alignment of the phase of the local oscillator in the receiver to the phase of the incoming carrier. The questions we address are:

 

1. Which physical mechanisms are responsible for phase noise? How can phase noise be modeled?

 

2. How can carrier-phase estimation algorithms systematically be derived?

 

3. What are the ultimate limits for communication over channels with phase noise?
    In particular:

​

         a. How much does the information rate of a communications channel decrease due to phase noise?

         b. How well can the (noisy) carrier phase be estimated?

In contrast to earlier and parallel work, our aim is not the design and optimization of fully operating communications systems. In this thesis, various tools are developed that lead (or may lead) to an answer to the above questions (and many other related questions).

​

We give a detailed analysis of phase noise in free-running clocks and PLLs (Question 1). We propose a simple intuitive model for phase noise in free-running oscillators. We describe two simple models for passband communications channels. The models take phase offsets into account between the received carrier and the local carrier in the receiver, but disregard timing offsets. In the first model, the phase is constant, in the second, the phase performs a random walk. We investigate under which conditions the two models are valid. Most methods of this thesis will be illustrated by means of both channel models.

​

Most methods we propose in this dissertation are based on graphical models, more precisely, factor graphs. Factor graphs are used to visualize the structure of the system at hand. They represent the factorization of multivariate functions. Each edge in the graph corresponds to a variable, each node corresponds to a factor. Factor graphs can represent any function, in particular, probabilistic models, error-correcting codes, block diagrams and other common models in communications, signal processing and beyond.

​

We show how factor graphs can be used as a tool to develop practical estimation and detection algorithms. Our techniques can be applied to model-based signal processing (e.g., phase estimation) and machine learning. In particular, we formulate several standard signal-processing and machine-learning algorithms as message passing on factor graphs, e.g., particle methods, gradient methods, decision-based methods, and expectation maximization. In all those algorithms, local rules are applied at the nodes in a factor graph. In other words, the (global) estimation and detection problem is tackled by a divide-and-conquer strategy: the global computation is carried out by multiple (simple) local computations. The local message update rules may be used as building blocks for novel estimation and detection algorithms. By listing the possible update rules at each node in the factor graph, one can systematically explore novel algorithms. We demonstrate this idea by deriving phase estimation algorithms for the constant-phase model and the random-walk phase model (Question 2). We also show how the back-propagation algorithm for the training of feed-forward neural networks follows by applying generic message-passing rules on a suitable factor graph. We elaborate on the computation of kernels in the light of message passing on factor graphs.

​

We demonstrate how message-passing algorithms for inference (in particular, PN-synchronization) can be implemented as dynamical systems, in particular, as clock-free analog electronic circuits. Those systems operate in continuous time, and do not require a digital clock; therefore, they circumvent the problem of timing synchronization.

​

We present a numerical algorithm to compute the information rate of continuous channels with memory (Question 3.a). The algorithm is an extension of the methods proposed earlier for discrete channels with memory. Also here, factor graphs and the summary-propagation algorithm are key ingredients. We apply the method to the random-walk phase model.

​

A numerical algorithm is proposed for computing the capacity (or lower bounds on capacity) of continuous memoryless channels (Question 3.a). We present numerical results for the Gaussian channel with average-power and/or peak-power constraints. We outline how the algorithm can be extended to continuous channels with memory (e.g., channels with phase noise) by means of message-passing techniques.

​

We propose message-passing algorithms to compute Cramér-Rao-type bounds. Cramér-Rao-type bounds are lower bounds on the minimum mean square estimation error; the bounds may be used to asses the performance of practical (message-passing) estimation algorithms, in particular, our phase-estimation algorithms (Question 3.b). The algorithms we propose for computing Cramér-Rao-type bounds open the door to exciting applications of information geometry, such as (1) natural-gradient-based algorithms; (2) the computation of Fisher kernels. 

​

​

Defense

​

Thursday 1st of December 2005

Time: 2pm

Place: ETZ E81

Slides of the defense. PDF file
 

Examiners

​

Prof. Dr. Hans-Andrea Loeliger    (ETH Zurich, Institute for Signal and Information Processing)

Prof. Dr. Shun-ichi Amari              (RIKEN, Brain Science Institute, Wako-shi, Japan)

Prof. Dr. Marc Moeneclaey           (Digital Communications Lab, Gent University, Gent, Belgium)

Dr. Jonathan Yedidia                      (Mitsubishi Electrics Research Lab, Cambridge, MA, US)