Synthesizing combinational logic to generate probabilities: Theories and algorithms

As CMOS devices are scaled down into the nanometer regime, concerns about reliability are mounting. Instead of viewing nano-scale characteristics as an impediment, technologies such as PCMOS exploit them as a source of randomness. The technology generates random numbers that are used in probabilistic algorithms. With the PCMOS approach, different voltage levels are used to generate different probability values. If many different probability values are required, this approach becomes prohibitively expensive. In this chapter, we demonstrate a novel technique for synthesizing logic that generates new probabilities from a given set of probabilities. We focus on synthesizing combinational logic to generate arbitrary decimal probabilities from a given set of input probabilities. We demonstrate how to generate arbitrary decimal probabilities from small sets-a single probability or a pair of probabilities-through combinational logic.