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

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

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

شرح الگوریتم

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

$S_{i+\nu }+{\mathrm{\Lambda }}_1{S}_{i+\nu -1}+\cdots +{\mathrm{\Lambda }}_{\nu -1}{S}_{i+1}+{\mathrm{\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,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\leftarrow S_k+C_1{S}_{k-1}+\cdots +C_L{S}_{k-L}.$

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

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

$C(x)\leftarrow C(x)-(d/b)x^{m}B(x).$

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

$d\leftarrow 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 بیشتر از ۱ افزایش می‌یابد را کنترل می‌کند.

نمونه کد

الگوریتم از الگو:Harvard citation text برای یک زمینه دلخواه:

  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 ₂ (همچنین GF (2)) می‌باشد. عناصر زمینه "۰" و "۱" هستند. عملیات میدانی "+" و "-" معادل عملیات "XOR" هستند. عملگر ضرب '*' عملیات منطقی AND می‌شود. عملگر تقسیم به عمل هویت کاهش می‌یابد (یعنی تقسیم میدان فقط برای تقسیم بر ۱ و x / 1 = x تعریف می‌شود).

1. Let $s_0,s_1,s_2\cdots s_{N-1}$ be the bits of the stream.
2. Initialise two arrays $b$ and $c$ each of length $N$ to be zeroes, except $b_0\leftarrow 1,c_0\leftarrow 1$
3. assign $L\leftarrow 0,m\leftarrow -1$.
4. For $n=0$ step 1 while $n<N$:
   • Let discrepancy $d$ be $s_n\oplus c_1{s}_{n-1}\oplus c_2{s}_{n-2}\oplus \cdots \oplus c_L{s}_{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_L{s}_a\oplus c_{L-1}{s}_{a+1}\oplus c_{L-2}{s}_{a+2}\oplus \cdots =0$

برای همه $a$ .

جستارهای وابسته

• تصحیح خطای رید-سالامون

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

• الگو:Springer
• Berlekamp–Massey algorithm at PlanetMath.
• الگو:MathWorld
• GF(2) implementation in Mathematica
• الگو:In lang Applet Berlekamp–Massey algorithm
• Online GF(2) Berlekamp-Massey calculator