LP-decodable multipermutation codes

Author

Xishuo Liu ; Draper, Stark C.

Author_Institution

Dept. of Electr. & Comput. Eng., Univ. of Wisconsin-Madison, Madison, WI, USA

fYear

2014

fDate

Sept. 30 2014-Oct. 3 2014

Firstpage

828

Lastpage

835

Abstract

In this paper, we introduce a new way of constructing and decoding multipermutation codes. Multipermutations are permutations of a multiset that may consist of duplicate entries. We first introduce a new class of matrices called multipermutation matrices. We characterize the convex hull of multipermutation matrices. Based on this characterization, we propose a new class of codes that we term LP-decodable multipermutation codes. Then, we derive two LP decoding algorithms. We first formulate an LP decoding problem for memoryless channels. We then derive an LP algorithm that minimizes the Chebyshev distance. Finally, we show a numerical example of our algorithm.

Keywords

convex programming; decoding; linear codes; linear programming; matrix algebra; Chebyshev distance minimization; LP decoding problem; LP-decodable multipermutation code; duplicate entry; linear programming; memoryless channel; multipermutation matrix convex hull; multiset permutation; Ash; Decoding; Hamming distance; Linear matrix inequalities; Optimization; Symmetric matrices; Vectors;

fLanguage

English

Publisher

ieee

Conference_Titel

Communication, Control, and Computing (Allerton), 2014 52nd Annual Allerton Conference on

Conference_Location

Monticello, IL

Type

conf

DOI

10.1109/ALLERTON.2014.7028540

Filename

7028540