Methods and apparatus are provided for encoding input data for recording in s-level storage(2)of a solid state storage device(1), where s≥2. Input data words are encoded in groups of M input data words in accordance with first and second BCH codes to produce, for each group, a set of M first codewords of the first BCH code. The set of M first codewords is produced such that at least one predetermined linear combination of the M first codewords produces a second codeword of the second BCH code, this second BCH code being a sub- code of the first BCH code. The sets of M first codewords are then recorded in the s-level storage(2).If each of the first and second codewords comprises N q-ary symbols where q =p k , k is a positive integer and p is a prime number, the q-ary code alphabet can be matched to the s-ary storage (2) by ensuring that q and s are u th and v th powers respectively of a common base r, where u and v are positive integers and k≥u, whereby p (k/u)v = s.