This paper proposes a heuristic procedure for the design of instruction decoder PLAs for microprogrammed controllers, which can be considered as an output encoding problem where the input and output of the PLA are a set of macroinstructions and a set of starting addresses for the corresponding microcode sequences, respectively. Unlike conventional output encoding problems, the encoding space is severely constrained. An exhaustive search of the encoding space accompanied by a two-level logic minimization procedure takes a prohibitively long computation time. In this paper, we present a simplified model and a practical solution based on a simulated annealing framework, where a fast and relatively accurate cost approximation method is crucial for obtaining a good solution in reasonable CPU time. We introduce a cost estimation method that is more than 100 times faster and more accurate than ESPRESSO-II with 'fast' option. Experimental results show that the proposed method produces on average, a 20-40% reduction in the number of product terms in the decoder PLA compared to those of random encoding for various sizes of example PLAs.