نمایش مبدأ برای کد گری

{{ویکی‌سازی}}نمایش کدهای [[دودویی]] که بعد از [[فرانک گری (محقق)|فرانک گری]] (Frank Gray) به نام '''کد گِرِی''' شناخته شد، یک سیستم از اعداد دودویی است که هر دو عدد متوالی فقط در یک [[بیت (رایانه)|بیت]] با هم اختلاف داشته باشند.
امروزه کدگری به طورِ گسترده برای تصحیحِ اشکالات در سیستم ارتباط دیجیتالی مثل [[تلویزیون کابلی]] و [[تلویزیون دیجیتال]] استفاده می‌شود.

== نام ==
یکی از محققان [[آزمایشگاه‌های بل|آزمایشگاه بل]] (Bell) به نام فرانک گری اولین بار به‌طور رسمی کد گری را مورد استفاده قرار داد و این کد بعد از گری توسط افرادی که از آن استفاده می‌کردند کد گری نامگذاری شد.

== تاریخچه و کاربردهای علمی ==
کد گری قبل از آن که در مهندسی به کار رود در پازل‌های ریاضی به کار برده می‌شد، ریاضیدان فرانسوی ''Emile Boudat'' از کد گری در سال ۱۸۷۸در [[تلگراف]] استفاده کرد و برای این کارش مدال دریافت کرد.

و اما کاربردهای آن، از کد گری به عنوان یک رمزگذار استفاده می‌شود که نسبت به رمزگذار عادی برتری دارد.

در نمایش کد گری خاصیت دایره‌ای بودن آن باعث می‌شود که دو عدد دو سر نیز فقط در یک بیت متفاوت باشند.

کد گری یک [[مسیر همیلتونی|دور همیلتونی]] در یک مکعب <math>n</math> بعدی <math>Q_n</math> تولید می‌کند که هر کدام از اعداد آن یک راس را نشان می‌دهد و نیز در الگوریتم‌های ژنتیکی از آن استفاده می‌شود و البته برچسب گذاری [[جدول کارنو]] از موارد دیگر استفاده آن است.

زمانی کد گری برای آدرس دهی حافظه در [[رایانه|کامپیوتر]] استفاده می‌شود، کامپیوتر نیروی کمتری صرف یافتن آدرس‌ها می‌کند چون هر آدرس با قبلی فقط در یک بیت متفاوت است.

طراحان [[دروازه منطقی|مدارهای منطقی]] از کد گری به‌طور گسترده برای عبور چند بیت اطلاعات بین سیستم‌های همزمان استفاده می‌کنند.

{{وسط‌چین}}[[پرونده:Encoder Disc (3-Bit).svg|یک دیسک کدبندی با یک کد خاکستری بازتابنده ۳ بیتی]]{{پایان}}

== انگیزهٔ پیدایش کد گری ==
بعضی از دستگاه‌ها وضعیت دستگاه را با کدهای باینری نمایش می‌دهند، اگر این دستگاه‌ها از کد باینری عادی استفاده کند این دو وضعیت پشت سر هم خواهند بود
{{چپ‌چین}}..

۰۱۱

۱۰۰...

{{پایان چپ‌چین}}
و مشکل کد باینری عادی این است که در [[حالت طبیعی]] خیلی بعید است که چند بیت همزمان تغییر کنند همان‌طور که در بالا نمایش داده شده‌است که در کد باینری عادی هر سه بیت همزمان تغییر کرده‌اند اما می‌توان اعداد را طوری در کنار هم قرار داد که فقط در یک بیت متفاوت باشند و تغییر زیادی نکنند مثل<math>011-001-101-100</math>
پس کد باینری منعکس شده یا همان کد گری این مشکل را حل می‌کند زیرا که فقط یک بیت در آن‌ها تغییر می‌کند.
{{چپ‌چین}} Gray Binary
{{سخ}}۰ ۰۰۰ ۰۰۰
{{سخ}}۱ ۰۰۱ ۰۰۱
{{سخ}}۲ ۰۱۱ ۰۱۰
{{سخ}}۳ ۰۱۰ ۰۱۱
{{سخ}}۴ ۱۱۰ ۱۰۰
{{سخ}}۵ ۱۱۱ ۱۰۱
{{سخ}}۶ ۱۰۱ ۱۱۰{{سخ}}
۷ ۱۰۰ ۱۱۱

