Guessing What, Noise or Codeword?

Guessing What, Noise or Codeword?

30 Jan 2024 | Xiao Ma
This paper distinguishes two guessing algorithms for decoding binary linear codes: guessing noise decoding (GND) and guessing codeword decoding (GCD). It proves that GCD is a maximum likelihood (ML) decoding algorithm and more efficient than GND for most practical applications. Several variants of ordered statistic decoding (OSD) are introduced to balance the complexity of Gaussian elimination (GE) and guessing. These variants may be useful for decoding short block codes in high signal-to-noise ratio (SNR) regions. The paper discusses the ML decoding problem, which is NP-hard for general linear block codes. However, it is feasible for short codes in high SNR regions, especially for ultra-reliable low-latency communication (URLLC). Examples of ML decoding include Chase decoding and ordered statistic decoding (OSD). The OSD algorithm is universal and near-optimal, applicable to various short linear block codes, including BCH, LDPC, and polar codes. In contrast, the guessing random additive noise decoding (GRAND) algorithm guesses noise sequences from most likely to least likely until a valid codeword is found. GRAND is an ML algorithm when the number of guesses is unlimited. Variants of GRAND, such as soft-GRAND, GRAND with symbol reliability information, and ordered reliability bits GRAND, are also discussed. The paper analyzes the differences between GND and GCD, showing that GCD is more efficient in terms of the number of guesses. It proves that GCD is an ML algorithm and requires fewer guesses than GND. Simulation results validate this analysis, showing that GCD requires fewer guesses than GND, especially for low-rate codes. The paper also discusses variants of OSD, such as LC-OSD, ROSD, and quasi-OSD, which aim to reduce complexity and delay. Simulation results show that these variants perform well in various scenarios, with GCD requiring fewer guesses than GND. The paper concludes that GCD is a more efficient and universal decoding algorithm compared to GND, especially for short block codes in high SNR regions.This paper distinguishes two guessing algorithms for decoding binary linear codes: guessing noise decoding (GND) and guessing codeword decoding (GCD). It proves that GCD is a maximum likelihood (ML) decoding algorithm and more efficient than GND for most practical applications. Several variants of ordered statistic decoding (OSD) are introduced to balance the complexity of Gaussian elimination (GE) and guessing. These variants may be useful for decoding short block codes in high signal-to-noise ratio (SNR) regions. The paper discusses the ML decoding problem, which is NP-hard for general linear block codes. However, it is feasible for short codes in high SNR regions, especially for ultra-reliable low-latency communication (URLLC). Examples of ML decoding include Chase decoding and ordered statistic decoding (OSD). The OSD algorithm is universal and near-optimal, applicable to various short linear block codes, including BCH, LDPC, and polar codes. In contrast, the guessing random additive noise decoding (GRAND) algorithm guesses noise sequences from most likely to least likely until a valid codeword is found. GRAND is an ML algorithm when the number of guesses is unlimited. Variants of GRAND, such as soft-GRAND, GRAND with symbol reliability information, and ordered reliability bits GRAND, are also discussed. The paper analyzes the differences between GND and GCD, showing that GCD is more efficient in terms of the number of guesses. It proves that GCD is an ML algorithm and requires fewer guesses than GND. Simulation results validate this analysis, showing that GCD requires fewer guesses than GND, especially for low-rate codes. The paper also discusses variants of OSD, such as LC-OSD, ROSD, and quasi-OSD, which aim to reduce complexity and delay. Simulation results show that these variants perform well in various scenarios, with GCD requiring fewer guesses than GND. The paper concludes that GCD is a more efficient and universal decoding algorithm compared to GND, especially for short block codes in high SNR regions.
Reach us at info@study.space