A Heuristic for Ordering a Linear Block Code to Minimize Trellis State Complexity
A Heuristic for Ordering a Linear Block Code to Minimize Trellis State Complexity
复制标题
排序线性分组码以最小化网格状态复杂性的启发式方法
DOI：
--
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
G. B. Horn
中科院分区：
文献类型：
--
作者：
F. Kschischang;G. B. Horn
| 分组码格形理论和应用中的一个重要问题是寻找一个使给定码的格形状态复杂度最小的坐标置换。在本文中，我们表明，最小化一个给定的组件的状态复杂性proole的问题是NP-完全的。我们描述了一个算法，虽然不能保证找到最优的坐标排序，但使用启发式下降技术找到问题的“好”解。我们已将此算法应用于各种代码，我们的结果列表。
| An important problem in the theory and application of block code trellises is to nd a coordinate permutation for a given code that minimizes the trellis state complexity. In this paper we show that the problem of minimizing a given component of the state complexity proole is NP-complete. We describe an algorithm, though not guaranteed to nd an optimal coordinate ordering, uses a heuristic descent technique to nd \good" solutions to the problem. We have applied this algorithm to various codes, and our results are tabulated.