counterfeit_detection

counterfeit_detection a MATLAB code which considers problems in which one or more counterfeit coins are to be identified by the fact that they do not have the standard weight.

Methods include:

• brute force: weigh every coin and report those with bad weight;
• combinatorial: assume there is only 1 bad coin, and that the number of coins is 2^n-1. carry out n weighings to determine the bad coin.
• compressed sensing: weigh a certain number of random subsets of the coins and solve an underdetermined linear system minimizing the l1 norm.

Licensing:

The computer code and data files described and made available on this web page are distributed under the MIT license

Languages:

counterfeit_detection is available in a MATLAB version and a Python version.

Related Data and Programs:

counterfeit_detection_test

Reference:

1. Kurt Bryan, Tanya Leise,
   Making do with less: an introduction to compressed sensing,
   SIAM Review,
   Volume 55, Number 3, September 2013, pages 547-566.

Source Code:

• counterfeit_detection_brute.m, brute force approach to finding counterfeit coins;
• counterfeit_detection_combinatorial.m, combinatorial approach to finding a counterfeit coin;
• counterfeit_detection_compressed.m, compressed sensing approach to finding countereit coins.
• ksub_random2.m, selects a random subset of size K from a set of size N.