The meaning of data (information) hiding is to embed the secret information into a cover host, such as an image. Usually, the naked eye of the people cannot perceive any change when the image is modified slightly. The evaluation of data hiding schemes should be measured by the distortion (or called Mean Square Error; MSE) and the embedding rate (the average number of bits embedded in a cover pixel). In this paper, we propose an improved data hiding scheme which improves the matrix encoding-based data hiding algorithm by the idea of Hamming+1 to further enhance the stego-image quality. This proposed improved scheme is verified to be correct through the theoretical analysis and the experiment.