[정보통신공학] ch6. 오류 검출과 오류 정정

1. 학습목표

1.1. Timing

• 송신측이 보낸 비트의 시작과 끝이 수신측이 정확히 아는 것 = 동기화
• 1. Asynchronous Transmission 비동기식 직렬 전송
  • 데이터를 문자Character 단위 전송
  • 데이터의 시작을 알리는 start bit 0과 끝을 알리는 stop bit 1을 데이터의 앞 뒤에 붙여 수신기가 비트 경계 인식하게 함
  • 하드웨어 단순, 비용 저렴
  • 데이터마도 오버헤드(start/stop bit) 발생 → 전송 효율 낮음
• 2. Synchronous Serial Transmission 동기식 직렬 전송
  • 송신측과 수신측이 동일한 클록 신호에 맞춰서 대량의 데이터(프레임 단위)를 연속적으로 전송하는 방식
  • 데이터 블록의 시작과 끝에 특정한 비트 패턴(프레임 플래그)를 배치해서 동기화 유지
  • 오버헤드x, 고속 전송 적합, 전송 효율 높음

2.1. Error Detection 오류 검출

• 1. parity check 패리티 검사
  • 데이터 끝에 1비트의 parity bit를 추가해서 전체 1의 개수를 홀수 또는 짝수로 맞춤
  • 한 비트가 변하면 감지하지만 두 비트가 변하면 감지 못함
• 2. Internet Checksum 인터넷 체크섬
  • IP, TCP/UDP 에서 사용
  • 데이터를 일정 단위 (16비트)로 나누어 모두 더한 뒤, 그 합의 보수 (Complement)를 계산해서 전합
  • 수신 측에서 합이 맞는지 확인
• 3. Cyclic Redundancy Check CRC 순환 중복 검사
  • 수항적 다항식 나눗셈 이용
  • 데이터를 특정한 생성 다항식으로 나눈 나머지 값을 데이터에 붙여 보냄
  • 매우 강력한 검출 능력, 오늘날의 이더넷 등 대부분의 데이터 링크 계층에서 표준으로 사용

3.1. Error Correction 오류 정정

• 1. Backward Error Correction (BEC, 후방 오류 정정)
  • 수신측에서 오류를 검출하면 송신 측에 해당 데이터를 재전송(retransmission)해달라고 요청
  • ARQ- Automatic Repeat Request 프로토콜 이용, 전송 효율 낮으나 구현 명확
• 2. Forward Error Correction (FEC, 전방 오류 정정)
  • 송신 측에서 데이터에 Redundant bits 잉여 정보를 충분히 추가해서 보냄
  • 수신 측은 이 정보를 통해 재전송 요청 없이 스스로 오류 찾고 수정
  • 재전송을 위한 피드백 채널이 없으므로 지연 Latency가 중요한 실시간 통신, 심우주 통신에 주로 사용
  • Hamming Code, Reed-Solomon Code

2. 타이밍 드리프트 Timing Drift

2.4. Clock

• 디지털 시스템에서 모든 동작의 기준이 되는 주기적인 신호

2.5. Drift

• 두 장치의 클록 주파수가 완벽하게 일치하지 않아 시간이 지날수록 그 오차가 누적되는 현상

 

2.6. 샘플링 sampling

• 수신기가 들어오은 전기 신호를 읽어 0인지 1인지 결정하는 행위
• 전압 측정

수신 측의 클럭 속도가 더 빨라서 수신기가 비트를 여러번 샘플링 → 타이밍 드리프트에 의한 데이터 왜곡

 

해결방법

A. 별도의 클록 선 Clock Line 제공

• 송신기가 데이터를 보낼 때, 지금 읽으라는 클럭 신호를 별도의 선으로 함께 보내주는 방식
• 장거리 통신에서 비용 발생, 짧은 거리에서만 사용 (메인 보드 내부 등)

B. 데이터 안에 타이밍 정보 포함 (self-clocking)

• 데이터 신호의 변화(Edge) 자쳄나 보고 타이밍을 맞추는 방식
• 비동기식 전송(start/stop bit)
• 신호의 전압 변화를 이용하는 멘체스터 인코딩 Manchester Encoding

 

3. tx와 rx 사이의 신뢰성있는 통신

3.1 Rx가 알아야 하는거 2개

• bit arrial time: 첫번째 비트가 정확히 언제 시작하는지
• bit duration time: 비트 하나가 얼마 동안 유지되는지

3.2 rx는 중간 지점에서 샘플링 mid-point

• 비트가 시작되는 지점이나 끝나는 시점 edge는 전압이 바뀌는 불안정 구간
• 정중앙이 가장 전압 안정

3.3 타이밍의 구성요소

• rate 속도
  • 초당 몇 비트 보낼건지 bit rate, bps
• duration 지속 시간
  • 비트 하나가 점유하는 시간 T = 1/rate
• spacing 간격
  • 비트와 비트 사이, 프레임과 프레임 사이의 시간 거리는 얼마인지

3.4 rx와 tx의 클록을 동기화하는 2가지 방법

• Asynchronous 비동기식
  • 송신기와 수신기와 공통된 클럭 신호에 의해 지속적으로 동기화하지 않음
  • 평소에 조용하다가 데이터 올 때만 알려줌
  • 데이터 블록(바이트 단위) 앞에 start bit두서 수신기 시계 깨우기
  • 끝에 stop bit둬서 끝을 알림
  • 짧은 데이터 전송에 유리, 데이터 길어지면 내부 클록의 미세한 차이 drift때문에 뒤쪽 비트에서 오류
