# cs_decoding.run
## compressed-sensing based decoding
## application in LP book by Matousek and Gaertner

option randseed 0;
param eps default 1e-6;

## original message to be sent
include "jll/dat/ciao_bella.dat";

## encoding matrix Q and encoded vector z
param n integer, > 0, default 2*k;
set N := 1..n;
param Q{N,K} default Uniform(-1,1);
param z{j in N} default sum{i in K} Q[j,i]*w[i];

## transmit (=tamper with) z
param e default 0.1;
param xerr{j in N} default if (Uniform01() < e) then Uniform(-1,1) else 0;
param zbar{j in N} default z[j] + xerr[j];



#*** CODE HERE ******************************************




#compute error-free solution in
param y{j in N};
#using Q
#hint : formulate and solve the problem of finding A orthogonal to Q




#*** END CODE HERE **************************************


# verify it
param count integer, default 0;
for {j in N : abs(z[j] - y[j]) > eps} {
  let count := count + 1;
}
printf "[CS] sent/received: %d different components over %d\n", count, n;
param yzerr := sum{j in N} abs(z[j] - y[j]);
printf "[CS] sent/received ell-1 error = %g\n", yzerr;
printf "[CS] sent/rec mean ell-1 error = %g\n", yzerr / n;



#*** CODE HERE ******************************************





# recover original message in 
param wrec{K};
#using Q and error free solution y




#*** END CODE HERE **************************************


# display results
printf "[CS] w_org = ";
for {i in K} {
   printf "%d", w[i];
}
printf "\n";
printf "[CS] w_rec = ";
for {i in K} {
   printf "%d", wrec[i];
}
printf "\n";
param werr >= 0;
let werr := sum{i in K} abs(w[i] - wrec[i]);
printf "[CS] ||w_org - w_rec||_1 = %g\n", werr;

include "jll/bin2str.run";