Publications by Rüdiger Urbanke

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Polar codes, invented by Arikan in 2009, are known to achieve the capacity of any binary-input memoryless outputsymmetric channel. Further, both the encoding and the decoding can be accomplished in O(N log(N)) real operations, where N is the blocklength. O ...

Investigations on spatially coupled codes have lead to the conjecture that, in the infinite size limit, the average input-output conditional entropy for spatially coupled low-density parity-check ensembles, over binary memoryless symmetric channels, equals ...

This paper is about a novel technique called spatial coupling and its application in the analysis of random constraint satisfaction problems (CSP). Spatial Coupling was recently invented in the area of error correcting codes where it has resulted in efficient capacity-achieving codes for a wide range of channels. However, this technique is not limited to problems in communications. It can be applied in the much broader context of graphical models. We describe here a general methodology for applying spatial

Consider a binary linear code of length N, minimum distance d(min), transmission over the binary erasure channel with parameter 0 < epsilon < 1 or the binary symmetric channel with parameter 0 < epsilon < 1/2, and block-MAP decoding. It was shown by Tillic ...

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

Motivated by the significant performance gains which polar codes experience when they are decoded with successive cancellation list decoders, we study how the scaling exponent changes as a function of the list size L. In particular, we fix the block error ...

We study a new encoding scheme for lossy source compression based on spatially coupled low-density generatormatrix codes. We develop a belief-propagation guided-decimation algorithm, and show that this algorithm allows to approach the optimal distortion of ...

We consider LDPC codes, transmission over the binary symmetric channel (BSC), and decoding using Gallager's algorithm A. For those ensembles whose threshold is determined by the behavior of the algorithm at the beginning of the decoding process we derive a ...

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

We want to extend the approximation of the error probability via a scaling approach from the BEC to general binary-input memoryless output-symmetric (BMS) channels. In particular, we consider such scaling laws for regular LDPC ensembles and message-passing ...

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

Advances in statistical physics relating to our understanding of large-scale complex systems have recently been successfully applied in the context of communication networks. Statistical mechanics methods can be used to decompose global system behavior int ...

Spatial coupling has recently emerged as a powerful paradigm to construct graphical models that work well under low-complexity message-passing algorithms. Although much progress has been made on the analysis of spatially coupled models under message passin ...

We consider lossy source compression of a binary symmetric source using polar codes and the low-complexity successive encoding algorithm. It was recently shown by Arikan that polar codes achieve the capacity of arbitrary symmetric binary-input discrete mem ...

The aim of this paper is to show that spatial coupling can be viewed not only as a means to build better graphical models, but also as a tool to better understand uncoupled models. The starting point is the observation that some asymptotic properties of gr ...

We show that the finite-length scaling parameters for irregular LDPC codes when used over the binary erasure channel can be computed without resorting to "covariance evolution''. We provide simple expressions that can be evaluated using solely the degree d ...

It is shown that any point in the capacity region of a Gaussian multiple-access channel is achievable by single-user coding without requiring synchronization among users, provided that each user splits data and signal into two parts. Based on this result, a new multiple-access technique called rate-splitting multiple accessing (RSMA) is proposed. RSMA is a code-division multiple-access scheme for the M-user Gaussian multiple-access channel for which the effort of finding the codes for the M users, of encodi

Polar coding solutions demonstrate excellent performance under the list decoding that is challenging to implement in hardware due to the path sorting operations. As a potential solution to this problem, permutation decoding recently became a hot research t ...

We consider lossy source compression of a binary symmetric source with Hamming distortion function. We show that polar codes combined with a low-complexity successive cancellation encoding algorithm achieve the rate-distortion bound. The complexity of both ...

Rüdiger Urbanke

Chat with Graph Search

Universal Polar Codes

How to Prove the Maxwell Conjecture Via Spatial Coupling - A Proof of Concept

New Bounds for Random Constraint Satisfaction Problems via Spatial Coupling

Almost Optimal Scaling of Reed-Muller Codes on BEC and BSC Channels

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

Scaling Exponent of List Decoders with Applications to Polar Codes

Lossy source coding via spatially coupled LDGM ensembles

Finite-Length Scaling For Gallager A

Improved decoding of second-order Reed-Muller codes

A Generalization of the Finite-Length Scaling Approach Beyond the BEC

On the Efficiency of Polar-Like Decoding for Symmetric Codes

Physics-Inspired Methods for Networking and Communications

Displacement Convexity - A Useful Framework for the Study of Spatially Coupled Codes

Polar Codes are Optimal for Lossy Source Coding

Spatial Coupling as a Proof Technique and Three Applications

Analytic Determination of Scaling Parameters

A rate-splitting approach to the Gaussian multiple-access channel

The Generalized Area Theorem and Some of its Consequences

Polar Codes Do Not Have Many Affine Automorphisms

Polar Codes are Optimal for Lossy Source Coding