note-math

Examples in natural language

Digital circuits represent bool

The hardware implementation of digital circuits is not handled here. I don’t know the details either

• And, , and, logical conjunction
• Or, , or, logical disjunction
• Not, , not, logical negation

Examples in natural language

Formal language

Digital circuit and logic gate representations of

Are gates designed to disallow reverse current?

A not gate turns low level into high level, which shows the hardware implementation of a gate needs external energy, it needs to be powered

are “redundant”, e.g. logically equivalently, we can use to represent

Circuit gate implementation starts with not,nand, i.e., . But I think maintaining the symmetry of is useful, whether cognitively or in terms of the duality of with respect to

Any function can be made using logic gates

(image from p.85 of ref-1)

Consider the input and output of the function separately

• Construction of inputs

Regarding the output, let’s first discuss the output

• Construction of output

Among the inputs, connect the wires that you want to output as to an or gate

Example not xor function. Connect the inputs to the output or gate

xor is called exclusive or, . The truth table for this function

1	1	0
1	0	1
0	1	1
0	0	0

• Construction of output. Can be thought of as as its components

If a full function isn’t needed, the circuit computing elements don’t necessarily have to be built in this fixed way. They can be further simplified based on the situation to reduce the number of gates used. But we won’t get into details here

bool algebra is denoted as or

[bool-distributive-law] Distributive Law

[bool-commutative-law] 交换律 . same for

[bool-associative-law] 结合律 . same for

Black box model

Possible implementation

• The middle of the diagram uses a loop circuit to reuse the Bool value from the previous cycle. If write control is turned off, the values of remain unchanged
• Inverters (not gates) ensure current direction and prevent attenuation (via external energy)
• Suppose the value of the yellow part in the loop circuit is , and the blue part is . To write into an existing , a higher write voltage than the one in the loop circuit is needed to override the loop, i.e. using higher voltage thus to override the existing

[finite-machine] Finite State Machine

[i/o] The input of a circuit might come from the outside world (e.g. sensors, keyboards), and the output of a circuit might also go to the outside world (e.g. signal lights, screens)

The rhythm of external inputs is usually inconsistent with the rhythm of the computer’s internal periodic circuits, so the external inputs need to pass through synchronization components first

Example is the number of steps taken when counting from 000, 001, 010 to 111, although this assumes we can recognize three bits. ,

Use the range of natural numbers contained in multiple bits, for example 3 bits as parameters, to correspond to real-world content. Example The representation of characters in a computer e.g. ASCII, Unicode, the position and color of pixels on a screen

(image modified from wiki media about ASCII. Hex refers to hexadecimal)

In practical applications, multiple bits per address is better than 1 bit per address, or rather, a two-dimensional memory array is more efficient than a one-dimensional one

(p. 265 of ref-1)

Control the computer to complete some circuit tasks through instructions. Instructions are also represented by binary (multi-bit data). The instruction stream is generated by the compiler based on the source code and stored in memory, then read and executed by the CPU

Some common circuit tasks

• Addition of natural numbers
• Judging whether bit data meets the required conditions, for example, judging if
• Jumping to the execution of other instructions

Assume an instruction is completed within one circuit cycle (single-cycle computer)

Example add instruction. add x_1 x_2. The bit data fields of the instruction are divided into three areas, representing different types of information

1. Reading the add instruction

   • The add instruction at adress_0 (add x_1 x_2 as well as adress_1, adress 2 come from source code and compiler generation)
   • The value adress_0 stored at the fixed memory address adress_of_instruction is read out, the data in the index area of the add instruction is sent to the control signal component (control unit), then control signals are calculated and output (too many details, see ref-1)

2. Execute the add instruction

   • The output control signals are input to the memory’s control circuit components, reading out x_1 in adress_1 and x_2 in adress_2 from memory, and inputting them into the arithmetic component (ALU)
   • Based on the output control signals, the output x_1 + x_2 from the arithmetic component is written to adress_1 (overwriting the value of x_1)

3. Enter and fetch the instruction for the next cycle

   • The value adress_0 stored in adress_of_instruction is sent by the pre-designed circuit to the arithmetic component to calculate adress_0 + 1 i.e. the next instruction address, which is then written into the data within adress_of_instruction. adress_0 + 1 will be executed in the next circuit cycle

Other instructions might have more than two data areas (non-instruction index areas)

The speed of the cycle circuit is far higher than human speed (1 GHz = 10^9 cycles per second)

Loops in high-level programming languages

let i : int = 0;

while (i < 10) {

    i = i + 1;

} // result = 10

let i : int = 0;

while (i < 10) {

    i = i + 1;

} // result = 10

1. Fetch instruction

   The bgt (branch_grater_than) instruction is stored at adress_0. (Instructions are generated from source code and the compiler.) 10 is in one data area of bgt, and the number of instructions needed for the while loop 3 is in another data area of bgt

2. Execute instruction

   Execute condition check

   Read out i and 10, compare their sizes in the arithmetic unit, give a control signal based on the result, and combine it with the control signal given by the bgt index area

   According to the result of the conditional judgment, perform different tasks

   • When

   The arithmetic unit outputs a control signal based on this judgment, changing the value stored in adress_of_instruction to the address of the next instruction adress_0 + 1

   • The instruction at adress_0 + 1 needs to perform the task

     Use the add instruction to calculate i + 1 and write it back to adress_1

   • After executing add, go back to the judgment for the next loop

     The instruction following the add instruction is a jump instruction at adress_0 + 2; its execution result is modifying the value of adress_of_instruction to adress_of_instruction - 2 = (adress_0 + 2) - 2 = adress_0, achieving an instruction jump to perform the next loop judgment

   • When
   The arithmetic unit outputs a control signal based on this bgt judgment, changing the value stored in adress_of_instruction to adress_0 + 3 instead of adress_0 + 1, jumping out of the while loop to execute the subsequent instructions

Use a parser or compiler to verify the correctness of the token stream language; essentially, it traverses all language rules and then stores them in memory as structured data (some visual descriptions: tables, nodes, trees)

One implementation method is recursive descent, enum + match (or if else) + recursion

If you want to make software run on a computer, you have to turn the token stream of the source code into structured data, and then into an instruction stream

If language rules are complex, they can be categorized and decomposed (multiple times), first traversing categories, then traversing rules within those categories. Example split into “syntax check” and “semantics check”