חזור לתיקייה: 00440252 - מערכות ספרתיות ומבנה המחשב

5 - מכונות מצבים סופיות(אוטומטים)

חיפוש בתיקיה
Ctrl K
לחץ כאן או הקש Ctrl K כדי לחפש בכל התיקיה
  • מכונת מצבים
  • סוגי מכונות מצבים
  • ביטוי רגולרי
  • תזמון במכונת מצבים
  • תכנון מערכת עקיבה
  • מגבלות מערכת עקיבה
  • גילוי שגיאות במערכת עקיבה
  • שיטת הסריקה
  • בדיקת זכרונות: BIST&BISR
  • צנרור (Pipeline)
  • ביצועים של מערכות ספרתיות
  • יוצרים מערכות מהירות
  • ההשפעה של ה-Pipeline

5 - מכונות מצבים סופיות(אוטומטים)

00440252

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

רשימות הרצאה לקריאה בשבת

מכונות מצבים סופיות(אוטומטים)

הופק מתוך תקיית התואר של שקד

uni-folder.vercel.app

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

מכונת מצבים

נבדיל בין שני סוגים של מערכות:

  1. מערכת צירופית: ערכי הפלט לתויים אך ורק בערכים הנוכחיים של משתני הקלט
  2. מערכת סדרתית: מערכת צירופית + זכרון הזוכר מצב. ערכי הפלט תלויים גם בערכי הקלט וגם במצב הקיים בזיכרון. ערכי המצב החדש תלויים גם הם בערכי הקלט ובמצב הקיים.

מערכת סדרתית/עקיבה נמצאת בכל רגע נתון ב"מצב" מסוים. המצב מיוצג ע"י ערכי הזיכרון של מערכת העקיבה.
המערכת יכולה לעבור ממצב אחד למצב אחר בתלות במצב ובכניסות.

  • המעבר הוא ממצב אחד לעוקב ולכן היא נקראת מערכת עקיבה.
  • ישנה סדרת מצבים ומעברים בין מצבים ולכן היא נקראת מערכת סדרתית

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

דוגמה

FlipFlopFlipFlopFlipFlop היא מערכת סנכרונית המיוצרת ממערכות לא סינכרוניות.

דוגמה (מנעול סדרתי)

נתון שסדרת הפתיחה של המנעול היא 803803803. קודם 888, אחר כך 000 ולבסוף 333.
נתכנן את המנעול בשלושה שלבים:

  1. כמה כניסות ומוצאים? הגדרת מוצא ZZZ: 000 נעול ו-111 פתוח.
  2. הגדרת מצבי זכרון
  3. שרטוט דיאגרמת מצבים

נגדיר שלושה מצבים:

  • מצב התחלתי AAA
  • הוכנס המספר 888 - מצב BBB
  • הוכנס המספר 000 - מצב CCC

יציאות אפשריות מהמכונה יהיו 000 נעול ו-111 פתוח.
המכונה ניתנת לתיאור ע"י דיאגרמת מצבים אשר על כל מעבר מסומנים הכניסה שגרמה לו ויציאה.
נסתכל על זה כעת:
​5 - מכונות מצבים סופיות(אוטומטים) 2026-06-02 15.45.08.excalidraw.svg

הגדרה 1 (MealyMealyMealy - מילי)

מכונת מילי היא תיאור סדרתי עקרוני בזמן מופשט

דוגמה (מסכם בינארי טורי)

נסתכל על טבלת האמת של מסכם בינארי טורי:

t5t4t3t2t1011000111011010    x1x2Z\begin{array}{ccccccc} t_{5} & t_{4} & t_{3} & t_{2} & t_{1} \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 \\ \hline 1 & 1 & 0 & 1 & 0 \end{array}\;\;\begin{array}{c} \\ x_{1} \\ x_{2} \\ Z \end{array}t5​001​t4​111​t3​110​t2​011​t1​000​​x1​x2​Z​

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

  • AAA שיהיה נשא 000.
  • BBB שיהיה נשא 1

