Unique and Minimum Distance Decoding of Linear Codes with Reduced Complexity

2010/03/24 by Spasov, Dejan
#FOS: Computer and information sciences #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.1003.4627

Abstract

We show that for (systematic) linear codes the time complexity of unique decoding is O(n²q^{nRH(delta/2/R)}) and the time complexity of minimum distance decoding is O(n²q^nRH(delta/R)). The proposed algorithm inspects all error patterns in the information set of the received message of weight less than d/2 or d, respectively.

Related

• Finding the minimum distance and decoding linear codes with Gaussian Elimination Method
• On the Computational Complexity of Blind Detection of Binary Linear Codes
• On error distance of received words with fixed degrees to Reed-Solomon code
• Fast generalized minimum-distance decoding of algebraic-geometry and Reed-Solomon codes
• Simple Codes and Sparse Recovery with Fast Decoding