There has been much recent progress in improving the reliability of digital communication over a fading channel by means of the trellis-coding technique, whereby a M-ary channel signal constellation is used in conjunction with trellis codes. The coding gain is achieved by constructing a code in the expanded signal set. Some improvement in the sense of the coding gain can be obtained by searching for optimal codes according to some additive metric, which takes into account the combined weight of the Euclidean distance and the diversity of the code. The disadvantage of this approach is that the order of diversity remains equal to the minimum number of distinct symbols between two codewords. In this paper, an alternative approach is described, which increases the diversity. This approach, based on a convolutional code followed by log(M) bit interleavers, yields a better coding gain over a Rayleigh channel than its original counterpart. Here, the discussion will be restricted to a rate 2/3 coded system with 8-PSK modulation.