Phase error of a time-to-digital converter (TDC) within an all-digital phase-locked loop (ADPLL) is compensated by predicting possible phase error, which are predicted according to an estimated quantization error, a period of a digital-controlled oscillator (DCO), a gain of the TDC or a combination thereof. By appropriate inductions, the possible phase error may be further indicated by the quantization error, a code variance corresponding to a half of a reference period received by a TDC module having the TDC, a dividing ratio of a frequency divider of the ADPLL, a fractional number related to the quantization error or a combination thereof. A digital phase error cancellation module is also used for generating the possible phase error for compensating the phase error of the TDC.