Let $c_1,...,c_n,c':\mathbb{Z^d}\rightarrow \{0,1\}$ all have finite support. Let $C$ be the linear, shift-invariant code generated by $c_1,..,c_n$.

It is possible to calculate the nearest codeword $c\in C$ to $c'$ (measured in Hamming distance)? Equivalently, is it decidable to tell given $k$ if $C\cap B(c',k)=\varnothing$? (the equivalence of the two versions is a nice exercise).

For $k=0$ this is just asking if $c'\in C$, essentially an ideal membership problem, decidable with Gröbner bases. $d=1$ is easy. Already for $d=2,k=1$ I'm stumped.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.