الگوریتم چندجمله‌ای

الگوریتم چندجمله‌ای (به انگلیسی: polynomial algorithm)، در نظریه کدگذاری، کد چندجمله‌ای نوعی از کدهای خطی است که مجموعهٔ کد واژه‌های قابل قبول آن شامل آن دسته از چندجمله‌ای ها(معمولاً با طول ثابت)است که با یک چندجمله‌ای داده شده و ثابت (با طول ثابت به نام چندجمله‌ای مولد) قابل قسمت هستند.

تعریف

عبارت چند جمله(GF(x ای را در نظر بگیرید که عناصر آن را ضرایب آن می‌گیریم. برای ساخت کدهای چندجمله‌ای، یک رشته از n ضریب a_n-1,a_n-2,... ,a_۰ را با چندجمله‌ای زیر مشخص می‌کنیم:

a_n-1x+a_n-2x+... +a_۰

اعداد صحیح و ثابت را در نظر بگیرید و فرض کنید که (g(x چندجمله‌ای ثابت از درجه‌ای m (به نام چندجمله‌ای مولد) باشد. کد چندجمله‌ای ای که با (g(x تولید می‌شود، کدی خواهد بود که کد واژه‌های آن قطعاً چندجمله‌ای‌هایی با درجهٔ کمتر از n بوده و بر (g(x بخش پذیر هستند(بدون باقی‌مانده).

الگوریتم‌های چندجمله‌ای

در نظریه کدگذاری، کد چندجمله‌ای نوعی از کدهای خطی است که مجموعهٔ کد واژه‌های قابل قبول آن شامل آن دسته از چندجمله‌ای ها(معمولاً با طول ثابت)است که با یک چندجمله‌ای داده شده و ثابت (با طول ثابت به نام چندجمله‌ای مولد) قابل قسمت هستند.

تعریف

عبارت چند جمله(GF(x ای را در نظر بگیرید که عناصر آن را ضرایب آن می‌گیریم. برای ساخت کدهای چندجمله‌ای، یک رشته از n ضریب a_n-1,a_n-2,... ,a_۰ را با چندجمله‌ای زیر مشخص می‌کنیم:

a_n-1x+a_n-2x+... +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+۱

به‌طور مشابه می‌توان کد واژه‌ها را به صورت رشته‌هایی از ارقام دودویی نمایش داد:

۰۰۰۰۰٬۰۰۱۱۱٬۰۱۱۱۰٬۰۱۰۰۱ ۱۱۱۰۰٬۱۱۰۱۱٬۱۰۰۱۰٬۱۰۱۰۱

توجه کنید که هر کد چندجمله‌ای خود یک کد خطی نیز هست. پس هر ترکیب خطی از کد واژه‌های ان نیز کد واژه خواهدبود.

کد گذاری

در یک کد چندجمله‌ای روی(GF(q، با طول کد n و چندجمله‌ای مولد(q(x، دقیقاً $q^{n-m}$

کد واژه وجود خواهد داشت. البته طبق تعریف(p(x یک کد واژه‌است اگر و فقط اگر

p(x)=g(x)\cdot q(x)

، که در آن(q(x(خارج قسمت) از درجهٔ کمتر از

n-m

است. پس چون به تعداد

q^{n-m}

از این خارج قسمت‌ها وجود خواهد داشت، به همین تعداد نیز کد واژه‌های قابل قبول وجود دارد.

بازی از مولفان مانند(Lidl & Pilz, 1999) فقط تابدیلاتی $q(x)\mapsto g(x)\cdot q(x)$

را به عنوان نسبت دادن داده واژه‌ها به کد واژه‌ها بر رسی می‌کنند. به هر حال بدی این روش این است که داده واژه به عنوان قسمتی از کد واژه ظاهر نمی‌شود.

مثال

برای مثال بالا با $n=5$

,

m=2

و چندجمله‌ای مولد

g(x)=x^{2}+x+1

، انتصاب زیر را از داده واژه‌ها به کد واژه‌ها به دست می‌آوریم:

۰۰۰ ← ۰۰۰۰۰
۰۰۱ ← ۰۰۱۱۱
۰۱۰ ← ۰۱۰۰۱
۰۱۱ ← ۰۱۱۱۰
۱۰۰ ← ۱۰۰۱۰
۱۰۱ ← ۱۰۱۰۱
۱۱۰ ← ۱۱۰۱۱
۱۱۱ ← ۱۱۱۰۰

رمز گشایی

یک پیغام حاوی خطا می‌تواند با یک کار بسیار سر راست شناسایی شود، به طوری که تقسیم چندجمله‌ای بر چندجمله‌ای مولد باقی‌ماندهٔ غیر صفر می‌دهد.

بااین فرض که کد واژه فاقد خطاست، یک کد اصولی را می‌توان به سادگی با برداشتن m رقم(مجموع مقابله‌ای) آن، رمز گشایی کرد.

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

ویژگی‌های کدهای چندجمله‌ای

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

خانواده‌های ویژه‌ای از کدهای چندجمله‌ای

کدهای چرخشی:هر کد چرخشی خود نیز یک کد چندجمله‌ای به شمار می‌رود, کد افزونگی چرخشی مثال معروفی از این دسته کدهااست.

کدهای BCH:خانواده‌ای از کدهای چرخشی با مقدار فاصلهٔ همینگ زیاد و الگوریتم‌های جبری تصحیح خطای بسیار مفید.

تصحیح خطای رید-سالامون:زیر مجموعهٔ بسیار مهمی از کدهای BHCبا ساختارهای بسیار ویژه و مفید.

کاربرد

تشخیص خطا در انتقال.

تصحیح خطا در انتقال.

منابع

W.J. Gilbert and W.K. Nicholson: Modern Algebra with Applications, 2nd edition, Wiley, 2004.
R. Lidl and G. Pilz. Applied Abstract Algebra, 2nd edition. Wiley, 1999.