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

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

الوین برلیکمپ یک الگوریتم برای رمزگشایی Bose–Chaudhuri–Hocquenghem (BCH) codes ابداع کرد.

جیمز مسی کاربرد آن در ثبات تغییر بازخورد خطی را یافت و الگوریتم را ساده‌سازی کرد. مسی این الگوریتم را الگوریتم سنتر LFSR نام گذاشت اما اکنون به عنوان الگوریتم برلیکمپ-مسی شناخته می‌شود

شرح الگوریتم 
الگوریتم Berlekamp-Massey جایگزینی برای رمزگشایی رید- سلیمان پترسون برای حل مجموعه معادلات خطی است. می‌توان آن را به عنوان یافتن ضرایب Λ 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;

الگوریتم برای زمینه باینری 
الگوریتم Berlekamp- Massey زیر مخصوص میدان محدود دودویی 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
آشکارسازی و اصلاح خطا
صفحات با ترجمه بازبینی‌نشده