Contact: Niek J. Bouman
Currently, several changes are taking place on the production side of the electrical grid (e.g., installation of solar panels and wind turbines), as well as on the consumption side (e.g., the advent of the electric car). Because of these changes, controlling the grid such that the utilisation of the power sources is maximised, while ensuring stable and safe operation, becomes challenging. In the COMMELEC research project we are developing a radically new and smart way to controlling electricity grids. In particular, we take a distributed approach, meaning that multiple control nodes communicate to each other over a packet network, using UDP.
Project Description
In COMMELEC, control set-points are computed every few milliseconds, based on fresh sensor data from various resources in the grid. Usually, the size of this data is moderate (say, 1000 bytes per resource) so that the data fits in a single IP packet. In this case, forward error correction (on the packet level) cannot be applied, except for simply repeating the packet (a repetition code on the packet level). Once in a while, however, the sensor data might be too large to fit in a single IP packet (the maximum transmission unit(MTU) of Ethernet is typically 1500 bytes) and the UDP datagram needs to be split over multiple (say, k) IP packets (fragmentation). Using an appropriate packet erasure code, we could then generate r additional redundant packets, yielding n= k+r packets in total, such that the k original packets can be recovered perfectly from any size-k subset out of the n packets. Hence, in the case where packet fragmentation is necessary, erasure coding (on the packet level) can improve the reliability of transmission while keeping the overall delay within its constraints.
In this assignment, we will implement a fast (i.e., O(n log n), where n is the number of packets in a codeword) encoder and decoder for a Reed–Solomon packet erasure code. The implementation will be in C++11, and some cross-compiling will be involved to run the code on an embedded ARM Cortex A9 platform. We will carefully select the finite field over which we work, so that
- the Galois-field operations map directly to operations on integers, hence we exploit the computational power and power-efficiency of the integer-arithmetic unit of the ARM processor, and
- the Lagrange interpolation function (which is used for both encoding and decoding) can be implemented using the prime-factor FFT algorithm, giving the O(n log n) complexity.
What You’ll Learn from this Project
Apart from the elegant theoretical aspects of finite fields, erasure codes and fast transform techniques, you will learn about many practical aspects that come into play when one implements an algorithm on embedded hardware. We will make use of modern tools, like the new LLVM compiler, and modern systems programming standards and patterns, like C++11 and “RAII” (i.e., “Resource Allocation Is Initialization”). Learning how to develop for embedded platforms makes a lot of sense, because these platforms (like Raspberry Pi, or BeagleBone) have become very cheap, and can form the heart of your next research experiment, new product for your tech-startup, or hobby project!
Keywords
- C++11, Boost::Asio, network programming, memory-alignment aspects, LLVM/clang, cmake;
- Cross-platform development and cross-compilation to ARM;
- Finite-field (Galois field) arithmetic, Lagrange interpolation, fast number transforms, prime-factor FFT;
- Coding theory, erasure decoding, Reed–Solomon codes.
References
H. S. Cronie. Fast decoding of GF(q) packet erasure codes. In Proceedings of the 31st Symposium on Information Theory in the Benelux, pages 129– 135. Werkgemeenschap voor Informatie- en Communicatietheorie and the IEEE Benelux Information Theory Chapter, 2010. [PDF (full text)]