Defect List Compression

We consider a setting relevant to the design of storage systems in which a list of defective storage blocks, as determined at manufacture time, is stored in a high-speed system controller memory to enable the efficient bypassing of defective blocks in a transparent manner, external to the system. Conventionally, such lists have been compressed losslessly to save on the cost of the controller memory. Under the assumption of a total system cost that is a linear combination of the number of storage blocks and the controller memory size, we study the potential benefits of compressing the defect list using lossy algorithms. The only restriction is that the reconstructed defect list not label any defective storage blocks as being non-defective.