A Lower Bound on the Success Probability of Binary Random Linear Network Codes Aided by Noise Decoding
Ioannis Chatzigeorgiou · IEEE Open Journal of the Communications Society · 2025
The decoding of binary random linear codes for packet erasures relies on receivers collecting a sufficient number of error-free coded packets for the reconstruction of a transmitted message. Syndrome decoding (SD), which conforms to the broad definition of guessing random additive noise decoding (GRAND), endeavors to repair partially-correct received coded packets – which would otherwise be discarded by the packet erasure decoder – and boost the probability of a receiver successfully recovering the transmitted message. This paper introduces a low-complexity variant of SD, dubbed single-error correcting SD (SEC-SD), and conducts an in-depth analysis of the success probability of packet erasure decoding aided by SEC-SD. The analysis leads to a practical lower bound on the success probability of packet erasure decoding complemented by SD, and provides guidance on how SEC-SD can be modified to potentially achieve a higher success probability than SD at a lower computational cost.