Petrick's Method and Cyclic Covers
Solve a prime implicant chart with no essential prime by listing every cover as a product. Then see why exact covering does not scale.
You Will Be Able To
- Recognize a cyclic chart: no essential prime and no dominance.
- Write Petrick's product of sums for a chart and multiply it out with absorption.
- Pick the cheapest cover from the expanded products.
- Explain why exact covering grows too fast for large functions.
- Lesson
- G3.6
- Time
- 30 min
- Runs on
- Your browser
- Check
- 5 questions
Some charts give the method nothing to start from. Every column has two X. Every row is as good as its neighbours. A guess still gives a cover, but maybe not the smallest.
| Cover of the same function | Product terms | Literals |
|---|---|---|
| Primes picked without a plan | 5 | 15 |
| The cheapest product of Petrick's method | 4 | 12 |
Computed for f = Σm(1, 3, 6, 7, 8, 9, 12, 14). Both covers are correct on all 16 rows.
A Chart with No Way In
The function f = Σm(1, 3, 6, 7, 8, 9, 12, 14) has eight prime implicants. Each is a pair of cells. Name them P1 to P8.
| Prime | Term | 1 | 3 | 6 | 7 | 8 | 9 | 12 | 14 |
|---|---|---|---|---|---|---|---|---|---|
| P1 | b'c'd | X | X | ||||||
| P2 | bcd' | X | X | ||||||
| P3 | a'cd | X | X | ||||||
| P4 | a'b'd | X | X | ||||||
| P5 | a'bc | X | X | ||||||
| P6 | ac'd' | X | X | ||||||
| P7 | ab'c' | X | X | ||||||
| P8 | abd' | X | X |
Every column has exactly two X, and every row holds two columns.
No column has one X, so no prime is essential. No row holds more than another, so row dominance removes nothing. No column holds another, so column dominance fails too. The chart is cyclic.
- Neutral
- Structure
- Cover A
Take every other prime: P1 P2 P3 P6. Each line touches one of them.
- Cover B
Or take the other half: P4 P5 P7 P8. It also touches every line.
- A careless start
Start with P1 and P5, which are not alternate. The ring then needs 5 primes, such as P1 P3 P5 P6 P8.
Read the diagram as text
- P1 = b'c'd: rows 1, 9
- P4 = a'b'd: rows 1, 3
- P3 = a'cd: rows 3, 7
- P5 = a'bc: rows 6, 7
- P2 = bcd': rows 6, 14
- P8 = abd': rows 12, 14
- P6 = ac'd': rows 8, 12
- P7 = ab'c': rows 8, 9
- P1 = b'c'd → P4 = a'b'd: row 1
- P4 = a'b'd → P3 = a'cd: row 3
- P3 = a'cd → P5 = a'bc: row 7
- P5 = a'bc → P2 = bcd': row 6
- P2 = bcd' → P8 = abd': row 14
- P8 = abd' → P6 = ac'd': row 12
- P6 = ac'd' → P7 = ab'c': row 8
- P7 = ab'c' → P1 = b'c'd: row 9
Eight lines and eight primes: four primes are enough only if they alternate around the ring.
Petrick's Product
Write each column as a sum: the primes that can cover it. A cover must satisfy every column, so AND the sums together.
(P1 + P4) // row 1
(P3 + P4) // row 3
(P2 + P5) // row 6
(P3 + P5) // row 7
(P6 + P7) // row 8
(P1 + P7) // row 9
(P6 + P8) // row 12
(P2 + P8) // row 14Multiply the sums out, one at a time. After each step, apply absorption: a product that holds all the primes of a smaller product adds nothing. X + XY = X.
| Sum multiplied in | Products before absorption | Products after absorption |
|---|---|---|
| row 1: (P1 + P4) | 2 | 2 |
| row 3: (P3 + P4) | 4 | 2 |
| row 6: (P2 + P5) | 4 | 4 |
| row 7: (P3 + P5) | 8 | 4 |
| row 8: (P6 + P7) | 8 | 8 |
| row 9: (P1 + P7) | 16 | 7 |
| row 12: (P6 + P8) | 14 | 9 |
| row 14: (P2 + P8) | 18 | 10 |
Generated by the expansion code of this lesson. Without absorption the list would double at every row: 256 products at the end.
Open the 10 products that remain
| Product (a cover) | Primes | Literals |
|---|---|---|
| P1 P2 P3 P6 | 4 | 12 |
| P1 P2 P3 P7 P8 | 5 | 15 |
| P1 P3 P5 P6 P8 | 5 | 15 |
| P1 P3 P5 P7 P8 | 5 | 15 |
| P2 P3 P4 P6 P7 | 5 | 15 |
| P2 P3 P4 P7 P8 | 5 | 15 |
| P1 P2 P4 P5 P6 | 5 | 15 |
| P1 P4 P5 P6 P8 | 5 | 15 |
| P2 P4 P5 P6 P7 | 5 | 15 |
| P4 P5 P7 P8 | 4 | 12 |
Every row of this table is a cover that no smaller cover is inside.
Choose the Cheapest Product
Every product is a cover. Pick the one with the fewest primes. Here two products have four primes: P1 P2 P3 P6 and P4 P5 P7 P8.
If several products tie on primes, count literals and keep the smallest. In this chart every prime has three literals, so both ties cost the same.
| Cover | Primes | Expression | Terms | Literals |
|---|---|---|---|---|
| A | P1 P2 P3 P6 | b'c'd + bcd' + a'cd + ac'd' | 4 | 12 |
| B | P4 P5 P7 P8 | a'b'd + a'bc + ab'c' + abd' | 4 | 12 |
Both are minimum covers. The exact minimizer finds the same two.
Petrick's method finishes the work of lesson G3.5. Take the essential primes and apply dominance first. Then use Petrick only on the cyclic part that is left.
Why Exact Covering Grows Too Fast
Petrick's method is exact, and that is its weakness. The expansion can hold a huge number of products before absorption trims it.
| Primes in a chart | Subsets to try by brute force |
|---|---|
| 8 | 256 |
| 20 | 1,048,576 |
| 40 | about 1.1 million million |
| 100 | more than 10^30 |
Each prime is in or out of a cover, so there are 2 to the power of the number of primes subsets.
Picking the fewest primes to cover a chart is a set-cover problem. No known method solves every large case quickly. Real tools use heuristics and accept a cover that is small, not always minimum.
Asked in interviews
What is a cyclic prime implicant chart?
A chart where every column has at least two X and no dominance rule applies. No prime is forced, so you must search.
How does Petrick's method work?
Each column becomes a sum of the primes that cover it. The product of the sums, multiplied out with absorption, lists every cover. Take the cheapest.
Why do synthesis tools not find the exact minimum?
Exact two-level covering grows too fast with the number of primes. Tools use heuristic minimizers that give a good cover quickly.
Try It
The table holds the careless cover: P1 P3 P5 P6 P8. The bench finds no wrong row and counts 5 terms.
Enter cover A: N = 4, CARE = {4'b1011, 4'b1011, 4'b0111, 4'b0111} and VALUE = {4'b1000, 4'b0011, 4'b0110, 4'b0001}. The bench prints minimum is 4 terms, 12 literals: reached.
Enter cover B: CARE = {4'b1101, 4'b1110, 4'b1110, 4'b1101} and VALUE = {4'b1100, 4'b1000, 4'b0110, 4'b0001}. It reaches the minimum too. A cyclic chart can have more than one minimum cover.
0 of 16 rows wrong 5 terms, 15 literals minimum is 4 terms, 12 literals: not reachedRead included file: tb.sv
// tb.sv: the bench (read-only). It builds the sum of products from the table in module answer,
// compares it with f on every row that is not a don't-care, and counts terms and literals.
module tb;
// Bit m of F is f on row m, where m is the binary value of abcd. DC marks the don't-care rows.
localparam logic [15:0] F = 16'b0101001111001010;
localparam logic [15:0] DC = 16'b0000000000000000;
wire [7:0] n;
wire [31:0] care, value;
answer ans (.n(n), .care(care), .value(value));
// The sum of products on one row: 1 when some term of the table holds the row.
function automatic logic table_at(input logic [3:0] row);
logic hit;
hit = 1'b0;
for (int t = 0; t < 8; t++)
if (t < n && ((row ^ value[4*t +: 4]) & care[4*t +: 4]) == '0) hit = 1'b1;
return hit;
endfunction
initial begin
int wrong, lits;
logic [3:0] row, used;
#1; // let the table reach the wires
wrong = 0;
lits = 0;
for (int m = 0; m < 16; m++) begin
row = m[3:0];
if (!DC[m] && table_at(row) !== F[m]) begin
if (wrong == 0) $display("first wrong row: abcd = %b (f is %b, the table gives %b)", row, F[m], table_at(row));
wrong++;
end
end
for (int t = 0; t < 8; t++) if (t < n) begin
used = care[4*t +: 4]; // one group's CARE bits
lits += $countones(used);
end
$display("%0d of 16 rows wrong", wrong);
$display("%0d terms, %0d literals", n, lits);
if (wrong == 0 && n == 4 && lits == 12) $display("minimum is 4 terms, 12 literals: reached");
else if (wrong == 0) $display("minimum is 4 terms, 12 literals: not reached");
end
endmodule
Check Yourself
Common Mistakes
Wrong Pick primes in a cyclic chart until every 1 is covered, in any order.
The first pick decides the rest. A careless start gives a legal cover that is one term too big.
Fix List every cover with Petrick's method, then take the cheapest.
Wrong Multiply out Petrick's product without absorption.
The list doubles with each sum, and most products are covers with extra primes.
Fix After each step, drop any product that holds a smaller product: X + XY = X.
Wrong Take the shortest product and stop.
Two products can have the same number of primes and different literal counts.
Fix Among the shortest products, count literals and keep the cheapest.
Remember
- A cyclic chart has no essential prime and no dominance, so the earlier rules cannot choose.
- Petrick's method writes one sum per column and multiplies them out with absorption: every product is a cover.
- Choose the product with the fewest primes, then the fewest literals.
- Exact covering grows too fast, so tools use heuristic minimizers on large functions.