הצגת המקור של הדף "קוד גריי"

'''קוד גריי''' הוא שיטה לקידוד [[מספר]]ים באופן [[בסיס בינארי|בינארי]] שבה כל מספר-עוקב שונה מקודמו ב[[סיבית|ספרה בינארית]] אחת בלבד.

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

'''דוגמה'''
{| class=wikitable style="text-align:center;"
|+
! עשרוני
! בינארי
! גריי
|-
| 0
| 000
| 000
|-
| 1
| 001
| 001
|-
| 2
| 010
| 011
|-
| 3
| 011
| 010
|-
| 4
| 100
| 110
|-
| 5
| 101
| 111
|-
| 6
| 110
| 101
|-
| 7
| 111
| 100
|}
כפי שניתן לראות, הקוד של 2 ו־3 הוא היפוך הסדר של הקוד של 0 ו־1, בהוספת הסיבית 1 משמאל. באותו אופן, הקוד של 4 עד 7 הוא היפוך הקוד של 0 עד 3, בהוספת 1 משמאל (והצבת אפסים בספרות החסרות). באופן זה, ניתן להמשיך ולבנות את הקוד. הקוד עבור 8 יהיה 1100, והקוד עבור 15 יהיה 1000.

==המרה בין קוד גריי ובסיס 2==
על מנת להפוך מספר בבסיס 2 לקוד גריי נתחיל משמאל. את הספרה הראשונה משמאל נעתיק. עכשיו נביט בספרה הסמוכה לה – אם זו ספרה זהה נרשום מימין לספרה שהעתקנו 0, אם היא שונה נרשום 1 (פעולת [[XOR]] בין שני משתנים).

לדוגמה, נמצא את הייצוג של המספר 100110 בקוד גריי:
{|
|תחילה נעתיק את הראשונה
|style=text-align:left|'''1'''
|-
|יש שוני בין שתי הספרות 1,0 ולכן נרשום 1
|style=text-align:left|'''11'''
|-
|אין שוני בין שתי הספרות 0,0 ולכן נרשום 0
|style=text-align:left|'''110'''
|-
|יש שוני בין שתי הספרות 0,1 ולכן נרשום 1
|style=text-align:left|'''1101'''
|-
|אין שוני בין שתי הספרות 1,1 ולכן נרשום 0
|style=text-align:left|'''11010'''
|-
|יש שוני בין שתי הספרות 1,0 ולכן נרשום 1
|style=text-align:left|'''110101'''
|}

על מנת לבצע את הפעולה ההפוכה (להפוך מייצוג של קוד גריי למספר בבסיס 2) צריך להתחיל מהספרה הימנית ביותר ולספור את מספר האחדות הנמצאים משמאלה. אם יש [[מספר זוגי]] של אחדות מעתיקים את הספרה, ואם יש מספר אי זוגי הופכים. לדוגמה נקח את המספר 110 (4) ונסתכל מהספרה הימנית. נראה שיש מספר זוגי (2) של אחדות ולכן נעתיק 0. נמשיך לספרה הבאה ונראה שמשמאלה יש רק ספרת 1 בודדה ולכן נהפוך אותה ל-0. את הספרה האחרונה פשוט מעתיקים לכן יצא לנו 100 שזהו 4 בבסיס 2.

שיטה נוספת להמרה מגריי לבינארי רגיל: מתחילים מהספרה השמאלית. הספרה המקבילה במספר הבינארי היא הספרה הנוכחית בקוד גריי XOR הספרה הקודמת בקוד הבינארי (עבור האיטרציה הראשונה אפשר להוסיף 0 משמאל למספר הבינארי). עבור אותו מספר: 110, נוסיף 0 אחד משמאל: ???0. XOR של 1 ו-0 זה 1- הספרה השמאלית במספר הבינארי, כך שבינתיים יש לנו ??01. עוברים לספרה הבאה מימין: XOR של 1 ו-1 זה 0, ונקבל ?010. עוברים עוד ספרה: XOR של 0 ו-0 זה 0. קיבלנו 0100 שזה 4 דצימאלי כמו בשיטה הקודמת.

אפשר לייצג זאת בנוסחה:
:<math>B_i=G_i\oplus B_{i+1}</math>
כאשר <math>G_i</math> הספרה ה-<math>i</math> בקוד גריי, ו-<math>B_i</math> הספרה ה-<math>i</math> במספר הבינארי.

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

==קישורים חיצוניים==
{{ויקישיתוף בשורה}}
*{{MathWorld|GrayCode}}
*[http://www.toolmenow.com/71/Gray-Code-To-Binary ממיר מקוד גריי למספר בינארי] {{אנגלית}}
*[http://www.toolmenow.com/70/Binary-To-Gray-Code ממיר ממספר בינארי לקוד גריי] {{אנגלית}}
*עידו גנדל, [https://web.archive.org/web/20140223013420/http://net.nana10.co.il/Article/?ArticleID=718880&ssv=1&sid=127 האנטומיה של הקוד של גריי], באתר נענע10, 16 במאי 2010
*{{OEIS|A003188|סדרת הייצוג העשרוני של קוד גריי כמספרים רגילים בבסיס ספירה שניים}}

[[קטגוריה:קומבינטוריקה]]
[[קטגוריה:קידוד נתונים|גריי]]
[[קטגוריה:שיטות ספירה]]