Compressive sensing of binary signals is corresponding to the problem of binary symbol detection in the faster-than-Nyquist signaling systems, which has significant research value. Traditional compressive measurement of a binary signal is based on Gaussian matrix, and l1 minimization is a classic algorithm for signal reconstruction. However, stochastic matrix such as the Gaussian matrix can hardly be realized by a digital circuit, and the reconstruction performance of l1 minimization is not well enough for binary signals. Thus, it is of great meaning to construct a new kind of measurement matrix as well as a better reconstruction algorithm for binary signals. This paper constructs a chaotic circulant measurement matrix based on Cat chaotic map (CCMM), and proposes a brand new algorithm for binary signal reconstructionsmooth function approximation method (SFAM). Chaotic sequence has characteristics of both internal certainty and external randomness, while a circulant matrix requires less elements and can be realized through fast Fourier transform. CCMM conbines the advantages of both chaotic sequence and circulant matrix, so that it not only satisfies the RIPless property required by the compressive measurement matrix because of external randomness, but also has the power to resist the effect of low signaling efficiency and low SNR due to the internal certainty. Moreover, the circle structure gives CCMM the potential to be digital realized in the future. In SFAM, we first use a non-convex function to approximate the original discontinuous objective function, in order to transfer the original combinatorial optimization problem into an optimization problem with equality constraints which can be solved much easier. Then we use the interior point method to solve this optimization problem. Furthermore, sparse Bayesian learning algorithm is used to correct the reconstruction error for a more accurate result. Compressive measurement and reconstruction of binary signals in additive Gaussian white noise channel are operated. Result of numerical experiments shows that CCMM is much better than the traditional Gaussian matrix for compressive measurement, especially in the condition of low signaling efficiency and low SNR, and SFAM is much better than l1 minimization for binary signal reconstruction. At the end of this paper, we explain the essential reason why CCMM performs better than the traditional Gaussian matrix, through calculating the autocorrelation function of compressive measurement vector in various conditions.