همه چیز از همه جا برای تو

دنیای سرگرمی های خاص خاص

همه چیز از همه جا برای تو

دنیای سرگرمی های خاص خاص

مفاهیم کدینگ (Coding Concepts)

1-1 مفاهیم کدینگ (Coding Concepts) 
برای آنکه بتوانیم یک کلمه (Word) از داده ها را بگونه ای کد گذاری کنیم که قابلیت تشخیص و تصحیح خطا را داشته باشد، باید تعداد بیت هاى آن را افزایش دهیم. اگر طول یک Data Word به اندازه D بیت باشد، پس از کد گذاری یک کلمه کد شده (Codeword) به اندازه C بیت خواهد بود. بگونه ای که C>D می‌باشد. پس حالا ما بجای 2D حالت ممکن، 2C حالت ممکن داریم. ولی تمام این حالت ها درست نیستند، و این همان چیزی است که باعث می شود سیستم بتواند وجود خطا را تشخیص دهد. یعنی اگر یک عدد در یکی از این حالات غیرمجاز باشد، سیستم می فهمد که خطایی روى داده است. در بعضی از روش ها، سیستم در یک سری از حالات می تواند خطای بوجود آمده را نیز اصلاح کند. روش ارائه شده باید این قابلیت را داشته باشد که از بین C بیت موجود D بیت اصلی را خارج کند. به این عمل اصطلاحا Decoding می گویند. یکی از مشکلات استفاده از کدینگ این است که سیستم مجبور است تا یک مدت زمانى را صرف عملیات Encoding و Decoding کند که باعث ایجاد سربار (Overhead) در سیستم می شود.

1-2 کد همینگ

در دهه ۱۹۵۰ میلادی ریچارد همینگ که در آزمایشگاههای شرکت بل کار می کرد به معرفی دسته ای از کد های اصلاح کننده خطا پرداخت که بنام خود او کدهای همینگ خوانده می شوند. شاید ساده ترین روش برای آشکار کردن خطای یک بیت در یک بایت، استفاده از بیت توازن است. 


1-3 فاصله همینگ (Hamming Distance) 

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

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

چند مثال برای فاصله همینگ بین چند رشته:

«toned»و«roses» فاصله همینگ سه هست.

۱۰۱۱۱۰۱ و ۱۰۰۱۰۰۱ فاصله همینگ دو هست.

۲۱۷۳۸۹۶ و ۲۲۳۳۷۹۶ فاصله همینگ سه هست.

کدهای 101 و 011 در 2 بیت با یک دیگر متفاوت هستند. در نتیجه فاصله همینگ بین آنها برابر 2 است. اما کدهای 101 و 100 فقط در یک بیت با هم تفاوت دارند. در نتیجه اگر یک خطا در بیت کم ارزش آنها روى دهد، یکی از آنها را به دیگری تبدیل می کند و سیستم متوجه وجود خطا نخواهد شد. فاصله همینگ به اندازه 2 تضمین می کند که اگر یک خطای تک بیتی اتفاق بیفتد سیستم حتما متوجه بروز خطا خواهد شد. 

در شکل روبه رو مکعب باینری را میبیند که در هر گوشه آن یک عدد باینری قرار دارد . در این مکعب هر ضلع یک فاصله همینگ به حساب می آید . برای مثال فاصله بین دو عدد 001 تا 010 دو ضلع است به عبارتی فاصله همینگ آن 2 است .    
 
                                                     فاصله همینگ 




1-4 فاصله کد (Code Distance) 

فاصله کد برابر است با کمترین فاصله همینگ که بین هر دو کد موجود در یک مجموعه کد وجود دارد. یعنی اگر مثلا در یک روش کدینگ فاصله کد برابر 2 باشد به این معنی است که هیچ کدام از کدها با کدهای دیگر فاصله همینگ کمتر از 2 ندارند. برای مثال مجموعه کدهای {001، 010، 100، 111} همگی باهم فاصله 2 دارند. در نتیجه این کد می تواند هر خطای تک بیتی را تشخیص دهد. 

به عنوان مثالی دیگر کدهای {000، 111} داراى فاصله 3 هستند پس می توانند هر خطای تک بیتی یا دو بیتی را تشخیص دهند. اما اگر فرض شود احتمال خطای دو بیتی کم است، این کد را می توان به عنوان روشى که می تواند خطاهای تک بیتی را اصلاح (Correct) کند، نیز استفاده شود. 


