کدهای کشف خطای c r c

***********

در روش CRC به ازای مجموعه بیت های کل یک فریم ، تعدادی بیت کنترلی به نام کد CRC محاسبه و به انتهای فریم اظافه می شود. تعداد بیتهای کد کشف خطای CRC مستقل از طول فریم و ثابت است. مبنای محاسبه کدهای CRC با استفاده از تقسیم چند جمله ای است که روش محاسبه آن با ارائه یک مثال توضیح داده شده است:

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

11100101 داده اصلی

11100101  رشته داده

76543210  موقعیت توانی

D ( X ) = 1.x7+ 1.x6+ 1.x5+ 0.x4+ 0.x4 + 0.x3 + + 1.x2+ 0.x1 + 1.x0

D( x ) = x7 + x6 + x5+ x2+ 1

ب ) بین گیرنده و فرستنده یک جمله به نام مولد قرارداد می شود . این چند جمله ای انتخابی است ولی دادای ویژگی (( کاهش ناپذیری در میدان گالوای ( 2 ) GF )) است . بحث در مورد این ویژگی خارج از حیطه این تحقیق است فعلاً فرض کنید که این چند جمله ای ، به نحوه مناسبی انتخاب شده است . در مثال مان چند جمله ای زیر را انتخاب کرده ایم:

G ( x ) = x2+ 1

ج ) برای تولید کد CRC ، ابتدا چند جمله ای داده در جمله با بزرگترین توان مولد ضرب می شود . سپس چند جمله ای xn. D ( x )  بر چند جمله ای مولد تقسیم می شود . ( n بالاترین توان چند جمله ای مولد است . ) تقسیم در مبنای 2 انجام می شود ، یعنی ضرایب جملات با توان مساوی با هم XOR خواهد شد  و تفریق معنا ندارد.

D ( x ) .x2 = x9 + x8 + x7+ x4+ x2

x9 + x8 + x7+ x4+ x2       mod  G ( x )

جواب : که در اینجا  x9 + x8 + x7+ x4+ x2 تقسیم بر x2+1  می شود .

که خارج قسمت آن : x7 + x6 + x4+ 1 و باقی مانده آن +1 بدست می آید.

د) باقیمانده xn.D ( x )  بر  D ( x ) با مقسوم جمع می شود و نتیجه به عنوان داده جدید به شکل رشته بیت ارسال می گردد. با این کار در حقیقت باقیمانده تقسیم به عنوان کد های کنترل خطا در انتهای داده ها ارسال خواهد شد.

x9 + x8 + x7+ x4+ x2+1                11100101 01