해밍 Code오류 탐지 및 수정 (예시 포함)

오류란 무엇입니까?

Transmit전송 중인 데이터는 손상될 수 있습니다. 외부 잡음이나 물리적 오류 등의 영향을 받을 가능성이 높습니다. 이러한 경우 입력 데이터와 출력 데이터가 일치하지 않게 됩니다. 이러한 불일치를 "오류"라고 합니다.

데이터 오류는 중요하거나 보안이 유지되어야 할 데이터의 손실을 초래할 수 있습니다. 디지털 시스템에서 데이터 전송의 대부분은 "비트 전송" 형태로 이루어지며, 단 하나의 비트라도 작은 변화가 생기면 전체 시스템의 성능에 영향을 미칠 수 있습니다. 데이터 시퀀스에서 1이 0으로 바뀌거나 0이 1로 바뀌는 경우를 "비트 오류"라고 합니다.

오류 유형

데이터 전송 시 발생하는 비트 오류에는 크게 세 가지 유형이 있습니다. transmit송신자에서 수신자로 전달됩니다. 아래 다이어그램은 각 유형이 데이터 시퀀스에 미치는 영향을 보여줍니다.

• 단일 비트 오류
• 다중 비트 오류
• 버스트 오류

단일 비트 오류

전체 데이터 시퀀스에서 단 하나의 비트만 변경되는 것을 "단일 비트 오류"라고 합니다. 단일 비트 오류는 흔하게 발생하는 것은 아닙니다. 주로 병렬 통신 시스템에서 발생하는데, 이는 데이터가 비트 단위로 별도의 회선을 통해 전송되기 때문에 한 회선에 노이즈가 발생하고 다른 회선은 깨끗한 상태를 유지할 가능성이 높기 때문입니다.

다중 비트 오류

데이터 시퀀스의 두 개 이상의 비트가 변경될 때 transmit송신측과 수신측 간에 발생하는 오류를 "다중 비트 오류"라고 합니다.

이러한 유형의 오류는 직렬 및 병렬 데이터 통신 네트워크 모두에서 발생합니다.

버스트 오류

데이터 시퀀스에서 연속된 비트 집합이 변경되는 것을 "버스트 오류"라고 합니다. 버스트 오류의 길이는 처음 변경된 비트부터 마지막으로 변경된 비트까지로 측정됩니다.

오류 탐지 및 오류 수정이란 무엇입니까?

디지털 통신 시스템에서는 데이터가 한 장치에서 다른 장치로 전송되는 과정에서 오류가 발생할 수 있습니다. 이러한 오류를 감지하고 수정하지 않으면 데이터가 손실됩니다. 효과적인 통신을 위해서는 높은 정확도로 데이터를 전송해야 하며, 이는 오류를 식별한 후 수정함으로써 달성할 수 있습니다.

오류 감지 데이터에 존재하는 오류를 찾는 방법입니다. transmit테드 출신 transmit수신기로 데이터 통신 시스템.

중복 코드는 데이터가 잘못되었을 때 추가 비트를 데이터에 더하여 이러한 오류를 찾는 데 사용됩니다. transmit출처에서 가져온 내용입니다. 이러한 추가 비트를 "오류 검출 코드"라고 합니다. 가장 일반적인 세 ​​가지 오류 검출 코드 유형은 다음과 같습니다.

• 패리티 검사
• CRC (Cyclic Redundancy Check)
• 종방향 중복 검사(LRC)

패리티 검사

• 패리티 검사라고도 합니다.
• 이는 비용 효율적인 오류 감지 메커니즘을 제공합니다.
• 이 기법에서는 모든 데이터 단위에 추가되는 중복 비트를 패리티 비트라고 합니다. 이 비트는 해당 단위 내의 1의 총 개수가 짝수(짝수 패리티) 또는 홀수(홀수 패리티)가 되도록 설정됩니다.

종방향 중복 검사

