Multi-symbol non-coherent continuous phase modulation (CPM) detectors having a trellis structure, methods of continuous phase detection using a trellis structure, and trellis-based lock detectors and methods for digitally modulated signals are described. The continuous phase modulation detector includes receiver, observation, memory, and adjustment portions. The receiver has a trellis structure and is adapted for receiving digitally modulated signals having a generally continuous phase. The observation portion is adapted for performing multi-symbol observations on received digitally modulated signals and the memory is adapted for storing historic observation data corresponding to multi-symbol observations performed by the observation portion. The adjustment portion is adapted for selectively adjusting the receiver in accordance with stored historic observation data. A trellis-based lock detector computes a global survivor for consecutive time indexes as a maximum cumulative branch metric corresponding to a given time index for consecutive branches of the trellis structure.