CS공부(개념)

오류검출 및 제어: 패리티검사와 해밍코드

cantor 2023. 8. 4. 10:41

CONTENTS

        - 1. 오류
            - 비트오류 / 기타오류
            - 오류의 발생 이유

        - 2. 오류검출, 오류제어

            - 패리티코드
                - 단순 패리티검사
                - 2차원 패리티검사

            -  해밍코드

DETAILS

1.오류

데이터 전송의 정확도는 오류율 RER (Residual Error Rate)로 표기
- 오류비트수/전체비트수

오류: 보낸 데이터와 받은 데이터 사이에 차이가 존재하는경우

오류가 발생하는 이유

전자기 신호는 열, 자기장 및 여러형태의 간섭을 받기 쉬움

  • 원래의 신호, 타이밍등이 바뀔 수 있음

비트오류

비트값의 변경 으로 이루어짐

  • 단일비트오류(Single-Bit Error)
    • 한개의 비트가 변경

  • 다중비트오류(Multiple-Bit Error)
    • 여러개의 비트가 변경

  • 폭주오류(Burst Error)
    • 연속된 여러개의 비트가 변경

기타 오류

  • 주어진 시간안에 전송 실패
  • 주소 오류
  • 전송시스템 과부하

2. 오류제어 및 검출방식

오류제어

잡음, 고장등의 영향에 대비하여 RER을 허용 한계치 아래로 유지하는 기능

  1. 전진 오류정정(Forward Error Correction)
    • 송신측이 전송할 프레임에 추가적인 정보를 첨가
    • 수신측에서 오류를 검출, 수신 비트열을 통해 오류 내용도 유추
  1. 후진 오류정정 (Backward Error Correction)
    • 수신측이 오류를 검출할 수 있는 부가적 정보를 담아 전송
    • 오류 검출시 송신측에 재전송 요구

오류검출방식

패리티 검사 (parity check)

단순 패리티검사 (Single parity check)

전송 문자마다 패리티 비트 하나를 첨부하여, 오류의 발생여부를 검출하는 방식

전체 비트의 합이 짝수 또는 홀수가되도록 패리티 비트의 값을 설정
- 기준을 어떻게잡느냐에 따라 짝수 패리티, 홀수 패리티로 구분

과정예시: 짝수패리티

    1. 송신측에서 메시지의 전체 비트값의 합을 계산

 

    1. 패리티 비트 첨부
      • 비트값의 합이 홀수이면 패리티비트의 값을 1 로 설정
      • 짝수이면 패리티 비트를 0으로 설정

 

    1. 수신측에서 메시지를 수신

 

    1. 전체 비트값의 합을 계산
      • 홀수인 경우 송신측에 메시지 재전송 요청
      • 짝수인 경우 통과

단점: 비트가 짝수번 바뀌는 오류는 검출불가

2차원 패리티 검사 (Two-dimensional Parity check)

특정 메시지의 개수마다 블록 단위로 끊어,

행 뿐만아닌 열 에 대한 패리티 비트를 추가하는방식

해밍코드 (haming code)

잉여비트를 여러개 첨부해 오류를 감지하는것은 물론 오류가 발생한 비트도 파악 할 수 있게 하는 자기 오류정정 코드

  • 잉여비트(redundant bit)란 오류제어를 위해 추가한 비트를 뜻함.
    • 실제로 전송하고픈 정보는 데이터비트
    • 패리티비트는 잉여비트의 일종

 

  • 1비트의 오류를 찾아 정정할 수 있음

 

해밍코드를 위한 잉여비트 계산공식

2r ≥ m + r + 1

r = 잉여비트 수 , m = 데이터 비트 수

m r
2 2
4 3
5 4
26 5

짝수 패리티를 이용한 11비트 메시지 해밍코드 오류검출

1. 잉여비트 할당

2의 제곱에 해당하는 칸을 잉여비트 칸으로 할당

번호 11 10 9 8 7 6 5 4 3 2 1
자리 m m m 23 m m m 22 m 21 20
모양 m m m R4 m m m R3 m R2 R1

2. 잉여비트별 검사 위치

각 R1, R2, R3,... 잉여비트들은 2진수 비트열의 모양중,자신의 번호에 해당하는 이진수의 위치에 해당하는 값에 1을 가진 비트를 합하여 패리티 검사

R1: 첫번쨰 비트가 1인 위치의 비트들을 합하여 검사

1011 1001 111 101 11 1
11 9 7 5 3 1

 

R2: 두번째 비트가 1인 위치의 비트들을 합하여 검사

검사칸 1011 1010 111 110 11 10
십진수 11 10 7 6 4 3

 

R3: 세번째 비트가 1인 위치의 비트들을 합하여 검사

검사칸 1100 111 110 101 100
십진수 12 X 7 6 5 4

 

R4 : 네번째 비트가 1인 위치의 비트들을 합하여 검사

검사칸 1011 1010 1001 1000
십진수 11 10 9 8
  • 각 잉여 비트가 검사하는 위치

3. 오류 검출

검사합 결과를 일렬로 나열하면, 오류가 발생한 위치가 나옴

예시:

R4검사합 R3검사합 R2검사합 R1검사합
0 1 0 1
  • 0101 : 5 번 비트에서 오류가 발생

계산 방식

짝수 패리티

  • 검사합이 0이면 패스
  • 검사합이 1이면 오류
R4검사합 R3검사합 R2검사합 R1검사합
0 1 0 1
잉여비트 검사위치 오류여부
R1 1, 3, 5, 7, 9, 11 O
R2 2, 3, 6, 7, 11 X
R3 4, 5, 6, 7 O
R4 8, 9, 10, 11 X

R1과 R3의 공통비트중 오류가 발생

  • 5 또는 7이 오류비트 위치

R2에 속하는 비트 배제

  • 7이 배제

그러므로 5번비트에 오류가 있음을 알 수 있음

 

cs스터디중 네트워크: 오류 검출 및 제어 파트를 정리했습니다.

 

참고: https://www.geeksforgeeks.org/hamming-code-in-computer-network/

'CS공부(개념)'의 다른글

  • 현재글오류검출 및 제어: 패리티검사와 해밍코드
댓글

티스토리툴바