Abstract: The study of the capacity of CPM systems was concerned with. The definition as well as the Finite-State-Machine (FSM) model of CPM was introduced. The development of calculating the capacity of CPM over AWGN channels was first reviewed. Then this methodology was generalized to deal with Rayleigh fading channels. The Monte-Carlo based algorithms were derived to calculate the capacity of CPM over Rayleigh fading channels with and without knowing channel-state-information(CSI). The proposed algorithms were justified by some numerical results of some typical CPM schemes.