This contribution considers the true Cramer-Rao bound (CRB) related to estimating the carrier phase of a noisy linearly modulated signal in the presence of encoded data symbols. Timing delay and frequency offset are assumed to be known. A generall expression and computational method is derived to evaluate the CRB in the presence of codes for which a trellis diagram can be drawn (block codes, trellis codes, convolutional codes,…). Results are obtained for several minimum free distance non-recursive convolutional (NRC) codes, and are compared with the CRB obtained with random (uncoded) data [1] and with the modified Cramer-Rao bound (MCRB) from [2]. We find that for small signal-to-noise ratio (SNR) the CRB is considerably smaller for coded transmission than for uncoded transmission. We show that the SNR at which the CRB is close to the MCRB decreases as the coding gain increases, and corresponds to a bit error rate (BER) of about 0.001. We also compare the new CRBs with the simulated performance of (i) the (code-independent) Viterbi & Viterbi phase estimator [3] and (ii) the recently developed turbo synchronizer [4,5].