3 - 6) 에러 검출, 패리티 비트, 해시 함수

 

 

 

 

1. 에러 검출

 

- 데이터 링크, 네트워크, 전송 계층 모두 에러 검출을 위한 동작 수행

- 각 계층에서 사용하는 방식이 서로 다를 수 있음

- 일반적 에러 검출 기법인 "패리티 사용 기법"만 다루기로 하자

- NIC는 CRC 코드를 생성하고 이를 통해 에러 발생을 검출함

 

2. 에러 검출 및 정정

 

- 에러 검출을 위해서는 추가적인 데이터를 전송 데이터와 함께 보내줘야 함

 

- 가장 간단한 에러 검출 알고리즘 : 패리티 비트

- 수신 데이터의 에러 검출 후 에러를 정정하는 방식도 존재

: 비용이 많이 들어 잘 쓰이진 않음

: 에러 정정을 위한 알고리즘 : 해밍 코드

: 일반적으로는 에러 검출만 하고 다시 데이터를 재전송시킴으로써 에러에 대응함

 

3. 에러 검출 - 1차원 패리티

 

- 패리티 비트 : 보낼 비트 패턴에 1비트를 추가하여 전송 에러를 검출

* 단, 에러가 홀수 개 발생했을 때만 검출 가능하다

- 짝수 패리티 : 1의 개수가 짝수가 되도록 패리티를 지정

- 홀수 패리티 : 1의 개수가 홀수가 되도록 패리티를 지정

- 송신 호스트와 수신 호스트는 동일한 패리티 방식을 사용해야 함

 

- ASCII 코드의 MSB를 패리티 비트로 사용할 수 있음

- 수신 측은 MSB를 에러 체크에서만 이용하고, MSB를 다시 0으로 바꿔서 사용

 

ex ) 짝수 패리티

패리티 비트 외의 비트들이 짝수이면 0, 홀수이면 1을 대입한다.

첫 비트가 패리티 비트 / 11101011 / 01101001

 

 

4. 에러 검출 - 2차원 패리티

 

- 1차원 패리티는 짝수 개의 에러 검출 불가

- 수평, 수직 방향 모두에 패리티 비트를 지정

- 짝수 개의 비트가 깨지는 오류도 검출 가능 (항상 검출한다는 의미는 아님)

 

- 오버헤드가 1차원 패리티 비트 기법에 비해 크다

- 수평, 수직 방향 모두에서 사각형 형태로 발생한 짝수 개의 집단 오류는 검출 못함

 

 

5. 체크섬

 

- 주어진 디지털 데이터에 대해 미리 정해진 계산을 통해 일정한 길이의 작은 크기 데이터를 생성

- 이를 체크섬 이라고 함

- 주어진 데이터 D에 대해 체크섬 함수를 적용하여 값을 얻어냄. 즉, 체크섬을 계산함

 

< 체크섬 함수 >

- 동일한 데이터에 대해서 항상 동일한 체크섬이 나옴

- CF(D) = CF(D) 인게 당연한데, D에 오류가 발생했을 경우 동일한 체크섬값이 나오지 않을 것이므로 오류 검출이 가능하다

- 데이터 D를 일정한 크기로 나누고, 나눈 데이터들을 더하는 방식

 

< 체크섬 예 >

- 두 통신 entity N1, N2가 서로 통신한다고 가정

- N1과 N2는 체크섬 함수 CF()를 공유

- 전송 (D, CF(D)) -> N2

- N2는 받은 데이터에 대해 원래 알고있던 CF()함수로 다시 체크섬 계산

- 새로 계산된 체크섬 값과 수신한 체크섬 값이 일치하지 않으면 에러 발생으로 판단

 

* 단, 값이 일치한다고 해서 항상 에러가 없었다고 단정할 수는 없다. 독립 변수가 틀려도 종속 변수가 같게 나올 수 있기 때문이다.

 

 

6. Hash 함수

 

- 입력 데이터 m에 대해 일정한 길이의 비트 스트림으로 대응시킴

- H(m) -> S

- m의 길이는 정해지지 않은 것임

 

- 좋은 해시 함수는 m != m' 일 때, f(m) != f(m') 의 결과를 보이는 것임

- S가 클수록 충돌 현상이 줄어듦

- Y값을 안다고 해서 X값을 알 수 있는 것은 아님

 

- 널리 쓰이는 해시 알고리즘으로는 MD5와 SHA-1

- 체크섬 함수도 해시 함수 중 하나라고 할 수 있음

- 비트코인 채굴 과정에서도 해시 함수가 사용됨

 

< 충돌 가능성 >

- 2비트 : 1/2의 2승

- 16비트 : 1/2의 16승