التصميم الرقمي · خرائط كارنو والتجميع الملتف

#06 تبسيط دالة ذات أربعة مداخل وتجميع ثماني خلايا إلى متممة B

استعمل تجاور Gray والتجميع المستطيل والتفاف الحواف لاختزال دالة ذات أربعة مداخل إلى متغير منطقي متمم واحد.

السؤال

إطار كامل من الفيديو العربي الأصلي يوضح عناوين خريطة كارنو أو التجاور عبر الحواف أو تجميع الثماني خلايا ونتيجته B المتممة. — الصفوف AB والأعمدة CD بترتيب Gray الدوري 00 و01 و11 و10. في المثال يكون الصفان العلوي والسفلي متجاورين عبر الحافة ويحتويان ثماني قيم واحد. يبقى B صفرا، فتكون الدالة متممته.

اعمل على دالة بوليانية محددة الخرج لجميع تركيبات المداخل الثنائية المستقلة A وB وC وD. الصفوف AB والأعمدة CD، وكلا المحورين بترتيب Gray الدوري 00,01,11,10. فهرس minterm العددي هو 8A+4B+2C+D بالحساب الصحيح العادي، وN=2^4=16 هو عدد الخلايا. كل خلية تقابل تركيب مداخل واحدا، والعدد المكتوب فيها هو خرج الدالة لذلك التركيب. تظل الخلية ذات القيمة صفر مرتبطة بحد minterm؛ لا تخلط هوية الخلية مع قيمة الخرج فيها. الشاشات الأولية ذات الأصفار تشرح العناوين والتخطيط، وليست دالة المثال اللاحق. في العبارات البوليانية يعني الجمع OR الشامل، والنقطة AND، والشرطة العليا المتممة وليست مشتقة. يختلف الجيران أفقيا أو عموديا في بت واحد، بما في ذلك الحواف المتقابلة. لا يعد الجيران قطريا متجاورين بهذه القاعدة. العنوانان 01 و10 يختلفان في بتين. تفسر الهوية A·X+A'·X=(A+A')·X=X حذف المتغير عندما تأخذ قيمتاه مع شروط المتغيرات الأخرى نفسها. في SOP دون حالات لا مبالاة، يحتوي كل تجميع على خلايا الواحد فقط، ويكون مستطيلا على الخريطة الملتفة بأطوال أضلاع من 1 أو2 أو4. حجمه G=2^k لعدد صحيح k من صفر إلى أربعة؛ ويبقى في حده L=4−k من المتغيرات الثابتة. الخلية المعزولة تجميع من خلية واحدة، والخريطة الممتلئة بالواحد تجميع من ست عشرة خلية يمثل الدالة الثابتة واحد. غطّ كل خلايا الواحد، واسمح بالتداخل عند الحاجة. لا يكفي أن يكون عدد الخلايا قوة للعدد اثنين؛ يجب أن تمثل أيضا مستطيلا صحيحا تتغير داخله كل تركيبات المتغيرات المحذوفة. في رسم التجاور الخليتان المظللتان هما m0 وm2. تختلفان في C وحده، وتعطيان A'·B'·D'. يشير القوس المنحني إلى تجاور الحافتين، ولا يضم الأصفار الواقعة بين الخليتين على الورقة. في المثال الكامل تكون الدالة واحدا عند الفهارس 0,1,2,3,8,9,10,11 وصفر في غيرها. يحتوي الصف العلوي AB=00 الفهارس 0,1,3,2 بترتيب الأعمدة المعروض، ويحتوي الصف السفلي AB=10 الفهارس 8,9,11,10. الصفان متجاوران عبر الأعلى والأسفل ويشكلان مستطيلا ملتفا من صفين وأربعة أعمدة. حدهما A'·B'+A·B' يساوي B'. تتغير A وتأخذ C وD جميع تركيباتهما، بينما يبقى B صفرا. تحقق من التركيبـات الستة عشر. الدالة غير ثابتة، لذلك لا تمثل بحد ثابت بلا متغيرات، بينما يمثلها متغير متمم واحد؛ هذه النتيجة بالذات دنيا في عدد المتغيرات المنطقية. ابحث عموما عن تجميعات صحيحة لا يمكن توسيعها، ثم اختر غطاء لكل خلايا الواحد. البدء بأكبر تجميع وحده لا يثبت أن اختيارا جشعا يعطي أقل عدد حدود أو أقل عدد متغيرات لكل دالة؛ قد تلزم مقارنة التجميعات الأساسية والأغطية البديلة. لا تضم صفرا ولا تخترع حالات لا مبالاة لتكبير التجميع. يحفظ التبسيط الدالة المستقرة، ولا يضمن وحده تأخيرا فيزيائيا محددا أو غياب أخطار عابرة. تعني شمولية NAND أو NOR إمكان استعمال شبكة من عدة بوابات وتوصيلات مناسبة من عائلة واحدة، ولا تعني أن بوابة منفردة تنفذ كل دالة.