1-5 محدودیت تشخیص و تصحیح (Detection and Correction) 

به عنوان یک تعریف ریاضی می توان گفت : برای آنکه بتوانیم تا حداکثر t بیت خطا را تشخیص دهیم، نیاز به حداقل فاصله کد به اندازه t+1 داریم. ولی برای آنکه بتوانیم تا حداکثر t بیت خطا را تصحیح کنیم، نیاز به حداقل فاصله کد 2t+1 داریم. 


1-6 کدینگ و افزونگی (Coding and Redundancy)

فرض کنید که یک مجموعه کد شامل دو حالت به صورت {000، 111} باشد که برای نشان دادن تنها یک بیت به کار می رود. در واقع عدد 0 به شکل 000 کد شده است و عدد 1 به شکل 111. این سیستم کد دهی معادل سیستم های TMR می باشد. در واقع کدینگ همیشه همراه با افزونگی (Redundancy) می‌باشد که در نتیجه می توان از تکنیکهاى بکار رفته شده برای افزونگی در کدینگ نیز استفاده کرد. مثلا Duplex یکی از راه هاى افزونگی است که در این روش Codeword دو بار عینا تکرار می شود. برای مثال برای یک تک بیت دو حالت وجود دارد که 00 و 11 است که از دو بار تکرار 0 و 1 به دست آمده اند. 


1-7 جداپذیری کد (Code Separability) 

داده های کد شده می توانند دو حالت داشته باشند :

    جدا پذیر (Separable)


کدی را جداپذیر می گوییم که بیت هاى مربوط به داده اصلی با بیت های اضافه شده برای کد از هم جدا باشند. در این حالت استخراج اطلاعات از کد بسیار ساده تر است. چون تنها کافیست که بیت هاى مربوط به کد را کنار بگذاریم. 


    جدا ناپذیر (Non-Separable) 

در کدهای جداناپذیر داده های اصلی با کدهای اضافی با هم ترکیب شده اند و جدا سازی آنها از یک دیگر نیاز به انجام پردازش های اضافی دارد. 


2-1 روشهای کدینگ (Coding methods) 


2-1-1 کد Parity (Parity Coding) 

پریتی (Parity) ساده ترین روش کد گذاری جدا پذیر است. در این روش اطلاعات کد شده شامل N بیت داده اصلی به همراه یک بیت اضافه که Parity را نگه می دارد، می‌باشد. دو نوع Parity وجود دارد:

     Even (زوج)

در روش زوج بیت Parity به گونه ای تنظیم می شود که تعداد یک ها در کل بیت ها (داده اصلی و Parity) زوج باشد. 


     Odd (فرد)

روش فرد بر عکس عمل می کند. یعنی در روش فرد بیت Parity به گونه ای تنظیم می شود که تعداد یک ها در کل بیت ها (داده اصلی و Parity) فرد باشد. 

تعداد کل بیت ها در نهایت برابر (N+1) است. در این حالت عملا به میزان 1/N بیت جدید به داده اضافه شده است. کد Parity داراى فاصله همینگ 2 می‌باشد که در نتیجه می تواند هر خطای تک بیتی را تشخیص دهد ولی نمی تواند هیچ نوع تصحیحی انجام دهد. کد Parity نمی تواند یک خطای دو بیتی را تشخیص دهد، ولی خطاهای سه بیتی را می تواند تشخیص دهد. در کل کد پریتی قابلیت تشخیص خطا در تعداد فرد را دارد .


    Parity فرد بهتر است یا زوج؟ 

