غولی زکات علمش را میدهد! پنجشنبه دهم بهمن 1387 16:51

سلام.از وقتی این غولمراد خان گل گلاب رو استخدامش کردم، مدام عین چی داره روی اعصاب من راه میره و میگه که بار علمی این بلاگت خیلی خیلی اومده پایین. دیدم بیچاره راست میگه! بنابراین از این پس، روند بلاگ، خاطره ای- اجتماعی -سیاسی- فرهنگی- هنری-...- و یه ذره هم(!) آموزشی- علمی خواهد بود! احتمالا برخی اوقات از دانسته های غولی هم کمک خواهم گرفت! (غولی هم مثل من بر این معتقده که زکات علم، یاد دادنش به دیگرانه!)  و حتی شاید سر برخی موضوعات یا مسائل از غولی کمک یا مشاوره هایی هم بگیرم.[0] البته برای اینکه دیگه بار علمی بلاگ بچسبه به سقف، شاید نمونه سوالهای گسسته خودم یا غولی، c و کلا دروس کارشناسی مهندسی کامپیوتر رو هم براتون بگذارم.

برای شروع...(نمیدونم موضوع خوبی برای شروع هست یا نه...) اگر درس مدار منطقی را گذرانده باشید، به احتمال خیلی خوبی اسمی از کدگری به گوشتان خورده! و حتی شاید بدانید که  چگونه کدهایی هستند. حتی اگر درس ساختار را هم گذرانده باشید، بازهم به احتمال خوبی با این نوع کد آشنا شده اید. من خودم ترم دوم توی درس مدارمنطقی سرکلاس استاد کیاسری با کد گری آشنا شدم. (یاد کلاسای استاد بخیر...) به هرحال، اون موقع برای من جالب بود که این نوع کدها اصلا به چه درد میخورند. به همین خاطر به دنبال کسب اطلاعات بیشتر از تعدادی از انواع کدها توی گوگل جستجو کردم. خلاصه چیزایی که درباره این نوع کد فهمیده بودم اینا هستن:

کدگری(Gray Code)، یک سیستم از اعداد دودویی هست که هر دو عدد متوالی فقط در یک بیت با هم اختلاف دارند.  فرانک گری که یکی از محققان آزمایشگاه بل بود، برای اولین بار این نوع کد رو مورد استفاده قرار داد. و برای آن نام کدهای باینری آینه ای را انتخاب کرد. که بعدا در مورد وجه تسمیه آن صحبت خواهم کرد. بعدها کسانیکه از این کد استفاده میکردند، اون رو کد گری نامیدند.

کدهای گری کاربردهای زیادی دارند. از جمله اینکه در انکدرهای خطی(linear encoder) و چرخشیrotary encoder))استفاده میشوند. در انکدرهایی که از کدهای باینری عادی استفاده میکنند، ممکنه وقتی که تعدادی از بیتها تغییر میکنند، یه الگوی بیتی  ناخواسته ای به وجود بیاد که نه اون الگوی قبلی هست و نه الگوی جدید![1] اما چون در کد گری هر دو عدد متوالی تنها در یه بیت با هم تفاوت دارند این مشکل دیگه وجود ندارد. و خاصیت دایره ای بودن این کد (یعنی اینکه دو عدد اول و آخر هم فقط تو یه بیت باهم تفاوت دارند) باعث شده که در انکدرهای چرخشی هم استفاده شود.

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

جالب است بدانید که در الگوریتم های ژنتیکی هم سرو کله این کدها پیدا شده است. از همان آغاز کشف کد ژنتیک مشاهده میشد که در این کد گونه ای از نظم دیده میشود و ساختار کدهای ژنتیک میتواند به کد گری مرتبط باشد. بر همین مبنا جدول کد ژنتیک با نوع چرخشی آن جایگزین شد.

