Methods and apparatus are described for improving the transmission of multimedia data over wireless communication channels. These techniques include determining a physical layer packet size of the wireless communication system and determining a maximum size of a compressed header. Then, partitioning an information unit, wherein the size of the partitions are selected such that after a partition is encoded the aggregate size of the encoded partition and the compressed header are the size of the physical layer packet, or less. The techniques can be used for various types of information units, such as multimedia data, variable bit rate data streams, video streams, video teleconference stream, or voice over IP. The techniques can also be used with various over the air interfaces, such as, Global System for Mobile Communication (GSM), General Packet Radio Service (GPRS), Enhanced Data GSM Environment (EDGE), or standards based on CDMA such as TIA/EIA-95-B (IS-95), TIA/EIA-98-C (IS-98), IS2000, HRDP, cdma2000, Wideband CDMA (WCDMA), and others.