اینکه کدام یک از دو حالت Parity موثرتر هستند کاملا بستگی به شرایط دارد. یکی از خطاهای رایج به نام Burst Error یا All-Bits Error وجود دارد . در این نوع خطا همه بیت ها یا 1 می شوند و یا 0 می شوند . در صورتی که از Parity زوج استفاده شود آنگاه خطای همه 0 (All-0'S) قابل تشخیص نیست. ولی با انتخاب Parity فرد این خطا تشخیص داده می شود . پس اگر احتمال خطای همه 0 بیشتر است بهتر است که از Parity فرد استفاده شود. اگر احتمال خطای همه 1 بیشتر است، آنگاه دو حالت وجود دارد اگر تعداد کل بیت ها ( همراه با Parity ، N+1) زوج باشد باید از Parity فرد و اگر تعداد کل بیت ها فرد باشد از Parity زوج استفاده کرد .


می توانیم بجای آنکه به کل بیت ها یک Parity اختصاص دهیم به هر گروه از آنها، مثلا هر یک بایت، یک Parity اختصاص دهیم. در این حالت بدیهی است که میزان Overhead از 1/N به M/N افزایش خواهد یافت. (M تعداد گروه یا بایت ها است) در این حالت حد اکثر M خطا قابل تشخیص است، البته به شرطی که خطا ها در بایت های مختلف باشند. اگر هر دو نوع خطای همه 0 و همه 1 ممکن است اتفاق بیفتد می توانید از پریتى Parity برای یک بایت و از Parity فرد برای بایت بعدی استفاده کنید. 


2-1-2 کد همینگ

در اصل کد همینگ یک نوع کدگذاری از خانواده ی کدگذاری پریتی است . در روش همینگ از سه بیت توازن برای آشکارسازی و اصلاح خطا استفاده میشود. همانطور که در شکل مشخص است چهار بیت d1 الی d4 به عنوان داده ورودی در نظر گرفته میشوند. سپس با ترتیب نشان داده شده بیتهای توازن p1 تا p3 از XOR کردن بیت ها محاسبه می شوند و در نهایت داده هفت بیتی بدست آمده ارسال می گردد.




           کد همینگ                                                  

                                           نحوه محاسبه بیتهای توازن در کد همینگ



                           کد همینگ 

نمایش گرافیکی از 4 بیت اطلاعات و 3 بیت پریتی که نشان می دهد کدام بیت داده در کدام بیت پریتی اثر گذار است.


در مقصد بیت توازن با بیتهای گروه خود XOR میشود مثلا بیتهای p1 و d1 و d2 و d4 با هم XOR می شوند و نتیجه به عنوان بیت اول نشانه s1 در نظر گرفته میشود به همین ترتیب بیتهای دوم و سوم نشانه هم بدست می آیند. هرگاه هر سه بیت نشانه صفر باشد داده درست منتقل شده است. اما در صورت یک بودن هر یک از بیت های خطا رخ داده است. اگر سه بیت نشانه را از کوچک به بزرگ در کنار هم قرار دهیم یک عدد سه بیتی بدست می آید که مقدار آن نشان دهنده محل وقوع خطاست . با عوض کردن بیت مورد نظر داده اولیه بدست می آید. باید توجه داشت که این روش همینگ امکان اصلاح یک خطا را دارد و در صورت بروز دو خطا فقط امکان آشکار سازی وجود دارد.


            کد همینگ      

                                                خطا در بیت ششم رخ داده است


برای آنکه بدانیم به چند بیت برای Parity نیاز داریم ، باید طبق رابطه زیر عمل کنیم : اگر تعداد بیت های داده برابر D باشد و تعداد بیت های Parity برابر R باشد. در آن صورت جمعا" D+R بیت داریم که هر کدام از آنها می تواند دچار خطا شود یعنی با فرض اینکه خطا های ما تک بیتی هستند، D+R حالت مختلف خطا داریم. علاوه بر حالت های خطا یک حالت درست هم داریم که در آن هیچ بیتی دچار اشکال نشده است. پس جمعا D+R+1 حالت ممکن وجود دارد که باید توسط Parity نمایش داده شود.

پس با توجه به اینکه R بیت Parity وجود دارد می توانیم 2R حالت مختلف داشته باشیم که شامل حالت های خطا و درست می شود. پس اگر داشته باشیم :

                                                                        2R >= R+D+1       

آنگاه می توانیم مطمئن باشیم که تعداد بیت های Parity کافى است.



2-1-3 جمع کنترلی ( Checksum )

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

2-1-3-1 Single-Percision (تک دقتی):

در این روش جمع به پیمانه (Modulo) 2D انجام می شود. یعنی حاصل جمع به 2D تقسیم می شود و باقیمانده آن فقط در نظر گرفته می شود. یا به عبارتی تنها D رقم سمت راست حاصل جمع در نظر گرفته می شود.


2-1-3-2 Double-Percision (دقت مضاعف):

کاملا شبیه Single است ولی بجای 2D از 22D استفاده می شود که در نتیجه این روش خطاهای بیشتری را می تواند کشف کند.



2-1-3-3 Residue Checksum (باقیمانده):

 در این روش بیت هاى اضافی بعد از D اُمین بیت که در روش Single دور ریخته می شد، مجددا با خود داده اصلی جمع می شود که در نتیجه قابلیت اطمینان سیستم بالاتر می رود. زیرا وجود خطا در آن بیت هاى اضافی نیز تاثیر گذار هستند. 


2-1-3-4 Honeywell Checksum :

در این روش هر دو کلمه را به هم می چسبانند و سپس کل این مجموعه های دوتایی را با هم جمع میکنند و نتیجه را به پیمانه 22D در نظر می گیرند. حسن این روش این است که اگر یک خطا همواره روی یکی از بیت هاى هر کلمه (مثلا بیت سوم) اتفاق بیفتد، در گونه های قبلى ممکن بود تشخیص داده نشود، ولی در این روش جلوى این نوع خطا ها نیز گرفته می شود. 


    نکته : روشهای Checksum فقط می توانند وجود خطا را تشخیص دهند ولی نمی توانند آن را تصحیح کنند. به همین خاطر اگر خطایی روى دهد، کل بلوک باید مجددا ارسال شود. 




2-1-4 کد برگر (Berger Code )

کد بِرگر یک روش جداپذیر (Separable) است. این روش به این شکل عمل می کند که ابتدا تعداد یک های درون داده را می شمارد، سپس از عدد به دست آمده مکمل می گیرد و سپس این عدد به دست آمده را در کنار عدد اصلی قرار میدهد. 

برای مثال فرض کنید عدد 11101 را داریم. درون این عدد چهار 1 وجود دارد که فرم باینرى آن 100 می شود و مکمل آن 011 است. حالا اگر این عدد را در کنار عدد اصلی قرار دهیم، داریم 11101011 . این روش می تواند هر نوع خطای Unidirectional را تشخیص دهد، چه خطا از 0 به 1 باشد یا برعکس آن. اما اگر هم زمان بعضی 0 ها به 1 تبدیل شوند، و همان تعداد 1 نیز به 0 تبدیل شوند، نمی تواند خطا را تشخیص دهد. 





2-1-5 کد افزونگی چرخشی CRC

یک کد افزونگی چرخشی (به انگلیسی: Cyclic redundancy code) (سی‌آرسی) تابع درهم‌سازی غیرایمنی است که جهت تشخیص تغییرات تصادفی رو داده‌های خام طراحی شده‌است. این تابع عموما در شبکه‌های مخابراتی دیجیتال و وسایل ذخیره‌سازی داده‌ها از جمله دیسک سخت مورد استفاده قرار می‌گیرد. یک دستگاه دارای قابلیت سی‌آرسی، یک توالی کوتاه و با طول ثابت را، به نام کد سی‌آرسی (یا فقط سی‌آرسی)، برای هر بلاک از داده‌ها محاسبه نموده و آن را همراه با داده‌ها ذخیره یا ارسال می‌کند. زمانی که یک بلاک دریافت یا خوانده می‌شود دستگاه محاسبه را تکرار می‌کند؛ در صورت مغایرت با کد محاسبه شده قبلی مشخص می‌شود که این بلاک دارای خطای داده است و در این حالت دستگاه ممکن است عملی را جهت اصلاح خطا از جمله خواندن یا درخواست ارسال مجدد بلاک انجام دهد. اصطلاح سی‌آرسی می‌تواند به کد اعتبارسنج یا تابع تولید کد اطلاق شود. سی‌آرسی‌ها به جهت پیاده‌سازی ساده در سخت‌افزار دودویی، سادگی تحلیل ریاضی آن‌ها و عملکرد خوب در تشخیص خطاهای معمول حاصل از اختلال در کانال‌های انتقال دارای محبوبیت زیادی هستند. سی‌آرسی توسط W. Wesley Peterson اختراع و در مقاله ۱۹۶۱ وی منتشر شد . سی‌آرسی 32 بیتی پیشنهادی موسسه مهندسین الکتریک و الکترونیک (IEEE)، که در اترنت و سایر جاها استفاده شده‌است، در کنفرانس مخابراتی سال 1975 ظاهر شد.

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

اگرچه سی‌آرسی‌ها می‌توانند با استفاده از هر میدان محدودی ساخته شوند، همه سی‌آرسی‌های پرکاربرد از میدان محدود GF(2) بهره می‌برند. این میدانی از دو عنصر، عموما به نام ۰ و ۱، است که به راحتی با معماری کامپیوتر سازگار است. یک دلیل مهم برای محبوبیت سی‌آرسی‌ها برای تشخیص تغییرات تصادفی داده‌ها اطمینان از کیفیت آن‌ها است. نوعا"، یک سی‌آرسی nبیتی، که برای یک بلاک داده با طول دلخواه محاسبه شده‌است، هر حوزه خطای با طول کمتر از n بیت (به عبارت دیگر، هر تغییری که محدوده آن بیش از n بیت مجاور از داده‌ها نباشد) و 1-2^(-n) تعداد از سایر حوزه‌های با طول بیش از n بیت را تشخیص می‌دهد. خطاها در هیچ‌یک از کانال‌های انتقال و رسانه‌های ذخیره‌سازی مغناطیسی دارای توزیع تصادفی نیستند و در نتیجه فایده خواص سی‌آرسی‌ها را نسبت به سایر روش‌های تشخیص خطا از جمله کدهای چندگانه زوجیت بیشتر می‌کنند. ساده‌ترین سامانه تشخیص خطا، بیت زوجیت، در واقع یک سی‌آرسی عادی است که از مقسم دوبیتی ۱۱ استفاده می‌کند.



2-1-5-1 سی‌آرسی‌ها و تمامیت داده‌ها

سی‌آرسی‌ها، به خودی خود، راهکار مناسبی برای حفاظت در مقابل تغییرات عمدی روی داده نیستند (مثلا در برنامه‌های اعتبارسنجی)، چون مبانی ساده ریاضیات آن‌ها باعث می‌شود که بتوان هر تغییر دلخواه را روی داده‌ها طوری اعمال کرد که سی‌آرسی داده‌ها تغییر نکند. اغلب این فرض غلط وجود دارد که وقتی پیامی به همراه سی‌آرسی آن از یک کانال آزاد دریافت می‌شود و سی‌آرسی دریافتی با سی‌آرسی محاسبه شده مطابقت می‌کند پس پیام ممکن نیست در حین دریافت تغییر کرده باشد. این درست نیست چون هر دوی آن‌ها می‌توانند تغییر کرده باشند، به طوری که سی‌آرسی جدید با پیام جدید مطابقت کند. بنابراین سی‌آرسی‌ها می‌توانند جهت بررسی درستی داده‌ها استفاده شوند ولی نه برای اطمینان از تمامیت آن. ایجاد پیام‌های دیگری که همان سی‌آرسی را ایجاد کنند کار ساده‌ای است، خصوصا پیام‌هایی که بسیار شبیه پیام اصلی هستند. طبق طراحی پیامی که بسیار شبیه پیام اصلی است (و تفاوت آن تنها در یک الگوی تداخل تصادفی است) سی‌آرسی کاملا متفاوتی خواهد داشت و بنابراین تشخیص داده خواهد شد. در مقابل، یک راه موثر برای محافظت پیام‌ها در برابر تغییرات عمدی استفاده از کدهای اعتبار سنجی پیام همچون HMAC است.


2-1-5-2 محاسبه سی‌آرسی

برای محاسبه یک سی‌آرسی دودویی nبیتی، بیت‌های ورودی را در یک سطر بنویسید، و الگوی (n+1)بیتی را که نشان‌دهنده مقسم سی‌آرسی است (و چندجمله‌ای نامیده می‌شود) زیر سمت چپ‌ترین بیت قرار دهید. در زیر، اولین محاسبه برای ایجاد یک سی‌آرسی ۳بیتی نشان داده شده‌است:

                                                   
                                                                   11010011101100 <--- ورودی

                                                                                       1011 <--- مقسم (4 بیت) 

                                                                    ----------------------

                                                                   01100011101100 <--- نتیجه


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



                                                                   00000000001110 <--- نتیجه محاسبه قبلی

                                                                   1011                     <--- مقسم

                                                                    ----------------------- 

                                                                   00000000000101 <--- باقی‌مانده (3 بیت)


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


2-1-5-3 مشخصات سی‌آرسی

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

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


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



    یک پیاده‌سازی خاص ممکن است نتیجه را با یک الگوی ثابت XOR کند.


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



    ترتیب بایت‌ها: در سی‌آرسی‌های چند بایتی، ممکن است این تردید پیش آید که آیا بایت منتقل شده اول، کم‌ارزش‌ترین بایت است یا باارزش‌ترین. به عنوان مثال در برخی روش‌ها بایت‌های سی‌آرسی ۱۶بیتی را جابجا می‌کنند.


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


2-1-5-4 سی‌آرسی‌های پرکاربرد و استاندارد

اگرچه سی‌آرسی‌ها از اجزای معیارها متعددی هستند اما خودشان، از منظر وجود الگوریتمی جهانی، مورد قبول نیستند. به عنوان مثال دو چندجمله‌ای سی‌آرسی-۱۲، ده نوع مستند سی‌آرسی-۱۶ و چهار سی‌آرسی-۳۲ وجود دارد. این چندجمله‌ای‌ها عموما بهترین چندجمله‌ای‌های ممکن نیستند. بین ۱۹۹۳ و ۲۰۰۴، کوپمن، کستاگنولی و سایرین فضای چندجمله‌ای‌ها تا ۱۶ بیت، 24 و ۳۲ بیتی را جهت یافتن مثال‌هایی با کارایی بهتر (از نظر فاصله هامنی برای یک طول پیام خاص) از چندجمله‌ای‌های پروتکل‌های پیشین بررسی کردند و بهترین آن‌ها را در جهت بهبود ظرفیت تشخیص خطای استانده‌های آتی منتشر کردند. به طور خاص، iSCSI یکی از یافته‌های این پژوهش را مورد استفاده قرار داده‌است.



2-1-6 کد گری

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

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




2-1-6-1 تاریخچه و کاربردهای علمی

کد گری قبل از آن که در مهندسی به کار رود در جدول‌ها پازل‌های ریاضی به کار برده می‌شد، ریاضیدان فرانسویEmile Boudat از کد گری در سال۱۸۷۸در تلگراف استفاده کرد و برای این کارش مدال دریافت کرد و اما کاربردهای آن، از کد گری به عنوان یک رمزگذار استفاده می‌شود که نسبت به رمزگذار عادی برتری دارد. در نمایش کد گری خاصیت دایره‌ای بودن آن باعث می‌شود که دو عدد دو سر نیز فقط در یک بیت متفاوت باشند. کد گری یک دور همیلتونی در یک مکعب n بعدی Qn تولید می‌کند که هر کدام از اعداد آن یک راس را نشان می‌دهد و نیز در الگوریتم‌های ژنتیکی از آن استفاده می‌شود و نیز البته برچسب گذاری جدول کارنو از موارد دیگر استفاده آن است. زمانی کد گری برای آدرس دهی حافظه در کامپیوتر استفاده می‌شود کامپیوتر نیروی کمتری صرف یافتن آدرس‌ها می‌کند چون هر آدرس با قبلی فقط در یک بیت متفاوت است. طراحان مدارهای منطقی از کد گری به طور گسترده برای عبور چند بیت اطلاعات بین سیستم‌های همزمان استفاده می‌کنند.


                          کد گری

                                 
 
                                                       دایره کد گری


2-1-6-2 انگیزهٔ پیدایش کد گری

بعضی از دستگاه‌ها وضعیت دستگاه را با کدهای باینری نمایش می‌دهند، اگر این دستگاه‌ها از کد باینری عادی استفاده کند این دو وضعیت پشت سر هم خواهند بود 011 -- > 100 و مشکل کد باینری عادی این است که در حالت طبیعی خیلی بعید نست که چند بیت همزمان تغییر کنند همان طور که در بالا نمایش داده شده‌است که در کد باینری عادی هر سه بیت همزمان تغییر کرده‌اند اما می‌توان اعداد را طوری در کنار هم قرار داد که فقط در یک بیت متفاوت باشند و تغییر زیادی نکنند مثلا" 011 − 001 − 101 − 100 پس کد باینری منعکس شده یا همان کد گری این مشکل را حل می‌کند زیرا که فقط یک بیت در آن‌ها تغییر می‌کند.


   
Gray Binary  
000 000 0
001  001  1
 011  010  2
 010  011  3
 110  100  4
 111  101  5
 101  110  6
 100  111  7


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

نحوه تبدیل کد باینری به کد گری به شکل زیر است :

   

                  کد گری

نحوه تبدیل کد گری به کد باینری به شکل زیر است :
     
                    کد گری

نظرات 0 + ارسال نظر
برای نمایش آواتار خود در این وبلاگ در سایت Gravatar.com ثبت نام کنید. (راهنما)
ایمیل شما بعد از ثبت نمایش داده نخواهد شد