The increasing complexity of applications with shortening timeto- market window created a strong research interest towards highperformance and flexible processors. A huge application domain, chiefly consisting of wireless and handheld devices, strongly requires this class of processors to be power-efficient, too. Within this domain, a demanding problem is to determine the instruction encoding of the processor for achieving minimum power consumption in the instruction bus and in the instruction memory. In this paper, a framework for determining power-efficient instruction encoding is presented. We have integrated existing and novel techniques in this framework and have proposed novel heuristic approaches. The framework accepts an existing processor instruction-set and a group of applications. The output, which is an optimized instruction encoding under the constraints of a well-defined cost model, minimizes the power consumption of the instruction bus and the instruction memory. This results in strong reduction of the overall power consumption. Case studies with commercial embedded processors show the effectiveness of this framework.