היום נדבר על מפת קרנו, נצמצם פונקציות, על גורמים ראשוניים וגוררים ראשוניים וצירופי ברירה.
בנוסף, נדבר על שהייה וחישוב שלה.

מפת קרנו

ראינו שאפשר לממש פונקציות בשערים לוגיים, אבל שער הוא בעל שטח ולוקח אנרגייה והנדל"ן מוגבל.
נרצה לממש פונקציות בתצורה היעילה ביותר!

מפת קרנו מורכבת:

$2^n$ משבצות עבור $n$ משתנים
כל משבצת מתאימה למינטרם או מקסטרם
סדר העמודות/שורות הוא לפי קוד גריי (קוד ציקלי)
לכל משבצת יש $n$ משבצות סמוכות

\begin{array}{c|c|c|c|c|} _{zw}\backslash^{xy} & {\mathbf{00}} & {\mathbf{01}} & {\mathbf{11}} & {\mathbf{10}} \\ \mathbf{00} & 0 & 4 & 12 & 8 \\ \mathbf{01} & 1 & 5 & 13 & 9 \\ \mathbf{11} & 3 & 7 & 15 & 11 \\ \mathbf{10} & 2 & 6 & 14 & 10 \\ \end{array}

הצמצום מתבצע לפי הכללים הבאים:

