오류 검출과 정정

해당 블로그의 내용은 학교에서 배운 내용을 개인적으로 정리한 내용이므로, 잘못된 부분이 있을 수도 있습니다. 

 

 

개요

• 오류의 유형 
  • 단일-비트 오류(Single-Bit Error)
    • 오직 하나의 비트만이 변경되는 오류(0 => 1, 1=> 0)
  • 폭주 오류(Burst-Error)
    • 2개 이상의 연속적인 비트들이 변경되는 오류
• 중복(Redundancy)
  • 오류를 검출하거나 정정하기 위해 데이터 이외에 추가하는 비트
  • 중복 비트들은 송신자에 의해 더해지며 수신자가 제거
• 오류 검출(Error Detection): 오류가 있는지만 판별
• 오류 정정(Error Correction): 정확하게 몇 비트가 잘못되었는지 알아야 하며, 특히 어느 비트가 잘못되었는지를 알아내는 것
  
  • 전진 오류 정정(Forward error correction)
    
    • 수신자가 메세지의 중복 비트를 이용하여 메세지를 추측하는 과정
  • 재전송(Retransmission)
    • 오류 발생을 검출하여 송신자에게 다시 보내줄 것을 요청하는 과정 
• 패리티 검사 코드
  • 홀수 개의 오류를 검출
• 부호화(encoding)
  • 블록 부호화
  • 컨볼루션 부호화
• 모듈러 연산(modular arithmetic)
  • 모듈러 N이라는 제한된 정수 사용
  • 0부터 N-1까지 정수 사용
  • 모듈러-2 연산: 2, 0, 1 만 사용

 

블록 부호화

• 메세지를 데이터워드(dataword)라는 k비트의 블록으로 나눔
• 각 블록에 r개의 중복 비트들을 더하여 길이 n=k+r로 만듬
• n비트 블록을 코드워드(codeword)라고 부름 

오류 검출을 위한 조건

• 수신자는 유효 코드워드를 찾을 수 있거나 그 목록을 가지고 있음
• 원래 코드워드가 무효 코드워드로 바뀌면 >> 오류 발생 확인 >> 폐기

오류 정정

• 오류 검출보다 많은 중복 비트가 필요 

해밍 거리

• 오류 제어를 위한 중심 개념
• 전송되는 동안에 오류가 생긴 비트의 수
  • ex) d(0000,1011) = 3 , 3개의 비트가 바뀌었기 때문
• 전송 도중 n개의 오류가 발생했다면, 최소 해밍 거리는 n+1이 된다.
  • 손상된 채로 유효 코드 중의 하나가 될 수 없게 하기 위함 

선형 블록 코드 (Linear block codes)

• 오늘날 사용되는 대부분의 블록 코드
• 선형 블록 코드에서는 임의의 두 유효 코드워드(codeword)에 XOR연산을 가하면 다른 유효코드가 생성
• 패리티 검사 코드
• 최소 해밍 거리
  • 0이 아닌 가장 적은 수의 1을 가지고 있는 코드워드의 1의 개수 
• 2차원 패리티 검사

순환 코드

• 하나의 특별한 성질을 갖는 선형 블록 코드
• 코드워드를 순환시키면 다른 코드워드를 얻음 
• 순환 중복 검사(CRC, Cyclic Redundancy Check)
  • 오류를 정정하기 위한 순환 코드를 생성
  • LAN이나 WAN에서 많이 사용
  • 절차 
    • 데이터워드의 오른편에 (n-k) 만큼의 0을 더한다
    • 데이터워드를 나누기 장치(모듈러2 나누기)로 나눈다
      • 제수는 표준 제수에 의해 선택되고, 나누는 도중 LSB(최하위 오른쪽 비트)가 0이면.
        제수 0000을 사용한다. 
      • 제수의 길이는 k이고, 피제수와 나머지의 길이는 n-k 이다. 
      • 곱하기는 AND 연산, 빼기는 XOR 연산을 한다. 
    • 몫은 버리고, 나머지를 데이터워드에 덧붙여 코드워드로 만든다 
    • 이 나머지는 신드롬이 되고, 신드롬이 모두 0이면 높은 확률로 오류가 없는 것.
    • CRC-(n) 표준 다항식에서 n이 최고 차항의 계수가 된다. 

표준 다항식

• 다항식
  • 덧셈과 뺄셈
  • 곱셈과 나눗셈
  • 이동   
    • 왼쪽 이동: 오른쪽 비트에 0 더함
    • 오른쪽 이동: 오른쪽 비트를 지움
• 이점
  • 단일 비트, 2비트, 홀수개 비트, 폭주 오류를 검출하는데 우수함
  • 하드웨어 및 소프트웨어로 쉽게 구현
  • 하드웨어로 구현시 속도가 빠름
    • 많은 네트워크에서 사용

 

검사합

• 모든 길이의 메세지에 적용시킬 수 오류 검출 기법
• 네트워크층과 전송층에서 사용
• 생성기(generator)
  • 검사합을 포함한 모두 워드를 1의 보수 연산을 하여 더한다
  • 그 합을 보수를 취하여 최종값을 검사합으로 한다  
  • 기존 메세지에 검사합 비트(m비트 단위)를 추가한다
• 확인기(checker)
  
  • 전송된 검사합을 이용하여 새로운 검사합을 만든다
    • 모든 워드를 보수 연산을 하여 더한다
    • 그 합을 보수를 취하여 최종값을 새로운 검사합으로 한다. 
  • 새로운 검사합이 모두 0이면, 오류가 없는 것이고 그렇지 않으면 메세지는 폐기된다.
• 보수의 합인 검사합을 전송하면 수신자의 작업을 보다 쉽게 만들 수 있다