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

الگوریتم برلکمپ-مسی (به انگلیسی: Berlekamp–Massey algorithm) الگوریتمی است که کوتاهترین ثبات تغییر بازخورد خطی (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\leq n\leq 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 ^m، مقدار (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 بیشتر از ۱ افزایش می‌یابد را کنترل می‌کند.

نمونه کد

الگوریتم از (Massey 1969) برای یک زمینه دلخواه:

  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 تعریف می‌شود).

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$ $n=0$ step 1 while $n<N$ $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\leq {\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.