Title :
LP decodable permutation codes based on linearly constrained permutation matrices
Author :
Wadayama, Tadashi ; Hagiwara, Manabu
Author_Institution :
Dept. of Comput. Sci., Nagoya Inst. of Technol., Nagoya, Japan
fDate :
July 31 2011-Aug. 5 2011
Abstract :
A set of linearly constrained permutation matrices are proposed for constructing a class of permutation codes. Making use of linear constraints imposed on the permutation matrices, we can formulate a minimum Euclidian distance decoding problem for the proposed class of permutation codes as a linear programming (LP) problem. The main feature of this novel class of permutation codes, called LP decodable permutation codes, is this LP decodability. It is demonstrated that the LP decoding performance of the proposed class of permutation codes is characterized by the vertices of the code polytope of the code. In addition, based on a probabilistic method, several theoretical results for randomly constrained permutation codes are derived.
Keywords :
decoding; linear programming; matrix algebra; probability; random codes; LP decodable permutation codes; code polytope; linear programming problem; linearly constrained permutation matrices; minimum Euclidian distance decoding problem; probabilistic method; randomly constrained permutation codes; AWGN channels; Error probability; Linear matrix inequalities; Maximum likelihood decoding; Modulation; Upper bound;
Conference_Titel :
Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on
Conference_Location :
St. Petersburg
Print_ISBN :
978-1-4577-0596-0
Electronic_ISBN :
2157-8095
DOI :
10.1109/ISIT.2011.6033769