Publications related to Expander code

A Generalized Adjusted Min-Sum Decoder for 5G LDPC Codes: Algorithm and Implementation

Andreas Peter Burg, Alexios Konstantinos Balatsoukas Stimming, Yifei Shen, Yuqing Ren, Hassan Harb

5G New Radio (NR) has stringent demands on both performance and complexity for the design of low-density parity-check (LDPC) decoding algorithms and corresponding VLSI implementations. Furthermore, decoders must fully support the wide range of all 5G NR bl ...

Ieee-Inst Electrical Electronics Engineers Inc2024

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

Ultra-High-Throughput EMS NB-LDPC Decoder with Full-Parallel Node Processing

Hassan Harb

This paper presents an ultra-high-throughput decoder architecture for NB-LDPC codes based on the Hybrid Extended Min-Sum algorithm. We introduce a new processing block that updates a check node and its associated variable nodes in a fully pipelined way, th ...

SPRINGER2022

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

An Explicit Construction of Optimal Streaming Codes for Channels With Burst and Arbitrary Erasures

Damian Dudzicz

This paper presents a new construction of error correcting codes which achieves optimal recovery of a streaming source over a packet erasure channel. The channel model considered is the sliding-window erasure model, with burst and arbitrary losses, introdu ...

2020

New Results On The Pseudoredundancy

Jens Markus Zumbrägel, Zihui Liu

The concepts of pseudocodeword and pseudoweight play a fundamental role in the finite-length analysis of LDPC codes. The pseudoredundancy of a binary linear code is defined as the minimum number of rows in a parity-check matrix such that the corresponding ...

2019

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

On the Tradeoff Between Accuracy and Complexity in Blind Detection of Polar Codes

Andreas Peter Burg, Alexios Konstantinos Balatsoukas Stimming, Pascal Giard

Polar codes are a recent family of error-correcting codes with a number of desirable characteristics. Their disruptive nature is illustrated by their rapid adoption in the 5 th-generation mobile-communication standard, where they are used to protect contro ...

IEEE2018

Fast-SSC-Flip Decoding of Polar Codes

Andreas Peter Burg, Pascal Giard

Polar codes are widely considered as one of the most exciting recent discoveries in channel coding. For short to moderate block lengths, their error-correction performance under list decoding can outperform that of other modern error-correcting codes. Howe ...

2018

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

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

A Fast Hadamard Transform for Signals with Sub-linear Sparsity

Martin Vetterli, Robin Scheibler, Saeid Haghighatshoar

A new iterative low complexity algorithm has been presented for computing the Walsh-Hadamard transform (WHT) of an N dimensional signal with a K-sparse WHT, where N is a power of two and K = O(N^α), scales sub- linearly in N for some 0 < α < 1. Assuming a ...

2013

Efficient Implementation of Linear Programming Decoding

Mohammad Amin Shokrollahi

While linear programming (LP) decoding provides more flexibility for finite-length performance analysis than iterative message-passing (IMP) decoding, it is computationally more complex to implement in its original form, due to both the large size of the r ...

2011

Phase Transitions for Mutual Information

Mohammad Amin Shokrollahi, Amir Hesam Salavati, Krishna Kumar, Raj Kumar Krishna Kumar

We consider ensembles of binary linear error correcting codes, obtained by sampling each column of the generator matrix G or parity check matrix H independently from the set of all binary vectors of weight d (of appropriate dimension). We investigate the c ...

IEEE2010

Applications of Derandomization Theory in Coding

Mahdi Cheraghchi Bashi Astaneh

Randomized techniques play a fundamental role in theoretical computer science and discrete mathematics, in particular for the design of efficient algorithms and construction of combinatorial objects. The basic goal in derandomization theory is to eliminate ...

EPFL2010

Block copolymers and uses thereof

Jeffrey Alan Hubbell, Melody Swartz, Conlin O'Neil

An encoding/decoding apparatus and method using a low-density parity-check code (LDPC code) is disclosed. Basic column group information, serving as a set of information regarding positions of rows with weight 1, is extracted from a reference column in eac ...

2010

Protection of data from erasures using subsymbol based codes

Mohammad Amin Shokrollahi

An encoder uses output symbol subsymbols to effect or control a tradeoff of computational effort and overhead efficiency to, for example, greatly reduce computational effort for the cost of a small amount of overhead efficiency. An encoder reads an ordered ...

2008

Codes, graphs and graph based codes

Andrew Brown

This work is concerned with codes, graphs and their links. Graph based codes have recently become very prominent in both information theory literature and practical applications. While most research has centered around their performance under iterative dec ...

EPFL2007

Griffiths Kelly Sherman correlation inequalities: a useful tool in the theory of error correcting codes

Nicolas Macris

It is shown that a correlation inequality of statistical mechanics can be applied to linear low-density parity-check codes. Thanks to this tool we prove that, under a natural assumption, the exponential growth rate of regular low-density parity-check (LDPC ...

Institute of Electrical and Electronics Engineers2007