note-math

Examples of Natural Language

Digital circuits represent bool

I won't deal with the hardware implementation of digital circuits here. I don't know the details either.

• And, $\wedge$, and, logical conjunction
• Or, $\vee$, or, logical disjunction
• Not, $\neg$, not, logical negation

Examples of Natural Language

Formal Language

Representation of $\wedge ,\vee ,\neg$ in digital circuits and logic gates

Are gates designed to prevent reverse current?

The not gate converts a low level to a high level, indicating that the hardware implementation of the gate requires external energy and needs to be powered on

"Redundancy" e.g. we can use $\neg ,\wedge$ to represent $\vee$

Circuit gate implementations start with not,nand or $\neg ,\left(\neg \wedge \right)$. But I think maintaining the symmetry of $\wedge ,\vee$ is useful, cognitively or in terms of negative duals.

Logic gates can be used to create any ${\left\{0,1\right\}}^{𝑛}\to {\left\{0,1\right\}}^{𝑚}$ function

(image from p.85 of ref-1)

• Construction of ${\left\{0,1\right\}}^{𝑛}$ input

• Construction of ${\left\{0,1\right\}}^1$ output

In the input, connect the wires that you want to output to 1 to the or gate

Example not xor

Exclusive or, ⊕, xor

• Construction of ${\left\{0,1\right\}}^{𝑚}$ output. Just connect the required wires to $𝑚$ or games

If the function does not require complete ${\left\{0,1\right\}}^{𝑛}\to {\left\{0,1\right\}}^{𝑚}$, the circuit calculation components do not necessarily have to be constructed in this fixed way. It can be further simplified and the use of gates can be reduced depending on the situation. But I won't go into details here

bool algebra is denoted as $\left\{0,1\right\},+,\cdot$ or $\left\{0,1\right\},\vee ,\wedge$

bool-distributive-law_(tag) distributive law

bool-commutative-law_(tag) Commutative law $𝐴+𝐵=𝐵+𝐴$. same for $\cdot$

bool-associative-law_(tag) Associative law $\left(𝐴+𝐵\right)+𝐶=𝐴+\left(𝐵+𝐶\right)$. same for $\cdot$

Black box model

Possible implementation

• Use a ring circuit to reuse the 1/0 value of $𝑎,\overline{𝑎}$ from the previous cycle
• Inverter (not gate) ensures current direction and prevents 1 from decaying (through external energy)
• In order to write 0 to an existing 1, you need to write 1 to $\overline{\text{write}}$ to get $\overline{𝑎}=1$, and then invert it to $𝑎=0$
• Need a higher write voltage than the voltage in the loop to overwrite the previously existing $1$? e.g. use a higher voltage $\overline{\text{write }}=1$ to overwrite the existing $𝑎=1$

finite-machine_(tag) Finite State Machine

i/o_(tag) The input of a circuit may come from the outside world (e.g. sensors, keyboards), and the output of the circuit may also reach the outside world (e.g. signal lights, screens)

The rhythm of external input is usually inconsistent with the rhythm of the computer's internal periodic circuit, so the external input needs to pass through synchronization components first

Binary, order, natural number. Example $2^3$ is the number of steps from 000, 001, 010 to 111, although this assumes that we can recognize three bits. $2^{𝑛}=\underset{𝑛\text{-fold}}{\underbrace{2\cdots 2}}$, $101=1\cdot 2^2+0\cdot 2^1+1\cdot 2^0=4+1=5$

The range of natural numbers contained in multiple bits, for example, 3 bits of $0,1,\dots ,7$ as parameters, to correspond to the real world content. Example Computer's character representation e.g. ASCII, Unicode, the position and color of the light-emitting points on the screen

(image modified from wiki media about ASCII)

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

Usually represented by multi-bit data written in an address in memory to indicate certain circuit tasks

Some common circuit tasks

• Addition of natural numbers
• Determine whether the bit data meets the required conditions
• Jump to the execution of other instructions

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

Example add instruction. add x_1 x_2. The bit data of the instruction is divided into three regions, representing different types of information

1. Read the add instruction

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

2. Execute the add instruction

   • The output control signal is input to the control circuit element of the memory, reading x_1 in adress_1 and x_2 in adress_2 from the memory, and inputting them to the arithmetic element (ALU)
   • According to the output control signal, the output of the arithmetic element x_1 + x_2 is written to adress_1

3. Enter and read the instruction of the next cycle

   • The value adress_0 stored in adress_of_instruction is sent to the arithmetic element by a well-designed circuit, calculating adress_0 + 1 i.e. the next instruction address, which is written into the data in adress_of_instruction. adress_0 + 1 will be executed in the next circuit cycle

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

The speed of a periodic circuit is far greater than human speed (1 GHz = 10^9 cycles per second)

Loops in high-level programming languages

i : int = 0;
while (i < 10) {
    i = i + 1;
} // result = 10

1. Reading instructions

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

2. Executing instructions

   Executing the conditional judgment $𝑖<10$

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

   Perform different tasks based on the result of the conditional judgment

   • When $𝑖<10$

   The arithmetic element 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 is to perform the task ${𝑖}_{\text{new }}={𝑖}_{\text{ old }}+1$

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

   • After executing add, we need to return to the judgment of the next loop $𝑖<10?$

     The next instruction after the add instruction is the jump instruction. The result of the execution is to modify the value of adress_of_instruction to adress_0, implementing the jump of the instruction and performing the judgment of the next loop $𝑖<10?$

   • When $𝑖\ge 10$
   The arithmetic element outputs a control signal based on this judgment, changing the value stored in adress_of_instruction to adress_0 + 3, breaking out of the while loop, and executing the subsequent instructions

Use a parser to verify the correctness of the token stream language, essentially it's traversing all language rules, or using a generated finite state machine

The operation of the parser requires generating large and complex data structures in memory (some figurative descriptions: tables, nodes, trees)

If the data stream is source code of a high-level programming language, an instruction stream can also be generated based on this data structure. This is called compilation (compile), but parse and compile are often used interchangeably

If the language rules are very complex, the language rules can be classified and decomposed (multiple times), first traversing the classification, and then traversing the rules within the classification. Example Separate into "syntax check" and "semantics check"