이 오류 검출 기법에서는 비트 블록이 표 형태로 구성됩니다. LRC 방식은 각 열에 대해 패리티 비트를 계산하고, 이 패리티 비트 세트를 원본 데이터와 함께 전송합니다. 수신자는 이 패리티 비트 블록을 통해 중복 여부를 확인하고 오류를 감지할 수 있습니다.

순환 중복 검사

순환 중복 검사(CRC)는 데이터 단위 끝에 중복 비트 시퀀스를 추가하여 결과 데이터 단위가 미리 정해진 두 번째 이진수로 정확히 나누어 떨어지도록 합니다.

수신 측에서는 수신된 데이터를 동일한 숫자로 나눕니다. 나머지가 없으면 데이터 단위가 올바른 것으로 간주하여 수락합니다. 그렇지 않으면 데이터 단위가 전송 중에 손상된 것으로 판단하여 거부합니다.

해밍이란 무엇인가 Code?

해밍 코드는 최대 두 개의 연속된 비트 오류를 ​​감지하고 단일 비트 오류를 ​​수정하는 데 유용한 선형 코드입니다. 이러한 유형의 오류 수정은 일반적으로 데이터 링크 계층에서 작동하며, 데이터를 프레임화하고 인접 노드 간의 데이터 무결성을 검사합니다.

해밍 부호화에서 발신자는 메시지에 중복 비트를 추가하여 메시지를 인코딩합니다. 이러한 중복 비트는 오류 감지 및 수정 과정을 수행하기 위해 메시지의 특정 위치에 삽입되고 생성됩니다.

해밍의 역사 Code

• 해밍 코드는 RW 해밍이 오류를 감지하고 수정하기 위해 개발한 기술입니다.
• 이 방법은 길이에 상관없이 모든 데이터 단위에 적용할 수 있으며, 데이터 비트와 중복 비트 간의 관계를 이용합니다.
• 해밍은 오류 수정 문제를 연구하며 점점 더 강력한 알고리즘들을 개발했습니다.
• 1950년에 그는 해밍 코드를 발표했는데, 이 코드는 오늘날에도 ECC 메모리와 같은 응용 분야에서 널리 사용되고 있습니다.

해밍의 응용 Code

다음은 해밍 코드의 일반적인 응용 사례입니다.

• 위성
• 컴퓨터 메모리(ECC RAM)
• 모뎀
• 플라즈마캠
• 커넥터 열기
• 차폐 와이어
• 임베디드 프로세서

해밍의 장점 Code

• 해밍 코드는 데이터 스트림이 단일 비트 오류에 노출될 수 있는 네트워크에서 효과적입니다.
• 이 기능은 비트 오류를 ​​감지할 뿐만 아니라 오류가 포함된 비트를 식별하여 수정할 수 있도록 도와줍니다.
• 해밍 코드는 사용이 간편하여 컴퓨터 메모리 및 단일 오류 수정에 매우 적합합니다.

해밍의 단점 Code

• 이는 단일 비트 오류 검출 및 정정 코드입니다. 여러 비트에 오류가 발견될 경우, 실제로는 올바른 비트가 잘못되어 데이터가 더욱 손상될 수 있습니다.
• 해밍 코드 알고리즘은 단일 비트 문제만 해결할 수 있습니다.

해밍 방식으로 메시지를 인코딩하는 방법 Code

발신자가 메시지를 인코딩하는 과정은 다음 세 단계로 구성됩니다.

• 중복 비트의 총 개수를 계산하십시오.
• 중복 비트의 위치를 ​​확인합니다.
• 각 중복 비트의 값을 계산합니다.

중복 비트가 메시지 내에 삽입되면 전체 코드워드가 수신자에게 전송됩니다.

1단계) 중복 비트의 총 개수를 계산합니다.

메시지에 다음 내용이 포함되어 있다고 가정해 봅시다. n 데이터 비트 및 p 2를 만들기 위해 추가된 중복 비트^p 적어도 (n + p + 1)개의 서로 다른 상태를 나타낼 수 있습니다.

여기서 (n + p)는 (n + p)개의 비트 위치 각각에서 오류의 위치를 ​​나타내며, 하나의 추가 상태는 오류가 없음을 나타냅니다. p개의 패리티 비트는 2ⁿ을 나타낼 수 있습니다.^p 주, 2^p (n + p + 1) 이상이어야 합니다.

