According to one embodiment, a decoding device decodes a (k+m) bit codeword in accordance with a check matrix. The codeword includes k-bit information symbols and an m-bit parity check code. The check matrix includes a unit matrix and a coefficient matrix. The most significant bit of each of a second vector to a last vector in the coefficient matrix is 1. Binary codes with values 1 to k−1 are sequentially arranged from the second vector to the last vector in a matrix which is obtained by excluding the most significant bits of the second to the last vectors from the matrix including the second to the last vectors. A first vector of the coefficient matrix disagrees with the other vectors in the check matrix, and the first vector is composed of a specified bit pattern having a most significant bit of 0.