An encoding device and a decoding device use linear and nonlinear codes for encoding and decoding system data for a storage device. The encoding device includes a linear encoder for encoding first data to generate encoded data and a nonlinear transformer for transforming the encoded data with second data to generate output data. The first data includes data on a physical address corresponding to a logical address. The second data includes the logical address and a timestamp value indicating a version of map data mapping between the logical address and the physical address.