Hauptseminar Digitale Kommunikationssysteme

Vortragende/r (Mitwirkende/r)
Nummer220085453
ArtSeminar
Umfang3 SWS
SemesterWintersemester 2019/20
UnterrichtsspracheDeutsch
Stellung in StudienplänenSiehe TUMonline
TermineSiehe TUMonline

Termine

Teilnahmekriterien & Anmeldung

Siehe TUMonlineDie Vorbesprechung findet am Donnerstag, den 17. Oktober 2019 in Raum N2408 um 15:00 statt. Bitte beachten Sie, dass Sie nur dann Ihren in TUM Online zugesicherten Fixplatz behalten können, wenn Sie bei der Vorbesprechung anwesend sind! Aus dem selben Grund sollten Sie auch erscheinen, falls Sie einen Wartelistenplatz haben - die Erfahrung hat gezeigt, dass Studenten oft nachrücken. Bitte wählen Sie >>vier<< der auf http://www.lnt.ei.tum.de/index.php?id=85 stehenden Themen und senden sie mit Prioritäten an Tobias Prinz (tobias.prinz@tum.de) bis spätestens Mittwoch, den 17. Oktober 2019 23:59. Die Themen werden nach dem first come first served Prinzip vergeben.

Lernziele

Nach dem erfolgreichen Absolvieren des Seminars sind die Studierenden in der Lage, sich in ein wissenschaftliches Thema einzulesen und dessen Kernpunkte zusammenzufassen. Sie koennen schriftliche, wissenschaftliche Arbeiten mit geigneter Strukturierung verfassen und haben die Faehigkeit erworben, die Kernpunkte der Arbeit in einer kurzen Praesentation vorzustellen. Die Studierenden haben ein grundsaetzliches Verstaendnis fuer die wissenschaftliche Arbeitsweise entwickelt.

Beschreibung

Für das Seminar werden verschiedene Themen aus den Gebieten der Digitalen Kommunikationstechnik (z.B. Sprach- und Videocodierung, Multimediaübertragung, AdHoc-Netzwerke, optische Übertragungstechnik, Informationstheorie und Kanalcodierung) ausgewählt, die von den Studenten selbständig bearbeitet, schriftlich zusammengefasst und abschliessend praesentiert werden.

Lehr- und Lernmethoden

Vortrag zur Methodenlehre im Plenum; Textanalyse in Einzelarbeit mit Betreuung; Verfassen von Artikeln in Selbsttaetigkeit; Praesentation mit Moderation und Diskussion

Studien-, Prüfungsleistung

Die Dauer des Vortrags ist 15 Minuten gefolgt von 5-10 Minuten für Fragen und Diskussionen. Der Vortrag sollte möglichst allgemein verständlich sein, dennoch besteht im Anschluss an die Präsentation die Möglichkeit, auf tiefergehende Fragen einzugehen. Die Bewertung erfolgt nach folgendem Schema: Ausarbeitung 50%, Vortrag 50%

Links

Organizational Matter

The preliminary meeting will be on Thursday, October 17, 2019 at 3PM in room N2408. Please note that only students which participate in this meeting can be considered for this seminar! The final number of participants will be limited by the number of available topics and if there are too many students, those with earlier registration will be given prioriy.

Below is a list of available topics. Please pick four of them and send your choice including priorities to Tobias Prinz latest until Thursday, October 17, 2019 23:59. The topics will be assigned by the first come, first served principle.

Available Topics

Modified Nonlinear Inverse Synthesis for Optical Transmission Systems with Lumped and Distributed Amplification Schemes (Benedikt Leible)

In an attempt to improve achievable rates for optical communication systems in the high input power regime, modulation via the nonlinear Fourier transform (NFT) has attracted some attention in recent years. Since the NFT was conceived for the deterministic lossless nonlinear Schrödinger equation (NLSE), the fiber loss present in realistic optical communication systems degrades the achievable data rates for NFT aided communication systems. To mitigate the negative effects of attenuation on the nonlinear spectra during propagation, a path loss average (PLA) approach was proposed in [1] and [2] for lumped EDFA and distributed Raman amplification respectively.

The students task is to first get familiar with the models for distributed Raman amplification [3, 4] and lumped EDFA amplification and get an overview of why the NFT is thought of as promising in the context of optical transmission systems, by reading the respective sections in [5] (Please note that it is not necessary to fully understand all the intricacies regarding the NFT in [5], since it would be too much for the scope of this seminar. However a basic understanding of the NFT is required and a short introduction into the topic should be given in the paper/talk.). Finally both PLA approaches should be reviewed/explained thoroughly, using references [1] and [2].

