According to an embodiment, an error correction device includes first calculators, second calculators, estimators, and an inverter. Each first calculator calculates a first message representing a probability that 1-bit data that is input in a corresponding variable node is 1. Each second calculator calculates a second message representing a probability that a value of the data input to the variable node is 1 for each of two or more variable nodes connected to the check node by using the first messages of the variable nodes connected to the check node. Each estimator estimates a true value of the data input to the variable node to generate an estimated value by using the first and second messages. The inverter inverts the estimated value associated with at least one of the variable nodes with a probability higher than 0 and lower than 1.