Q-ary GRAND enables maximum-likelihood decoding for linear codes
q-ary GRAND
Information Theory
Summary
Decoding messages that may have errors is a challenge when sending data reliably. This work introduces a decoding method called q-ary GRAND that works with codes using symbols from multiple values, not just binary. The authors created a way to systematically try possible error patterns, guaranteeing to find the most likely original message if given enough time. They tested it on Reed-Solomon codes and showed it matches the best possible decoding while balancing complexity and performance.
What this means in practice
- •For communication engineers: Implement higher accuracy decoding in multi-level symbol communication systems using q-ary GRAND for more reliable data transmission.
- •For storage system designers: Use q-ary GRAND to improve error correction in data storage devices employing Reed-Solomon codes for better data integrity.
Authors
Reza Dianat, Majid Nasiri Khormuji, Hiroyuki Seki
Abstract
We develop q-ary Guessing Random Additive Noise Decoding (GRAND) for linear codes over a q-ary alphabet. The decoder works on a sorted symbol-likelihood array and uses three local child generation rules to generate symbol deviation patterns. We then prove that these rules induce a monotone rooted spanning tree of the full row-index space, so best-first traversal gives maximum-likelihood (ML) decoding under unlimited search. Reed-Solomon simulations verify ML agreement and show the finite-budget performance-complexity tradeoff.