נשרטט את דיאגרמת המצבים:
​5 - מכונות מצבים סופיות(אוטומטים) 2026-06-02 16.02.27.excalidraw.svg
נמיר את תיאור המכונה מדיאגרמת מצבים לטבלת מצבים אשר אותה נסדר לפי קוד גריי

PS00011110AA,0A,1B,0A,1BA,1B,0B,1B,0\begin{array}{|c|cccc|} \hline PS & 00 & 01 & 11 & 10 \\ \hline A & A,0 & A,1 & B,0 & A,1 \\ B & A,1 & B,0 & B,1 & B,0 \\ \hline \end{array}PSAB​00A,0A,1​01A,1B,0​11B,0B,1​10A,1B,0​​

כעת נפריד את הטבלה לטבלה המתארת את המצב הבא וטבלה המתארת את הפלט.
בנוסף נקצה ספרות לסימון המצבים כאשר A=0,B=1A=0,B=1A=0,B=1 ואז נקבל:

PS ∣   NS(Next  State)∣Z(Output)                    0001111000011110000100101101111010\begin{matrix} \begin{matrix} PS\ |\ \; NS(Next\;State)| & Z(Outpu{ t }) \;\;\;\;\;\;\;\;\;\; \end{matrix}\\ \begin{array}{|c|cccc|cccc|} \hline & 00 & 01 & 11 & 10 & 00 & 01 & 11 & 10 \\ \hline 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 1 & 1 & 0 & 1 & 0 \\ \hline \end{array} \end{matrix}PS ∣ NS(NextState)∣​Z(Output)​01​0000​0101​1111​1001​0001​0110​1101​1010​​​

נרצה כעת לחשב את פונקציית המעברים - ה-NSNSNS, ואת פונקציית התוצאה, ה-ZZZ.
נוכל לעשות זאת באמצעות מפת קרנו כך:
​ספרתיות הרצאת אוטומטים 1 - 1.png

NS=x1x2+PSx1+PSx2=C0Z=1⊕x2⊕PS=SumNS=x_{1}x_{2}+PSx_{1}+PSx_{2}=C_{0} \quad \quad \quad Z=1 \oplus x_{2} \oplus PS=SumNS=x1​x2​+PSx1​+PSx2​=C0​Z=1⊕x2​⊕PS=Sum

במימוש הרכיב האמיתי אנו נשתמש ב-DFFDFFDFF.
​ספרתיות הרצאת אוטומטים 1 - 2.png

דוגמה (גלאי מחרוזת)

נתכנן מערכת אשר לה כניסה אחת ויציאה אחת והיציאה היא 111 אם ורק אם מתגלה בכניסה המחרוזת 010101010101.
לצורך כך נדרש 444 מצבים:

  • AAA לא התחילה סדרה
  • BBB התחילה סדרה - 000
  • CCC קיבלנו 111 אחרי 000
  • DDD קיבלנו 000 אחרי ה-111.

נשרטט את הדיאגרמה שלנו:
​5 - מכונות מצבים סופיות(אוטומטים) 2026-06-02 16.44.04.excalidraw.svg
נבנה טבלת מצבים:

PSX=0X=1AB,0A,0BB,0C,0CD,0A,0DB,0C,1\begin{array}{|c|cc|} \hline PS & X=0 & X=1 \\ \hline A & B,0 & A,0 \\ B & B,0 & C,0 \\ C & D,0 & A,0 \\ D & B,0 & C,1 \\ \hline \end{array}PSABCD​X=0B,0B,0D,0B,0​X=1A,0C,0A,0C,1​​

נסמן A=00,B=01,C=11,D=10A=00,B=01,C=11,D=10A=00,B=01,C=11,D=10 לפי קוד גרי ואז נקבל:

