دنباله گری

دنباله گری یک سیستم عددی باینری است که در آن، هر دو عدد متوالی تنها در یک بیت اختلاف دارند. هدف از ابداع این دنباله یا به اصطلاح کد، استفاده از آن در وسایلی بود که با کلید های دو حالته کار می‌کردند.
فرض کنید دستگاهی داریم که با توجه به وضعیت سه کلید خروجی آن با یکی از هشت دستگاه موجود دیگر، ارتباط برقرار می‌کند. حال وضعیتی را در نظر بگیرید که نیاز است تا ارتباط به دستگاه شماره 001 قطع شود و ارتباط با دستگاه 110 برقرار گردد.برای این کار باید کلید های روی دستگاه تغییر وضعیت بدهند. مشخص است که تغییر وضعیت این کلید‌های مکانیکی به صورت همزمان رخ نمی‌دهد و در این بین ممکن است با دستگاه‌های دیگری ارتباط برقرار کند.
برای مثال فرض کنید در طی این تغییر، دنباله‌ی زیر به‌وجود آید.
001 –> 000 –> 010 –> 110
هر چند که زمان ماندن در وضعیت‌های میانی بسیار کم است، اما همین زمان ناچیز هم می‌تواند مشکلات جدی، بوجود آورد.

یک الگوریتم بازگشتی بسیار ساده برای ساخت دنباله گری وجود دارد، که به شرح زیر است :
فرض کنید دنباله‌ی گری n-1 بیتی داریم و می‌خواهیم از روی آن دنباله‌ی n بیتی بسازیم. ابتدا دنباله‌ی n-1 بیتی را زیر هم قرار می‌دهیم و علاوه بر آن، دنباله به صورت عمودی آینه می‌کنیم. پس از آن در انتهای هر عدد باینری نیمه بالایی بیت 0 و در انتهای اعداد نیمه‌ پایینی بیت 1 قرار می‌دهیم. با یک مثال این روش روشن می‌شود.

00          00,0 --> 000
10          10,0 --> 100
11          11,0 --> 110
01          01,0 --> 010
     --->  ------
            01,1 --> 011
            11,1 --> 111
            10,1 --> 101
            00.1 --> 001

فرض کنید می‌خواهیم k امین عدد در دنباله n بیتی گری را بیابیم. تابع زیر این عمل را پیاده‌سازی می‌کند.

unsigned int gray (int n,int k) {
    if (n == 1 && k > 1)
        return -1;
    else if (n == 1 && k < 2)
        return k;
    else {
       if ( k < pow(2 , n-1) )
           return gray(n-1 , k)*2;
       else
           return gray(n-1 , pow(2,n)-1-k)*2+1;
    }
}

حالت پایه کد بالا همان دو شرط اولیه است. اگر n=1 که دو حالت بیشتر نداریم، یا k=0 و یا k=1 که در هرکدام ازین حالات مقدار تابع گری برابر k است. اگر n > 1 باشد آنگاه دو حالت پیش می‌آید :
حالت اول :‌ (k < 2^(n-1 که در این حالت خروجی تابع گری همان خروجی تابع گری به ازای n-1 است، با این تفاوت، که در انتهای آن یک بیت 0 اضافه شده است، که معادل با ضرب کردن در 2 است.
حالت دوم : (k >= 2^(n-1 که در این حالت باید معادل این عدد در رشته‌ی n-1 بیتی بیابیم و به انتهای آن یک بیت 1 اضافه کنیم(ضرب کردن در 2 و جمع کردن با 1)
مشخص است که این الگوریتم از (O(n است.

اگر به جای آن که بعد از قرینه کردن دنباله، بیت‌های 0 و 1 را به انتهای اعداد اضافه کنیم، به ابتدای آن‌ها اضافه کنیم الگوریتم دیگری برای تولید دنباله به دست می‌آید. همچنین در این حالت می‌توان به راحتی اندیس یک کد گری در دنباله‌اش را به دست‌آورد.

/*
        The purpose of this function is to convert an unsigned
        binary number to binary Gray code.
 
        The operator >> is shift right. The operator ^ is exclusive or.
*/
unsigned int binaryToGray(unsigned int num)
{
        return (num >> 1) ^ num;
}
 
/*
        The purpose of this function is to convert a binary
        Gray code number to a binary number.
*/
unsigned int grayToBinary(unsigned int num)
{
    unsigned int mask;
    for (mask = num >> 1; mask != 0; mask = mask >> 1)
    {
        num = num ^ mask;
    }
    return num;
}