الگوریتم برلیکمپ-مسی چیست؟ توضیح بده.
الگوریتم برلکمپ-مسی الگوریتمی است که کوتاهترین ثبات تغییر بازخورد خطی (LFSR) را برای یک دنباله دودویی داده شده پیدا می‌کند. این الگوریتم همچنین کوچکترین چند جمله ای یک دنباله ی خطی بازگشتی در یک میدان دلخواه را پیدا می‌کند. پیش‌نیاز میدان یعنی الگوریتم برلکمپ‌مسی نیازمند به این است که همه‌ی عنصرهای ناصفر وارون ضربی داشته باشند. ریدز و اسلون تعمیمی را برای حلقه ارائه می‌دهند.الوین برلیکمپ یک الگوریتم برای کدگشایی پدید آورد. جیمز مسی کاربرد آن در ثبات تغییر بازخورد خطی را یافت و الگوریتم را ساده‌سازی کرد. مسی این الگوریتم را الگوریتم سنتر LFSR نام گذاشت اما اکنون به عنوان الگوریتم برلکمپ‌مسی شناخته می‌شود.شرح الگوریتم.الگوریتم برلکمپ‌مسی جایگزینی برای رمزگشایی رید- سلیمان پترسون برای حل مجموعه معادلات خطی است. می‌توان آن را به عنوان یافتن ضرایب Λ "j" از چند جمله ای Λ ("x") خلاصه کرد به طوری که برای همه موقعیت‌های "i" در یک جریان ورودی "S":در مثالهای کد زیر("C" "(x" یک نمونه از("Λ" ("x" است. خطا یاب چند جمله ای ("C" "(x" برای خطاهای "L" تعریف می‌شود:یا معکوس شده:هدف این الگوریتم تعیین حداقل درجه "L" و("C" "(x" است که منجر به این سندرم‌ها می‌شودبرابر با ۰:الگوریتم: ("C" "(x" در ابتدا ۱ می‌باشد، "L" تعداد خطاهای فرض شده‌است و در ابتدا صفر است. "N" تعداد کل سندرم‌هاست. "از n" به عنوان شمارندهٔ اصلی و برای شماره گذاری سندرمها از ۰ تا "N" -1 استفاده می‌شود. ("B" "(x" یک نسخه از آخرین("C" "(x" است زیرا "L" به روز شده و برابر ۱ قرار گرفته‌است. "b" نسخه ای از آخرین اختلاف "d است" (در زیر توضیح داده شده‌است) از آنجا که "L" به روز شده و برابر ۱ قرار گرفته‌است. m تعداد شمارش شده از وقتی است که ("B" "(x و، L , B به روز شده و برابر ۱ شده‌اند."در هر بار اجرای الگوریتم، اختلاف d را محاسبه می‌شود"." در اجرای "kام":اگر "d" صفر باشد، الگوریتم فرض می‌کند که ("C" "(x" و "L" برای لحظه صحیح اند، "m" افزایش یافته و ادامه می‌یابد.اگر "d" صفر نباشد، الگوریتم ("C" "(x" را تنظیم می‌کند تا در محاسبه مجدد "d" صفر شود:"x m"، مقدار (B"(x" را شیفت می‌دهد تا از سندرم‌های مربوط به "b" پیروی کند. اگر به روزرسانی قبلی "L" در تکرار "j" رخ داده باشد، "m" = "k" - "j" و یک اختلاف d مجدد محاسبه می‌شود:این اختلاف مجدد محاسبه شده را به:تغییر می‌دهد.الگوریتم همچنین در صورت لزوم نیاز به افزایش "L" (تعداد خطاها) دارد. اگر "L" برابر با تعداد واقعی خطاها باشد، در طی فرایند تکرار، اختلافات قبل از اینکه "n" از ۲ بزرگتر یا برابر با ۲ شود، "L" صفر می‌شوند. در غیر این صورت "L" به روز شده و الگوریتم "B" ("x")، "b را به روزرسانی کرده و" "L را" افزایش می‌دهد و "m" = ۱ را مجدداً تنظیم می‌کند. فرمول "L" = ("n" + 1 − "L") , L "را" به تعدادی از سندرمهای موجود برای محاسبه اختلافات محدود می‌کند، و همچنین مواردی را که "L" بیشتر از ۱ افزایش می‌یابد را کنترل می‌کند.نمونه کد.الگوریتم از برای یک زمینه دلخواه: polynomial(field K) s(x) = ... /* coeffs are s_j; output sequence as N-1 degree polynomial) */ /* connection polynomial */ polynomial(field K) C(x) = 1; /* coeffs are c_j */ polynomial(field K) B(x) = 1; int L = 0; int m = 1; field K b = 1; int n; /* steps 2. and 6. */ for (n = 0; n &lt; N; n++) { /* step 2. calculate discrepancy */ field K d = s_n + \Sigma_{i=1}^L c_i * s_{n-i}; if (d == 0) { /* step 3. discrepancy is zero; annihilation continues */ m = m + 1; } else if (2 * L &lt;= n) { /* step 5. */ /* temporary copy of C(x) */ polynomial(field K) T(x) = C(x); C(x) = C(x) - d b^{-1} x^m B(x); L = n + 1 - L; B(x) = T(x); b = d; m = 1; } else { /* step 4. */ C(x) = C(x) - d b^{-1} x^m B(x); m = m + 1; return L;الگوریتم برای زمینه باینری.الگوریتم برلکمپ‌مسی زیر مخصوص میدان محدود دودویی F 2 (همچنین GF (2)) می‌باشد. عناصر زمینه "۰" و "۱" هستند. عملیات میدانی "+" و "-" معادل عملیات "XOR" هستند. عملگر ضرب '*' عملیات منطقی AND می‌شود. عملگر تقسیم به عمل هویت کاهش می‌یابد (یعنی تقسیم میدان فقط برای تقسیم بر ۱ و x / 1 = x تعریف می‌شود).در پایان الگوریتم ، formula_33 طول حداقل LFSR برای جریان است، و ما داریم:formula_37برای همه formula_38 .