버거 코드

통신에서 버거 코드는 단방향 오류 탐지 코드로, 그것의 발명가 J. M. 버거의 이름을 따서 명명되었다. 버거 코드는 모든 단방향 오류를 감지할 수 있다. 단방향 오류는 비대칭 채널과 같이 0을 0으로 바꾸거나 0을 0으로 바꾸는 오류다. 버거 코드의 체크 비트는 정보 워드의 모든 0을 세고, 그 숫자를 자연 이진수로 표현함으로써 계산된다. If the information word consists of ${\displaystyle n}$ bits, then the Berger code needs ${\displaystyle k=\lceil \log _{2}(n+1)\rceil }$ "check bits", giving a Berger code of length k+n. (In other words, the ${\displaystyle k}$ check bits are enough to check up to ${\display$$스타일 n=2^{k}-1$} 정보$$ 비트). 버거 코드는 동일한 코드 워드에서 0 대 1의 오류가 발생하지 않는 한 1 대 0 비트 플립 오류를 얼마든지 감지할 수 있다. 마찬가지로 버거 코드는 동일한 코드 워드에서 1 대 0 비트 플립 오류가 발생하지 않는 한 0 대 1 비트 플립 오류를 얼마든지 감지할 수 있다. 버거 코드는 오류를 수정할 수 없다.

모든 단방향 오류 감지 코드와 마찬가지로 버거 코드는 지연 과민성 회로에서도 사용할 수 있다.

단방향 오류 감지

위에서 설명한 것처럼 버거 코드는 단방향 오류를 임의로 감지한다. 주어진 코드 워드의 경우, 값이 1인 일부(또는 모든) 비트가 값 0으로 변경된 오류만 발생한 경우, 이 변환은 버거 코드 구현에 의해 감지된다. 그 이유를 이해하려면 다음과 같은 세 가지 경우를 고려하십시오.

1. 코드 워드의 정보 부분에서 일부 1s 비트가 0s로 변경되었다.
2. 코드 워드의 체크(또는 중복) 부분에 있는 일부 1s 비트가 0s로 변경되었다.
3. 정보와 체크 부분의 일부 1s 비트가 0s로 변경되었다.

사례 1의 경우 오류의 정의에 따라 정보 섹션의 0 값 비트 수가 증가한다. 따라서 우리의 버거 체크 코드는 데이터에 대한 실제 0비트 카운트보다 낮아져 체크가 실패할 것이다.

사례 2의 경우 정보 섹션의 0 값 비트 수는 그대로 유지되었지만, 체크 데이터의 값은 변경되었다. 일부 1이 0으로 변한 것을 알고 있지만 0이 1로 변한 것은 없기 때문에(이 경우 오류 모델을 정의한 방법), 체크 데이터의 인코딩된 이진수 값이 내려간다(예: 이진수 1011부터 1010까지, 또는 1001 또는 0011까지). 정보 데이터는 그대로 유지되었기 때문에 이전과 동일한 수의 0을 가지며, 이는 더 이상 변이된 체크 값과 일치하지 않게 된다.

정보와 체크 섹션 모두에서 비트가 변경된 사례 3의 경우, 사례 1에 대해 설명한 정보 섹션의 0의 수가 증가하고 사례 2에 대해 설명한 것처럼 체크 부분에 저장된 이진수 값이 감소했다는 점에 주목한다. 따라서 두 사람이 서로 다른 유효한 암호어가 될 정도로 돌연변이를 일으킬 가능성은 없다.

일부 0 값 비트가 1로 변경되는 오류만 발생하는 경우 유사한 분석을 수행할 수 있으며 완벽하게 유효하다. 따라서 특정 코드 워드에서 발생하는 모든 오류가 동일한 방향으로 발생한다면 이러한 오류는 감지될 것이다. 다음 암호 단어가 전송되는 경우(예를 들어), 오류는 반대 방향으로 갈 수 있으며, 모두 서로 같은 방향으로 가는 한 여전히 탐지될 것이다.

단방향 오류는 특정 상황에서 흔히 발생한다. 예를 들어 플래시 메모리에서는 비트를 1로 재설정할 수 있는 것보다 더 쉽게 0으로 프로그래밍할 수 있다.

참조

• J. M. Berger (March 1961). "A note on an error detection code for asymmetric channels". Information and Control. 4 (1): 68–73. doi:10.1016/S0019-9958(61)80037-5.
• Subhash Mitra와 Edward J. McCluskey, "어떤 동시 오류 감지 체계를 선택할 것인가?", Stanford University, 2000년 Stanford University의 신뢰할 수 있는 컴퓨팅 센터. CiteSeer^x: 10.1.1.9.2021
• Tom Verhoeff (March 1988). "Delay-insensitive codes — an overview] by" (PDF). Distributed Computing. 3 (1): 1–8. doi:10.1007/BF01788562.