References

  • [1] Le, Son Thai et al. “Nonlinear Inverse Synthesis Technique for Optical Links with Lumped Amplification.”
  • [2] Le, Son Thai et al. "Modified Nonlinear Inverse Synthesis for Optical Links with Distributed Raman Amplification"
  • [3] Bromage, Jake. "Raman Amplification for Fiber Communications Systems."
  • [4] Muga, Nelson J., et al. "ASE Noise Simulation in Raman Amplification Systems."
  • [5] Yousefi, Mansoor I., and Frank R. Kschischang. "Information Transmission Using the Nonlinear Fourier Transform, Part I: Mathematical Tools."

Prerequisites

  • Optical Communication Systems
  • Nonlinear Optics

Belief Propagation Decoding of Polar Codes (Thomas Wiegart)

Polar codes [1] are capacity achieving codes with a successive cancellation decoder. Their finite-length performance is, however, relatively bad. Several approaches to improve the performance have been presented, such as list decoding and CRC-aided list decoding, which come with the cost of increased complexity. An other approach is to interpret the polar code as factor graph and perform belief propagation (BP) decoding [2]. BP is a well established iterative decoding procedure (known e.g. from LDPC codes) which usually allows efficient and parallel decoding.

The student's task is to understand polar codes and the idea of belief propagation (BP) decoding for polar codes. Furthermore, the student should summarize recend advances in BP decoding (such as [3],[4]).

References

Prerequisites

  • Channel Codes for Iterative Decoding

Burst-Insertions/Deletions-Correcting Codes (Lorenz Welter)

Error-correcting codes like a Hamming-Code or Reed-Solomon-Code are widely know for the usage to correct bit-errors (1->0, 0->1) or bit-erasures (0,1->E). However in digital communication and data storage systems also the insertion and deletion of bits is a typical error. For instance these can be caused through timing defects or packet-loss. Consequently there need to be code constructions capable of correcting these kind of errors.

The student's task is to understand the insertion/deletion-scenario and review proposed techniques to cope with one special scenario, the burst deletion case. Here the channel deletes only consecutive bits, i.e. a burst.

References

  • [1] L. Cheng, T. G. Swart, H. C. Ferreira and K. A. S. Abdel-Ghaffar, "Codes for correcting three or more adjacent deletions or insertions," 2014 IEEE International Symposium on Information Theory, Honolulu, HI, 2014, pp. 1246-1250.
  • [2] C. Schoeny, A. Wachter-Zeh, R. Gabrys and E. Yaakobi, "Codes Correcting a Burst of Deletions or Insertions," in IEEE Transactions on Information Theory, vol. 63, no. 4, pp. 1971-1985, April 2017.
  • [3] V. I. Levenshtein, "Asymptotically optimum binary codes with correction for losses of one or two adjacent bits", Syst. Theory Res., vol. 19, pp. 298-304, 1970.
  • [4] N. J. A. Sloane, "On single-deletion-correcting codes", Proc. Codes Designs, pp. 273-291, 2001.
  • [5] A. S. J. Helberg and H. C. Ferreira, "On multiple insertion/deletion correcting codes," in IEEE Transactions on Information Theory, vol. 48, no. 1, pp. 305-308, Jan. 2002.

Prerequisites

  • Channel Coding
  • (Recommended to take the lecture "Coding Theory for Storage and Networks")

Advances in Locally Repairable Codes (Lukas Holzbaur)

Locally repairable codes (LRC) are codes developed for distributed data storage, that allow for the repair of a small number of nodes from few other nodes and have attracted a lot of attention in recent years. Many constructions have since been introduced that achieve the Singleton-like bound [1,2] on the distance. A class of LRCs that are subcodes of Reed-Solomon codes, which is popular due to it's flexibility and small required field size, was introduced by Tamo et al. in [3]. One important part of this code construction are so-called "good polynomials", which are polynomials of a given degree that evaluate to a constant on given sets of evaluation points.

The students task is to understand the construction of [3] and investigate the construction and properties of such good polynomials.

References

  • [1] Gopalan, P., Huang, C., Simitci, H., & Yekhanin, S. (2012). On the Locality of Codeword Symbols. IEEE Transactions on Information Theory, 58(11), 6925–6934.
  • [2] Kamath, G. M., Prakash, N., Lalitha, V., & Kumar, P. V. (2013). Codes with local regeneration. In 2013 IEEE International Symposium on Information Theory (pp. 1606–1610). IEEE.
  • [3] Tamo, I., & Barg, A. (2014). A Family of Optimal Locally Recoverable Codes. IEEE Trans. Inf. Theory, 60(8), 4661–4676.