PSNS(Y1Y2) ⁣ ⁣ ⁣ ⁣=D1D2Zy1y2X=0X=10001,000,00101,011,01110,000,01001,011,1\begin{array}{|c|cc|} \hline PS & NS(Y_{1}Y_{2}) &\!\!\!\! =D_{1}D_{2}Z \\ y_{1}y_{2} & X=0 & X=1 \\ \hline 00 & 01,0 & 00,0 \\ 01 & 01,0 & 11,0 \\ 11 & 10,0 & 00,0 \\ 10 & 01,0 & 11,1 \\ \hline \end{array}PSy1​y2​00011110​NS(Y1​Y2​)X=001,001,010,001,0​=D1​D2​ZX=100,011,000,011,1​​

ואז נוכל לראות מהן מפות הקרנו לכל אחד מהרכיבים. לדוגמה ל-D1D_{1}D1​ מתקיים:

y1y2X=0X=100011111101\begin{array}{|c|c|c|} \hline y_{1}y_{2} & X=0 & X=1 \\ \hline 00 \\ \hline 01 & & 1 \\ \hline 11 & 1 \\ \hline 10 & & 1 \\ \hline \end{array}y1​y2​00011110​X=01​X=111​​

וכך נוכל לבנות את פונקציות המעברים ופונקצית הפלט:

D1=xy1‾y2+x‾y1y2+xy1y2‾D2=x‾   ⁣y1‾+y1‾y2+y1y2‾Z=xy1y2‾\begin{align*} & D_{1}=x\overline{y_{1}}y_{2}+\overline{x}y_{1}y_{2}+xy_{1}\overline{y_{2}} \\ & D_{2}=\overline{x}\;\!\overline{y_{1}}+\overline{y_{1}}y_{2}+y_{1}\overline{y_{2}} \\ & Z=xy_{1}\overline{y_{2}} \end{align*}​D1​=xy1​​y2​+xy1​y2​+xy1​y2​​D2​=xy1​​+y1​​y2​+y1​y2​​Z=xy1​y2​​​

המימוש של גלאי המחרוזות יהיה כך:
​ספרתיות הרצאת אוטומטים 1 - 3.png

הערה

הקצאת מצבים שונה תביא למימוש שונה!

סוגי מכונות מצבים

מערכת עקיבה ממומשת ע"י מכונת מצבים סופית המוגדרת באמצעות:

  • קבוצה סופית של מצבים SSS אשר אחד מהם נקבע כהתחלתי
  • קבוצה סופית של כניסות בינאריות XXX
  • קבוצה סופית של יציאות בינאריות ZZZ
  • פונקציית מעבר λ:S×2x→2z\lambda:S\times2^x\to2^zλ:S×2x→2z
  • פונקציית היציאה ΩMEALY:S×2x→2z\Omega_{MEALY}: S\times 2^x\to 2^zΩMEALY​:S×2x→2z
  • תזמוני כניסה tS,tHt_{S},t_{H}tS​,tH​ ותזמוני יציאה tcC−Q,tpC−Qt_{cC-Q},t_{pC-Q}tcC−Q​,tpC−Q​

מכונת מצבים זו קרויה MealyMealyMealy. לעומתה, במכונת MooreMooreMoore פונקציית היציאה תלויה במצב הנוכחי בלבד. כלומר, ΩMOORE:S→2z\Omega_{MOORE}:S\to 2^zΩMOORE​:S→2z.

​ספרתיות הרצאת אוטומטים 1 - 4.png

המכונה MealyMealyMealy משמשת לתיאור תיאורתי והיא מוגבלת לגילוי מילים השייכות לשפה.
המכונה MooreMooreMoore תשומש לבניית מערכות מורכבות. היא מונעת מסלול צירופי מכניסה ליציאה.
בתהליכים אמיתיים בחומרה לא נרצה מכונות MealyMealyMealy שכן בהן יש מסלול צירופי ישיר מכניסה ליציאה ואז במקרה שאנו מחברים כמה מכונות ביחד, המעגל הצירופי באחת ימנע את כניסת הערך המתאים לשנייה שכן לא עבר מספיק זמן שה-FlipFlopFlipFlopFlipFlop יתעדכן. לכן, תמיד נשתמש במכונות MooreMooreMoore.

