Thiết kế mạch số dùng HDL-Chương số 2 : Thiết kế mạch luận lý tổ hợp

dce

2009

Thiết kế mạch số dùng HDL

Chương 2: Thiết kế mạch luận lý tổ hợp

Nội dung chính

i

• Luận lý tổ hợp và đại số Boole • Qui tắc tối giản đại số Boole • Biểu diễn mạch luận lý tổ hợp • Đơn giản hóa biểu thức Boole • Glitch và Hazard • Các khối cơ bản cho thiết kế luận lý

9 0 0 2 g n i r e e n g n E r e t u p m o C

Nội dung chính

i

9 0 0 2 g n i r e e n g n E r e t u p m o C

Mạch tổ hợp – mạch tuần tự

• Combinational circuit  Trạng thái ngõ ra của

Combinational

Logic

b c d

mạch tại thời điểm t chỉ phụ thuộc vào trạng thái ngõ vào tại thời điểm t

i

• Sequential circuit

 Trạng thái ngõ ra phụ

Sequential

thuộc vào “lịch sử” ngõ ra và ngõ vào hiện tại

b c

Circuit

9 0 0 2 g n i r e e n g n E r e t u p m o C

Điện áp nguồn

• GND = 0V • Năm 1980 VDD = 5V • VDD ngày càng giảm trong các bộ xử lý hiện

i

đại  VDD cao làm hư các Transistor  VDD thấp tiết kiệm năng lượng

• VDD = 3.3, 2.5, 1.8, 1.5, 1.2, 1.0,…

9 0 0 2 g n i r e e n g n E r e t u p m o C

Transistor

• nMos

i

• pMos

9 0 0 2 g n i r e e n g n E r e t u p m o C

Công nghệ CMOS

pMos Pull-up network

Input

Output

• Complementary metal- oxide semiconductor • Output của các cổng

CMOS luôn là 0 hoặc 1

i

nMos Pull-down network

Invert gate

NAND gate

NOR gate

9 0 0 2 g n i r e e n g n E r e t u p m o C

Example: O3AI

•

i

9 0 0 2 g n i r e e n g n E r e t u p m o C

Đại số Boole – Định nghĩa (1)

• Đại số Boole gồm một tập

giá trị B = {0, 1} và hai phép toán “+” và “”

• Mỗi biến Boole nhận một trong hai giá trị 0 hoặc 1 • Mỗi biến Boole a có phần

i

bù kí hiệu a’

• Một không gian nhiều chiều được bao phủ bởi một tập hợp n biến Boole được biểu diễn bằng Bn

• Mỗi điểm trong không gian

Bn được gọi là đỉnh và được biểu diễn bởi một vector nhị phân n chiều

9 0 0 2 g n i r e e n g n E r e t u p m o C

Đại số Boole – Định nghĩa (2)

• Một biến Boole được biểu diễn bằng một ký tự (a, b,

c’…)

• Một biểu thức Boole được biểu diễn bằng một chuỗi các biến và các phép toán Boole (abc’, a + b’c…)

i

• Một tích của các biến được gọi là 1 cube (abc’,

a’b…)

• Một cube chứa một hay nhiều đỉnh • Một hàm Boole đầy đủ n ngõ nhập là một ánh xạ

• Một hàm Boole không đầy đủ là ánh xạ

* don’t-care

9 0 0 2 g n i r e e n g n E r e t u p m o C

Đại số Boole – Định nghĩa (3)

• On_Set của một hàm Boole là tập hợp các

đỉnh mà tại đó hàm khẳng định (đúng) On_Set = {x:x Bn and f(x) = 1}

i

• Off_Set của một hàm Boole là tập hợp các đỉnh mà tại đó hàm không khẳng định (sai) Off_Set = {x:x Bn and f(x) = 0} • Don’t_care_Set là tập hợp các đỉnh mà tại đó

không quan tâm đến giá trị hàm

9 0 0 2 g n i r e e n g n E r e t u p m o C

Đại số Boole – Tính chất

Tính chất

Tổng các tích

Tích các tổng

a + 0 = a

a1 = a

Kết hợp với 0, 1

a + 1 = 1

a0 = 0

Giao hoán

a + b = b + a

ab = ba

i

Kết hợp

a+b+c = (a+b)+c = a+(b+c)

abc = (ab)c = a(bc)

Phân phối

a(b+c) = ab+ac a+bc = (a+b)(a+c)

a + a = a

aa = a