Prerequisites

  • Channel Coding

Photonic-aided analog-to-digital converter (ADC) enabled by synchronized frequency combs (Yizhao Jia)

Optical frequency combs (OFC), have very recently revolutionized fields of metrology, spectroscopy and optical communications, and are potential candidates to be used in photonic-aided ADC. Photonic-aided ADC aims at the acquisition of broadband signals with a high effective number of bits (ENOB) when compared to conventional ADC.

The student's task is to understand the principle and review proposed techniques for photonic-aided ADC.

References

  • [1] N. Fontaine et al., “Real-time full-field arbitrary optical waveform measurement,” Nature Photon., vol. 4, no. 4, pp. 248–254, Feb. 2010.
  • [2] George C. Valley, "Photonic analog-to-digital converters," Opt. Express 15, 1955-1982 (2007)
  • [3] Han, Y. & Jalali, B. Photonic time-stretched analog-to-digital converter: fundamental concepts and practical considerations. J. Lightwave Technol. 21, 3085–3103 (2003).
  • [4] "Optical frequency comb technology for ultra-broadband radio-frequency photonics". Laser and Photonics Reviews. 8: 368–393. May 2017.

Prerequisites

  • ADC Theory
  • Coherent Optical Communication Systems

Trellis Shaping (Fabian Steiner)

Trellis Shaping was invented by Forney in [1] and provides a coded modulation setup based on trellis coded modulation (TCM) that is able to achieve a shaping gain. The student is asked to review that scheme, and implement a small example by him/herself. Time permitting, further comparisons to state-of-the-art scheme should be done.

References

Prerequisites

  • Information Theory
  • Channel Coding
  • Channel Codes for Iterative Decoding

Code-Based Signature Scheme (Thomas Jerkovits)

McEliece is one of the oldest known public key cryptosystems. Though it was less widely studied than RSA, it is remarkable that all known attacks are still exponential. It is widely believed that code-based cryptosystems like McEliece do not allow practical digital signatures. The student should read the paper listed below and understand how the proposed code-based signature scheme works and point out the difficulties of code-based signature schemes.

References

  • [1] Courtois N.T., Finiasz M., Sendrier N. (2001) How to Achieve a McEliece-Based Digital Signature Scheme. In: Boyd C. (eds) Advances in Cryptology — ASIACRYPT 2001. ASIACRYPT 2001. Lecture Notes in Computer Science, vol 2248. Springer, Berlin, Heidelberg (www.iacr.org/archive/asiacrypt2001/22480158.pdf)

Prerequisites

  • Channel Coding

Code-Based Encryption (Julian Renner)

Assuming an attack of a sufficiently large quantum computer, several classical public-key algorithms based on factoring large integers and the discrete logarithm problem become insecure since computationally intensive mathematical problems become easy-to-solve. Thus, the National Insitute of Standards and Technology (NIST) started the Post-Quantum Cryptography Standardization. The student should understand the cryptosystem based on MDPC codes [1] and determine its applications in the NIST proposals.

References

Prerequisites

  • Basic Knowledge in Channel Coding

Bounds on Minimum Distance and Cardinality for Partially Stuck Memory Cells with Error Correction (Haider Al Kim)

Code constructions for masking $u$ partially stuck memory cells with $q$ levels and correcting additional random errors have been presented. However, it is necessary to derive bounds to understand how good these constructions actually are. It is possible to use code families that have generator matrix with all-ones vector to have upper bounds (necessary conditions). On the other hand, we can consider a sufficient condition ( Gilbert–Varshamov Bound) to show the existence of codes with certain parameters ($n$, $k$, $d$, and $q$) that can not only correct certain errors but also meet partially stuck cell constraints.

The student task is to understand the current constructions for masking partially-stuck-at memory cells with error correction and then to derive a general bound on the minimum distance and the cardinality with the constrains where the code construction has partially stuck cells.

References

  • [1] C. Heegard, “Partitioned linear block codes for computer memory with ‘stuck-at’ defects,” IEEE Trans. Inf. Theory, vol. 29, no. 6, pp. 831–842, Nov. 1983.
  • [2]  G. W. Burr et al., “Phase change memory technology,” J. Vac. Sci.Technol. B, vol. 28, no. 2, pp. 223–262, 2010.
  • [3]  A.Wachter-Zeh and E. Yaakobi, “Codes for Partially Stuck-At Memory Cells,” IEEE Transactions on Information Theory, vol. 62, no. 2, pp. 639–654, February 2016.

Prerequisites

  • Channel Coding
  • (Recommend to take the lecture "Coding Theory for Storage and Networks (Chapter 1 only)")