• Synchronous 동기식
  • 데이터가 일정한 속도 연속적인 흐름 Continuous stream 을 가지며 전송되는 방식
  • 송신기가와 수신기가 아주 긴 시간동안 똑같은 속도로 동작
  • 데이터 + 클록 신호(Self-clocking) 합쳐서 보내거나
  • 별도의 동기화 신호 주고 받음
  • start/stop 비트 없어서 대용량 데이터 빠르게 보냄

 

4. Asynchronous Transmission 비동기식 직렬 전송

- 데이터가 언제 올지 모르니 데이터 자체에 타이밍 정보 심어서 보내기

- 송수신기가 공통의 클록 신호 공유 x

 

4.1 데이터 프레임의 구조 frame와 절차

데이터를 문자 단위로 쪼개서 보냄 

• Idle state: 데이터를 보내지 않을 때 선로는 1 high 상태 유지
• start bit: 송신기를 전송을 시작할 때 선로의 전압을 0으로 떨굼 수신기가 이 전압 변화 edge를 감지하고 내부 클럭 리셋, 샘플링 시작
• data bits: 실 정보들 5 ~ 8비트 길이, LSB 먼저 전송됨
• parity bit: 오류 검출을 위해 추가되는 비트
• stop bit: 전송이 끝났음을 알리기 위해 다시 선로를 1 high 상태로 되돌림 최소 1 비트 이상의 길이

4.2 사전 협의 사항

송수신기가 사전에 다음과 같은 프로토콜 파라미터를 설정해야함

• 데이터 비트의 개수: 5 ~ 8비트 중에 고름, 한번에 보낼 데이터의 길이 결정
• 데이터 비트의 순서
• stop bit의길이: 정지 비트 길이를 1, 1.5, 2비트중 뭐로할지 정함, 수신기가 다음 데이터를 준비할 시간 주려고
• parity 설정: 오류 검출 할건지, 하면 짝수인지 홀수인지 (선택적)
• bit interval (비트 간격): 초당 몇 비트 보낼 건지 bps, 이게 일치해야 수신기가 mid-point 정확히 계산, 비트하나가 차지하는 시간, data rate의 역수

4,3 데이터는 한번에 한 문자씩 전송된다

비동기식 프레임 구성

• start bit: 각 문자의 시작으로 start bit 인식하기
  • 수신기가 하강 edge 기점으로 로컬 클록 0으로 맞추고 bit interval에 따라 샘플링 시작
• data bit: 각 문자는 5 ~ 8비트 길이
  • 현대통신에선느 8비트 1바이트가 표준
  • LSB 먼저 전송 MSB 마지막 전송
  • 수신 측에서 비트 수신하는 즉시 가중치 부여해서 값 계산하기 위함
• parity bit: 끝에는 (짝/홀 수)개의 패리티 비트 붙임
  • 데이터 비트 바로 뒤에 붙여서 전송 중 1비트의 오류가 발생했는지 확인하는 잉여 비트
  • 짝수 패리티: 전체 비트 중 1의 개수가 짝수가 되도록 맞춤
  • 홀수 패리티: 전체 비트 중 1의 개수가 홀수가 되도록 맞춤
  • 2개의 비트가 동시에 변하면 오류 못찾음
• stip bit: 마지막 비트
  • 다시 선로를 high(logical 1)으로 맞춤
  • 한 문자의 전송 끝, 수신기가 다음 시작 비트 감지하도록 선로를 다시 high상태로 충전하는 시간적 여유를 줌
  • 1, 1.5, 2비트 길이 사용, 수신기의 처리 속도에 맞춰 조정함

4.4. 프레이밍 에러 Framing Error

• 수신기가 nosie로 인해 선로 전압이 떨어져서 가짜 start bit로 오인한 경우
• 수신기는 가짜 시작 비트 기준으로 샘플링 시작 → 데이터 끝의 stop bit 위치에서 예상과 다른 전압 발견 → framing error

 

4.5 오버헤드

시작 비트 1개, 정지비트 2개, 데이터 8비트, 패리티 없음

total bit = start(1) + data(8) + stop(2) = 11

오버헤드 비트: 3bit

오베헤드 비율 = control bit / total bit = 3/11 = 약 28퍼 → 자원 낭비 

 

오버헤드들 줄이려면 큰 데이터 블록을 쓰면 됨 → 누적된 타이밍 에러 발생 timing drfit

비동기는 타이밍 오차가 누적되기 전에 전송을 끝내야 함 → 데이터를 짭은 단위로 끊어서 보내야함

* 데이터 전송 간의 interval은 예측 불가능함

 

4.6 재동기화

• 수신기는 각 문자의 시작마다 재동기화할 기회가 생긴다
• 타이밍 에러가 문자 간에 누적되지 않는다
• 시작 비트가 나타나는 순간 수신기는 이전까지 쌓인 drift 무시하고 다시 내부 클록 0으로 맞춤
• 8비트 읽는 동안의 미세한 오차는 샘플링에 영향x

4.7 장점

• 단순하고 쌈 - 송수신기 클럭을 서로 맞추는 비싼 동기화 회로 x
• 키보드나 teletypewriter처럼 입력할 때까지 긴 gap이 있는 데이터 전송에 최적화

4.8 단점

• 문자 당 오버헤드 2-3비트 (20% 차지) → 대역폭 20%이상 낭비 
• 너무 많은 데이터 블록을 보내면 타이밍 에러 발생

4.9 큰 데이터 블록을 보냈을 때의 타이밍 에러

 

송신기의 데이터 전송 속도(클럭속도) = 10kbps = 100μs

수신기의 데이터 수신 속도(클럭속도)가 송신기보다 6% 빠른 경우 = 94μs

송신기기가 50 150 250.. 시간 단위로 비트 전송하면

