In one embodiment of a header-compression method, a 32-bit timestamp value is divided by a 16- or 8-bit stride value using a plurality of 16/8-bit division operations, each performed using a corresponding hardware instruction issued to an arithmetic logic unit (ALU) of the corresponding communication device, such as an access terminal or a base station of a communication system. When specialized 32/16-bit and/or 32/8-bit division-logic circuitry is not available in the ALU, embodiments of the header-compression method can advantageously be used to improve the speed and efficiency of timestamp compression in communication devices.