A method of storing data on a storage device is disclosed. The method includes receiving data at a storage device containing the storage media, adding error correction code to the received data, generating additional error correction information based upon an amount of free space on the storage media, storing the data on the storage media, and storing the generated additional error correction information on the storage media. The method further includes selecting one of a plurality of methods for generating error correction information based upon the amount of free space on the storage media, and generating the error correction information based on the selected method.