# Fast Decoding of Low Density Lattice Codes

**Authors:** Shuiyin Liu, Yi Hong, Emanuele Viterbo, Alessia Marelli, Rino Micheloni  
**arXiv:** [1806.05524](https://arxiv.org/abs/1806.05524)  
**Date:** 2018-06-14  
**Summary page:** https://www.summarizepaper.com/en/paper/1806.05524v1/

## Key points

- Authors: Shuiyin Liu, Yi Hong, Emanuele Viterbo, Alessia Marelli, Rino Micheloni
- Topic: Fast Decoding of Low Density Lattice Codes (LDLC)
- LDLC can be efficiently decoded using a message-passing algorithm
- Convergence not proven
- High computational complexity ($O(2^d)$ operations at each variable node)
- Established sublinear or faster convergence rates for GA-based LDLC decoders in high SNR regions
- Introduced a novel GA-based LDLC decoder with reduced computational complexity ($O(d)$ operations per variable node)
- Proposed decoder maintains error correction performance while significantly reducing decoding complexity
- Simulation results validate effectiveness of the proposed decoder compared to existing methods

## Summary

In their paper titled "Fast Decoding of Low Density Lattice Codes," authors Shuiyin Liu, Yi Hong, Emanuele Viterbo, Alessia Marelli, and Rino Micheloni delve into the realm of low density lattice codes (LDLC) and propose a novel decoding approach to enhance efficiency. LDLC are a type of lattice codes that can be efficiently decoded using a message-passing algorithm. The authors highlight two key weaknesses in current GA-based decoders: firstly, the convergence of these approximate decoders has not been proven; secondly, the best-known decoder requires a high computational complexity of $O(2^d)$ operations at each variable node. To address these challenges, the authors make significant contributions in their research. Firstly, they establish through rigorous analysis that all GA-based LDLC decoders exhibit sublinear or faster convergence rates in regions characterized by high signal-to-noise ratios (SNR). This finding provides valuable insights into the performance and reliability of GA-based decoding methods for LDLC. Secondly, the authors introduce a novel GA-based LDLC decoder that significantly reduces computational complexity. Unlike existing decoders that require $O(2^d)$ operations at each variable node, their proposed decoder only necessitates $O(d)$ operations per variable node. This substantial reduction in complexity is achieved without compromising on error correction performance. Simulation results presented in the study validate the effectiveness of the proposed decoder by demonstrating comparable error correcting capabilities to the best-known decoder while offering substantially lower decoding complexity. The research findings pave the way for more efficient decoding strategies for LDLCs and contribute to advancing communication systems' reliability and performance in various applications.