Take $B$ to be a "parity-check matrix", i.e. an $n \times (n-m)$ matrix with $BA=0$ which exists by linear algebra as long as $n > m$ (but maybe your $m$'s and $n$'s are mixed up, the input should be from a lower dimensional space then the code vector). So, putting $g(x) = Bx$ will have the property that $g(Af+\epsilon)=g(\epsilon)$ but $g$ takes values in $\mathbb{R}^{n-m}$. Now, syndrome decoding requires you to have, for each syndrome $s \in \mathbb{R}^{n-m}$ a choice of $v_s \in \mathbb{R}^n, Bv_s=s$ usually by minimizing the norm of $v_s$ among all choices. In your situation, $y-v_{g(\epsilon)}$ will be a codeword which, hopefully is $f$.

These things are not usually done in $\mathbb{R}^n$ because there is no good way to choose the $v_s$. If you work over a finite field, then it is possible for all $s$ to choose $v_s$ minimizing the Hamming norm and so maximizing the changes of correct decoding (assuming few errors in the Hamming norm). Now making this list of the $v_s$ for all $s$ is not efficient in the sense of complexity theory as there might be a lot of $s$'s. But, if you can afford the time to do it once and for all, then using the syndromes is an efficient way of decoding.

`$\mathbb{R}^m$`

. Where did you want the range of $g$ to be? – Harald Hanche-Olsen Feb 9 '10 at 13:34