Duffy, Ken R. and Li, Jianje and Medard, Muriel (2018) Capacity-achieving Guessing Random Additive Noise Decoding (GRAND). Working Paper. arXiv.

Preview

Download (914kB) | Preview

Abstract

We introduce a new algorithm for realizing Maximum Likelihood (ML) decoding in discrete channels with or without memory. In it, the receiver rank orders noise sequences from most likely to least likely. Subtracting noise from the received signal in that order, the first instance that results in a member of the code-book is the ML decoding. We name this algorithm GRAND for Guessing Random Additive Noise Decoding. We establish that GRAND is capacity-achieving when used with random code-books. For rates below capacity we identify error exponents, and for rates beyond capacity we identify success exponents. We determine the scheme's complexity in terms of the number of computations the receiver performs. For rates beyond capacity, this reveals thresholds for the number of guesses by which if a member of the code-book is identified it is likely to be the transmitted code-word. We introduce an approximate ML decoding scheme where the receiver abandons the search after a fixed number of queries, an approach we dub GRANDAB, for GRAND with ABandonment. While not an ML decoder, we establish that the algorithm GRANDAB is also capacity-achieving for an appropriate choice of abandonment threshold, and characterize its complexity, error and success exponents. Worked examples are presented for Markovian noise that indicate these decoding schemes substantially out-perform the brute force decoding approach.

Item Type:	Monograph (Working Paper)
Keywords:	Discrete channels; Maximum likelihood decoding; Approximate ML decoding; Error probability; Channel coding;
Academic Unit:	Faculty of Science and Engineering > Research Institutes > Hamilton Institute
Item ID:	10172
Identification Number:	arXiv:1802.07010
Depositing User:	Dr Ken Duffy
Date Deposited:	02 Nov 2018 17:30
Publisher:	arXiv
URI:
Use Licence:	This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

Repository Staff Only(login required)

Item control page

Downloads

Origin of downloads