לסכום מכפלות: $Ax+Ax'=A$
למכפלות סכומים: $(A+x)(A+x')=A$

לדוגמה:
תרגול ספרתיות מפות קרנו 1.png

הגדרה 1 (גורר)

ליטרל או מכפלת ליטרלים המכוסה ע"י הפונקציה.

g \subseteq f \;\; if \;\; g=1\implies f=1

תרגול ספרתיות מפות קרנו 3.png

הגדרה 2 (גורר ראשוני)

גורר שכל השמטה של ליטרל ממנו יוצרת מכפלה שאינה מכוסה ע"י הפונקציה.

עבור הפונקציה $f=yw$ מתקיים כי:

\begin{matrix} \begin{array}{c|c|c|c|c|} _{zw}\backslash^{xy} & 00 & 01 & 11 & 10 \\ \hline 00 \\ \hline 01 & & {\color{red}1} & {\color{red}1} \\ \hline 11 & & {\color{red}1} & {\color{red}1} \\ \hline 10 \\ \hline \end{array} & \begin{array}{c|c|c|c|c|} _{zw}\backslash^{xy} & 00 & 01 & 11 & 10 \\ \hline 00 \\ \hline 01 & & {\color{red}1} & {\color{red}1} \\ \hline 11 & & 1 & 1 \\ \hline 10 \\ \hline \end{array} \\ yw & y{\color{red}z'}w \\ \R{\text{ראשוני!}} & \R{\text{לא ראשוני!}} \end{matrix}

הגדרה 3 (גורר ראשוני הכרחי)

גורר ראשוני המכסה מינטרם שאינו מכוסה ע"י אף גורר ראשוני אחר.

נניח בטבלה הבאה:

\begin{array}{c|c|c|c|c|} _{zw}\backslash^{xy} & 00 & 01 & 11 & 10 \\ \hline 00 & 1 \\ \hline 01 & 1 & 1 & 1 \\ \hline 11 & & 1 & 1 \\ \hline 10 \\ \hline \end{array}

הגוררים הראשונים ההכרחים הינם: $yw,x'y'z'$ , שהם הריבוע והפס בשמאל למעלה.

מציאת הצגה מינימלית

השיטה הולכת כך:

יצירת רשימה של כל הגוררים הראשוניים.
מציאת כל הגוררים הראשונים ההכרחיים והכנסתם לביטוי.
הוצאת כל הגוררים הראשונים ההכרחיים וכל הגוררים הראשונים שכוסו ע"י ההכרחיים מרשימת הגוררים.
אם קבוצת הגוררים הראשונים ההכרחיים מכסה את $f$ - סיימנו.
אחרת, נבחר את הגוררים הראשונים המינימליים, כך שכל הפונקציה תכוסה.

נתונה הפונקציה: $f(x,y,z)=\sum(0,1,2,4,5)$ . מצאו את סכום המכפלות ומכפלת הסכומים המינימלית:
4 - מפות קרנו ושהייה 2026-05-25 08.48.57.excalidraw.svg
נתחיל מהמינטרם ונרשום את כל הגורמים הראשוניים: $x'z',y'$ , נכניס את כל ההכרחיים לביטוי ואז נקבל כי כיסינו את $f$ כך:

f(x,y,z)=x'z'+y'

באותו הדרך, במכפלת סכומים נקבל:

f(x,y,z)=(z'+y')(y'+x')

נצמצם כעת את הפונקציה הבאה: $f(w,x,y,z)=\sum(0,1,2,4,5,7,10,11,14,15)$ ונמצא את כל הכיסויים המינימליים כסכום מכפלות.

\begin{align*} PI: \;\;& \overline{w}xz,xyz,\overline{w}\ \!\overline{x}\ \!\overline{z},\overline{x}y\overline{z},wy \\ EPI: \;\;& \overline{w}\ \! \overline{y} \end{align*}

כעת נוכל לכסות את המפה ונקבל את הפונקציות הבאות:
[להשלים אחרי התרגול[שקף 16]]

תרגיל

נתונה הפונקציה: $f(w,x,y,z)=x(w+y)+z+\overline{x}(\overline{y}+w\overline{z})$ .
מצאו ביטוי מינימלי ל- $\overline{f}$ .

נפתח סוגריים:

f(w,x,y,z)=xw+xy+z+\overline{x}\ \!\overline{y}+\overline{x}w\overline{z}

כעת, נציב במפת קרנו ונבחר את האפסים כאחדים :)
4 - מפות קרנו ושהייה 2026-05-25 09.00.27.excalidraw.svg

הגדרה 4 (צירופי ברירה -

\varnothing

)

צירופים שבהם הפונקציה אינה מוגדרת וניתן להגדירם כ- $0$ או $1$ כרצוננו.

אם נכסה צירוף ברירה תתקבל בסוף הליך צמצום הפונקציה שונה מאשר אם לא היינו מכסים אותו, אך שתי הפונקציות נכונות. כלומר, שתיהן מייצגות נכון את הצירופים שבהם הפונקציה מוגדרת.

תרגיל

מצאו ביטוי מינימלי לפונקציה:

f(w,x,y,z)=\sum(1,4,5,12)+\sum_{\varnothing}(0,3,8,15)

4 - מפות קרנו ושהייה 2026-05-25 09.06.27.excalidraw.svg
נבחר ששני צירופי הברירה העליונים יהיו $1$ בעוד ששני התחתונים יהיו $0$ כדי שנוכל לצמצם הכי טוב שאפשר:

f(w,x,y,z)=\overline{y}\ \!\overline{z}+\overline{w}\ \! \overline{y}=\sum(0,1,4,5,8,12)

תרגיל (אביב 2017 א')

נתון הרכיב הצירופי הבא:
4 - מפות קרנו ושהייה 2026-05-25 09.14.03.excalidraw.svg
ל- $f_{1}$ 4 כניסות ויציאה אחת. נתון שהמוצא של הרכיב $f_{1}$ יהיה $1$ אם ורק אם בכניסות שלו יהיו לפחות $3$ אחדים.
מהו הייצוג המינימלי של $f_{1}$ כסכום מכפלות עבור הרכיב הספציפי הזה?

נבנה מפת קרנו של האירוע הזה:
4 - מפות קרנו ושהייה 2026-05-25 09.10.24.excalidraw.svg

נשים לב כי החוט של $w$ זהה לחוט של $x$ ולכן הם תמיד יהיו שווים. לכן, לא איכפת לנו מה יקרה אם הם שונים כי זה בחיים לא יקרה ולכן שמנו שם צירוף ברירה.

PI:\; xz,wz,wy,xy

אין גורם הכרחי שכן כל 1 מכוסה לפחות על ידי שני ריבועים. לכן, נבנה 4 פונקציות:

\begin{matrix} f_{1}=xz+wy \\ f_{2}=xz+xy \\ f_{3}=wz+wy \\ f_{4}=wz+xy \end{matrix}

אלו כלון ייצוג של $f_{1}$ לאור צירופי הברירה, שכן אנו יכולים לבחור שהם 0 ו-1 מתי שאנו רוצים.

זמני שהייה של שערים לוגיים

שערים לוגיים הם רכיב פיזי ויש להם דיליי אופייני שאפשר לחשב.

הגדרה 5 (

t_{\tiny CD}

)

הזמן מתחילת ביצוע שינוי בכניסה במהלכו מובטח כי היציאה אינה משנה את ערכה הלוגי.

ההגדרה הזו היא קצת הזיה, אז בואו נסתכל על מה הולך.
מרגע שהגענו ל- $V_{IH}$ ישנו שינוי שמתרחש בשער וזאת עד שנגיע ל- $V_{IL}$ .
$t_{CD}$ מדבר על הזמן בין הרגע שהקלט מתחיל להשתנות לרגע שהפלט מתחיל להשתנות

הגדרה 6 (

t_{PD}

)

הזמן מרגע סיום ביצוע השינוי בכניסה שלאחריו מובטח כי היציאה התייצבה על ערכה הלוגי הסופי.

$t_{PD}$ מדבר על הזמן מרגע שהפלט מתחיל להשתנות ועד שהוא מתייצב בערכו הסופי.
תרגול ספרתיות מפות קרנו 4.png

דוגמה

נניח יש לנו שער $NAND$ עם $t_{cd}=5ns, t_{pd}=10ns$ .
תרגול ספרתיות מפות קרנו 5.png

סוגים של זמני שהייה

אנחנו מבדילים בין $t_{pdLH},t_{pdHL}$ שכן הזמן השהייה בין $0$ ל- $1$ שונה מזמן השהייה בין $1$ ל- $0$ .
בנוסף יש $glitch$ -ים מדי פעם והם מסומנים $t_{pdHH},t_{pdLL}$ .

\begin{matrix} t_{pd,H}=\max\left\{ t_{pdLH},t_{pdHH} \right\} \\ t_{pd,L}=\max\left\{ t_{pdHL},t_{pdLL} \right\} \\ t_{pd}=\max\left\{ t_{pdL},t_{pdH} \right\} \end{matrix}

דוגמה

אנו מעוניינים לחשב $t_{pdHL}$ עבור המסלול הבא:
תרגול ספרתיות מפות קרנו 6.png
כלומר, אנו מעוניינים לחשב את $t_{pd}$ כאשר היציאה עוברת מגבוה לנמוך.
שער 3 הוא שער $NAND$ שכניסותיו זהות. לכן, כשאנו עוברים מ- $H$ ל- $L$ בפלט אנו נדרש שקלט יעבור מ- $L$ ל- $H$ .
באותו האופן, השער השני הוא $OR$ ולכן, שתי כניסותיו יעברו מ- $L$ ל- $H$ שכן הן זהות.
השער הראשון הוא $NOT$ ולכן כניסותיו יעברו מ- $H$ ל- $L$ .
נתונה הטבלה הבאה לפיה נחשב:

\begin{array}{|c|c|c|} \hline & t_{pdLH} & t_{pdHL} \\ \hline NOT & 3 & 5 \\ OR & 4 & 2 \\ NAND & 3 & 4 \\ \hline \end{array}

t_{pdHL}(0\to 3)=t_{pdHL}(NAND)+t_{pdLH}(OR)+t_{pdLH}(NOT)=4+4+3=11 ns

כעת, אנו מעוניינים לחשב את $t_{pd}$ . לשם כך נדרש לחשב את $t_{pdLH}$ .

t_{pdLH}(0\to{3})=t_{pdLH}(NAND)+t_{pdHL}(OR)+t_{pdHL}(NOT)=3+2+5=10ns

t_{pd}=\max\left\{ 11ns,10ns \right\}=11ns

תרגיל

מצאו ביטוי ל- $t_{pd}(Z\to Q)$ בהנחה שרק כניסה $Z$ משתנה.
קבעו מהו ערכן של שאר הכניסות $Y,X$ שגורמות לשינוי במוצא $Q$ .
תרגול ספרתיות מפות קרנו 7.png

כדי לנעול את ה- $OR$ ואת ה- $NAND$ כדי שרק $Z$ ישפיע עליהם נקבע $X=0,Y=1$ .
כעת נתחיל מ- $LH$ שבשבילו הכניסה של $OR$ תבצע שינוי $LH$ ב- $NAND$ יתבצע שינוי $LH$ וב- $NOT$ יתבצע $HL$ ואז:

t_{pdLH}(Z\to Q)-t_{pdLH}(OR)+t_{pdLH}(NAND)+t_{pdHL}(NOT)

באותו האופן נחשב את $t_{pdHL}$ ואז נמצא באמצעות מקסימום.

תרגיל

מצאו ביטוי ל- $t_{pdHL}(X\to Q)$ וביטוי ל- $t_{pdLH}(X\to Q)$
תרגול ספרתיות מפות קרנו 8.png

נשים לב כי בסוף הפלט הוא $x$ שכן $\overline{\overline{x}}=x$ .
כאשר אנו משנים את $X$ מ- $0$ ל- $1$ הפלט יתעדכן ישר כש- $X$ יפגע בו שכן זה שער $OR$ . לכן:

t_{pdLH}=t_{pdLH}(OR)

בצד השני זה לא כזה פשוט, שכן השערים צריכים להתהפך כדי שב- $OR$ לא יהיה 1 מהצד של ה- $NOT$ .

t_{pdHL}=t_{pdLH}(NOT)+t_{pdHL}(NOT)+t_{pdHL}(OR)

זמן שהייה של פונקציה צירופית

הגדרה 7

זמן השהיה של כניסה $x_{0}$ הוא הזמן שנדרש מרגע שכניסה זו משתנה ועד שמוצא המערכת משתנה.
זאת כאשר שאר הכניסות קבועות.

זמן ההשהיה תלוי במימוש הפונקציה
יתכן זמן השהיה שונה מכניסה מסויימת למוצא בהתאם לערך ביתר הכניסות
יתכן שעבור ערכים בכניסות האחרות, כניסה $x_{0}$ לא תשנה את המוצא.

זמני ההשהיה מכניסה מסויימת נקבעים לפי המקרה הגרוע ביותר.
אנו נשתמש במפת קרנו כדי לראות אילו ערכים צריכים להיות ביתר הכניסות כדי ששינוי יתרחש.
תרגול ספרתיות מפות קרנו 9.5.png

תרגיל

נתונות הפונקציות הלוגיות הבאות:

S=x \oplus y \oplus C_{i}

C_{0}=xy+xC_{i}+yC_{i}

השתמשו בשערים הבאים למימוש המעגל:

\begin{array}{|c|c|c|} \hline & t_{pdLH} & t_{pdHL} \\ \hline \text{2 input AND} & 15 & 20 \\ \text{2 input OR} & 22 & 22 \\ \text{2 input XOR} & 30 & 23 \\ \hline \end{array}

תרגול ספרתיות מפות קרנו 10.png

נתחיל בלחפש $C_{i}\to C_{out}$ .
מה אנחנו רואים כשאנו מסתכים על המעגל הזה?

השער $OR$ לא איכפת לנו איזה שינוי הוא עושה.
ישנה סימטריה בין $x$ ל- $y$ .

ננחש ש- $t_{pd}(C_{i}\to C_{0})=t_{pdHL}(AND)+2t_{pd}(OR)=64 ns$ .
איך אנו יודעים שזה מסלול חוקי? נבחר $x=0$ ואז כיבינו את $u_{2}$ . נשים $y=1$ ואז נקבל בדיוק את המסלול שרצינו.
זה המקרה הגרוע שניחשנו והוא קיים ולכן אין צורך לבדוק עוד אפשרויות.

נותר לנו לעשות $C_{i}\to S$ .

אין לנו הרבה חופש בחירה
זה חייב לעבור דרך שער $XOR$ .
ה- $XOR$ המסומן $u_{6}$ לא משנה כלל כאשר $C_{i}$ משתנה שכן אין הוא תלוי בו.

ננחש את ה- $XOR_{LH}$ ואז: $t_{pd}(C_{i}\to S)=t_{pdLH}(XOR)=30ns$
המסלול הזה מתקיים כאשר $x=y=0$ ואז $u_{6}$ מחזיר $0$ .
אזי בהתחלה היו לנו $0$ בשתי הכניסות של $u_{7}$ ואז שינינו את $C_{i}$ ל- $1$ ולכן גם $u_{7}$ ישתנה.

כעת נדרש לבדוק גם כן עבור $x,y$ . - נבדוק רק עבור $x$ שכן $x,y$ סימטריים לחלוטין.

t_{pd}(x\to S)=2t_{pdLH}(XOR)=60ns

t_{pd}(x\to C_{0})=t_{pd}(C_{i}\to C_{0})=64ns

תרגיל

ממשו את הפונקציה הלוגית בעזרת שערי $NAND$ עם 2 כניסות בלבד.

C_{0}=xy+xC_{i}+yC_{i}

=\overline{\overline{xy}\cdot \overline{xC_{i}}}+yC_{i}=\overline{\overline{\overline{\overline{xy}\cdot \overline{xC_{i}}}}\cdot \overline{yC_{i}}}

D=NAND(NAND(x,y),NAND(x,C_{i}))

NOT(D)=NAND(D,D)

C_{0}=NAND(NOT(D),NAND(y,C_{i}))

תרגיל

ממשו את הפונקציה הלוגית בעזרת שערי $NAND$ עם 2 כניסות בלבד.

S=x \oplus y \oplus C_{i}=XOR(XOR(X,Y),C_{i})

XOR(a,b)=\overline{a}b+\overline{b}a=a\overline{a}+a\overline{b}+\overline{a}b+b\overline{b}=a(\overline{a}+\overline{b})+\overline{b}(a+b)=\overline{\overline{a(\overline{a}+\overline{b})+\overline{b}(a+b)}}

=\overline{\overline{a\overline{\overline{(\overline{a}+\overline{b})}}}\cdot \overline{b\cdot \overline{\overline{(\overline{a}+\overline{b})}}}}=\overline{\overline{a\cdot \overline{a\cdot b}}\cdot \overline{b\cdot \overline{a\cdot b}}}

S=NAND(NAND(a,NAND(a,b)), NAND(b, NAND(a,b)))

מפת קרנו

מפת קרנו מורכבת:

$2^n$ משבצות עבור $n$ משתנים
כל משבצת מתאימה למינטרם או מקסטרם
סדר העמודות/שורות הוא לפי קוד גריי (קוד ציקלי)
לכל משבצת יש $n$ משבצות סמוכות

\begin{array}{c|c|c|c|c|} _{zw}\backslash^{xy} & {\mathbf{00}} & {\mathbf{01}} & {\mathbf{11}} & {\mathbf{10}} \\ \mathbf{00} & 0 & 4 & 12 & 8 \\ \mathbf{01} & 1 & 5 & 13 & 9 \\ \mathbf{11} & 3 & 7 & 15 & 11 \\ \mathbf{10} & 2 & 6 & 14 & 10 \\ \end{array}

הצמצום מתבצע לפי הכללים הבאים:

לסכום מכפלות: $Ax+Ax'=A$
למכפלות סכומים: $(A+x)(A+x')=A$

לדוגמה:
תרגול ספרתיות מפות קרנו 1.png

הגדרה 1 (גורר)

ליטרל או מכפלת ליטרלים המכוסה ע"י הפונקציה.

g \subseteq f \;\; if \;\; g=1\implies f=1

תרגול ספרתיות מפות קרנו 3.png

הגדרה 2 (גורר ראשוני)

גורר שכל השמטה של ליטרל ממנו יוצרת מכפלה שאינה מכוסה ע"י הפונקציה.

עבור הפונקציה $f=yw$ מתקיים כי:

\begin{matrix} \begin{array}{c|c|c|c|c|} _{zw}\backslash^{xy} & 00 & 01 & 11 & 10 \\ \hline 00 \\ \hline 01 & & {\color{red}1} & {\color{red}1} \\ \hline 11 & & {\color{red}1} & {\color{red}1} \\ \hline 10 \\ \hline \end{array} & \begin{array}{c|c|c|c|c|} _{zw}\backslash^{xy} & 00 & 01 & 11 & 10 \\ \hline 00 \\ \hline 01 & & {\color{red}1} & {\color{red}1} \\ \hline 11 & & 1 & 1 \\ \hline 10 \\ \hline \end{array} \\ yw & y{\color{red}z'}w \\ \R{\text{ראשוני!}} & \R{\text{לא ראשוני!}} \end{matrix}

הגדרה 3 (גורר ראשוני הכרחי)

גורר ראשוני המכסה מינטרם שאינו מכוסה ע"י אף גורר ראשוני אחר.

נניח בטבלה הבאה:

\begin{array}{c|c|c|c|c|} _{zw}\backslash^{xy} & 00 & 01 & 11 & 10 \\ \hline 00 & 1 \\ \hline 01 & 1 & 1 & 1 \\ \hline 11 & & 1 & 1 \\ \hline 10 \\ \hline \end{array}

הגוררים הראשונים ההכרחים הינם: $yw,x'y'z'$ , שהם הריבוע והפס בשמאל למעלה.

מציאת הצגה מינימלית

השיטה הולכת כך:

יצירת רשימה של כל הגוררים הראשוניים.
מציאת כל הגוררים הראשונים ההכרחיים והכנסתם לביטוי.
הוצאת כל הגוררים הראשונים ההכרחיים וכל הגוררים הראשונים שכוסו ע"י ההכרחיים מרשימת הגוררים.
אם קבוצת הגוררים הראשונים ההכרחיים מכסה את $f$ - סיימנו.
אחרת, נבחר את הגוררים הראשונים המינימליים, כך שכל הפונקציה תכוסה.

f(x,y,z)=x'z'+y'

באותו הדרך, במכפלת סכומים נקבל:

f(x,y,z)=(z'+y')(y'+x')

נצמצם כעת את הפונקציה הבאה: $f(w,x,y,z)=\sum(0,1,2,4,5,7,10,11,14,15)$ ונמצא את כל הכיסויים המינימליים כסכום מכפלות.

\begin{align*} PI: \;\;& \overline{w}xz,xyz,\overline{w}\ \!\overline{x}\ \!\overline{z},\overline{x}y\overline{z},wy \\ EPI: \;\;& \overline{w}\ \! \overline{y} \end{align*}

כעת נוכל לכסות את המפה ונקבל את הפונקציות הבאות:
[להשלים אחרי התרגול[שקף 16]]

תרגיל

נתונה הפונקציה: $f(w,x,y,z)=x(w+y)+z+\overline{x}(\overline{y}+w\overline{z})$ .
מצאו ביטוי מינימלי ל- $\overline{f}$ .

נפתח סוגריים:

f(w,x,y,z)=xw+xy+z+\overline{x}\ \!\overline{y}+\overline{x}w\overline{z}

כעת, נציב במפת קרנו ונבחר את האפסים כאחדים :)
4 - מפות קרנו ושהייה 2026-05-25 09.00.27.excalidraw.svg

הגדרה 4 (צירופי ברירה -

\varnothing

)

צירופים שבהם הפונקציה אינה מוגדרת וניתן להגדירם כ- $0$ או $1$ כרצוננו.

תרגיל

מצאו ביטוי מינימלי לפונקציה:

f(w,x,y,z)=\sum(1,4,5,12)+\sum_{\varnothing}(0,3,8,15)

f(w,x,y,z)=\overline{y}\ \!\overline{z}+\overline{w}\ \! \overline{y}=\sum(0,1,4,5,8,12)

תרגיל (אביב 2017 א')

נבנה מפת קרנו של האירוע הזה:
4 - מפות קרנו ושהייה 2026-05-25 09.10.24.excalidraw.svg

PI:\; xz,wz,wy,xy

אין גורם הכרחי שכן כל 1 מכוסה לפחות על ידי שני ריבועים. לכן, נבנה 4 פונקציות:

\begin{matrix} f_{1}=xz+wy \\ f_{2}=xz+xy \\ f_{3}=wz+wy \\ f_{4}=wz+xy \end{matrix}

אלו כלון ייצוג של $f_{1}$ לאור צירופי הברירה, שכן אנו יכולים לבחור שהם 0 ו-1 מתי שאנו רוצים.

זמני שהייה של שערים לוגיים

שערים לוגיים הם רכיב פיזי ויש להם דיליי אופייני שאפשר לחשב.

הגדרה 5 (

t_{\tiny CD}

)

הזמן מתחילת ביצוע שינוי בכניסה במהלכו מובטח כי היציאה אינה משנה את ערכה הלוגי.

הגדרה 6 (

t_{PD}

)

הזמן מרגע סיום ביצוע השינוי בכניסה שלאחריו מובטח כי היציאה התייצבה על ערכה הלוגי הסופי.

$t_{PD}$ מדבר על הזמן מרגע שהפלט מתחיל להשתנות ועד שהוא מתייצב בערכו הסופי.
תרגול ספרתיות מפות קרנו 4.png

דוגמה

נניח יש לנו שער $NAND$ עם $t_{cd}=5ns, t_{pd}=10ns$ .
תרגול ספרתיות מפות קרנו 5.png

סוגים של זמני שהייה

\begin{matrix} t_{pd,H}=\max\left\{ t_{pdLH},t_{pdHH} \right\} \\ t_{pd,L}=\max\left\{ t_{pdHL},t_{pdLL} \right\} \\ t_{pd}=\max\left\{ t_{pdL},t_{pdH} \right\} \end{matrix}

דוגמה

\begin{array}{|c|c|c|} \hline & t_{pdLH} & t_{pdHL} \\ \hline NOT & 3 & 5 \\ OR & 4 & 2 \\ NAND & 3 & 4 \\ \hline \end{array}

t_{pdHL}(0\to 3)=t_{pdHL}(NAND)+t_{pdLH}(OR)+t_{pdLH}(NOT)=4+4+3=11 ns

כעת, אנו מעוניינים לחשב את $t_{pd}$ . לשם כך נדרש לחשב את $t_{pdLH}$ .

t_{pdLH}(0\to{3})=t_{pdLH}(NAND)+t_{pdHL}(OR)+t_{pdHL}(NOT)=3+2+5=10ns

t_{pd}=\max\left\{ 11ns,10ns \right\}=11ns

תרגיל

t_{pdLH}(Z\to Q)-t_{pdLH}(OR)+t_{pdLH}(NAND)+t_{pdHL}(NOT)

באותו האופן נחשב את $t_{pdHL}$ ואז נמצא באמצעות מקסימום.

תרגיל

מצאו ביטוי ל- $t_{pdHL}(X\to Q)$ וביטוי ל- $t_{pdLH}(X\to Q)$
תרגול ספרתיות מפות קרנו 8.png

t_{pdLH}=t_{pdLH}(OR)

בצד השני זה לא כזה פשוט, שכן השערים צריכים להתהפך כדי שב- $OR$ לא יהיה 1 מהצד של ה- $NOT$ .

t_{pdHL}=t_{pdLH}(NOT)+t_{pdHL}(NOT)+t_{pdHL}(OR)

זמן שהייה של פונקציה צירופית

הגדרה 7

זמן ההשהיה תלוי במימוש הפונקציה
יתכן זמן השהיה שונה מכניסה מסויימת למוצא בהתאם לערך ביתר הכניסות
יתכן שעבור ערכים בכניסות האחרות, כניסה $x_{0}$ לא תשנה את המוצא.

תרגיל

נתונות הפונקציות הלוגיות הבאות:

S=x \oplus y \oplus C_{i}

C_{0}=xy+xC_{i}+yC_{i}

השתמשו בשערים הבאים למימוש המעגל:

\begin{array}{|c|c|c|} \hline & t_{pdLH} & t_{pdHL} \\ \hline \text{2 input AND} & 15 & 20 \\ \text{2 input OR} & 22 & 22 \\ \text{2 input XOR} & 30 & 23 \\ \hline \end{array}

תרגול ספרתיות מפות קרנו 10.png

נתחיל בלחפש $C_{i}\to C_{out}$ .
מה אנחנו רואים כשאנו מסתכים על המעגל הזה?

השער $OR$ לא איכפת לנו איזה שינוי הוא עושה.
ישנה סימטריה בין $x$ ל- $y$ .

נותר לנו לעשות $C_{i}\to S$ .

אין לנו הרבה חופש בחירה
זה חייב לעבור דרך שער $XOR$ .
ה- $XOR$ המסומן $u_{6}$ לא משנה כלל כאשר $C_{i}$ משתנה שכן אין הוא תלוי בו.

כעת נדרש לבדוק גם כן עבור $x,y$ . - נבדוק רק עבור $x$ שכן $x,y$ סימטריים לחלוטין.

t_{pd}(x\to S)=2t_{pdLH}(XOR)=60ns

t_{pd}(x\to C_{0})=t_{pd}(C_{i}\to C_{0})=64ns

תרגיל

ממשו את הפונקציה הלוגית בעזרת שערי $NAND$ עם 2 כניסות בלבד.

C_{0}=xy+xC_{i}+yC_{i}

=\overline{\overline{xy}\cdot \overline{xC_{i}}}+yC_{i}=\overline{\overline{\overline{\overline{xy}\cdot \overline{xC_{i}}}}\cdot \overline{yC_{i}}}

D=NAND(NAND(x,y),NAND(x,C_{i}))

NOT(D)=NAND(D,D)

C_{0}=NAND(NOT(D),NAND(y,C_{i}))

תרגיל

ממשו את הפונקציה הלוגית בעזרת שערי $NAND$ עם 2 כניסות בלבד.

S=x \oplus y \oplus C_{i}=XOR(XOR(X,Y),C_{i})

XOR(a,b)=\overline{a}b+\overline{b}a=a\overline{a}+a\overline{b}+\overline{a}b+b\overline{b}=a(\overline{a}+\overline{b})+\overline{b}(a+b)=\overline{\overline{a(\overline{a}+\overline{b})+\overline{b}(a+b)}}

=\overline{\overline{a\overline{\overline{(\overline{a}+\overline{b})}}}\cdot \overline{b\cdot \overline{\overline{(\overline{a}+\overline{b})}}}}=\overline{\overline{a\cdot \overline{a\cdot b}}\cdot \overline{b\cdot \overline{a\cdot b}}}

S=NAND(NAND(a,NAND(a,b)), NAND(b, NAND(a,b)))

4 - מפות קרנו ושהייה

מערכות ספרתיות ומבנה המחשב

מפות קרנו ושהייה

4 - מפות קרנו ושהייה

מערכות ספרתיות ומבנה המחשב

מפות קרנו ושהייה

מפת קרנו

מציאת הצגה מינימלית

זמני שהייה של שערים לוגיים

סוגים של זמני שהייה

זמן שהייה של פונקציה צירופית

מפת קרנו

מציאת הצגה מינימלית

זמני שהייה של שערים לוגיים

סוגים של זמני שהייה

זמן שהייה של פונקציה צירופית