Mạch kỹ thuật số - Phương pháp K-Map
Trong các chương trước, chúng ta đã đơn giản hóa các hàm Boolean bằng cách sử dụng các định đề và định lý Boolean. Đây là một quá trình tốn thời gian và chúng ta phải viết lại các biểu thức đã đơn giản hóa sau mỗi bước.
Để vượt qua khó khăn này, Karnaughđã giới thiệu một phương pháp đơn giản hóa các hàm Boolean một cách dễ dàng. Phương pháp này được gọi là phương pháp bản đồ Karnaugh hoặc phương pháp bản đồ K. Nó là một phương pháp đồ họa, bao gồm 2 n ô cho các biến 'n'. Các ô liền kề chỉ khác nhau ở vị trí bit đơn.
K-Maps cho 2 đến 5 biến
Phương pháp K-Map phù hợp nhất để giảm thiểu các hàm Boolean của 2 biến thành 5 biến. Bây giờ, chúng ta hãy thảo luận về K-Maps cho 2 đến 5 biến từng biến một.
2 Bản đồ K biến
Số ô trong bản đồ K 2 biến là bốn, vì số biến là hai. Hình sau cho thấy2 variable K-Map.
Chỉ có một khả năng nhóm 4 số hạng min liền kề.
Các tổ hợp có thể có của nhóm 2 số hạng nhỏ nhất liền kề là {(m 0 , m 1 ), (m 2 , m 3 ), (m 0 , m 2 ) và (m 1 , m 3 )}.
3 Bản đồ K biến
Số ô trong 3 biến K-map là tám, vì số biến là ba. Hình sau cho thấy3 variable K-Map.
Chỉ có một khả năng nhóm 8 số hạng min liền kề.
Các tổ hợp có thể có của nhóm 4 số hạng nhỏ nhất liền kề là {(m 0 , m 1 , m 3 , m 2 ), (m 4 , m 5 , m 7 , m 6 ), (m 0 , m 1 , m 4 , m 5 ), (m 1 , m 3 , m 5 , m 7 ), (m 3 , m 2 , m 7 , m 6 ) và (m 2 , m 0 , m 6 , m 4 )}.
Các tổ hợp có thể có của nhóm 2 số hạng nhỏ nhất liền kề là {(m 0 , m 1 ), (m 1 , m 3 ), (m 3 , m 2 ), (m 2 , m 0 ), (m 4 , m 5 ) , (m 5 , m 7 ), (m 7 , m 6 ), (m 6 , m 4 ), (m 0 , m 4 ), (m 1 , m 5 ), (m 3 , m 7 ) và ( m 2 , m 6 )}.
Nếu x = 0 thì ánh xạ K 3 biến trở thành ánh xạ K 2 biến.
4 Bản đồ K biến
Số ô trong 4 biến K-map là mười sáu, vì số biến là bốn. Hình sau cho thấy4 variable K-Map.
Chỉ có một khả năng nhóm 16 số hạng min liền kề.
Gọi R 1 , R 2 , R 3 và R 4 lần lượt đại diện cho các số hạng tối thiểu của hàng đầu tiên, hàng thứ hai, hàng thứ ba và hàng thứ tư. Tương tự, C 1 , C 2 , C 3 và C 4 lần lượt thể hiện các số hạng tối thiểu của cột đầu tiên, cột thứ hai, cột thứ ba và cột thứ tư. Các kết hợp có thể có của nhóm 8 số hạng tối thiểu liền kề là {(R 1 , R 2 ), (R 2 , R 3 ), (R 3 , R 4 ), (R 4 , R 1 ), (C 1 , C 2 ) , (C 2 , C 3 ), (C 3 , C 4 ), (C 4 , C 1 )}.
Nếu w = 0, thì bản đồ K 4 biến trở thành bản đồ K 3 biến.
5 Bản đồ K biến
Số ô trong 5 biến K-map là ba mươi hai, vì số biến là 5. Hình sau cho thấy 5 variable K-Map.
Chỉ có một khả năng nhóm 32 số hạng min liền kề.
Có hai khả năng nhóm 16 số hạng nhỏ nhất liền kề. tức là, nhóm các số hạng nhỏ nhất từ m 0 đến m 15 và m 16 đến m 31 .
Nếu v = 0, thì bản đồ K 5 biến trở thành bản đồ K 4 biến.
Trong tất cả các bản đồ K ở trên, chúng tôi chỉ sử dụng ký hiệu thuật ngữ tối thiểu. Tương tự, bạn có thể sử dụng riêng ký hiệu điều khoản Max.
Giảm thiểu các hàm Boolean bằng K-Maps
Nếu chúng ta xem xét sự kết hợp của các đầu vào mà hàm Boolean là '1', thì chúng ta sẽ nhận được hàm Boolean, trong đó standard sum of products sau khi đơn giản hóa K-map.
Tương tự, nếu chúng ta xem xét sự kết hợp của các đầu vào mà hàm Boolean là '0', thì chúng ta sẽ nhận được hàm Boolean, trong đó standard product of sums sau khi đơn giản hóa K-map.
Làm theo những rules for simplifying K-maps để có được dạng tổng sản phẩm tiêu chuẩn.
Chọn K-map tương ứng dựa trên số lượng biến có trong hàm Boolean.
Nếu hàm Boolean được cho dưới dạng tổng của các số hạng min, thì hãy đặt chúng tại các ô số hạng min tương ứng trong K-map. Nếu hàm Boolean được cho dưới dạng tổng của các sản phẩm, thì hãy đặt các sản phẩm đó vào tất cả các ô có thể có của bản đồ K mà các điều khoản sản phẩm đã cho là hợp lệ.
Kiểm tra khả năng nhóm số lượng tối đa những cái liền kề. Nó phải là quyền hạn của hai. Bắt đầu từ công suất cao nhất của hai và tối đa là công suất nhỏ nhất của hai. Công suất cao nhất bằng số biến được xem xét trong bản đồ K và công suất nhỏ nhất bằng không.
Mỗi nhóm sẽ cung cấp một thuật ngữ theo nghĩa đen hoặc một sản phẩm. Nó được biết đến nhưprime implicant. Hàm ý chính được cho làessential prime implicant, nếu ít nhất đơn '1' không được bao phủ bởi bất kỳ nhóm nào khác mà chỉ bao gồm nhóm đó.
Ghi lại tất cả các hàm nguyên tố và hàm ý nguyên tố cần thiết. Hàm Boolean đơn giản chứa tất cả các hàm nguyên tố cần thiết và chỉ các hàm nguyên tố bắt buộc.
Note 1 - Nếu đầu ra không được xác định cho một số kết hợp đầu vào, thì các giá trị đầu ra đó sẽ được biểu diễn bằng don’t care symbol ‘x’. Điều đó có nghĩa là, chúng ta có thể coi chúng là '0' hoặc '1'.
Note 2- Nếu thuật ngữ không quan tâm cũng xuất hiện, thì địa điểm không quan tâm 'x' trong các ô tương ứng của K-map. Chỉ xem xét dấu 'x' không quan tâm hữu ích cho việc nhóm số lượng tối đa những cái liền kề. Trong những trường hợp đó, hãy coi giá trị không quan tâm là '1'.
Thí dụ
Hãy để chúng tôi simplify hàm Boolean sau đây, f(W, X, Y, Z)= WX’Y’ + WY + W’YZ’ sử dụng K-map.
Hàm Boolean đã cho có dạng tổng các sản phẩm. Nó có 4 biến W, X, Y & Z. Vì vậy, chúng tôi yêu cầu4 variable K-map. Các4 variable K-map với những người tương ứng với các điều khoản sản phẩm nhất định được hiển thị trong hình sau.
Ở đây, 1s được đặt trong các ô sau đây của K-map.
Các ô chung cho giao điểm của Hàng 4 và cột 1 & 2 tương ứng với cụm từ sản phẩm, WX’Y’.
Các ô chung cho giao điểm của Hàng 3 & 4 và cột 3 & 4 tương ứng với thuật ngữ sản phẩm, WY.
Các ô chung cho giao điểm của Hàng 1 & 2 và cột 4 tương ứng với thuật ngữ sản phẩm, W’YZ’.
Không có khả năng nhóm 16 cái liền kề hoặc 8 cái liền kề. Có ba khả năng nhóm 4 cái liền nhau. Sau ba nhóm này, không còn một nhóm nào là chưa được nhóm. Vì vậy, chúng ta không cần phải kiểm tra nhóm của 2 cái liền kề. Các4 variable K-map với ba cái này groupings được hiển thị trong hình sau.
Ở đây, chúng tôi có ba hàm ý chính WX ', WY & YZ'. Tất cả những hàm ý chính làessential bởi vì những lý do sau đây.
Hai cái (m8 & m9)của nhóm hàng thứ tư không được bao phủ bởi bất kỳ nhóm nào khác. Chỉ nhóm hàng thứ tư bao gồm hai hàng đó.
Người độc thân (m15)của nhóm hình vuông không bị bao phủ bởi bất kỳ nhóm nào khác. Chỉ nhóm hình vuông mới bao gồm nhóm đó.
Hai cái (m2 & m6)của nhóm cột thứ tư không được bao gồm bởi bất kỳ nhóm nào khác. Chỉ nhóm cột thứ tư bao gồm hai nhóm đó.
Do đó, simplified Boolean function Là
f = WX’ + WY + YZ’
Làm theo những rules for simplifying K-maps để có được sản phẩm tiêu chuẩn của dạng tổng.
Chọn K-map tương ứng dựa trên số lượng biến có trong hàm Boolean.
Nếu hàm Boolean được đưa ra dưới dạng tích của dạng số hạng Max, thì hãy đặt các số 0 tại các ô số hạng Max tương ứng trong K-map. Nếu hàm Boolean được cho dưới dạng tích của dạng tổng, thì hãy đặt các số 0 vào tất cả các ô có thể có của ánh xạ K mà các số hạng tổng đã cho là hợp lệ.
Kiểm tra khả năng nhóm số lượng số 0 liền kề tối đa. Nó phải là quyền hạn của hai. Bắt đầu từ công suất cao nhất của hai và công suất nhỏ nhất là hai. Công suất cao nhất bằng số biến được xem xét trong bản đồ K và công suất nhỏ nhất bằng không.
Mỗi nhóm sẽ cung cấp một thuật ngữ theo nghĩa đen hoặc một tổng. Nó được biết đến nhưprime implicant. Hàm ý chính được cho làessential prime implicant, nếu ít nhất đơn '0' không được bao phủ bởi bất kỳ nhóm nào khác mà chỉ bao gồm nhóm đó.
Ghi lại tất cả các hàm nguyên tố và hàm ý nguyên tố cần thiết. Hàm Boolean đơn giản chứa tất cả các hàm nguyên tố cần thiết và chỉ các hàm nguyên tố bắt buộc.
Note- Nếu thuật ngữ không quan tâm cũng xuất hiện, thì địa điểm không quan tâm 'x' trong các ô tương ứng của K-map. Chỉ xem xét dấu 'x' không quan tâm hữu ích cho việc nhóm số lượng tối đa các số 0 liền kề. Trong những trường hợp đó, hãy coi giá trị không quan tâm là '0'.
Thí dụ
Hãy để chúng tôi simplify hàm Boolean sau, $ f \ left (X, Y, Z \ right) = \ prod M \ left (0,1,2,4 \ right) $ bằng cách sử dụng K-map.
Hàm Boolean đã cho là sản phẩm của dạng số hạng Max. Nó có 3 biến X, Y & Z. Vì vậy, chúng tôi yêu cầu 3 biến K-map. Các số hạng Max đã cho là M 0 , M 1 , M 2 & M 4 . 3variable K-map với các số 0 tương ứng với các số hạng Max đã cho được thể hiện trong hình sau.
Không có khả năng nhóm 8 số 0 liền kề hoặc 4 số 0 liền kề. Có ba khả năng nhóm 2 số 0 liền kề. Sau ba nhóm này, không còn số 0 nào là chưa được nhóm. Các3 variable K-map với ba cái này groupings được hiển thị trong hình sau.
Ở đây, chúng tôi có ba hàm số nguyên tố X + Y, Y + Z & Z + X. Tất cả các hàm số nguyên tố này là essential bởi vì một số 0 trong mỗi nhóm không được bao gồm bởi bất kỳ nhóm nào khác ngoại trừ các nhóm riêng lẻ của chúng.
Do đó, simplified Boolean function Là
f = (X + Y).(Y + Z).(Z + X)
Bằng cách này, chúng ta có thể dễ dàng đơn giản hóa các hàm Boolean lên đến 5 biến bằng phương pháp K-map. Đối với nhiều hơn 5 biến, rất khó để đơn giản hóa các hàm bằng K-Maps. Bởi vì, số lượngcells trong K-map được doubled bằng cách bao gồm một biến mới.
Do đó, việc kiểm tra và nhóm các số liền kề (số hạng tối thiểu) hoặc số không liền kề (số hạng tối đa) sẽ phức tạp. Chúng ta sẽ thảo luậnTabular method trong chương tiếp theo để khắc phục những khó khăn của phương pháp K-map.