VericodeRTL · DV · QUIZTìm bài học, kiến thức…Ctrl K
Học để hiểu. Thực hành để vững.

K-map, SOP và POS: gộp các hàng chỉ khác một biến

Khoảng 45 phútMức 1/3Bản nháp: một số khẳng định chưa đối chiếu spec

Tiên quyết

Sau bài này bạn sẽ

  • Đặt đúng thứ tự Gray và nhóm được cả biên bản đồ
  • Viết SOP từ nhóm 1 và POS từ nhóm 0
  • Dùng don’t-care theo hợp đồng thay vì hiểu nó là X lúc chạy

Hai hàng có thể dùng chung một điều kiện

Hai minterm A'B'C và A'B'C' khác nhau đúng ở C. OR chúng lại được A'B'·(C+C')=A'B'. Biến thay đổi đã biến mất khỏi điều kiện chung.

K-map đặt những hàng như thế cạnh nhau để nhìn thấy chỗ gộp. Bản đồ là cách sắp lại bảng chân trị, không thay đổi hàm cần thực hiện.

Nhãn Gray và các cạnh quấn vòng

Với hai biến, bản đồ là 2×2, mỗi chiều mang một biến. Với ba biến, dùng hai hàng A bằng 0/1 và bốn cột BC theo thứ tự Gray. Thêm biến thứ tư tạo bản đồ 4×4 bên dưới.

Bản đồ bốn biến dưới dùng AB cho hàng, CD cho cột; cả hai theo thứ tự 00, 01, 11, 10. A là bit cao nhất khi đánh số minterm.

AB / CD 00 01 11 10
00 1 0 0 1
01 0 1 1 0
11 0 1 1 0
10 1 0 0 1

Cột đầu và cuối kề nhau; hàng đầu và cuối cũng vậy. Đi ngang hoặc dọc một ô kề chỉ đổi một biến. Đi chéo không phải quan hệ kề.

Bốn góc tạo thành một nhóm bốn ô hợp lệ nhờ quấn qua hai biên. Điều đó không có nghĩa mọi cặp góc đều kề nhau; hai góc đối diện khác hai biến.

Nhóm là hình chữ nhật có số ô lũy thừa hai

Để tìm SOP, nhóm các ô 1 thành hình chữ nhật có 1, 2, 4, 8 hoặc 16 ô, có thể quấn biên. Không nhóm chéo, hình chữ L hoặc ba ô.

Mỗi nhóm giữ các biến có giá trị cố định và bỏ biến thay đổi. Nhóm càng lớn thì tích có càng ít literal. Cho phép các nhóm chồng nhau; chỉ cần mọi ô 1 được phủ và không phủ ô 0.

Prime implicant là nhóm không mở rộng thêm được mà vẫn hợp lệ. Essential prime implicant là nhóm duy nhất phủ được ít nhất một ô 1. Chọn các nhóm thiết yếu trước, rồi phủ phần còn lại; không mặc định một lựa chọn tham lam bất kỳ sẽ cho lời giải nhỏ nhất.

Đọc SOP từ hai nhóm trong ví dụ

Bốn góc có B bằng 0, D bằng 0; A và C thay đổi, nên tạo tích B'D'. Bốn ô 1 ở giữa có B bằng 1, D bằng 1, nên tạo tích BD.

SOP thu được là F=B'D'+BD. Các minterm của bảng là 0, 2, 5, 7, 8, 10, 13, 15. Có thể kiểm lại từng hàng; hàm thực chất so B và D bằng nhau.

SOP tổng quát là OR của các tích, không bắt buộc mỗi tích chứa đủ bốn biến. Canonical SOP mới dùng một minterm đủ mọi biến cho từng hàng ra 1.

Đọc POS từ các nhóm 0

Với nhóm 0, lập tổng sao cho tổng ấy bằng 0 trên toàn nhóm. Biến cố định 0 xuất hiện trực tiếp; biến cố định 1 xuất hiện dạng đảo. AND các tổng lại để được POS.

Trong bảng, một nhóm 0 có B bằng 0, D bằng 1 → tổng B+D'. Nhóm còn lại có B bằng 1, D bằng 0 → tổng B'+D. Vì vậy F=(B+D')·(B'+D).

