Computable or Not Computable: Algorithmic Aspects of Channel Capacity

Grigorescu Vlass, Andrea Leticia

Andrea Leticia Grigorescu Vlass

If you experience problems opening the document, please try this link.

Original title:: Computable or Not Computable: Algorithmic Aspects of Channel Capacity
Translated title:: Berechenbar oder Nicht Berechenbar: Algorithmische Aspekte der Kanalkapazität
Author:: Grigorescu Vlass, Andrea Leticia
Year:: 2024
Document type:: Dissertation
Faculty/School:: TUM School of Computation, Information and Technology
Institution:: Theoretische Informationstechnik (Prof. Boche)
Advisor:: Boche, Holger (Prof. Dr.)
Referee:: Boche, Holger (Prof. Dr.); Poor, Vincent H. (Prof., Ph.D.)
Language:: en
Subject group:: ELT Elektrotechnik
TUM classification:: ELT 500
Abstract:: The advent of 6G technology is set to expand the accessibility of Internet of Things (IoT) and Tactile Internet applications, necessitating a highly reliable, secure, and efficient infrastructure, requiring the automated calculation of link capacities and resource allocations. This study employs the concept of Turing machines to delve into the algorithmic evaluation of communication rate benchmarks across various channel models, highlighting the fundamental performance limits of digital computing in this context. The study begins with the compound broadcast channel with confidential messages (BCC), examining the continuity of its secrecy capacity region with respect to system parameters and affirming the model's robustness. However, when considering finite state channels (FSCs) with feedback, it is revealed that their feedback capacity function is not Banach-Mazur computable, and consequently, not Borel-Turing computable. This indicates that either achievability or converse results—or possibly both—cannot be algorithmically computed. This implies that for these FSCs, it is impossible to algorithmically determine computable tight upper and lower bounds for their feedback capacities. This negative result raises a fundamental question: What is the simplest communication channel whose capacity cannot be numerically computed? This inquiry leads to the band-limited additive colored Gaussian noise (ACGN) channel, a model with a straightforward structure but intricate computational properties. It is shown that some ACGN channels with computable noise power spectral densities (psd) have non-computable capacities, and deriving computable tight upper bounds for these capacities is unfeasible. A significant finding is that when the noise psd is strictly positive and computable, the capacity of ACGN channels becomes computable and it is shown to be a #P₁-complete problem, indicating a higher complexity level than NP₁-complete problems. This complexity extends to finding the capacity-achieving distribution, also shown to be #P₁-complete. Additionally, the study examines the impact of computable convex constraints on the computability of optimal solutions in convex optimization scenarios, revealing that certain constraints hinder the precise computation of optimal points, even with strictly convex objective functions. This work highlights significant computational challenges and complexities in the design and evaluation of communication systems within the emerging 6G landscape, suggesting future research into alternative computing technologies for computing communication systems benchmarks, such as analog computing.
Translated abstract:: Die Einführung der 6G-Technologie soll die Zugänglichkeit von Internet of Things (IoT) und Taktiles-Internet-Anwendungen erweitern, was eine hochzuverlässige, sichere und effiziente Infrastruktur erfordert, einschließlich der automatisierten Berechnung von Verbindungskapazitäten und Ressourcenzuweisungen. Diese Studie verwendet das Konzept der Turing-Maschinen, um die algorithmische Bewertung von Kommunikationsraten-Benchmarks für verschiedene Kanalmodelle zu untersuchen und die grundlegenden Leistungsgrenzen der digitalen Datenverarbeitung in diesem Kontext hervorzuheben. Die Studie beginnt mit dem Compound Broadcast Channel with Confidential Messages. Sie untersucht die Stetigkeit der Secrecy-Kapazität in Bezug auf Systemparameter und bestätigt die Robustheit des Modells. Bei der Betrachtung von Finite State Channels (FSCs) mit Feedback wird jedoch festgestellt, dass ihre Feedback-Kapazitätsfunktion nicht Banach-Mazur-berechenbar und folglich nicht Borel-Turing-berechenbar ist. Dies deutet darauf hin, dass entweder Erreichbarkeits- oder Umkehrergebnisse---oder möglicherweise beide---nicht algorithmisch berechnet werden können. Dies bedeutet, dass es für diese FSCs unmöglich ist, algorithmisch berechenbare scharfe obere und untere Grenzen für ihre Feedback-Kapazitäten zu bestimmen. Dieses negative Ergebnis wirft eine grundlegende Frage auf: Was ist der einfachste Kommunikationskanal, dessen Kapazität nicht numerisch berechnet werden kann? Diese Frage führt zum Band-limited Additive Colored Gaussian Noise (ACGN) Kanal, einem Modell mit einer einfachen Struktur, aber komplexen Berechnungseigenschaften. Es wird gezeigt, dass einige ACGN-Kanäle mit berechenbaren Rauschleistungsdichtespektren nicht-berechenbare Kapazitäten haben und das Bestimmen berechenbarer scharfer oberer Grenzen für diese Kapazitäten unmöglich ist. Ein wichtiges Ergebnis ist, dass, wenn das Rauschleistungsdichtespektrum streng positiv und berechenbar ist, die Kapazität von ACGN-Kanälen berechenbar wird und zu einem #P₁-vollständigen Problem wird, was auf ein höheres Komplexitätsniveau als NP₁-vollständige Probleme hinweist. Diese Komplexität betrifft ebenso die Ermittlung des kapazitätserreichenden Leistungsdichtespektrums, welches ebenfalls als #P₁-vollständig nachgewiesen wird. Darüber hinaus untersucht diese Studie den Einfluss von berechenbaren konvexen Nebenbedingungen auf die Berechenbarkeit optimaler Lösungen in konvexen Optimierungsszenarien und zeigt, dass bestimmte konvexe Nebenbedingungen die genaue Berechnung optimaler Punkte verhindern, selbst bei streng konvexen Zielfunktionen. Diese Arbeit hebt bedeutende rechnerische Herausforderungen und Komplexitäten beim Entwurf und der Bewertung von Kommunikationssystemen innerhalb der zukünftigen 6G-Technologie hervor und schlägt zukünftige Forschungen zu alternativen Rechentechnologien für die Berechnung von Benchmarks für Kommunikationssysteme vor, wie beispielsweise Analog Computing.
WWW:: https://mediatum.ub.tum.de/?id=1739840
Date of submission:: 15.04.2024
Oral examination:: 22.10.2024
File size:: 930376 bytes
Pages:: 119
Urn (citeable URL):: https://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:91-diss-20241022-1739840-1-4
Last change:: 25.11.2024
BibTeX