ישנן 444 דרכים להמיר מכונת MealyMealyMealy למכונת MooreMooreMoore:

  • תכנון מחדש כמכונת MooreMooreMoore
  • הוספת רגיסטרים בכניסה
  • הוספת רגיסטרים ביציאה
  • הוספת מצבים לטבלת המצבים היכן שהמוצא אינו זהה לכל החיצים היוצאים ממצב מסויים
הערה (ההמרה בפועל באמצעות הוספת מצבים)

במכונת MealyMealyMealy המוצא נקבע על גבי החץ בעוד שבמכונת MooreMooreMoore המוצא נקבע בתול המצב.

  1. אם כל החיצים שנכנסים למצב מסויים מוציאים את אותו פלט, אפשר פשוט להכניס את הפלט המתאים למצב.
  2. אם למצב נכנסים חיצים שמפיקים פלטים שונים, עלינו לפצל את המצב לשני מצבים חדשים אשר יתנו פלטים שונים.
  3. מזיזים את המוצאים אל תוך המצבים החדשים בצעד זמן אחד קדימה וכך מבטלים את התלות המיידית בקלט.

ביטוי רגולרי

מערכת סדרתית נתנת לתיאור מתמטי הנקרא ביטוי רגולרי.

יהי Σ\SigmaΣ א"ב. תחילה נרצה לגדיר קבוצת ביטויים רגולריים RΣR_{\Sigma}RΣ​ מעל Σ\SigmaΣ:
בסיס: ∅,ε\emptyset,\epsilon∅,ε הם ביטויים רגולריים. בנוסף, לכל σ∈Σ\sigma \in\Sigmaσ∈Σ: σ∈RΣ\sigma \in R_{\Sigma}σ∈RΣ​.
צעד: אם r1,r2∈RΣr_{1},r_{2} \in R_{\Sigma}r1​,r2​∈RΣ​ אזי הביטויים הבאים גם ב-RΣR_{\Sigma}RΣ​:

(r1+r2),(r1⋅r2),(r1∗)(r_{1}+r_{2}), \qquad (r_{1}\cdot r_{2}), \qquad (r_{1}^*)(r1​+r2​),(r1​⋅r2​),(r1∗​)
דוגמה

נקח את Σ={a,b}\Sigma=\left\{ a,b \right\}Σ={a,b}. ביטויים רגולרים ב-RΣR_{\Sigma}RΣ​:

a,b,∅,ε,(a+b),(ε⋅b),(∅∗),(b⋅b),((a+b)⋅ε),((a+b)∗),((b⋅b)+(e⋅b)),(((a+b)⋅ε)∗)\begin{align*} & a,b,\emptyset,\epsilon, \\ & (a+b),(\epsilon\cdot b),(\emptyset^*),(b\cdot b), \\ & ((a+b)\cdot\epsilon),((a+b)^*),((b\cdot b)+(e\cdot b)), \\ & (((a+b)\cdot\epsilon)^*) \end{align*}​a,b,∅,ε,(a+b),(ε⋅b),(∅∗),(b⋅b),((a+b)⋅ε),((a+b)∗),((b⋅b)+(e⋅b)),(((a+b)⋅ε)∗)​

וכו וכו'.

דוגמה

בדוגה שראינו זה עתה, הביטוי של מכונת המצבים שלנו היה (0101)∗(0101)^*(0101)∗

תזמון במכונת מצבים

​ספרתיות הרצאת אוטומטים 1 - 5.png
משך מחזור השעון TTT מקיים:

T≥tpCQ(FF)+tpd(C.Logic)+tsu(FF)T\geq t_{pCQ}(FF)+t_{pd}(C.Logic)+t_{su}(FF)T≥tpCQ​(FF)+tpd​(C.Logic)+tsu​(FF)

