The increasing rate of transient faults necessitates the use of on-chip fault-tolerant techniques in embedded microprocessors. Performance overhead is a challenging problem in on-chip fault-tolerant techniques used in the random logic of the embedded microprocessors. This paper presents a signature-based error detection and roll-back recovery technique for the control logic with much lower performance overhead as compared to many previous techniques. The low performance overhead is achieved by eliminating the fault masking overhead cycles in the previous techniques. The performance overhead is analytically studied, and the analytical results recommend at which fault rate the use of the technique is preferred. To measure the cycle time of the pipeline critical path and area overhead, this technique has been implemented and synthesized using a behavioral VHDL model of the Leon2 processor. The synthesis results show that the area and the cycle time overhads of the technique are only 17.7% and 3.4%, respectively. In addition, the injection of about 74000 transient single bit-flip faults into the control logic part of the Leon2 processor shows that the technique detected about 99% of the injected faults.