This paper offers a review of recent developments in non-deterministic error correction decoding methods, which can be described in two broad classes. The first class uses stochastic computation to emulate the arithmetic operations of conventional decoding algorithms. The second class achieves noise enhancement by randomly perturbing the calculations of a standard decoder. Stochastic decoders inherit analysis techniques from the conventional algorithms they emulate, but the noise-enhanced algorithms are newer, more difficult to explain, and not yet fully understood. We describe a Markov chain analysis technique to both explain and optimize noise enhancement in these algorithms. Circuit implementation is also discussed, including both conventional hardware architectures and circuits based on memristor threshold logic, where memristor non-determinism can be exploited for noise enhancement.