תנאי SETUPSETUPSETUP אשר מתקיים בכניסה למכונה:

tsu(IN)≥tpd(C.Logic)+tsu(FF)t_{su}(IN)\geq t_{pd}(C.Logic)+t_{su}(FF)tsu​(IN)≥tpd​(C.Logic)+tsu​(FF) thold(IN)≥thold(FF)−tcd(C.Logic)t_{hold}(IN)\geq t_{hold}(FF)-t_{cd}(C.Logic)thold​(IN)≥thold​(FF)−tcd​(C.Logic)
הערה

ראינו שבחיבור טורי של FlipFlopFlipFlopFlipFlop-ים חייב להתקיים תנאי חמור יותר:

tcd(C→Q)≥thold(FF)t_{cd}(C\to Q)\geq t_{hold}(FF)tcd​(C→Q)≥thold​(FF)

סה"כ: ישנם ארבעה מסלולים: שעון לשעון, קלט לשעון, קלט לפלט ושעון לפלט.
כדי לבטיח פעולה תקינה של מערכת עקיבה יש להקפיד על כלל אחד לכל מסלול:

  1. מסלול שעון לשעון: משך מחזור השעון TTT חייב להיות ארוך מספיק כדי לאפשר לאות לצאת מה-FlipFlopFlipFlopFlipFlop, לעבור בלוגיה הצירופית ולהתייצב לפני עליית השעון הבאה כדי להיכנס ל-FlipFlopFlipFlopFlipFlop הבא ולכן נדרש כי:
    T≥tpCQ(FF)+tpd(C.Logic)+tsetup(FF)T\geq t_{pCQ}(FF)+t_{pd}(C.Logic)+t_{setup}(FF)T≥tpCQ​(FF)+tpd​(C.Logic)+tsetup​(FF)
  2. מסלול קלט לשעון: הכניסות למערכת הצירופית צריכות להיות יציבות בערכים הנכונים מספיק זמן לפני עליית השעון ולכן, נדרש כי:
    tsetup(Inputs)≥tpd(C.Logic)+tsetup(FF)t_{setup}(Inputs)\geq t_{pd}(C.Logic)+t_{setup}(FF)tsetup​(Inputs)≥tpd​(C.Logic)+tsetup​(FF)
  3. מסלול שעון לקלט: הכניסות צריכות להישאר יציבות לאחר עליית השעון כדי לא לפגוע בזמן ההחזקה של ה-FlipFlopFlipFlopFlipFlop ולכן נדרוש:
    thold(Inputs)≥thold(FF)−tcd(C.Logic)t_{hold}(Inputs)\geq t_{hold}(FF)-t_{cd}(C.Logic)thold​(Inputs)≥thold​(FF)−tcd​(C.Logic)
  4. מסלול פנימי: הזמן המינימלי שלוקח לאות לעבור חייב להיות גדול מזמן ההחזקה כדי שה-FlipFlopFlipFlopFlipFlop לא "יבלע" נתון חדש מהר מדי. לכן, נדרוש:
    tcd(C→Q)+tcd(C.Logic)≥thold(FF)t_{cd}(C\to Q)+t_{cd}(C.Logic)\geq t_{hold}(FF)tcd​(C→Q)+tcd​(C.Logic)≥thold​(FF)
הערה

במערכות מעשיות, אות השעון לא מגיע לכל ה-FlipFlopFlipFlopFlipFlop-ים בדיוק באותו הרגע בגלל זמני התפשטות שונים בחוטים.
הפרש הזמנים הזה נקרא Clock  SkewClock\; SkewClockSkew והוא בדרך כלל מקטין ביצועים מכיוון שהוא מאלץ אותנו להגדיל את זמן מחזור השעון הכולל כדי למנוע שגיאות תזמון.

דוגמה (גלאי 111111 בכניסה)

