With regards to energy constrained Autonomous Underwater Vehicles (AUVs), and difficulties inherent to the acoustic underwater communication channel, a non-coherent method is investigated in order to improve energy consumption and reliability over traditional Frequency Shift Keying (FSK), without increasing the bandwidth. A proposed method of adapting Trellis Coded Modulation (TCM) to constant amplitude Permutated Frequency Shift Keying (PFSK) symbol constellations is evaluated. A system implementation of two PFSK methods is simulated in an Additive White Gaussian Noise channel, and field tested in an underwater channel in the Stockholm archipelago, where a binary FSK reference method is used as a comparison. The main interest is comparing electrical bit energy and bit error rate (BER) for the methods. Time variability of frequency fading, related to wind speed, is also evaluated from the field tests.