This paper presents an improved decoding algorithm of non-binary LDPC codes based on the Expanded Min-Sum algorithm, analyzes the complexity of the algorithm in decoding efficiency. According to the fact that the reliability of variable note is increased with the increase of the iterative number, the reliability of the variable notes is estimated by the maximum post probability of variable notes and illegal parity-check values. By the estimation rule, the iterative calculations or some variable notes are stopped, the number of calculation for updating variable and parity-check notes is reduced, thus the decoding complexity is decreased and the decoding efficiency is improved. A simulation is made using regular non-binary LDPC codes under White Gaussian Noise channel based on GF(4), the result shows that the performance decreases by about 0.05 dB when BER(Bit Error Rate) is ,but the decoding complexity is reduced and the decoding efficiency is improved significantly.