موضوع مقاله: الگوریتم چندجمله‌ای | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم چندجمله‌ای | مقدمه: الگوریتم چندجمله‌ای ، در نظریه کدگذاری، کد چندجمله‌ای نوعی از کدهای خطی است که مجموعهٔ کد واژه‌های قابل قبول آن شامل آن دسته از چندجمله‌ای ها(معمولاً با طول ثابت)است که با یک چندجمله‌ای داده شده و ثابت (با طول ثابت به نام چندجمله‌ای مولد) قابل قسمت هستند. | ## بخش 1: الگوریتم چندجمله‌ای | +a۰ اعداد صحیح و ثابت را در نظر بگیرید و فرض کنید که (g(x چندجمله‌ای ثابت از درجه‌ای m (به نام چندجمله‌ای مولد) باشد. کد چندجمله‌ای ای که با (g(x تولید می‌شود، کدی خواهد بود که کد واژه‌های آن قطعاً چندجمله‌ای‌هایی با درجهٔ کمتر از n بوده و بر (g(x بخش پذیر هستند(بدون باقی‌مانده). الگوریتم‌های چندجمله‌ای در نظریه کدگذاری، کد چندجمله‌ای نوعی از کدهای خطی است که مجموعهٔ کد واژه‌های قابل قبول آن شامل آن دسته از چندجمله‌ای ها(معمولاً با طول ثابت)است که با یک چندجمله‌ای داده شده و ثابت (با طول ثابت به نام چندجمله‌ای مولد) قابل قسمت هستند. +a۰ اعداد صحیح و ثابت را در نظر بگیرید، و فرض کنید که(g(x چندجمله‌ای ثابت از درجه‌ای m (به نام چندجمله‌ای مولد) باشد. کد چندجمله‌ای ای که با (g(x تولید می‌شود، کدی خواهد بود که کد واژه‌های آن قطعاً چندجمله‌ای‌های با درجهٔ کمتر از n بوده و بر (g(x بخش پذیر هستند(بدون باقی‌مانده). مثال کد چندجمله‌ای روی {GF(2) = {0,1، باm=2,n=5 و چندجمله‌ای مولد g(x) = x2 + x + 1 را در نظر بگیرید.in کد شامل کد واژه‌های زیر است: x۲+x+1, x۳+x۲+x, x۳+۱ ,۰, x۴+x۳+x۲ , x۴+x۳+x+1 , ,x۴+x,x۴+x۲+۱ به‌طور مشابه می‌توان کد واژه‌ها را به صورت رشته‌هایی از ارقام دودویی نمایش داد: ۰۰۰۰۰٬۰۰۱۱۱٬۰۱۱۱۰٬۰۱۰۰۱ ۱۱۱۰۰٬۱۱۰۱۱٬۱۰۰۱۰٬۱۰۱۰۱ توجه کنید که هر کد چندجمله‌ای خود یک کد خطی نیز هست. | ## بخش 2: الگوریتم چندجمله‌ای | کد گذاری در یک کد چندجمله‌ای روی(GF(q، با طول کد n و چندجمله‌ای مولد(q(x، دقیقاً کد واژه وجود خواهد داشت. البته طبق تعریف(p(x یک کد واژه‌است اگر و فقط اگر ، که در آن(q(x(خارج قسمت) از درجهٔ کمتر از است. پس چون به تعداد از این خارج قسمت‌ها وجود خواهد داشت، به همین تعداد نیز کد واژه‌های قابل قبول وجود دارد. بازی از مولفان مانند(Lidl & Pilz, 1999) فقط تابدیلاتی را به عنوان نسبت دادن داده واژه‌ها به کد واژه‌ها بر رسی می‌کنند. به هر حال بدی این روش این است که داده واژه به عنوان قسمتی از کد واژه ظاهر نمی‌شود. مثال برای مثال بالا با, و چندجمله‌ای مولد، انتصاب زیر را از داده واژه‌ها به کد واژه‌ها به دست می‌آوریم: ۰۰۰ ← ۰۰۰۰۰ ۰۰۱ ← ۰۰۱۱۱ ۰۱۰ ← ۰۱۰۰۱ ۰۱۱ ← ۰۱۱۱۰ ۱۰۰ ← ۱۰۰۱۰ ۱۰۱ ← ۱۰۱۰۱ ۱۱۰ ← ۱۱۰۱۱ ۱۱۱ ← ۱۱۱۰۰ رمز گشایی یک پیغام حاوی خطا می‌تواند با یک کار بسیار سر راست شناسایی شود، به طوری که تقسیم چندجمله‌ای بر چندجمله‌ای مولد باقی‌ماندهٔ غیر صفر می‌دهد. | ## بخش 3: الگوریتم چندجمله‌ای | بااین فرض که کد واژه فاقد خطاست، یک کد اصولی را می‌توان به سادگی با برداشتن m رقم(مجموع مقابله‌ای) آن، رمز گشایی کرد. برای کدهای چندجمله‌ای خاص، مثل کدهای BCH، الگوریتم‌های مفیدی برای رمز گشایی وجود دارد. ویژگی‌های کدهای چندجمله‌ای مثل همهٔ کدهای دیجیتال، توانایی کدهای چندجمله‌ای در تشخیص و تصحیح خطا با حداقل فاصلهٔ همینگ آن کدتعیین می‌شود. از آنجایی که کدهای چندجمله‌ای نوعی کد خطی هستند، حد اقل فاصلهٔ همینگ آن‌ها برابر است باحداقل وزن(weight) کد واژه‌های غیر صفر آن. خانواده‌های ویژه‌ای از کدهای چندجمله‌ای کدهای چرخشی:هر کد چرخشی خود نیز یک کد چندجمله‌ای به شمار می‌رود, کد افزونگی چرخشی مثال معروفی از این دسته کدهااست. کدهای BCH:خانواده‌ای از کدهای چرخشی با مقدار فاصلهٔ همینگ زیاد و الگوریتم‌های جبری تصحیح خطای بسیار مفید. | ## جمع‌بندی | تصحیح خطای رید-سالامون:زیر مجموعهٔ بسیار مهمی از کدهای BHCبا ساختارهای بسیار ویژه و مفید.