On error correction with errors in both the channel and syndrome

We address the problem of error correction by linear block codes under the assumption that the syndrome of a received vector is found with errors. We propose a construction of parity-check matrices which allow to solve the syndrome equation even with an erroneous syndrome, in particular, parity-check matrices with minimum redundancy, which are analogs of Reed-Solomon codes for this problem. We also establish analogs of classical coding theory bounds, namely the Hamming, Singleton, and Gilbert–Varshamov bounds. We show that the new problem can be considered as a generalization of the well-known Ulam's problem on searching with a lie and as a discrete analog of the compressed sensing problem.