DocumentCode :
1178988
Title :
A Coding Algorithm for Constant Weight Vectors: A Geometric Approach Based on Dissections
Author :
Tian, Chao ; Vaishampayan, Vinay A. ; Sloane, N. J A
Author_Institution :
AT&T Shannon Lab., Florham Park, NJ
Volume :
55
Issue :
3
fYear :
2009
fDate :
3/1/2009 12:00:00 AM
Firstpage :
1051
Lastpage :
1060
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.
Keywords :
binary codes; computational complexity; decoding; geometric codes; vectors; Euclidean space; binary vectors; computational complexity; decoder mapping; decoding constant weight vectors; encoder mapping; encoding constant weight vectors; geometric interpretation; hyper-rectangle space; inductive dissection algorithm; polytope space; Algorithm design and analysis; Chaos; Circuit faults; Circuit synthesis; Computer networks; Decoding; Encoding; Hamming weight; Optical computing; Test pattern generators; Constant weight codes; Dehn invariant; bijections; dissections; encoding algorithms; mappings; polyhedral dissections;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/TIT.2008.2011441
Filename :
4787615
Link To Document :
بازگشت