标题： 通用最大似然（列表）解码通过快速向量-矩阵乘法 显示英文标题

标题： Universal Maximum Likelihood (List) Decoding via Fast Vector-Matrix Multiplication

摘要： 最大似然（ML）解码对于任意分组码仍然是根本困难的，最坏情况下的时间复杂度（以总乘法次数衡量）不优于直接穷举搜索，后者对于一个$q^{k} n$码需要$[n,k]_q$次操作。 本文介绍了一种简单且与码无关的框架，将最坏情况下的复杂度降低了一个因子$n$，降至$q^{k}$次操作，这在实践中是一种非常理想的减少。 该结果适用于一般无记忆信道上的线性和非线性分组码，以及硬判决和软判决解码。 它自然扩展到符号间干扰（ISI）信道和ML列表解码，仅带来可忽略的复杂度增加。 我们的核心见解是，当接收器接收到每个序列时，该序列对于码本中每个码字的条件概率 （即\emph{似然性}）可以表示为两个精心构造向量的内积——第一个依赖于接收到的序列，第二个依赖于该码字本身。 因此，评估码本中所有码字的可能性 reduces 到一次向量-矩阵乘法，ML解码（MLD）变成在结果向量中选择最大元素的简单任务。 唯一的非平凡成本在于向量-矩阵乘积。 然而，我们的矩阵构造允许使用 Mailman 算法来降低此成本。 这种时间减少是以高空间复杂度为代价的，需要$\mathcal{O}(q^{k+1} n)$的空间来存储预计算的码本矩阵。 显示英文摘要

摘要： Maximum-likelihood (ML) decoding for arbitrary block codes remains fundamentally hard, with worst-case time complexity-measured by the total number of multiplications-being no better than straightforward exhaustive search, which requires $q^{k} n$ operations for an $[n,k]_q$ code. This paper introduces a simple, code-agnostic framework that reduces the worst-case complexity by a factor of $n$, down to $q^{k}$ operations, a highly desirable reduction in practice. The result holds for both linear and nonlinear block codes over general memoryless channels and under both hard-decision and soft-decision decoding. It naturally extends to intersymbol-interference (ISI) channels and ML list decoding with only a negligible increase in complexity. Our core insight is that, upon receipt of each sequence at the receiver, the conditional probability of that sequence for each codeword in the codebook (i.e., the \emph{likelihood}) can be expressed as the inner product of two carefully constructed vectors -- the first depending on the received sequence, and the second on that codeword itself. As a result, evaluating the likelihoods for all codewords in the codebook reduces to a single vector-matrix multiplication, and ML decoding (MLD) becomes the simple task of picking the maximum entry in the resulting vector. The only non-trivial cost lies in the vector-matrix product. However, our matrix construction allows the use of the Mailman algorithm to reduce this cost. This time reduction is achieved at the cost of high space complexity, requiring $\mathcal{O}(q^{k+1} n)$ space to store the pre-computed codebook matrix.