Karnaugh Mapsنەخشەکانی کارنۆ

In Simplifying Boolean expressions you used the rules of Boolean algebra. It works, but you must see which rule to apply next, and it is easy to stop too early. A Karnaugh map (K-map) does the same job with a picture: it rearranges the truth table so that terms which can be combined sit next to each other. You then simplify by drawing loops.

لە کورتکردنەوەی دەربڕینە بوولییەکان ڕێساکانی جەبری بوولت (Boolean algebra) بەکار هێنا. کار دەکات، بەڵام دەبێت ببینیت کام ڕێسا دواتر بەکاربهێنیت و ئاسانە زوو بوەستیت. نەخشەی کارنۆ ⁦(K-map)⁩ هەمان کار بە وێنەیەک دەکات: خشتەی ڕاستییەکە بە شێوەیەک ڕێک دەخاتەوە کە ئەو بڕانەی دەتوانرێن یەک بخرێن لە تەنیشت یەکەوە دابنرێن. پاشان بە کێشانی بازنە کورتی دەکەیتەوە.

Maurice Karnaugh introduced the map in 1953, improving a chart that Edward Veitch had published a year earlier. It is used by hand for functions of up to four variables.

⁦Maurice Karnaugh⁩ لە ساڵی ⁦1953⁩دا ئەم نەخشەیەی هێنایە ئاراوە و خشتەیەکی باشتر کرد کە ⁦Edward Veitch⁩ ساڵێک پێشتر بڵاوی کردبووەوە. بە دەست بۆ نەخشە بوولییەکانی هەتا چوار گۆڕاوی بوولی بەکار دێت.

Look at two minterms that differ in one variable only, such as $AB\overline{C}$ and $ABC$. Factor out what they share:

سەیری دوو مینتێرم بکە کە تەنها لە یەک گۆڕاوی بوولیدا جیاوازن، وەک $AB\overline{C}$ و $ABC$. ئەوەی هاوبەشیانە دەربهێنە:

If four minterms form two such pairs, the same step works twice and two variables disappear. A K-map is built so that every such pair sits side by side.

ئەگەر چوار مینتێرم دوو جووتی وا پێک بهێنن، هەمان هەنگاو دوو جار کار دەکات و دوو گۆڕاوی بوولی نامێنن. نەخشەی کارنۆ بەو شێوەیە دروست کراوە کە هەموو جووتێکی وا لە تەنیشت یەکەوە بێت.

A K-map has one cell for each row of the truth table: 4 cells for 2 variables, 8 for 3, 16 for 4. The variables are split between the rows and the columns, and each cell holds the output of its row. The number written in a corner of a cell is its minterm number.

نەخشەی کارنۆ بۆ هەر ڕیزێکی خشتەی ڕاستی یەک خانەی هەیە: 4 خانە بۆ 2 گۆڕاوی بوولی، 8 بۆ 3، ⁦16⁩ بۆ 4. گۆڕاوە بوولییەکان لە نێوان ڕیز و ستوونەکاندا دابەش دەکرێن و هەر خانەیەک دەرخستەی (Output) ڕیزەکەی خۆی هەڵدەگرێت. ئەو ژمارەیەی لە گۆشەی خانەیەکدا نووسراوە ژمارەی مینتێرمەکەیەتی.

Look at the column order: 00, 01, 11, 10 — not 00, 01, 10, 11. This is the Gray code, where only one bit changes from one step to the next. If 10 came straight after 01, two bits would change ($01 \to 10$) and the neighbours could not be combined. That is why the cell numbers run 0, 1, 3, 2 — the 2-bit Gray code, which is built by reflecting the list.

سەیری ڕیزبەندیی ستوونەکان بکە: ⁦00⁩، ⁦01⁩، ⁦11⁩، ⁦10⁩ — نەک ⁦00⁩، ⁦01⁩، ⁦10⁩، ⁦11⁩. ئەمە کۆدی گرەیە کە تێیدا لە هەنگاوێکەوە بۆ هەنگاوی دواتر تەنها یەک بیت (Bit) دەگۆڕێت. ئەگەر ⁦10⁩ ڕاستەوخۆ دوای ⁦01⁩ بهاتایە، دوو بیت دەگۆڕان ($01 \to 10$) و دراوسێکان نەیاندەتوانی یەک بخرێن. بۆیە ژمارەی خانەکان بەم شێوەیەن: 0، 1، 3، 2 — کۆدی گرەیی دوو بیت، کە بە هەڵگەڕاندنەوەی لیستەکە دروست دەکرێت.

The first and the last columns are neighbours too: 00 and 10 differ in one bit. In a 4-variable map the top and bottom rows are also neighbours, so the four corners (cells 0, 2, 8 and 10) all touch each other. Imagine the map printed on a sheet that you roll into a tube, and then bend the tube into a ring: every edge meets the opposite edge.