هم چنین کدهای گری در حل مساله برجهای هانوی کمک کنند. به این صورت که یک کد گری  nبیتی، برای حل مساله برجهای هانوی n دیسکی به کار برده میشود. سمت راست ترین بیت نماینده کوچکترین دیسک است و سمت چپ ترین نماینده بزرگترین دیسک. از صفر شروع میکنیم و به ترتیب میرویم جلو. بیتی که تغییر می کند نشان میدهد که در این مرحله کدام دیسک باید جابجا شود. البته متاسفانه نمی گوید که به کجا میروم آخر!

 همچنین کد گری، یک دور همیلتونی (دور همیلتونی دوری است که از تمام رئوس یک گراف فقط یک بار عبور میکند!) در یک مکعب n بعدی Qn تولید می‌کند که هر کدام از اعداد آن یک راس را نشان می‌دهد.  تا اونجایی که یادم میاد توی کتاب روزن ( منبع درس گسسته مان) یه توضیحاتی راجع به آن داده بود و اتفاقا توی امتحان پایان ترممون هم اثبات همین مساله اومده بود. که یادم میاد به شیوه بازگشتی حلش کرده بودیم. به این صورت که  میتوانیم Qn را از روی Qn-1 بسازیم. یعنی  دو مکعب n-1 بعدی  Qn-1 رو کنار هم می گذاریم. ابتدای بیتهای مکعب اولی صفر و ابتدای بیتهای مکعب دومی یک می گذاریم و بعد راسهای متناظر این دو را به هم وصل میکنیم. مکعب Qn  به دست میاد.  اگر به جزوه طراحی الگوریتم دکتر قدسی هم مراجعه بکنید، می بنیید که به همین روش، اثبات شده که برای هر عددی به فرم  مربع، کد گری وجود دارد.

هم چنین سطر و ستونهای جدول کارنو هم به روش کد گری، کدگذاری شده اند.[2]

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

خب... حالا می رسیم به چگونگی ساخت این نوع کد! میدانید که دو عدد متوالی در کد باینری عادی ممکن است در بیش از یک بیت با هم تفاوت داشته باشند:000,001,010,011,100,101,110,111

که این مساله رو کدهای گری حل کردند و به همین خاطر به آنها کدهای باینری تک فاصله ای هم گفته میشود. چون فاصله همینگ [3] بین دو عدد متوالی در این نوع کد، یک هست:000,001,011,010,110,111,101,100

توجه کنید که  حالت 0 و 7 هم تنها در یک بیت اختلاف دارند.( خاصیت چرخشی بودن کد های گری که قبلا اشاره شد)

یک کد گری n بیتی را میتوان به صورت بازگشتی به دست آورد. به این صورت که وقتی یک لیست n-1 بیتی از کد گری داشته باشیم، آن را وارونه کرده و در انتهای آن لیست قرار میدهیم. آنگاه در سمت راست لیست اول 0 و در انتهای سمت راست لیست دوم 1 میگذاریم. حالت اولیه هم میتواند برای n=0 در نظر گرفته شود که کد گری آن میشودG = { " " }! یا اینکه n=1 در نظر گرفته شود که کد گری آن میشود G = {0, 1}.

وجه تسمیه کدهای آیینه ای هم به همین خاطر است. اگه دقت کنید میبینید که در هر مرحله کد n بیتی از آیینه کردن  کد n-1 بیتی به دست می آید.

تبدیل کد گری به باینری و برعکس:

یادم میاد این، یکی از تمرین هایی بود که استاد کیاسری به ما داده بودند. من نیز بدون اینکه به خودم یه اپسیلوم زحمت بدم، به یکی از مهندسین خانه روی آورده بودم و ایشان هم جواب را صاف کف دست ما قرار داده بودند و  ما نیز...!!

برای تبدیل گری به باینری، بیت سمت چپ را تغییر نمی دهیم و برای یافتن سایر بیتها، بیت متناظر در گری را با بیت قبلی XOR میکنیم. الگوریتم آن در ویکی پدیا بدین صورت نوشته شده است:

۱ Let G[n:۰] be the input array of bits in Gray code
۲ Let B[n:۰] be the output array of bits in the usual binary representation
۳ B[n] = G[n]
۴ for i = n-۱ downto ۰
۵ B[i] = B[i+۱] XOR G[i]

 

