Combinatorial Logic

From Chessprogramming wiki
Jump to: navigation, search

Home * Hardware * Combinatorial Logic

A Combinatorial Logic (also Combinational Logic) is a digital circuit where one or more outputs are boolean functions of multiple inputs. The basic boolean operations conjunction, disjunction and logical negation are sufficient to derive all other boolean as well as arithmetical operations. Opposed to a sequential logic, outputs are not dependent on their history, that is a combinatorial logic does not require memory.

Implementation

In hardware, combinatorial logic can either realized with hardwired gates of certain logic families or programmable logic devices. If the number of inputs is reasonable small, a once programmed ROM or LUT can act as combinatorial logic. The inputs are the address, while one output is associated with a data-pin. In software this is like performing ALU-operations versus a memory lookup with pre-calculated outputs for all relevant inputs, related to the space-time tradeoff.

Basic Operations

Operator symbols, truth tables, IEC and ANSI circuit diagram symbols, as well as discrete and relay logic circuits are given.

AND

An AND gate implements a logical conjunction.

a ∧ b

Truth Table

a b a and b
0 0 0
0 1 0
1 0 0
1 1 1

Symbols and Circuits

IEC AND label.svg
AND ANSI Labelled.svg
Diode-AND2.png
Relay and.svg

OR

An OR gate implements a logical disjunction.

a ∨ b

Truth Table

a b a or b
0 0 0
0 1 1
1 0 1
1 1 1

Symbols and Circuits

IEC OR label.svg
Or-gate-en.svg
Diode-OR2.png
Relay or.svg

NOT

A NOT gate or Inverter implements a logical negation.

¬a

Truth Table

a not a
0 1
1 0

Symbols and Circuits

IEC NOT label.svg
Not-gate-en.png
Transistor pegelumsetzer.svg
Relay not.svg

Derived Operations

Concrete electronic gates often combine AND and OR with trailing NOT for so called NAND and NOR gates. As application of De Morgan's laws a NAND can also be interpreted as OR of inverted inputs, and NOR as AND of inverted inputs.

NAND

A NAND gate is the inversion of AND, NOT AND.

a ⊼ b

Truth Table

a b not(a and b)
0 0 1
0 1 1
1 0 1
1 1 0

Symbols and Circuits

IEC NAND label.svg
AND ANSI Labelled.svg
TTL npn nand.svg
Relay nand.svg

NOR

A NOR gate is the inversion of OR, NOT OR.

a ⊽ b

Truth Table

a b not(a or b)
0 0 1
0 1 0
1 0 0
1 1 0

Symbols and Circuits

IEC NOR label.svg
NOR ANSI Labelled.svg
MC717 Circuit.svg
Relay nor.svg

XOR

A XOR gate implements a exclusive disjunction, which might be derived from AND/OR/NOT, for instance from four NAND gates.

a ⊻ b

Truth Table

a b a xor b
0 0 0
0 1 1
1 0 1
1 1 0

Symbols and Circuits

IEC XOR label.svg
XOR ANSI.svg
XOR from NAND.svg
Relay xor.svg

DNF and CNF

Combinational logic can be visualized by truth tables and the construction is generally done using disjunctive (sum of products) or conjunctive normal form (products of sums), and using boolean algebra or Karnaugh maps to simplify the expression.

ALU

Combinatorial logic is a huge part of the arithmetic logic unit (ALU) of processors, which provides accordant boolean logical instructions working on all bits of a register in parallel as mentioned in General Setwise Operations of Bitboards. Therefor each Combinatorial Logic can of course emulated in software.

Adder

A half adder performs an addition on two one-bit binary numbers. Output of an AND gate is the carry, while a XOR gate leaves the one-bit sum. A full adder with tad more gates adds three one-bit binary numbers, the third usually to feed in the carry from the previous digit, usually in carry look ahead architectures, such as Kogge-Stone adder, also mentioned as parallel prefix algorithm.

Full-adder logic diagram.svg

Full Adder

4-bit carry lookahead adder.svg

4-bit adder with Carry Look Ahead

Combinatorial Attacks

Assuming there are 13 times 64 digital inputs from a hardware wired chessboard. The 13 inputs per square has one exclusive "one" signal for either one of the twelve pieces or an empty signal. For each square a number of attacks/defend outputs may be defined to implement a huge Combinatorial Logic as a "zero cycle" attack table, i. e. output a8 is attacked from south by white rook as DNF (sum of products).

C Syntax

