To store N bits of M≧2 logical pages, the bits are interleaved and the interleaved bits are programmed to [N/M] memory cells, M bits per cell. Preferably, the interleaving puts the same number of bits from each logical page into each bit-page of the [N/M] cells. When the bits are read from the cells, the bits are de-interleaved. The interleaving may be deterministic or random, and may be effected by software or by dedicated hardware.