یەکەم و دوایین ستوون دراوسێی یەکترن: ⁦00⁩ و ⁦10⁩ لە یەک بیتدا جیاوازن. لە نەخشەیەکی چوار گۆڕاوی بوولیدا ڕیزی سەرەوە و خوارەوەش دراوسێن، بۆیە چوار گۆشەکە (خانەکانی 0، 2، 8 و ⁦10⁩) هەموویان بەریەک دەکەون. وا دابنێ نەخشەکە لەسەر پەڕەیەک چاپ کراوە کە دەیپێچیت بۆ بۆرییەک و پاشان بۆرییەکە دەچەمێنیتەوە بۆ ئەڵقەیەک: هەر لێوارێک بە لێوارە بەرامبەرەکەی دەگات.

Reading a group: a variable that has the same value in every cell of the group stays in the term (plain if it is 1, with a bar if it is 0). A variable that changes inside the group disappears. So a group of $2^k$ cells in a map of n variables gives a term with $n-k$ literals:

خوێندنەوەی کۆمەڵەیەک: گۆڕاوێکی بوولی کە لە هەموو خانەکانی کۆمەڵەکەدا هەمان بەهای هەبێت لە بڕەکەدا دەمێنێتەوە (ساکار ئەگەر 1 بێت، بە هێڵ ئەگەر 0 بێت). گۆڕاوێکی بوولی کە لە ناو کۆمەڵەکەدا بگۆڕێت نامێنێت. کەواتە کۆمەڵەیەکی $2^k$ خانە لە نەخشەیەکی n گۆڕاوی بوولیدا بڕێک دەدات بە $n-k$ لیتەراڵ (Literal).

Take the function of the minterms lesson, $X = \sum m(3, 4, 5, 6, 7)$. Put a 1 in cells 3, 4, 5, 6 and 7 and a 0 elsewhere.

نەخشە بوولییەکەی وانەی مینتێرمەکان وەربگرە، $X = \sum m(3, 4, 5, 6, 7)$. لە خانەکانی 3، 4، 5، 6 و 7دا 1 دابنێ و لە شوێنی تر 0.

Five minterms with three literals each became two short terms. Boolean algebra agrees: $\overline{A}BC + A(\ldots) = A + \overline{A}BC = A + BC$ by rule 11.

پێنج مینتێرم کە هەر یەکێکیان سێ لیتەراڵی هەبوو بوون بە دوو بڕی کورت. جەبری بوولیش هاوڕایە: $\overline{A}BC + A(\ldots) = A + \overline{A}BC = A + BC$ بە ڕێسای ⁦11⁩.

The exam expression $\overline{AB+AC}+\overline{A}\,\overline{B}C$ took six lines of algebra in the simplification lesson. Its truth table has 1s in cells 0, 1, 2, 3 and 4 (see the circuit lesson):

دەربڕینە بوولییەکەی تاقیکردنەوەکە $\overline{AB+AC}+\overline{A}\,\overline{B}C$ شەش دێڕ جەبری پێویست بوو لە وانەی کورتکردنەوە. خشتەی ڕاستییەکەی لە خانەکانی 0، 1، 2، 3 و 4دا 1ـی تێدایە (بڕوانە وانەی سووڕ):

The whole top row ($A = 0$) is a quad → $\overline{A}$. Cell 4 pairs with cell 0 above it (column $BC = 00$) → $\overline{B}\,\overline{C}$. So $X = \overline{A}+\overline{B}\,\overline{C}$ — exactly the course author's answer, without any algebra tricks.

هەموو ڕیزی سەرەوە ($A = 0$) چوارینەیەکە ← $\overline{A}$. خانەی 4 لەگەڵ خانەی 0ـی سەرەوەی جووت دەبێت (ستوونی $BC = 00$) ← $\overline{B}\,\overline{C}$. کەواتە $X = \overline{A}+\overline{B}\,\overline{C}$ — ڕێک وەڵامەکەی خاوەنی کۆرسەکە، بەبێ هیچ فێڵێکی جەبری.

A wrap-around example: $X = \sum m(0, 2, 5, 7)$. Cells 0 and 2 are in the first and last columns of the top row — neighbours across the edge → $\overline{A}\,\overline{C}$. Cells 5 and 7 are side by side in the bottom row → $AC$. So $X = \overline{A}\,\overline{C} + AC$, which is the XNOR of A and C.

نموونەیەکی سووڕانەوە: $X = \sum m(0, 2, 5, 7)$. خانەکانی 0 و 2 لە یەکەم و دوایین ستوونی ڕیزی سەرەوەدان — دراوسێن بە ناو لێوارەکەدا ← $\overline{A}\,\overline{C}$. خانەکانی 5 و 7 لە ڕیزی خوارەوەدا لە تەنیشت یەکن ← $AC$. کەواتە $X = \overline{A}\,\overline{C} + AC$، کە XNORـی A و Cـیە.

Now a 4-variable function, $F = \sum m(0, 2, 3, 8, 10, 12, 13, 14, 15)$. Watch the groups being circled in order — biggest first, and only as many as needed.

