Calculating the minimum distance of linear block codes via Integer Programming
Calculating the minimum distance of linear block codes via Integer Programming
复制标题
通过整数规划计算线性块代码的最小距离
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
H. Hamacher
中科院分区：
文献类型：
--
作者：
Mayur Punekar;F. Kienle;N. Wehn;A. Tanatmis;Stefan Ruzika;H. Hamacher
近年来，几位作者使用整数编程（IP）公式来建模最大可能性（ML）解码问题。可以修改ML解码问题的IP公式，以计算代码的最小距离。基于IP的MD计算方法可有效地用于小块长度代码。但是，尚不清楚这种方法是否对实践中使用的中度和长度代码有用。在本文中，我们通过将基于IP的方法应用于实际相关代码来证明基于IP的方法对MD计算的有用性。我们计算3GPP LTE涡轮代码，WIMAX Duo-Binary Turbo代码以及WiMax＆WiFi低密度奇偶校验检查代码的MD上的真实MD或上限。还引入了一种新的IP公式来计算刺穿的涡轮代码的MD。除了MD计算外，相同的IP公式用于查找多重的低重量密码字。我们的结果证明，基于IP的方法可以相当快地估算实际相关代码的MD，还可以提供有关给定锤子重量的多种码字的信息。同样，基于IP的MD计算方法与所使用的代码无关，并且可以轻松适应刺穿方案。
In recent years several authors have used Integer Programming (IP) formulations to model the Maximum Likelihood (ML) decoding problem. IP formulation of the ML decoding problem can be modified to calculate the minimum distance of the code also. The IP based approach for MD calculation can be effectively used for small block length codes. However, it is not known if this approach is useful for the moderate and long length codes used in practice. In this paper we demonstrate the usefulness of the IP based approach for the MD calculation by applying it to practically relevant codes. We calculate either the true MD or upper bounds on the MD for 3GPP LTE turbo codes, WiMax duo-binary turbo codes and WiMax & WiFi low density parity-check codes. A new IP formulation is also introduced to calculate the MD of punctured turbo codes. Along with MD calculation, the same IP formulation is used to find multiplicity of low weight codewords. Our results prove that, the IP based approach can estimate the MD of practically relevant codes fairly quickly and can also provide information about the multiplicity of codewords with a given Hamming weight. Also, the IP based method for the MD calculation is independent of the code used and can easily accommodate puncturing schemes.