Angebotene Arbeiten

• Diese Seite als PDF öffnen.

Analysis of Identification for the Binary Symmetric Channel and a comparison to decoding problem

Stichworte:
Identification, Binary Symmetric Channel, Communication Complexity

Kurzbeschreibung:
Problem of transmission and Identification over the BSC is investigated and analysed. Further it will be shown that identification would be easier than decoding problem in terms of minimum number of bits of communication

Beschreibung

Assuming that the communication channel between two processors P1 and P2 makes an error with probability ε>0, the identification problem is to determine whether P1 and P2 have the same n-bit integer. The decoding problem is for P2 to determine the n-bit integer of P1. For the latter problem we show that given any arbitrarily large constant λ>0, there exists an ε, 0<ε<1/2, for which no scheme requiring less than λn bits of communication can guarantee (for large n) any bound q<1 on the error probability. On the other hand, given any arbitrarily small constant γ>0 and any ε, 0<ε<1/2, the identification problem can be solved with (1+γ)n bits of (one-way) communication with an error probability bounded by c2^{-αn}, where c and α are positive constants. 

Voraussetzungen

Betreuer:

• Diese Seite als PDF öffnen.

Identification Without Randomization for the Discrete Memoryless Channel

Stichworte:
Identification, Identification Without Randomization, Complexity of Distributive Computing, One-Way/Two-Way Probabilistic Communications

Kurzbeschreibung:
Identification without randomization for a general DMC would be studied and investigated. Method of coding, decoding sets, type I/II errors and a closed-form solution of non-randomized 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 a general DMC.

Voraussetzungen

Betreuer:

• Diese Seite als PDF öffnen.

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

Betreuer:

• Diese Seite als PDF öffnen.

Group Testing and Information Theory

Stichworte:
Group Testing

Kurzbeschreibung:
Use ideas of Information Theory to get new group testing strategies.

Beschreibung

The concept of group testing (also called pooled testing or pooling) dates back to mathematical ideas for improving the efficiency of syphilis tests developed by Dorfman in 1943 [Dor43].The idea of Dorfman’s method is to combine portions of k different individual blood samples into onesample in a first stage. If it tested negative then that entire group could be dismissed without further testing. Then, separately retesting the samples of individuals from positive pools in a second stage. Forlow to moderate infection rates, this strategy has a high throughput since most of the group, when chosen wisely, will be declared negative. Naturally, the efficiency of pooling strategies for the current pandemichas been shown to depend on the prevalence of SARS-CoV-2, patient-pool size and test sensitivity. While the sensitivity needs to be understood on an experimental level, the prevalence needs to be estimated from available test results and the pool size should be optimized with Information Theory models before widespread implementation.

Voraussetzungen

Betreuer:

• Diese Seite als PDF öffnen.

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:

• Diese Seite als PDF öffnen.

Protograph-based LDPC Code Design for Finite Number of Iterations

Beschreibung

Low-density parity-check (LDPC) codes are usually designed using an extrinsic information transfer (EXIT) analysis to compute the asymptotic iterative decoding threshold for a given code ensemble. The iterative decoding threshold over an additive white Gaussian noise (AWGN) channel is thereby defined as the minimum signal-to-noise ratio (SNR) for which the a posteriori mutual information converges to one as the number of decoding iterations goes to infinity.

For practical applications, however, decoding is often performed using only a small number of iterations. Mulholland et al. investigated a code design for protograph-based LDPC codes where the protograph-based EXIT (PEXIT) analysis [1] is run for the targeted number of decoding iterations only [2]. They showed that for the binary erasure channel (BEC), the obtained iteration-constrained threshold does not match the bit error rate (BER) threshold of finite-length codes.

In this thesis, the student will understand and reproduce the results from [2], apply these tools to the AWGN channel, and compare them to code design tools developed at the institute.

[1] G. Liva and M. Chiani, “Protograph LDPC codes design based on EXIT analysis,” in Proc. IEEE Global Telecommun. Conf. (GLOBECOM), Nov. 2007, pp. 3250–3254.

[2] I. P. Mulholland, E. Paolini, and M. F. Flanagan, “Design of protograph-based LDPC code ensembles with fast convergence properties,” in Proc. Int. ITG Conf. Syst. Commun. Coding (SCC), Feb. 2017, pp. 1–6.

Voraussetzungen

Betreuer:

• Diese Seite als PDF öffnen.

Adaptive List Decoding for Polar Codes

Beschreibung

The finite-length performance of polar codes can be improved by using successive cancellation list decoding. In this thesis, decoder design/implementation and performance prediction are investigated.

Reference:

[1] I. Tal and A. Vardy. "List decoding of polar codes." IEEE Transactions on Information Theory 61.5 (2015): 2213-2226.

