According to one embodiment, a storage device performs error correction processing of a code of which the maximum correction performance is T bits, the decoding device including an error correction processor for performing error correction processing using calculating devices capable of handling errors of J bits (J is an integer equal to or more than one and less than T), wherein an initial value of an error number expectation value is set to I (I is an integer equal to or more than one and less than T), and execution of increment of the error number expectation value and execution of the error correction processing is repeated until no error is detected or the error number expectation value becomes T bits.