(a’)’ = a

9 0 0 2 g n i r e e n g n E r e t u p m o C

a + a’ = 1

aa’ = 0

Định lý De-Morgan

a’

b’

a’

b’

i

a’.b’

(a.b)’

a+b

a’+b’

(a+b)’

(a+b+c+…)’ = a’b’c’… Phủ định của một tổng bằng tích các phủ định

(abc…)’ = a’+b’+c’+… Phủ định của một tích bằng tổng các phủ định

9 0 0 2 g n i r e e n g n E r e t u p m o C

Nội dung chính

i

9 0 0 2 g n i r e e n g n E r e t u p m o C

Các qui tắc tối giản đại số Boole

i

Tổng các tích ab+ab’ = a a+ab = a ab’+b = a+b a+a’b = a+b (a+b)(a’+c) = ac + a’b ab+bc+a’c = ab+a’c

Tích các tổng (a+b)(a+b’) = a a(a+b) = a (a+b’)b = ab (a’+b)a = ab ab+a’c = (a+c)(a’+b) (a+b)(b+c)(a’+c) = (a+b)(a’+c)

9 0 0 2 g n i r e e n g n E r e t u p m o C

Phần phụ đại số của hàm Boole (co-factor)

• Một hàm boole f(x1, x2, x3,…,xn) có phần phụ

đại số với biến xi là

fxi = f(x1, x2, x3,…xi-1, 1, xi+1,…,xn)

• Phần phụ đại số với biến xi’ là

i

fxi’ = f(x1, x2, x3,…xi-1, 0, xi+1,…,xn) • Khai triển Shannon hàm f theo phần phụ đại

số của biến xi

f = xi.fxi + xi’.fxi’ = (xi + fxi’)(xi’ + fxi)

• Vi phân của một hàm boole

9 0 0 2 g n i r e e n g n E r e t u p m o C

Nội dung chính

i

9 0 0 2 g n i r e e n g n E r e t u p m o C

Biểu diễn mạch luận lý tổ hợp

i

• Biểu diễn dưới dạng sơ đồ kết nối (schematic) • Bảng sự thật (Truth table) • Biểu thức boole • BDD (binary decision diagram)

 Sử dụng trong các phần mềm thiết kế tự động  Hiệu quả và dễ tính toán hơn bảng sự thật  Hỗ trợ phát hiện hazard

9 0 0 2 g n i r e e n g n E r e t u p m o C

Các thuật ngữ (1)

• Implicant của một hàm boole một số hạng trong

biểu thức boole ở dạng tổng các tích (SOP)

• Minterm là một cube trong đó tất cả các biến đều

i

xuất hiện  abcd là một minterm của hàm f(a, b, c, d)  a’bd không là một minterm của hàm f(a, b, c, d)  Minterm được biểu diễn bằng mi, ví dụ m7 = a’bcd

• Một hàm boole ở dạng SOP được gọi là chuẩn tắc (canonical) nếu mọi cube có biểu diễn duy nhất mà trong đó các biến ở dạng khẳng định hay phủ định  abcd + a’bcd là một canonical

9 0 0 2 g n i r e e n g n E r e t u p m o C

Các thuật ngữ (2)

• Một hàm boole ở dạng POS được gọi là chuẩn tắc (canonical) nếu mọi thừa số có biểu diễn duy nhất mà trong đó các biến ở dạng khẳng định hay phủ định  (a+b+c)(a+b’+c) là một canonical

i

• Maxterm là một tổng các biến mà trong đó mỗi biến xuất hiện một lần ở dạng khẳng định hoặc phủ định • Một cube được gọi là dư thừa (redundant) nếu tập

hợp các đỉnh mà nó biểu diễn là con của tập hợp các đỉnh được biểu diễn bởi một cube khác

• Một biểu thức boole không dư thừa (irredundant) nếu không có cube nào chứa cube khác (không có cube dư thừa)

9 0 0 2 g n i r e e n g n E r e t u p m o C

Các thuật ngữ (3)

• Prime implicant

 Là implicant không thể suy ra từ implicant khác  Là một cube mà tất cả các đỉnh của nó không nằm

trong cube khác

i

• Essential prime implicant

 Là prime implicant mà không bị bao phủ (covered)

bởi bất kỳ tập hợp các implicant nào

9 0 0 2 g n i r e e n g n E r e t u p m o C

Ví dụ

• Cube ab là redundant

trong biểu thức

i