수신기는 50*0.94 = 47, 150*0.94 = 141..이런 시간으로 빨리 읽음

마지막에는 8번째 비트를 못읽고 7번째 비트를 다시 읽게됨

→ 큰 비트 블록으로 인한 누적된 타이밍 에러 발생 Cumulative timing error due to large blocks of bits

 

 

5. Synchronous Serial Transmission 동기식 직렬 전송

5.1 동기화

• timing drift를 막기위해 전송 내내 계속 수신기와 송신기의 클럭을 동기화해야한다 ↔ 데이터 올 때만 잠깐 맞춤(비동기식)

5.2 방법1 - 별도의 쿨럭 선 사용 seperate clock line

• 송신기가 데이터 전송시 별도의 전선을 통해 클럭 신호(박자)를 함께 보내주는 방식
• 데이터 선외에 클록 선 하나 더 연결
• 송신기가 비트를 보낼 때마다 클럭 선에 짧은 pulse를 줘서 수신기에게 샘플링 타이밍 알려줌
• 장점
  • 설계 매우 단순, 확실
  • 짧은 거리에서 좋음, 본체 내부 등
• 단점
  • 거리가 멀어지면 impairment, 장거리 통신x
  • 데이터 선과 클록 선 사이의 전기적 특성 차이로 인해 prapagation delay 전파 지연이 달라지는 clock stew 현상 발생
  • 박자는 도착했는데 정작 데이터는 아직 안왔거나 이미 지나갔거나

5.3 방법2 - 데이터 신호에 클록 정보를 내장 = encoding

• 멘체스터 인코딩 Manchester Encoding
• 1계층에서 L1 디지털 신호를 전송할 때 사용하는 방법
• 비트의 값을 전압의 높고 낮음(level)로만 결정하지 말고, 비트 구간의 중간에서 일어나는 전압의 변화 방향(transition)으로 결정하기
• bit 0
  • 전압이 고 → 저로 변한 경우
• bit 1
  • 전압이 저 → 고로 변한 경우
• 어떤 비트를 보내더라도 비트 구간의 정중앙에서 반드시 전압 변화 발생 → 수신기가 이 변화를 감지해 자기 클록을 계속 조정( Resynchronize) → 데이터가 곧 클럭 신호의 역할까지 수행
• 장점
  • 누적 타이밍 오차 완벽하게 해결
  • 장거리 전송에서도 데이터 스스로 클록을 제공함
• 단점 bandwidth
  • 비트 하나를 표현하기 위해 전압이 최소 한번 이상 변해야함
  • 일반적인 전송 방식보다 두배의 대역폭 소모
  • 10Mbps 속도를 내려면 물리적으로는 20Mbps 성능을 가진 선로 필요

 

5.4 framing 프레이밍 - L2 데이터 링크 계층에서 동기화 맞추기 ↔ L1 물리 계층에서 동기화 맞추기(멘체스터 인코딩)

• 동기식은 데이터 사이의 gap이 없어서 비트가 연속적인 흐름으로 들어옴
• 수신기는 어디서부터가 진짜 데이터이고 어디서 끝나는지 알아야함
• Framiing : correctly recognizing a packet boundary 데이터 경계 확정
• 수신기가 경계를 찾을 수 있도록 프레임의 앞뒤에 특수한 비트 패턴을 붙임
  • Preamable (프리앰블)
    • 프레임 시작 신호
    • 수신기가 클록 동기화를 점검하고 데이터의 첫 번째비트를 맞이할 준비하게 만듦
    • 이더넷의경우 10101010...같은 반복적인 패턴 이용해서 수신기 깨움
  • Postamble (포스트앰블)
    • 프레임 끝 신호
    • 프레임이 끝났음을 명시해서 불필요한 노이즈를 데이터로 인식x
• L1 물리 계층에서는 전압의 변화 Encoding으로 클럭 맞춤
  • 수신기가 비트를 0인지 1인지 정확히 읽기
• L2 물리 계층에서는 비트 패턴 Flag로 의미적 동기화 맞춤
  • 읽어낸 비트 중 어디서부터가 제어 정보이고 어디서부터가 진짜 데이터인지 구분하기

 

 

앞  8bit flag = preamble

뒤 8bit flag = postable

앞 control field = 헤더

