Brain-like communication based on spikes has potential advantages in terms of energy consumption, but it is unclear what type of encoding of information allows good robustness to errors. This paper shows how to construct Error Correcting Codes that are particularly applicable to spike-based signals. We adopt an encoding based on Inter-Spike Intervals, and show how the addition of a few “check” spikes makes the codes robust to interference with other spikes. Key in our construction is the use of finite automata that are adapted to recognize specific spike trains. Once the first few spikes are received by such spike automata, they can predict the timing of subsequent spikes, and use this prediction to test whether a spike train is a valid message or not. The proposed spike encoding may find application in wireless sensor networks, in which low energy consumption rather than high data rates is a priority.