Title :
Genetic search for Golomb arrays
Author :
Robinson, John P.
Author_Institution :
Dept. of Electr. & Comput. Eng., Iowa Univ., Iowa City, IA, USA
fDate :
5/1/2000 12:00:00 AM
Abstract :
Genetic search with a decision level chromosome is used to search efficiently for Golomb (1982) arrays. A Golomb array A is a binary array with three values for its discrete autocorrelation function; M, the number of ones in A for no offset, 1 when there is partial overlap, and 0 otherwise. In one dimension, A is known as a Golomb ruler. The method yields improvement because the genetic search considers only feasible solutions in the most likely portion of the search space. Each chromosome bit represents a decision to place a one in an iterative construction. The representation includes all possible arrays. Since the chromosome bits represent binary decisions in the search space, genetic operations (such as crossover and mutation) always result in feasible descendent chromosomes. Experimental results include comparison to previously known search methods and several new arrays. These results indicate that the proposed search is significantly more efficient than prior methods
Keywords :
arrays; binary codes; binary decision diagrams; genetics; search problems; Golomb arrays; Golomb ruler; binary array; binary codes; binary decisions; chromosome bit; crossover; decision level chromosome; descendent chromosomes; discrete autocorrelation function; experimental results; genetic operations; genetic search; hypergraphs; iterative construction; mutation; search space; Ash; Conferences; Constellation diagram; Convergence; Digital modulation; Entropy; Genetic communication; Information theory; Maximum likelihood estimation; Upper bound;
Journal_Title :
Information Theory, IEEE Transactions on