• Diese Seite als PDF öffnen.

Group testing techniques based on sparse graphs for large-scale population screening

Description

Group testing is a combinatorial technique (developed by R. Dorfman in 1943) which allows to detect infected individuals by running “pooled” tests on (blood) samples. More specifically, by merging the samples of a subset of individuals into a pool, a test is carried out to verify the positivity (or negativity) of the pool. By repeating the test on different subsets, it is eventually possible to detect the individuals carrying the infection, possibly with very few tests compared with the test population. The approach is currently scouted to speed-up the testing in the context of the COVID-19  pandemic (see https://www.nature.com/articles/d41586-020-02053-6 and [1-2]). The technique admits a description which shares several similarities with the syndrome-based error correction problem via linear block codes. It is not a surprise that major contributions in the area of group testing have been given by coding and information theorists.

The scope of the thesis is to investigate the adoption of capacity-approaching codes based on sparse graphs (e.g., low-density parity-check codes) to attack the group testing problem. The use of sparse-graph codes for this purpose has been already envisaged in [3-4]. In this work, we will address the design of adaptive/non-adaptive and quantitative/non-quantitative group testing techniques based on sparse graphs, under various detection algorithms (belief propagation, as well as combinatorial orthogonal matching pursuit).

[1] Mutesa, Leon, et al. "A strategy for finding people infected with SARS-CoV-2: optimizing pooled testing at low prevalence." arXiv preprint arXiv:2004.14934 (2020). [2] Narayanan, Krishna R., Anoosheh Heidarzadeh, and Ramanan Laxminarayan. "On Accelerated Testing for COVID-19 Using Group Testing." arXiv preprint arXiv:2004.04785(2020). [3] K. Lee, R. Pedarsani and K. Ramchandran, "SAFFRON: A fast, efficient, and robust framework for group testing based on sparse-graph codes," 2016 IEEE International Symposium on Information Theory (ISIT), Barcelona, 2016  - available at https://arxiv.org/abs/1508.04485  [4] Aldridge, Matthew, Oliver Johnson, and Jonathan Scarlett. "Group testing: an information theory perspective,: NOW Published, 2020 - available at https://arxiv.org/pdf/1902.06002.pdf

Prerequisites

Contact

Supervisor:

• Diese Seite als PDF öffnen.

Scaling exponent of polar codes

Description

Topic for "Hauptseminar Digitale Kommunikationssysteme" (MSEI) (https://www.ei.tum.de/index.php?id=5492) NOT for "Seminar on Topics in Communications Engineering" (MSCE).

Understanding and presenting the results on the scaling exponent of polar codes.

References

• https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5513579
  https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6866198

• https://ieeexplore.ieee.org/abstract/document/7028536

• https://arxiv.org/abs/1304.4321

• https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8709690

• https://dl.acm.org/doi/abs/10.1145/3357713.3384323

Prerequisites

Supervisor:

• Diese Seite als PDF öffnen.

Coding for binary-adder channel

Description

The student is asked to understand the achievable rates via linear codes for 2-user binary adder channel (see, e.g., [1]) for an unsourced scheme [2], i.e., if the codebook for both users are the same. Then, the results should be compared to simulations employing a polar coding scheme [3].

[1] https://ieeexplore.ieee.org/document/1055529

[2] https://ieeexplore.ieee.org/document/8006984

[3] https://ieeexplore.ieee.org/document/6532306

Supervisor:

Student

• Diese Seite als PDF öffnen.

Successive cancellation inactivation decoding of single parity-check product codes (and a non-trivial extension to improve finite-length performance)

Description

The task of the student is to implement an efficient successive cancellation (SC) inactivation decoder for single parity-check product codes, which is (probably) an efficient MAP decoder for such codes over the erasure channels. At the end of the internship, the aim is to assess the MAP performance of very long product codes. Note that this has strong ties with a conjecture that some product codes might be capacity-achieving (although we are just after a numerical evidence for now). If the time permits, we consider the modifications to these codes to enable a better finite-length performance. Related literature is below [1,2].

[1] https://arxiv.org/abs/2004.05969

[2] https://arxiv.org/abs/2008.06938

 

Supervisor:

Student

• Diese Seite als PDF öffnen.

Product codes with polar component codes

Description

The task of the student would be to implement an iterative decoding of a product code composed of polar component codes. S/he should start by regenerating the results from [1]. Then, the work is extended to have improved decoding, which still allow for high-throughput applications, for such product codes. Later, s/he will enhance the code construction tailored to the introduced algoithms to improve the performance. The performance might be compared to the results from [2,3].

 

 

[1] https://arxiv.org/pdf/1901.06892.pdf

 

[2] https://arxiv.org/abs/2008.06938

 

[3] https://arxiv.org/abs/1908.10397

Prerequisites

Contact

Supervisor:

Student

• Diese Seite als PDF öffnen.

Investigation of polar and Reed-Muller codes under inactivation decoding for distributed computing

Description

 

Recently, channel codes are proposed to speed up computation in distributed systems by introducing redundant calculations to avoid the latency due to, e.g., straggling nodes (see, e.g., [1]). Since this problem can be casted as coding for erasure channels (where the erasure probability itself might be a random variable), there are works using inactivation decoding, an efficient way of implementing Gaussian elimination, for this problem [2]. In this internship, the task of the student is to understand the advantages of polar codes under successive cancellation (SC) decoding [3] and investigate polar codes and their variants, e.g., Reed-Muller codes, under an inactivation decoder [4] to understand their performance compared to the existing works, e.g., [2].

 

 

 

[1] https://arxiv.org/pdf/1512.02673.pdf

 

[2] https://arxiv.org/pdf/1712.08230.pdf

 

[3] https://arxiv.org/pdf/1901.06811.pdf

 

[4] https://arxiv.org/abs/2004.05969

 

Supervisor:

Student