10.1 Intro
📁 Type of Errors
- single-bit error : bit 하나 오류
- burst error : 두개 이상 bit 오류
Redundancy (중복)
- error 탐지를 위해 보내는 data에 추가적인 정보를 붙여서 보낸다.
Coding
- 정보에 추가 bit를 붙여 가공
- ex) block coding
Sender
기존 data에 추가(redundant) bit를 더해준다. 기존 data와 추가 bit에 대한 realationship을 만듦.
Receiver
sender가 만든 realationship을 바탕으로 추가bit와 기존bit를 비교하여 에러가 있는지 확인하고 수정한다.
10.2 Block Coding
- message를 block 단위로 쪼갠다.
📁 Data word vs Code word
- Data word : data(k)
- Code word : data(k) + 추가 bit(r) = n bit
- k bit 단위로 Data word를 쪼갠다 - block으로 쪼갠것
- 각 block 마다 추가 bit (r bit)를 더해 n bit를 만든다
📁 Error detection
receiver의 역할
- valid codeword(sender가 encoding 함)를 가지고 있어서 error를 체크할 수 있다.
- codeword를 비교하고 안맞으면 discard
- error correction까지 하는 경우 codeword를 비교해서 data를 수정
📁 Hamming Distance (해밍 거리)
- 한 코드워드와 다른 비트 수 = XOR 연산에서 1의 개수
- codeword끼리 비교하는 것!
- d_min = 최소 해밍 거리
- d_min - 1개의 오류까지 탐지 가능
- d_min이 클 수록 많은 에러를 잡을 수 있다
ex)
-> 따라서 d_min = 2 -> 최대 1개의 오류만 탐색가능!- 예를 들어 101 Codeword를 수신해야하는데 1개 에러가 발생해서 100을 수신. 표 체크 하면 100이 없으니까 에러 ok 하고 discard = 에러 탐지 성공
- 근데 2개의 오류가 발생해서 000을 수신했다고 가정하면 표에 일치하는 게 생겨버림. 그냥 dataword 00을 잘 보냈구나~ 하고 에러를 탐지하지 못함
10.3 Linear Block Code(선형 블록 코드)
- Parity-check code (패리티 확인 코드)
- Hamming Code
- CRC (Cyclic Redundancy Check)
📁 Parity-check code
- simple parity check code : 홀수개 에러만 탐지
- two dimensional parity check code : 3개까지 탐지
📁 Hamming Code
C(n,k) = C(codeword,dataword)
- d_min = 3가 기본
- 단점 : Codeword 길이가 길어지면 계산이 복잡하다
n = 2^m - 1
k = n - m
- Data word : data(k)
- Code word : data(k) + 추가 bit(m) = n bit
- m = redundancy bit
- 보낼 때
- 받을 때
-> Syndrome(s0,s1,s2) 계산을 한 후 아래의 표를 통해 확인한다
📁 CRC (Cyclic Redundancy Check)
= 순환 중복 검사
- LAN, WAN에서 사용
- 해밍 코드와 연산만 다르다
-> CRC-N = N bit의 Syndrome = N bit의 추가 bit
