In this paper, we consider the area-minimal implementation of the instruction decoder for microprogrammed processors such as modern CISC-type microprocessor. We formulate it as a constrained output encoding problem and, based on simulated annealing algorithm, propose efficient heuristic solution methods both for PLA and multi-level implementation of the decoder. Experimental results on various examples show that our methods produce, on the average, 10~40% reduction of the number of product terms for the PLA implementations and 9.8~34.4% reduction of the number of literal for the multi-level implementations compared to the results of random encoding method.