2단계) 불필요한 부품들을 올바른 위치에 배치합니다.

p개의 중복 비트는 2의 거듭제곱인 비트 위치(예: 1, 2, 4, 8, 16)에 배치됩니다. 이 비트들은 p로 표시됩니다.₁ (위치 1에서), p₂ (위치 2에서), p₃ (4번째 위치에서) 등등.

3단계) ​​각 중복 비트의 값을 계산합니다.

각각의 중복 비트는 패리티 비트로서, 해당 그룹 내 1의 개수를 짝수 또는 홀수로 만듭니다. 패리티에는 두 가지 유형이 있습니다.

• 동등한 조건: 가려진 위치에 있는 1의 총 개수가 짝수가 됩니다.
• 홀수 패리티: 가려진 위치에 있는 1의 총 개수가 홀수가 됩니다.

각 패리티 비트는 위치 번호의 이진 표현에 의해 결정되는 특정 위치 집합을 담당합니다.

• p₁ 이진 값의 최하위 비트가 1인 모든 위치(1, 3, 5, 7, 9, 11 등)를 확인합니다.
• p₂ 이진 값의 오른쪽에서 두 번째 비트가 1인 모든 위치(2, 3, 6, 7, 10, 11 등)를 확인합니다.
• p₃ 이진 값의 오른쪽에서 세 번째 비트가 1인 모든 위치(4~7번째 위치, 12~15번째 위치 등)를 확인합니다.

예시 (7,4): 4개의 데이터 비트를 고려해 보세요. 10113개의 패리티 비트가 필요합니다(2³ = 8 ≥ 4 + 3 + 1), 따라서 7비트 코드워드는 p로 표현됩니다.₁ p₂ d₁ p₃ d₂ d₃ d₄데이터를 배치하면 위치 3, 5, 6, 7은 1, 0, 1, 1이 됩니다. 짝수 패리티를 사용하면 p₁ 위치 1, 3, 5, 7을 포함합니다 (비트 1, 0, 1 → p).₁ = 0); p₂ 2, 3, 6, 7을 포함합니다 (비트 1, 1, 1 → p)₂ = 1); p₃ 4, 5, 6, 7을 포함합니다 (비트 0, 1, 1 → p)₃ = 0). transmit따라서 테드 코드워드는 다음과 같습니다. 0110011.

해밍에서 메시지를 해독하는 방법 Code

수신자는 수신된 메시지를 받아 오류를 찾아 수정하기 위해 재계산을 수행합니다. 재계산 과정은 다음과 같은 단계를 거칩니다.

• 중복 비트의 개수를 세어 보세요.
• 모든 중복 비트를 올바른 위치에 배치하십시오.
• 패리티 검사를 수행합니다.

1단계) 중복 비트의 개수를 셉니다. 인코딩에 사용한 것과 동일한 공식을 사용합니다: 2^p ≥ n + p + 1, 여기서 n은 데이터 비트 수이고 p는 중복 비트 수입니다.

2단계) 모든 중복 비트를 올바른 위치에 배치합니다. 각각의 중복 비트는 2의 거듭제곱인 비트 위치에 있습니다. 예를 들어 1, 2, 4, 8 등이 있습니다.

3단계) ​​패리티 검사를 수행합니다. 패리티 비트는 데이터 비트와 수신된 중복 비트로부터 다시 계산됩니다.

• p₁ = 패리티(1, 3, 5, 7, 9, 11, …)
• p₂ = 패리티(2, 3, 6, 7, 10, 11, …)
• p₃ = 패리티(4–7, 12–15, 20–23, …)

재계산된 패리티 비트들을 합쳐 이진수를 만듭니다. 이 숫자가 0이면 오류가 없는 것이고, 그렇지 않으면 해당 값은 손상된 비트 하나의 정확한 위치를 나타내며, 이 비트를 뒤집어 메시지를 수정합니다.

자주 묻는 질문