Two Decoding Algorithms for Linear Codes

We propose an algorithm to compute the nearest codeword in a BSC. For a linear code of length $n$ and rate $R$, the algorithm executes in time of order $2^{n(1-R)/2}$. For codes with distance $d$ increasing linearly with length, we propose an algorithm capable of correcting $[(d-1)/2]$+const errors which involves a linearly increasing number of attempts to correct $[(d-1)/2]$ errors.