An error correction encoding device 1 includes a sparse matrix computing unit 2 that computes exclusive OR of a submatrix, in a parity-check matrix, corresponding to an information bit sequence, and the information bit sequence on the basis of the position of 1 in the submatrix to calculate a vector, a fundamental matrix operator 3 that calculates a predetermined matrix by performing a predetermined fundamental matrix operation on a submatrix, in the parity-check matrix, corresponding to a parity bit sequence, and a matrix multiplier 4 that calculates the parity bit sequence by multiplying the predetermined matrix which the fundamental matrix operator 3 calculates, and the vector which the sparse matrix computing unit 2 calculates.