{{پایان چپ‌چین}}
با توجه به حالت ۷ و ۰ می‌بینیم که فقط در یک بیت تفاوت دارند که همان خاصیت دوره‌ای یا چرخشی بودن کد گری می‌گوییم.

== ساختن کد گری <math>n</math> بیتی ==
یک کد گری <math>n</math> بیتی را می‌توان به صورت بازگشتی تولید کرد، به این شکل که یک لیست <math>n-1</math> بیتی داریم آن را وارونه می‌کنیم (خط افقی در شکل زیر مانند آینه عمل کند) و در انتهای لیست اصلی می‌چسبانیم و سپس در ابتدای لیست اول <math>0</math> و در ابتدای لیست دوم <math>1</math> قرار می‌دهیم مثلاً برای کد گری یک بیتی ، <math>G={0,1}</math> را داریم (البته می‌توان از کد گری <math>0</math> بیتی هم استفاده کرد). <math>n=0 ,G={0,1}</math>، و بعد با آن کد گری<math>1</math> بیتی را به صورت بازگشتی بسازیم و اکنون [[شبه‌کد|شبه کد]] آن را داریم.
[[پرونده:Gray code reflect.png|بندانگشتی|چپ|400px|نمودار تولید یک کد خاکستری. ساخته Derrick Coetzee در Illustrator و فتوشاپ.]]

=== الگوریتم کد گری ===
ابتدا یک الگوریتم برای تبدیل کد باینری عادی به کد گری وجود دارد.
{{چپ‌چین}}
۱ Let B[n:0] be the input array of bits in the usual binary representation, [0] being LSB
{{سخ}}۲ Let G[n:0] be the output array of bits in Gray code
{{سخ}}۳ G[n] = B[n]
{{سخ}}۴ for i = n-1 downto 0
{{سخ}}۵ G[i] = B[i+1] XOR B[i]
{{پایان چپ‌چین}}

=== الگوریتم تبدیل کد گری به کد باینری ===
{{چپ‌چین}}
۱ Let G[n:0] be the input array of bits in Gray code
{{سخ}}۲ Let B[n:0] be the output array of bits in the usual binary representation
{{سخ}}۳ B[n] = G[n]
{{سخ}}۴ for i = n-1 downto 0
{{سخ}}۵ B[i] = B[i+1] XOR G[i]
{{پایان چپ‌چین}}

=== الگوریتم تبدیل کد باینری به گری ===
اول از همه کد باینری عدد مورد نظر را می‌نویسیم

سپس از سمت چپ شروع می‌کنیم و اولین عدد را همان‌طور که هست نوشته سپس دوتا دوتا عددها رو مقایسه می‌کنیم، اگر هردو یکسان باشند در این صورت به جای آن دو عدد صفر می‌گذاریم، در غیر این صورت: یعنی اگر یکی از عددها صفر و دیگری یک باشد، آن وقت به جای آن دو عدد یک را به جای آنها می‌نویسیم

برای مثال

۷ باینری>> ۱ ۱ ۱ ۰

۷ گری>> ۰ ۰ ۱ ۰

