Is there a functionally complete fixed-function logic circuit?

Thread Starter

m_moraes

Joined Jan 26, 2015
5
Hello, I know this is probably a very basic question but.. Is there a way to create a fixed-function logic circuit of n-inputs and 1-output that can represent any of the 2^(2^n) possible truth tables for n-inputs? And if not, what would be the impact of such circuit in modern computer architecture..
 

WBahn

Joined Mar 31, 2012
29,976
If you have a logic circuit in a black box that just has N inputs and one output and it implements a particular N-input logic function, then how could it also represent a different N-input logic function?
 

Thread Starter

m_moraes

Joined Jan 26, 2015
5
What if I add secondary inputs of n-bits to each of the n inputs and depending on the value of each secondary input a different logic function will be performed, i.e., a different truth table of the 2^(2^n) possible truth tables will be represented. Would that be the same as using PLDs?
 

WBahn

Joined Mar 31, 2012
29,976
What if I add secondary inputs of n-bits to each of the n inputs and depending on the value of each secondary input a different logic function will be performed, i.e., a different truth table of the 2^(2^n) possible truth tables will be represented. Would that be the same as using PLDs?
Somewhat.

If you want a circuit that can do arbitrary functions, then the easiest way is to use a memory. That requires additional inputs since you have to be able to program the memory cells, but you really only need one additional bit to put it into programming mode and then you can use the n-input signals and a suitable protocol to rewrite the memory. This is, in very rough terms, how an FPGA works. If you wanted to, you could program in multiple functions and then use additional input signals to select which one you want. But, as you can see, the number of functions grows not only exponentially, but the exponent grows exponentially. So even with n=4 you have over 65k functions and with n=6 you have 2^64 and to give you some idea of how many functions that is, if you could enumerate one billion (10^9) functions every second it would take you over 500 years to get through them all.
 

Thread Starter

m_moraes

Joined Jan 26, 2015
5
Somewhat.

If you want a circuit that can do arbitrary functions, then the easiest way is to use a memory. That requires additional inputs since you have to be able to program the memory cells, but you really only need one additional bit to put it into programming mode and then you can use the n-input signals and a suitable protocol to rewrite the memory. This is, in very rough terms, how an FPGA works. If you wanted to, you could program in multiple functions and then use additional input signals to select which one you want. But, as you can see, the number of functions grows not only exponentially, but the exponent grows exponentially. So even with n=4 you have over 65k functions and with n=6 you have 2^64 and to give you some idea of how many functions that is, if you could enumerate one billion (10^9) functions every second it would take you over 500 years to get through them all.
ok. thank you, that was very helpful.
 
Top