بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
پیاده سازی دیکد کننده Reed SolomOn با بکارگیری پردازنده میدان گالیوس
چکیده:
کد های Reed Solomon بدلیل قابلیت تصحیح بالایی که دارند در مخابرات دیجیتال از اهمیت زیادی برخوردار میباشند و به همین دلیل در افزاره های ذخیره سازی، مخابرات بی سیم، از راه دور و ماهواره ای، تلویزیون های دیجیتال و مودم های پر سرعت مانند XDSL از این روش در تصحیح خطا استفاده می شود. کد و دیکد کردن در میدان گالیوس انجام می گیرد و سخت افزارهای پیاده سازی شده نیز از پیچیدگی بالایی بر خوردار می باشند که همگی جهت بالا بردن سرعت و راندمان از موازی سازی استفاده می نمایند. در این مقاله با ارائه چند کد اسمبلی به زبان GFASM از پردازنده محاسباتی میدان گالیوس جهت انجام عملیات ریاضی بر روی چندجمله ایها و پیاده سازی روش دیکد نمودن استفاده گردیده است. لذا می توان با بکارگیری پردازنده محاسباتی میدان گالیوس در مدارهای ذکر شده و از پیش برنامه ریزی نمودن حافظه آن، عملیات را با پارامترهای مختلف بدون اینکه کوچکترین تغییری در ساختار پردازنده ایجاد گردد، براحتی پیاده سازی نمود.
کلمات کلیدی: کد کردن - دیکدا کردن - تصحیح خطا -پردازنده - میدان -گالیوس - اسمبلی - چندجمله ای
۱ - مقدمه:
کدینگ به روش Reed Solomon یا بطور اختصار RS یکی از بهترین و استاندارد ترین شیوه ها جهت تصحیح خطا هي باشد. بدین منظور در اکثر سیستمهای مخابرات دیجیتال (دریافت کننده های دیجیتالی) و رسانه های ذخیره سازی (هارد دیسک) روش RS بکار گرفته می شود.
در کد کننده یک بلاک از داده دیجیتالی گرفته می شود و در انتهای آن بیتهای افزون اضافه می گردد. در زمان انتقال یا ذخیره سازی به علتهای مختلف ممکن است خطا رخ دهد. در نتیجه دیکد کننده هر بلاک از داده را پردازش نموده و سعی در تصحیح و بازیابی داده اصلی دارد. قابل ذکر است تعداد و نوع خطاهای که می توانند تصحیح شوند به مشخصات کد RS بستگی دارد.
در پردازنده محاسباتی میدان گالیوس [۵] دستور العمل هایی در اختیار قرار داده شده است که به راحتی عملیات جمع، صرب و تقسیم را انجام می دهند و در حافظه فقط خواندنی خود نیز متدهایی جهت انجام عملیات محاسباتی بر روی چندجمله ای ها در دسترس قرار داده است. از آنجایی که روش Reed Solomon عملیات را در میدان گالیوس انجام می دهد، از این پردازنده در پیاده سازی این روش استفاده شده است که بر خلاف پیچیدگی خاصی که در پیاده سازی های مشابه مشاهده می شود ۳] و [۴]، کد و دیکد کردن با برنامه نویسی به زبان اسمبلی GFASM بصورت سطح بالا انجام می پذیرد و از سوی دیگر چون طراحی پردازنده برای اول های مختلف می باشد، این انعطاف به کد و دیکد کننده نیز به ارث میرسد.
خواص کد های Reed Solomon
کدهای RS زیرمجموعه ای از کدهای BCH بوده و با نماد (RS(n,k با تعداد نماد مشخص می گردند. این بدان معناست که کد کننده تعداد k نماد داده S بیتی گرفته و با افزودن نمادهای توازن آن را به یک قالب با تعداد n نماد تبدیل می نماید. بنابراین در هر قالب کد تعداد n-k نماد توازن وجود دارد. نکته قابل توجه در این است که دیکد کننده RS تنها قابلیت تصحیح نماد خطا را دارد که در آن می باشد.
شکل (۲) قالب یک کد RS را نشان می دهد. از آنجاییکه در این روش داده اصلی دست نخورده باقی می ماند و تنها نمادهای توازن به انتهای آن افزوده می شود این کدها از دسته کدهای سیستماتیک می باشند.
باید توجه داشت اگر نمادها S بیتی باشند، حداکثر طول قالب در یک کد RS برابر می باشد. حال اگر طول تعداد نمادهای ورودی کمتر از k باشد، به انتهای آن آنقدر صفر می افزاییم تا به تعداد k نماد برسیم. سپس عمل کدینگ را انجام داده و پس از آن نمادهای اصلی را به همراه نمادهای توازن (بدون صفرهای اضافه شده) ارسال می داریم.
۳- کد نمودن:
کد RS با نمادهایی از میدان را در نظر بگیرید و فرض کنید عنصر مقدماتی در میدان باشد. چندجمله ای تولید کننده یک کد RS بطول با قابلیت تصحیح خطا به صورت زیر می باشد:
اکنون اگر (a(x با نمایش زیر پیغامی است که باید کد گردد، تعداد 2t نماد توازن ضرایب چندجمله ای (b(x میباشند که در اصل باقیمانده حاصل از تقسیم چند جمله ای پیغام بصورت بر چند جمله ای تولید کننده یعنی (g(x می باشد.
از آنجایی که کد کننده RS به راحتی توسط یک LFSR قابل پیاده سازی می باشد [۴] و از پیچیدگی خاصی برخوردار نمیباشد، در این مقاله تنها نحوه پیاده سازی روش دیکد نمودن آورده شده است.
۴- دیکد نمودن:
روشهای دیکد کردن کدهای Reed Solomon می توانند به دو دسته دامنه زمان و دامنه فرکانس طبقه بندی شوند. تجربه نشان داده است که روشهای دامنه زمان هم در تاخیر و هم در مساحت اشغال شده پس از ساخت نتایج قابل قبول تری داشته است. اکثر شیوه های دامنه زمان منتشر شده یکی از الگوریتم های زیر را برای تخمین چندجمله ای موقعیت خطا استفاده نموده اند.
5 – روش Modified Euclid
مزیت اصلی استفاده از این روش حذف عمل تقسیم دو چندجمله ای می باشد. و از آنجایی که عملیات تنها بر روی چندجمله ایهاست و نیازی به محاسبات بازگشتی ماتریسی نمی باشد، از دیگر الگوریتمها نیز سریعتر عمل میکند.
این الگوریتم مسیر زیر را جهت دیکد نمودن و تصحیح خطا می پیماید:
- تولید چند جمله ای Syndrome
- مقدار دهی اولیه چند جمله ایها و انجام الگوریتم Modified Euclid
- بدست آوردن چند جمله ای تخمین گرو موقعیت یاب خطا
- جستجوی ریشه ها به کمک روش Chien و تصحیح خطا
البته قابل ذکر است قابلیت تصحیح کدهای RS در صورتیکه از پاک شدگی نیز استفاده شود به 2t نماد خواهد رسید. پاک شدگی زمانی اتفاق می افتد که موقعیت نماد خراب مشخص شده باشد. اطلاعات پاک شدگی معمولاً در سیستمهای مخابراتی دیجیتال توسط دمودلاتور تغذیه می شوند. در این مقاله پاک شدگی در نظر نگرفته نشده است که البته با تغییر ناچیزی می توان کد را برای حالت وجود پاک شدگی نیز استفاده نمود. اکنون بطور مرحله به مرحله روش پیاده سازی الگوریتم به زبان GFASM شرح داده می شود.
6 – پیاده سازی روش Modified Euclid
6- 1 – تولید Syndrome ها
اگر پیغام دریافت شده بصورت زیر نمایش داده شود:
چندجمله ای Syndrome بصورت زیر بدست می آید:
پیاده سازی:
از آنجاییکه در پیاده سازی این الگوریتم از متدهای آماده پردازنده استفاده شده است، در بخش ضمیمه جهت یادآوری نام و شرح عملکرد آنها آورده شده است. در این متدها فرض بر این است که چندجمله ای ها با ساختار خاصی ذخیره شوند، بدین صورت که در خانه اول درجه چند جمله ای و در خانه های بعدی ضریب درجات مختلف از بزرگترین درجه تا عدد ثابت ذخیره گردد و نیز باید در نظر داشت که تمام متدها ضرایب را به فرم نمایی در نظر می گیرند.
در نتیجه برای محاسبه (S(X با قرار دادن آدرس شروع (R(X در اشاره گر FSR1 و نیز مقداردهی مناسب خانه ای که FSR2 به آن اشاره می کند و آدرس محل ذخیره ضرایب (S(X در آن قرار دارد، تولید این چند جمله ای به کمک متد (P(a^k انجام میگیرد.
