The voice storage device of the invention includes a storage means that stores a voice signal, and a voice compression means that compresses the voice signal requiring a re-coding compression, of the voice signal stored in the storage means, in accordance with a compression degree and a significance of the voice signal. The voice coding device includes: an LSP quantizer that quantizes LSP parameters, an LSP multi-stage quantizer that quantizes quantization error components that the LSP quantizer is impossible to express, a pitch component coder that attains pitch components from linear predictive errors, an excitation source coder in which an excitation source is configured with a multi-stage code book, an essential code output unit that outputs a code essential to decoding from the output of the LSP quantizer, the pitch component coder, and the excitation source coder, and a sound quality improving code output unit that outputs a code to improve a decoded sound quality from the output of the LSP multi-stage quantizer and the excitation source coder.