==== یک الگوریتم سریع درC/java به شکل زیر است ====
{{چپ‌چین}}
۱ long inverseGray(long n) {
{{سخ}}۲ long ish, ans, idiv;
{{سخ}}۳ ish = ۱;
{{سخ}}۴ ans = n;
{{سخ}}۵ while(true) {
{{سخ}}۶ idiv = ans>> ish;
{{سخ}}۷ ans ^= idiv;
{{سخ}}۸ if (idiv <= ۱ || ish == ۳۲)
{{سخ}}۹ return ans;
{{سخ}}۱۰ ish <<= ۱; // double number of shifts next time}{{سخ}}}
{{پایان چپ‌چین}}

== کد گری n تایی ==
انواع مختلفی از کد گری وجود دارد که یی از این انواع مختلف کد گری n تایی است که به عنوان کد گری غیر دوتایی (۰و۱)هم شناخته می‌شود یعنی به غیر از ۰ و ۱ از اعداد دیگر هم استفاده می‌شود (همان‌طور که نام آن نشان می‌دهد) و در رمزگذاری هم از آن استفاده می‌شود.
برای مثال یک کد گری سه تایی از بیت‌های {۰و۱و۲} استفاده می‌کند.
کد گری سه تایی
{{چپ‌چین}}

،۰۰۰
،۰۰۱
،۰۰۲
،۰۱۲
،۰۱۱
،۰۱۰
،۰۲۰
،۰۲۱
،۰۲۲
،۱۲۲
،۱۲۱
،۱۲۰
،۱۱۰
،۱۱۱
،۱۱۲
،۱۰۲
،۱۰۱
،۱۰۰
،۲۰۰
،۲۰۱
،۲۰۲
،۲۱۲
،۲۱۱
،۲۱۰
،۲۲۰
،۲۲۱
،۲۲۲
{{پایان چپ‌چین}}

یک کد گری (n,k)تایی یک کد گری n تایی است که دارای k بیت است مثلاً یک کد گری(۲و۳)برابر است با
{۰۰، ۰۱، ۰۲، ۱۲، ۱۱، ۱۰، ۲۰، ۲۱، ۲۲}
و اکنون الگوریتم ساخت کد گری (n,k) در C/java در زیر آمده‌است
 {{چپ‌چین}}
{{سخ}}int n[k+1]; // stores the maximum for each digit
{{سخ}}int g[k+1]; // stores the Gray code
{{سخ}}int u[k+1]; // stores +1 or -1 for each element
{{سخ}}int i, j;
{{سخ}}// initialize values
{{سخ}}for(i = ۰; i <= k; i++) {
{{سخ}}g[i] = ۰;
{{سخ}}u[i] = ۱;
{{سخ}}n[i] = N;
{{سخ}}}
{{سخ}}// generate codes
{{سخ}}while(g[k] == ۰) {
{{سخ}}// at this point (g[۰],... ,g[k-1]) hold a subsequent element of the (N,k)-Gray code
{{سخ}}i = ۰;
{{سخ}}j = g[۰] + u[0];
{{سخ}}while((j>= n[i]) || (j <۰)) {
{{سخ}}u[i] = -u[i];
{{سخ}}i++;
{{سخ}}j = g[i] + u[i];
{{سخ}}}
g[i] = j;
}
{{سخ}}{{پایان چپ‌چین}}

اما یادآور می‌شویم که کد گری (n,k)تایی برای nهای فرد خاصیت چرخشی را حفظ نمی‌کنند ولی برای nهای زوج خاصیت چرخشی را حفظ می‌کنند.

== پیوند بیشتر ==
{{چپ‌چین}}
* [http://engknowledge.com/shaft_absolute_encoder_gray_code.aspx "Gray Code" demonstration by Michael Schreiber, The Wolfram Demonstrations Project (with Mathematica implementation). 2007.]
* [http://demonstrations.wolfram.com/BinaryGrayCode/ NIST Dictionary of Algorithms and Data Structures: Gray code]
* [http://www.nrbook.com/a/bookcpdf/c20-2.pdf Numerical Recipes in C, section 20.2 describing Gray codes in detail]
* [http://www.hpl.hp.com/techreports/2000/HPL-2000-81.html Single-Track Circuit Codes by Hiltgen, Alain P.; Paterson, Kenneth G.] {{Webarchive|url=https://web.archive.org/web/20110607080958/http://www.hpl.hp.com/techreports/2000/HPL-2000-81.html |date=۷ ژوئن ۲۰۱۱ }}
{{پایان چپ‌چین}}

== منابع ==
{{پانویس}}
{{چپ‌چین}}
* Black, Paul E. Gray code. 25 February 2004. NIST
* Savage, Carla. "A Survey of Combinatorial Gray Codes." Society of Industrial and Applied Mathematics Review 39 (1997): 605–629.
* Wilf, Herbert S. Combinatorial algorithms: an update, SIAM, 1989, {{ISBN|0-89871-231-9|en}}. Chapters 1-3.
* [https://web.archive.org/web/20070930040812/http://etc.manuel-breitfeld.de/gray-code-java-implementierung.html A Gray code implementation in Java to convert decimals]
{{پایان چپ‌چین}}
* [http://ww.theory.cs.uvic.ca/~cos/gen/comb.html Subsets or Combinations Can generate BRGC strings]{{پیوند مرده|date=نوامبر ۲۰۱۹ |bot=InternetArchiveBot}}

[[رده:انتقال داده]]
[[رده:سامانه‌های عددی ارزش مکانی غیراستاندارد]]
[[رده:عددنویسی]]
[[رده:علوم رایانه]]
[[رده:محاسبه اعداد دودویی]]