خريطة كارنو

في المثال أعلاه، يمكن دمج متغيرات الإدخال الأربعة بست عشرة طريقة مختلفة، لذا يحتوي جدول الحقيقة على ستة عشر صفًا، وخريطة كارنو على ستة عشر موضعًا. وبالتالي، تُرتّب خريطة كارنو في شبكة 4  ×  4.

يتم ترتيب مؤشرات الصفوف والأعمدة (الموضحة أعلى وأسفل الجانب الأيسر من خريطة كارنو) باستخدام ترميز غراي بدلاً من الترتيب العددي الثنائي. يضمن ترميز غراي أن متغيرًا واحدًا فقط يتغير بين كل زوج من الخلايا المتجاورة. تحتوي كل خلية في خريطة كارنو المكتملة على رقم ثنائي يمثل ناتج الدالة لتلك المجموعة من المدخلات.

بعد إنشاء خريطة كارنو، تُستخدم لإيجاد أحد أبسط الأشكال الممكنة - الشكل القياسي - للمعلومات الواردة في جدول الحقيقة. تمثل الآحاد المتجاورة في خريطة كارنو فرصًا لتبسيط التعبير. تُحدد الحدود الدنيا (minterms) للتعبير النهائي بتطويق مجموعات الآحاد في الخريطة. يجب أن تكون مجموعات الحدود الدنيا مستطيلة الشكل، وأن تكون مساحتها قوة من قوى العدد اثنين (أي 1،  2،  4،  8، ...). ينبغي أن تكون مستطيلات الحدود الدنيا بأكبر حجم ممكن دون أن تحتوي على أي أصفار. يمكن أن تتداخل المجموعات لتكبير كل منها. تُحدد المجموعات المثلى في المثال أدناه بالخطوط الخضراء والحمراء والزرقاء، وتتداخل المجموعتان الحمراء والخضراء. المجموعة الحمراء عبارة عن مربع 2  ×  2، والمجموعة الخضراء عبارة عن مستطيل 4  ×  1، ومنطقة التداخل موضحة باللون البني.

غالبًا ما يُشار إلى الخلايا باختصار يصف القيمة المنطقية للمدخلات التي تغطيها الخلية. على سبيل المثال، AD تعني خلية تغطي مساحة 2x2 حيث تكون A و D صحيحتين، أي الخلايا المرقمة 13 و9 و15 و11 في الرسم التوضيحي أعلاه. من ناحية أخرى، A D تعني الخلايا حيث تكون A صحيحة و D خاطئة (أي أن D صحيحة).

الشبكة متصلة حلقيًا ، مما يعني أن المجموعات المستطيلة يمكن أن تمتد عبر الحواف (انظر الصورة). الخلايا الموجودة في أقصى اليمين "مجاورة" لتلك الموجودة في أقصى اليسار، بمعنى أن قيم الإدخال المقابلة لا تختلف إلا ببت واحد؛ وبالمثل، فإن الخلايا في الأعلى والخلايا في الأسفل متجاورتان. لذلك، يمكن أن يكون المصطلح AD صحيحًا - فهو يشمل الخليتين 12 و8 في الأعلى، ويمتد إلى الأسفل ليشمل الخليتين 10 و14 - وكذلك المصطلح B D ، الذي يشمل الزوايا الأربع.

بمجرد إنشاء خريطة كارنو وربط المربعات المستطيلة والمربعة المجاورة، يمكن إيجاد الحدود الجبرية الصغرى من خلال فحص المتغيرات التي تبقى كما هي داخل كل مربع.

بالنسبة للمجموعة الحمراء:

• A هو نفسه ويساوي 1 في جميع أنحاء المربع، لذلك يجب تضمينه في التمثيل الجبري للحد الأدنى الأحمر.
• لا يحتفظ B بنفس الحالة (ينتقل من 1 إلى 0)، وبالتالي يجب استبعاده.
• لا تتغير قيمة C. فهي دائمًا صفر، لذا يجب تضمين مكملتها، أي NOT-C. وبالتالي، يجب تضمين C.
• يتغير D ، لذلك يتم استبعاده.

وبالتالي فإن الحد الأدنى الأول في تعبير مجموع المنتجات المنطقية هو A C.

بالنسبة للمجموعة الخضراء، يحافظ كل من A و B على حالته، بينما يتغير كل من C و D. قيمة B تساوي صفرًا، ويجب نفيها قبل تضمينها. بالتالي، يكون الحد الثاني هو AB . لاحظ أنه من المقبول أن تتداخل المجموعة الخضراء مع المجموعة الحمراء.

وبالمثل، فإن المجموعة الزرقاء تعطي المصطلح BC D.

يتم دمج حلول كل مجموعة: الشكل الطبيعي للدائرة هو${\displaystyle A{\overline {C}}+A{\overline {B}}+BC{\overline {D}}}$.

وهكذا ساهمت خريطة كارنو في تبسيط

