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

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

الوین برلیکمپ یک الگوریتم برای کدگشایی کد Bose–Chaudhuri–Hocquenghem (BCH)  پدید آورد. جیمز مسی کاربرد آن در ثبات تغییر بازخورد خطی را یافت و الگوریتم را ساده‌سازی کرد. مسی این الگوریتم را الگوریتم سنتر LFSR نام گذاشت اما اکنون به عنوان الگوریتم برلکمپ‌مسی شناخته می‌شود.

## شرح الگوریتم
الگوریتم برلکمپ‌مسی جایگزینی برای رمزگشایی رید- سلیمان پترسون برای حل مجموعه معادلات خطی است. می‌توان آن را به عنوان یافتن ضرایب Λ *j* از چند جمله ای Λ (*x*) خلاصه کرد به طوری که برای همه موقعیت‌های *i* در یک جریان ورودی *S*:

:  S_{i + \nu} + \Lambda_1 S_{i+\nu-1} + \cdots + \Lambda_{\nu-1} S_{i+1} + \Lambda_\nu S_i = 0. 

در مثالهای کد زیر(*C* *(x* یک نمونه از(*Λ* (*x* است. خطا یاب چند جمله ای (*C* *(x* برای خطاهای *L* تعریف می‌شود:

:  C(x) = C_L x^L + C_{L-1} x^{L-1} + \cdots + C_2 x^2 + C_1 x + 1 

یا معکوس شده:

:  C(x) = 1 + C_1 x + C_2 x^2 + \cdots + C_{L-1} x^{L-1} + C_L x^L. 

هدف این الگوریتم تعیین حداقل درجه *L* و(*C* *(x* است که منجر به این سندرم‌ها می‌شود

:  S_n + C_1 S_{n-1} + \cdots + C_L S_{n-L}

برابر با ۰:

:  S_n + C_1 S_{n-1} + \cdots + C_L S_{n-L} = 0,\qquad L\le n\le N-1.

الگوریتم: (*C* *(x* در ابتدا ۱ می‌باشد، *L* تعداد خطاهای فرض شده‌است و در ابتدا صفر است. *N* تعداد کل سندرم‌هاست. *از n* به عنوان شمارندهٔ اصلی و برای شماره گذاری سندرمها از ۰ تا *N* -1 استفاده می‌شود. (*B* *(x* یک نسخه از آخرین(*C* *(x* است زیرا *L* به روز شده و برابر ۱ قرار گرفته‌است. *b* نسخه ای از آخرین اختلاف *d است* (در زیر توضیح داده شده‌است) از آنجا که *L* به روز شده و برابر ۱ قرار گرفته‌است. m تعداد شمارش شده از وقتی است که (*B* *(x و، L , B به روز شده و برابر ۱ شده‌اند.*

در هر بار اجرای الگوریتم، اختلاف d را محاسبه می‌شود*.* در اجرای *kام*:

:  d \gets S_k + C_1 S_{k-1} + \cdots + C_L S_{k-L}.

اگر *d* صفر باشد، الگوریتم فرض می‌کند که (*C* *(x* و *L* برای لحظه صحیح اند، *m* افزایش یافته و ادامه می‌یابد.

اگر *d* صفر نباشد، الگوریتم (*C* *(x* را تنظیم می‌کند تا در محاسبه مجدد *d* صفر شود:

: C(x) \gets C(x) - (d / b) x^m B(x).

*x <sup>m</sup>*، مقدار (B*(x* را شیفت می‌دهد تا از سندرم‌های مربوط به *b* پیروی کند. اگر به روزرسانی قبلی *L* در تکرار *j* رخ داده باشد، *m* = *k* - *j* و یک اختلاف d مجدد محاسبه می‌شود:

:  d \gets S_k + C_1 S_{k-1} + \cdots - (d/b) (S_j + B_1 S_{j-1} + \cdots ).

این اختلاف مجدد محاسبه شده را به:

:  d = d - (d/b)b = d - d = 0.

تغییر می‌دهد.

الگوریتم همچنین در صورت لزوم نیاز به افزایش *L* (تعداد خطاها) دارد. اگر *L* برابر با تعداد واقعی خطاها باشد، در طی فرایند تکرار، اختلافات قبل از اینکه *n* از ۲ بزرگتر یا برابر با ۲ شود، *L* صفر می‌شوند. در غیر این صورت *L* به روز شده و الگوریتم *B* (*x*)، *b را به روزرسانی کرده و* *L را* افزایش می‌دهد و *m* = ۱ را مجدداً تنظیم می‌کند. فرمول *L* = (*n* + 1 − *L*) , L *را* به تعدادی از سندرمهای موجود برای محاسبه اختلافات محدود می‌کند، و همچنین مواردی را که *L* بیشتر از ۱ افزایش می‌یابد را کنترل می‌کند.

## نمونه کد
الگوریتم از  برای یک زمینه دلخواه: 
```c
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 s_0, s_1, s_2 \cdots s_{N-1} be the bits of the stream.
# Initialise two arrays b and c each of length N to be zeroes, except b_0 \leftarrow 1, c_0 \leftarrow 1
# assign L \leftarrow 0, m \leftarrow -1.
# **For** n = 0 **step** 1 **while** n :
#* Let discrepancy d be s_n \oplus c_1s_{n-1} \oplus c_2s_{n-2} \oplus \cdots \oplus c_Ls_{n-L}.
#* **if** d = 0, **then** c is already a polynomial which annihilates the portion of the stream from n-L to n.
#* **else**:
#** Let t be a copy of c.
#** Set c_{n-m} \leftarrow c_{n-m} \oplus b_0, c_{n-m+1} \leftarrow c_{n-m+1} \oplus b_1, \dots  up to c_{N-1} \leftarrow c_{N-1} \oplus b_{N-n+m-1} (where \oplus is the Exclusive or operator).
#** If L \le \frac{n}{2}, set L \leftarrow n+1-L, set m \leftarrow n, and let b \leftarrow t; otherwise leave L, m and b alone.

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

c_Ls_a \oplus c_{L-1}s_{a+1} \oplus c_{L-2}s_{a+2} \oplus \cdots = 0

برای همه a .

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

## منابع

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