A trellis coded 4-ary Pulse Amplitude Modulation (4-PAM) is presented, where the encoding algorithm is derived from Distance Preserving Mapping (DPM) algorithm. In this work, we modify the DPM algorithm for 4-PAM and obtain a new construction for mapping binary sequences to permutation sequences, where the permutation sequences are obtained by permuting symbols of a 4-PAM constellation. The resulting codebook of permutation sequences formed this way are termed mappings. We also present several metrics for assessing the performance of the mappings from our construction, and we show that a metric called the Sum of Product of Distances (SOPD) is the best metric to use when judging the performance of the mappings. Finally, performance results are presented, where the mappings from our construction are compared against each other and also against the conventional mappings in the literature.