A semiconductor memory device and method of operating same are described. The semiconductor memory device includes a first anti-fuse array having a plurality of first anti-fuse elements that store first fuse data, a second anti-fuse array having a plurality of second anti-fuse elements that store error correction code (ECC) data associated with the first fuse data, and an ECC decoder configured to generate second fuse data by correcting the first fuse data using the ECC data.