Enhancing Iterative Algorithms with Spatial Coupling
(2024) In Series of licentiate and doctoral theses- Abstract
- Iterative algorithms are becoming more common in modern systems. This ranges from algorithms for communication
systems receivers, machine learning, group testing, and various computation problems. The success of these
algorithms lies in the ability to simplify computation by breaking down the system into components and exchanging
messages on graphs. The graph has the components as nodes and connections between them as edges. This separation
is needed since attempting to solve the problem without dividing it into parts results into an optimal solution,
the joint maximum a posterior (MAP) solution, but the computational complexity is prohibitive.
With the systems divided into separate parts it often seems reasonable... (More) - Iterative algorithms are becoming more common in modern systems. This ranges from algorithms for communication
systems receivers, machine learning, group testing, and various computation problems. The success of these
algorithms lies in the ability to simplify computation by breaking down the system into components and exchanging
messages on graphs. The graph has the components as nodes and connections between them as edges. This separation
is needed since attempting to solve the problem without dividing it into parts results into an optimal solution,
the joint maximum a posterior (MAP) solution, but the computational complexity is prohibitive.
With the systems divided into separate parts it often seems reasonable to use the best component for each part
to achieve good performance. This, however, results into degraded performance compared to the optimal overall
solution. To get improved performance the components have to exchange information iteratively in a number of
cycles a process known as belief propagation (BP). This principle has been applied with much success in various
areas such as the design of turbo codes and low density parity-check (LDPC) codes for reliable communication.
Other examples include iterative receivers for cancelling intersymbol interference (ISI) and better performance of
modulation and coding in coded modulation.
Choosing component codes for communication systems with iterative systems is often a process which involves
compromises. For example, if one chooses a strong code to work with a particular detector, the resulting performance
in the waterfall region becomes poor but the error floor is improved whereas choosing a weak code results in improved
waterfall region but poor error floor. One can also optimize the code, for example, by tuning the degree distribution
of LDPC codes to achieve good performance but the optimization introduces weak components that compromise the
error floor. Furthermore, the optimization can work well for a given set of channel conditions, but the optimized
code may not work well if the conditions are changed.
These problems are a result of the fact that we have limitations from two aspects. First, we are limited by the
component (e.g. codes or detectors) choice which sets the limit on the MAP threshold. A strong code will then
have a good MAP threshold and good error floor wheres a weak code will have a bad MAP threshold and bad error
floor. It is important to note that the MAP threshold is the best we can do with the choice of the components but
it can still be away from the ultimate information theoretical limit of the system (this corresponds to the capacity
in communication systems for example). A second limitation comes from the decoding algorithm. The BP algorithm
is not globally optimal for most graph used, thus setting a limit which is termed the BP threshold. A strong code
has then a bad BP threshold whereas a weak code has a better BP threshold.
This thesis focuses on improving the performance of iterative algorithms by tackling the limitations highlighted.
We propose improved algorithms and, more importantly, we apply the concept of spatial coupling to improve the
performance and robustness of the systems. We do this in two parts.
In the first part we apply the concept on channels with ISI showing that we can obtain robust performance with
changing channel conditions and changing detector type. We propose three schemes of coupling and compute the
BP and MAP thresholds as well as perform finite length simulations.
In the second part, we investigate non-adaptive quantitative group testing using sparse graphs. We propose
improvements of the algorithms and show that with spatial coupling we can obtain improved and robust performance. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/d11099c6-efae-4853-a071-c22c283b42ae
- author
- Mashauri, Mgeni Makambi LU
- supervisor
-
- Michael Lentmaier LU
- Ove Edfors LU
- opponent
-
- Prof. Milenkovic, Olgica, University of Illinois Urbana-Champaign, USA.
- organization
- publishing date
- 2024-10
- type
- Thesis
- publication status
- published
- subject
- in
- Series of licentiate and doctoral theses
- issue
- 178
- pages
- 192 pages
- publisher
- Electrical and Information Technology, Lund University
- defense location
- Lecture Hall E:1406, building E, Ole Römers väg 3, Faculty of Engineering LTH, Lund University, Lund. The dissertation will be live streamed, but part of the premises is to be excluded from the live stream.
- defense date
- 2024-11-08 09:15:00
- ISSN
- 1654-790X
- 1654-790X
- ISBN
- 978-91-8104-213-9
- 978-91-8104-214-6
- language
- English
- LU publication?
- yes
- id
- d11099c6-efae-4853-a071-c22c283b42ae
- date added to LUP
- 2024-10-14 13:41:14
- date last changed
- 2025-04-04 15:24:38
@phdthesis{d11099c6-efae-4853-a071-c22c283b42ae,
abstract = {{Iterative algorithms are becoming more common in modern systems. This ranges from algorithms for communication<br/>systems receivers, machine learning, group testing, and various computation problems. The success of these<br/>algorithms lies in the ability to simplify computation by breaking down the system into components and exchanging<br/>messages on graphs. The graph has the components as nodes and connections between them as edges. This separation<br/>is needed since attempting to solve the problem without dividing it into parts results into an optimal solution,<br/>the joint maximum a posterior (MAP) solution, but the computational complexity is prohibitive.<br/>With the systems divided into separate parts it often seems reasonable to use the best component for each part<br/>to achieve good performance. This, however, results into degraded performance compared to the optimal overall<br/>solution. To get improved performance the components have to exchange information iteratively in a number of<br/>cycles a process known as belief propagation (BP). This principle has been applied with much success in various<br/>areas such as the design of turbo codes and low density parity-check (LDPC) codes for reliable communication.<br/>Other examples include iterative receivers for cancelling intersymbol interference (ISI) and better performance of<br/>modulation and coding in coded modulation.<br/>Choosing component codes for communication systems with iterative systems is often a process which involves<br/>compromises. For example, if one chooses a strong code to work with a particular detector, the resulting performance<br/>in the waterfall region becomes poor but the error floor is improved whereas choosing a weak code results in improved<br/>waterfall region but poor error floor. One can also optimize the code, for example, by tuning the degree distribution<br/>of LDPC codes to achieve good performance but the optimization introduces weak components that compromise the<br/>error floor. Furthermore, the optimization can work well for a given set of channel conditions, but the optimized<br/>code may not work well if the conditions are changed.<br/>These problems are a result of the fact that we have limitations from two aspects. First, we are limited by the<br/>component (e.g. codes or detectors) choice which sets the limit on the MAP threshold. A strong code will then<br/>have a good MAP threshold and good error floor wheres a weak code will have a bad MAP threshold and bad error<br/>floor. It is important to note that the MAP threshold is the best we can do with the choice of the components but<br/>it can still be away from the ultimate information theoretical limit of the system (this corresponds to the capacity<br/>in communication systems for example). A second limitation comes from the decoding algorithm. The BP algorithm<br/>is not globally optimal for most graph used, thus setting a limit which is termed the BP threshold. A strong code<br/>has then a bad BP threshold whereas a weak code has a better BP threshold.<br/>This thesis focuses on improving the performance of iterative algorithms by tackling the limitations highlighted.<br/>We propose improved algorithms and, more importantly, we apply the concept of spatial coupling to improve the<br/>performance and robustness of the systems. We do this in two parts.<br/>In the first part we apply the concept on channels with ISI showing that we can obtain robust performance with<br/>changing channel conditions and changing detector type. We propose three schemes of coupling and compute the<br/>BP and MAP thresholds as well as perform finite length simulations.<br/>In the second part, we investigate non-adaptive quantitative group testing using sparse graphs. We propose<br/>improvements of the algorithms and show that with spatial coupling we can obtain improved and robust performance.}},
author = {{Mashauri, Mgeni Makambi}},
isbn = {{978-91-8104-213-9}},
issn = {{1654-790X}},
language = {{eng}},
number = {{178}},
publisher = {{Electrical and Information Technology, Lund University}},
school = {{Lund University}},
series = {{Series of licentiate and doctoral theses}},
title = {{Enhancing Iterative Algorithms with Spatial Coupling}},
url = {{https://lup.lub.lu.se/search/files/197393093/ThesisFinal.pdf}},
year = {{2024}},
}