${\displaystyle {\begin{aligned}f(A,B,C,D)={}&{\overline {A}}BC{\overline {D}}+A{\overline {B}}\,{\overline {C}}\,{\overline {D}}+A{\overline {B}}\,{\overline {C}}D+A{\overline {B}}C{\overline {D}}+{}\\&A{\overline {B}}CD+AB{\overline {C}}\,{\overline {D}}+AB{\overline {C}}D+ABC{\overline {D}}\\={}&A{\overline {C}}+A{\overline {B}}+BC{\overline {D}}\end{aligned}}}$

كان من الممكن أيضًا استخلاص هذا التبسيط من خلال تطبيق بديهيات الجبر البولياني بعناية ، ولكن الوقت اللازم للقيام بذلك ينمو بشكل أسي مع عدد الحدود.

يتم حل معكوس الدالة بنفس الطريقة عن طريق تجميع الأصفار بدلاً من ذلك. ^{[ ملاحظة 1 ]}

تظهر الحدود الثلاثة التي تغطي المعكوس جميعها بمربعات رمادية ذات حدود ملونة مختلفة:

• بني : أ ب
• الذهب : أ ج
• أزرق : BCD

وهذا ينتج عنه العكس:

${\displaystyle {\overline {f(A,B,C,D)}}={\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+BCD}$

باستخدام قوانين دي مورغان ، يمكن تحديد حاصل ضرب المجاميع :

${\displaystyle {\begin{aligned}f(A,B,C,D)&={\overline {\overline {f(A,B,C,D)}}}\\&={\overline {{\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+BCD}}\\&=\left({\overline {{\overline {A}}\,{\overline {B}}}}\right)\left({\overline {{\overline {A}}\,{\overline {C}}}}\right)\left({\overline {BCD}}\right)\\&=\left(A+B\right)\left(A+C\right)\left({\overline {B}}+{\overline {C}}+{\overline {D}}\right)\end{aligned}}}$

تُسهّل خرائط كارنو أيضًا تبسيط الدوال التي تتضمن جداول الحقيقة فيها شروطًا " غير مهمة ". الشرط "غير المهم" هو مجموعة من المدخلات التي لا يهتم المصمم بمخرجاتها. لذلك، يمكن تضمين الشروط "غير المهمة" في أي مجموعة مستطيلة أو استبعادها منها، أيهما يزيد حجمها. وعادةً ما يُشار إليها على الخريطة بشرطة أو علامة X.

المثال على اليمين هو نفسه المثال أعلاه، ولكن مع استبدال قيمة f (1,1,1,1) بـ "لا يهم". هذا يسمح للحد الأحمر بالامتداد إلى أسفل بالكامل، وبالتالي، يزيل الحد الأخضر تمامًا.

وهذا ينتج عنه معادلة الحد الأدنى الجديدة:

${\displaystyle f(A,B,C,D)=A+BC{\overline {D}}}$

لاحظ أن الحد الأول هو A فقط ، وليس AC . في هذه الحالة، قام "لا يهم " بإسقاط حد (المستطيل الأخضر)؛ وتبسيط حد آخر (المستطيل الأحمر)؛ وإزالة خطر التنافس (إزالة الحد الأصفر كما هو موضح في القسم التالي حول مخاطر التنافس).

أما الحالة العكسية فتُبسط على النحو التالي:

${\displaystyle {\overline {f(A,B,C,D)}}={\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+{\overline {A}}D}$

باستخدام قوانين دي مورغان ، يمكن تحديد حاصل ضرب المجاميع :

${\displaystyle {\begin{aligned}f(A,B,C,D)&={\overline {\overline {f(A,B,C,D)}}}\\&={\overline {{\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+{\overline {A}}\,D}}\\&=\left({\overline {{\overline {A}}\,{\overline {B}}}}\right)\left({\overline {{\overline {A}}\,{\overline {C}}}}\right)\left({\overline {{\overline {A}}\,D}}\right)\\&=\left(A+B\right)\left(A+C\right)\left(A+{\overline {D}}\right)\end{aligned}}}$

تُعدّ خرائط كارنو مفيدةً في اكتشاف حالات التزامن غير المتزامن والقضاء عليها . يسهل رصد مخاطر التزامن غير المتزامن باستخدام خريطة كارنو، إذ قد تحدث حالة التزامن غير المتزامن عند الانتقال بين أي زوج من المناطق المتجاورة، ولكن المنفصلة، ​​والمحددة على الخريطة. مع ذلك، ونظرًا لطبيعة ترميز غراي، فإنّ مصطلح " متجاور" له تعريف خاص كما هو موضح أعلاه - فنحن في الواقع نتحرك على سطح حلقي، وليس مستطيلًا، ملتفًا حول الجزء العلوي والسفلي والجوانب.

• في المثال أعلاه ، توجد حالة تنافس محتملة عندما تكون قيمتا C و D صفرًا، وقيمة A واحدًا، وتتغير قيمة B من 1 إلى 0 (أي تنتقل من الحالة الزرقاء إلى الحالة الخضراء). في هذه الحالة، يُفترض أن يبقى الناتج ثابتًا عند 1، ولكن نظرًا لأن هذا الانتقال غير مشمول بحدٍّ محدد في المعادلة، فهناك احتمال لحدوث خلل (انتقال مؤقت للناتج إلى 0).
• يوجد خلل محتمل ثانٍ في المثال نفسه، وهو أكثر صعوبة في اكتشافه: عندما تكون قيمة D تساوي 0، وقيمتا A و B تساويان 1، وتتغير قيمة C من 1 إلى 0 (أي تنتقل من الحالة الزرقاء إلى الحالة الحمراء). في هذه الحالة، يمتد الخلل من أعلى الخريطة إلى أسفلها.

يعتمد حدوث الأعطال فعليًا على طبيعة التنفيذ الفيزيائية، وتعتمد الحاجة إلى القلق بشأنها على التطبيق. في الدوائر المنطقية المعتمدة على التوقيت، يكفي أن تستقر الدائرة على القيمة المطلوبة في الوقت المناسب للوفاء بالموعد النهائي. في مثالنا، لا نأخذ الدوائر المنطقية المعتمدة على التوقيت في الاعتبار.

في حالتنا، مصطلح إضافي من${\displaystyle A{\overline {D}}}$سيؤدي ذلك إلى القضاء على خطر التنافس المحتمل، والربط بين حالات الإخراج الخضراء والزرقاء أو حالات الإخراج الزرقاء والحمراء: يظهر هذا على شكل المنطقة الصفراء (التي تلتف من أسفل إلى أعلى النصف الأيمن) في الرسم التخطيطي المجاور.

إن هذا المصطلح زائد عن الحاجة من حيث المنطق الثابت للنظام، ولكن غالبًا ما تكون هناك حاجة إلى مثل هذه المصطلحات الزائدة أو مصطلحات التوافق لضمان الأداء الديناميكي الخالي من التنافس.

وبالمثل، مصطلح إضافي من${\displaystyle {\overline {A}}D}$يجب إضافته إلى المعكوس لإزالة خطر سباق محتمل آخر. يؤدي تطبيق قوانين دي مورغان إلى إنشاء تعبير آخر لمجموع المجاميع لـ f ، ولكن مع عامل جديد هو${\displaystyle \left(A+{\overline {D}}\right)}$.

فيما يلي جميع خرائط كارنو الممكنة ذات المتغيرين، 2  ×  2. ويُدرج مع كل خريطة الحدود الصغرى كدالة لـ${\textstyle \sum m()}$والمعادلة الدنيا الخالية من مخاطر التنافس ( انظر القسم السابق ). يُعرَّف الحد الأدنى بأنه تعبير يُعطي أبسط شكل ممكن للتعبير عن المتغيرات المُرتبطة. يمكن تكوين جميع الكتل المترابطة أفقيًا ورأسيًا. يجب أن يكون حجم هذه الكتل من قوى العدد 2 (1، 2، 4، 8، 16، 32، ...). تُنشئ هذه التعبيرات تعيينًا منطقيًا أدنى لتعبيرات المتغيرات المنطقية الدنيا للتعبيرات الثنائية المراد تعيينها. فيما يلي جميع الكتل ذات الحقل الواحد.

يمكن تمديد الكتلة عبر أسفل المخطط أو أعلاه أو يمينه أو يساره. بل ويمكن أن تمتد خارج حافة المخطط لتقليل عدد المتغيرات. وذلك لأن كل متغير منطقي يقابل عمودًا رأسيًا وصفًا أفقيًا. يمكن اعتبار تمثيل خريطة كارنو أسطوانيًا، حيث تكون الحقول عند الحواف اليسرى واليمنى متجاورة، وكذلك عند الحواف العلوية والسفلية. يجب تمثيل خرائط كارنو لأربعة متغيرات على شكل حلقة دائرية أو طارة، حيث تكون زوايا المربع المرسوم بواسطة خريطة كارنو الأربع متجاورة. أما الخرائط الأكثر تعقيدًا فتتطلب خمسة متغيرات أو أكثر.

• 
  Σ m (0)؛ K = 0
• 
  Σ m (1)؛ K = A ′ B ′
• 
  Σ m (2)؛ K = AB ′
• 
  Σ m (3)؛ K = A ′ B
• 
  Σ m (4)؛ K = AB
• 
  Σ m (1,2)؛ K = B ′
• 
  Σ m (1,3)؛ K = A ′
• 
  Σ m (1,4)؛ K = A ′ B ′ + AB
• 
  Σ m (2,3)؛ K = AB ′ + A ′ B
• 
  Σ m (2,4)؛ K = A
• 
  Σ m (3,4)؛ K = B
• 
  Σ m (1,2,3)؛ K = A' + B ′
• 
  Σ m (1,2,4)؛ K = A + B ′
• 
  Σ m (1,3,4)؛ K = A ′ + B
• 
  Σ m (2,3,4)؛ K = A + B
• 
  Σ m (1,2,3,4)؛ K = 1