A data storage format for encoding a bit stream on or in a surface. The format includes at least one data portion which encodes a data sequence including the bit stream followed by corresponding redundancy data. The data sequence is formed from interleaved codewords, each of which encodes at least part of the bit stream and redundancy data associated with the respective bit stream part. This allows errors in the data to be corrected by writing corrected data to the store, whilst the bit stream is maintained contiguously.