برای تبدیل باینری به گری هم کافیست اولین بیت سمت چپ را تغییر ندهیم و سایر بیتها را با بیت سمت چپ خود XOR کنیم.

۱ Let B[n:۰] be the input array of bits in the usual binary representation, [۰] being LSB
۲ Let G[n:۰] be the output array of bits in Gray code
۳ G[n] = B[n]
۴ for i = n-۱ downto ۰
۵ G[i] = B[i+۱] XOR B[i]

یکی از انواع مختلف کد گری n تایی است که به عنوان کد گری غیر دوتایی (۰و۱)هم شناخته می‌شود. یعنی به غیر از ۰ و ۱ از اعداد دیگر هم استفاده می شود. برای مثال یک کد گری سه تایی از بیت‌های {۰و۱و۲} استفاده می‌کند. کد گری سه تایی:

,۰۰۰ ,۰۰۱ ,۰۰۲ ,۰۱۲ ,۰۱۱ ,۰۱۰ ,۰۲۰ ,۰۲۱ ,۰۲۲ ,۱۲۲ ,۱۲۱ ,۱۲۰ ,۱۱۰ ,۱۱۱ ,۱۱۲ ,۱۰۲ ,۱۰۱ ,۱۰۰ ,۲۰۰ ,۲۰۱ ,۲۰۲ ,۲۱۲ ,۲۱۱ ,۲۱۰ ,۲۲۰ ,۲۲۱ ,۲۲۲


یک کد گری (n,k)تایی هم یک کد گری n تایی است که دارای k بیت است مثلاً یک کد گری(۲و۳)برابر است با {۰۰, ۰۱, ۰۲, ۱۲, ۱۱, ۱۰, ۲۰, ۲۱, 22}.

[0]- قبلا گفتم که! غولی، دانشجو و یا شاید هم فارغ التحصیل مهندسی کامپیوتره! البته بعدا در مورد غولی چیزهای عجیبتری خواهید شنید؛ فعلا فقط بدونید این غولی از بس سرش تو کتاب و پژوهشه گاهی وقتا، کمتر به سر و وضع خودش میرسه! مثلا همین موهاش! ببینید چقدر موهاش ژولیده پولیده شده! گاهی وقتا صداش میکنم ژولی غولی!

این عکس مال همین تازگیاست البته! قبلنا بیشتر مو داشت ها! که همونا ژولیده میشدن!  اما از بس سرشو تو کتاب فرو برده، همین دو سه تا تار مو بیشتر نمونده! حالا من هی بهش بگم خوب نیست آدم زندگیش اینجور باشه! هی این گوش نکنه به من! بیا...اینم آخر و عاقبتش!! :دی ( میخواستم به مناسبت تولدش یه شامپوی ضد شوره براش بگیرم! حیف شدا!)

[1]- فرض کنید بخواهیم از جایگاه 7 روی دیسک برسیم به جایگاه  8! یعنی از 0111 به 1000 . اگر که از کد باینری عادی استفاده شود، ممکن است عدد0000 به دست بیاید که معادل است با 0 که به اندازه 8 تا از مکان مورد نظر فاصله دارد!

[2]- جدول کارنو: جدولی که برای ساده سازی توابع به کار برده میشود. اگه منطقی گذرانده باشید، حتما میدانید. اما اگر آدم بی منطقی هستید(!) فقط این توضیح مختصر رو بدم که  هر تابع بولی رو میشود به صورت مجموعه ای از مینترم هانوشت.(تو روخدا بی خیال شید که بپرسید مینترم دیگه چیه؟! :دی) جدول کارنو شامل خانه هایی هست که هرکدام  نشان دهنده یک مینترم هستند. هر دو خانه همسایه فقط در یک متغیر با هم تفاوت دارند.(به خاطر همین برچسب گذاری گری). در نتیجه میشود متغیر مشترکشان را حذف و مجموع آنها راساده کرد.

 Hamming distance-[3]: تعداد بیتهای متفاوت دو الگوی بیتی.

 

نوشته شده توسط محبوبه  | لینک ثابت |
 Powered By  BLOGFA.COM
 
جنبش بزرگ وبلاگی حامیان مهندس میرحسین موسوی