Bộ cộng nhị phân là mạch ghép các cổng logic để cộng hai số viết bằng 0 và 1. Viên gạch nhỏ nhất là bộ cộng bán phần: chữ số tổng là A XOR B, số nhớ là A AND B. Ghép hai bộ bán phần và một cổng OR được bộ cộng toàn phần, cộng được cả số nhớ từ cột bên phải; xếp n bộ toàn phần nối đuôi nhau là cộng được hai số n bit — đúng như cách ta cộng tay từng cột.
Cộng tay trong hệ nhị phân trước đã
Hệ nhị phân chỉ có hai chữ số 0 và 1, và chỉ có bốn phép cộng một chữ số cần nhớ:
- 0 + 0 = 0
- 0 + 1 = 1
- 1 + 0 = 1
- 1 + 1 = 10 (viết 0, nhớ 1 — giống 5 + 5 = 10 ở hệ thập phân)
Cộng hai số nhiều chữ số thì làm từ phải sang trái, cột nào cũng cộng ba thứ: chữ số của số thứ nhất, chữ số của số thứ hai, và số nhớ từ cột trước. Lớn nhất là 1 + 1 + 1 = 11 (viết 1, nhớ 1).
Ví dụ: 1011 + 0110. Đổi sang thập phân để biết đáp án trước: 1011 = 8 + 2 + 1 = 11; 0110 = 4 + 2 = 6; tổng 17 = 16 + 1 = 10001.
| Cột (từ phải) | Chữ số A | Chữ số B | Nhớ vào | Tổng cột | Viết | Nhớ ra |
|---|---|---|---|---|---|---|
| 1 (hàng 1) | 1 | 0 | 0 | 1 | 1 | 0 |
| 2 (hàng 2) | 1 | 1 | 0 | 2 = 10 | 0 | 1 |
| 3 (hàng 4) | 0 | 1 | 1 | 2 = 10 | 0 | 1 |
| 4 (hàng 8) | 1 | 0 | 1 | 2 = 10 | 0 | 1 |
Đọc từ trên xuống, chữ số viết ra là 1, 0, 0, 0 (từ phải sang trái) và còn nhớ 1 ở cuối: kết quả 10001 = 17. Khớp.
Câu hỏi của người thiết kế mạch là: "viết" và "nhớ ra" ở mỗi cột có phải là hàm logic của ba đầu vào không? Có — và đó là toàn bộ bí mật.
Bộ cộng bán phần: XOR cho chữ số, AND cho số nhớ
Bỏ số nhớ vào, chỉ cộng hai bit A và B. Gọi S là chữ số tổng, C là số nhớ:
| A | B | A + B | S | C |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 10 | 0 | 1 |
Nhìn cột S: bằng 1 khi đúng một trong hai bằng 1 — đó là XOR (ký hiệu ⊕). Nhìn cột C: bằng 1 chỉ khi cả hai bằng 1 — đó là AND (ký hiệu ·). Vậy:
S = A ⊕ B C = A · B
Hai cổng, một XOR và một AND, là đủ. Gọi là "bán phần" vì nó chưa nhận được số nhớ từ cột trước, nên chỉ dùng được cho cột ngoài cùng bên phải.
Bộ cộng toàn phần: cộng ba bit
Thêm đầu vào Cv (nhớ vào), đầu ra Cr (nhớ ra). Lập bảng đủ 8 trường hợp bằng cách đếm số bit 1 trong ba đầu vào:
| A | B | Cv | Số bit 1 | S | Cr |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 2 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 2 | 0 | 1 |
| 1 | 1 | 0 | 2 | 0 | 1 |
| 1 | 1 | 1 | 3 | 1 | 1 |
Quy luật hiện ra ngay:
- S = 1 khi số bit 1 là lẻ (1 hoặc 3). Đó là XOR ba đầu vào: S = A ⊕ B ⊕ Cv — cùng phép tính "đếm chẵn lẻ" của đèn cầu thang ba công tắc.
- Cr = 1 khi có ít nhất hai bit 1. Đó là hàm "đa số": Cr = A·B + A·Cv + B·Cv.
Người thiết kế thường viết Cr ở dạng khác cho tiện ghép mạch: Cr = A·B + Cv·(A ⊕ B). Kiểm hai dạng bằng nhau qua bốn dòng có Cr = 1 và một dòng dễ nhầm:
- A = 0, B = 1, Cv = 1: A·B = 0; A ⊕ B = 1, Cv·1 = 1 ⇒ Cr = 1. Đúng.
- A = 1, B = 0, Cv = 1: tương tự, Cr = 1. Đúng.
- A = 1, B = 1, Cv = 0: A·B = 1 ⇒ Cr = 1. Đúng.
- A = 1, B = 1, Cv = 1: A·B = 1 ⇒ Cr = 1. Đúng (ở đây A ⊕ B = 0 nhưng không sao).
- A = 0, B = 0, Cv = 1: A·B = 0; A ⊕ B = 0 ⇒ Cr = 0. Đúng — một bit 1 thì không nhớ.
Ghép từ hai bộ bán phần
Dạng Cr = A·B + Cv·(A ⊕ B) cho thấy cách lắp:
- Bộ bán phần thứ nhất nhận A, B: ra s₁ = A ⊕ B và c₁ = A·B.
- Bộ bán phần thứ hai nhận s₁ và Cv: ra S = s₁ ⊕ Cv và c₂ = s₁·Cv.
- Một cổng OR gộp hai số nhớ: Cr = c₁ + c₂. (c₁ và c₂ không bao giờ cùng bằng 1, vì c₁ = 1 cần A = B = 1, khi đó s₁ = 0 nên c₂ = 0.)
Tổng cộng: 2 cổng XOR, 2 cổng AND, 1 cổng OR cho mỗi bộ toàn phần.
Nối đuôi thành bộ cộng nhiều bit
Đặt bốn bộ toàn phần cạnh nhau, đầu "nhớ ra" của bộ bên phải nối vào "nhớ vào" của bộ bên trái, đầu "nhớ vào" của bộ ngoài cùng bên phải nối cố định với 0. Kiểu nối này gọi là bộ cộng lan truyền nhớ (ripple-carry): số nhớ chạy từ phải qua trái như sóng.
Ví dụ 1: 0111 + 0101
Thập phân: 7 + 5 = 12 = 1100. Mạch tính:
| Bộ | A | B | Cv | S = A⊕B⊕Cv | Cr |
|---|---|---|---|---|---|
| Bit 0 | 1 | 1 | 0 | 0 | 1 |
| Bit 1 | 1 | 0 | 1 | 0 | 1 |
| Bit 2 | 1 | 1 | 1 | 1 | 1 |
| Bit 3 | 0 | 0 | 1 | 1 | 0 |
Đọc S từ bit 3 xuống bit 0: 1100 = 12. Nhớ ra cuối cùng bằng 0: kết quả nằm gọn trong 4 bit.
Ví dụ 2: 1011 + 0110 và chuyện tràn số
Làm như bảng cộng tay ở đầu bài, bốn bộ cho S = 0001 và nhớ ra cuối cùng = 1. Nếu máy chỉ giữ 4 bit, kết quả bị cắt còn 0001 = 1 thay vì 17: đây là tràn số. Bộ vi xử lý giữ bit nhớ cuối này trong một "cờ nhớ" để phần mềm biết mà xử lý — đó là lý do một biến kiểu số nguyên 8 bit không dấu cộng 200 + 100 lại ra 44 (300 − 256).
Trừ bằng chính mạch cộng
Máy tính không cần mạch trừ riêng. Với số bù hai, A − B = A + (đảo mọi bit của B) + 1. Phần "+ 1" lấy luôn từ đầu nhớ vào của bit 0, đặt bằng 1 thay vì 0.
Ví dụ 4 bit: 9 − 3.
- 9 = 1001; 3 = 0011.
- Đảo bit của 0011 được 1100.
- Cộng 1001 + 1100 với nhớ vào bằng 1: 1001 + 1100 = 10101; thêm 1 được 10110.
- Bỏ bit nhớ thứ năm: 0110 = 6. Đúng 9 − 3 = 6.
Phần "đảo bit khi trừ, giữ nguyên khi cộng" làm bằng cổng XOR: B ⊕ 0 = B, B ⊕ 1 = B'. Một tín hiệu điều khiển "trừ" nối vào một đầu của mọi cổng XOR và vào nhớ vào của bit 0 là xong. Một tính chất XOR quen thuộc, lại có chỗ dùng.
Nhanh hơn: khi số nhớ không phải chờ
Bộ lan truyền nhớ đơn giản nhưng chậm: bit cao nhất phải đợi số nhớ đi qua mọi bit thấp hơn. Với 64 bit, đó là 64 tầng chờ. Các chip thật dùng bộ cộng nhìn trước số nhớ (carry-lookahead). Ý tưởng là logic thuần tuý:
- Bit i tự sinh nhớ khi Aᵢ·Bᵢ = 1, ký hiệu Gᵢ = Aᵢ·Bᵢ.
- Bit i truyền nhớ khi Aᵢ ⊕ Bᵢ = 1 (có nhớ vào thì nhớ ra), ký hiệu Pᵢ = Aᵢ ⊕ Bᵢ.
- Vậy Cᵢ₊₁ = Gᵢ + Pᵢ·Cᵢ. Thay liên tiếp: C₂ = G₁ + P₁·G₀ + P₁·P₀·C₀.
Biểu thức của C₂ chỉ chứa A, B và C₀, không chứa số nhớ trung gian nào, nên tính được cùng lúc với C₁ thay vì đợi. Đổi lại phải dùng thêm cổng: tốc độ và số cổng là cuộc mặc cả thường trực trong thiết kế chip.
Một chút lịch sử
| Năm | Mốc |
|---|---|
| 1937 | George Stibitz ở Bell Labs ghép rơ-le thành một mạch cộng nhị phân một bit ngay tại bàn bếp nhà mình, sau gọi là "Model K". |
| 1937–1938 | Luận văn của Claude Shannon có một mạch cộng nhị phân bằng rơ-le trong phần ví dụ, thiết kế từ đại số Boole. |
| Thập niên 1940–1950 | Máy tính dùng đèn điện tử, rồi bóng bán dẫn; bộ cộng nằm trong khối số học của mọi máy. |
| Ngày nay | Khối số học – logic (ALU) trong bộ vi xử lý chứa bộ cộng nhiều tầng nhìn trước số nhớ, vẫn dựng trên đúng hai công thức S và Cr ở trên. |
Bài tập
- Tính 0101 + 0011 bằng bảng bốn bộ toàn phần. — Đáp án: 5 + 3 = 8 = 1000; nhớ ra cuối bằng 0.
- Với A = 1, B = 0, Cv = 1, tính S và Cr. — Đáp án: S = 1 ⊕ 0 ⊕ 1 = 0; Cr = 1·0 + 1·(1 ⊕ 0) = 1.
- Một bộ cộng 8 bit lan truyền nhớ dùng bao nhiêu cổng nếu mỗi bộ toàn phần dùng 5 cổng? — Đáp án: 8 × 5 = 40 cổng (nếu bit 0 cũng dùng bộ toàn phần).
- Tính 6 − 2 trong 4 bit bằng cách đảo bit và cộng. — Đáp án: 0110 + 1101 + 1 = 0110 + 1110 = 10100, bỏ bit thứ năm còn 0100 = 4.
- Vì sao c₁ và c₂ trong bộ toàn phần không bao giờ cùng bằng 1? — Đáp án: c₁ = 1 cần A = B = 1, khi đó s₁ = A ⊕ B = 0 nên c₂ = s₁·Cv = 0.
Dùng vào đâu
- Môn Kỹ thuật số, Kiến trúc máy tính: bộ cộng toàn phần là bài thi kinh điển; thuộc hai công thức S, Cr và vẽ được từ hai bộ bán phần là qua phần này.
- Lập trình: hiểu tràn số và số bù hai giải thích vì sao số nguyên có giới hạn, vì sao cộng hai số dương lớn có thể ra số âm trong nhiều ngôn ngữ.
- Tự thử: các phần mềm mô phỏng mạch logic miễn phí cho phép kéo thả cổng XOR, AND, OR để dựng bộ cộng 4 bit và bấm thử từng phép tính.
- Đọc tiếp: bài cổng NAND trong cùng danh mục cho thấy cả bộ cộng có thể dựng chỉ bằng một loại cổng.
Câu hỏi thường gặp
Bộ cộng bán phần và bộ cộng toàn phần khác nhau thế nào?
Bộ cộng bán phần cộng hai bit, cho ra chữ số tổng và số nhớ, nhưng không nhận số nhớ từ cột trước. Bộ cộng toàn phần cộng ba bit (hai chữ số và một số nhớ vào), nên dùng được cho mọi cột khi cộng số nhiều bit.
Công thức của bộ cộng toàn phần là gì?
Chữ số tổng S = A ⊕ B ⊕ Cv, tức bằng 1 khi số bit 1 trong ba đầu vào là lẻ. Số nhớ ra Cr = A·B + Cv·(A ⊕ B), tương đương "có ít nhất hai trong ba đầu vào bằng 1".
Vì sao bộ cộng dùng cổng XOR?
Chữ số hàng đơn vị khi cộng hai bit là 1 khi đúng một bit bằng 1, và là 0 khi hai bit bằng nhau (0 + 0 = 0, 1 + 1 = 10). Đó chính là bảng chân trị của XOR.
Máy tính trừ hai số bằng cách nào?
Phần lớn máy tính dùng số bù hai: lấy A cộng với B đã đảo hết bit, rồi cộng thêm 1. Nhờ vậy cùng một mạch cộng làm được cả phép trừ, chỉ thêm cổng XOR để đảo bit khi cần.
Tràn số là gì?
Tràn số xảy ra khi kết quả cần nhiều bit hơn số bit máy giữ. Ví dụ cộng 1011 + 0110 trong 4 bit cho 10001, bit thứ năm bị bỏ nên chỉ còn 0001. Bộ vi xử lý báo điều này qua cờ nhớ hoặc cờ tràn.
