In communications, error correction refers to mechanisms that can detect and correct errors in the data that appear duet to distortion in the transmission channel. Standard approaches for error correction rely on repetition schemes, redundancy checks, or nearest neighbor code search. We consider the particular case in which a signal xx with MM entries is coded by taking length-NN linearly independent codewords {φ1,....φM}{φ1,....φM}, with N>MN>M and summing them using the entries of xx as coefficients. The received message is a length-NN code y=∑m=1Mφixi=Φfy=∑m=1Mφixi=Φf, where ΦΦ is a matrix that has the different codewords for columns. We assume that the transmission channel corrupts the entries of yy in an additive way, so that the received data is y=Φx+ey=Φx+e, where ee is an error vector.
The techniques developed for sparse recovery in the context of compressive sensing (CS) provide a number of methods to estimate the error vector ee — therefore making it possible to correct it and obtain the signal xx — when ee is sufficiently sparse [1]. To estimate the error, we build a matrix ΘΘ that is a basis for the orthogonal subspace to the span of the matrix ΦΦ, i.e., an (N-M)×N(N-M)×N matrix ΘΘ that holds ΘΦ=0ΘΦ=0. When such a matrix is obtained, we can modify the measurements by multiplying them with the matrix to obtain y˜=Θy=ΘΦx+Θe=Θey˜=Θy=ΘΦx+Θe=Θe. If the matrix ΘΘ is well-suited for CS (i.e., it satisfies a condition such as the restricted isometry property) and ee is sufficiently sparse, then the error vector ee can be estimated accurately using CS. Once the estimate e^e^ is obtained, the error-free measurements can be estimated as y^=y-e^y^=y-e^, and the signal can be recovered as x^=Φ†y^=Φ†y-Φ†e^x^=Φ†y^=Φ†y-Φ†e^. As an example, when the codewords φmφm have random independent and identically distributed sub-Gaussian entries, then a KK-sparse error can be corrected if M<N-CKlogN/KM<N-CKlogN/K for a fixed constant CC (see "Matrices that satisfy the RIP").
-
Candès, E. and Rudelson, M. and Tao, T. and Vershynin, R. (2005, Oct.). Error correction via linear programming. In Proc. IEEE Symp. Found. Comp. Science (FOCS). Pittsburg, PA