נתונה סדרת קלט x(n)x(n)x(n) כאשר nnn הוא מונה זמן בדיד.
אנו נדרשים לחשב סדרת פלט מתאימה המוגדרת: z(n)=x(n)⋅x(n−1)z(n)=x(n)\cdot x(n-1)z(n)=x(n)⋅x(n−1)
נגדיר "תנאי שפה" z(0)=0z(0)=0z(0)=0.
נצייר את דיאגרמת המצבים מסוג mealymealymealy.
​5 - מכונות מצבים סופיות(אוטומטים) 2026-06-02 17.45.15.excalidraw.svg
כעת נבנה טבלת מצבים כאשר A=0,B=1A=0,B=1A=0,B=1.

PS(y)x=0x=1A=00,01,0B=10,01,1\begin{array}{|c|cc|} \hline PS(y) & x=0 & x=1 \\ \hline A=0 & 0,0 & 1,0 \\ B=1 & 0,0 & 1,1 \\ \hline \end{array}PS(y)A=0B=1​x=00,00,0​x=11,01,1​​

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

D=xz=x⋅yD=x \qquad \qquad z=x\cdot yD=xz=x⋅y

​ספרתיות הרצאת אוטומטים 1 - 6.png
כדי להפוך את המכונה הזו מ-mealymealymealy ל-mooremooremoore נוכל פשוט להוסיף FlipFlopFlipFlopFlipFlop בסוף.
נבחן מה קורה בכל רגע במערכת ה-mealymealymealy. נניח X=0110  ⟹  Z=0010X=0110 \implies Z=0010X=0110⟹Z=0010 וזה יראה כך:
​ספרתיות הרצאת אוטומטים 1 - 8.png

תרגיל (מונה בינארי מודולו 8)

יציאת המונה תהיה 111 עם קבלת ה-111 השמיני, הששה עשר, העשרים ורביעי וכו'.
​ספרתיות הרצאת אוטומטים 1 - 9.png
אנו נקבל את טבלת המצבים הבאה:

PSx=0x=1S0S0,0S1,0S1S1,0S2,0S2S2,0S3,0S3S3,0S4,0S4S4,0S5,0S5S5,0S6,0S6S6,0S7,0S7S7,0S0,1\begin{array}{|c|cc|} \hline PS & x=0 & x=1 \\ \hline S_{0} & S_{0},0 & S_{1},0 \\ S_{1} & S_{1},0 & S_{2},0 \\ S_{2} & S_{2},0 & S_{3},0 \\ S_{3} & S_{3},0 & S_{4},0 \\ S_{4} & S_{4},0 & S_{5},0 \\ S_{5} & S_{5},0 & S_{6},0 \\ S_{6} & S_{6},0 & S_{7},0 \\ S_{7} & S_{7},0 & S_{0},1 \\ \hline \end{array}PSS0​S1​S2​S3​S4​S5​S6​S7​​x=0S0​,0S1​,0S2​,0S3​,0S4​,0S5​,0S6​,0S7​,0​x=1S1​,0S2​,0S3​,0S4​,0S5​,0S6​,0S7​,0S0​,1​​

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

Y3=x‾y3+y3y2‾+y3y1‾+xy3‾y2y1Y_{3}=\overline{x}y_{3}+y_{3}\overline{y_{2}}+y_{3}\overline{y_{1}}+x\overline{y_{3}}y_{2}y_{1}Y3​=xy3​+y3​y2​​+y3​y1​​+xy3​​y2​y1​ Y2=x‾y2+y2y1‾+xy2‾y1Y_{2}=\overline{x}y_{2}+y_{2}\overline{y_{1}}+x\overline{y_{2}}y_{1}Y2​=xy2​+y2​y1​​+xy2​​y1​ Y1=x‾y1+xy1‾=x⊕yY_{1}=\overline{x}y_{1}+x\overline{y_{1}}=x \oplus yY1​=xy1​+xy1​​=x⊕y Z=xy3y2y1Z=xy_{3}y_{2}y_{1}Z=xy3​y2​y1​

