In this paper, we investigate the error correction performance of Permutation Trellis Codes (PTC) combined with M-ary Frequency Shift Keying (M-FSK) modulation in Cognitive Radio Networks (CRNs). Using this modulation technique, a secondary user (SU) can improve its data rate by increasing its transmission bandwidth while operating at low power and without creating destructive interference to the primary users (PUs). Given an active PU, we first derive the bit error rate (BER) of the PTC based M-FSK system for a given SU link. For different PTCs, we compare the analytical BER with the corresponding simulation results. For the same transmitting power, bandwidth availability and transmission time, simulation results show that for a SU link, M-FSK scheme using PTC provides better protection against the interference caused by the PU than M-FSK schemes employing conventional error correction coding such as convolutional and low density parity check (LDPC) codes.