Capacité d'un canal | EPFL Graph Search

La capacité d'un canal, en génie électrique, en informatique et en théorie de l'information, est la limite supérieure étroite du débit auquel l'information peut être transmise de manière fiable sur un canal de communication. Suivant les termes du théorème de codage du canal bruyant, la capacité d'un canal donné est le débit d'information le plus élevé (en unités d'information par unité de temps) qui peut être atteint avec une probabilité d'erreur arbitrairement faible. La théorie de l'information, développée par Claude E. Shannon en 1948, définit la notion de capacité de canal et fournit un modèle mathématique permettant de la calculer. Le résultat clé stipule que la capacité du canal, telle que définie ci-dessus, est donnée par le débit maximum de l'information mutuelle entre l'entrée et la sortie du canal, où la maximisation se fait par rapport à la distribution de l'entrée. La notion de capacité du canal a été au cœur du développement des systèmes de communication modernes, fil

Hierarchical Beamforming for Large One-Dimensional Wireless Networks

Olivier Lévêque, Alla Merzakreeva

We consider a wireless network with a large number of source-destination pairs distributed over a line. Under line-of-sight propagation, this network has only one degree of freedom for communication. At high SNR, this one degree of freedom can be readily achieved by multi-hop relaying between nodes. At low SNR, however, the performance is determined by the power transfer in the network. We show that none of the existing architectures can achieve optimal capacity scaling. We develop a digital hierarchical beamforming architecture and show that it is scaling optimal. This result reveals a new regime for large wireless networks, where beamforming techniques are needed to achieve capacity.

Ieee2012

Symmetry in design and decoding of polar-like codes

Kirill Ivanov

The beginning of 21st century provided us with many answers about how to reach the channel capacity. Polarization and spatial coupling are two techniques for achieving the capacity of binary memoryless symmetric channels under low-complexity decoding algorithms. Recent results prove that another way to achieve capacity is via symmetry, which is the case of the Reed-Muller and extended Bose-Chaudhuri-Hocquenghem (BCH) codes. However, this proof holds only for erasure channel and maximum a posteriori decoding, which is computationally intractable for the general channels.In the first part of this thesis, we talk about the performance improvements that an automorphism group of the code brings on board. We propose two decoding algorithms for the Reed-Muller codes, which are invariant under a large group of permutations and are expected to benefit the most. The former is based on plugging the codeword permutations in successive cancellation decoding, and the latter utilizes the code representation as the evaluations of Boolean monomials. However, despite the performance improvements, it is clear that the decoding complexity grows quickly and becomes impractical for moderate-length codes. In the second part of this thesis, we provide an explanation for this observation. We use the Boolean polynomial representation of the code in order to show that polar-like decoding of sufficiently symmetric codes asymptotically needs an exponential complexity. The automorphism groups of the Reed-Muller and eBCH codes limit the efficiency of their polar-like decoding for long codes, hence we either should focus on short lengths or find another way. We demonstrate that asymptotically same restrictions (although with a slower convergence) hold for more relaxed condition that we call partial symmetry. The developed framework also enables us to prove that the automorphism group of polar codes cannot include a large affine subgroup.In the last part of this thesis, we address a completely different problem. A device-independent quantum key distribution (DIQKD) aims to provide private communication between parties and has the security guarantees that come mostly from quantum physics, without making potentially unrealistic assumptions about the nature of the communication devices. After the quantum part of the DIQKD protocol, the parties share a secret key that is not perfectly correlated. In order to synchronize, some information needs to be revealed publicly, which makes this formulation equivalent to the asymmetric Slepian-Wolf problem that can be solved using binary linear error-correction codes. As any amount of the revealed information reduces the key secrecy, the utilized code should operate close to the finite-length limits. The channel in consideration is non-standard and, due to its experimental nature, it can actually slightly differ from the considered models. In order to solve this problem, we designed a simple scheme using universal SC-LDPC codes and used in the first successful experimental demonstration of DIQKD protocol.

EPFL2022

Performance of Polar Codes for Channel and Source Coding

Nadine Hussami, Satish Babu Korada, Rüdiger Urbanke

Polar codes, introduced recently by Arikan, are the first family of codes known to achieve capacity of symmetric channels using a low complexity successive cancellation decoder. Although these codes, combined with successive cancellation, are optimal in this respect, their finite-length performance is not record breaking. We discuss several techniques through which their finite-length performance can be improved. We also study the performance of these codes in the context of source coding, both lossless and lossy, in the single-user context as well as for distributed applications.

2009

Symmetry in design and decoding of polar-like codes

Kirill Ivanov

EPFL2022