뒤 control field = trailer (FCS(Frame Check Sequence)들어가서 CRC 같은 오류 검출 코드

data field = payload - 수백 ~ 수천 바이트의 대량 데이터 가능

→ 데이터가 몇 비트가 되든 앞 뒤에 flag만 붙이면 됨 → 데이터가 커질수록 오버헤드 0됨 

 

5.5 효율성

비동기식처럼 비트/문자 마다 start, stop비트 안 붙임 → 데이터 전체를 하나의 큰 블록으로 묶으로 그 앞 뒤에 제어 정보만 붙임

• HDLC (High-Level Data Link Control): bit-oriented 프로토콜, 데이터의 내용과 상관없이 비트 흐름 그 자체를 제어
• LAN - 문자 지향 Character-oriented 혹은 프레임 기반 전송 수행

큰 데이터 블록에 대해서는 비동기식보다 고효율 & 더 적은 오버헤드

• HDLC 구조가 프레임당 48비트를 control, preamable, postable 필드로 사용한다 가정
• 1000개의 문자(각 8비트)로 이루어진 데이터 프레임을 처리하면
• 오버헤드  = 48bits/(8000 + 48)bit = 0.6% (데이터 전송을 위해 희생된 비트의 비율)
• 효율성 = 8000bit/(8000 +48)bit = 99.4% (실제 순수 데이터 차지 비율)
• 비동기는 오버헤드 20% 이상임
• 즉 1Gbps속도의 광랜 사용시 비동기는 700~800Mbps, 동기식는 990Mpbs 이상의 성능

 

6. 비동기식과 동기식 비교

동기식

• 빠른 전송 (프레임(data) 사이 gapx)
• 프레임 안에 sync 정보 없음
• 낮은 오버헤드 → 높은 대역폭 효율 higher bandwidth effiicieny
• 하드웨어 비쌈 (송수신기가 클럭 신호 공유, 데이터를 프레임 단위로 모아서 한꺼번에 보내고 받아야 하므로 전송이 완료될 때까지 데이터 저장해둘 buffer memory 필수)
• 살짝 더 복잡함
• More efficient and reliable
• 이더넷과 ATM 등 고솓 데이터 프로토콜의 표준

비동기식

• 느린 전송(byte(데이터)간의 gap)
• 프레임 안에 start/stop bit있음
• 높은 오버헤드(문자당 2,3 bit) → 낮은 대역폭 효율 lower bandwidth effiicieny
• 싸고 구현하기 쉬움 (클럭 공유x, 버퍼x)
• simple
• Less efficiency and reliable
• 데이터가 sporadically 간혈적으로 보내질 때 좋음 ex. 키보드, RS-232/422/428같은 직렬 통신 규격

 

7. 에러의 종류

에러는 전송과 수신간에서 비트가 바뀐 것을 의미한다

7.1 Single bit error 단일 비트 오류

• 오직 하나의 비트가 바뀜
• 인접 비트들에게 영향x
• white noise에 의해 발생

7.2 burst error 버스트 오류

• 연속된 비트의 흐름 속에서 첫 번쨰 오류비트 부터 마지막 오류 비트까지의 거리 B인 구간 내에서 발생하는 오류
• B개의 비트가 전부 오류x, 그 중에서 발생한 것으로 뭉텅이로 깨진 구간
• higher data rate 고속 전송에서 영향이 더 큼 (오류의 피해가)
• 원인
  • 충격 잡음 impulse nose (번개, 스파크, 오로라 등)
  • Fading (무선 이동통신환경에서 신호가 산이나 건물에 부딪혀 세기가 약해지는 현상 )

7.3 L2에서 에러 검출

• 어떠한 설계에도  송신된 프레임에서 하나 이상의 비트가 변하는 에러가 발생한다
• 단일 비트 오류(bit error rate, BER)가 발생할 확률이 높아질 수록 프레임 전체에 오류가 없을 확률은 낮아진다
  
  • 프레임 하나에 비트 에러가 없을 확률 Pf
  • 단일 비트가 발생할 오류 Pe
  • 비트 하나하나가 독립시행일 때 
  • Pf = (1 - Pe)^n (n은 비트 수)
• 프레임 길이(n)가 길어질 수록 프레임 전체에 오류가 없을 확률은 낮아진다
  • 프레임을 길게 만들면 오버헤드 ↓ but 전송 줄 깨질 확률 높아짐, 재전송 ↑ → 성능 ↓ trade off
  • 프레임이 길어질수록 효율은 좋아지지만, 단 한 비트만 틀려도 프레임 전체를 버려야 한다는 위험이 커진다.
• 프레임의 길이가 길수록, 프레임을 구성하는 비트 수가 많을 수록, 에러가 발생할 확률이 높아진다
• 최적의 프레임 길이 정해야함
  • 에러가 적은 환경 (광섬유) → 긴 프레임 → 전송 효율 극대화
  • 에러가 많은 환경(무선 Wi-Fi, 위성 통신) → 짧은 프레임 → 오류 발생시 재전송해야 하는 데이터 양 줄임

8 에러 검출 과정

모든 에러 검출 알고리즘 (Parity, Checksum, CRC)의 공통 원리

전송기 TX

• data: 전송하고자하는 순수 데이터 k bit
• f(data): 특정 알고리즘 함수 f에 data를 집어넣음
• E = f(data): check bit or redundancy, n - k = r bit
• 전체 프레임 = data + e = k + r = n

수신기 RX

• 분리: 수신한 프레임에서 data' 와 E 분리
• 송신기와 동일한 함수 f를 사용해 받은 data'에 대해 f(data') 계산 = E'
• E와 E' 대조해서 에러 검출
  • E  = E' → 데이터를 상위 계층으로 보냄
  • E != E' → Mismatch, 에러 발생 알림

E, E' = error-detecting codes : 에러 검출 코드, 비트

f = error-detecting function : 에러 검출 코드 함수, 무작위 노이즈 발생해도 우연하게 E = E'될 확률을 극히 낮춤 (CRC)

 

① 송신기가 추가 비트 붙임 ( error-detecting codes 나 check bits)

② 수신기가 그 코드를 재계산하고 검사함

 

9. 3가지 에러 검출 기술

 

9.1 Parity check

• L2 데이터 링크 계층에서 하드웨어적으로 구현
• 데이터 뒤에 딱 1 비트만 추가해서 검출
• single bit error를 잘 잡지만, burst error는 못잡음

9.2 Internet checksum 인터넷 체크섬

• L3 인터넷(네트워크) 계층에서 IPv4가 사용
• L4 TCP/UDP가 소프트웨어적으로 구현
• 운영체제의 커널이나 프로토콜 스택 알고리즘 내에서의 덧셈 연산을 통해 이루어짐
• 하드웨어가 아니라 CPU가 계산하기 적합하도록 단순 산술 연산(1의 보수 합) 사용
• CRC만큼 강력x but 소프트웨어로 빠르게 처리

9.3 Cyclic Redundancy Check (CRC)

