In almost all the work owned out in the area of automatic modulation classification (AMC), the dictionary of all possible modulations that can occur is assumed to be fixed and given. In this paper, we consider the problem of discovering the unknown digital amplitude-phase modulations when the dictionary is not given. A deconvolution based framework is proposed to estimate the distribution of the transmitted symbols, which completely characterizes the underlying signal constellation. The method involves computation of the empirical characteristic function (ECF) from the received signal samples, and employing constrained least squares (CLS) filtering in the frequency domain to reveal the unknown symbol set. The decoding of the received signals can then be carried out based on the estimate of the signal constellation. The proposed method can be implemented efficiently using fast Fourier transform (FFT) algorithms. In addition, we show that the distribution estimate of the transmitted symbols can be refined if the signal constellation is known to satisfy certain symmetry and independence properties. (C) 2014 The Franklin Institute. Published by Elsevier Ltd. All rights reserved.