Data complexity analysis should play an important role in software engineering. Unfortunately it has been relatively ignored in the past. In this paper, we develop an innovative theoretic model called information coding based data complexity (ICDC) for measuring data complexity. We define first the concept of information describing program data, and derive general formulas for information in various data structures. In order to avoid conflit with software practice, we advocate then two basic laws of data processing. These two laws refer to the information correlation and repetition removing principles which, we believe, reflect human information processing mechanism. The complexity of data is defined as the measurement of the coded information by eliminating correlated and repetitive parts. A formal description of data is advanced, from which the correlated information can be calculated. Properties of data based on ICDC model are also presented which coincide well with software empirical knowledge.