Question: Optimization over Binary Polynomials

Assume that x[i] with 1≤i≤n are binary numbers. Let I_[k] be a subset with k elements of the set {1,2,⋯,n}.

Now Consider the following binary linear functions

It is clear that to obtain f[j]'s we need to compute ∑k[j] XOR bitwise operator. But it is possible to get f[j]'s with less than ∑k[j] XOR.

Example: Let n=8 and m=7 and suppose that

It follows from (1) that we need to do 20 XOR bitwise operator to get f[j]'s with 1≤j≤7. But set

which results in  f[j]'s are computed with just 9 XOR.

It is useful to mention that the relation (1) can be represented by a 8x8 binary matrix in the form of M*X=F. 

Question: Is it possible to implement a procedure in Maple such that by applying the procedure we get  f[j]'s with the minimum number of XOR bitwise operator.

One solution for this question is the "parr algorithm" that is given in the following paper

https://ieeexplore.ieee.org/document/613165

This edition is because of @Carl Love commnet.

The paar algorithm is provided in C++ in the following link

https://github.com/rub-hgi/shorter_linear_slps_for_mds_matrices/blob/master/paar.cpp

and is defined by 

My problem is that I couldn't implement the paar algorithm in Maple.

Thanks for any help

 

 

 

Please Wait...