New Binary Constant Weight Codes Based on Cayley Graphs of Groups and Their Decoding Methods

Jun IMAI  Yoshinao SHIRAKI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E88-A   No.10   pp.2734-2744
Publication Date: 2005/10/01
Online ISSN: 
DOI: 10.1093/ietfec/e88-a.10.2734
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
Category: Coding Theory
Cayley graphs,  permutation representations,  nonlinear binary codes of constant weights,  Buckminster Fullerene,  

Full Text: PDF>>
Buy this Article

We propose a new class of binary nonlinear codes of constant weights derived from a permutation representation of a group that is given by a combinatorial definition such as Cayley graphs of a group. These codes are constructed by the following direct interpretation method from a group: (1) take one discrete group whose elements are defined by generators and their relations, such as those in the form of Cayley graphs; and (2) embedding the group into a binary space using some of their permutation representations by providing the generators with realization of permutations of some terms. The proposed codes are endowed with some good characteristics as follows: (a) we can easily learn information about the distances of the obtained codes, and moreover, (b) we can establish a decoding method for them that can correct random errors whose distances from code words are less than half of the minimum distances achieved using only parity checking procedures.