A Balanced Tree Transformation to Reduce GRAND Queries
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912771898081280 |
|---|---|
| author | Rapp, Lukas Feng, Jiewei Médard, Muriel Duffy, Ken R. |
| author_facet | Rapp, Lukas Feng, Jiewei Médard, Muriel Duffy, Ken R. |
| contents | Guessing Random Additive Noise Decoding (GRAND) and its variants, known for their near-maximum likelihood performance, have been introduced in recent years. One such variant, Segmented GRAND, reduces decoding complexity by generating only noise patterns that meet specific constraints imposed by the linear code. In this paper, we introduce a new method to efficiently derive multiple constraints from the parity check matrix. By applying a random invertible linear transformation and reorganizing the matrix into a tree structure, we extract up to log2(n) constraints, reducing the number of decoding queries while maintaining the structure of the original code for a code length of n. We validate the method through theoretical analysis and experimental simulations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_19033 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Balanced Tree Transformation to Reduce GRAND Queries Rapp, Lukas Feng, Jiewei Médard, Muriel Duffy, Ken R. Information Theory Guessing Random Additive Noise Decoding (GRAND) and its variants, known for their near-maximum likelihood performance, have been introduced in recent years. One such variant, Segmented GRAND, reduces decoding complexity by generating only noise patterns that meet specific constraints imposed by the linear code. In this paper, we introduce a new method to efficiently derive multiple constraints from the parity check matrix. By applying a random invertible linear transformation and reorganizing the matrix into a tree structure, we extract up to log2(n) constraints, reducing the number of decoding queries while maintaining the structure of the original code for a code length of n. We validate the method through theoretical analysis and experimental simulations. |
| title | A Balanced Tree Transformation to Reduce GRAND Queries |
| topic | Information Theory |
| url | https://arxiv.org/abs/2503.19033 |