Adders and flip-flops · Additionneurs et bascules
| English | Français |
|---|---|
| carry/ˈkæri/ | retenue |
| half adder/hɑːf ˈædə/ | demi-additionneur |
| full adder/fʊl ˈædə/ | additionneur complet |
| flip-flop/flɪp flɒp/ | basculier |
| ripple-carry adder/ˈrɪpl ˈkæri ˈædə/ | additionneur à propagation d'addition |
| bistable/baɪˈsteɪbl/ | bistable |
| counters/ˈkaʊntəz/ | compteurs |
| SRAM/ˈesræm/ | SRAM |
| SR flip-flop/ˌes ˈɑː flɪp flɒp/ | Bascule SR |
| JK flip-flop/ˌdʒeɪ ˈkeɪ flɪp flɒp/ | Bascule JK |
| toggle/ˈtɒɡl/ | bascule |
How a machine that only knows true and false does arithmetic
- A processor has no adder in the sense of a thing that knows numbers. It has gates that answer true or false, and nothing else.
- Yet $1 + 1 = 10$ falls out of two gates: an XOR gives the sum digit, an AND gives the carry. That is the entire arithmetic unit in miniature, and chaining copies of it adds numbers of any width.
- The other half of a computer is remembering, and one bit of memory is also just gates, wired so that their outputs feed back into their inputs and hold.
- This lesson is the half adder 半加器, the full adder 全加器, and the flip-flop 触发器 that stores a bit.
Comment une machine qui ne connaît que le vrai et le faux effectue l'arithmétique
- Un processeur n'a pas d'additionneur au sens d'un objet qui connait les nombres. Il a des portes qui répondent vrai ou faux, et rien d'autre.
- Pourtant $1 + 1 = 10$ résulte de deux portes : un XOR donne le chiffre de somme, un AND donne la retenue. C'est l'unité arithmétique entière en miniature, et en enchaînant des copies de celle-ci, on additionne des nombres de n'importe quelle largeur.
- L'autre moitié d'un ordinateur est la mémoire, et un bit de mémoire est également composé de portes, câblées de sorte que leurs sorties retournent vers leurs entrées et maintiennent l'état.
- Cette leçon porte sur l'additionneur semi (half adder) 半加器, l'additionneur complet (full adder) 全加器 et le bascule (flip-flop) 触发器 qui stocke un bit.
The half adder
- A half adder adds two single bits, $A$ and $B$, producing a sum $S$ and a carry 进位 $C$.
| A | B | S | C |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
- Read the columns: $S$ is 1 when exactly one input is 1, which is XOR. $C$ is 1 only when both are 1, which is AND. So $S = A \oplus B$ and $C = A \cdot B$.
- It ignores any carry in, which is why it is only "half" an adder and cannot be chained on its own.
Two gates, and binary addition exists
L'additionneur demi
- Un additionneur semi additionne deux bits simples, $A$ et $B$, produisant une somme $S$ et une retenue 进位 $C$.
| A | B | S | C |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
- Lisez les colonnes : $S$ vaut 1 si exactement une entrée est à 1, c'est-à-dire XOR. $C$ vaut 1 uniquement si les deux sont à 1, c'est-à-dire AND. Donc $S = A \oplus B$ et $C = A \cdot B$.
- Il ignore toute retenue entrante, ce qui explique qu'il ne soit qu'un « demi » additionneur et qu'il ne puisse pas être enchaîné seul.
Deux portes, et l'addition binaire existe
The gates inside an adder · Les portes à l'intérieur d'un additionneur
A half-adder's sum bit is an XOR gate and its carry is an AND gate — toggle A and B and watch the truth-table row light up. · Le bit de somme d'un demi-additionneur est une porte XOR et sa retenue est une porte AND — alternez A et B et observez la ligne de la table de vérité s'allumer.
In a half adder, the sum output S is produced by which gate? · Dans un demi-additionneur, quelle porte produit la sortie S ?
$S = A \text{ XOR } B$ (1 when the inputs differ); the carry is $A \text{ AND } B$. · $S = A \text{ XOR } B$ (1 lorsque les entrées diffèrent) ; la retenue est $A \text{ AND } B$.
In a half adder the carry output C is produced by which single gate? · Dans un demi-additionneur, quelle porte unique produit la sortie C ?
C is 1 only when both inputs are 1, which is AND. The sum S is 1 when exactly one input is 1, which is XOR. · C vaut 1 uniquement lorsque les deux entrées valent 1, ce qui correspond à AND. La somme S vaut 1 lorsque exactement une entrée vaut 1, ce qui correspond à XOR.
The full adder
- A full adder adds three bits: $A$, $B$ and a carry-in, producing a sum and a carry-out. $S = A \oplus B \oplus C_{\text{in}}$.
- It can be built from two half adders plus an OR gate: the first half adder adds $A$ and $B$, the second adds that sum to the carry-in, and the OR combines the two carries.
- Chain full adders so that each carry-out feeds the next carry-in, and you have a multi-bit ripple-carry adder 行波进位加法器: four of them add two 4-bit numbers.
The carry is what has to travel, which is why it is called ripple
L'additionneur complet
- Un additionneur complet additionne trois bits : $A$, $B$ et une retenue entrante, produisant une somme et une retenue sortante. $S = A \oplus B \oplus C_{\text{in}}$.
- Il peut être construit à partir de deux additionneurs semi plus une porte OR : le premier additionneur semi ajoute $A$ et $B$, le second ajoute cette somme à la retenue entrante, et la porte OR combine les deux retenues.
- Enchaînez des additionneurs complets de sorte que chaque retenue sortante alimente la retenue entrante suivante, vous obtenez un additionneur à propagation de retenue 行波进位加法器 : quatre d'entre eux additionnent deux nombres de 4 bits.
La retenue est ce qui doit voyager, c'est pourquoi on l'appelle propagation
Match each building block to what it does. · Reliez chaque bloc de construction à ce qu'il fait.
Adders add bits (chain full adders for multi-bit addition); flip-flops store a bit (the JK fixes the SR forbidden state). · Les additionneurs ajoutent des bits (enchaînez des additionneurs complets pour l'addition multi-bit) ; les bascules stockent un bit (JK corrige l'état interdit de SR).
How does a full adder differ from a half adder? · En quoi un additionneur complet diffère-t-il d'un demi-additionneur ?
A full adder adds A, B and a carry-in (so adders can be chained) — built from two half adders plus an OR gate. · Un additionneur complet additionne A, B et une retenue d'entrée (permettant de chaîner les additionneurs) — construit à partir de deux demi-additionneurs plus une porte OR.
Worked example: why a full adder, not two half adders
- Explain why a 4-bit adder is built from full adders rather than half adders.
- Adding two 4-bit numbers column by column, every column except the rightmost may receive a carry from the column to its right, so it has three inputs to add, not two.
- A half adder has no carry-in, so it cannot take that third input, and the carry would simply be lost.
- Only the least significant column has no carry-in, so a half adder would do there; in practice all four are full adders, with the first carry-in tied to 0.
Exemple résolu : pourquoi un additionneur complet, et non deux additionneurs semi
- Expliquez pourquoi un additionneur de 4 bits est construit à partir d'additionneurs complets plutôt que d'additionneurs semi.
- En additionnant deux nombres de 4 bit colonne par colonne, chaque colonne sauf la droite peut recevoir une retenue provenant de la colonne de droite, elle a donc trois entrées à additionner, pas deux.
- Un additionneur semi n'a pas de retenue entrante, il ne peut donc pas prendre cette troisième entrée, et la retenue serait simplement perdue.
- Seule la colonne de poids faible n'a pas de retenue entrante, un additionneur semi suffirait là ; en pratique, les quatre sont des additionneurs complets, avec la première retenue entrante fixée à 0.
Why must a 4-bit adder use full adders rather than half adders? · Pourquoi un additionneur 4 bits doit-il utiliser des additionneurs complets plutôt que des demi-additionneurs ?
A half adder does produce a carry; what it lacks is a carry-in, so it cannot accept the carry arriving from the previous column. · Un demi-additionneur produit bien une retenue ; ce qu'il lui manque, c'est une retenue d'entrée, il ne peut donc pas accepter la retenue provenant de la colonne précédente.
Put the construction of a 4-bit ripple-carry adder in order. · Placez la construction d'un additionneur à propagation de retenue 4 bits dans l'ordre.
Gates make a half adder, half adders make a full adder, full adders chain into a word-width adder. The carry rippling along is what gives it its name. · Les portes font un demi-additionneur, les demi-additionneurs font un additionneur complet, les additionneurs complets forment un additionneur large. La retenue qui propage le long donne son nom.
Flip-flops
- A flip-flop is a bistable 双稳态 circuit: it has two stable states, 0 and 1, and it remembers the one it is in. It stores exactly one bit.
- It is the basic element of registers, where $n$ bits means $n$ flip-flops, of counters, and of SRAM 静态RAM cells.
- Unlike an adder, whose output depends only on its inputs now, a flip-flop's output depends on its past inputs. That is what memory means at the circuit level.
Les bascules
- Une bascule (flip-flop) est un circuit bistable 双稳态 : elle possède deux états stables, 0 et 1, et elle mémorise celui dans lequel elle se trouve. Elle stocke exactement un bit.
- C'est l'élément de base des registres, où $n$ bits signifie $n$ bascules, des compteurs et des cellules de SRAM 静态RAM.
- Contrairement à un additionneur dont la sortie dépend uniquement de ses entrées actuelles, la sortie d'une bascule dépend de ses entrées passées. C'est cela qui signifie mémoire au niveau du circuit.
A flip-flop is used to: · Une bascule est utilisée pour :
A flip-flop has two stable states and holds one bit — the building block of registers and SRAM. · Une bascule a deux états stables et conserve un bit — le bloc de base des registres et de la SRAM.
A flip-flop is bistable — it has two stable states and remembers one bit — which makes it the building block of registers and SRAM. · Une bascule est bistable — elle a deux états stables et mémorise un bit — ce qui en fait le bloc de base des registres et de la SRAM.
Chaining flip-flops gives registers and counters; SRAM cache is built from them (no refresh needed, unlike DRAM). · Enchaîner des bascules donne des registres et des compteurs ; le cache SRAM est construit à partir d'eux (pas besoin de rafraîchissement, contrairement à la DRAM).
SR and JK
- An SR flip-flop SR触发器 has inputs S (set) and R (reset) and outputs $Q$ and $\overline{Q}$, built from two cross-coupled NOR gates.
S=1, R=0sets $Q$ to 1.S=0, R=1resets $Q$ to 0.S=0, R=0holds the current state, which is the memory.S=1, R=1is invalid: it asks for set and reset at once.- A JK flip-flop JK触发器 removes that flaw by giving the
1,1input a meaning: toggle 翻转, so the output flips to its opposite. That makes it ideal for counters 计数器, since a chain of toggling flip-flops counts in binary. - A JK is usually clocked: the inputs act only on a clock edge, which keeps every flip-flop in the machine in step.
The invalid input turned into a useful one
SR et JK
- Un bascule SR SR触发器 a des entrées S (set) et R (reset) et des sorties $Q$ et $\overline{Q}$, construites à partir de deux portes NOR croisées.
S=1, R=0met $Q$ à 1.S=0, R=1remet $Q$ à 0.S=0, R=0maintient l'état actuel, c'est la mémoire.S=1, R=1est invalide : il demande set et reset à la fois.- Une bascule JK JK触发器 élimine ce défaut en donnant à l'entrée
1,1une signification : toggle 翻转 (retournement), de sorte que la sortie passe à l'état opposé. Cela la rend idéale pour les compteurs 计数器, car une chaîne de bascules à retournement compte en binaire. - Une bascule JK est généralement horlogée : les entrées n'agissent qu'à un front d'horloge, ce qui maintient toutes les bascules de la machine synchronisées.
L'entrée invalide s'est transformée en une entrée utile
For an SR flip-flop, which statements are correct? Select all · tout that apply. · Pour une bascule SR, quelles affirmations sont correctes ? Sélectionnez tous ceux qui s'appliquent.
Toggling on 1,1 is the JK's improvement. On an SR that input asks for set and reset at once and is invalid. · La bascule sur 1,1 est l'amélioration apportée au JK. Sur un SR, cette entrée demande à la fois la mise en position et la remise à zéro, ce qui est invalide.
The JK flip-flop's toggle behaviour is what makes it suitable for building counters. · Le comportement de bascule du bascule JK est ce qui le rend adapté à la construction de compteurs.
A chain of flip-flops each toggling on its input counts in binary. Clocking them keeps every stage in step. · Une chaîne de bascules se basculant chacune à son entrée effectue un comptage binaire. Les impulser d'horloge maintient chaque étage en phase.
Worked example: trace an SR flip-flop
- $Q$ is currently 0. Give $Q$ after the inputs S=1 R=0, then S=0 R=0, then S=0 R=1.
- S=1, R=0 sets the output, so $Q$ becomes 1.
- S=0, R=0 holds, so $Q$ stays 1. This is the step that shows it is a memory: the inputs say nothing, and the output persists.
- S=0, R=1 resets, so $Q$ becomes 0. If S=1 and R=1 were applied, the answer is that the input is invalid, not a value.
Exemple résolu : suivre une bascule SR
- $Q$ est actuellement 0. Donnez $Q$ après les entrées S=1 R=0, puis S=0 R=0, puis S=0 R=1.
- S=1, R=0 définit la sortie, donc $Q$ devient 1.
- S=0, R=0 maintient, donc $Q$ reste 1. C'est l'étape qui montre que c'est une mémoire : les entrées ne disent rien, et la sortie persiste.
- S=0, R=1 réinitialise, donc $Q$ devient 0. Si S=1 et R=1 étaient appliqués, la réponse est que l'entrée est invalide, pas une valeur.
Marks that slip away
- $S = A \oplus B$ and $C = A \cdot B$: XOR for the sum, AND for the carry. Swapping them loses both marks.
- "Half" means no carry-in, not "half the bits".
- A full adder is two half adders plus an OR, and the OR combines the two carries.
- On an SR flip-flop,
0,0holds and1,1is invalid. The JK's improvement is that1,1toggles.
Pièges qui font perdre des points
- $S = A \oplus B$ et $C = A \cdot B$ : XOR pour la somme, AND pour la retenue. Les échanger fait perdre les deux points.
- « Demi » signifie pas de retenue entrante, pas « la moitié des bits ».
- Un additionneur complet est deux additionneurs semi plus une OR, et la OR combine les deux retenues.
- Sur une bascule SR,
0,0maintient et1,1est invalide. L'amélioration de la JK est que1,1retourne.
You've got it
- half adder: two bits in, $S = A \oplus B$ from an XOR and $C = A \cdot B$ from an AND; no carry-in
- full adder: three bits in, built from two half adders plus an OR; chain them, carry-out to carry-in, for a ripple-carry adder
- a flip-flop is bistable and stores one bit; $n$ flip-flops make an $n$-bit register, and they are the cells of SRAM
- SR: set, reset,
0,0holds,1,1invalid · JK:1,1toggles, which is what makes counters, and it is clocked to stay synchronised
Vous avez compris
- additionneur semi : deux bits en entrée, $S = A \oplus B$ issu d'une XOR et $C = A \cdot B$ issu d'une AND ; pas de retenue entrante
- additionneur complet : trois bits en entrée, construit à partir de deux additionneurs semi plus une OR ; enchaînez-les, retenue sortante vers retenue entrante, pour un additionneur à propagation de retenue
- une bascule est bistable et stocke un bit ; $n$ bascules font un registre de $n$ bits, et elles sont les cellules de SRAM
- SR : set, reset,
0,0maintient,1,1invalid · JK :1,1retourne, ce qui rend les compteurs possibles, et elle est horlogée pour rester synchronisée