The Guesswork of Ordered Statistics Decoding: Guesswork Complexity and Decoder Design
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910747865382912 |
|---|---|
| author | Yue, Chentao She, Changyang Vucetic, Branka Li, Yonghui |
| author_facet | Yue, Chentao She, Changyang Vucetic, Branka Li, Yonghui |
| contents | This paper investigates guesswork over ordered statistics and formulates the achievable guesswork complexity of ordered statistics decoding (OSD) in binary additive white Gaussian noise (AWGN) channels. The achievable guesswork complexity is defined as the number of test error patterns (TEPs) processed by OSD immediately upon finding the correct codeword estimate. The paper first develops a new upper bound for guesswork over independent sequences by partitioning them into Hamming shells and applying Hölder's inequality. This upper bound is then extended to ordered statistics, by constructing the conditionally independent sequences within the ordered statistics sequences. Next, we apply these bounds to characterize the statistical moments of the OSD guesswork complexity. We show that the achievable guesswork complexity of OSD at maximum decoding order can be accurately approximated by the modified Bessel function, which increases exponentially with code dimension. We also identify a guesswork complexity saturation threshold, where increasing the OSD decoding order beyond this threshold improves error performance without further raising the achievable guesswork complexity. Finally, the paper presents insights on applying these findings to enhance the design of OSD decoders. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_18488 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Guesswork of Ordered Statistics Decoding: Guesswork Complexity and Decoder Design Yue, Chentao She, Changyang Vucetic, Branka Li, Yonghui Information Theory This paper investigates guesswork over ordered statistics and formulates the achievable guesswork complexity of ordered statistics decoding (OSD) in binary additive white Gaussian noise (AWGN) channels. The achievable guesswork complexity is defined as the number of test error patterns (TEPs) processed by OSD immediately upon finding the correct codeword estimate. The paper first develops a new upper bound for guesswork over independent sequences by partitioning them into Hamming shells and applying Hölder's inequality. This upper bound is then extended to ordered statistics, by constructing the conditionally independent sequences within the ordered statistics sequences. Next, we apply these bounds to characterize the statistical moments of the OSD guesswork complexity. We show that the achievable guesswork complexity of OSD at maximum decoding order can be accurately approximated by the modified Bessel function, which increases exponentially with code dimension. We also identify a guesswork complexity saturation threshold, where increasing the OSD decoding order beyond this threshold improves error performance without further raising the achievable guesswork complexity. Finally, the paper presents insights on applying these findings to enhance the design of OSD decoders. |
| title | The Guesswork of Ordered Statistics Decoding: Guesswork Complexity and Decoder Design |
| topic | Information Theory |
| url | https://arxiv.org/abs/2403.18488 |