Construction and VHDL Implementation of a Fully Local Network with Good Reconstruction Properties of the Inputs

摘要

This report shows how one can find a solution to the K-SAT equations with the use of purely local computations. Such a local network, inspired by the Survey Propagation equations driven by an external input vector, potentially has an exponential number of attractors. This gives the network powerful classification properties, and permits to reconstruct either noisy or incomplete inputs. It finds applications from bayesian inference to error-correcting codes and gene-regulatory networks, and its local structure is ideal for an implementaion on FPGA. Here we write its algorithm, characterize its main properties and simulate the corresponding VHDL code. One shows that the time of convergence towards a solution optimally scales with the size of the network.