We present a fully implicit encoding algorithm for minimization of average power dissipation in sequential circuits, based on the reduction of the average number of bit changes per state transition.We have studied two novel schemes for this purpose, one based on recursive weighted non-bipartite matching, and one on recursive minicut bi-partitioning. We employ ADDs (Algebraic Decision Diagrams) to computate the transition probabilities, to measure the potential area saving, and in the encoding algorithms themselves.Our experiments show the effectiveness of our method in reducing power dissipation for large sequential designs.