A Coding Algorithm for Constant Weight Vectors: A Geometric Approach Based on Dissections Academic Article

abstract

• We present a novel technique for encoding and decoding constant weight binary vectors that uses a geometric interpretation of the codebook. Our technique is based on embedding the codebook in a Euclidean space of dimension equal to the weight of the code. The encoder and decoder mappings are then interpreted as a bijection between a certain hyper-rectangle and a polytope in this Euclidean space. An inductive dissection algorithm is developed for constructing such a bijection. We prove that the algorithm is correct and then analyze its complexity. The complexity depends on the weight of the vector, rather than on the block length as in other algorithms. This approach is advantageous when the weight is smaller than the square root of the block length. 2009 IEEE.

authors

• Tian, Chao

published proceedings

• IEEE TRANSACTIONS ON INFORMATION THEORY

author list (cited authors)

• Tian, C., Vaishampayan, V. A., & Sloane, N.

citation count

• 13

complete list of authors

• Tian, Chao||Vaishampayan, Vinay A||Sloane, NJA

publication date

• March 2009

publisher

• Institute of Electrical and Electronics Engineers (IEEE)  Publisher

published in

• IEEE TRANSACTIONS ON INFORMATION THEORY  Journal

keywords

• Bijections
• Constant Weight Codes
• Dehn Invariant
• Dissections
• Encoding Algorithms
• Mappings
• Polyhedral Dissections

Digital Object Identifier (DOI)

• 10.1109/TIT.2008.2011441

start page

• 1051

end page

• 1060

volume

• 55

issue

• 3

URL

• http://dx.doi.org/10.1109/tit.2008.2011441