M sequence message is a typical message of HF data link. According to the statistical properties of M sequence message, this paper puts forward a new improved arithmetic coding, i.e. a semi-fixed probability estimative model based on frame structure proposed to quantify the probability of low probability symbols, a dynamic update mechanism of encoding interval length applied to update discretely encoding interval length in real time, and the algorithm caused the coding efficiency loss up to 10.04%. The test results show that when the quantity of M sequence message is from 2 to 9 and MIAC compression coding algorithm loses its compression ratio by 20% at most, compression time of the improved algorithm is lower than the original arithmetic coding at least 50%. And this will provide a new way of thinking for the study of the performance of data link system in the future.