A multi-antenna transmitter includes an adaptive bit interleaver for orthogonal frequency division multiplexed (OFDM) communications. The adaptive bit interleaver permutes a variable number of coded bits per OFDM symbol (Ncbps). The variable number of coded bits is calculated based on individual subcarrier modulation assignments for orthogonal subcarriers. The interleaver matrix size may be based on the variable number of coded bits per OFDM symbol and the number of subchannels. The interleaver may add padding bits to the interleaver matrix to fill any remaining positions, and after performing an interleaving operation, the interleaver may prune the padding bits to provide a sequence of interleaved bits for subsequent modulation on the orthogonal subcarriers and transmission by more than one antenna. The transmitter may transmit the OFDM symbol in accordance with an IEEE 802.16 standard.