Cơ sở toán họccho các hệ thống số là đại số Boolean
(Boolean algebra)
George Boole giới thiệu vào năm 1854
Tương tự các hệ đại số khác, được xây dựng thông qua
việc xác định nghĩa những vấn đề cơ bản sau:
Miền(domain), là tập hợp (set) các phần tử(element)
mà trên đó định nghĩa nên hệ đại số
Các phép toán(operation) thực hiện được trên miền
Các định đề (postulate), hay tiên đề (axiom) được
công nhận không qua chứng minh
Tập các hệ quả(set of consequences) được suy ra từ
định đề, định lý(theorem), định luật (law) hay luật(rule)
74 trang |
Chia sẻ: lylyngoc | Lượt xem: 3137 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Đại số Boolean và cổng luận lý, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Đại số Boolean và
cổng luận lý
Bộ môn Kỹ thuật máy tính
Bùi Văn Hiếu
bvhieu@cse.hcmut.edu.vn
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 2
Đại số Boolean
Cơ sở toán học cho các hệ thống số là đại số Boolean
(Boolean algebra)
George Boole giới thiệu vào năm 1854
Tương tự các hệ đại số khác, được xây dựng thông qua
việc xác định nghĩa những vấn đề cơ bản sau:
Miền (domain), là tập hợp (set) các phần tử (element)
mà trên đó định nghĩa nên hệ đại số
Các phép toán (operation) thực hiện được trên miền
Các định đề (postulate), hay tiên đề (axiom) được
công nhận không qua chứng minh
Tập các hệ quả (set of consequences) được suy ra từ
định đề, định lý (theorem), định luật (law) hay luật(rule)
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 3
Định đề Huntington
1. Tính đóng (closure): tồn tại miền B với ít nhất 2 phần
tử phân biệt và 2 phép toán (+) và (•) sao cho:
Nếu x và y là các phần tử thuộc B thì (x + y),
(x•y) cũng là 1 phần tử thuộc B
Phép toán (+) được gọi là phép cộng luận lý
(logical addition)
Phép toán (• ) được gọi là phép nhân luận lý
(logical multiplication)
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 4
Định đề Huntington (tt)
2. Phần tử đồng nhất (identity elements)
Nếu x là một phần tử thuộc miền B thì
Tồn tại một phần tử 0 thuộc B, gọi là phần tử đồng
nhất với phép toán (+ ), thỏa mãn tính chất
x + 0 = x
Tồn tại một phần tử 1 thuộc B, gọi là phần tử đồng
nhất với phép toán (•), thỏa mãn tính chất
x • 1 = x
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Định đề Huntington (tt)
3. Tính giao hoán (commutative law)
x + y = y + x
x • y = y • x
4. Tính phân phối (distributive law)
x • (y + z) = (x • y) + (x • z)
x + (y • z) = (x + y) • (x + z)
5. Bù (complementation)
Nếu x là 1 phần tử trong miền B, tồn tại một phần tử
khác gọi là x’, là phần tử bù của x thỏa mãn:
x + x’ = 1
và
x • x’ = 0
5
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 6
Tính đối ngẫu (duality)
Quan sát các định đề Hungtinton, ta thấy chúng mang
tính đối xứng (symmetry) tức là các định đề xuất hiện
theo cặp
Mỗi định đề trong 1 cặp có thể được xây dựng từ định đề
còn lại bằng cách
Hoán đổi các phép toán 2 ngôi
Hoán đổi các phần tử đồng nhất
Như vậy đại số Boolean mang tính đối ngẫu
Phép toán (+) và (•) đối ngẫu
Phần tử đồng nhất 0 và 1 đối ngẫu
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 7
Các định lý cơ bản (fundamental
theorems)
Các định lý được chứng minh từ các định đề Huntington
và các định đề đối ngẫu theo 2 phương pháp
Phương pháp phản chứng (contradiction)
Giả sử kết quả đối ngược là đúng
Chứng minh mâu thuẫn với sự thật
Phương pháp quy nạp (induction)
Chứng minh định luật đúng với trường hợp k = 1
Giả sử định luật đúng vơí trương hợp k = n
Chứng minh định luật đúng với k = n +1
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Các định lý cơ bản (tt)
Định lý 1. (Null Law)
x + 1 = 1
x • 0 = 0
Định lý 2. (Involution)
(x’ )’ = x
Định lý 3. (Idempotency)
x + x = x
x • x = x
Định lý 4. (Absorption)
x + (x • y) = x
x • (x + y) = x
8
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 9
Các định lý cơ bản (tt)
Định lý 5. (Simplification)
x + x’• y = x + y và x• (x’ + y) = x•y
Định lý 6. (Associative Law)
x + (y + z) = (x + y) + z = x + y + z
x • (y • z) = (x • y) • z = x • y • z
Định lý 7. (Consensus)
(x • y) + (x’ • z) + (y • z) = (x • y) + (x’ • z)
(x + y) • (x’ + z) • (y + z) = (x + y) • (x’ + z)
Định lý 8. (De Morgan’s Law)
(x + y)’ = x’ • y’
(x • y)’ = x’ + y’
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 10
Đại số chuyển mạch (switching
algebra)
Đối với đại số Boolean, miền không bị giới hạn (không
giới hạn số lượng phần tử trong miền)
Ta chỉ khảo sát đại số Boolean giới hạn 2 phần tử
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Đại số chuyển mạch (tt)
Năm 1937, Claude Shannon hiện thực đại số Boolean 2
phần tử bằng mạch các chuyển mạch (circuit of switches)
Chuyển mạch là thiết bị có 2 vị trí: tắt (off) hay mở (on)
2 vị trí này biểu diễn cho 0 hay 1
Đại số Boolean 2 phần tử được gọi là đại số chuyển
mạch
Các phần tử đồng nhất được gọi là các hằng chuyển
mạch (switching constant)
Các biến (variable) biểu diễn các hằng chuyển mạch
được gọi là các biến chuyển mạch (switching variable)
hay tín hiệu (signal)
11
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 12
Các phép toán chuyển mạch
Đại số chuyển mạch sử
dụng các phép toán trong
luận lý mệnh đề với tên gọi
khác
Phép toán AND: tương
đương với phép nhân luận
lý
Phép toán OR: tương
đương với phép cộng luận
lý
Phép toán NOT: tương
đương với phép bù luận lý
Bảng sự thật
x y x y x + y x’
0 0 0 0 1
0 1 0 1 1
1 0 0 1 0
1 1 1 1 0
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 13
Các phép toán chuyển mạch (tt)
Các phép toán chuyển mạch có thể được hiện thực bởi
mạch phần cứng
Bảng sự thật có thể sử dụng như 1 công cụ dùng để xác
minh quan hệ giữa các phép toán chuyển mạch
Vd: định lý De Morgan (x + y)’ = x’ y’
x y x’ y’ x + y (x + y)’ x’ y’
0 0 1 1 0 1 1
0 1 1 0 1 0 0
1 0 0 1 1 0 0
1 1 0 0 1 0 0
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 13
Các phép toán chuyển mạch (tt)
Các phép toán chuyển mạch có thể được hiện thực bởi
mạch phần cứng
Bảng sự thật có thể sử dụng như 1 công cụ dùng để xác
minh quan hệ giữa các phép toán chuyển mạch
Vd: định lý De Morgan (x + y)’ = x’ y’
x y x’ y’ x + y (x + y)’ x’ y’
0 0 1 1 0 1 1
0 1 1 0 1 0 0
1 0 0 1 1 0 0
1 1 0 0 1 0 0
Điều gì xảy ra nếu số
lượng tín hiệu là rất lớn ?
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Biểu thức chuyển mạch
Biểu thức chuyển mạch (switching expression) là một
quan hệ hữu hạn giữa các hằng, biến, và các phép toán
y + 1
xx’ + x
z (x + y’)’
(x + yz)(x + y’) + (x + y)’
Biến hay bù của biến được gọi chung là literal
Quy ước:
Không cần ghi kí hiệu của phép nhân
Phép nhân thực hiện trước phép cộng
14
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 15
Biểu thức chuyển mạch
Một biểu thức có thể được chuyển thành nhiều dạng
tương đương bằng cách sử dụng các luật Boolean
E = (x + yz)(x + y’) + (x + y)’
E1 = xx + xy’ + xyz + yy’z + x’y’
E2 = x + x(y’ + yz) + x’y’
E3 = x + x’y’
E4 = x + y’
Tại sao phải biến đổi các biểu thức ?
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Sự dư thừa (redundant)
Một biểu thức gọi là dư thừa nếu nó có chứa
Literal lặp: xx hay x+x
Biến và bù của biến: xx’ hay x+x’
Hằng: 0 hay 1
Các thành phần dư thừa có thể loại bỏ khỏi biểu thức
Các thành phần thừa trong biểu thức không cần hiện
thực trong phần cứng
16
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 17
Dạng chính tắc (canonic form)
Một biểu thức n biến luôn có thể được biểu diễn dưới 2 dạng
Dạng tổng các tích (sum-of-product hay s-o-p): biểu thức
được biểu diễn dưới dạng tổng (sum) các toán hạng (term),
mỗi toán hạng là tích (product) của các literal
E = x y + x y’ z + x’ y z’
Dạng tích các tổng (product-of-sum hay p-o-s): biểu thức
được biểu diễn dưới dạng tích các toán hạng, mỗi toán hạng
là tổng của các literal
E = ( x + y ) ( x + y’ + z ) ( x’ + y + z’ )
Dạng chính tắc: biểu thức n biến dạng s-o-p hay p-o-s có đặc
điểm mỗi toán hạng của nó có đúng n literal và không chứa các
literal thừa
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 18
Minterm, Maxterm
Luôn có thể biến đổi một s-o-p (hay p-o-s) không chính
tắc (noncanonic) về dạng chính tắc
Vd: E = xy’ + x’y + xz + yz
= xy’(z + z’) + x’y(z + z’) + xz(y + y’) + yz(x + x’)
=
xy’z + xy’z’ + x’yz + x’yz’ + xyz + xy’z
+ xyz + x’yz
=
xy’z + xy’z’ + x’yz + x’yz’ + xyz
Minterm: một tích không dư thừa các literal của dạng
chính tắc
Maxterm: một tổng không dư thừa các literal của dạng
chính tắc
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Định lý De Morgan tổng quát
(x1 + x2 + … + xn)’
=
x1’x2’ … xn’
(x1x2 … xn)’
=
x1’ + x2’ + … + xn’
E’(x1, x2, x3, ..., xn, +,•) = E(x1’, x2’, x3’, ..., xn’, •, +)
19
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 20
Hàm chuyển mạch
2 biểu thức (x + x’ y’) và (x + y’) có tương đương ?
Hàm chuyển mạch (switching function) là một phép gán
xác định và duy nhất của những giá trị 0 và 1 cho tất cả
các tổ hợp giá trị của các biến thành phần
Số lượng hàm chuyển mạch của n biến là
BT: SV liệt kê các 16 hàm chuyển mạch với 2 biến.
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 20
Hàm chuyển mạch
2 biểu thức (x + x’ y’) và (x + y’) có tương đương ?
Hàm chuyển mạch (switching function) là một phép gán
xác định và duy nhất của những giá trị 0 và 1 cho tất cả
các tổ hợp giá trị của các biến thành phần
Số lượng hàm chuyển mạch của n biến là
BT: SV liệt kê các 16 hàm chuyển mạch với 2 biến.
x y x’ y’ x’ y’ x + x’ y’ x + y’
0 0 1 1 1 1 1
0 1 1 0 0 0 0
1 0 0 1 0 1 1
1 1 0 0 0 1 1
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Hàm chuyển mạch (tt)
Sự khác nhau giữa hàm và biểu thức chuyển mạch ?
Nếu mọi giá trị của biểu thức trùng với giá trị của hàm,
ta gọi biểu thức biểu diễn (represent) hàm
Tồn tại nhiều biểu thức cùng biểu diễn cho 1 hàm
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Hàm chuyển mạch (tt)
Biểu diễn hàm dưới dạng danh sách minterm/maxterm
Chuyển đổi dạng chuẩn s-o-p sang p-o-s
Xử dụng De Morgan cho phần bù của các minterm
không có trong biểu thức
22
Decimal x y z Maxterms f Minterms
0 0 0 0 x + y + z 0 x’ y’ z’
1 0 0 1 x + y + z’ 0 x’ y’ z
2 0 1 0 x + y’ + z 1 x’ y z’
3 0 1 1 x + y’ + z’ 1 x’ y z
4 1 0 0 x’ + y + z 1 x y’ z’
5 1 0 1 x’ + y + z’ 1 x y’ z
6 1 1 0 x’ + y’ + z 0 x y z’
7 1 1 1 x’ + y’ + z’ 1 x y z
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 23
Hàm chuyển mạch (tt)
Một hàm chuyển mạch bất kì đều có biểu thức dạng
chuẩn s-o-p (p-o-s) tương đương hay không ?
Định lý Shannon mở rộng:
Cho hàm f(x1, x2, ..., xn) bất kì. Thì
f(x1, x2, ..., xn) = x1.f(1, x2, ..., xn) + x1’.f(0, x2, ..., xn)
Một hàm chuyển mạch bất kỳ n biến luôn có thể được
biểu diễn dưới dạng s-o-p n literal, mỗi literal ứng với 1
biến
Dạng p-o-s: sv tự đọc
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Phép toán NAND (NOT AND) (xy)’ = x’ + y’
Phép toán NOR (NOT OR) (x + y)’ = x’.y’
Phép toán XOR (Exclusive OR) x 㱾 y = x’y + y’x
Phép toán XNOR (NOT XOR) (x 㱾 y)’ = xy + x’y’
24
Phép toán chuyển mạch khác
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Phép toán NAND (NOT AND) (xy)’ = x’ + y’
Phép toán NOR (NOT OR) (x + y)’ = x’.y’
Phép toán XOR (Exclusive OR) x 㱾 y = x’y + y’x
Phép toán XNOR (NOT XOR) (x 㱾 y)’ = xy + x’y’
24
Phép toán chuyển mạch khác
Biến NAND NOR Ex. OR XNOR
x y (x . y)’ (x + y)’ x 㱾 y (x 㱾 y)’
0 0 1 1 0 1
0 1 1 0 1 0
1 0 1 0 1 0
1 1 0 0 0 1
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 25
Tập phổ dụng của các phép toán
Một tập các phép toán được gọi là phổ dụng (universal)
nếu mọi hàm chuyển mạch đều có thể được biểu diễn chỉ
cần các phép toán của tập trên
Tập
{ NOT , AND , OR } có là tập phổ dụng ?
Tập
{ NOT , AND } có là tập phổ dụng ?
Tập
{ NOT , OR } có là tập phổ dụng ?
Tập
{ NAND } có là tập phổ dụng ?
Tập
{ NOR } có là tập phổ dụng ?
Tập
. . .
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 26
Cổng luận lý
Để đại số chuyển mạch có thể thực hiện các công việc
trong đời thật, cần phải có:
Thiết bị vật lý thực hiệc các phép toán chuyển mạch
Tín hiệu vật lý (điện áp, …) thay thế cho các biến
chuyển mạch
Cổng (gate) là tên chung dùng để gọi các thiết bị vật lý
thực hiện các phép toán chuyển mạch với độ chính xác
(accuracy) và thời gian trễ (delay) chấp nhận được
Mỗi cổng được biểu diễn bởi 1 biểu tượng (schematic
symbol) cùng với 1 số chân (pin, terminal) tượng trưng
cho các biến chuyển mạch
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 26
Cổng luận lý
Để đại số chuyển mạch có thể thực hiện các công việc
trong đời thật, cần phải có:
Thiết bị vật lý thực hiệc các phép toán chuyển mạch
Tín hiệu vật lý (điện áp, …) thay thế cho các biến
chuyển mạch
Cổng (gate) là tên chung dùng để gọi các thiết bị vật lý
thực hiện các phép toán chuyển mạch với độ chính xác
(accuracy) và thời gian trễ (delay) chấp nhận được
Mỗi cổng được biểu diễn bởi 1 biểu tượng (schematic
symbol) cùng với 1 số chân (pin, terminal) tượng trưng
cho các biến chuyển mạch
Một biểu thức chuyển mạch bất kỳ luôn có
thể được hiện thực trong đời thật bằng
cách kết nối các cổng lại với nhau (mạch
luận lý - logic circuit - hay mạch chuyển
mạch - switching circuit)
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 27
Biểu tượng của các cổng luận lý
XNOR
XORNOROR
NANDANDNOT
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 28
Một số dạng tương đương
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 28
Một số dạng tương đương
Kết luận về chuyển đổi cổng
AND và cổng OR ?
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 29
Thí dụ
Biểu thức chuyển mạch
x = A’BC(A+D)’
Mạch luận lý
Bảng sự thật ?
Mạch tương đương ?
A
B
C
D
x
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 29
Thí dụ
Biểu thức chuyển mạch
x = A’BC(A+D)’
Mạch luận lý
Bảng sự thật ?
Mạch tương đương ?
D C B A x
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
A
B
C
D
x
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 30
Luận lý dương, âm & hỗn tạp
Giá trị luận lý 0, 1 được biểu diễn trong thế giới thật bởi
các tín hiệu vật lý (thường là mức điện áp)
Tùy theo hệ thống, giá trị cụ thể của các mức điện áp có
thể khác nhau, nhưng luôn tồn tại 1 mức điện áp cao hơn
mức còn lại
High (H) và Low (L)
Hai cách thể hiện mối tương quan giữa giá trị luận lý và
mức điện áp
Luận lý dương (positive logic): 1-H, 0-L
Luận lý âm (negative logic): 1-L, 0-H
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 31
Tích cực cao – Tích cực thấp
Hai trạng thái hoạt động của thiết bị là tích cực (activity)
và không tích cực (inactivity)
Xét các thí dụ đối với điện thoại, đèn, động cơ, v.v…
Do thói quen, qui ước tích cực ứng với mức luận lý 1
còn không tích cực ứng với mức luận lý 0
Tích cực cao (active high)
Tích cực → Luận lý 1 → Mức điện áp cao
Tích cực thấp (active low)
Tích cực → Luận lý 1 → mức điện áp thấp
Thực tế đôi khi không tuân theo qui ước !
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 32
Một số vần đề trong thực hành
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 32
Một số vần đề trong thực hành
Cổng luận lý được thiết kế và chế
tạo phụ thuộc vào công nghệ tại
thời điểm hiện hành
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 32
Một số vần đề trong thực hành
Cổng luận lý được thiết kế và chế
tạo phụ thuộc vào công nghệ tại
thời điểm hiện hành
Các mạch chuyển mạch đầu tiên
được chế tạo với các thiết bị cơ
(switch và relay)
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 32
Một số vần đề trong thực hành
Cổng luận lý được thiết kế và chế
tạo phụ thuộc vào công nghệ tại
thời điểm hiện hành
Các mạch chuyển mạch đầu tiên
được chế tạo với các thiết bị cơ
(switch và relay)
Các thiết bị chuyển mạch đầu tiên
mang tên “cổng” được thiết kế với
các đèn điện tử (vacuum tube)
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 32
Một số vần đề trong thực hành
Cổng luận lý được thiết kế và chế
tạo phụ thuộc vào công nghệ tại
thời điểm hiện hành
Các mạch chuyển mạch đầu tiên
được chế tạo với các thiết bị cơ
(switch và relay)
Các thiết bị chuyển mạch đầu tiên
mang tên “cổng” được thiết kế với
các đèn điện tử (vacuum tube)
• Đèn điện tử, sau đó, được thay thế bởi
diode bán dẫn, transistor lưỡng cực, rồi
đến MOSFET
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 32
Một số vần đề trong thực hành
Cổng luận lý được thiết kế và chế
tạo phụ thuộc vào công nghệ tại
thời điểm hiện hành
Các mạch chuyển mạch đầu tiên
được chế tạo với các thiết bị cơ
(switch và relay)
Các thiết bị chuyển mạch đầu tiên
mang tên “cổng” được thiết kế với
các đèn điện tử (vacuum tube)
• Đèn điện tử, sau đó, được thay thế bởi
diode bán dẫn, transistor lưỡng cực, rồi
đến MOSFET
• Mỗi cổng được chế tạo từ các linh kiện
rời (discrete component)
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 32
Một số vần đề trong thực hành
Cổng luận lý được thiết kế và chế
tạo phụ thuộc vào công nghệ tại
thời điểm hiện hành
Các mạch chuyển mạch đầu tiên
được chế tạo với các thiết bị cơ
(switch và relay)
Các thiết bị chuyển mạch đầu tiên
mang tên “cổng” được thiết kế với
các đèn điện tử (vacuum tube)
• Đèn điện tử, sau đó, được thay thế bởi
diode bán dẫn, transistor lưỡng cực, rồi
đến MOSFET
• Mỗi cổng được chế tạo từ các linh kiện
rời (discrete component)
Sự ra đời của mạch tích hợp (IC –
Integrated circuit) hay vi mạch cho
phép chế tạo 1/nhiều cổng trong 1
phần tử linh kiện
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 32
Một số vần đề trong thực hành
Cổng luận lý được thiết kế và chế
tạo phụ thuộc vào công nghệ tại
thời điểm hiện hành
Các mạch chuyển mạch đầu tiên
được chế tạo với các thiết bị cơ
(switch và relay)
Các thiết bị chuyển mạch đầu tiên
mang tên “cổng” được thiết kế với
các đèn điện tử (vacuum tube)
Độ tích hợp của các vi mạch
• Đèn điện tử, sau đó, được thay thế bởi
diode bán dẫn, transistor lưỡng cực, rồi
đến MOSFET
• Mỗi cổng được chế tạo từ các linh kiện
rời (discrete component)
Sự ra đời của mạch tích hợp (IC –
Integrated circuit) hay vi mạch cho
phép chế tạo 1/nhiều cổng trong 1
phần tử linh kiện
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 32
Một số vần đề trong thực hành
Cổng luận lý được thiết kế và chế
tạo phụ thuộc vào công nghệ tại
thời điểm hiện hành
Các mạch chuyển mạch đầu tiên
được chế tạo với các thiết bị cơ
(switch và relay)
Các thiết bị chuyển mạch đầu tiên
mang tên “cổng” được thiết kế với
các đèn điện tử (vacuum tube)
Độ tích hợp của các vi mạch
• Đèn điện tử, sau đó, được thay thế bởi
diode bán dẫn, transistor lưỡng cực, rồi
đến MOSFET
• Mỗi cổng được chế tạo từ các linh kiện
rời (discrete component)
Sự ra đời của mạch tích hợp (IC –
Integrated circuit) hay vi mạch cho
phép chế tạo 1/nhiều cổng trong 1
phần tử linh kiện
SSI Small-scale integration < 12 cổng
MSI Medium-scale integration 12 ÷ 99 cổng
LSI Large-scale integration 100 ÷ 9.999 cổng
VLSI Very large-scale integration 10.000 ÷ 99.999 cổng
ULSI Ultra large-scale integration ≥ 100.000 cổng
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 33
Các họ luận lý
Một tập hợp các cổng luận lý sử dụng cùng 1 công nghệ
chế tạo được gọi là 1 họ luận lý (logic family)
RTL (resistor-transistor logic) xuất hiện đầu tiên, nay đã
lỗi thời
ECL (emitter-coupled logic): hãng Motorola
TTL (transistor-transistor logic): hãng Texas Instrument.
Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 33
Các họ luận lý
Một tập hợp các cổng luận lý sử dụng cùng 1 công nghệ
chế tạo được gọi là 1 họ luận lý (logic family)
RTL (resistor-transistor logic) xuất hiện đầu tiên, nay đã
lỗi thời
ECL (emitter-coupled logic): hãng Motorola
TTL (transistor-transistor logic): hãng Texas Instrument.
Designation Name Power Speed
LS Low-power Schottky Low Slow
ALS Advanced LS Low Moderate
S Schottky Medium Fast
AS Advanced Schottky Medium Fast
L Low-power Low Moderate
F Fast High Very fast