Noisy Chinese remaindering in the Lee norm (Q1827579)

The authors address the decoding problem for Chinese remainder codes using the Lee metric. In a Chinese remainder code the codewords for integer messages \(a\in Z\bmod K\) are given by their residues modulo a number \((n)\) of primes (\(n\) is the code length). So the codeword for \(a\) has coordinates \(a\bmod p_i\). Allowing nonzero noise per component \((e_i)\) where for each coordinate the noise is Lee-bounded \((| e_i- kp_i|< h)\), where \(h\) is the bound and \(k\) is an integer, the authors show that the set of integers at Lee-distance less than \(h\) from \(y= a+ e\) is contained in a relatively small interval \([a-h,a+h]\), except for a number of exceptional choices for the primes (the hard cases), relying on the interval \([0,K]\) and the bound \(h\). They then give a polynomial time algorithm that finds an interval \([\alpha^*, \beta^*]\) consisting of solutions (i.e. integers at Lee-distance less than \(h\) from \(y\)). Of course those solutions are exactly the candidates for \(a\). The algorithm for finding the interval is based on the CVP-algorithm for lattices developed by \textit{R. Kannan} in [Algorithmic geometry of numbers, Ann. Rev. Comput. Sci. 2, 231--267 (1987)].