أنواع التنفيذ ثنائي المستوى للتعبيرات المنطقية
تغطي هذه الوحدة تبسيط مضروب المجاميع (POS)، وحالات عدم الاكتراث (Don't Care)، والبوابات الشاملة (NAND و NOR)، وتحويل الدوائر، وبوابات XOR مع تطبيقاتها في اكتشاف الأخطاء.
Two-Level Implementation types of Boolean expressions
This module covers Product-of-Sums (POS) simplification, Don't Care conditions, Universal Gates (NAND & NOR), circuit conversion, and XOR gates with error detection applications.
أهداف التعلم
- استنتاج صيغتي مجموع المضاريب (SOP) ومضروب المجاميع (POS) مباشرة من خريطة كارنوف.
- إنشاء خريطة كارنوف لدالة منطقية انطلاقاً من جدول الحقيقة الخاص بها.
- تبسيط الدوال المنطقية باستخدام حالات عدم الاكتراث (Don't-Care conditions).
- تنفيذ الدوائر الرقمية باستخدام تركيبات مختلفة من البوابات المنطقية (مثل NAND و NOR).
- فهم بوابات XOR (الاستبعاد المنطقي) واستخداماتها في الأنظمة الرقمية.
- Obtain the sum of products and the product of sums forms of a Boolean function directly from its Karnaugh map.
- Create the Karnaugh map of a Boolean function from its truth table.
- Simplify a Boolean function using Don’t-Care conditions.
- Implement digital circuits (Boolean functions) using various combinations of logic gates.
- Understand the XOR gates and its usage.
1 تبسيط مضروب المجاميع (POS)
1 Product-of-Sums (POS) Simplification
تجميع الأصفار في خريطة كارنوف يعطينا متمم الدالة، وبتطبيق نظرية دي مورغان نحصل على صيغة مضروب المجاميع.
Grouping 0s in a K-map gives the complement function; applying DeMorgan's theorem yields the POS form.
في خريطة كارنوف، تمثل المربعات التي تحتوي على '1' حدود المضروب (minterms) للدالة. أما المربعات الفارغة (أو التي تحتوي على '0') فتمثل متمم الدالة (F').
إذا قمنا بتجميع الأصفار، نحصل على تعبير مبسط بصيغة مجموع المضاريب (SOP) لمتمم الدالة.
للحصول على الدالة الأصلية F بصيغة مضروب المجاميع (POS)، نقوم بأخذ المتمم للنتيجة باستخدام نظرية دي مورغان (DeMorgan's theorem).
In a K-map, the 1s represent the minterms of the function. The empty squares (marked with 0s) represent the minterms not included in F, denoting its complement (F').
By combining the 0s, we obtain a simplified sum-of-products expression for F'.
Taking the complement of F' using DeMorgan's theorem gives us back the function F in product-of-sums form.
لماذا نستخدم هذه الطريقة؟ في بعض الأحيان، ينتج عن تجميع الأصفار تعبير منطقي يتطلب بوابات أقل أو مدخلات أقل مقارنة بتجميع الآحاد.
يمنح هذا مصممي الدوائر الرقمية مرونة لاختيار التنفيذ الأقل تكلفة (SOP أو POS) بناءً على طبيعة الدالة.
Why use POS? Sometimes the complement of a function yields fewer terms or literals than the function itself.
By evaluating both SOP (grouping 1s) and POS (grouping 0s and complementing), designers can choose the hardware implementation that requires the fewest gates and inputs, optimizing cost and delay.
| SOP | POS | |
|---|---|---|
| التجميع في خريطة كارنوف Grouping in K-map | تجميع الآحاد (1s) Grouping 1s | تجميع الأصفار (0s) ثم أخذ المتمم Grouping 0s then complementing |
| البوابات الأساسية المستخدمة Basic Gates Used | AND ثم OR AND then OR | OR ثم AND OR then AND |
إذا كانت خريطة كارنوف تحتوي على عدد أصفار أقل بكثير من الآحاد، فأي صيغة ستكون الأبسط غالباً: SOP أم POS؟ If a K-map has significantly fewer 0s than 1s, which form will likely be simpler: SOP or POS?
صيغة POS ستكون الأبسط، لأن تجميع عدد قليل من الأصفار سينتج عنه حدود أقل في F'، مما يؤدي إلى تعبير POS أقصر.
The POS form will likely be simpler. Fewer 0s mean fewer groups for F', resulting in a shorter POS expression after applying DeMorgan's.
2 حالات عدم الاكتراث (Don't Care)
2 Don't Care Conditions
حالات لا يمكن أن تحدث في الواقع (مثل الأرقام 10-15 في نظام BCD)، نرمز لها بـ 'X' ونستخدمها كـ 0 أو 1 لتبسيط الدائرة.
Input combinations that never occur are marked as 'X' and can be treated as 0 or 1 to optimize logic gates.
في بعض الأنظمة الرقمية، هناك تركيبات من المدخلات لا تحدث أبداً. على سبيل المثال، في نظام BCD (الذي يستخدم 4 بتات لتمثيل الأرقام من 0 إلى 9)، الحالات من 1010 إلى 1111 لا تظهر أبداً.
نطلق على هذه الحالات اسم 'حالات عدم الاكتراث' ونرمز لها بالحرف 'X' في خريطة كارنوف.
عند التبسيط، يمكننا اختيار اعتبار الـ 'X' كـ 1 إذا كان ذلك سيساعدنا في تكوين مجموعة أكبر (وبالتالي تبسيط أكثر)، أو نعتبره 0 إذا لم يكن مفيداً.
In some digital systems, certain input conditions never occur. For example, dealing with BCD (Binary Coded Decimal), 4 bits can encode 16 items, but we only care about the first 10 (0000 to 1001).
The remaining states (1010 to 1111) are 'don't care' conditions, marked with an 'X' in the K-map.
We can treat an 'X' as either a 1 or a 0, whichever leads to a simpler implementation by allowing larger groupings.
من الناحية الفيزيائية، الدائرة لا تخرج 'X'؛ بل ستخرج دائماً إما 0 أو 1.
الـ 'X' هي مجرد أداة تصميمية تمنح المهندس حرية اختيار المخرج الذي يقلل من تعقيد الأجهزة.
بمجرد بناء الدائرة، ستأخذ حالات الـ 'X' التي تم تضمينها في المجموعات قيمة 1، والتي تم تجاهلها قيمة 0.
Physically, logic gates do not output an 'X'; they always output a deterministic 0 or 1.
The 'X' is purely a design abstraction that gives the engineer the freedom to assign an output that minimizes hardware complexity.
Once the circuit is built, the 'X's included in K-map groups will physically output 1, and those left out will output 0.
هل يجب علينا تجميع كل علامات 'X' في خريطة كارنوف؟ Do we have to group all the 'X's in a K-map?
لا، نجمع فقط علامات 'X' التي تساعدنا في تكوين مجموعات أكبر مع الآحاد. أي 'X' لا يفيد في التبسيط نتركه (ونعتبره 0).
No, we only group the 'X's that help us form larger groups with the 1s. Any 'X' that doesn't help simplify the expression is left ungrouped (treated as 0).
3 البوابات الشاملة (NAND و NOR)
3 Universal Gates (NAND and NOR)
بوابات NAND و NOR تسمى بوابات شاملة لأنه يمكن بناء أي دائرة رقمية باستخدام نوع واحد منها فقط.
NAND and NOR are universal gates because any digital circuit can be built using only one of these types.
تعتبر بوابة NAND وبوابة NOR بوابات 'شاملة' (Universal). هذا يعني أن أي دائرة رقمية يمكن تصميمها وتنفيذها باستخدام بوابات NAND فقط، أو بوابات NOR فقط.
لإثبات ذلك، يكفي أن نثبت أن بوابة NAND قادرة على محاكاة عمل بوابات AND و OR و NOT الأساسية.
تُفضل هذه البوابات في الصناعة لأنها أسهل وأرخص في التصنيع باستخدام تقنية CMOS.
NAND and NOR gates are considered 'Universal'. This means any digital circuit can be designed and realized using only NAND gates, or only NOR gates.
To prove a gate is universal, we only need to show it can emulate the basic AND, OR, and NOT gates.
Digital circuits are frequently constructed with only NAND or NOR implementations because they are easier to fabricate using CMOS technology.
في تقنية CMOS، الترانزستورات تعكس الإشارة بشكل طبيعي. بناء بوابة NAND يتطلب 4 ترانزستورات فقط، بينما بناء بوابة AND يتطلب 6 ترانزستورات (بوابة NAND متبوعة بعاكس NOT).
لذلك، استخدام منطق NAND بالكامل يوفر مساحة السيليكون ويقلل من استهلاك الطاقة وتأخير الإشارة.
In CMOS technology, transistors naturally act as inverters. A NAND gate requires only 4 transistors, whereas an AND gate requires 6 (a NAND gate followed by a NOT gate).
Therefore, mapping a circuit entirely to NAND logic saves silicon area, reduces power consumption, and minimizes propagation delay.
| NAND | NOR | |
|---|---|---|
| العملية المنطقية Logical Operation | NOT AND NOT AND | NOT OR NOT OR |
| الشمولية (Universality) Universality | شاملة (يمكن بناء أي دائرة بها) Universal | شاملة (يمكن بناء أي دائرة بها) Universal |
كيف يمكن لبوابة NAND أن تعمل كبوابة OR؟ How can a NAND gate function as an OR gate?
بناءً على نظرية دي مورغان، إذا قمنا بعكس المدخلات قبل إدخالها إلى بوابة NAND، فإن النتيجة تكافئ بوابة OR.
Based on DeMorgan's theorem, inverting the inputs before feeding them into a NAND gate produces an OR function.
4 التحويل إلى دوائر NAND بالكامل
4 Conversion to all-NAND Circuits
لتحويل دائرة AND-OR إلى NAND، نستبدل البوابات ونضيف فقاعات (Bubbles)، ثم نلغي الفقاعات المتقابلة ونضيف عواكس للفقاعات الفردية.
To convert AND-OR to all-NAND, replace gates with NAND equivalents, check for uncompensated bubbles, and add inverters where needed.
الإجراء العام لتحويل مخطط AND-OR متعدد المستويات إلى مخطط NAND بالكامل هو:
- تحويل جميع بوابات AND إلى بوابات NAND (باستخدام رمز AND-NOT).
- تحويل جميع بوابات OR إلى بوابات NAND (باستخدام رمز NOT-OR).
- فحص جميع الفقاعات (Bubbles) في المخطط؛ كل فقاعة لا يتم تعويضها بفقاعة أخرى على نفس الخط تتطلب إدراج عاكس (Inverter) أو عكس المتغير المدخل.
The general procedure for converting a multi-level AND-OR diagram into an all-NAND diagram is:
- Convert all AND gates to NAND gates with AND-NOT graphic symbols.
- Convert all OR gates to NAND gates with NOT-OR graphic symbols.
- Check all the bubbles in the diagram. Every bubble that is not compensated by another along the same line will require the insertion of an inverter or complementing the input literal.
هذه الطريقة البصرية ('دفع الفقاعات') هي تطبيق مباشر لنظرية دي مورغان.
عندما نضع فقاعة على مخرج AND (لتصبح NAND) وفقاعة على مدخل OR (لتصبح NOT-OR، وهي تكافئ NAND)، فإن هاتين الفقاعتين على نفس السلك تلغيان بعضهما البعض (نفي النفي إثبات)، مما يحافظ على المنطق الأصلي للدائرة دون تغيير.
This visual 'bubble pushing' method is a direct application of DeMorgan's theorem.
When we place a bubble on the output of an AND gate (making it NAND) and a bubble on the input of an OR gate (making it NOT-OR, which is equivalent to NAND), the two bubbles on the same wire cancel each other out (double negation), preserving the original Boolean logic.
ماذا نفعل إذا وجدنا فقاعة (Bubble) واحدة فقط على سلك يربط بين بوابتين؟ What do we do if we find only a single uncompensated bubble on a wire connecting two gates?
يجب علينا إضافة بوابة عاكس (NOT) على ذلك السلك، أو عكس المتغير المدخل إذا كان السلك متصلاً مباشرة بمدخل الدائرة، للحفاظ على المنطق الصحيح.
We must insert an inverter (NOT gate) on that line, or complement the input literal if it's an external input, to maintain the correct logic.
5 النماذج غير المتدهورة (Nondegenerate Forms)
5 Nondegenerate Forms
من بين 16 تركيبة لبوابات المستوى الأول والثاني، هناك 8 تركيبات لا تنهار إلى عملية واحدة، وتسمى النماذج غير المتدهورة.
Out of 16 possible two-level gate combinations, 8 do not collapse into a single operation; these are called nondegenerate forms.
بالنظر إلى 4 أنواع من البوابات (AND, OR, NAND, NOR)، لدينا 16 تركيبة ممكنة لمستويين من البوابات.
- بعض هذه التركيبات 'تتدهور' (Degenerate) إلى عملية واحدة (مثلاً AND-AND هي مجرد بوابة AND كبيرة).
- التركيبات الأخرى 'غير متدهورة' (Nondegenerate) وعددها 8، مثل AND-OR-INVERT و OR-AND-INVERT.
هذه النماذج مفيدة جداً في التنفيذ الفعلي للدوائر، خاصة عند استخدام 'المنطق السلكي' (Wired Logic) حيث يتم ربط مخارج البوابات معاً فيزيائياً.
Considering four types of gates (AND, OR, NAND, NOR), we have 16 combinations for first-level and second-level gates.
- Some combinations will degenerate to a single operation (e.g., AND-AND degenerates to just an AND operation).
- Other combinations are nondegenerate (cannot be folded into a single operation); we have 8 such combinations.
Examples include AND-OR-INVERT and OR-AND-INVERT, which are highly relevant in implementations using Wired Logic.
- تنفيذ AND-OR-INVERT (AOI) يتطلب إيجاد صيغة مجموع المضاريب (SOP) لمتمم الدالة.
- بينما تنفيذ OR-AND-INVERT (OAI) يتطلب إيجاد صيغة مضروب المجاميع (POS) لمتمم الدالة.
المنطق السلكي (Wired Logic) يسمح بتنفيذ هذه النماذج بعدد بوابات أقل عن طريق ربط المخارج معاً (مثل Wired-AND في بوابات TTL ذات المجمع المفتوح).
- The AND-OR-INVERT (AOI) implementation requires the Sum-of-Products (SOP) expression of the complement of the function.
- Conversely, OR-AND-INVERT (OAI) requires the Product-of-Sums (POS) expression of the complement.
Wired logic allows these forms to be implemented with fewer physical gates by tying outputs together (e.g., Wired-AND in open-collector TTL gates).
لماذا نعتبر تركيبة OR-OR تركيبة متدهورة (Degenerate)؟ Why is the OR-OR combination considered degenerate?
لأن مستويين من بوابات OR المتتالية يقومان بنفس وظيفة بوابة OR واحدة كبيرة، فلا يقدمان منطقاً ثنائي المستوى حقيقياً.
Because two successive levels of OR gates perform the exact same function as a single, larger OR gate, offering no true two-level logic capability.
6 بوابة الاستبعاد (XOR) والتكافؤ
6 Exclusive OR (XOR) and Parity
بوابة XOR تخرج 1 إذا كان عدد الآحاد في المدخلات فردياً، وتستخدم بشكل أساسي لاكتشاف الأخطاء عبر بت التكافؤ.
The XOR gate outputs 1 if an odd number of inputs are 1; it is primarily used for error detection via parity bits.
بوابة الاستبعاد المنطقي (XOR) هي عملية منطقية تخرج 1 إذا اختلفت المدخلات. لثلاثة متغيرات أو أكثر، تُعرف XOR بـ 'الدالة الفردية' (Odd Function)، حيث تساوي 1 فقط إذا كان عدد المتغيرات التي تساوي 1 فردياً.
هذه الخاصية تجعلها مثالية في الأنظمة الرقمية للعمليات الحسابية واكتشاف الأخطاء.
'بت التكافؤ' هو بت إضافي يُضاف إلى الرسالة لجعل إجمالي عدد الآحاد زوجياً (أو فردياً). يتم استخدام بوابات XOR لبناء 'مولد التكافؤ' عند الإرسال، و'فاحص التكافؤ' عند الاستقبال.
The Exclusive OR (XOR) is a logical operation that outputs 1 if the inputs differ. For three or more variables, XOR acts as an 'odd function', equaling 1 only if an odd number of variables are equal to 1.
This makes it highly useful in digital system design for arithmetic operations and error detection/correction.
A 'parity bit' is an extra bit added to a message to make the total number of 1s even (or odd). XOR gates are used to build parity generators (at the transmitter) and parity checkers (at the receiver).
نظام التكافؤ البسيط يمكنه اكتشاف أخطاء البت الواحد (Single-bit errors).
إذا انقلب بت واحد بسبب تشويش، سيتغير عدد الآحاد من زوجي إلى فردي، وسيقوم فاحص التكافؤ (المكون من بوابات XOR) بإخراج 1 للإشارة إلى وجود خطأ.
ومع ذلك، إذا انقلب بتان في نفس الوقت، سيبقى العدد زوجياً ولن يكتشف النظام الخطأ.
A simple parity system is excellent for detecting single-bit errors.
If noise flips one bit, the count of 1s changes from even to odd, and the parity checker (a cascade of XOR gates) will output a 1, flagging an error.
However, it cannot detect two-bit errors, because flipping two bits maintains the original even/odd parity state.
إذا استقبلنا البيانات 1011 مع بت تكافؤ زوجي (Even Parity)، هل يوجد خطأ؟ If we receive the data 1011 in an Even Parity system, is there an error?
نعم، يوجد خطأ. البيانات 1011 تحتوي على ثلاثة آحاد (عدد فردي)، بينما يتطلب التكافؤ الزوجي أن يكون إجمالي عدد الآحاد زوجياً.
Yes, there is an error. The data 1011 contains three 1s (an odd number), whereas an even parity system requires the total number of 1s to be even.