MURAL - Maynooth University Research Archive Library

    Capacity-Achieving guessing random additive noise decoding

    Duffy, Ken R. and Li, Jiange and Medard, Muriel (2019) Capacity-Achieving guessing random additive noise decoding. IEEE Transactions on Information Theory, 65 (7). ISSN 0018-9448

    Download (1MB) | Preview

    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...

    Add this article to your Mendeley library


    We introduce a new algorithm for realizing maximum likelihood (ML) decoding for arbitrary codebooks in discrete channels with or without memory, in which 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 codebook 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 codebooks. 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 that the receiver performs. For rates beyond capacity, this reveals thresholds for the number of guesses by which, if a member of the codebook is identified, that 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 capacityachieving 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 outperform the brute force decoding approach.

    Item Type: Article
    Keywords: Discrete channels; maximum likelihood decoding; approximate ML decoding; error probability; channel coding;
    Academic Unit: Faculty of Science and Engineering > Electronic Engineering
    Item ID: 13476
    Identification Number:
    Depositing User: Dr Ken Duffy
    Date Deposited: 05 Nov 2020 10:57
    Journal or Publication Title: IEEE Transactions on Information Theory
    Publisher: IEEE
    Refereed: Yes
    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)

    View Item Item control page


    Downloads per month over past year

    Origin of downloads