Belief Propagation Decoding of CRC-Polar Concatenated Codes (Tobias Prinz)

Polar Codes [1] are capacity achieving codes with a successive cancellation decoder. Their finite-length performance is, however, relatively bad. Several approaches to improve the performance have been presented, such as list decoding and CRC-aided list decoding, which come with the cost of increased complexity. An other approach is to interpret the polar code as factor graph and perform belief propagation (BP) decoding [2]. However, BP decoding cannot be used with outer CRC-codes directly which leads to a significant loss compared to CRC-aided list decoding.

In [3,4,5], methods with belief propagation decoding that include outer CRC-codes are presented. The students task is to summarize these methods and compare them to state-of-the-art CRC-aided list decoding.

References

Prerequisites

  • Channel Coding
  • Channel Codes for Iterative Decoding

Learning to Flip Successive Cancellation Decoding of Polar Codes (Peihong Yuan)

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 [1, 2] 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 [3, 4].

The task of the student is to understand the algorithms to find the flip positions.

References

  • [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).

Accuracy of the Split-Step Fourier Method for Wideband Optical Communication Systems (Daniel Plabst)

The propagation of pulses on the optical fiber is modelled by the Nonlinear Schrödinger Equation (NLSE). Since an analytical solution for the NLSE does not exist in the general case, reliable numerical techniques are necessary to estimate the evolution of the optical pulse along the fiber. A simple and efficient tool for solving the NLSE numerically is the Split-Step Fourier Method (SSFM) [1,2].

The SSFM divides the propagation distance into small increments and approximates the propagation within each increment. Unavoidably, numerical estimation errors are introduced, which can be mitigated by reducing the step size and therefore increasing the simulation complexity. In [3] the authors investigate the behavior of the SSFM accuracy versus the step size and aim at finding guidelines for efficient yet accurate numerical simulations. The authors choose a perturbation analysis of the SSFM error and argue that at practical accuracies, the well-known arguments of the Baker-Campbell-Hausdorff (BCH) [1,3] formula may not hold.

The student should understand how both the symmetric and asymmetric SSFM [1] are derived from the NLSE and what the BCH formula implies for both methods. Finally, the key ideas of [3] should be understood and compared to state-of-the-art usages of the SSFM.

References

  • [1] Agrawal, G. P. "Nonlinear fiber optics 5th ed." (2012): pp. 51.
  • [2] Schneider, Thomas. "Nonlinear optics in telecommunications". Springer Science & Business Media, 2004, pp. 139.
  • [3] S. Musetti, P. Serena and A. Bononi, "On the Accuracy of Split-Step Fourier Simulations for Wideband Nonlinear Optical Communications," in Journal of Lightwave Technology, vol. 36, no. 23, pp. 5669-5677, Dec.1, 2018.

Prerequisites

  • Optical Communication Systems

Linear and Nonlinear Frequency Division Multiplexing (Daniel Plabst)

Frequency Division Multiplexing The propagation of pulses on the optical fiber is modeled by the Nonlinear Schrödinger Equation (NLSE). Under certain assumptions, the NLSE can be solved using a tool called the Nonlinear Fourier Transform (NFT). Similar to the well-known Fourier Transform, which diagonalizes a linear convolution channel, the NFT converts a nonlinear dispersive Schrödinger channel into a number of parallel scalar channels. Information can now be encoded in the nonlinear spectrum and motivates Nonlinear Frequency-Division Multiplexing (NFDM), which is the counterpart of OFDM used for linear channels.

Whereas the mathematical foundation of the NFT requires a noise- and lossless Schrödinger channel, these assumption are not valid for practical optical communication systems. Recently, the achievable information rates between state-of-the-art Wavelength-Division Multiplexing (WDM) systems and NFDM systems were compared in [1] for the quasi-lossless case, when Raman amplification is assumed. Those results were extended in [2], considering periodic amplification using EDFAs.

The student should explain the idea behind NFDM and summarize the general results and shortcomings of [1] and [2].

References

  • [1] Mansoor I. Yousefi, Xianhe Yangzhang, "Linear and Nonlinear Frequency-Division Multiplexing", arxiv.org/abs/0807.3917
  • [2] X. Yangzhang, D. Lavery, P. Bayvel and M. I. Yousefi, "Impact of Perturbations on Nonlinear Frequency-Division Multiplexing," in Journal of Lightwave Technology, vol. 36, no. 2, pp. 485-494, 15 Jan.15, 2018.

Prerequisites

  • Optical Communication Systems

Insertion and Deletion Correction Using Convolutional Codes (Andreas Lenz)

