الگوریتم برلیکمپ-مسی

الگوریتم برلکمپ-مسی  الگوریتمی است که کوتاهترین ثبات تغییر بازخورد خطی (LFSR) را برای یک دنباله دودویی داده شده پیدا می‌کند. این الگوریتم همچنین کوچکترین چند جمله ای یک دنباله ی خطی بازگشتی در یک میدان دلخواه را پیدا می‌کند. پیش‌نیاز میدان یعنی الگوریتم برلکمپ‌مسی نیازمند به این است که همه‌ی عنصرهای ناصفر وارون ضربی داشته باشند. ریدز و اسلون تعمیمی را برای حلقه ارائه می‌دهند.

الوین برلیکمپ یک الگوریتم برای کدگشایی کد Bose–Chaudhuri–Hocquenghem (BCH)  پدید آورد. جیمز مسی کاربرد آن در ثبات تغییر بازخورد خطی را یافت و الگوریتم را ساده‌سازی کرد. مسی این الگوریتم را الگوریتم سنتر 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 < 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 <= 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 تعریف می‌شود).
 Let  be the bits of the stream.
 Initialise two arrays  and  each of length  to be zeroes, except 
 assign .
 For  step 1 while :
 Let discrepancy  be .
 if , then  is already a polynomial which annihilates the portion of the stream from  to .
 else:
 Let  be a copy of .
 Set  up to  (where  is the Exclusive or operator).
 If , set , set , and let ; otherwise leave ,  and  alone.

در پایان الگوریتم ،  طول حداقل LFSR برای جریان است، و ما داریم:

برای همه  .

 جستارهای وابسته 
 تصحیح خطای رید-سالامون

 منابع 

 پیوند به بیرون 

 Berlekamp–Massey algorithm at PlanetMath.

 GF(2) implementation in Mathematica
  Applet Berlekamp–Massey algorithm
 Online GF(2) Berlekamp-Massey calculator
رده:آشکارسازی و اصلاح خطا
رده:صفحات با ترجمه بازبینی‌نشده