[정보통신공학] 6. Digital data communication techniques

Timing

Asynchronous Transmission

Data are transmitted one character at a time

timing은 각 char에만 유지됨. receiver가 각 char를 resynchronize함

• bit error: 이전/이후 비트를 잘못 샘플
• framing error: 이전/이후 프레임 잘못 샘플 => 더 큰 에러
  overhead of 2 or 3 bites per char (stop bit 1, start bit 1-2)
  => to increase efficiency, larger block of bits required
  => greater cumulative timing error
  효율성 때문에 요즘은 많이 사용되지 않음

  
  Assume odd parity, stop bit: 1 bit
  ABC: 1000001 0100001 1100001
  0 1000001 1 1 0 0100001 1 1 0 1100001 0 1

Synchronous Transmission

block of data가 start,stop bits 없이 전송됨
block의 start, end indicate 필요

• preamble, postamble bit patterns
  ex) series of SYN char: LAN, Ethernet => character oriented
  ex) block of 01111110 pattern. bit pattern => bit oriented
  

asynchronous보다 효율적 (overhead 낮음)
ex) HDLC: bit oriented, LAN: character oriented

Error detection

Types of Errors

• Single bit error: one bit (0->1 // 1->0). adjacent bits not affected. caused by white noise
• burst error (of length B): 묶음. data rate ⬆, effect ⬆. caused by impulse noise or by fading in a mobile wireless environment

• frames: data transmitted as one or more contiguous sequences of bits
  frame이 bit error 없이 도착할 확률 ⬇, single bit error 확률 ⬆
  frame이 bit error 없이 도착할 확률 ⬇, frame length ⬆
  => frame length ⬆, frame bit error 확률 ⬆

• $P_{b}$: 받은 bit에 오류가 있을 확률
• $P_{1}$: frame이 bit error 없이 도착할 확률. $P_{1} = (1-P_{b})^F$ (F: # of bits per frame)
• $P_{2}$: error detection 알고리즘이 사용될 때, 수신자가 오류가 있는데 detect하지 못할 확률. $P_{2} = 1-P_{1}$ (error detecting 알고리즘 사용 X일 때)
• $P_{3}$: error detection 알고리즘이 사용될 때, 오류가 있고 undetected bit error가 없을 확률. $P_{3} = 0$ (error detecting 알고리즘 사용 X일 때)
  => 목적: P2 ⬇, P3 ⬆ (undetected error 줄이고, detected error 높이기)

오류 유무 탐지만 가능. 어느 오류인지 correct는 불가

Parity Check

: 데이터 블록 뒤에 parity bit을 붙여서 error detect
여러 계층: tcp, ip, data link layer(주로 여기), network access
오류 탐지 ⬇
character에 있는 # of 1이 짝수인지 홀수인지에 따라 parity bit이 결정됨. (주로, even parity -> synchronous, odd parity -> asynchronous)
Even number of bit errors -> undetected
XOR 연산 사용. (00, 11 -> 0 / 01, 10 -> 1)

• Two-Dimensional Even Parity Scheme(LDC): single bit error -> detect + correct까지 가능. 한 줄 parity check보다는 오류 탐지율 높음

Internet Checksum

3,4계층.

• One's complement
  : 0->1, 1->0. addition할 때는 leftmost bit에 carry가 있으면 그냥 sum 값에 1 더해주기
  16진수 one's complement 연산.(마지막에 꼭 ones complement 해주기)
  - sender가 보내는 checksum, 즉 연산 최종 결과값을 마지막에 붙여주기. checksum field: 2 octets
  - receiver가 check할 때는 ones complement 이전 값과 이후 값을 더해서 FFFF가 나오면 -> no error

P2 ⬇, P3 ⬆ parity보다 잘 충족, CRC보다 less effective

Cyclic Redundancy Check (CRC)

가장 common, powerful checks
k-bits의 block -> n-k bit sequence FCS (Frame Check Sequence)
나머지가 0이면 no error

• Modulo 2 arithmetic
  : XOR. no carries. remainder => FCS
• Polynomials
  : x에 대한 연산으로 표현
• Digital logic
  : # of shift registers => length of FCS
  # of XOR gates: # of 1 in P -1
  i가 1의 bit position에 있는 ith register에 XOR gate 삽입

Error correction

• data block의 재전송을 필요로 함
• wireless communication에는 부적합
  - bit error rate ⬆: 재전송 많이 필요
  - propagation delay ⬆: 에러 있는 프레임 재전송 요구할수도있음

=> need to correct errors on basis of bits received
FEC (Forward Error Correction): 수신 측에서 correct

Codeword

: k-bit block이 n-bit block과 mapped. (n>k)

• FEC encoder 사용해서 mapping
• received codeword가 FEC decoder로 들어오면
  - error X => original data block
  - some error patterns: detected & corrected
  - some error patterns: detected but !corrected
  - some (rare) error patterns: !detected

ex) block error correction code
add (n-k) bits to end of block: gives n bit block (codeword), all of original k bits are included in codeword
some FEC map k bit input into n bit codeword such that original k bits do not appear

• hamming code
  : FEC encoder를 통해 생성된 codeword 내에 원래의 데이터가 그대로 남아있지 않고 새로운 codeword 생성
  20개 -> single bit error (hamming distance = 1)
  8개 -> double bit error => detect o, correct x
  

Line configuration

• topology: physical arrangement of stations on medium
  - point-to-point: two stations
  (-) 각각의 comp에 각각의 I/O ports => 비용 ⬆
  (+) 각각 data direct 전송 => 관리 수월
  - multipoint: computer and terminals, LAN
  (-) I/O port 한 개 => 관리 복잡
  (+) 비용 ⬇
• duplex
  - half duplex: only one station may transmit at a time. two-way alternate; one lane, two way bridege. requires one data path
  - full duplex: simultaneous transmission and reception between two stations. two lane, two way bridge. requires two data paths