ئێستا نەخشەیەکی بوولی بە چوار گۆڕاوی بوولی، $F = \sum m(0, 2, 3, 8, 10, 12, 13, 14, 15)$. سەیری بازنەکردنی کۆمەڵەکان بکە بە ڕیز — سەرەتا گەورەترین و تەنها ئەوەندەی پێویستە.

Some input combinations never happen. A BCD digit, for example, only uses 0000 to 1001; the codes 1010 to 1111 never appear. For those rows we do not care what the circuit outputs, so we write X in the truth table and in the map. An X may be treated as 1 if that makes a group bigger, and as 0 otherwise. Never make a group of X's only. A priority encoder is a real circuit whose truth table is full of X's.

هەندێک تێکەڵەی نێوخستە هەرگیز ڕوو نادەن. بۆ نموونە، ژمارەیەکی کۆدی دەیی دووانی تەنها ⁦0000⁩ تا ⁦1001⁩ بەکار دەهێنێت؛ کۆدەکانی ⁦1010⁩ تا ⁦1111⁩ هەرگیز دەرناکەون. بۆ ئەو ڕیزانە گرنگ نییە سووڕەکە (Electric circuit) چی بدات، بۆیە لە خشتەی ڕاستی و نەخشەکەدا X دەنووسین. X دەتوانێت وەک 1 دابنرێت ئەگەر کۆمەڵەیەک گەورەتر بکات و لە حاڵەتی تردا وەک 0. هەرگیز کۆمەڵەیەک تەنها لە X دروست مەکە. کۆدکەری پێشینەیی سووڕێکی ڕاستەقینەیە کە خشتەی ڕاستییەکەی پڕە لە X.

Example: a circuit receives one BCD digit ABCD and outputs 1 when the digit is 5 or more — the test used when rounding a decimal number. The 1s are cells 5 to 9, the X's are cells 10 to 15.

نموونە: سووڕێک یەک ژمارەی کۆدی دەیی دووانی (BCD) ABCD وەردەگرێت و کاتێک ژمارەکە 5 یان زیاتر بێت 1 دەدات — ئەو تاقیکردنەوەیەی لە نزیککردنەوەی ژمارەیەکی دەییدا بەکار دێت. 1ـەکان خانەکانی 5 تا 9ن و Xـەکان خانەکانی ⁦10⁩ تا ⁦15⁩.

Without the X's the best you can do is $\overline{A}BD + \overline{A}BC + A\overline{B}\,\overline{C}$ (three terms, nine literals). With them: $F = A + BD + BC$ (five literals), which can even be written $A + B(C + D)$. The circuit gives the right answer for every real digit 0–9.

بەبێ Xـەکان باشترین ئەنجام $\overline{A}BD + \overline{A}BC + A\overline{B}\,\overline{C}$ـە (سێ بڕ، نۆ لیتەراڵ). بە Xـەکانەوە: $F = A + BD + BC$ (پێنج لیتەراڵ)، کە تەنانەت دەتوانرێت بنووسرێت $A + B(C + D)$. سووڕەکە بۆ هەموو ژمارەیەکی ڕاستەقینەی ⁦0–9⁩ وەڵامی ڕاست دەدات.

A K-map can also give a simplified POS expression. Group the 0s with exactly the same rules. Each group of 0s gives a sum term, read with the maxterm rule: a variable that stays 0 is written plain, one that stays 1 gets a bar. Multiply the sum terms.

نەخشەی کارنۆ دەتوانێت لێکدانی کۆکانی کورتکراوەش بدات. 0ـەکان بە هەمان ڕێسا کۆمەڵ بکە. هەر کۆمەڵەیەکی 0 بڕێکی کۆ (Sum term) دەدات کە بە ڕێسای ماکستێرم دەخوێنرێتەوە: گۆڕاوێکی بوولی کە وەک 0 بمێنێتەوە بە ساکاری دەنووسرێت و ئەوەی وەک 1 بمێنێتەوە هێڵی لەسەر دادەنرێت. بڕەکانی کۆ لێک بدە.

For $\sum m(3,4,5,6,7)$ the 0s are cells 0, 1 and 2. Cells 0–1 keep $A = 0$ and $B = 0$ → $(A + B)$; cells 0–2 (across the edge) keep $A = 0$ and $C = 0$ → $(A + C)$. So $X = (A + B)(A + C)$, and rule 12 confirms that this equals $A + BC$ — the same function as the SOP answer.

بۆ $\sum m(3,4,5,6,7)$ 0ـەکان خانەکانی 0، 1 و 2ن. خانەکانی ⁦0–1⁩ $A = 0$ و $B = 0$ دەهێڵنەوە ← $(A + B)$؛ خانەکانی ⁦0–2⁩ (بە ناو لێوارەکەدا) $A = 0$ و $C = 0$ دەهێڵنەوە ← $(A + C)$. کەواتە $X = (A + B)(A + C)$ و ڕێسای ⁦12⁩ دەیسەلمێنێت کە ئەمە یەکسانە بە $A + BC$ — هەمان نەخشەی بوولیی وەڵامی SOP.