Guesswork Complexity of Ordered Statistics Decoding and its Saturation Threshold
Published in IEEE International Symposium on Information Theory (ISIT), 2025
This paper provides the first analytical characterization of the achievable guesswork complexity of ordered statistics decoding (OSD) in binary AWGN channels. This complexity is defined as the number of test error patterns (TEPs) processed by OSD immediately upon finding the correct codeword estimate. We show that for an order- k OSD of a (n,k) code, the average achievable guesswork complexity is tightly approximated by e−kpeI0(2kpe−−√), where I0 is the modified Bessel function and pe is determined by the code rate and SNR. Furthermore, for an order-m OSD (m< k), we identify a guesswork complexity saturation threshold ms=⌈kpe−−√⌉, beyond which increasing the OSD order improves error performance without raising the average achievable guesswork complexity. This threshold provides new insights for decoder design, particularly for lowrate codes where the complexity can saturate well before reaching the decoding order required for near-ML performance.