This article proposes a deadzone-free clock and data recovery (CDR) without an external reference clock. To extract a frequency difference, the proposed referenceless CDR adopts a stochastic frequency detector, which utilizes consecutive data and edge samples. Although the probability-based frequency detection (FD) technique is promising, a deadzone should be carefully considered to prevent false locking. Therefore, by analyzing the stochastic FD thoroughly, this work proposes an autocovariance-based stochastic FD (ASFD) to resolve the deadzone issue and provide a more robust CDR operation. Since the autocovariance function is easily implemented in the digital domain, the proposed digital CDR with the ASFD improves the frequency tracking ability with minimal hardware overhead. Fabricated in 40-nm CMOS technology, the prototype CDR occupies an active area of 0.032mm2. The CDR achieves a seamless frequency locking with a capture range from 14 to 32 Gb/s and frequency acquisition time within s. At 32 Gb/s, the CDR achieves a bit error rate (BER) of less than and an energy efficiency of 1.15 pJ/b at a supply voltage of 1.0 V.