• L2 데이터 링크 계층에서 하드웨어나 소프트웨어로 구현
• 이더넷, Wi-Fi
• 매우 복잡한 이진 나눗셈 연산이 필요하므로 속도를 위해 전용 하드웨어 로직으로 구현되지만 소프트웨어로도 구현 가능
• 수학적인 생성 다항식을 이용해 버스트 오류 burst error를 거의 100% 잡아냄 신뢰성 매우 높음

9.4 공통점

• payload 데이터에 추가 비트(additional bits, redundancy)가 붙여짐
• 송신기가 붙임
• 에러 검출(Error detection) 목적으로 사용

→ 완벽한 신뢰성을 얻으려면 반드시 대역폭의 일부를 검사 비트로 할애하는 비용 overhead 지불 필요

 

10. Single (odd or even) Parity Check 단일 패리티 검사

• 송신기가 데이터 블록 끝에 1비트의 패리티 비트를 추가함 (가장 심플한 구조)
• 수신기가 해당 코드를 재계산하여 검사함
• 짝수 패리티 even parity: 전체 1의 개수가 짝수가 되도록 패리티 비트 결정
• 홀수 패리티 odd parity: 전체 1의 개수가 홀수가 되도록 패리티 비트 결정
• ex. data = 0101011 (1의 개수 4개) 
  • even parity 적용시 - 1이 이미 짝수개 이므로 패리티 비트는 0이됨 → 01010110
  • odd parity 적용시 - 1을 개수를 홀수로 만들어야 하므로 패리티 비트는 1 → 01010111
• 하드웨어적으로 XOR 게이트 이용해서 만듦
  • 데이터 + 패리티 비트에서 1의 개수가 홀수(1이 하나라도 있으면 1) → 1
  • 데이터 + 패리티 비트에서 1의 개수가 짝수 → 0
• 송신기에서 모든 데이터 비트를 XOR 연산하면 짝수 패리티 비트를 바로 얻을 수 있음 
• 수신기에서도 전체 비트를 XOR 연산해서 결과 0(짝수 패리티 기준)인지 확인하는 방식으로 에러 검출

10.1 한계 foolproof

• 짝수 개수의 비트가 뒤집히면 패리티 비트가 에러 검출 못함 (1의 전체 개수가 변하더라도 짝수/홀수 성질은 그대로 유지) → 에러 발생해도 정상으로 판단
• 홀수 개수의 비트가 뒤집히면 패리티 비트가 에러 검출 가능

 

11. 2-dimensional parity check 2차원 패리티 검사, 수직 수평 중복 검사 → detection 뿐만 아니라 correction도 가능

단일 비트 오류를 스스로 고칠 수 있는 FEC(Forward Error Correction) 기능 수행

 

 

12. Internet checksum 인터넷 체크섬

• IPv4와 TCP/UDP같은 인터넷 표쥰 프로토콜에서 사용하는 에러 검출 코드 (IPv6는 해당 필드 없음)
• CPU가 소프트웨어적으로 빠르게 처리

3단계

• 1. 16 bit Alignment
  • 전송하려는 전체 데이터를 16비트 (2바이트) 단위로 나눔
  • 만약 전체 데이터 길이가 홀수 비트라면 마지막에 0으로 된 padding 추가
•  2. 1의 보수 합 Ones-complement Addition
  • 나열된 16비트 데이터를 각각 부호 없는 정수로 간주하고 모두 더함
  • End-around carry: 덧셈 과정에서 최상위 비트 MSB위로 올림수 (carry)가 발생하면 이를 버리지 말고 최하위 비트 LSB에 다시 더해줌
  • 모든 비트가 합계에 균등하게 기여해서 오류 검출 능력 높임
• 3. 1의 보수 연산 Ones-complement Operation
  • 2의 결과 비트를 전부 반전시킴
  • 이 최종값이 checksum이 되며 송신기는 데이터와 함께 이걸 보냄

수신측

• 1. 수신된 데이터 + 체크섬을 모두 1의 보수 합
• 2. 데이터에 오류가 없다면 합의 결과는 모든 비트가 1인 결과
• 3. 결과값 중에 0이 하나라도 있다면 전송 중에 오류 발생

IPv4, TCP/UDP 같은 소프트웨어에서 구현 이유

• CRC처럼 복잡한 나눗셈이나 비트 이동x 단순 덧셈 위주 → 범용 CPU에서 구현하기 효율적
• 버스트 오류 검출 능력은 CRC 보다 떨어지지만, L3나 L4 계층에서 소프트웨어 부하를 최소화하면서 기본적인 무결성을 지킴
• 속도와 신뢰성 사이의 영리한 타협점

A + ~A = 1을 이용한 연산임

 

한계

• 두 개의 비트가 바뀌면 에러 검출 못함
  • 16비트 데이터 블록에서 n번째 비트가 0 → 1로, m번째 비트가 1 → 0으로 동시에 바뀌었다고 가정
  • 한쪽에서는 +2^n만큼이 값이 변하고 한쪽에서는 -2^m만큼 감소
  • 이 변화가 서로 다른 워드 사이에서 발생하여 전체 합계에 미치는 영향이 0이 되면(또는 보수 연산 과정에서 상쇄되면) 수신기를 에러 검출x
  • 근데 실제로 비트가 하필이면 합계가 같아지도록 정교하게 교환될 확률은 매우 낮아서 걍 사용함
  • 이더넷 L2에서 CRC가 이미 한번 강력하게 필터링 해줌
  • L3/L4에서의 인터넷 체크섬은 혹시 모를 소프트웨어 처리 과정의 오류를 잡아내는 것
• 덧셈의 교환법칙으로 인한 에러
  • 정상 데이터 Word A + Word B
  • 에러 데이터 Word B + Word A 
  • checksum은 동일하게 나와서 에러 검출 못함
