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.
No comments:
Post a Comment