پرش به محتویات

کد گری

کد گری یک سیستم اعداد دودویی است که در آن دو مقدار متوالی تنها در یک بیت با هم تفاوت دارند.

برای مثال، دنباله‌ی کدهای گری برای اعداد ۳ بیتی به این صورت است: 000، 001، 011، 010، 110، 111، 101، 100، بنابراین $G(4) = 6$ است.

این کد توسط فرانک گری در سال ۱۹۵۳ اختراع شد.

پیدا کردن کد گری

بیایید به بیت‌های عدد $n$ و بیت‌های عدد $G(n)$ نگاه کنیم. توجه کنید که بیت $i$-ام از $G(n)$ تنها زمانی برابر با ۱ است که بیت $i$-ام از $n$ برابر با ۱ و بیت $i+1$-ام برابر با ۰ باشد، یا برعکس (بیت $i$-ام برابر با ۰ و بیت $i+1$-ام برابر با ۱ باشد). بنابراین، $G(n) = n \oplus (n >> 1)$ است:

int g (int n) {
    return n ^ (n >> 1);
}

پیدا کردن معکوس کد گری

با داشتن کد گری $g$، عدد اصلی $n$ را بازیابی می‌کنیم.

ما از پراهمیت‌ترین بیت‌ها به سمت کم‌اهمیت‌ترین بیت‌ها حرکت می‌کنیم (بیت کم‌اهمیت دارای اندیس ۱ و بیت پراهمیت دارای اندیس $k$ است). رابطه بین بیت‌های $n_i$ از عدد $n$ و بیت‌های $g_i$ از عدد $g$ به این صورت است:

$$\begin{align} n_k &= g_k, \\ n_{k-1} &= g_{k-1} \oplus n_k = g_k \oplus g_{k-1}, \\ n_{k-2} &= g_{k-2} \oplus n_{k-1} = g_k \oplus g_{k-1} \oplus g_{k-2}, \\ n_{k-3} &= g_{k-3} \oplus n_{k-2} = g_k \oplus g_{k-1} \oplus g_{k-2} \oplus g_{k-3}, \vdots \end{align}$$

ساده‌ترین راه برای نوشتن این منطق در کد به این صورت است:

int rev_g (int g) {
  int n = 0;
  for (; g; g >>= 1)
    n ^= g;
  return n;
}

کاربردهای عملی

کدهای گری کاربردهای مفیدی دارند که گاهی اوقات کاملاً غیرمنتظره هستند:

  • کد گری با $n$ بیت، یک دور همیلتونی روی یک ابرمکعب (hypercube) تشکیل می‌دهد، که در آن هر بیت متناظر با یک بُعد است.

  • کدهای گری برای به حداقل رساندن خطاها در تبدیل سیگنال‌های دیجیتال به آنالوگ (مثلاً در سنسورها) استفاده می‌شوند.

  • از کد گری می‌توان برای حل مسئله برج‌های هانوی استفاده کرد. فرض کنید $n$ تعداد دیسک‌ها باشد. با کد گری به طول $n$ که شامل همه صفرها است ($G(0)$) شروع کنید و بین کدهای گری متوالی حرکت کنید (از $G(i)$ به $G(i+1)$). فرض کنید بیت $i$-ام از کد گری فعلی، دیسک $i$-ام را نشان می‌دهد (کم‌اهمیت‌ترین بیت مربوط به کوچک‌ترین دیسک و پراهمیت‌ترین بیت مربوط به بزرگ‌ترین دیسک است). از آنجایی که در هر مرحله دقیقاً یک بیت تغییر می‌کند، می‌توانیم تغییر بیت $i$-ام را به عنوان حرکت دادن دیسک $i$-ام در نظر بگیریم. توجه کنید که برای هر دیسک (به جز کوچک‌ترین دیسک) در هر مرحله (به جز وضعیت شروع و پایان) دقیقاً یک گزینه حرکت وجود دارد. برای کوچک‌ترین دیسک همیشه دو گزینه حرکت وجود دارد، اما یک استراتژی وجود دارد که همیشه به جواب منجر می‌شود: اگر $n$ فرد باشد، دنباله حرکت‌های کوچک‌ترین دیسک به این صورت است: $f \to t \to r \to f \to t \to r \to ...$ (که در آن $f$ میله اولیه، $t$ میله مقصد و $r$ میله باقیمانده است)، و اگر $n$ زوج باشد: $f \to r \to t \to f \to r \to t \to ...$

  • کدهای گری در تئوری الگوریتم‌های ژنتیک نیز کاربرد دارند.

مسائل تمرینی