f(a,b,c) = ab + ac’ + bc • Prime implicant • Essential prime

implicant  ac’, bc

Essential PI

9 0 0 2 g n i r e e n g n E r e t u p m o C

Nội dung chính

i

9 0 0 2 g n i r e e n g n E r e t u p m o C

Đơn giản hóa biểu thức Boole

• f1(a, b, c) = abc + a’bc + abc’ + a’b’c + ab’c’ + a’b’c’

• f2(a, b, c) = bc + ab +

a’b’ + b’c’

• Một hàm boole SOP được gọi là tối giản (mininal) nếu và chỉ nếu nó chứa số lượng các tích số và các biến ít nhất

i

• Các phương pháp tối

• f1 = f2 • f1: canonical • f2: minimal

giản  Bìa Karnaugh  Quine-McClusky  Dùng các tính chất đại số

Boole

 Dùng các công cụ

(Espresso-II, mis-II…)

9 0 0 2 g n i r e e n g n E r e t u p m o C

Bìa Karnaugh (K-map)

• Dùng tối giản các mạch lên đến 5 hoặc 6 biến • Sum of product • Product of sum

i

9 0 0 2 g n i r e e n g n E r e t u p m o C

bcd và abd là prime implicant nhưng không là essential implicant Advanced Digital Design with the Verilog HDL – chapter 2

Quine McClusky

• Giải thuật thực hiện qua hai bước

 Tìm các prime implicant  Tìm bao nhỏ nhất của hàm

• Với mỗi bước sử dụng một bảng 2 chiều để

i

thực hiện giải thuật

• Ví dụ

9 0 0 2 g n i r e e n g n E r e t u p m o C

Tìm prime implicants (1)

Implicant table

0000 d(0)

0100 m(4) 1000 m(8)

i

• Điền vào cột 1 của bảng implicant các tổ hợp làm cho hàm bằng 1 và các tổ hợp don’t care • Nhóm các tổ hợp theo thứ tự tăng dần số lượng các bit 1

0101 m(5) 0110 m(6) 1001 m(9) 1010 m(10)

0111 d(7) 1101 m(13)

1111 m(15)

9 0 0 2 g n i r e e n g n E r e t u p m o C

Implicant table

0000 d(0) 

0-00 * -000 *

01-- *

0100 m(4)  1000 m(8) 

Tìm prime implicants (2) • So sánh từng cặp tổ hợp thuộc hai nhóm N bit 1 và N+1 bit 1, nếu 2 tổ hợp này khác nhau 1 biến thì thay biến này bằng dấu “_” và thêm vào cột tiếp theo • Đánh dấu ghi nhận các tổ

i

hợp đã được kết hợp

-1-1 *

010-  01-0  100- * 10-0 *

0101 m(5)  0110 m(6)  1001 m(9)  1010 m(10) 

• Tiếp tục thực hiện kết hợp trên các cột tiếp theo cho đến khi không thể sinh ra cột mới

0111 d(7)  1101 m(13) 

01-1  -101  011-  1-01 

• Tổ hợp nào không thể thực hiện kết hợp được đánh dấu (*)

1111 m(15) 

• Các tổ hợp được đánh dấu (*) là các prime implicant

9 0 0 2 g n i r e e n g n E r e t u p m o C

-111  11-1 

Tìm tập bao nhỏ nhất (1)

5

6

8

9

10

13

4 x

0_00

_000

x

100_

x

i

10_0

x

• Tạo bảng coverage table có hàng là các prime implicant, cột là các tổ hợp làm cho hàm đúng (On_Set) (không bao gồm các tổ hợp don’t care)

1_01

x

01__

x

• Đánh dấu x tại các vị trí On_Set được bao bởi prime implicant

_1_1

x

9 0 0 2 g n i r e e n g n E r e t u p m o C

Tìm tập bao nhỏ nhất (1)

5

6

8

9

10

13

4 x

0_00

_000

x

100_

x

i

• Nếu cột chỉ có 1 dấu x thì prime implicant trên hàng tương ứng là essential prime implicant và sẽ xuất hiện trong hàm tối giản cuối cùng

10_0

x

1_01

x

X

• Xóa tất cả các cột được bao bởi các essential prime implicant

01__

x

• Tìm tập hợp nhỏ các

_1_1

x

prime implicant có thể bao hết các cột còn lại

9 0 0 2 g n i r e e n g n E r e t u p m o C

Tìm tập bao nhỏ nhất (1)

5

6

8

9

