Comments on ' An efficient algorithm for computing free distance ' by Bahl , L .
Comments on ' An efficient algorithm for computing free distance ' by Bahl , L .
复制标题
对 Bahl, L 的“计算自由距离的有效算法”的评论。
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
M. Dong
中科院分区：
文献类型：
--
作者：
Paul Tawiah;Jeff Duer;S. Bryant;S. Larter;S. O’Brien;M. Dong
在上面的论文中，Bahl等人描述了一种用于计算卷积码的自由距离的双向搜索算法。这个算法有些缺陷这封信包含了一个校正版本的算法一起证明，校正版本总是计算的自由距离noncatastrophic代码。Bahl等人'已经描述了一种用于计算卷积码的自由距离的非常有效的双向搜索算法。但是，该算法也存在一些缺陷，这些缺陷将在本文的最后进行描述。下面是一个修正的版本，以及一个证明，确保新算法计算出非灾难性代码的真实自由距离。与原算法一样，新算法基于状态转移图。当一条路径到达一个状态时，它与路径类型（向前或向后）和路径权重的信息一起存储在一个数组中。如果有许多路径到达一个状态，则存储最低权重。因此，要存储的信息如下。S路径的终端状态。W到S的路径的最小汉明权重。T状态类型S。该类型由T1和T2两部分组成。T1指示状态S是D（ead）还是非D，并且T2是首先找到的到S的最小权重路径的类型F（orward）或B（ackward）。因此，我们有四种可能的类型：F、B、DF和DB。令W* 表示当前的上限d，。然后，速率-1/n码的算法如下。1972年8月31日接收，1973年2月5日修订。_. Aptho！@与传播理论实验室，丹麦技术大学，林比。丹麦。1升。R.巴尔角D. Cullum，W. D.弗雷泽和F. Jelinek，IEEE Trans. In@cm.理论，卷！？第18页。437-439，梅-！？72. L. J. L. Massey和M. K. Sam，“Hnear时序机的逆”，IEEE Trans. Comput.，第C-17卷，第100页。330-337，1968年4月。
In the above paper,’ Bahl et al. described a bidirectional search algorithm for computing the free distance of convolutional codes. There are some flaws in that algorithm. This correspondence contains a corrected version of the algorithm together with a proof that the corrected version always computes the free distance for noncatastrophic codes. Bahl et al.’ have described a very efficient bidirectional search algorithm for computing the free distance of convolutional codes. However, this algorithm had some flaws, which will be described at the end of this paper. A corrected version follows here, together with a proof that ensures that the new algorithm computes the true free distance for noncatastrophic codes.’ Like the original algorithm, the new one is based on the state transition diagram. When a state is reached by a path it is stored in an array together with information on the type of the path (forward or backward) and the weight of the path. If there are many paths to a state, then the lowest weight is stored. Thus the information to be stored is as follows. S Terminal state of path. W Minimum Hamming weight of paths to S known at the moment. T Type of state S. The type consists of two parts, Tl and T2. Tl indicates whether the state S is D(ead) or non-D and T2 is the type, F(orward) or B(ackward), of the minimum-weight path first found to S. Thus we have four possible types: F, B, DF, and DB. Let W* denote the current upper bound on d,,,,. Then the algorithm for a rate-l/n code is the following. Manuscript received August 31, 1972; revised February 5, 1973. _. The aptho! @ with the Labofatory for Communication Theory, Technical University of Denmark, Lyngby. Denmark. 1 L. R. Bahl, C. D. Cullum, W. D. Frazer, and F. Jelinek, IEEE Trans. In@cm. Theory, vol.!?-18, pp. 437-439, May-!?72. L J. L. Massey and M. K. Sam, “Inverses of hnear sequential machmes,” IEEE Trans. Comput., vol. C-17, pp. 330-337, Apr. 1968.