​ספרתיות הרצאת אוטומטים 1 - 10.png

תרגיל (ברמה גבוהה)

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

למערכת זו יש כניסה אחת המקבלת x1,x2,x3x_{1},x_{2},x_{3}x1​,x2​,x3​ ויציאה אחת המוציאה z1,z2,z3,z4z_{1},z_{2},z_{3},z_{4}z1​,z2​,z3​,z4​ כאשר z1=x1,z2=x2,z3=x3z_{1}=x_{1},z_{2}=x_{2},z_{3}=x_{3}z1​=x1​,z2​=x2​,z3​=x3​.

נגדיר את מצבי הזיכרון:

  • נדרש לזכור את אינדקס הכניסה מודולו 444 (4 מצבים)
  • נדרש לזכור את זוגיות האחדים בשלילשיה (2 מצבים)

סה"כ קיבלנו 888 מצבים (אולי פחות? לפי מהייל-נרוד אנו יודעים כי יש פחות)
נבנה אוטומט עם 7 מצבים. נחלק את המצבים שלנו לשתי קבוצות: קבוצה זוגית, עם 333 מצבים וקבוצה אי זוגית, עם 333 מצבים. המצב האחרון יהיה המצב ההתחלתי אשר יכול להיות אך ורק בעל מספר זוגי של אחדים AKAAKAAKA 0.
​5 - מכונות מצבים סופיות(אוטומטים) 2026-06-02 18.17.28.excalidraw.svg
וזה האוטומט שלנו :)

תכנון מערכת עקיבה

נוכל לתכנן מערכת עקיבה באמצעות השלבים הבאים:

  1. נתייחס לתיאור המערכת הנדרשת ובכך הבנת מהו מספר הכניסות, מספר היציאות ומצבי הזיכרון.
  2. נבנה טבלת מצבים או דיאגרמת מצבים.
  3. נצמצם את טבלת המצבים (לא בחומר הסמסטר הזה לאור המלחמה\color{blue}\R{\text{לא בחומר הסמסטר הזה לאור המלחמה}}לא בחומר הסמסטר הזה לאור המלחמה)
  4. נבחר הקצאת מצבים ורכיבי זיכרון אשר בקורס הזה תמיד יהיו מסוג D−FFD-FFD−FF.
  5. נרשום את טבלת המעברים ואת טבלת היציאה
  6. נמצא את פונקציות המעבר ופונקציות היציאה
  7. נשרטט את המעגל המממש את המערכת

מגבלות מערכת עקיבה

  • מערכות העקיבה מומשו עד כה באמצעות זיכרון סופי ולכן מספר המצבים הוא סופי.
  • לא ניתן לחשב באמצעות מכונה כזו כל חישוב שהוא לאור מספר המצבים הסופי.
משפט (למת הניפוח בניסוח מזעזע)

מכונה בעלת מספר מצבים סופי מפיקה יציאה מחזורית תחת קלט מחזורי, למעט "זמן-מעבר" סופי.

הוכחה:
נניח שלמכונה nnn מצבים ואורך המחזור של סדרת הקלט הוא kkk סיביות. נבדוק מהו מצב המכונה בכל פעם שמחזור הקלט מתחיל מחדש.
לאחר n+1n+1n+1 מחזורי קלט לכל היותר, לפחות שני מצבים יהיו זהים:

St(0)→1St(1)→1St(2)→1⋯→1St(j)→1⋯→1St(n−1)→1St(n)→1…S_{t(0)}\xrightarrow{1}S_{t(1)}\xrightarrow{1}S_{t(2)}\xrightarrow{1}\dots\xrightarrow{1}S_{t(j)}\xrightarrow{1}\dots\xrightarrow{1}S_{t(n-1)}\xrightarrow{1}S_{t(n)}\xrightarrow{1}\dotsSt(0)​1​St(1)​1​St(2)​1​⋯1​St(j)​1​⋯1​St(n−1)​1​St(n)​1​…

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

