A storage device includes a first nonvolatile memory chip; a second nonvolatile memory chip; and a controller. The controller may include a processor configured to execute a flash translation layer (FTL) loaded onto an on-chip memory; an ECC engine configured to generate first parity bits for data and to selectively generate second parity bits for the data, under control of the processor; and a nonvolatile memory interface circuit configured to transmit the data and the first parity bits to the first nonvolatile memory chip, and to selectively transmit the second parity bits selectively generated to the second nonvolatile memory chip.