10

13

4 x

0_00

x

_000

i

x

100_

x

10_0

• Độ phức tạp giải thuật tìm

x

X

1_01

các prime implicant là O(3m) (m là số biến)

• Độ phức tạp giải thuật tìm

01__

x

tập bao nhỏ nhất là O(2n) (n số prime implicant)

x

_1_1

x

9 0 0 2 g n i r e e n g n E r e t u p m o C

Nội dung chính

i

9 0 0 2 g n i r e e n g n E r e t u p m o C

Glitches và Hazards

• Glitches là những sự chuyển trạng thái không mong muốn ở ngõ ra của một mạch kết hợp trong điều kiện ngõ vào không làm thay đổi ngõ ra

i

• Một mạch có thể xảy ra glitches khi đưa tín hiệu ngõ vào xác định được gọi là có hazard • Không ảnh hưởng nhiều trên mạch đồng bộ • Là vấn đề cần giải quyết trên mạch bất đồng

bộ

9 0 0 2 g n i r e e n g n E r e t u p m o C

Hazard tĩnh

• Ngõ ra thay đổi trên thực tế trong khi theo lý thuyết

là không thay đổi

• Xảy ra do sự trể lan truyền • Hazard có xảy ra hay không tùy thuộc vào các mẫu

i

tín hiệu ngõ vào

9 0 0 2 g n i r e e n g n E r e t u p m o C

Loại bỏ Hazard tĩnh

Có Hazard

• Thêm vào các cube dư thừa (hazard cover cube)

• Giả sử tín hiệu ngõ vào

chỉ thay đổi 1 bit

i

Không Hazard

9 0 0 2 g n i r e e n g n E r e t u p m o C

Hazard động

• Theo lý thuyết sự thay đổi trên ngõ vào chỉ gây ra một thay

đổi ngõ ra, nhưng thực tế có hai hay nhiều sự thay đổi ngõ ra trước khi đạt đến giá trị mong muốn

• Là kết quả của nhiều hazard tĩnh trên mạch đa mức

(multilevel circuit)

i

• Khó để loại bỏ • Nếu mạch không có hazard tĩnh thì không có hazard động

9 0 0 2 g n i r e e n g n E r e t u p m o C

Loại bỏ hazard động

• Theo các bước

 Chuyển mạch nhiều mức

về mạch hai mức  Tìm và loại bỏ tất cả

hazard tĩnh

i

9 0 0 2 g n i r e e n g n E r e t u p m o C

Hazard – Tổng kết

i

9 0 0 2 g n i r e e n g n E r e t u p m o C

Nội dung chính

i

9 0 0 2 g n i r e e n g n E r e t u p m o C

Cấu trúc NAND-NOR

• Trong kỹ thuật CMOS, cổng AND và OR

không được hiện thực hiệu quả bằng NAND, NOR

• Chuyển mạch dạng SOP về NAND và Invert

i

 Thay các cổng AND bằng NAND  Đặt các invert trước các ngõ vào cổng OR  Thay cổng OR có các invert ở ngõ vào bằng

NAND

• Chuyển mạch dạng POS về NOR và Invert

 Tương tự như trên

9 0 0 2 g n i r e e n g n E r e t u p m o C

Ví dụ

i

NAND/Invert structure of an SOP expression

9 0 0 2 g n i r e e n g n E r e t u p m o C

Multiplexers

• Chọn dữ liệu từ một trong nhiều ngõ nhập để đưa ra ngõ ra • Multiplexers có thể dùng để hiện thực các mạch tổ hợp

i

Gate level schematic

y_out = sel’.a + sel.b

Schematic symbol

Data_out = Data_in[address[k]]

9 0 0 2 g n i r e e n g n E r e t u p m o C

Demultiplexers

• Ngược lại với multiplexer • Multiplexer và demultiplexer không làm biến đổi dữ liệu

i

Schematic symbol

Data_out[address[k]] = Data_in

9 0 0 2 g n i r e e n g n E r e t u p m o C

Encoders

• Biến đổi dữ liệu ngõ vào và đưa ra ngõ ra • Ánh xạ 1-1 giữa dữ liệu ngõ vào và dữ liệu ngõ ra • Kích thước dữ liệu nhập lớn hơn kích thước dữ liệu xuất • Thông thường chỉ một bit ở ngõ nhập “khẳng định” ở một thời điểm • Priority encoder cho phép nhiều bit ở ngõ nhập đồng thời “khẳng