• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Information Theory >LP-Decodable Multipermutation Codes
【24h】

LP-Decodable Multipermutation Codes

机译：LP可解码多置换码

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this paper, we introduce a new way of constructing and decoding multipermutation codes. Multipermutations are the permutations of a multiset that generally consist of duplicate entries. We first introduce a class of binary matrices called multipermutation matrices, each of which corresponds to a unique and distinct multipermutation. By enforcing a set of linear constraints on these matrices, we define a new class of codes that we term linear program (LP)-decodable multipermutation codes. In order to decode these codes using an LP, thereby enabling soft decoding, we characterize the convex hull of multipermutation matrices. This characterization allows us to relax the coding constraints to a polytope and to derive two LP decoding problems. These two problems are, respectively, formulated by relaxing the maximum likelihood decoding problem and the minimum Chebyshev distance decoding problem. Because these codes are non-linear, we also study efficient encoding and decoding algorithms. We first describe an algorithm that maps consecutive integers, one by one, to an ordered list of multipermutations. Based on this algorithm, we develop an encoding algorithm for a code proposed by Shieh and Tsai, a code that falls into our class of LP-decodable multipermutation codes. Regarding decoding algorithms, we propose an efficient distributed decoding algorithm based on the alternating direction method of multipliers. Finally, we observe from the simulation results that the soft decoding techniques we introduce can significantly outperform hard decoding techniques that are based on quantized channel outputs.
机译：在本文中，我们介绍了一种构造和解码多置换码的新方法。多重排列是通常由重复条目组成的多重集的排列。我们首先介绍一类称为多重置换矩阵的二进制矩阵，每个矩阵都对应一个唯一且独特的多重置换。通过对这些矩阵执行一组线性约束，我们定义了一类新的代码，我们称其为线性程序（LP）可分解的多置换代码。为了使用LP解码这些代码，从而实现软解码，我们表征了多置换矩阵的凸包。这种表征使我们可以放宽对多态性的编码约束，并得出两个LP解码问题。通过放松最大似然解码问题和最小切比雪夫距离解码问题来表述这两个问题。由于这些代码是非线性的，因此我们还将研究有效的编码和解码算法。我们首先描述一种算法，该算法将连续的整数一个接一个地映射到多重排列的有序列表。基于此算法，我们为Shieh和Tsai提出的代码开发了一种编码算法，该代码属于我们的LP可解码多置换代码类。关于解码算法，我们提出了一种基于乘法器交替方向方法的高效分布式解码算法。最后，我们从仿真结果中观察到，我们引入的软解码技术可以大大优于基于量化信道输出的硬解码技术。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号