A clock data recovery circuit includes a phase detector circuit, a majority voter circuit, and a phase shift circuit. The phase detector circuit is operable to compare a phase of a periodic signal to a phase of a data signal to generate a phase error signal. The majority voter circuit includes a shift register circuit. The shift register circuit is operable to generate an output signal based on the phase error signal. The majority voter circuit is operable to generate a majority vote of the phase error signal based on the output signal of the shift register circuit. The phase shift circuit is operable to set the phase of the periodic signal based on the majority vote generated by the majority voter circuit.