کد گری

نمایش کدهای دودویی که بعد از فرانک گری (Frank Gray) به نام کد گری شناخته شد که یک سیستم از اعداد دودویی است که هر دو عدد متوالی فقط در یک بیت با هم اختلاف داشته باشند.
امروزه کدگری به طور گسترده برای تصحیح اشکالات در سیستم ارتباط دیجیتالی مثل کابل‌های تلویزیونی و تلویزیون‌های دیجیتالی جهانی استفاده می‌شود.
نام
یکی از محققان آزمایشگاه بل (Bell) به نام فرانک گری اولین بار به طور رسمی کد گری را مورد استفاده قرار داد و این کد بعد از گری توسط افرادی که از آن استفاده می‌کردند کد گری نامگذاری شد.
تاریخچه و کاربردهای علمی
کد گری قبل از آن که در مهندسی به کار رود در پازل‌های ریاضی به کار برده می‌شد، ریاضیدان فرانسوی Emile Boudat از کد گری. در سال۱۸۷۸در تلگراف استفاده کرد و برای این کارش مدال دریافت کرد.
و اما کاربردهای آن، از کد گری به عنوان یک رمزگذار استفاده می‌شود که نسبت به رمزگذار عادی برتری دارد.
در نمایش کد گری خاصیت دایره‌ای بودن آن باعث می‌شود که دو عدد دو سر نیز فقط در یک بیت متفاوت باشند.
کد گری یک دور همیلتونی در یک مکعب بعدی تولید می‌کند که هر کدام از اعداد آن یک راس را نشان می‌دهد و نیز در الگوریتم‌های ژنتیکی از آن استفاده می‌شود و نیز البته برچسب گذاری جدول کارنو از موارد دیگر استفاده آن است.
زمانی کد گری برای آدرس دهی حافظه در کامپیوتر استفاده می‌شود کامپیوتر نیروی کمتری صرف یافتن آدرس‌ها می‌کند چون هر آدرس با قبلی فقط در یک بیت متفاوت است.
طراحان مدارهای منطقی از کد گری به طور گسترده برای عبور چند بیت اطلاعات بین سیستم‌های همزمان استفاده می‌کنند.
یک دیسک کدبندی با یک کد خاکستری بازتابنده ۳ بیتی
انگیزه پیدایش کد گری
بعضی از دستگاه‌ها وضعیت دستگاه را با کدهای باینری نمایش می‌دهند، اگر این دستگاه‌ها از کد باینری عادی استفاده کند این دو وضعیت پشت سر هم خواهند بود
۰۱۱
۱۰۰…
و مشکل کد باینری عادی این است که در حالت طبیعی خیلی بعید است که چند بیت همزمان تغییر کنند همان‌طور که در بالا نمایش داده شده‌است که در کد باینری عادی هر سه بیت همزمان تغییر کرده‌اند اما می‌توان اعداد را طوری در کنار هم قرار داد که فقط در یک بیت متفاوت باشند و تغییر زیادی نکنند مثل
پس کد باینری منعکس شده یا همان کد گری این مشکل را حل می‌کند زیرا که فقط یک بیت در آن‌ها تغییر می‌کند.
Gray Binary
۰ ۰۰۰ ۰۰۰
۱ ۰۰۱ ۰۰۱
۲ ۰۱۱ ۰۱۰
۳ ۰۱۰ ۰۱۱
۴ ۱۱۰ ۱۰۰
۵ ۱۱۱ ۱۰۱
۶ ۱۰۱ ۱۱۰
۷ ۱۰۰ ۱۱۱
با توجه به حالت ۷ و ۰ می‌بینیم که فقط در یک بیت تفاوت دارند که همان خاصیت دوره‌ای یا چرخشی بودن کد گری می‌گوییم.
ساختن کد گری بیتی
یک کد گری بیتی را می‌توان به صورت بازگشتی تولید کرد به این شکل که یک لیست بیتی داریم آن را وارونه می‌کنیم (خط افقی در شکل زیر مانند آینه عمل کند) و در انتهای لیست اصلی می‌چسبانیم و سپس در ابتدای لیست اول و در ابتدای لیست دوم قرار می‌دهیم مثلا برای کد گری یک بیتی ، را داریم (البته می‌توان از کد گری بیتی هم استفاده کرد). ، و بعد با آن کد گری بیتی را به صورت بازگشتی بسازیم و اکنون شبه کد آن را داریم.
نمودار تولید یک کد خاکستری. ساخته Derrick Coetzee در Illustrator و فتوشاپ.
الگوریتم کد گری
ابتدا یک الگوریتم برای تبدیل کد باینری عادی به کد گری وجود دارد.
۱ Let B be the input array of bits in the usual binary representation, 0 being LSB
۲ Let G be the output array of bits in Gray code
۳ Gn = Bn
۴ for i = n-1 downto 0
۵ Gi = Bi+1 XOR Bi
الگوریتم بتبدیل کد گری به کد باینری
۱ Let G be the input array of bits in Gray code
۲ Let B be the output array of bits in the usual binary representation
۳ Bn = Gn
۴ for i = n-1 downto 0
۵ Bi = Bi+1 XOR Gi
الگوریتم تبدیل کد باینری به گری
اول از همه کد باینری عدد مورد نظر را مینویسیم
سپس از سمت چپ شروع میکنیم و اولین عدد را هوانطور که هست نوشته سپس دوتا دوتا عددها رو مقایسه میکنیم، اگر هردو یکسان باشند در این صورت به جای آن دو عدد صفر میگذاریم ، در غیر این صورت: یعنی اگر یکی از عددها صفر و دیگری یک باشد، آن وقت به جای آن دو عدد یک را به جای آنها مینوسیم
برای مثال
7 باینری >> 1 1 1 0
7 گری >> 0 0 1 0
و یک الگوریتم سریعتر درC/java به این شکل است
۱ long inverseGray(long n) {
۲ long ish, ans, idiv;
۳ ish = ۱;
۴ ans = n;
۵ while(true) {
۶ idiv = ans>> ish;
۷ ans ^= idiv;
۸ if (idiv
= ni)
(j <۰)) {
ui = -ui;
i++;
j = gi + ui;
gi = j;
اما یادآور می‌شویم که کد گری (n,k)تایی برای nهای فرد خاصیت چرخشی را حفظ نمی‌کنند ولی برای nهای زوج خاصیت چرخشی را حفظ می‌کنند.
پیوند بیشتر