[2] P. Yuan and F. Steiner. "Efficient Decoding Algorithms for Polar Codes based on 2×2 Non-Binary Kernels." International Symposium on Turbo Codes & Iterative Information Processing. 2018.

Voraussetzungen

Betreuer:

• Diese Seite als PDF öffnen.

Machine Learning for Fiber-Optical Communications

Beschreibung

Intensity-Modulation and Direct-Detection (IMDD) transceivers can be built with low hardware complexity, low power consumption and small form factors, which makes them a promising approach for fiber-optical transmission over short distances. However, by their reduced hardware complexity, nonlinear distortions are introduced, which need to be compensated.

The task of the student is to understand and implement [1], [2] in order to communicate over an IMDD link.

Betreuer:

• Diese Seite als PDF öffnen.

Group Testing and Information Theory

Stichworte:
Group Testing

Kurzbeschreibung:
Use ideas of Information Theory to get new group testing strategies.

Beschreibung

The concept of group testing (also called pooled testing or pooling) dates back to mathematical ideas for improving the efficiency of syphilis tests developed by Dorfman in 1943 [Dor43].The idea of Dorfman’s method is to combine portions of k different individual blood samples into onesample in a first stage. If it tested negative then that entire group could be dismissed without further testing. Then, separately retesting the samples of individuals from positive pools in a second stage. Forlow to moderate infection rates, this strategy has a high throughput since most of the group, when chosen wisely, will be declared negative. Naturally, the efficiency of pooling strategies for the current pandemichas been shown to depend on the prevalence of SARS-CoV-2, patient-pool size and test sensitivity. While the sensitivity needs to be understood on an experimental level, the prevalence needs to be estimated from available test results and the pool size should be optimized with Information Theory models before widespread implementation.

Voraussetzungen

Betreuer:

• Diese Seite als PDF öffnen.

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:

• Diese Seite als PDF öffnen.

Simmulation eines Quantenrepeaters

Stichworte:
Simmulation, Quantenrepeater

Kurzbeschreibung:
Ein Quantenrepeater ist wichtiger Baustein für Quantenkommunikation über große Distanzen. Hier soll ein Quantenrepeater der 1. Generation simmuliert werden.

Beschreibung

Im Gegensatz zu klassischen Signalen ist bei einem quantenmechanischen Zustand das Verstärken oder Kopieren des Signals nicht möglich, Der Quantenrepeater (1. Generation) basiert auf Verschränkung, und der Destillation. Die einzelnen Komponenten des Repeaters können unterschiedlich realisiert werden. Ziel der Simmulation ist es Vor- und Nachteile der verschiedenen möglichen Komponenten heraus zu finden.

Voraussetzungen

Betreuer:

• Diese Seite als PDF öffnen.

Adaptive List Decoding for Polar Codes

Beschreibung

The finite-length performance of polar codes can be improved by using successive cancellation list decoding. In this thesis, decoder design/implementation and performance prediction are investigated.

Reference:

[1] I. Tal and A. Vardy. "List decoding of polar codes." IEEE Transactions on Information Theory 61.5 (2015): 2213-2226.

[2] P. Yuan and F. Steiner. "Efficient Decoding Algorithms for Polar Codes based on 2×2 Non-Binary Kernels." International Symposium on Turbo Codes & Iterative Information Processing. 2018.

Voraussetzungen

Betreuer:

• Diese Seite als PDF öffnen.

An Introduction to Zero Error Identification Capacity

Stichworte:
Identification via channels, identification with zero mis-rejection probability

Beschreibung

1. The zero error capacity (C_0) for transmission (Shannon 1956) is the least upper bound of rates at which it is possible to transmit information across the noisy channel with zero probability of error.
   
   
2. Similarly a zero error capacity for identification (Ahlswede et al 1996) is the least upper bound of rates at which it is possible to identify information across the noisy channel with zero probability of type I error (type II is still nonzero).
   
   
3. In Identification scheme (Ahlwsede and Dueck 1989) the receiver is not interested in to estimate the sent message but rather it wants to answer reliably to a binary question with Yes/No answers. The question is: Is the actual sent message is my desired message or not?
   
   
4. Identification codes (with randomized encoder) the code size scales doubly exponential in block length, n (e^e^(nc)) which apparently outperform the classic Shannon codes with a code size of only single order exponential (e^(nc)).
   
   
5. As preliminaries, we study the Shannon zero error capacity as its own merit for transmission and a relation to Shannon zero error capacity of a graph. Further, we study and understand the identification capacity of a noisy channel and at the end we aims to perceive the zero error identification capacity of a noisy channel (i.e. type I error = 0 and type II error is not zero).
   
   
6. On the way of understanding C_0id, we need to address the zero-error capacities for transmission such as Erasure, List and Detection. Finally we draw the link between C_0id and C_0.

Voraussetzungen

Betreuer: