An error correction circuit using a BCH code may include a decoder performing at least one of a first error correction decoding using a first error correction capability or a second error correction decoding using a second error correction capability and an encoder generating a codeword based on a message and a generation matrix corresponding to the first error correction capability and generating an additional parity based on the codeword and one or more rows of a parity check matrix corresponding to the second error correction capability, wherein a syndrome vector generated based on a read vector corresponding to the codeword is used during the first error correction decoding and an additional syndrome generated based on the additional parity is used during the second error correction decoding, and wherein the one or more rows are extended from a parity check matrix corresponding to the first error correction capability.