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.
翻译:我们引入了一个新的算法, 实现最大隐隐隐隐隐隐隐( ML) 解码, 在有或没有记忆的离散频道中实现最大隐隐隐隐( ML) 解码。 在它里, 接收者排序顺序的噪声序列从最有可能到最可能最有可能的。 从此顺序中接收到的信号中将噪音从接收到的信号中减去, 代码簿中的第一个结果就是 ML 解码。 我们命名了这个算法, 用于猜测随机添加噪音的解码。 我们确定GRAND 在使用随机代码簿时, 能力不足的速率是实现能力。 对于能力不足的速率, 我们确定成功指数的速率。 我们从计算接收者数量上决定了这个计划的复杂性。 对于能力以外的速率, 这揭示了猜想的阈值数, 如果发现代码簿中的某个成员, 它可能是传输的代码字典。 我们引入了一种大致的 ML 解码计划, 这些接收者在使用固定数量的查询方法后放弃搜索, 我们将GRAND( GRAND) 和Amb登隐隐隐隐定义的方法, 我们用GRADRADADADADADADAD) 的计算方法。 虽然没有确定一个选择,, 并显示它的成功度的缩缩缩缩算。