Statistical Property and Subclass Structure of Sequence Triple Code Space for Repeated Placements

Sequence triple code scheme was proposed for representing a "repeated placement" which arose from a layout of regular array structure, such as an array of homogeneous sub-circuits, FPGA, multiprocessor on a chip, etc. Each code consists of three permutations of module names, and represents left-right relation and below-above relation between modules. First in this paper, a probability imbalance between left-right relation and below-above relation in the sequence triple solution space is proven mathematically, and its relevance to a tall placement as a result of SA based placement optimization is discussed. Secondary, a subclass structure of the sequence triple solution space is proposed, which provides us a variety of solution sub-spaces having different sizes and different degrees of the probability imbalance between left-right relation and below-above relation.