해밍 코드를 사용하여 메시지를 수정하는 방법

StackOverflow https://stackoverflow.com/questions/757409

  •  09-09-2019
  •  | 
  •  

문제

그래서 이번 여름 프로젝트에서 Hamming Code를 사용하여 메시지 전송 오류를 수정하는 작업을 진행하고 싶지만 실제로 어떻게 작동하는지 알 수 없습니다.온라인에서 많은 기사를 읽었지만 알고리즘을 실제로 이해하지 못합니다.누구든지 간단한 용어로 설명할 수 있나요?

감사해요.

도움이 되었습니까?

해결책

모든 것에 관한 것입니다 해밍 거리.

두 밑수 2 값 사이의 해밍 거리는 서로 다른 비트 수입니다.따라서 귀하가 A를 전송했지만 내가 B를 수신하는 경우 전송 시 전환되어야 하는 비트 수는 A와 B 사이의 해밍 거리입니다.

해밍 코드는 각 코드 워드의 비트가 어떻게든 별도로 전송될 때 유용합니다.직렬인지 병렬인지는 상관하지 않지만, 예를 들어 여러 비트를 나타내는 아날로그 값으로 결합되거나 인코딩 후 압축/암호화되지는 않습니다.

따라서 각 비트는 독립적으로(일부 고정 확률로 무작위로) 올바르게 수신되거나 반전됩니다.전송이 상당히 안정적이라고 가정하면 대부분의 비트가 올바르게 수신됩니다.따라서 적은 수의 비트에서 오류가 발생할 가능성이 더 높으며 많은 비트에서 동시에 오류가 발생할 가능성은 거의 없습니다.

따라서 해밍 코드는 일반적으로 1비트 오류를 ​​수정하거나 2비트 ​​오류를 ​​감지하는 것을 목표로 합니다(두 가지 주요 유형에 대한 자세한 내용은 Wikipedia 문서 참조).더 큰 오류를 수정/감지하는 코드를 구성할 수 있지만 AFAIK는 많이 사용되지 않습니다.

코드는 "해밍 공간"에서 코드 포인트의 간격을 균등하게 두는 방식으로 작동합니다. 이 공간은 수학적으로 해밍 거리를 메트릭으로 사용하여 관련 단어 크기의 모든 값으로 구성된 메트릭 공간입니다.각 코드 포인트가 잘못된 값의 작은 "버퍼 영역"으로 둘러싸여 있다고 상상해 보세요.코드 포인트가 아닌 값이 수신되면 유효한 코드 포인트만 전송되므로 오류가 발생한 것입니다.

버퍼존의 값이 수신되면 1비트 오류가 발생했다는 가정하에, 전송된 값은 수신된 값으로부터 거리 1이어야 합니다.그러나 코드 포인트가 분산되어 있기 때문에 닫히는 코드 포인트는 단 하나뿐입니다.따라서 수신된 값을 생성하기 위해 다른 코드 포인트에 필요한 더 큰 오류보다 1비트 오류가 더 가능성이 높기 때문에 해당 코드 포인트로 "수정"됩니다.확률 측면에서, 내가 받은 값을 받았다는 점을 고려하면 가까운 코드 포인트를 보낸 조건부 확률은 다른 코드 포인트를 보내는 조건부 확률보다 큽니다.그래서 전송의 신뢰성과 각 단어의 비트 수를 바탕으로 어느 정도 확신을 가지고 근처에 있는 것을 보낸 것 같습니다.

두 코드 포인트에서 등거리에 있는 유효하지 않은 값이 수신되면 하나가 다른 것보다 실제 값일 가능성이 더 높다고 말할 수 없습니다.그래서 오류를 감지했지만 수정할 수는 없습니다.

분명히 3비트 오류는 SECDED 해밍 코드로 수정되지 않습니다.수신된 값은 다른 코드 포인트보다 실제로 보낸 값에서 더 멀어서 잘못된 값으로 잘못 "수정"했습니다.따라서 신경 쓰지 않을 만큼 안정적인 전송이 필요하거나 더 높은 수준의 오류 감지도 필요합니다(예: 전체 메시지에 대한 CRC).

다른 팁

구체적으로 위키 백과, 알고리즘은 다음과 같습니다.

  1. 1 : 비트 1, 2, 3, 4, 5 등에서 시작하는 비트를 번호로 숫자.
  2. 이진에 비트 번호를 작성하십시오. 1, 10, 11, 100, 101 등
  3. 2 개의 힘 인 모든 비트 위치 (위치의 이진 형태에 1 비트가 1 비트가 있음)는 패리티 비트입니다.
  4. 이진 형태의 위치에 2 개 이상의 1 비트가있는 다른 모든 비트 위치는 데이터 비트입니다.
  5. 각 데이터 비트는 비트 위치의 이진 형태에 의해 결정되는 2 개 이상의 패리티 비트의 고유 한 세트에 포함됩니다.
    1. 패리티 비트 1은 가장 유의미한 비트 세트를 갖는 모든 비트 위치를 다룹니다. 비트 1 (패리티 비트 자체), 3, 5, 7, 9 등
    2. 패리티 비트 2는 두 번째 최소 비트 세트가있는 모든 비트 위치를 덮습니다 : 비트 2 (패리티 비트 자체), 3, 6, 7, 10, 11 등
    3. 패리티 비트 4는 세 번째 최소 비트 세트가있는 모든 비트 위치를 덮습니다 : 비트 4–7, 12–15, 20–23 등.
    4. 패리티 비트 8은 네 번째 최소 비트 세트가있는 모든 비트 위치를 덮습니다 : 비트 8–15, 24–31, 40–47 등.
    5. 일반적으로 각 패리티 비트는 이진 및 패리티 위치 및 비트 위치가 0이 아닌 모든 비트를 포함합니다.

그만큼 위키 백과 기사 그것을 아주 멋지게 설명합니다.

알고리즘의 특정 측면을 이해하지 못하면 누군가가 문제의 특정 부분을 해결할 수 있도록 질문 (또는 세부 사항)을 다시 제출해야합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top