• 인터켓 체크섬은 순서나 위치에 민감하지 않음
  • 합을 구하는 것이기에 숫자의 순서가 바뀌거나 합계가 바뀌지 않는 수준의 미세한 변화는 잡아낼 수 없음

13. CRC(Cyclic Redundancy Check, 순환 중복 검사)

• burst error는 단순한 parity check로 못 잡아냄
• 수신측에서 CRC는 프레임의 끝 trailer에 FCS(Frame Check Sequence)라 불리는 redundant 비트를 붙임
• RX가 나중에 FCS로 에러 검출

13.1 방법

• k = 원본 데이터의 비트 수 D(k)
• D = k비트의 원본 메세지
• n = 프레임을 구성하는 비트 수, 프레임의 크기 T(n)
• T = 데이터 뒤에 FCS (F)를 붙인 총 n 비트의 전송 데이터
• 송신기는 FCS라 부르는 n-k개의 비트열을 만들어냄, F(n-k)는
  • T(n) (프레임)은 P(n - k + 1)라는 n-k+1 비트 길이의 나누는 수로 나누어짐
  • P는 송수신이 미리 약속하여 공유되는 수로 생성 다항식
  • F는 n-k 비트 길이의 나머지 값 (n - k +1로 나누면 나머지는 0 ~ n-k 값이 나옴
• P = n-k+1 비트의 나누는 수
• F = n-k 비트의 나머지 값 = FCS = 찾아야 하는 것

13.2 송신측

• 원본 데이터 D 뒤에 n-k개의 0을 붙임 (왼쪽으로 비트 시프트)
• 이 값을 P로 나눔 XOR 연산을 기반으로 한 Modulo-2 나눗셈임
• 나눗셈 후 남은 나머지 값이 FCS(F)가 됨
• D뒤에 0 대신 방금 계산한 F를 붙임

13.3 수신측

• T를 받아서 P로 나눔
  • 나머지가 없음 → 에러 없음
  • 나머지가 0이 아님 → 에러 발생, 패킷 버림 
  • 에러가 절묘하게 발생해서 변조된 데이터가 P의 배수가 되버리면 → 에러 검출 불가
  • CRC의 유일한 약점이나 P를 충분히 복잡한 다항싱(CRC-32)로 설정하면 해결

13.4 CRC 생성

CRC의 목표

• T(n)(D + FCS)을 P(n-k-1)로 나누어 떨어질 수 있게하는 비트 패턴 FCS를 찾는 것임
• 따라서 FCS의 처음 패턴은 전부 0임

주어진 data D와 나누는 수 P를 가지고 FCS 찾기

• 원본 데이터 D 뒤에 n-k개의 0을 붙임(padding), n-k는 FCS 비트의 비트 수 → 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0
• 이 데이터를 P로 나눔 XOR 연산을 사용하는 Modulo-2 나눗셈으로
  • 빌림이나 올림 없음
  • 나눗셈을 끝까지 하면 마지막에 나머지가 나옴
• padding 자리에 실제 나머지 값을 갈아 끼움 → 최종 데이터 T는 P로 나눴을 때 0이 됨

13.5 CRC 코드 생성 방법

• 1.Modulo-2 Arithmetic 비트 연산 방식
  • 덧셈 뺄셈을 전부 XOR 연산으로 함
  • D 뒤에 P보다 1비트 적은 수 만큼 0을 붙임
  • 나눗셈을 수행하되 매 단계마다 피제수와 제수를 XOR함
  • 최종적으로 남은 나머가 FCS
    
    
• 2. Polynomial Representation 다항식 방식
  • 각각의 비트 스트림의 각 자릿수를 x의 지수로 표현
  •  110101 →  

• M(x): 메세지 다항식
• G(x): 생성 다항식 (제수P)
• R(x): 나머지 다항식(FCS)
  • 어떤 생성 다항식이 버스트 오류를 잘 잡아내는지 수학적으로 증명할 때 사용

• 3. Digital Logic 디지털 로직 방식
  • NIC 내부에서 하드웨어적으로 구현됨, 나눗셈을 실시간으로 처리해야 해서 매우 빠름
  • Shift Register(데이터 이동)과 XOR Gate(연산)으로 이루어짐
  • 1. 데이터가 한 비트씩 시프트 레지스터로 들어옴
  • 2. 다항의 계수가 1인 위치마다 XOR 게이트가 배치되어 연산 수행
  • 3. 모든 데이터 비트가 통과하고 나면 레지스터에 남아있는 값이 FCS

14 Modulo-2 산술 방식

• 올림 없는 이진 연산 = XOR 연산
• 송신측
  • ① 2^(n-k) x D = 데이터를 왼쪽으로 n-k 비트 밀어냄 = D뒤에 n-k개의 0이 붙음
  • ② 1의 값을 P로 나눔 → 나머지 R(n-k)
  • ③ 1의 0자리를 나머지 R로 바꿈
  • ④ T = D + R로 송신, T는 P의 배수가 됨
• 수신측
  • T를 P로 나눔
  • 나머지 0이 아니면 에러

14.1 예제

D = 1 0 1 0 0 0 1 1 0 1, P = 1 1 0 1 0 1, R, FCS는?

 

원본 데이터 값에 앞에서부터 P로 XOR 연산해주면서 0으로 바꾸고 마지막 5자리 비트값이 FCS가 됨

D에 FCS를 붙여서 T를 송신함

수신측은 받아서 똑같이 P로 XOR 연산해주고 나머지가 0이면 에러 x

 

15 CRC – Polynomial method 다항식 방식

15.1. 초기화

• x(n-k) * D(x) 해서 데이터 끝에 0을 n-k개 추가

15.2. x(n-k)*D(x)를 P(x)로 나눔, 나머지가 FCS

 

15.3. x(n-k)*D(x) + FCS = T(n)

 

15.4 예제

FCS 비트의 자리수  = 전체 프레임의 길이 - 데이터의 길이 = n - k = r

이 자릿수를 맞춰야하기 때문에 만약 나머지가 자릿수가 맞지않게 나왔다면 앞에 0붙여서 맞춘다

 

16. 다항식 P(x) 선택하기

• 최소 두개 이상의 항을 가질 것
• x^0 (상수항)의 계수는 반드시 1
  • 다항식의 마지막 비트는 반드시 1이어야 함. 
  • 마지막 비트가 0이면 전체 다항식이 x로 나누어 떨어지게되고 오류 검출 효율 떨어짐, 오른쪽 시프트된 에러 못 잡아냄

사용 분야

• CRC-8 / CR-10 ATM Header (Asynchronous Transfer Mode)
• CRC-10: ATM AAL
• CRC-12: 6비트 문자 기반 데이터 전송
• CRC-16(CRC-ANSI): 미국 표준 8비트 문자 전송 (ex.USB, HDLC)
• CRC-CCITT: 유럽 통신 8비트 문자 (X.25)
• CRC-32: IEEE H02.3 Ethernet (LAN), Wi-Fi, ZIP 압축 등

CRC-32

• 32비트(4바이트) FCS를 추가해서
• 모든 단일 비트 오류 100% 검출
• 모든 인접한 2비트 오류 100% 검출
• 홀수 개의 비트 오류 100% 검출
• 길이가 32 이하인 모든 버스트 오류 100% 검출
• 길이가 33 이상인 버스트 오류도 약 99.9999999% 확률로 검출

17. CRC - 디지털 논리 회로 방법

• 쉬프트 레지스터와 XOR 게이트 사용 - 나눗셈 연산은 느리지만 비트를 옆으로 밀면서 특정 위치에서 연산하는건 빠름
• 쉬프트 레지스터
  • FCS의 길이인 n-k 필요 (0 채워넣기)
• XOR 게이트
  • P에서 값이 1인 비트의 개수에서 1을 뺀만큼 필요
  • P에서 1의 개수 -1 = <= n-kV
• XOR 게이트 배치 규칙
  • 생성 다항식 P에서 비트 값이 1인 위치의 직전(before) 레지스터에 XOR 게이트 삽입
  • 가장 마지막 레지스터에서 빠져나오는 비트가 1이라면, 나눌 수 있음을 의미하므로 다시 앞으로 보내 각 XOR 게이트의 입력으로 넣음
• 수신기에서도 동일한 로직 적용

• 1. 모든 레지스터 0으로 초기화
• 2. step 1 ~ step 10까지 데이터 비트가 한 비트씩 입력받고 들어오면서 레지스터 값 업데이트
• 3. step 10 최종 상태: 나머지 구해짐
• → 하드웨어 회로가 비트가 들어오는 박자에 맞춰 단 10번의 시프트 만으로 나머지 계산해님 → 효율적

예제

 

18. L2에서 에러 정정 - 두가지 방안

18.1 Backward Error Correction (BEC) method 재전송 기반

• rx가 에러가 발생한 프레임을 버리고 송신 측에 재전송 요청 = ARQ (Automatic Repeat Request)
• ex. L2의 HDLC, L4의 TCP
• 부적절
  
  • 대역폭이 좁아 무선 링크에선 사용x 재전송까지 하면 효율 떨어짐
  • 긴 지연 시간: 위성 통신의 경우 신호가 오가는데 시간이 너무 오래 걸려 재전송된 데이터를 기다리는 동안 전체 서비스 느려짐
  • VoIP같은 실시간 서비스

18.2 Forward Error Correction (FEC) method 정정 코드 기반

• rx가 에러를 정정할 수 있도록 tx가 block coding을 함께 보냄
  • Block coding, hamming code 사용
• 받은 비트들에 기반해서 에러 정정해야함
• ex. 재전송할 시간이 없는 응용들 VoIP, 실시간 스트리밍, 한번 쏘면 끝인 방송 시스템

 

 

 

19. FEC 에러 정정 과정 다이어그램

Forward: 송신측으로 다시 돌아가서 재전송 요청안하니까, 오직 앞으로만 전진

FEC가 얼마나 많은 오류를 정정할 수 있는지는 해밍 거리를 통해 결정됨

• 검출하려면 최소 거리 d +1 
• 정정하려면 최소 거리 2d + 1

 

20. (FEC) 블럭 코드 원리 - 해밍 거리

 

20.1 해밍거리

• 해밍거리: 동일한 길이를 가진 두 비트열 사이의 차이점을 측정하는 척도
• 두 비트열 v1과 v2에서 서로 다른 값을 가진 비트의 개수
• 두 비트열을 XOR 연산한 결과값에서 1의 개수를 세면됨
• ex. d(011011, 110001) = 3

20.2 해밍거리로 에러 정정하는 법

데이터를 코드워드 cordword라는 특별한 형태로 포장해야함

• 원본 데이터를 k비트의 블록으로 나눈다
• 각 k비트 블록을 그보다 긴 n 비트의 고유한 코드워드로 변환한다 (n > k)
  • 이때 추가되는 n-k비트가 비트 오류 정정을 위한 여분 redundancy이다
• 원본 데이터 대신 이 n비트의 codeword 송신
• 우리가 전송할 수 있는 코드워드들 사이의 최소 해멍거리를 충분히 멀리 떨어뜨려 놓아야함
• s개의 에러 검출: 최소 거리 dmin >= s + 1
• t개의 에러 정정: 최소 거리 dmin >= 2t + 1
• n이 k보다 훨씬 클수록 더 많은 에러 비트를 고칠 수 있으나 전송 효율이 떨어짐 trade off

 

20.3 원리

• tx와 rx간의 codeword 테이블은 공유된다
• 테이블 lookup 알고리즘이 필요하다
• 만약 k =2, n=5이고 codeword 테이블이 위와 같을 때, rx에 00100이 도착했을 경우
• cordword에 해당 비트열이 없으므로 에러가 발생
• 최소 해밍거리를 찾는다
  • d(000000, 00100) = 1
  • d(00111, 00100) = 2
  • d(11001, 00100) = 4
  • d(11110, 00100) = 3
• 가장 해밍거리가 짧은 00000을 원래 보냈던 코드워드로 간주하고 데이터를 00으로 복원

20. 효율성

FEC를 도입하면 신뢰성을 올라가지만 전송 효율을 떨어진다 이를 측정하는 두가지

• Redundancy (잉여율)
  • 데이터 비트에 대한 잉여비트의 비율
  • (n-k)/k
  • 데이터보다 얼마나 더 많은 비트를 잉여비트로 쓰는가
• code rate (부호율)
  • 전체 전송 비트중 실제 정보가 차지하는 비율
  • k/n
  • 부호율이 낮을 수록 에러 정정 능력은 좋아지지만, 동일한 데이터를 보낼 때 더 많은 대역폭 필요
• n-k의 값이 커질수록 코드워드 사이의 해밍거리가 멀어지므로 정정 능력 향상
• 그러나 n이 켜지면 전송 속도가 느려지거나 더 넓은 주파수 대역 필요

 

이 유효 코드워드 간의 최소거리를 계산하면

 

이 코드워드 간의 최소 해밍거리는 3이다.

 

수학적으로 t개의 비트 오류를 정정 Correction하려면 최소 거리가 dmin >= 2t+1이어야 한다.

• 단일 비트 오류 정정 (t=1)
  • 2(1) + 1 = 3이다. dmin >= 3이므로 1비트 오류는 100프로 정정 가능
• 두 비트 오류 정정 (t=2)
  • 2(2) + 1 = 4이다. dmin >= 3이기에 2비트 오류는 정정할 수 없다
  • 즉 비트 2개가 깨져서 들어온 코드워드가 있을 때, 유효한 코드워드들과 최소 해멍거리를 계산했을 때, 여러개의 코드워드로부터 같은 최소 거리가 나와서 원래 어느 코드워드였는지 판단x

 

교수님 요약

Serial communication 직렬 전송 = one bit after another over a single channel

주로 신경 쓰는건 tx와 rx사이의 클록 동기화

 

Asynchronous  비동기 직렬 연결

• L1 계층에서 클록 동기화 안함
• L2의 프레임에 타이밍 정보가 들어감
  • Timing info: 1개의 start bit, 1-2개의 stop bits → 클록 싱크를 맞추기 위한 오버헤드임
  • 1-bit even/odd parity: optional임, → error detection을 위한 오버헤드임
  • 응용: 5-8bit의 짧은 크기의 데이터(character)가 느린 속도로 전달되는 keyboard 또는 teletypewriter
  • Frame PDU가 data 외의 클록 정보(star, stop bit)를 가지고 있고 한번에 큰 data를 보낼 수 없음
  • 따라서 오베헤드가 크고 efficiency가 떨어져 고속 통신에는 부적합
  • The higher data bits, the more efficiency but the higher probability  of timing erro

Synchronous  동기 직렬 연결

• L1에서 지속적으로 클록 동기화도록 설계한 거임
• 방법1
  • 추가 channel, wire를 두고 클럭 신호 채널을 따로 만들기
• 방법2
  • 데이터 신호 그 자체에 클럭 정보 같이 보내기 = Encoding
• 어차피 클록 동기화는 L1이 하니 L2는 패킷의 경계를 찾는 것에 집중 = framing
• frame에는 클록 정보 필요 없음 && 한번에 큰 데이터 전송 가능
• → 따라서 frame의 BW efficiency는 Asynchronous  보다 우월
• 그러나 time drifting 을 막기 위한 1계층의 오버헤드(additional channel or encoding을 위한 추가BW) 있음

멘체스터 인코딩

• 디지털 인코딩의 한 형태로, 송신측은 비트중간에 전압 변이를 만들어 전송
• 수신측은 전압변이 감지로 전달된 신호를 파악해서 전송 속도(bit interval도 알아냄)를 알아낼 수 있게된다.
• 동일한 데이터 전송시 2배의 추가적인 bandwidth가 필요하다
  • 예를 들어 user가 최대 10Mbps의 전송속도를 요구할 때, 10Mbps 이더넷 타드를 사용해서는 해당 품질 서비스 불가
• IEEE 802.3 규칙
  • 저 → 고주파로 변한경우 1
  • 고주파 → 저주파로 변한경우 0
  • 1은 01로, 0은 01로 인코딩
  • 데이터와 클럭신호간의 XOR 연산을 해서 데이터를 인코딩할 수 있다

Encoding = tx로부터의 비트 스트림에서 모든 비트를 정확하게 인식하는 것 ex. 멘체스터 인코딩

Framing = 패킷 경계를 정확하게 인식하는 것

 

the higher data rate → the more impact on bit errors

데이터 전송률이 높을수록 비트 에러의 영향이 커진다

the longer frame → the higher probability of receiving a frame in error

프레임의 길이가 길어질수록 에러가 있는 프레임을 수신할 확률이 커진다

에러 검출 방법: Parity check, CRC, internet checksum