A modified delta encoding method and its applications to speech signal are proposed. In this method, Hungarian algorithm is applied to find the minimum distance of arbitrary two frames in speech signal and minimum spanning tree is used to find an effective delta encoding path. In simulation, the method is applied to the compression of sinusoidal coding. The results show that the data size after compression is 6% smaller than a usual delta encoding whose path is not suitably permutated. In addition, the proposed method has the potential to apply on data security for practical use because the delta encoding path which can be used as the security key is unordered and long enough.