الحل المكتوب ونص الشرح(يعرض الحل كاملًا)

تجد أدناه جميع الأسطر المكتوبة في الدفتر مع النص الكامل للشرح الصوتي.

1. من جدول الحقيقة إلى الخريطة
الصفوف AB والأعمدة CD بترتيب Gray الدوري 00 و01 و11 و10. في المثال يكون الصفان العلوي والسفلي متجاورين عبر الحافة ويحتويان ثماني قيم واحد. يبقى B صفرا، فتكون الدالة متممته.
تمثل خريطة كارنو الدالة نفسها التي يمثلها جدول الحقيقة.
تعيد الخريطة ترتيب تركيبات المداخل كي يصبح الجيران المختلفون في بت واحد متجاورين.
عدد خلايا خريطة ذات أربعة مداخل ثنائية:
$\displaystyle N = 2^{4} = 16$
فهرس الصف الثنائي بالحساب العددي:
$\displaystyle m = 8\cdot A+4\cdot B+2\cdot C+D$
يتغير ترتيب العرض، بينما تبقى الدالة البوليانية نفسها.
نص الشرح الصوتي
خريطة كارنوف ما زالت truth table. إنها تعيد ترتيب الصفوف داخل شبكة، كي يصبح الجيران المفيدون متجاورين. كل خلية تمثل minterm واحدا دقيقا: تركيبة واحدة للمدخلات، وقيمة خرج واحدة محتملة. في خريطة ذات أربعة متغيرات نسمي الصفوف A و B، ونسمي الأعمدة C و D. خريطة كارنوف ليست قاعدة Boolean جديدة، بل هي هندسة أفضل لرؤية الحدود التي يمكن دمجها.
2. ترتيب Gray والتجاور
الصفوف AB والأعمدة CD بترتيب Gray الدوري 00 و01 و11 و10. في المثال يكون الصفان العلوي والسفلي متجاورين عبر الحافة ويحتويان ثماني قيم واحد. يبقى B صفرا، فتكون الدالة متممته.
ترتيب العناوين على كل محور هو أساس التجاور المفيد.
استعمل الترتيب الدوري 00 ثم 01 ثم 11 ثم 10.
هذا ترتيب Gray؛ يختلف كل عنوانين متتاليين، ومنهما الأخير والأول، في بت واحد.
يغير الانتقال الأفقي أو العمودي بتا واحدا؛ الانتقال القطري لا يحقق هذا التجاور.
يضع الترتيب الثنائي العادي 01 بجوار 10 مع أنهما يختلفان في بتين.
احتفظ بترتيب Gray على محوري خريطة المداخل الأربعة.
حذف المتغير الذي يأخذ القيمتين مع الشروط الأخرى نفسها:
$\displaystyle Y = A\cdot X+A'\cdot X = X$
نص الشرح الصوتي
الترتيب على كل محور هو الحيلة الأساسية. نكتب صفر صفر، صفر واحد، واحد واحد، واحد صفر. وهذا هو ترتيب Gray code. عندما نتحرك خلية واحدة إلى اليسار أو اليمين أو الأعلى أو الأسفل، يتغير بت دخل واحد فقط. الترتيب الثنائي العادي سيضع صفر واحد بجوار واحد صفر، مع أن البتين يتغيران. ترتيب Gray يمنع هذا الخطأ. وعندما تختلف خليتان متجاورتان قيمتهما واحد في متغير واحد فقط، يمكن حذف ذلك المتغير من الحد المبسط.
3. قواعد التجميع والالتفاف
الصفوف AB والأعمدة CD بترتيب Gray الدوري 00 و01 و11 و10. في المثال يكون الصفان العلوي والسفلي متجاورين عبر الحافة ويحتويان ثماني قيم واحد. يبقى B صفرا، فتكون الدالة متممته.
في SOP اجمع الخلايا التي يكون خرج الدالة فيها واحدا.
حجم التجميع المستطيل الصحيح، حيث k عدد صحيح من صفر إلى أربعة:
$\displaystyle G = 2^{k}$
عدد المتغيرات الثابتة الباقية في حد تجميع أربعة مداخل:
$\displaystyle L = 4-k$
يمكن أن تتداخل التجميعات عندما يفيد ذلك في تغطية كل خلايا الواحد.
تلتف الخريطة عبر الحواف المتقابلة.
العمود الأول مجاور للأخير، والصف الأول مجاور للأخير أيضا.
نص الشرح الصوتي
في خريطة sum of products نجمع الخلايا التي يكون خرجها واحدا. يجب أن يحتوي كل تجميع على عدد من الخلايا يساوي قوة للعدد اثنين: خلية واحدة، أو خليتين، أو أربع، أو ثماني، أو ست عشرة خلية. يجب أن يكون التجميع مستطيلا وأن يكون بأكبر حجم تسمح به خلايا الواحد. ويمكن أن تدخل الخلية في أكثر من تجميع إذا أعطى ذلك نتيجة أكبر أو أبسط. والقاعدة المفاجئة هي أن الخريطة تلتف عند الحواف. فالعمود الأول مجاور للأخير، والصف الأول مجاور للأخير أيضا.
4. مثال تجميع ثماني خلايا
الصفوف AB والأعمدة CD بترتيب Gray الدوري 00 و01 و11 و10. في المثال يكون الصفان العلوي والسفلي متجاورين عبر الحافة ويحتويان ثماني قيم واحد. يبقى B صفرا، فتكون الدالة متممته.
بسّط المثال الكامل ذا المداخل الأربعة.
فهارس خلايا الواحد هي 0 و1 و2 و3 و8 و9 و10 و11.
ضع هذه القيم الثماني في الخريطة ذات الست عشرة خلية، واجعل بقية الخلايا صفرا.
حدا الصف العلوي والصف السفلي:
$\displaystyle F = A'\cdot B'+A\cdot B'$
يتجاور الصفان العلوي والسفلي عبر حد الخريطة.
ادمجهما في تجميع واحد ملتف من ثماني خلايا.
نص الشرح الصوتي
لنُبسّط مثالا كاملا. افترض أن الدالة تساوي واحدا عند minterms صفر، واحد، اثنين، ثلاثة، ثمانية، تسعة، عشرة، وأحد عشر. ضع هذه القيم الثماني داخل خريطة المتغيرات الأربعة. إنها تملأ الصف العلوي حيث A B يساوي صفر صفر، والصف السفلي حيث A B يساوي واحد صفر. يبدو الصفان منفصلين على الورق، لكن خريطة كارنوف تصل بينهما عبر الحافتين العليا والسفلى. وهكذا يشكلان تجميعا ملتفا واحدا من ثماني خلايا.
5. قراءة الحد المبسط
الصفوف AB والأعمدة CD بترتيب Gray الدوري 00 و01 و11 و10. في المثال يكون الصفان العلوي والسفلي متجاورين عبر الحافة ويحتويان ثماني قيم واحد. يبقى B صفرا، فتكون الدالة متممته.
اقرأ ما يبقى ثابتا عبر التجميع كله.
تأخذ A القيمتين صفر وواحد داخل التجميع، ولذلك تحذف من الحد.
تأخذ C وD كل تركيباتهما، ولذلك تحذفان أيضا.
المدخل الوحيد الثابت في التجميع:
$\displaystyle B = 0$
نكتب المدخل الثابت عند الصفر متمما، فتكون النتيجة:
$\displaystyle F = B'$
تختصر ثمانية حدود minterm قياسية إلى متغير منطقي متمم واحد.
نص الشرح الصوتي
الآن اقرأ التجميع كله، لا الخلايا منفردة. عبر الخلايا الثماني تتغير A من صفر إلى واحد، ولذلك تختفي. كما تأخذ C و D كل القيم الممكنة، ولذلك تختفيان أيضا. المتغير الوحيد الثابت هو B، وقيمته تبقى صفرا. المتغير الثابت عند صفر يُكتب مكمّلا، لذلك يصبح التجميع كله B prime. هذه هي النتيجة: ثمانية minterms قياسية اختُصرت إلى literal واحد.
6. مراجعة خطوات خريطة كارنو
الصفوف AB والأعمدة CD بترتيب Gray الدوري 00 و01 و11 و10. في المثال يكون الصفان العلوي والسفلي متجاورين عبر الحافة ويحتويان ثماني قيم واحد. يبقى B صفرا، فتكون الدالة متممته.
طبق خطوات الخريطة على دالة بوليانية محددة الخرج لكل تركيب.
ضع قيم الواحد من جدول الحقيقة في عناوينها بترتيب Gray.
كوّن تجميعات مستطيلة صحيحة كبيرة، واستعمل التفاف الحواف عند الحاجة.
احتفظ بالمتغيرات الثابتة في كل تجميع، ثم اجمع حدود الجداء بعملية OR.
تحقق من العبارة الناتجة بمقارنتها مع جدول الحقيقة الكامل.
يمهد الدرس التالي لتنفيذ الدوال بشبكات من بوابات NAND وحدها أو NOR وحدها.
نص الشرح الصوتي
هذه هي خطوات K-map. ضع قيم الواحد من truth table بترتيب Gray code. كوّن أكبر تجميعات ممكنة بأحجام تساوي قوى العدد اثنين، واستخدم التفاف الحواف عندما يلزم. ثم احتفظ فقط بالمتغيرات التي تبقى ثابتة داخل كل تجميع. خرائط كارنوف تجعل تبسيط Boolean عملية بصرية يمكن التحقق منها. في الدرس التالي سنستخدم بوابتي NAND و NOR لبناء أي دالة Boolean من عائلة واحدة من البوابات الشاملة.