ENTROPIC BOUNDS ON FSM SWITCHING

Several state assignment algorithms have attempted to minimize the ave rage Hamming distance per transition in the hopes of generating low po wer assignments. There has not been a reasonable theoretical lower bou nd on the average Hamming distance per transition that is applicable t o every state assignment for a given finite state machine (FSM). Such a lower bound serves many roles-a target for algorithm designers, prov ides clues about what types of FSM structures are likely to have low a verage switching per transition, could be incorporated into a high-lev el power model, We provide two such lower bounds which were also found to be achievable empirically within 17% for MCNC benchmarks. An inter esting byproduct of one of these 'theoretical' lower bounds was a gree dy state assignment algorithm which is amenable to a very distributed (parallel) implementation. This algorithm also outperforms JEDI by 2.5 % for area and by 21% for power over MCNC benchmarks.