A method and apparatus for overwriting data in a probe-based data storage device wherein data is represented by the presence and absence of pits formed in a storage surface by a probe of the device is provided. Input data is first coded such that successive bits of a given value x in the coded input data (b0, b1, b2, . . . ,) are separated by at least d bits of the complementary value {tilde over (x)}, where d is a predetermined number≧2. Overwrite data bits (v0, v1, v2, . . . ,) are then generated by encoding the coded input data bits (b0, b1, b2, . . . ,).