LIMITED SEARCH TRELLIS DECODING OF CONVOLUTIONAL-CODES
LIMITED SEARCH TRELLIS DECODING OF CONVOLUTIONAL-CODES
复制标题
DOI：
10.1109/18.42212
复制
发表时间：
1989-09-01
影响因子：
2.5
通讯作者：
ANDERSON, JB
中科院分区：
文献类型：
--
作者：
ANDERSON, JB
计算了在二进制对称信道上纠正t个错误的宽度优先树或网格解码器所需的最少存储和节点计算。宽度优先解码器与相同长度的代码路径一起工作，没有回溯。维特比算法是这种类型的穷举网格解码器;其他方案着眼于树或网格路径的子集。对于随机树码，证明了关于所需路径的渐近数和路径深度的定理。对于具体的卷积码，测量了t个错误序列的最坏情况存储。在这两种情况下，最佳解码器存储对t具有相同的简单依赖性。M算法和G. J. Foschini提出的算法（同上，第23卷，第605 -9，9月1977年）和S. J.西蒙斯（博士。diss.，皇后大学，安大略省金斯顿，加拿大）是最优的，或者接近最优;它们都比维特比算法有效得多。<>
The least storage and node computation required by a breadth-first tree or trellis decoder that corrects t errors over the binary symmetric channels is calculated. Breadth-first decoders work with code paths of the same length, without backtracking. The Viterbi algorithm is an exhaustive trellis decoder of this type; other schemes look at a subset of the tree or trellis paths. For random tree codes, theorems about the asymptotic number of paths required and their depth are proved. For concrete convolutional codes, the worst case storage for t error sequences is measured. In both cases the optimal decoder storage has the same simple dependence on t. The M algorithm and algorithms proposed by G.J. Foschini (ibid., vol.IT-23, p.605-9, Sept. 1977) and by S.J. Simmons (PhD. diss., Queens Univ., Kingston, Ont., Canada) are optimal, or nearly so; they are all far more efficient than the Viterbi algorithm.<>