Concept

Binary symmetric channel

Related publications (30)

On Speed and Advantage : Results in Information Velocity and Monitoring Problems

Information theory has allowed us to determine the fundamental limit of various communication and algorithmic problems, e.g., the channel coding problem, the compression problem, and the hypothesis testing problem. In this work, we revisit the assumptions ...

EPFL2024

On the (Im)possibility of Commitment over Gaussian Unfair Noisy Channels

Commitment is a key primitive which resides at the heart of several cryptographic protocols. Noisy channels can help realize information-theoretically secure commitment schemes; however, their imprecise statistical characterization can severely impair such ...

2023

On the Efficiency of Polar-Like Decoding for Symmetric Codes

Rüdiger Urbanke, Kirill Ivanov

The recently introduced polar codes constitute a breakthrough in coding theory due to their capacity-achieving property. This goes hand in hand with a quasilinear construction, encoding, and successive cancellation list decoding procedures based on the Plo ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022

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 algor ...

EPFL2022

The Stability of Low-Density Parity-Check Codes and Some of its Consequences

Rüdiger Urbanke, Wei Liu

We study the stability of low-density parity-check codes under blockwise or bitwise maximum a posteriori decoding, where transmission takes place over a binary-input memoryless output-symmetric channel. Our study stems from the consideration of constructin ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2021

Adaptive Path Interpolation Method for Sparse Systems: Application to a Censored Block Model

Nicolas Macris, Jean François Emmanuel Barbier, Chun Lam Chan

Recently, a new adaptive path interpolation method has been developed as a simple and versatile scheme to calculate exactly the asymptotic mutual information of Bayesian inference problems defined on dense factor graphs. These include random linear and gen ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2021

On the applicability of the Fujisaki-Okamoto transformation to the BIKE KEM

Dusan Kostic

The QC-MDPC code-based KEM BIKE is one of the Round-3 candidates of the NIST PQC standardization project. Its Round-2 specification document described variants claiming to have IND-CCA security. The security proof used the Fujisaki-Okamoto transformation a ...

TAYLOR & FRANCIS LTD2021

Enhancing the Reliability of Dense LoRaWAN Networks With Multi-User Receivers

Andreas Peter Burg, Joachim Tobias Tapparel, Mathieu Pierre Xhonneux

LoRaWAN is a low-power wireless technology that provides long-range connectivity to battery-powered Internet of Things (IoT) devices. To minimize the energy consumption of the IoT nodes, LoRaWAN networks use for the uplink a pure non-slotted ALOHA multiple ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2021

Over-the-Air Computation via Reconfigurable Intelligent Surface

Yuning Jiang, Wei Chen

Over-the-air computation (AirComp) is a disruptive technique for fast wireless data aggregation in Internet of Things (IoT) networks via exploiting the waveform superposition property of multiple-access channels. However, the performance of AirComp is bott ...

2021

On the Universality of Low-Density Parity-Check Block Codes

Rüdiger Urbanke, Wei Liu

An important class of modern channel codes is the capacity-achieving sequences of low-density parity-check block codes. Such sequences are usually designed for the binary erasure channel and are decoded by iterative message-passing algorithms. In this pape ...

IEEE2020

Recursive Projection-Aggregation Decoding of Reed-Muller Codes

Emmanuel Abbé, Min Ye

We propose a new class of efficient decoding algorithms for Reed-Muller (RM) codes over binary-input memoryless channels. The algorithms are based on projecting the code on its cosets, recursively decoding the projected codes (which are lower-order RM code ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020

Compute-Forward for DMCs: Simultaneous Decoding of Multiple Combinations

Michael Christoph Gastpar, Sung Hoon Lim, Adriano Pastore, Chen Feng

Algebraic network information theory is an emerging facet of network information theory, studying the achievable rates of random code ensembles that have algebraic structure, such as random linear codes. A distinguishing feature is that linear combinations ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020

Improved decoding of second-order Reed-Muller codes

Rüdiger Urbanke, Kirill Ivanov

In this paper, we consider low-complexity decoding of second-order Reed-Muller codes. A class of polynomial-time algorithms, based on the projections onto first-order codes, is studied. An old representative of this class, originally developed for binary s ...

IEEE2019

Displacement Convexity in Spatially Coupled Scalar Recursions

Rüdiger Urbanke, Nicolas Macris, Rafah El-Khatib

We introduce a technique for the analysis of general spatially coupled systems that are governed by scalar recursions. Such systems can be expressed in variational form in terms of a potential function. We show, under mild conditions, that the potential fu ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2019

Permutation-based Decoding of Reed-Muller Codes in Binary Erasure Channel

Rüdiger Urbanke, Kirill Ivanov

In this paper, we consider the problem of decoding Reed-Muller (RM) codes in binary erasure channel. We propose a novel algorithm, which exploits several techniques, such as list recursive (successive cancellation) decoding based on Plotkin decomposition, ...

IEEE2019

Reed-Muller codes polarize

Emmanuel Abbé, Min Ye

Reed-Muller (RM) codes were introduced in 1954 and have long been conjectured to achieve Shannon's capacity on symmetric channels. The activity on this conjecture has recently been revived with the emergence of polar codes. RM codes and polar codes are gen ...

IEEE COMPUTER SOC2019

Bits through Time

Elie Najm

In any communication system, there exist two dimensions through which the information at the source becomes distorted before reaching the destination: the noisy channel and time. Messages transmitted through a noisy channel are susceptible to modification ...

EPFL2019

LDPC Coded Multiuser Shaping for the Gaussian Multiple Access Channel

Alexios Konstantinos Balatsoukas Stimming

The joint design of input constellation and low-density parity-check (LDPC) codes to approach the symmetric capacity of the two-user Gaussian multiple access channel is studied. More specifically, multilevel coding is employed at each user to construct a h ...

IEEE2019

From LDPC Block to LDPC Convolutional Codes: Capacity, Stability, and Universality

Wei Liu

In his landmark paper "A Mathematical Theory of Communication," the founding father of information theory and coding theory, Claude E. Shannon, established the largest rate at which reliable communication is possible and he revealed that the key to this re ...

EPFL2019

Statistical Physics Methods for Community Detection

Chun Lam Chan

This thesis is devoted to information-theoretic aspects of community detection. The importance of community detection is due to the massive amount of scientific data today that describes relationships between items from a network, e.g., a social network. I ...

EPFL2019