A storage device includes a plurality of first memories, a controller, and a second memory. The controller controls the first memories such that first and second data chunks associated with target data are distributively stored in the plurality of first memories. The controller generates a first intermediate parity using the first data chunk, which is processed immediately before the second data chunk. When the second data chunk is not a data chunk which is processed last in connection with the target data and the first intermediate parity is buffered in the second memory, the controller generates a second intermediate parity using the first intermediate parity buffered in the second memory and the second data chunk, and outputs the second intermediate parity to the second memory to be buffered.