A modem (12) including a least-significant bit convolutional coding scheme is disclosed. In the transmit side of the modem (12), an encoder (28) is included, within which convolutional coders (35I, 35Q) are used to each encode one bit of each symbol applied to a phase and amplitude modulation constellation, preferably the least significant bits, such that the encoded bits select one of a plurality of sub-constellations in the modulated signal. Each of the coders (35, 35′) are arranged as finite state machines, of either thirty-two or sixty-four states. The minimum Hamming distance (dfree) provided by the codes is four, such that the resulting coding gain of the modem is improved over conventional encoding schemes.