Offered Theses
Please contact the doctoral researchers directly if you are interested in a Bachelor or Master thesis, a student job, an "Ingenieurspraxis" or a "Forschungspraxis". It is also usually possible to find a topic that matches your specific interests. Please include a curriculum vitae together with a list of attended courses when applying for a thesis. If your "Ingenieurspraxis" is selected to be supervised by one of our professors, please hand in the documents to Doris Dorn (Room N2401).
Bachelorarbeiten
Computation of Identification Function Over Faulty Channels
Computation of Identification Function Over Faulty Channels
Stichworte:
Identification via channels, Identification Function,
Kurzbeschreibung:
Identification problem over certain noisy channel is addressed.
Beschreibung
Identification problem for certain noisy channel is studied and the capacity is derived.
Voraussetzungen
Familiarity with basics of information theory and channel coding.
Betreuer:
A Jupyter Notebook for Line Coding in Access Networks (LB)
A Jupyter Notebook for Line Coding in Access Networks (LB)
Beschreibung
yle="margin-bottom: 0cm; line-height: 100%;">For the access network case, the spectrum of the transmit signal has to be adapted to the channel properties. This can either be achieved by choosing suitable transmit pulse shapes or by encoding the (redundancy free) source symbols [1].
yle="margin-bottom: 0cm; line-height: 100%;">The students task is to implement a demonstration of two line coding schemes in Python [2] (Jupyter Notebook) and visualize the results. Additionally, the student also has to arrange code and surrounding text, such that the content becomes self-explanatory.
yle="margin-bottom: 0cm; line-height: 100%;">[1] Skript "Physical Layer Methods“
yle="margin-bottom: 0cm; line-height: 100%;">[2] "Python in 30 minutes" (https://www.programiz.com/python-programming/tutorial)
Voraussetzungen
Since the Jupyter Notebook is to be written in german language, the student should be able to write in german at least on a basic level.
While some basics in any programming language are beneficial, this is also a great opportunity for programming beginners, wishing to expand their programming skills.
For this topic students of the "Lehramtsstudiengänge" are preferred.
Betreuer:
Deterministic Identification Over the Binary Symmetric Channel
Deterministic Identification Over the Binary Symmetric Channel
Stichworte:
Identification, Identification Without Randomization, Complexity of Distributive Computing, One-Way/Two-Way Probabilistic Communications
Kurzbeschreibung:
Identification without randomization over the binary symmetric channel (BSC) would be studied and investigated. Method of coding, decoding sets, type I/II errors and a closed-form solution of non-randomized (deterministic) identification capacity will be considered and analysed.
Beschreibung
In theory of Identification introduced by Ahlswede and Dueck the perspective of communications is changed from decoding to identification, i.e., the receiver is only interested to check whether or not his message was sent by transmitter. Ahslwede and Dueck proved that by means of local randomness (at encoder) they can achieve doubly exponential gain in code size which outperfrom substantially the classical scheme of Shannon transmission. (only exponential gain in code size). However, in many cases, there is no need to exploit the Randomization at encoder and thus the view of identification without randomization is introduced.
On the other hand to derive probabilistic complexity of models for one/two way communications for distributive computing (communication between two processors for determine copperatively value of an identification function) similar ideas were discussed. The student should understand those ideas and try to find the link between them and idea of Identification of Ahlswede and Dueck. Ideally the student attempt to derive forward or/and backward proof for non-randomized identification capacity of the Binary Symmetric Channel (BSC).
Voraussetzungen
- Familiarities with fundamental concepts of Information Theory, such as Entropy, Mutual Information, Hamming Distance, Rate, Probability of Error, The Binary Symmetric Channel etc)
- Familiarity with fundamentals of Identification Theroy
Betreuer:
Masterarbeiten
Semantic security of infinite-dimensional classical-quantum channels
Semantic security of infinite-dimensional classical-quantum channels
Beschreibung
Generalize semantic security of classical-quantum channels to infinite dimensional channel (not necessarily gaussian)
- [1] finite dimensional classical-quantum case
https://arxiv.org/abs/2001.05719 - finite and infinite dimensional classical case
https://arxiv.org/abs/1811.07798
- [this subpoint can be a project by itself] the finite dimesional case needs to be recast into smooth-max information (instead than Lemma 5.7 of [1]) as the classical case does, this paper proves properties of the smooth-max-inf in finite dimension that we would need for that
https://arxiv.org/abs/2001.05719
- papers regarding the capacity for infinite dimensional channels
http://arxiv.org/abs/quant-ph/9912067v1
http://arxiv.org/abs/quant-ph/0408009v3
http://arxiv.org/abs/quant-ph/0408176v1
Voraussetzungen
quantum information theory
Betreuer:
Asymptotic continuity of restricted quantum relative entropies under general channels
Asymptotic continuity of restricted quantum relative entropies under general channels
Stichworte:
quantum, relative entropy, Pinsker, reverse, inequality, information thoery, asymptotic, continuity
Beschreibung
Asypmtotic continuity is a property in the form of inequalities (classically known also as inequalities of the reverse-Pinker type) that is necessary to prove upper bounds on operational capacities.
The (quantum) relative entropy (also known as quantum divergence and classically also known as Kullbackt-Leibler divergence), can be used to define various entanglment measures many of which have a proven asymptotic continuity.
Of particular interest are the restricted quantum relative entropies defined by Marco Piani (https://arxiv.org/abs/0904.2705), many of which satisfy asymptotic continuity (A.S.)
- https://arxiv.org/abs/quant-ph/9910002
- https://arxiv.org/abs/quant-ph/0203107
- https://arxiv.org/abs/quant-ph/0507126
- https://arxiv.org/abs/1210.3181
- https://arxiv.org/abs/1507.07775
- https://arxiv.org/abs/1512.09047
In the above there are maybe 2-3 different proof styles.
We can group the results in the above as follows:
- A.S. for entropy, conditional entropies, mutual information, conditional mutual information
- A.S. for relative entropies with infimum over states on the second argument
- A.S. relative entropies with infimum over state *and maximization over measurement channels*
The goal of the project is to generalize the last case to asymptotic continuity for relative entropies with infimum over state and maximization over *general* channels
- Partial results toward this goal can be found in the appendix of my PhD thesis: http://web.math.ku.dk/noter/filer/phd18rf.pdf
- Such a result would have immediate applications to this paper: https://arxiv.org/abs/1801.02861
- Possible new proof directions could involve the use of Renyi α-realtive entropies with the limit α->1
Voraussetzungen
Knowledge of quantum information is highly recommended/required.
Knowledge of matrix analysis will be a strong advantage.
Kontakt
roberto.ferrara@tum.de
Betreuer:
Practical protocols for quantum synchronization in classical network
Practical protocols for quantum synchronization in classical network
Stichworte:
quantum, network, synchronization
Beschreibung
relevant papers
https://arxiv.org/abs/1310.6043
https://arxiv.org/abs/1304.5944
https://arxiv.org/abs/1310.6045
https://arxiv.org/abs/1703.05876
https://arxiv.org/abs/1303.6357
background papers
https://ieeexplore.ieee.org/document/7509657
Voraussetzungen
Knowledge of quantum theory as provided by the course Algorithms in Quantum Theory or similar
Betreuer:
Entanglement-measures upper bounds on device-independent distillable key
Entanglement-measures upper bounds on device-independent distillable key
Stichworte:
quantum, qkd, entanglement
Beschreibung
The goal of this work is to try to upper bound the device-independent distillable key in terms of locally restricted relative entropy of entanglement (an entanglement measure).
The following are relevant works/articles
- works toward even *a definition* of device independent distillable key
https://arxiv.org/abs/2005.13511
https://arxiv.org/abs/2005.12325
https://arxiv.org/abs/1810.05627 - works relating distillable entanglement and distillable key to locally restricted relative entropy measures
https://arxiv.org/abs/1609.04696
https://arxiv.org/abs/1402.5927 - the first definition of restricted relative entropies
https://arxiv.org/abs/0904.2705 - important properties of restricted relative entropies, and some overview of entanglement measures
https://arxiv.org/abs/1210.3181 - my PhD thesis
http://web.math.ku.dk/noter/filer/phd18rf.pdf
Voraussetzungen
Strong background in quantum theory is required, preferably in quantum information theory, which is not covered by the course Algorithms in Quantum Theory
Betreuer:
Intelligent Reflecting Surface -aided Beam Alignment for mmWave Communications
Intelligent Reflecting Surface -aided Beam Alignment for mmWave Communications
Stichworte:
Intelligent refelecting surface (IRS), mmWave beam alignment
Beschreibung
The future generation communication networks will be operated mainly at millimeter wave (mmWave) or even higher frequency bands in order to achieve high spectral efficiency as well as accurate localization/positioning, necessary for emerging autonomous applications. At such a high frequency bands, beamforming both at the transmitter and the receiver, or beam alignment (BA), is considered essential to compensate the high propagation and penetration loss. The design of BA achieving a good tradeoff between alignment accuracy and resource overhead has been extensively studied in the literature [1,2]. In particular, a number of recent works proposed to exploit some side information, such as location [3,4], database [5], or radar [6], at the base station side to speed up the initial acquisition time.
Intelligent reflecting surface (IRS) consists of a large number of passive reflecting elements that can be easily controlled at a base station or access points to cooperatively beamform without the need of any radio-frequency (RF) chains. So far, a number of recent works showed that IRS can be used as an external fixed helper to increase the coverage, mitigate the interference of the network [7] and references therein). Due to its low cost together with the advanced, future user terminals can be also equipped with small IRS. This IRS-integrated device provides a new opportunity that we wish to exploit to speed up the BA protocol.
In this mater thesis, we study IRS-aided BA and quantify how much the resource can be saved as a function of the IRS parameters. To this end, we aim to organize the work as follows:
- Understand the basic of IRS and mmWave BA.
- Study various types of IRS space-time (coding) functions to control passive reflecting elements [8].
- Study the tradeoff between the alignment accuracy and the required resource.
References
[1] X. Song, S. Haghighatshoar, and G. Caire, ``Efficient Beam Alignment for Millimeter Wave Single-Carrier Systems With Hybrid MIMO Transceivers," IEEE Trans. Wireless Commun., vol. 18, no. 3,pp. 1518-1533, 2019.
[2] S. Chiu, N. Ronquillo, and T. Javidi, ``Active Learning and CSI Acquisition for mmWave InitialAlignment," IEEE J. Sel. Areas Commun., vol. 37, no. 11, pp. 2474-2489, 2019.
[3] V. Va, T. Shimizu, G. Bansal, and R. W. Heath, ``Position-aided millimetre wave V2I beam alignment:A learning-to-rank approach," in 2017 IEEE 28th Annual International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC). IEEE, 2017, pp. 1-5.
[4] A. U. Rahman and M. Biswal, ``Error-tolerant Beam Steering of mmWave Antennas by Trajectory Estimation of Highway Vehicles," in 2019 11th International Conference on Communication Systems Networks (COMSNETS), 2019, pp. 530-531.
[5] V. Va, J. Choi, T. Shimizu, G. Bansal, and R. W. Heath, ``Inverse multipath fingerprinting for millimeter wave V2I beam alignment," IEEE Trans. Veh. Technol., vol. 67, no. 5, pp. 4042-4058, 2018.
[6] Nuria Gonzalez-Prelcic, Roi Mendez-Rial, and Robert W. Heath, ``Radar aided beam alignment in mmwave V2I communications supporting antenna diversity," in Information Theory and Applications Workshop (ITA), 2016. IEEE, 2016, pp. 1-7.
[7] Qingqing Wu, Shown Zhang, Beixiong Zheng, Changsheng You, and Rui Zhang, ``Intelligent reflecting surface aided wireless communications: A tutorial," IEEE Trans. Wireless Commun., 2021.
[8] Lei Zhang et al., ``Space-time-coding digital metasurfaces,” Nature communications, vol. 9, no. 1, pp. 1-11, 2018.
Voraussetzungen
- Solid background in signal processing and optimization.
- Matlab programming skills.
Kontakt
Mari Kobayashi (mari.kobayashi@tum.de)
Betreuer:
Joint Sensing and Communications for Future Autonomous Applications
Joint Sensing and Communications for Future Autonomous Applications
Stichworte:
Joint sensing and communication, capacity-distortion-cost tradeoff
Beschreibung
The key-enabler of mobility-driven networks such as vehicle-to-everything (V2X) communications is the ability to continuously track and react to the dynamically changing environment (hereafter called the network ``state") while exchanging information with each other. Motivated by such applications, the joint sensing and communication, where a transmitter equipped with on-board sensors wishes to communicate data to its receivers and simultaneously estimate/track the states, has been extensively studied in the literature. Although common waveforms to perform both communication and sensing tasks have been proposed for specific scenarios, the fundamental limit of such a system is not well understood yet.
In this master thesis, we aim to study the fundamental tradeoff between state sensing and communications in simple point-to-point channels. Our preliminary results were restricted to the memoryless channels with identically and identically distributed (i.i.d.) states, which is unrealistic in practical wireless channels. Therefore, the focus is to extend the preliminary results to temporally correlated channels such that the transmitter can predict the upcoming channels from the previous observations in order to enhance further both sensing and communication performance. If time allows, we will consider other types of channels such as block-fading channels, multiple-input-multiple-output (MIMO) channels.
Voraussetzungen
- Solid background in signal processing, optimization or information theory.
- Matlab programming skills.
Kontakt
Mari Kobayashi (mari.kobayashi@tum.de)
Betreuer:
Explicit Construction of Deterministic Identification Codes
Explicit Construction of Deterministic Identification Codes
Stichworte:
Identification via channels, identification codes,
Beschreibung
In this thesis, the student after studying deterministic identification will construct the explicit codes for certain channels.
Voraussetzungen
Background in Information Theory and Channel Coding
Familiarity in fundamentals of Identification Theory
Betreuer:
Group testing techniques based on sparse graphs for large-scale population screening
Group testing techniques based on sparse graphs for large-scale population screening
Beschreibung
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
Voraussetzungen
The student should have successfully passed the Channel Coding course and should exhibit a good understanding of probability theory. The Channel Codes for Iterative Decoding and Information Theory courses are plus.
Kontakt
mustafa.coskun@tum.de
Betreuer:
Efficient Implementation of Decryption Algorithms in Rank-Based Cryptography
Efficient Implementation of Decryption Algorithms in Rank-Based Cryptography
Beschreibung
Many Rank-based cryptosystems require decoding of Gabidulin codes in their decryption algorithm. In this work, the student should compare the theoretical complexity of different Gabidulin code decoders. Based on the theoretical complexity analysis, the students should decide on the most promising decoding algorithms. Then, the algorithms should be implemented in C and their performance should be compared on a microcontroller.
Voraussetzungen
- Good knowledge about rank-metric codes (e.g. by taking the course Coding Theory for Storage and Networks)
- Good knowledge about cryptography (e.g. by taking the course Security in Communications and Storage)
- Very good knowledge of the Programming language C
Betreuer:
The coin weighing problem
The coin weighing problem
Beschreibung
The question of finding a small subset of defective coins from a set of regular coins in the fewest number of weighings has been a notorious problem.
Suppose there is a collection of n coins so that some of them are defective. In other words, we know that the weight of regular coins is A, and the weight of the remaining coins is B, where integers A and B are given. The problem is to determine the weight of each coin by weighing subsets of coins in a spring scale. The main figure of merit when studying adaptive coin weighing algorithms is the number of required weighings in the worst-case and in the average-case. In this project, we design and implement an efficient algorithm which works for two coins.
Voraussetzungen
Coding theory, combinatorics
Good programming skills
Kontakt
Betreuer:
Error Correction in DNA Storage
Error Correction in DNA Storage
Stichworte:
DNA storage, Error Correction, Deletion, Insertion, Substitutions
Beschreibung
DNA storage is an uprising topic in the research field of storage systems. Due its natural longetivity, robustness, and density properties the main application would arise in high-dense long-term storage systems. The interest has become larger and larger due the large amount of data nowadays and the relative new biological advances in DNA synthesis and sequencing processes (e.g. polymerase chain reaction). In contrary to conventional storing methods, due to the nature of DNA and the involved biological processes special error patterns such as insertion, deletion, and substitution errors occur. To tackle these errors novel methods for correction have to be investigated. Moreover, the model of the DNA storage channel needs to be investigated thorougly, e.g. capacity statements.
Voraussetzungen
- Linear Algebra
- Channel Coding
- Coding Theory for Storage and Networks (optional)
Betreuer:
How to guess an n-digit number
How to guess an n-digit number
Beschreibung
In a deductive game for two players, Alice and Bob, Alice conceals an n-digit number x, and Bob, who knows n, tries to identify x by asking a number of questions, which are answered by Alice. Each question is an n-digit number y, and each answer is the number of positions at which the corresponding symbols of x and y are different. Moreover, we require Bob to ask all questions at once. The goal of this project is to design and implement an efficient coding scheme for Bob with an asymptotically optimal number of questions.
Voraussetzungen
Coding theory, combinatorics, analysis
Good programming skills
Kontakt
Betreuer:
DNA Storage Channel Modeling and Error Correction
DNA Storage Channel Modeling and Error Correction
Beschreibung
DNA-based data storage is a novel approach for long term data archiving.
Due to the unique nature of writing and reading DNA, the channel associated with these processes is still realtively poor understood and varies over different synthesis (writing) and sequencing (reading) technologies. The task of the student is to analyze different sequencing methods and the associated errors and formulate associated channel models. Based on these models, error-correcting schemes shall be evaluated.
Voraussetzungen
- Basic principles of stochastic and algebra
- Channel Coding
Betreuer:
Algebraic Coding for Distributed Storage
Algebraic Coding for Distributed Storage
Beschreibung
Distributed storage systems with a large number of storage commonly rely on MDS codes, such as Reed-Solomon codes, to protect the system from data loss in the event of node failures while keeping the storage overhead low. In the event of such a failure, the reconstruction of failed nodes induces a large amount of network traffic. In recent years several solutions to this problem have been proposed, most notably locally repairable codes and regenerating codes. We investigate the properties of specific subclasses of these codes, as well as the combination of the two properties.
Further, with the increased demand for data privacy, we develop methods for protecting users' data from the eyes of curious servers in distributed storage systems.
Betreuer:
Homomorphic encryption
Homomorphic encryption
Stichworte:
Cryptography
Beschreibung
Consider that a client would like to a server to do some computations for him but he does not want to give information meaningful information to the server. The client therefore sends encrypted messages c1 = Enc(pk, m1) and c2 = Enc(pk, m2) to the server and the client would like to obtain some function f of the two plaintexts f(m1,m2). It suffices for the client to get Enc(pk, f(m1,m2)) because the client owns the secret key sk. He is able to use the decryption function Dec on the ciphertext and gets Dec(sk, Enc(pk,f(m1,m2=))) = f(m1,m2).
The goal of this internship is to analyze schemes that achieve this property based on code-based cryptography.
Voraussetzungen
linear algebra
coding theory
basic understanding of cryptography
Betreuer:
Simulation and performance improvement of identification codes
Simulation and performance improvement of identification codes
Beschreibung
Identification is a communication scheme that allows rate doubly exponential in the blocklemght, with the tradeoff that identities cannot be decoded (as messages do) but can only be verified.
The double exponential growth presents various challenges in the finite regime: there are heavy computational costs introduced at the encoder and decoder and heavy trade-offs between the error and the codes sizes.
The ultimate goal is to find a fast, reliable implementation while still achieving large code sizes.
Your task will be implementing and testing new ideas toward this goal.
The coding will be in Matlab. Some existing code needs conversion from Sagemath to Matlab.
This work can accomodate multiple students.
The working language will be in English.
Environment: we collaborate with LTI. At LNT and LTI there is currently a lot of funding for research in identification. Therefore you will find a large group of people that might be available for discussion and collaboration.
Voraussetzungen
Nachrichtentechnik 2
Betreuer:
Two-sided search
Two-sided search
Beschreibung
In the most studied models in the literature, it is assumed that the target of the search is either stationary with its hidden position being chosen according to someknown distribution, or it is moving and its movements follow some known rules. In such cases, we talk about one-sided search, meaning that the target’s behaviour is somehow independent of the searcher’s attempt to catch it. Conversely, if the target can attempt to contrast the searcher’s activity and react in some intelligent way in order not to be found, the model is referred to as two-sided search. Two-sided search was introduced by Koopman. The goal is to implement a two-sided search algorithm.
Betreuer:
Learning Aided SC Flip Decoding for Polar Codes
Learning Aided SC Flip Decoding for Polar Codes
Beschreibung
Polar codes achieve the capacity of binary-input discrete memoryless channels asymptotically in the block length under successive cancellation (SC) decoding. Polar codes have been adopted for the control channel in 5G enhanced mobile broadband (eMBB).
Due to the serial nature of SC decoding, an erroneous bit decision can be caused by the channel noise or previous erroneous bit estimates. The main idea of SC flip decoding is trying to correct the first erroneous bit decision by sequentially flipping the unreliable decisions.
The optimal flipping strategy is considered difficult due to lack of an analytical solution. Alternatively, (deep) learning aided SC flip algorithm are investigated in this thesis.
[1] O. Afisiadis, A. Balatsoukas-Stimming, and A. Burg, “A low-complexity improved successive cancellation decoder for polar codes,” in Proc. 48th Asilomar Conf. Signals, Systems and Computers, pp. 2116-2120, 2014.
[2] L. Chandesris, V. Savin, and D. Declercq, “Dynamic-SCFlip Decoding of Polar Codes,” IEEE Trans. Commun., vol. 66, no. 6, pp. 2333-2345, Jun., 2018.
[3] X. Wang, et al. "Learning to Flip Successive Cancellation Decoding of Polar Codes with LSTM Networks." arXiv preprint arXiv:1902.08394 (2019).
[4] N. Doan, et al. "Neural Dynamic Successive Cancellation Flip Decoding of Polar Codes." arXiv preprint arXiv:1907.11563 (2019).
Betreuer:
Polar Coding with Non-Binary Kernels
Polar Coding with Non-Binary Kernels
Beschreibung
This thesis will focus on polar codes with non-binary kernels on GF(q). Some of the following tasks might be covered:
- Kernel selection
- Decoder implementation
- Efficient construction
- Comparison of binary and non-binary polar codes
Voraussetzungen
- Channel Coding
- Information Theory
- Matlab/C++
Betreuer:
Forschungspraxis oder MSCE Forschungspraxis
Fano's Inequality: Applications in Communications and Beyond the Communication Problem
Fano's Inequality: Applications in Communications and Beyond the Communication Problem
Beschreibung
Information theory plays an indispensable role in the development of algorithm-independent imposibility results, both for communication problems and for seemingly distinct areas such as statistics and machine learning. While numerous information-theoretic tools have been proposed for this purpose, the oldest one remains arguably the most versatile and widespread: Fano's inequality.
References:
[1] An Introductory Guide to Fano's Inequality with Applications in Statistical Estimation. Jonathan Scarlett, Volkan Cevher. (and references within).
https://arxiv.org/abs/1901.00555
Please contact the supervisor for possible additional references, too.
Voraussetzungen
-Background and interest in Probability theory and stochastic processes, statistics and Information theory.
-An interest in a possible numerical simulation using MATLAB or any other numerical simulation environment (Python, Julia..etc)
-The exact starting date is flexible. But it should be sometime around summer 2021.
Betreuer:
Decoding of product codes
BCJR Algorithm
Construction of Identification Codes via Prime Numbers
Construction of Identification Codes via Prime Numbers
Stichworte:
Identification via channels, Prime Number Encryption
Kurzbeschreibung:
An approach for construction of identification codes for noiseless channel by means of the prime number encryption would be studied.
Beschreibung
In original scheme of identificaion via channels (Ahlswede and Dueck, 1989), a non-constructive method for coding for noiseless channel was studied. To address the explicit construction of identificaion codes, foremost Ahlswede and Verboven, 1991 provide a number theoretic approach based on the two successive prime number encryption. This method require the knowledge of first 2^n prime numbers for a block-length of n codeword. In this research internship, this method along with related prime number encryption tools and theorems would be investigated. Further, the extension of this scheme to a general DMC will be analyzed.
Voraussetzungen
Background in Information Theory and Channel Coding
Familiarity with Fundamental of Identificaion Theory
Familiarity with Prime Number Theorem (Chebyshev)
Betreuer:
On the Equivalence of Identification and Authentication
On the Equivalence of Identification and Authentication
Stichworte:
Identification via channel, identification codes, authentication, authentication codes
Kurzbeschreibung:
A Certain equivalence of identification and authentication would be shown.
Beschreibung
It would be shown that under suitable formulations (preserving all salient features) the two problem of Identification (Ahlswede and Dueck, 1989) and Authentication (Simmons, G. J. 1984) are in essence very close to each other. This equivalency was conjectured first by M. S. Pinsker. In this research internship the student is expected to address this conjecture. Both problems must be studied separately and then the similar essence of them should be drawn out. In particular the identification codes and authentication codes along with theire relation will be investigated.
Voraussetzungen
- Background in Information Theory and Channel Coding
- Familiarity with fundamentals of Identification Theory
References:
- Simmons, G. J. 1984, “Message authentication: a game on hypergraphs,” Congressus Numer. 45:161-192.
- Simmons, G. J. 1982, “A game theory model of digital message authentication,” Congressus Numer., 34, 413-424
- Simmons, G. J. 1985, “Authentication theory/coding theory,” in: Advances in Cryptology: Proceedings of CRYPTO 84, Lecture Notes in Computer Science, vol. 196, Springer-Verlag, Berlin, pp. 411-432.
- E. Gilbert, F. J. MacWilliams and N.J. A. Sloane, 1974, “Codes which detect deception,” Bell System Tech. J., 53, 405-424.
- R. Ahlswede and G. Dueck, “Identification via channels,” in IEEE Trans. on Inf. Theory, vol. 35, no. 1, pp. 15-29, Jan. 1989, doi: 10.1109/18.42172.
- L. A. Bassalygo, M. V. Burnashev, “Authentication, Identification, and Pairwise Separated Measures”, Problems Inform. Transmission, 32:1 (1996), 33–39
Betreuer:
Analysis of Criss-Cross Deletion in Arrays
Analysis of Criss-Cross Deletion in Arrays
Beschreibung
yle="font-weight: normal;" lang="de-DE" align="left">In this project we study two dimensional deletion/insertion problem introduced in https://arxiv.org/pdf/2004.14740.pdf. An array of n rows and n columns is transmitted through a specific deletion channel which for example occurs in DNA storage systems and racetrack memories. After transmission the receiver observes an array of dimension (n-1)*(n-1). The goal is to allow the receiver to know exactly which n*n array was transmitted by using error-correction techniques.
The goal of the project is to derive bounds on the deletion ball of any two-dimensional array. A deletion ball of an array X is the set of unique arrays resulting from the deletion of any possible combination of a column and a row in X. Deriving such bounds is not trivial since it depends heavily on the structure of the array. Thus, it is important to investigate useful characteristics representing the structure of an array for this particular setting. Furthermore, having this bound will be helpful to characterize the optimal redundancy of a deletion-correcting code for this setting.
Betreuer:
Index Coding & Coded Caching
Index Coding & Coded Caching
Beschreibung
Coded caching problem has two phases, placement phase and delivery phase.
For a fixed placement scheme, designing the delivery protocol is equivalent to the index coding problem.
Transforming a coded caching problem with coded placement to the corresponding index coding problem is a hignly-interested topic and what is the optimal delivery scheme for a coded caching problem with coded placement is still an open problem.
References:
[1] N. S. Karat, S. Samuel, and B. S. Rajan. Optimal error correcting index codes for some generalized index coding problems. IEEE Transactions on Communications, 67(2):929–942, 2019.
[2] Z. Chen, P. Fan, and K. B. Letaief. Fundamental limits of caching: improved bounds for users with small buffers. IET Communications, 10(17):2315–2318, 2016.
Voraussetzungen
- Linear Algebra
- Channel Coding (recommended)
Betreuer:
Error Correction in DNA Storage
Error Correction in DNA Storage
Stichworte:
DNA storage, Error Correction, Deletion, Insertion, Substitutions
Beschreibung
DNA storage is an uprising topic in the research field of storage systems. Due its natural longetivity, robustness, and density properties the main application would arise in high-dense long-term storage systems. The interest has become larger and larger due the large amount of data nowadays and the relative new biological advances in DNA synthesis and sequencing processes (e.g. polymerase chain reaction). In contrary to conventional storing methods, due to the nature of DNA and the involved biological processes special error patterns such as insertion, deletion, and substitution errors occur. To tackle these errors novel methods for correction have to be investigated. Moreover, the model of the DNA storage channel needs to be investigated thorougly, e.g. capacity statements.
Voraussetzungen
- Linear Algebra
- Channel Coding
- Coding Theory for Storage and Networks (optional)
Betreuer:
Homomorphic encryption
Homomorphic encryption
Stichworte:
Cryptography
Beschreibung
Consider that a client would like to a server to do some computations for him but he does not want to give information meaningful information to the server. The client therefore sends encrypted messages c1 = Enc(pk, m1) and c2 = Enc(pk, m2) to the server and the client would like to obtain some function f of the two plaintexts f(m1,m2). It suffices for the client to get Enc(pk, f(m1,m2)) because the client owns the secret key sk. He is able to use the decryption function Dec on the ciphertext and gets Dec(sk, Enc(pk,f(m1,m2=))) = f(m1,m2).
The goal of this internship is to analyze schemes that achieve this property based on code-based cryptography.
Voraussetzungen
linear algebra
coding theory
basic understanding of cryptography
Betreuer:
Distributed learning on serverless compute services
Distributed learning on serverless compute services
Stichworte:
Distributed machine learning, straggler mitigation, neural networks, coding theory
Kurzbeschreibung:
The goal of this project is to implement a neural network on thousands of serverless computing instances. We start by evaluating two existing coding techniques designed to scale stochastic gradient descent for convex loss functions. We then deviate to devise a coding scheme tailored for distributed neural network that scale for convex and non convex loss functions.
Beschreibung
Applying machine learning on large data became part of daily life. Scalability of distributed machine learning algorithms requires tolerance of slower computing nodes referred to as stragglers. To mitigate the effect of stragglers, one can add redundancy to the distributed data. However, stochastic gradient descent (SGD) is known to perform well even when computing on a part of the data. It is shown that for convex loss functions, a small redundancy or no redundancy at all is enough to guarantee good performance of SGD.
In this project, we evaluate the existent coding techniques requiring small redundancy on serverless compute functions offered by Amazon Web Services, or equivalently cloud functions offered by Google Computing Platform. Our goal is to devise a coding technique that goes beyond SGD and can be used for non-convex loss functions. The main targeted application is a full implementation of a neural network on serverless functions with straggler tolerance.
Voraussetzungen
Knowledge of machine learning algorithms, e.g., linear regression, logistic regression, neural network
Good programming skills
Self-motivation and dedication
Plus: knowledge of probability, statistical pattern recognition, coding theory and convex optimization
Kontakt
rawad.bitar@tum.de
https://sites.google.com/site/rawadbitar1
Betreuer:
Investigation of polar and Reed-Muller codes under inactivation decoding for distributed computing
Investigation of polar and Reed-Muller codes under inactivation decoding for distributed computing
Beschreibung
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
Betreuer:
Two-sided search
Two-sided search
Beschreibung
In the most studied models in the literature, it is assumed that the target of the search is either stationary with its hidden position being chosen according to someknown distribution, or it is moving and its movements follow some known rules. In such cases, we talk about one-sided search, meaning that the target’s behaviour is somehow independent of the searcher’s attempt to catch it. Conversely, if the target can attempt to contrast the searcher’s activity and react in some intelligent way in order not to be found, the model is referred to as two-sided search. Two-sided search was introduced by Koopman. The goal is to implement a two-sided search algorithm.
Betreuer:
Learning Aided SC Flip Decoding for Polar Codes
Learning Aided SC Flip Decoding for Polar Codes
Beschreibung
Polar codes achieve the capacity of binary-input discrete memoryless channels asymptotically in the block length under successive cancellation (SC) decoding. Polar codes have been adopted for the control channel in 5G enhanced mobile broadband (eMBB).
Due to the serial nature of SC decoding, an erroneous bit decision can be caused by the channel noise or previous erroneous bit estimates. The main idea of SC flip decoding is trying to correct the first erroneous bit decision by sequentially flipping the unreliable decisions.
The optimal flipping strategy is considered difficult due to lack of an analytical solution. Alternatively, (deep) learning aided SC flip algorithm are investigated in this thesis.
[1] O. Afisiadis, A. Balatsoukas-Stimming, and A. Burg, “A low-complexity improved successive cancellation decoder for polar codes,” in Proc. 48th Asilomar Conf. Signals, Systems and Computers, pp. 2116-2120, 2014.
[2] L. Chandesris, V. Savin, and D. Declercq, “Dynamic-SCFlip Decoding of Polar Codes,” IEEE Trans. Commun., vol. 66, no. 6, pp. 2333-2345, Jun., 2018.
[3] X. Wang, et al. "Learning to Flip Successive Cancellation Decoding of Polar Codes with LSTM Networks." arXiv preprint arXiv:1902.08394 (2019).
[4] N. Doan, et al. "Neural Dynamic Successive Cancellation Flip Decoding of Polar Codes." arXiv preprint arXiv:1907.11563 (2019).
Betreuer:
Polar Coding with Non-Binary Kernels
Polar Coding with Non-Binary Kernels
Beschreibung
This thesis will focus on polar codes with non-binary kernels on GF(q). Some of the following tasks might be covered:
- Kernel selection
- Decoder implementation
- Efficient construction
- Comparison of binary and non-binary polar codes
Voraussetzungen
- Channel Coding
- Information Theory
- Matlab/C++
Betreuer:
Ingenieurpraxis
A Jupyter Notebook for Line Coding in Access Networks (LB)
A Jupyter Notebook for Line Coding in Access Networks (LB)
Beschreibung
yle="margin-bottom: 0cm; line-height: 100%;">For the access network case, the spectrum of the transmit signal has to be adapted to the channel properties. This can either be achieved by choosing suitable transmit pulse shapes or by encoding the (redundancy free) source symbols [1].
yle="margin-bottom: 0cm; line-height: 100%;">The students task is to implement a demonstration of two line coding schemes in Python [2] (Jupyter Notebook) and visualize the results. Additionally, the student also has to arrange code and surrounding text, such that the content becomes self-explanatory.
yle="margin-bottom: 0cm; line-height: 100%;">[1] Skript "Physical Layer Methods“
yle="margin-bottom: 0cm; line-height: 100%;">[2] "Python in 30 minutes" (https://www.programiz.com/python-programming/tutorial)
Voraussetzungen
Since the Jupyter Notebook is to be written in german language, the student should be able to write in german at least on a basic level.
While some basics in any programming language are beneficial, this is also a great opportunity for programming beginners, wishing to expand their programming skills.
For this topic students of the "Lehramtsstudiengänge" are preferred.
Betreuer:
Seminar Topics
The three Seminars "Seminar on Coding and Cryptography", "Seminar on Digital Communications" and "Seminar on Optical Communications" will be organized jointly.
It does not matter for which one you register (please pick *one*), we will assign you to the right one once you passed the application phase.
You can find an overview about the open topics below.