With C-like operators, that is '&' for AND and '|' for OR, the DNF would look like this:

southAttackByWhiteRook(a8) ::=
    wrook(a7)
| ( empty(a7) & wrook(a6) )
| ( empty(a7) & empty(a6) & wrook(a5) )
| ( empty(a7) & empty(a6) & empty(a5) & wrook(a4) )
| ( empty(a7) & empty(a6) & empty(a5) & empty(a4) & wrook(a3) )
| ( empty(a7) & empty(a6) & empty(a5) & empty(a4) & empty(a3) & wrook(a2) )
| ( empty(a7) & empty(a6) & empty(a5) & empty(a4) & empty(a3) & empty(a2) & wrook(a1) )

Circuit

The same sample as circuit f. i. in Diode logic with 34 diodes and 7 resistors:

 Board bus
 empty                    white rook                    
 a1 a2 a3 a4 a5 a6 a7 a8  a1 a2 a3 a4 a5 a6 a7 a8      ANDs (MIN)         OR (MAX)
 |  |  |  |  |  |  |  |   |  |  |  |  |  |  |  |		   
    |  |  |  |  |  |      |  |  |  |  |  |  |			   
    o--|--|--|--|--|------|--|--|--|--|--|--|----------|<|-----o---| R1 |---o +Vcc
       o--|--|--|--|------|--|--|--|--|--|--|----------|<|-----|
       |  o--|--|--|------|--|--|--|--|--|--|----------|<|-----|  D1-D7
       |  |  o--|--|------|--|--|--|--|--|--|----------|<|-----|
       |  |  |  o--|------|--|--|--|--|--|--|----------|<|-----|
       |  |  |  |  o------|--|--|--|--|--|--|----------|<|-----|
       |  |  |  |  |      o--|--|--|--|--|--|----------|<|-----o----------|>|------o  D28
       |  |  |  |  |         |  |  |  |  |  |                                      |
       o--|--|--|--|---------|--|--|--|--|--|----------|<|-----o---| R2 |---o +Vcc |
          o--|--|--|---------|--|--|--|--|--|----------|<|-----|                   |
          |  o--|--|---------|--|--|--|--|--|----------|<|-----|  D8-D13           |
          |  |  o--|---------|--|--|--|--|--|----------|<|-----|                   |
          |  |  |  o---------|--|--|--|--|--|----------|<|-----|                   |
          |  |  |  |         o--|--|--|--|--|----------|<|-----o----------|>|------o  D29
          |  |  |  |            |  |  |  |  |                                      |
          o--|--|--|------------|--|--|--|--|----------|<|-----o---| R3 |---o +Vcc |
             o--|--|------------|--|--|--|--|----------|<|-----|                   |
             |  o--|------------|--|--|--|--|----------|<|-----|  D14-18           |
             |  |  o------------|--|--|--|--|----------|<|-----|                   |
             |  |  |            o--|--|--|--|----------|<|-----o----------|>|------o  D30
             |  |  |               |  |  |  |                                      |
             o--|--|---------------|--|--|--|----------|<|-----o---| R4 |---o +Vcc |
                o--|---------------|--|--|--|----------|<|-----|  D19-D22          |
                |  o---------------|--|--|--|----------|<|-----|                   |
                |  |               o--|--|--|----------|<|-----o----------|>|------o  D31
                |  |                  |  |  |                                      |
                o--|------------------|--|--|----------|<|-----o---| R5 |---o +Vcc |
                   o------------------|--|--|----------|<|-----|  D23-D25          |
                   |                  o--|--|----------|<|-----o----------|>|------o  D32
                   |                     |  |                                      |
                   o---------------------|--|----------|<|-----o---| R6 |---o +Vcc |
                                         |  |                  |  D26-D27          |
                                         o--|----------|<|-----o----------|>|------o  D33
                                            |                                      |  D34
                                            o------------------o----------|>|------o-->--o a8 attacked  
                                                                                   |       by white rook
                                                                                   _       from south
                                                                                  | |  R7
                                                                                  |_|
                                                                                   |
                                                                                 --o--
                                                                                  ---   gnd
                                                                                   -

Publications

See also

External Links

AND gate
OR Gate
NOT Gate
NAND gate
NOR gate
XOR gate
XNOR gate
Fredkin gate
Toffoli gate [1]
Relay
Diode logic
Resistor–transistor logic
Diode–transistor logic
Transistor–transistor logic
Emitter-coupled logic
Complementary metal–oxide–semiconductor
Integrated injection logic

References

Up one Level