اطلاعیه

Collapse
No announcement yet.

طراحی مدار Cyclic Reduancy Check

Collapse
X
Collapse
 
  • صفحه of 1
  • فیلتر
  • زمان
  • Show
Clear All
new posts
قبلی template بعدی
    #1

    طراحی مدار Cyclic Reduancy Check

    سلام
    من می خواهم مدار crc را روی برد بورد ببندم. اما طرح اونا بلد نیستم .اگ میشه مدار crc که با نرم افزار های الکترونیکی مثل protous شبیه سازی کنید. در ضمن از کدام ای سی استفاده کنم. فوری ممنون
    برچسب ها: check, cyclic, reduancy, طراحی, مدار
    #2
    پاسخ : طراحی مدار Cyclic Reduancy Check

    سلام .....................

    در مورد طراحی مدار CRC سوال فرموده بودید، اما محدودیت ها و پارامترهایی که برای این طراحی لازمه اعم از g رو تعیین نکردید .. برای اینکه بتونیم یه جمعبندی کلی در این تاپیک داشته باشیم، گفتم در ابتدا یه بحثی در این مورد داشته باشیم و در انتها هم به موارد طراحی اون بپردازیم و در خاتمه هم طراحی رو خودتون انجام بدید ..

    CRC مخفف Cyclic Redundancy Check هست و معادل اون میشه کنترل افزونگی چرخشی .. اما این کد چه کدیه؟ کاربردش چیه؟ چه انواعی داره؟ انعطاف اون تا چه میزان هست؟ اینها مواردیه که باید روی تک تکشون صحبت کنیم .. ببینید یکی از مواردی که توی ارتباطات دیجیتال وجود داره اینه که هنگامی که دیتا ر ارسال میکنیم، هیچ درکی از دریافت صحیح اون نداریم یعنی اینکه دیتا از دید فرستنده بدون خطا ارسال میشه اما در هنگامی که به فرستنده میرسه ، ممکنه دچار خطا شده باشه و این امکان باید توسط متد خاصی بررسی بشه .. روش های مختلفی برای کنترل و آشکارسازی خطا وجود داره که با Accuracy های مختلف میتونن به وقوع خطا اعتراف کنن .. CRC یکی از این روش هاست که برای آشکارسازی خطا به کار میره و روش کار بسیار جالبی داره .. بنابراین کاربرد CRC برای آشکارسازی خطاست ..

    برحسب الگوریتمی که برای اون تعریف میشه از انواع مختلفی هم برخورداره که تنوع اونها بیشتر به تعریف Generator Polynomial مربوط میشه .. از نظر انعطاف هم میتونیم چندجمله ای g مون رو به هرترتیبی که میخوایم تعریف کنیم .. تنها باید به این نکته توجه داشته باشیم که این g که انتخاب میکنیم، باید g مناسبی باشه .. مناسب بودن انتخاب برای g رو در ادامه تعریف میکنیم ..

    اما CRC به چه ترتیبی به آشکارسازی خطا کمک میکنه؟ چگونه هست که میتونیم اون رو برای دیتامون تعریف کینم؟ خب برای سوال اول باید لغت این کد رو بررسی کنیم .. Redundancy .. این کلمه یعنی افزودگی (مضاعف ..) .. در حقیقت روال این کد به این ترتیبه .. یک قالبی از بیت ها رو به دیتا اختصاص میدیم که اونها رو با D نمایش میدیم .. D دیتای ما هست که در فرستنده منتظر ارسال شدنه .. یک قالب دیگه تعریف میکنیم به نام FCS که برای یک کد خاص r بیتی در نظر گرفته شده .. FCS مخفف Frame Check Sequence هست و در واقع همون قالبیه که باید در کنار قالب دیتامون قرار بگیره و کلمه ی Code رو برای ما بسازه .. از این جهته که به اون میگن کد افزونگی .. در حقیقت FCS در ادامه ی بیت های دیتامون قرار میگیره و کلمه ی کدی رو میسازه که برای ارسال آماده شده .. در نتیجه فرستنده این کلمه رو به عنوان خروجی، روی خط قرار میده تا گیرنده همین کلمه رو دریافت کنه و پس از پروسسی خاص، تشخیص بده که آیا دیتا خطادار بوده یا نه؟

    این از رویه ی کلی CRC .. اما از چه طریقی این الگوریتم رو پیاده سازی کنیم؟ در حقیقت در اینجا از چند جمله ای ها استفاده می کنیم و با روابطی که از طریق اونها تعریف می کنیم، میتونیم CRC رو پیاده سازی کنیم .. برای این منظور به روش زیر عمل میکنیم ..

    -- دیتای D رو با D(x) نشون میدیم و اینطور تعریف میکنیم که D(x) چند جله ای k بیتی هست که ضرایب اون میشن بیت های رشته ی باینریمون .. در حقیقت یک میدان بیتی تعریف کردیم که متغییر اون بر حسب x تعریف شده .. بنابر این برای رشته ی بیت فرضی 1100101010 چندجمله ای D(x) برابر خواهد بود با ..

    http://i39.tinypic.com/2005jwj.png


    -- میدان بیتی r بیتی r(x) رو تعریف میکنیم با این هدف که این چند جمله ای برابر همون چند جمله ای FCS یا Checksum ما باشه ..

    -- در انتها هم چند جمله ای V(x) رو تعریف میکنیم با این هدف که مجموع data و FCS ما باشه .. در نتیجه از نظر حجم بیتی برابر خواهد بود با n=k+r ..

    در این مرحله باید یه قضیه تعریف کنیم و بر طبق اون؛ الگوریتم CRC رو پیاده سازی کنیم .. قضیه ی معروف CRC به مضمون زیر تعریف میشه ..

    قضیه : اگر g(x) یک چند جمله ای از درجه ی n-k و فاکتوری از Xⁿ+1 باشد، در این صورت g(x) یک کد چرخشی CRC(n,k) را تولید میکند که در آن چند جمله ای کد V(x) برای دیتای D از رابطه ی زیر به دست می آید ..
    http://i39.tinypic.com/2jdf5ht.png


    تحلیل قضیه : در قضیه ی بالا روی چندین نکته تاکید شده که بد نیست اونها رو اندکی باز کنیم ..

    اولا خروجی قضیه چی هست؟ Code Word یا همون کلمه ی کد مورد نظر .. این کلمه ی کد رو کجا معرفی کردیم؟ همون قسمتی که D و r رو تعریف کردیم .. یعنی در حقیقت خروجی این قضیه دیتاییه که کد شده یا به عبارت بهتر با هدر FCS همراه شده و برای ارسال آماده هست ..

    دوما از یک مولد g صحبت کردیم، این Generator Polynomial وظیفه ی تولید کد FCS رو بر عهده داره و خواهیم دید که از چه طریق اینکار رو انجام میده ..
    سوما از r(x) ای صحبت کردیم که به عنوان باقیمانده طلقی میشه .. باقیمانده ی تقسیم زیر ..

    http://i41.tinypic.com/kebt5i.jpg


    اما از این قضیه به چه ترتیبی استفاده میکنیم؟ با یک مثال موارد رو ادامه میدیم ..

    Ex: در یک کد CRC(8,6) با چندجمله ای مولد g(x)=x^3+x^2+1 کلمه ی کد را برای متناظر با دیتای D=11101 را بیابید .. خب برای به دست آوردن کلمه ی کد باید از رابطه ی بالا مقدار ضرب رو به دست بیاریم و برای محاسبه ی r(x) هم به تقسیم چند جمله ای بپردازیم .. باقیمانده ی حاصل از تقسیم میشه r(x) و ضرب ب اولیه هم میشه بخشی از CodeWord و در نتیجه مجموع اینها میشه CodeWord نهایی برای اون دیتا .. (محاسباتش با شما ..)

    این روش به دست آوردن کلمه ی کد رو روش سیستماتیک میگن و به این دلیل که از روابط حاکم بر چندجمله ای ها استفاده کردیم و کلمه ی کد نهایی رو به دست آوردیم .. مجموعه عملیاتی که تا به اینجا انجام شد، همه برای فرستنده بودن اما در گیرنده به چه ترتیبی این کد؛ باز خوانی میشه یا به عبارتی دیکود میشه و تشخیص داده میشه که خطایی رخ داده یا نه؟ V(x) ای که برای فرستنده ارسال میشه طبیعتا باید بر g(x) تقسیم پذیر باشه (کاملا میشه اثباتش کرد ..) از این بخشپذیری استفاده میکنن و در نتیجه تشخصی میدن که کلمه ی کد معتبر هست یا نه (خطایی در هنگام ارسال در بیت های اون روی داده یا نه .. تنها اگه یک بیت اون هم تغییر کنه دیگه نمیتونه بر مولد بخشپذیر باشه ..)

    اما اجازه بدید حالتی رو بررسی کنیم که خطا رخ داده و ببینیم آیا امکان داره که در هنگام وقوع خطا، باز هم گیرنده متوجه کد غیر معتبر نشه؟! جواب اینه که ممکنه!! اما چطور؟ ببینید فرض می کنیم که CodeWord ما دارای خطای Er باشه در نتیجه میشه به راحتی نشون داد که CodeWord=V + Er .. همونطور که گفتیم CodeWord باید بر g بخش پذیر باشه در نتیجه میایم و CodeWord ای رو که Error Detection براش رخ داده رو بر g تقسیم میکنیم .. انتظار داریم مولفه ی اول باقیمانده نداشته باشه اما مولفه ی دوم باقیمانده داشته باشه .. توی یه Paper (الان دقیقا اسمش خاطرم نیست ..) ثابت کرده بودن که بیشتر خطا هایی که در ارسال یا دریافت اطلاعات اتفاق میفته، با CRC قابل تشخیص هستن (حتی عدد احتمالش رو هم بررسی کرده بودن ..) .. در نتیجه اکثر خطاها قابل تشخیص هستن اما اوههایی که قابل تشخیص نیستن چه اتفاقی براشون افتاده؟ در حقیقت در تقسیم مولفه ی دوم هم باقیمانده ای وجود نخواهد داشت (برای این خطاها ..) .. یعنی چی؟ یعنی اینکه Er بر g بخشپذیره و این اتفاقیه که خیلی به ندرت میفته ..

    سوالی که مطرح میشه اینه که این مشکل به چه دلیل به وجود میاد؟ اونچیزی که مسلمه اینه که نمیشه Er رو پیش بینی کرد، پس نمیتونیم مشکل رو از اونجا بدونیم (به دلیل اینکه کاملا random هست ..) اما میتونیم g رو به گونه ای انتخاب کنیم که مقسوم علیه های خیلی کمی داشته باشه .. توی ریاضیات گسسته قضیه ای وجود داره که میتونه این ضریب رو برای یه چند جمله ای به گونه ای برقرار کنه که کمترین مقسوم علیه ها رو داشته باشه .. اصولش هم زیاد مشکل نیست (اگه خواستید روی بسط ین موضوع صحبت میکنیم ..) به هر حال میتونیم g رو محدود کنیم .. برای رفع این مشکل چند مولد رو به عنوان مولد های پیشنهادی ارائه کردن که کاربردهای بسیار زیادس در ارتباطات دیجیتال و پروتکل های ارتباطی داره .. معروفترین اونها رو در تصویر زیر مشاهده میکنید ..
    http://i42.tinypic.com/6teqdv.png


    در انتها موارد انعطافی که برای این کد در نظر گرفته میشه رو میتونیم به فرم زیر بررسی کنیم ..
    -- قابلیت آشکار سازی کلیه ی خظاهای تک بیتی
    -- قابلیت آشکار سازی کلیه ی خطاهای دوبیتی
    -- قابلیت آشکار سازی کلیه ی خطاهای فرد بیت
    -- قبلیت آشکار سازی کلیه ی خطاهای trailer که طول اونها کمتر یا در نهایت مساوی r باشه
    -- قابلیت آشکار سازی بیشتر خطاهای trailer با طول بیشتر از r

    اما در مورد طراحی یا پیاده سازی سخت افزاری این طرح اگه بخوایم صحبت کنیم باید در نظر داشته باشیم که این الگوریتم تشکیل شده از تقسیم های متوالی، و در فضای Boolean تقسیم معادلی داره از تفاضل (مثل ضرب که معادلی داره از مجموع ..) در نتیجه اگه بخوایم طرحمون رو پیاده سازی کنیم باید به این نکته توجه کنیم .. نکته ی بعدی که باید خیلی به اون توجه کنیم اینه که این کد بر اساس یک مولد ثابت طراحی میشه و به ازای بیت های دیتا CodeWord رو پدیت میکنه .. در نتیجه outline این طراحی این خواهد بود که اگه بخوایم این واحد رو طراحی کنیم، احتمالا یک بخش ثابت خواهیم داشت که عملیات تقسیم رو انجام میده و به صورت شیف سلسله مراتبی عمل میکنه و یک سیستم فیدبک باید روی اون بخش تعریف کینم که بتونه تقسیم هامون رو نسبت به ورودی پدیت کنه و خروجی رو به V تحویل بده .. این کلیت طراحی .. اما detail موضوع ..

    ** شما باید یک رویه ی شیفت رجیستری طراحی کنید به طوریکه بتونید در هر کلاک یک بیت دیتا رو وارد کنید و به عناصر بعدی انتقال بدید ..
    ** شما باید عمل تقسیم رو با تفاضل معادل کنید .. این کار رو به راحتی و با گیت XOR میتونید انجام بدید ..

    اما برای اینکه اشل کلی طراحی دستتون باشه یک مدار نمونه برای g=x^4+x^2+1 رو طراحی میکنیم ..
    http://i39.tinypic.com/vfje2s.png


    برای مطالعه ی بیشتر میتونید از فایلل زیر استفاده کنید .. امیدوارم مطالب براتون مفید بوده باشه .. موفق باشید ..


    فایل های پیوست شده
    دوستان! مدتی کمتر به سایت میام ..

    دیدگاه

      #3
      پاسخ : طراحی مدار Cyclic Reduancy Check

      سلام .................

      توضیحات مدار و نحوه ی طراحی رو در پست قبل بررسی کردیم .. در این پست هم یک نمونه طراحی برای همون طرح بالا رو ارائه کردیم .. امیدوارم بتونید از اون استفاده کنید ..موفق باشید ..
      فایل های پیوست شده
      دوستان! مدتی کمتر به سایت میام ..

      دیدگاه

        #4
        پاسخ : طراحی مدار Cyclic Reduancy Check

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

        http://rapidshare.com/files/181544502/CRC.docx.html

        دیدگاه

        قبلی template بعدی
        لطفا صبر کنید...
        X