Due to recent advances in modern storage technologies, such as DNA-based data storage and racetrack memories, the investigation of insertion and deletion (synchronization) errors has gained significant attention in the last years. This is because insertion and deletions errors are one of the limiting factors of such storage systems.

Since the information about the position of the received bits is not certain under the presence of insertion and deletion errors, it is required to design codes that can handle this uncertainty. One way is to use convolutional codes [1] and adapt the Viterbi decoder to be able to handle insertions and deletions. The advantage hereby is that the Viterbi can be used to simultaneously correct  synchronization and also conventional symbol substitution errors.

The task of the student will be to investigate convolutional codes for insertions and deletions and, if time allows, implement the Viterbi decoder.

References

  • [1] Mohamed F. Mansour and Ahmed H.Tewfik, "Convolutional Decoding in the Presence of Synchronization Errors", in IEEE Journal on Selected Areas in Communications, vol. 28, no. 2, pp. 218-227, 2010

Prerequisites

  • Channel Coding

Array Codes with Locality (Lia Liu)

Locality has been increasingly studied for coded distributed storage systems (DSS), since we want to keep the communication cost small when some erroneous nodes (e.g., erased, updated) need to be repaired via contacting other nodes. Large-scale DSS can be represented as arrays, where the entries represents the memory cells. Different components codes in [1-4] are considered to construct array codes. Each of them has certain strength and weakness while coping with different error models.

The student’s task is to understand the code constructions introduced in [1-4] and compare the schemes in terms of code rate, error/erasure correction capability, field size, etc.

References

  • [1] M. Blaum, and S. Hetzler, “Array Codes with Local Properties.” Preprint: arxiv.org/abs/1906.11731
  • [2] H. Liu, L. Holzbaur, and A. Wachter-Zeh. “Locality in Crisscross Error Correction.” XVI International Workshop on Algebraic and Combinatorial Coding Theory (ACCT), 2018. arxiv: arxiv.org/abs/1806.07496
  • [3] S. Kadhe, S. Rouayheb, I. Duursma, and A. Sprintson. “Codes With Locality in the Rank and Subspace Metrics.” IEEE Transactions on Information Theory 65 (2017): 5454-5468. arxiv: arxiv.org/abs/1707.05944
  • [4] N. Silberstein, T. Etzion, and M. Schwartz. “Locality and Availability of Array Codes Constructed from Subspaces.” 2017 IEEE International Symposium on Information Theory (ISIT), 2017. arxiv: arxiv.org/abs/1701.07501v3

Prerequisites

  • Channel Coding 

Security Reductions Proofs in Cryptography (Georg Maringer)

Cryptography has a long lasting history. At first cryptosystems have been considered which become insecure immediately after an attacker obtains knowledge on how the system works. Later on it was considered that the security of a cryptographic algorithm must only depend on keeping the respective key secure and not in hiding the algorithm from an attacker (Kerckhoff's principle).

In the last couple of years techniques for proving the security of algorithms have been developed. This requires a very rigorous analysis of why an algorithm is considered to be secure. It involves for example stating all the assumptions the designer of the algorithm makes about the resources an attacker has to break the algorithm.

Nowadays it is very common to reduce the security of a cryptographic algorithm to the difficulty of solving a mathematical problem which was proved to be extremely complex for a certain set of parameters. The designer of the algorithm in this case has to show that breaking the algorithm implies solving the underlying mathematical problem.

The student's task is to get familiar with different notions of security (CPA-security, CCA-security) and to be able to understand why certain algorithms show resistance against various attacks. The student should also give examples where security proofs were not rigorous enough and could be exploited by an attacker.

References

  • [1] J. Katz, and Y. Lindell, "Introduction to modern cryptography", second edition, 2015
  • [2] D. Bernstein, "Comparing proofs of security for lattice-based encryption", eprint archive, 2019. eprint: eprint.iacr.org/2019/691
  • [3] S. Cavallar et. al., "Factorization of a 512-bit RSA modulus", Eurocrypt 2000, URL: www.iacr.org/archive/eurocrypt2000/1807/18070001-new.pdf 
  • [4] K. Bhargavan, G. Leurent, "On the practical (in-)security of 64-bit block ciphers: collision attacks on HTTP over TLS and OpenVPN", CCS 2016, URL: sweet32.info
  • [5] A. Inoue, T. Iwata, K. Minematsu, B. Poettering, "Cryptanalysis of OCB2: attacks on authenticity and condentiality", Crypto 2019, URL: eprint.iacr.org/2019/311
  • [6] G. Leurent, T. Peyrin, "From collisions to chosen-prex collisions: application to full SHA-1", Eurocrypt 2019, URL: eprint.iacr.org/2019/459