שאלה באסמבלי (ותכנון מעגל לוגי)

[iem]

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

למשל...: 00000000 נותן לנו 1

01010101 נותן לנו 2

11011101 נותן לנו 4

11111110 נותן לנו 8

לבנות את המעגל אין לי בעיה אחרי שאני אמלא את טבלאת האמת, אבל אין לי מושג איך צריכות להיראות שאר השורות בטבלאת

האמת ?!

אני יכול אולי לשער נניח ש01010101 מורכב מ-2 סיביות מחזוריות ולכן התוצאה 2.

וגם 11011101 מורכב מ-1101 מחזורי שגודלו 4 סיביות ולכן התוצאה היא 4..

אבל למה 00000000 הוא 1? בגלל שיש את 0 שהוא בגודל סיבית אחת ?

עכשיו.. נניח שהתיאוריה שלי נכונה... איך ייראה המוצא ? 4 סיביות ? כי יש מקסימום עד 1000 שזה 8?

או שהם רוצים ייצוג אחר ? ובמוצא אני מממש פונקציה לכל סיבית מה-4 סיביות ואח"כ מסדר אותן אחת מעל השניה במוצא ?

האם בכלל אני אנוס לבנות טבלאת אמת מהגיהנום או שמא קיימת שיטה אחרת נוחה יותר ?

תודה מראש !!

[Yehudaa]

IEM אסמבלי ???

איזה קורס באו"פ אתה עושה ?

[Zelig]

השאלה בכלל לא מוגדרת היטב. תחזור למי שנתן אותה ותבקש הגדרות ברורות יותר למשימה.

[iem]

IEM אסמבלי ???

איזה קורס באו"פ אתה עושה ?

Long time no see.....

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

השאלה בכלל לא מוגדרת היטב. תחזור למי שנתן אותה ותבקש הגדרות ברורות יותר למשימה.

דווקא הבנתי אותה ויש לי רעיון מימוש בלי פריסת 256 שורות בט. אמת... מה לא הבנת בניסוח ? ???

[Zelig]

"גודל התבנית המחזורית המינימלית" אינו ברור.

קודם כל, אני מניח שהתכוונו ל"אורך" לא "גודל". ומה זה "תבנית"? האם הכוונה למחרוזת?

מלבד זאת, אורך התבנית המחזורית המינימלית הוא תמיד אחד, שכן התבנית "1" היא מחזורית באורך 1 ונמצאת תמיד בכל מחרוזת שמכילה "1". (ואם לא, אז "0", ואם לא, אז האורך של התבנית המחזורית המינימלית הוא כמובן 0, שכן זה מספר ריק).

בקיצור, כדאי לתת הגדרה מדוייקת של הבעיה.

[iem]

למשל...: 00000000 נותן לנו 1

01010101 נותן לנו 2

11011101 נותן לנו 4

11111110 נותן לנו 8

למה למשל בדוגמא זה 4 ? כי... ככה ! סתם ;D , בגלל ש1101 חוזר על עצמו כל פעם (יש רק פעמיים 1101 ב-8 סיביות.. מה לעשות...), ולכן המחרוזת המינימלית היא 4, ולמשל בדוגמא של 2, המחרוזת היא 01 שחוזרת למשל כאן 4 פעם אבל גודלה הוא 2 כי היא 01 .

[Yehudaa]

אהה הבנתי , שאלה טובה

[exercise]

ההנחות שלך לפתרון נראות נכונות. תכתוב תוכנה שמחשבת לך את הטבלת אמת

[jackofalltrades]

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

[lo_toda]

זה שאלה קלאסית באוטומטים .... ;D

[Zelig]

ב-"11111110" המחרוזת 11 חוזרת מספר פעמים (3 או 6, תלוי איך מגדירים חזרה) ואורכה הוא 2 ולכן אורך המחרוזת החוזרת המינמלית היא 2. או 1, אם אתה מוכן לקבל את "1" כמחרוזת שחוזרת 7 פעמים, אז התשובה במקרה זה היא 1.

האם אותה מחרוזת שחוזרת על עצמה חייבת לכלול גם אפסים וגם אחדים? או שאולי כל 8 הסיביות (ובשום מקום לא מוגדר שאורך המחזורת הכולל הוא 8 סיביות!) חייבות להיות מורכבות מאותה תבנית מינילית מיתולוגית?

[iem]

המחרוזת 11111110 אינה חוזרת 7 פעמים, אתה מתעלם מה-0 שיש.

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

אז איך אני מממש את זה הכי טוב שניתן ?

[Zelig]

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

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

מאחר שאנחנו דורשים שהתבנית המחזורית תמלא 8 סיביות, אזי ברור שהאורכים האפשריים הם 1, 2, 4, 8.

אני הייתי מתחיל בלהשוות זוגות ביטים, זוגות של 2 ביטים, ולבסוף את ה-4 ביטים הראשונים לאחרונים.

לכך צריך:

4 משווים של ביט (כלומר XOR) להשוות בין Xi ל-Xi+1

3 משווים של 2 ביטים( 01 עם 23, 23 עם 45, 45 עם 67). אפשר גם לעשות אופטימיזציה ולוותר על אחד מהם.

משווה אחד של 4 ביטים (0123 עם 4567).

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

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

[iem]

אתה יכול להראות לי איך אתה עושה זאת עם טבלאת אמת ל-4 ?

[lo_toda]

נראה לי עדיף כיוון רקורסיבי ...

שוברים לשתים משווים ...כל אחד שוב שובר ל שתיים ומשווה ...כמו מיון ...QUICK SORT