오류 감지 및 수정 코드
우리는 비트 0과 1이 두 개의 다른 아날로그 전압 범위에 해당한다는 것을 알고 있습니다. 따라서 한 시스템에서 다른 시스템으로 이진 데이터를 전송하는 동안 노이즈도 추가 될 수 있습니다. 이로 인해 다른 시스템에서 수신 된 데이터에 오류가있을 수 있습니다.
이는 비트 0이 1로 변경되거나 비트 1이 0으로 변경 될 수 있음을 의미합니다. 우리는 노이즈의 간섭을 피할 수 없습니다. 그러나 먼저 오류가 있는지 여부를 감지 한 다음 해당 오류를 수정하여 원래 데이터를 복원 할 수 있습니다. 이를 위해 다음 코드를 사용할 수 있습니다.
- 오류 감지 코드
- 오류 수정 코드
Error detection codes− 수신 된 데이터 (비트 스트림)에 존재하는 오류를 감지하는 데 사용됩니다. 이러한 코드에는 원본 비트 스트림에 포함 (추가)되는 일부 비트가 포함되어 있습니다. 이 코드는 원본 데이터 (비트 스트림) 전송 중에 발생한 오류를 감지합니다.Example − 패리티 코드, 해밍 코드.
Error correction codes− 수신 된 데이터 (비트 스트림)에 존재하는 오류를 수정하는 데 사용되어 원래 데이터를 얻습니다. 오류 수정 코드는 또한 유사한 오류 감지 코드 전략을 사용합니다.Example − 해밍 코드.
따라서 오류를 감지하고 수정하기 위해 전송시 데이터 비트에 추가 비트가 추가됩니다.
패리티 코드
MSB의 왼쪽 또는 원래 비트 스트림의 LSB 오른쪽에 하나의 패리티 비트를 포함 (추가)하는 것은 쉽습니다. 패리티 코드에는 두 가지 유형, 즉 선택한 패리티 유형에 따라 짝수 패리티 코드와 홀수 패리티 코드가 있습니다.
심지어 패리티 코드
이진 코드에 1이 짝수이면 짝수 패리티 비트의 값은 0이어야합니다. 그렇지 않으면 하나 여야합니다. 그래서, 짝수 개의 사람들이even parity code. 패리티 코드조차도 데이터 비트와 패리티 비트를 포함합니다.
다음 표는 even parity codes각 3 비트 이진 코드에 해당합니다. 여기서 짝수 패리티 비트는 바이너리 코드의 LSB 오른쪽에 포함됩니다.
| 바이너리 코드 | 심지어 패리티 비트 | 심지어 패리티 코드 |
|---|---|---|
| 000 | 0 | 0000 |
| 001 | 1 | 0011 |
| 010 | 1 | 0101 |
| 011 | 0 | 0110 |
| 100 | 1 | 1001 |
| 101 | 0 | 1010 년 |
| 110 | 0 | 1100 년 |
| 111 | 1 | 1111 년 |
여기서 짝수 패리티 코드에 존재하는 비트 수는 4입니다. 따라서이 짝수 패리티 코드에서 가능한 짝수는 0, 2, 4입니다.
다른 시스템이 이러한 짝수 패리티 코드 중 하나를 수신하면 수신 된 데이터에 오류가 없습니다. 짝수 패리티 비트 이외의 비트는 이진 코드의 비트와 동일합니다.
다른 시스템이 패리티 코드 이외의 다른 코드를 수신하면 수신 된 데이터에 오류가 발생합니다. 이 경우 오류의 비트 위치를 모르기 때문에 원래 이진 코드를 예측할 수 없습니다.
따라서 패리티 비트조차도 수신 된 패리티 코드의 오류 감지에만 유용합니다. 그러나 오류를 수정하는 것만으로는 충분하지 않습니다.
홀수 패리티 코드
바이너리 코드에 홀수의 1이있는 경우 홀수 패리티 비트의 값은 0이어야합니다. 그렇지 않으면 하나 여야합니다. 그래서 홀수 개의odd parity code. 홀수 패리티 코드에는 데이터 비트와 홀수 패리티 비트가 포함됩니다.
다음 표는 odd parity codes각 3 비트 이진 코드에 해당합니다. 여기서, 이진 코드의 LSB 오른쪽에 홀수 패리티 비트가 포함됩니다.
| 바이너리 코드 | 홀수 패리티 비트 | 홀수 패리티 코드 |
|---|---|---|
| 000 | 1 | 0001 |
| 001 | 0 | 0010 |
| 010 | 0 | 0100 |
| 011 | 1 | 0111 |
| 100 | 0 | 1000 |
| 101 | 1 | 1011 |
| 110 | 1 | 1101 년 |
| 111 | 0 | 1110 년 |
여기서 홀수 패리티 코드에 존재하는 비트 수는 4입니다. 따라서 이러한 홀수 패리티 코드에서 가능한 홀수 수는 1과 3입니다.
다른 시스템이 이러한 홀수 패리티 코드 중 하나를 수신하면 수신 된 데이터에 오류가없는 것입니다. 홀수 패리티 비트 이외의 비트는 이진 코드의 비트와 동일합니다.
다른 시스템이 홀수 패리티 코드 이외의 다른 코드를 수신하면 수신 된 데이터에 오류가있는 것입니다. 이 경우 오류의 비트 위치를 모르기 때문에 원래 이진 코드를 예측할 수 없습니다.
따라서 홀수 패리티 비트는 수신 된 패리티 코드의 오류 감지에만 유용합니다. 그러나 오류를 수정하는 것만으로는 충분하지 않습니다.
해밍 코드
해밍 코드는 수신 된 데이터에 존재하는 오류를 감지하고 수정하는 데 유용합니다. 이 코드는 여러 패리티 비트를 사용하며 2의 거듭 제곱 위치에이 패리티 비트를 배치해야합니다.
그만큼 minimum value of 'k' 다음 관계가 올바른 (유효)은 필요한 패리티 비트 수입니다.
$$ 2 ^ k \ geq n + k + 1 $$
어디,
'n'은 이진 코드 (정보)의 비트 수입니다.
'k'는 패리티 비트 수입니다.
따라서 해밍 코드의 비트 수는 n + k와 같습니다.
하자 Hamming code$ b_ {n + k} b_ {n + k-1} ..... b_ {3} b_ {2} b_ {1} $ 및 패리티 비트 $ p_ {k}, p_ {k-1}, .... p_ {1} $. 'k'패리티 비트는 2 자리의 거듭 제곱으로 만 배치 할 수 있습니다. 나머지 비트 위치에는 이진 코드의 'n'비트를 배치 할 수 있습니다.
요구 사항에 따라 해밍 코드를 형성하는 동안 짝수 패리티 또는 홀수 패리티를 사용할 수 있습니다. 그러나 수신 된 데이터에 오류가 있는지 확인하기 위해서는 동일한 패리티 기술을 사용해야합니다.
이 절차에 따라 parity bits.
가치 찾기 p1, b 3 , b 5 , b 7 등의 비트 위치에있는 1의 수를 기반으로합니다 . 동등한 바이너리에서 이러한 모든 비트 위치 (접미사)는 2 0 의 자리 값에 '1'이 있습니다.
가치 찾기 p2, b 3 , b 6 , b 7 등의 비트 위치에있는 1의 수를 기반으로합니다 . 동등한 바이너리에서 이러한 모든 비트 위치 (접미사)는 2 1 의 자리 값에 '1'을 갖습니다 .
가치 찾기 p3, b 5 , b 6 , b 7 등의 비트 위치에있는 1의 수를 기반으로합니다 . 동등한 바이너리에서 이러한 모든 비트 위치 (접미사)는 2 2 의 자리 값에 '1'을 갖습니다 .
마찬가지로, 패리티 비트의 다른 값을 찾으십시오.
이 절차에 따라 check bits.
b 1 , b 3 , b 5 , b 7 등의 비트 위치에있는 1 의 수를 기반으로 c 1 의 값을 찾습니다 . 동등한 바이너리에서 이러한 모든 비트 위치 (접미사)는 2 0 의 자리 값에 '1'이 있습니다.
b 2 , b 3 , b 6 , b 7 등의 비트 위치에있는 1의 수를 기반으로 c 2 의 값을 찾습니다 . 동등한 바이너리에서 이러한 모든 비트 위치 (접미사)는 2 1 의 자리 값에 '1'을 갖습니다 .
b 4 , b 5 , b 6 , b 7 등의 비트 위치에있는 1의 수를 기준으로 c 3 의 값을 찾습니다 . 동등한 바이너리에서 이러한 모든 비트 위치 (접미사)는 2 2 의 자리 값에 '1'을 갖습니다 .
마찬가지로 다른 검사 비트 값을 찾으십시오.
수신 된 데이터의 검사 비트에 해당하는 십진수는 오류가있는 비트 위치의 값을 제공합니다. 해당 비트 위치에있는 값을 보완하십시오. 따라서 패리티 비트를 제거한 후 원래 이진 코드를 얻습니다.
예 1
바이너리 코드 d 4 d 3 d 2 d 1 = 1000에 대한 해밍 코드를 찾으십시오 . 짝수 패리티 비트를 고려하십시오.
주어진 이진 코드의 비트 수는 n = 4입니다.
다음 수학 관계를 사용하여 필요한 패리티 비트 수를 찾을 수 있습니다.
$$ 2 ^ k \ geq n + k + 1 $$
위의 수학적 관계에서 n = 4를 대입합니다.
$$ \ 오른쪽 화살표 2 ^ k \ geq 4 + k + 1 $$
$$ \ 오른쪽 화살표 2 ^ k \ geq 5 + k $$
위의 관계를 만족하는 k의 최소값은 3입니다. 따라서 3 개의 패리티 비트 p 1 , p 2 , p 3이 필요 합니다. 따라서 해밍 코드의 비트 수는 2 진 코드에는 4 비트, 패리티 비트는 3 비트이므로 7이됩니다. 우리는 아래와 같이 해밍 코드에 패리티 비트와 바이너리 코드의 비트를 배치해야합니다.
그만큼 7-bit Hamming code $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = d_ {4} d_ {3} d_ {2} p_ {3} d_ {1입니다. } p_ {2} bp_ {1} $
바이너리 코드의 비트를 대체하면 해밍 코드는 $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 100p_ {3} Op_ {2가됩니다. } p_ {1} $. 이제 패리티 비트를 찾아 보겠습니다.
$$ p_ {1} = b_ {7} \ oplus b_ {5} \ oplus b_ {3} = 1 \ oplus 0 \ oplus 0 = 1 $$
$$ p_ {2} = b_ {7} \ oplus b_ {6} \ oplus b_ {3} = 1 \ oplus 0 \ oplus 0 = 1 $$
$$ p_ {3} = b_ {7} \ oplus b_ {6} \ oplus b_ {5} = 1 \ oplus 0 \ oplus 0 = 1 $$
이러한 패리티 비트를 대체하면 Hamming code $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001011 $가됩니다.
예 2
위의 예에서 해밍 코드는 $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001011 $입니다. 이제 수신 된 코드가 $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001111 $ 일 때 오류 위치를 찾아 보겠습니다.
이제 체크 비트를 찾아 보자.
$$ c_ {1} = b_ {7} \ oplus b_ {5} \ oplus b_ {3} \ oplus b_ {1} = 1 \ oplus 0 \ oplus 1 \ oplus1 = 1 $$
$$ c_ {2} = b_ {7} \ oplus b_ {6} \ oplus b_ {3} \ oplus b_ {2} = 1 \ oplus 0 \ oplus 1 \ oplus1 = 1 $$
$$ c_ {3} = b_ {7} \ oplus b_ {6} \ oplus b_ {5} \ oplus b_ {4} = 1 \ oplus 0 \ oplus 0 \ oplus1 = 0 $$
체크 비트의 10 진수 값은 수신 된 해밍 코드에서 오류 위치를 나타냅니다.
$$ c_ {3} c_ {2} c_ {1} = \ left (011 \ right) _ {2} = \ left (3 \ right) _ {10} $$
따라서 해밍 코드의 세 번째 비트 (b 3 )에 오류가 있습니다. 원래 이진 코드를 얻으려면 해당 비트에있는 값을 보완하고 패리티 비트를 제거하십시오.