Berlekamp-Massey 알고리즘

Berlekamp-Massey 알고리즘은 주어진 이진 출력 시퀀스에 대해 최단 선형 피드백 시프트 레지스터(LFSR)를 찾는 알고리즘이다. 알고리즘은 또한 임의의 필드에서 선형적으로 반복되는 시퀀스의 최소 다항식도 찾을 것이다. 필드 요구사항은 Berlekamp-Massey 알고리즘이 0이 아닌 모든 원소에 승법 역이 필요함을 의미한다.^[1] 리드와 슬로운은 반지를 다룰 수 있는 연장선을 제공한다.^[2]

Elwyn Berlekamp는 Bose-Chaudhuri-Hocquenghem(BCH) 코드를 해독하는 알고리즘을 발명했다.^[3][4] 제임스 매시는 선형 피드백 시프트 레지스터에 대한 적용을 인식하고 알고리즘을 단순화했다.^[5][6] Massey는 알고리즘을 LFSR 합성 알고리즘(Berlekamp 반복 알고리즘)^[7]이라고 불렀지만, 현재는 Berlekamp-Massey 알고리즘으로 알려져 있다.

알고리즘 설명

Berlekamp-Massey 알고리즘은 일련의 선형 방정식을 해결하기 위한 리드-솔로몬 피터슨 디코더의 대안이다. 입력 스트림 S의 모든 위치 i에 대해 다음과 같이 요약할 수 있도록 다항식 ial(x)의 계수 λ을_j 찾는 것으로 요약할 수 있다.

${\displaystyle S_{i+\nu }+\lambda _{1}S_{i+\nu -1}+\lambda _{\nu -1}S_{i+1}+\lambda _{\nu }S_{i}=0.}$

아래 코드 예에서 C(x)는 λ(x)의 잠재적인 예다. L 오류에 대한 오류 로케이터 다항식 C(x)는 다음과 같이 정의된다.

${\displaystyle C(x)=C_{L}x^{L}+C_{L-1}x^{L-1}x^{L-1}+\cdots +C_{2}x^{2}+C_{1}x+1}$

또는 반전:

${\displaystyle C(x)=1+C_{1}x+C_{2}x^{2}x^{2}+\cdots +C_{L-1}x^{L-1}+C_{L}x^{L}.}$

알고리즘의 목표는 모든 신드롬을 일으키는 최소 L과 C(x)를 결정하는 것이다.

${\displaystyle S_{n}+C_{1}S_{n-1}+\cdots +C_{L}S_{n-L}}}$

0과 같음:

${\displaystyle S_{n}+C_{1}S_{n-1}+\cdots +C_{L}S_{n-L}=0,\qquad L\leq n\leq N-1.}$

알고리즘: C(x)는 1, L은 가정된 오류의 현재 수이며 0으로 초기화된다. N은 총 신드롬 수입니다. n은 주 반복기로 사용되며 0부터 N-1까지 신드롬을 지수화하는 데 사용된다.B(x)는 L이 업데이트되고 1. m이 업데이트되고 초기화된 이후 마지막 불일치 d(아래 설명)의 복사본이다.

알고리즘의 각 반복은 불일치 d를 계산한다. 반복 k에서 이것은 다음과 같을 것이다.

${\displaystyle d\gets S_{k}+C_{1}S_{k-1}+\cdots +C_{L}S_{k-L}.}$

d가 0인 경우 알고리즘은 C(x)와 L이 순간적으로 올바르고 m이 증가하며 계속된다고 가정한다.

d가 0이 아닌 경우, 알고리즘은 d의 재계산이 0이 되도록 C(x)를 조정한다.

${\displaystyle C(x)\gets C(x)-(d/b)x^{m}B(x)}$

x^m 용어는 B(x)를 이동하므로 b에 해당하는 신드롬을 따른다. 반복 j에서 L의 이전 업데이트가 발생한 경우 m = k - j 및 재계산된 불일치는 다음과 같을 것이다.

${\displaystyle d\gets S_{k}+C_{1}S_{k-1}+\cdots -(d/b)(S_{j}+B_{1)}S_{j-1}+\cdots .}$

이렇게 하면 재계산된 불일치가 다음과 같이 변경된다.

${\displaystyle d=d-(d/b)b=d-d=0.}$

알고리즘은 또한 필요에 따라 L(오류 수)을 증가시킬 필요가 있다. L이 실제 오차 수와 같을 경우 반복 프로세스 중에 불일치는 n이 2L보다 크거나 같기 전에 0이 된다. 그렇지 않으면 L이 업데이트되고 알고리즘이 B(x), b, 증가 L, 재설정 m = 1을 업데이트한다. L = (n + 1 - L) 공식은 불일치 계산에 사용되는 사용 가능한 신드롬의 수로 L을 제한하며, L이 1 이상 증가하는 경우도 처리한다.

코드 샘플

임의 필드에 대한 Massey(1969, 페이지 124)의 알고리즘:

  다항식의(밭을 갈다 K) s(x) = ... /* coeffs는 s_j; 출력 시퀀스는 N-1도 다항식) */   /* 연결 다항식 */   다항식의(밭을 갈다 K) C(x) = 1;  /* coeffs는 c_j */이다.   다항식의(밭을 갈다 K) B(x) = 1;   인트로 L = 0;   인트로 m = 1;   밭을 갈다 K b = 1;   인트로 n;    /* 단계 2. 및 6. */   을 위해 (n = 0; n < N; n++) {       /* 단계 2. 불일치 계산 */       밭을 갈다 K d = s_n + \시그마_{i=1}^L c_i * s_{n-i};        만일 (d == 0) {           /* 단계 3. 불일치는 0이며, 소멸은 계속된다 */           m = m + 1;       } 다른 만일 (2 * L <= n) {           /* 단계 5. */           /* C(x) */의 임시 복사본           다항식의(밭을 갈다 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;       } 다른 {           /* 단계 4. */           C(x) = C(x) - d b^{-1} x^m B(x);           m = m + 1;       }   }   돌아오다 L; 

이진 GF(2) BCH 코드의 경우 모든 홀수 단계에서 불일치 d가 0이 되므로 계산을 피하기 위해 검사를 추가할 수 있다.

/* ... */   을 위해 (n = 0; n < N; n++) {       /* 홀수 단계 번호, 불일치 == 0일 경우 */       만일 ((n&1) != 0) {           m = m + 1;           계속하다;       } /* ... */ 

참고 항목

• 리드-솔로몬 오차 보정
• Redes-Sloan 알고리즘, 정수보다 시퀀스 확장 모드 n
• 비선형 피드백 시프트 레지스터(NLFSR)

참조

외부 링크

• "Berlekamp-Massey algorithm", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• PlanetMath의 Berlekamp-Massey 알고리즘.
• Weisstein, Eric W. "Berlekamp–Massey Algorithm". MathWorld.
• Mathematica에서 GF(2) 구현
• (독일어로) 애플릿 Berlekamp-Massey 알고리즘
• 온라인 GF(2) Berlekamp-Massey 계산기