Site News  |   Monitor Keywords  |   Monitor Archive  |   Organizer  |   Account Info  |

Reversible sequential apparatuses

Reversible sequential apparatuses description/claims

1. Field of the Invention

The present invention relates to reversible sequential apparatuses, and more particularly to a reversible sequential apparatus configured by reversible gates.

2. Description of the Related Art

Reversible computing eliminates information loss during the computation process. Thus, it naturally minimizes heat generation due to information loss. Zero energy dissipation is possible only if all gates in a network are reversible. As a result, reversibility will become an essential property in future circuit design. Reversible logic has been applied to various future technologies, such as ultra-low-power CMOS design, optical computing, quantum computing and nanotechnology. These technologies increasingly employ reversible logic gates to reduce power consumption.

However, conventional logic gates are generally irreversible. Among the most commonly used gates, only the NOT gate is reversible. The AND gate and the OR gate are irreversible because they cannot satisfy the condition of one-to-one and mapping between the inputs and outputs of a logic gate. One way to make the AND function reversible is to add one input and two outputs, as shown in FIG. 1(a). These additional input and outputs for reversibility are called garbage bits. The AND function can be obtained in the third output column xy□z (□ representing an XOR gate) of FIG. 1(a), when setting z=0. The truth table of AND function is shown in bold.

This whole truth table is equivalent to the truth table of the 3-bit Toffoli gate, and its symbol is shown in FIG. 1(b). The third output column xy□z means that the output is z when x=y=1, and otherwise the output is z. This gate can be used to realize a 2-input reversible AND function by setting z as a constant 0, as mentioned.

Fredkin gate is a reversible gate as well and is also called controlled SWAP gate. FIG. 2(a) is the symbol of Fredkin gate and FIG. 2(b) is its truth table. Its behavior can be described as follows: if the control bit x is set to 1, the outputs of y and z are swapped; otherwise they remain unchanged.

A restriction on reversible logic synthesis has to be followed: the fanout count of a signal net must equal one so that a duplication is necessary if two copies of one signal are needed. This restriction is due to the fact that the fanout structure itself is not reversible. For fanout, the number of input signals is one, but there are two or more output signals. Therefore, for this restriction, a 2-bit Toffoli gate is utilized to duplicate a signal. The symbol of a 2-bit Toffoli gate and its truth table are shown in FIGS. 3(a) and 3(b), respectively. The function of the second output column is x□y. If y is set as a constant 0, a copy of input variable x will be obtained in the second output, which is shown in bold. Therefore, the fanout structure in a conventional network can be implemented in this way.

There are two objectives in reversible circuit synthesis: 1. Minimize the number of gates: the number of gates gives a simple estimation of the implementation cost of a reversible circuit. 2. Minimize the number of garbage outputs: we need extra implementation cost (area and power) for those garbage outputs in reversible circuits. Minimizing the number of garbage outputs leads to minimizing the chip area and power consumption of a reversible circuit.

However, the synthesis result of a traditional D latch is not good when the conventional direct transformation method is used to implement a reversible D latch. This is because the D latch is built by many irreversible gates; using the direct transformation method to construct a reversible D latch will require a large number of gates and garbage outputs.

An objective of the present invention is to provide a reversible sequential apparatus built by a minimum number of gates. The implementation cost of the reversible sequential apparatuses is substantially reduced.

In order to achieve the objective, the present invention discloses a reversible sequential apparatus comprising a first logic gate and a second logic gate. The first logic gate includes a first input terminal, a second input terminal, a third input terminal, a first output terminal, a second output terminal and a third output terminal. The second logic gate includes a first input line, a second input line, a first output line and a second output line. The terminals are used to designate the inputs and outputs of the first logic gate and the lines are used to designate the inputs and outputs of the second logic gate. The first input terminal for carrying a clock signal is coupled to the first output terminal and the second input terminal for carrying an input signal is coupled to the second output terminal. When the first input terminal and the second input terminal are simultaneously set to a first state, the level of the third output terminal is inverse to the level of the third input terminal; otherwise, the level of the third output terminal is identical to the level of the third input terminal. The third output terminal, second input line and second output line are coupled to each other. The input signal carried on the first input line is set to a constant level so that the second output line and the first output line have the same outputs. Furthermore, the first output line is fed back to the third input terminal.

The present invention further discloses a reversible sequential apparatus comprising a first logic gate, a second logic gate, a third logic gate and a fourth logic gate. The fourth logic gate includes a first input line, a second input line, a first output line and a second output line. The first logic gate includes first, second and third input lines and first, second, and third output lines. Each of the second logic gate and third logic gate includes first, second, third and fourth input lines and first, second, third and fourth output lines. The fourth input line and fourth output line of the third logic gate, the fourth input line and fourth output line of the second logic gate, the third input line and third output line of the first logic gate and the second input line and second output line of the fourth logic gate are connected in series. The third input line and third output line of the third logic gate and the third input line and third output line of the second logic gate are connected in series. The second input line and second output line of the third logic gate, the second input line and second output line of the second logic gate and the second input line and second output line of the first logic gate are connected in series. The first input line and first output line of the third logic gate, the first input line and first output line of the second logic gate and the first input line and first output line of the first logic gate are connected in series. When the first, second and fourth input lines of the third logic gate are simultaneously set to 1 as a first level, the levels of the third input line and the third output line of the third logic gate are opposite to each other. When the first, third and fourth input lines of the second logic gate are simultaneously set to the first level, the levels of the second input line and the second output line of the second logic gate are opposite to each other. When the first and second input lines of the first logic gate are simultaneously set to the first level, the levels of the third input line and the third output line of the first logic gate are opposite to each other. The input signal carried on the first input line of the fourth logic gate is set to a constant level so that the second output line and the first output line of the fourth logic gate have the same outputs. Furthermore, the first output line of the fourth logic gate is fed back to the fourth input line of the third logic gate.

• Provisional Patent
• Utility Patent

• What Is a Patent?
• What Is a Trademark or Servicemark?
• What Is a Copyright?
• Patent Laws