DBpedia – Linked Data Fragments

Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Three-input_universal_logic_gate> ?p ?o }

• Three-input_universal_logic_gate abstract "Logic gates are used to build computer chips. Reversible logic gates are of interest because they could in principle generate useful results for less heat generated. The nand gate is universal among irreversible logic gates, in the sense that it is possible to simulate any irreversible logic gate with a network of these gates. The Fredkin and Toffoli gates were the first gates to be proved universal among reversible logic gates. However, this universality is not unusual in the space of 3 input and 3 output reversible gates.A reversible logic gate of n input bits must have n output bits, by the pigeonhole principle. The reversibility requirements means that each of the 2n input combinations must have one and only one output combination - they must be a one-to-one map. Thus the outputs for the inputs are simply some permutation of the inputs, and so the number of n-input reversible gates is 2n! .For a three-input gate, this number is 8!, around 40 thousand.Let us define an equivalence relation: two gates are equivalent if the outputs of one can be gotten by rearranging the bits of the outputs of the other. That is, if we simply relabel the wires attached to the output terminals of the gate. Every gate, then, is a member of a 6-member equivalency class bringing the total number of possible gates down to 8000 or so. The three-input identity gate:is equivalent to this gate:which merely swaps outputs 0 and 1.We shall abbreviate the truth table above by treating columns as octal numbers and rows as hexadecimal numbers (a redundancy, but a useful one). The three-input identity table may be written [01234567:AA/CC/0F], and the second table above [02134657=CC/AA/0F]'. The first set of digits gives the output for each possible input, and the second set gives the truth table for each of the three outputs. The remainder of this article will use this notation.Omitting duplicates gives us around 8000 possible gates.We are interested in universality. Any one output of a three-input logic gate can have 28 possible truth tables for the 8 distinct input values. A logic gate (or set of logic gates) is universal when suitable cascades of gates can be constructed to give us any of these 256 truth tables.Surprisingly, it turns out that almost all of the 8 thousand or so 3/3 reversible gates are universal in this sense.There are 269 exceptions. One of them is the \"straight through\" gate.7 of them provide access to 8 possible truth tables. These are: [45670123=AA:CC:0F] is not universal - 8 truth tables accessible [46025713=F0:AA:33] is not universal - 8 truth tables accessible [46570213=CC:AA:0F] is not universal - 8 truth tables accessible [67234501=AA:0F:33] is not universal - 8 truth tables accessible [67452301=AA:33:0F] is not universal - 8 truth tables accessible [64752031=CC:55:0F] is not universal - 8 truth tables accessible [76543210=55:33:0F] is not universal - 8 truth tables accessibleThese ones are those that provide a \"not\" operator. The 8 truth tables are the 8 ways you can not or not-not each of the 3 inputs.The remaining exceptions all provide access to 16 truth tables. One example is [75462013=C3:99:0F]. As you can see, this table performs an Exclusive Or (XOR). The 16 truth tables that this gate and presumably all the others provide access to are: The 8 results provided by \"not\" alone The 3 ways you can XOR two different inputs The 3 ways you can ~XOR two different inputs The XOR of all 3 inputs The ~XOR of all 3 inputsThe possible logic gates form a group, with the \"set of all gates that XOR some of the inputs\" (etc.) being a subgroup.In summary: almost all 3 input/3 output reversible logic gates are universal in the sense that a network of them can produce any result. Thus the Fredkin and Toffoli gates are not remarkable in being universal.".
• Three-input_universal_logic_gate wikiPageID "4154909".
• Three-input_universal_logic_gate wikiPageLength "4780".
• Three-input_universal_logic_gate wikiPageOutDegree "13".
• Three-input_universal_logic_gate wikiPageRevisionID "704831491".
• Three-input_universal_logic_gate wikiPageWikiLink Category:Digital_electronics.
• Three-input_universal_logic_gate wikiPageWikiLink Exclusive_or.
• Three-input_universal_logic_gate wikiPageWikiLink Fredkin_gate.
• Three-input_universal_logic_gate wikiPageWikiLink Identity_(mathematics).
• Three-input_universal_logic_gate wikiPageWikiLink Logic_gate.
• Three-input_universal_logic_gate wikiPageWikiLink NAND_gate.
• Three-input_universal_logic_gate wikiPageWikiLink Reversible_computing.
• Three-input_universal_logic_gate wikiPageWikiLink Toffoli_gate.
• Three-input_universal_logic_gate wikiPageWikiLink Truth_table.
• Three-input_universal_logic_gate wikiPageWikiLinkText "Three-input universal logic gate".
• Three-input_universal_logic_gate wikiPageWikiLinkText "three-input universal logic gate".
• Three-input_universal_logic_gate wikiPageUsesTemplate Template:Cleanup.
• Three-input_universal_logic_gate wikiPageUsesTemplate Template:Context.
• Three-input_universal_logic_gate wikiPageUsesTemplate Template:Essay.
• Three-input_universal_logic_gate wikiPageUsesTemplate Template:Multiple_issues.
• Three-input_universal_logic_gate wikiPageUsesTemplate Template:Reflist.
• Three-input_universal_logic_gate subject Category:Digital_electronics.
• Three-input_universal_logic_gate type Page.
• Three-input_universal_logic_gate comment "Logic gates are used to build computer chips. Reversible logic gates are of interest because they could in principle generate useful results for less heat generated. The nand gate is universal among irreversible logic gates, in the sense that it is possible to simulate any irreversible logic gate with a network of these gates. The Fredkin and Toffoli gates were the first gates to be proved universal among reversible logic gates.".
• Three-input_universal_logic_gate label "Three-input universal logic gate".
• Three-input_universal_logic_gate sameAs Q7797258.
• Three-input_universal_logic_gate sameAs m.0bm2cc.
• Three-input_universal_logic_gate sameAs Q7797258.
• Three-input_universal_logic_gate wasDerivedFrom Three-input_universal_logic_gate?oldid=704831491.
• Three-input_universal_logic_gate isPrimaryTopicOf Three-input_universal_logic_gate.