গ্রে কোড#
গ্রে কোড হলো একটি বাইনারি সংখ্যা পদ্ধতি যেখানে দুটি পরপর মান কেবল একটি বিটে পৃথক হয়।
উদাহরণস্বরূপ, ৩-বিট সংখ্যার জন্য গ্রে কোডের ক্রম হলো: 000, 001, 011, 010, 110, 111, 101, 100, তাই $G(4) = 6$।
এই কোডটি ১৯৫৩ সালে ফ্র্যাংক গ্রে আবিষ্কার করেন।
গ্রে কোড নির্ণয়#
$n$ সংখ্যার বিট এবং $G(n)$ সংখ্যার বিটগুলো দেখা যাক। লক্ষ্য করুন যে $G(n)$-এর $i$-তম বিট কেবল তখনই ১ হয় যখন $n$-এর $i$-তম বিট ১ এবং $i + 1$-তম বিট ০ অথবা উল্টোটি ($i$-তম বিট ০ এবং $i + 1$-তম বিট ১)। সুতরাং, $G(n) = n \oplus (n >> 1)$:
int g (int n) {
return n ^ (n >> 1);
}ইনভার্স গ্রে কোড নির্ণয়#
গ্রে কোড $g$ দেওয়া আছে, মূল সংখ্যা $n$ পুনরুদ্ধার করতে হবে।
আমরা সবচেয়ে উচ্চ তাৎপর্যপূর্ণ বিট থেকে সবচেয়ে কম তাৎপর্যপূর্ণ বিটের দিকে যাব (সবচেয়ে কম তাৎপর্যপূর্ণ বিটের ইনডেক্স ১ এবং সবচেয়ে উচ্চ তাৎপর্যপূর্ণ বিটের ইনডেক্স $k$)। $n$ সংখ্যার বিট $n_i$ এবং $g$ সংখ্যার বিট $g_i$-এর মধ্যে সম্পর্ক:
$$\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$ বিটের গ্রে কোড একটি হাইপারকিউবে হ্যামিল্টোনিয়ান সাইকেল গঠন করে, যেখানে প্রতিটি বিট একটি মাত্রার সাথে সম্পর্কিত।
ডিজিটাল-টু-অ্যানালগ সিগন্যাল রূপান্তরে (উদাহরণস্বরূপ, সেন্সরে) ত্রুটি কমাতে গ্রে কোড ব্যবহৃত হয়।
টাওয়ার্স অব হ্যানয় সমস্যা সমাধানে গ্রে কোড ব্যবহার করা যায়। মনে করি $n$ হলো চাকতির সংখ্যা। $n$ দৈর্ঘ্যের গ্রে কোড দিয়ে শুরু করুন যেটি সব শূন্য নিয়ে গঠিত ($G(0)$) এবং পরপর গ্রে কোডের মধ্যে সরান ($G(i)$ থেকে $G(i+1)$-তে)। বর্তমান গ্রে কোডের $i$-তম বিট $n$-তম চাকতি নির্দেশ করুক (সবচেয়ে কম তাৎপর্যপূর্ণ বিট সবচেয়ে ছোট চাকতি এবং সবচেয়ে উচ্চ তাৎপর্যপূর্ণ বিট সবচেয়ে বড় চাকতি নির্দেশ করে)। যেহেতু প্রতিটি ধাপে ঠিক একটি বিট পরিবর্তন হয়, আমরা $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 ...$।
জেনেটিক অ্যালগরিদম তত্ত্বেও গ্রে কোড ব্যবহৃত হয়।