Distances between data are encoded by performing a random projection, followed by dithering and scaling, with a fixed scaling for all values. The resulting dithered and scaled projection is quantized using a non-monotonic 1-bit quantizer to form a vector of bits representing the signal. The distance between signals can be approximately calculated from the corresponding vectors of bits by computing the hamming distance of the two vectors of bits. The computation is approximately correct up to a specific distance, determined by the scaling, and not beyond that.