A clock and data recovery circuit in accordance with an embodiment of the inventive concept includes a phase locked loop configured to receive a data stream into which an additional bit is inserted at every reference period to generate parallelized data and a clock signal, and a first detector circuit configured to determine whether the parallelized data is locked based on a bit-conversion of the data stream according to an insertion of the additional bit. The bit-conversion is executed with respect to the additional bits according to a predetermined protocol, or is executed with respect to at least one bit from among data of the data stream between a current one of the additional bits and a next one of the additional bits.