Canonical POS dùng một maxterm cho mỗi hàng ra 0, chứa mỗi biến đúng một lần. Minterm chọn một hàng ra 1; maxterm loại một hàng bằng cách bằng 0 tại hàng ấy. Đừng dùng cùng quy tắc đảo biến cho hai loại.

Don’t-care là phạm vi yêu cầu, không phải giá trị bí ẩn

X trong K-map chỉ một đầu vào mà yêu cầu cho phép không quan tâm đầu ra. Có thể dùng ô ấy như 0 hoặc 1 để nhóm thuận tiện; không bắt buộc phủ nó.

Ví dụ so một chữ số BCD có từ 5 trở lên. Trên mã hợp lệ 0 tới 9, biểu thức A+B·(C+D) cho kết quả đúng. Nhưng với các mã binary 10 tới 15, biểu thức này đều cho 1. Một bản có kiểm mã hợp lệ có thể cho 0 trên cả sáu mã ấy.

Hai bản chỉ tương đương theo hợp đồng loại bỏ 10 tới 15. Nếu đầu vào có thể nhận các mã đó, phải định nghĩa cách xử lý, không viện “don’t-care” để bỏ kiểm tra. Chữ X trong mô phỏng 4-state là khái niệm khác; nó không tự cấp phép tối ưu mọi hành vi.

Các lỗi nhóm và kết luận quá xa

  • Đặt nhãn 00, 01, 10, 11 làm hai ô cạnh nhau đổi hai biến.
  • Quên quấn biên hoặc cho các ô chéo là kề.
  • Nhóm ba ô, hoặc bỏ sót một ô 1 chưa được phủ.
  • Đọc nhóm 0 theo quy tắc nhóm 1.
  • Tưởng SOP ít literal nhất luôn là phần cứng tốt nhất.

Hàm parity có thể không gộp được trong SOP hai mức mà vẫn viết rất gọn bằng XOR. K-map nhỏ giúp hiểu và kiểm; synthesis còn có phép factor nhiều mức và thư viện cell.

Tự gộp rồi kiểm lại bảng

  1. Vì sao nhóm bốn góc của bảng bỏ được A và C, nhưng giữ B và D?
  2. Chỉ ra minterm tương ứng ô hàng AB bằng 10, cột CD bằng 10.
  3. Thay B bằng 0, D bằng 1 trong cả SOP và POS đã tìm; kết quả có khớp không?
  4. Một thiết bị có thể gửi BCD không hợp lệ sau reset. Bạn có còn được coi mọi mã 10 tới 15 là don’t-care không?
  5. Bản đồ có hai nghiệm tối giản cùng số literal. Cần bằng chứng nào thêm trước khi chọn vì timing?

Kiểm tra

Tự kiểm tra: K-map, SOP và POS: gộp các hàng chỉ khác một biến

  1. Nhãn cột K-map hai biến nên dùng thứ tự nào?
  2. Bốn góc của bản đồ ví dụ giữ B=0,D=0. Tích rút gọn là gì?
  3. Nhóm SOP nào hợp lệ trên K-map?
  4. Khi đọc tổng POS từ nhóm 0, biến cố định 1 xuất hiện thế nào?
  5. Mã 10 tới 15 chỉ được bỏ qua trong bài BCD khi nào?

Bằng chứng kiểm chứng

Expected tính trước chạy: KMAP CHECK table=16 ones=8 bcd_valid=10 invalid_different=6 time_ns=32.

K-map SOP/POS và hợp đồng BCD don’t-care

Kỳ vọng tính trước chạy: KMAP CHECK table=16 ones=8 bcd_valid=10 invalid_different=6 time_ns=32

