Publications associées à Code à longueur variable

A Functional Perspective on Information Measures

Since the birth of Information Theory, researchers have defined and exploited various information measures, as well as endowed them with operational meanings. Some were born as a "solution to a problem", like Shannon's Entropy and Mutual Information. Other ...

EPFL2022

Relaxed Locally Correctable Codes With Nearly-Linear Block Length And Constant Query Complexity

Alessandro Chiesa

Locally correctable codes (LCCs) are error correcting codes C : \Sigmak \rightarrow \Sigman which admit local algorithms that correct any individual symbol of a corrupted codeword via a minuscule number of queries. For systematic codes, this notion is stro ...

SIAM PUBLICATIONS2022

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

Design rules for optimizing unipolar coded Brillouin optical time-domain analyzers

Luc Thévenaz, Zhisheng Yang, Marcelo Alfonso Soto Hernandez, Simon Adrien Zaslawski, Zonglei Li

The performance of unipolar unicolor coded Brillouin optical time-domain analysis (BOTDA) is evaluated based on both Simplex and Golay codes. Four major detrimental factors that limit the system performance, including decoded-gain trace distortion, coding ...

2018

Coding for Communications and Secrecy

Mani Bastaniparizi

Shannon, in his landmark 1948 paper, developed a framework for characterizing the fundamental limits of information transmission. Among other results, he showed that reliable communication over a channel is possible at any rate below its capacity. In 2008, ...

EPFL2017

Towards an algebraic network information theory: Simultaneous joint typicality decoding

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

Recent work has employed joint typicality encoding and decoding of nested linear code ensembles to generalize the compute-forward strategy to discrete memoryless multiple-access channels (MACs). An appealing feature of these nested linear code ensembles is ...

2017

Interleaving with Coroutines: A Practical Approach for Robust Index Joins

Anastasia Ailamaki, Georgios Psaropoulos

Index join performance is determined by the efficiency of the lookup operation on the involved index. Although database indexes are highly optimized to leverage processor caches, main memory accesses inevitably increase lookup runtime when the index outsiz ...

VLDB Endowment Inc.2017

Revisiting the Sanders-Bogolyubov-Ruzsa Theorem in F-p(n) and its Application to Non-malleable Codes

Divesh Aggarwal

Non-malleable codes (NMCs) protect sensitive data against degrees of corruption that prohibit error detection, ensuring instead that a corrupted codeword decodes correctly or to something that bears little relation to the original message. The split-state ...

Ieee2016

Analysis of Spatially Coupled Systems using the Potential Functional with Applications to Coding Theory

Rafah El-Khatib

For the past 70 years or so, coding theorists have been aiming at designing transmission schemes with efficient encoding and decoding algorithms that achieve the capacity of various noisy channels. It was not until the '90s that graph-based codes, such as ...

EPFL2016

From Polar to Reed-Muller Codes : Unified Scaling, Non-standard Channels, and a Proven Conjecture

Marco Mondelli

The year 2016, in which I am writing these words, marks the centenary of Claude Shannon, the father of information theory. In his landmark 1948 paper "A Mathematical Theory of Communication", Shannon established the largest rate at which reliable communica ...

EPFL2016

Non-malleable Reductions and Applications

Divesh Aggarwal

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs [DPW10], provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completel ...

ACM2015

Scaling Exponent of List Decoders With Applications to Polar Codes

Rüdiger Urbanke, Seyed Hamed Hassani, Marco Mondelli

Motivated by the significant performance gains which polar codes experience under successive cancellation list decoding, their scaling exponent is studied as a function of the list size. In particular, the error probability is fixed, and the tradeoff betwe ...

Ieee-Inst Electrical Electronics Engineers Inc2015

Re-proving Channel Polarization Theorems : An Extremality and Robustness Analysis

Mine Alsan

The general subject considered in this thesis is a recently discovered coding technique, polar coding, which is used to construct a class of error correction codes with unique properties. In his ground-breaking work, Arikan proved that this class of codes, ...

EPFL2015

Enabling Complexity-Performance Trade-Offs for Successive Cancellation Decoding of Polar Codes

Andreas Peter Burg, Georgios Karakonstantis, Alexios Konstantinos Balatsoukas Stimming

Polar codes are one of the most recent advancements in coding theory and they have attracted significant interest. While they are provably capacity achieving over various channels, they have seen limited practical applications. Unfortunately, the successiv ...

2014

Linear Programming Decoding of Spatially Coupled Codes

Rüdiger Urbanke, Badih Ghazi

For a given family of spatially coupled codes, we prove that the linear programming (LP) threshold on the binary-symmetric channel (BSC) of the tail-biting graph cover ensemble is the same as the LP threshold on the BSC of the derived spatially coupled ens ...

Ieee-Inst Electrical Electronics Engineers Inc2014

LLR-based Successive Cancellation List Decoding of Polar Codes

Andreas Peter Burg, Mani Bastaniparizi, Alexios Konstantinos Balatsoukas Stimming

We present an LLR-based implementation of the successive cancellation list (SCL) decoder. To this end, we associate each decoding path with a metric which (i) is a monotone function of the path’s likelihood and (ii) can be computed efﬁciently from the chan ...

Ieee2014

An Efficient Time-frequency Algorithm for the Weak Signal Acquisition of Modernized GNSS Signals

Pierre-André Farine, Cyril Botteron, Jérôme Leclère, Vincenzo Capuano, Jia Tian, Yanguang Wang

The new GPS/Galileo/Compass signals use much longer code lengths and higher code frequencies than the GPS L1 C/A signal. As a result, they can provide improved ranging and anti-jamming performances. Unfortunately, their acquisition complexity is significan ...

2014

XOR-Based Encoding With Instantaneous Decoding for the Broadcast Erasure Channel With Feedback: The Three-User Case

We study the case of a three-user broadcast erasure channel with multiple unicast traffic sessions, where feedback from the users is fed back to the transmitter in the form of positive acknowledgment (ACK)/negative acknowledgment (NACK) messages. The capac ...

Institute of Electrical and Electronics Engineers2014

Data Compression via Logic Synthesis

Giovanni De Micheli, Andreas Peter Burg, Pierre-Emmanuel Julien Marc Gaillardon, Luca Gaetano Amarù

Nowadays, most software and hardware applications are committed to reduce the footprint and resource usage of data. In this general context, lossless data compression is a beneficial technique that encodes information using fewer (or at most equal number o ...

2014

Polar Coding Theorems for Discrete Systems

Eren Sasoglu

Polar coding is a recently invented technique for communication over binary-input memoryless channels. This technique allows one to transmit data at rates close to the symmetric-capacity of such channels with arbitrarily high reliability, using low-complex ...

EPFL2011