Title :
Dissections and Constant Weight Codes
Author :
Vaishampayan, V.A. ; Sloane, N. J A
Author_Institution :
Shannon Lab., AT&T Labs-Res., NJ
Abstract :
The problem of encoding and decoding binary block codes of length n and constant Hamming weight w is formulated as a polytope dissection problem. This is done by working with a w-dimensional Euclidean space representation for the information and code vectors. Novel algorithms based on two new dissections are presented. The first is a dissection of a subset of the codebook, and has time-complexity o(w). The second is a dissection of the entire codebook, and has time-complexity o(w log w). Implementation issues associated with the second algorithm are discussed in detail
Keywords :
Hamming codes; binary codes; block codes; computational complexity; decoding; codebook; constant Hamming weight; constant weight codes; decoding binary block codes; encoding; polytope dissection problem; time-complexity; w-dimensional Euclidean space; Algorithm design and analysis; Block codes; Conferences; Costs; Decoding; Encoding; Hamming weight; Information theory; Laboratories; Table lookup;
Conference_Titel :
Information Theory Workshop, 2006. ITW '06 Chengdu. IEEE
Conference_Location :
Chengdu
Print_ISBN :
1-4244-0067-8
Electronic_ISBN :
1-4244-0068-6
DOI :
10.1109/ITW2.2006.323743