kmap_core.sv RTL
`timescale 1ns/1psmodule kmap_core(input logic [3:0] code,output wire canonical,sop,pos,xnor_form,strict_bcd,relaxed_bcd); wire a=code[3],b=code[2],c=code[1],d=code[0]; assign canonical=((~a)&(~b)&(~c)&(~d))|((~a)&(~b)&c&(~d))|((~a)&b&(~c)&d)|((~a)&b&c&d)|                   (a&(~b)&(~c)&(~d))|(a&(~b)&c&(~d))|(a&b&(~c)&d)|(a&b&c&d); assign sop=((~b)&(~d))|(b&d); assign pos=(b|(~d))&((~b)|d); assign xnor_form=~(b^d); assign strict_bcd=(code>=4'd5)&&(code<=4'd9); assign relaxed_bcd=a|(b&(c|d));endmodule
tb.sv testbench
`timescale 1ns/1psmodule tb_a2_kmap; logic [3:0] code;wire canonical,sop,pos,xnor_form,strict_bcd,relaxed_bcd; kmap_core dut(.*); logic [15:0] truth=16'ha5a5,bcd_truth=16'h03e0; int table_count=0,ones=0,bcd_valid=0,invalid_different=0; initial begin  for(int i=0;i<16;i++)begin   code=4'(i);#1;table_count++;   if(canonical!==truth[i]||sop!==truth[i]||pos!==truth[i]||xnor_form!==truth[i])$fatal(1,"Kmap table mismatch code=%0d",i);   if(sop)ones++;  end  for(int i=0;i<16;i++)begin   code=4'(i);#1;   if(strict_bcd!==bcd_truth[i])$fatal(1,"Kmap strict BCD mismatch code=%0d",i);   if(i<10)begin    bcd_valid++;if(relaxed_bcd!==bcd_truth[i])$fatal(1,"Kmap valid BCD mismatch code=%0d",i);   end else begin    if(relaxed_bcd!==1'b1)$fatal(1,"Kmap chosen invalid implementation mismatch");    if(strict_bcd!=relaxed_bcd)invalid_different++;   end  end  if(table_count!=16||ones!=8||bcd_valid!=10||invalid_different!=6||$time!=32)$fatal(1,"Kmap contract");  $display("KMAP CHECK table=%0d ones=%0d bcd_valid=%0d invalid_different=%0d time_ns=%0d",table_count,ones,bcd_valid,invalid_different,$time);  $finish; endendmodule

Đã kiểm chứng thế nào

  • Phân tích và elaborate theo LRM (pyslang 12.1.0)
  • Lint -Wall (Verilator 5.050)
  • Mô phỏng, exit 0 và output khớp kỳ vọng tính tay (Verilator 5.050, 2-state)
  • Tổng hợp, số cell khớp kỳ vọng (Yosys 0.70)

Output phải khớp: KMAP CHECK table=16 ones=8 bcd_valid=10 invalid_different=6 time_ns=32

Kỳ vọng sau tổng hợp: kmap_core: $_*DFF* = 0kmap_core: $_*LATCH* = 0

Finite known 0/1 input domains only. Generic synthesis, where claimed, is not technology mapping, STA or PPA. No all-width or X/Z language conformance claim.

Các kiểm tra chạy lúc xây dựng nội dung (2026-11-07), không chạy trong trình duyệt. Kỳ vọng được tính tay trước khi chạy.

Tham chiếu bảng là literal A5A5, tương ứng tám minterm đã tính; canonical SOP, SOP rút gọn, POS và XNOR phải cùng khớp cả 16 hàng. Ví dụ BCD dùng một literal khác cho yêu cầu strict; kiểm riêng 10 mã hợp lệ và sáu mã ngoài hợp đồng relaxed, không dùng X để che sai.

Parsed/linted/simulated/synthesized đạt, không flip-flop/latch trong synthesis generic. Không claim một kiểu biểu thức luôn tốt nhất về cell/timing hoặc đủ cho mọi chiều rộng. Kết quả ngoài miền don’t-care là lựa chọn cụ thể của implementation đã viết, không phải cam kết chung của mọi phép tối ưu.

[1] [2] [3]

Bài liên quan

Nguồn và mức độ đối chiếu

  1. Karnaugh Maps — bản chụp resources.zip, Why a Map Works; Gray-Code Ordering and Wraparound; The Grouping Rules; Worked Example: 4 Variables; Prime and Essential Prime Implicants; Reading a POS Expression: Grouping the 0s; Don't-Care Conditions; Patterns a K-Map Cannot Simplify. Trích dẫn; nguồn đã đọc các mục liên quan.
  2. Thí nghiệm nguyên bản A2.kmap, Sixteen canonical/SOP/POS truth rows and valid versus invalid BCD contracts. Trích dẫn; nguồn đã đọc toàn văn.
  3. IEEE 1800-2023 SystemVerilog LRM, Scalar bitwise expressions, packed indexing and explicit defined outputs outside a BCD contract — chưa đối chiếu LRM. Chưa đối chiếu với văn bản nguồn (chưa mở).