Noiseless encoding strategies based on conditional entropy encoding are proposed for 8-bit μ-law PCM speech, with μ = 255. Specifically, we formulate the conditional probabilities of the current and previous PCM samples to generate the codebook employed in the noiseless encoding process. In addition, we consider a second-order conditional entropy encoding scheme which, when coupled with a state-reduction technique, reduces the size of the codebook. The entries in the codebooks are established with the aid of a training speech sequence, and different sentences are used to test the noiseless encoding performance. For first- and second-order conditional entropy encoding we obtain average transmission rates of 50kbit/s and 40kbit/s, respectively, compared to the original bit rate of 64 kbit/s. These reductions in bit rate are achieved without affecting the recovered speech quality.