מסקנה

חישובים מסויימים אינם ניתנים למימוש באמצעות מכונה סופית.

גילוי שגיאות במערכת עקיבה

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

1. שיטת הסריקה

במקום להשתמש ב-FlipFlopFlipFlopFlipFlop-ים רגילים אנו נתשתמש ב-Scanned−FlipFlopScanned-FlipFlopScanned−FlipFlop ונחבר את כולם בשרשרת אחת מה שהופכת אותם לרכיב הזזה אחד. (כלומר, נקח את רגל ה-QQQ של אחד ונחבר לרגל ה-ScanInScanInScanIn של ההבאה)
נחבר בנוסף כניסת בקרה לכל ה-FlipFlopFlipFlopFlipFlop-ים
​ספרתיות 1+545.png
הבדיקה עצמה מתבצעת בשלבים:

  1. טעינה סדרתית: מעבירים את המערכת למצב סריקה(SCAN CONTROL = 1) ואז מכניסים טורית(ביט אחרי ביט) את וקטור הבדיקה לתוך המערכת. אם יש NNN דלגלגים נדרש להפעיל את השעון NNN מחזורים כדי להזין את הנתונים לכל ה-FlipFlopFlipFlopFlipFlop-ים.
  2. דגימה: מעבירים את SCAN CONTROL בחזרה לאפס למשך מחזור שעון אחד בלבד. באותו הרגע, הלוגיקה הצירופית מבצעת את החישוב שלה על מסך הערכים שטענו והתוצאה נשמרת בתוך ה-FFFFFF-ים.
  3. פריקה סדרתית: מעבירים שוב ל-111. ב-NNN מחזורי השעון הבאים קוראים את התוצאות החוצה ביט אחרי ביט כדי לבדוק אם הלוגיקה בכל שלב עבדה נכון.

​עוד תמונה מספרתיות הרצאת אוטומטים 2.png

בדיקת זכרונות: BIST&BISRBIST\&BISRBIST&BISR

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

הגדרה 2 (בדיקה מובנת מראש - BISTBISTBIST)

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

הגדרה 3 (תיקון מובנה מראש - BISRBISRBISR)

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

צנרור (PipelinePipelinePipeline)

ביצועים של מערכות ספרתיות

כאשר אנו בונים מערכת לוגית ישנם שני מדדים עקריים שדרכם אנו בוחנים את הביצועים שלה:

  • השהייה (LatencyLatencyLatency): הזמן שעובר מרגע תחילת החישוב של נתון מסויים ועד לקבלת התוצאה הסופית שלו.
    במערכת צירופית, זהו פשוט ה-tpdt_{pd}tpd​ המקסימלי של המעגל.
  • ספיקה (ThroughputThroughputThroughput): קצב החישוב. כלומר, כמה חישובים המערכת מסוגלת לסיים ביחידת זמן נתונה.

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

יוצרים מערכות מהירות

הגדרה 4 (PipelinePipelinePipeline)

תהליך בו חישוב טורי ארוך מחולק לשלבים(תחנות) כאשר בין שלב לשלב מציבים רכיבי זיכרון(FFFFFF-ים או אפילו אוגרים)

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

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

ההשפעה של ה-PipelinePipelinePipeline

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

ההשהיה, לעומת זאת, לא משתפרת שכן ייקח לנתון בודד לפחות את אותו הזמן לעבור מתחילת הצינור ועד סופו.
למעשה, בגלל שהוספנו אוגרים ברך התווספו לנו זמני ה-tpCQt_{pCQ}tpCQ​ וה-tsetupt_{setup}tsetup​ ולכן ההשהיה הכוללת אפילו גדלה במקצת לעומת המערכת הצירופית המקורית. היא מוגדרת כעת כ-K⋅TK\cdot TK⋅T כאשר KKK הוא מספר השלבים ו-TTT הוא זמן המחזור של רכיב הזיכרון.