[정보통신공학] Digital Data Communication Techniques

Overview

• For two devices linked by a transmission medium to exchange data, a high degree of cooperation is required
 Timing (Synchronization: rate, duration, spacing)
 Error Detection
 Error Correction
 Line Configuration

---

Asynchronous and Synchronous Transmission

• 타이밍 문제에는 송신기와 수신기를 동기화하는 메커니즘이 필요하다
Timing problems require a mechanism to synchronize the transmitter and receiver

• Two solutions to synchronize clocks
 Asynchronous
 Synchronous

동기화가 왜 필요할까?
ex) Date rate: 1 Mbps 
1 bit duration (1 bit를 보내는데 걸리는 시간) : 1 µsec 이라고 해보자

송신자와 수신자 사이에 차이가 발생한다 (drift)
: 빛의 중앙으로부터 50% (50개까지는) 괜찮다. 그치만 그 이상이 되면 잘못된 bit time 이다
이를 해결하기 위해 동기화가 필요하다

 

Asynchronous Transmission

• 데이터 한번에 한 캐릭터 전송 / Data are transmitted one character at a time
 Each character is 5 to 8 bits in length

• 캐릭터마다 timing 유지한다 / Timing is only maintained within each character
• Receiver resynchronizes with each character
- drift가 발생하면 resynchronize를 통해 다음은 제자리(중간)로 맞게한다

• Two types of errors:
 Bit error - 다른 bit를 sampling
 Framing error - 다른 frame을 sampling (더 큰 개념)

• Simple and cheap
• Overhead of 2 or 3 bits per char (20% or more)
=> To increase efficiency, larger block of bits required
=> Greater cumulative timing error

 

(a) character format
- 데이터가 들어오면 start bit =0
- 전체 1의 개수가 even 인지 odd 인지 확인
- stop element (1 or 2 bits) =1

(b) 8-bit asynchronous character stream
- start bit 부터 parity bit 까지 1의 개수를 세어 parity bit 이 0 인지 1인지를 결정한다
(만약 format이 1의 개수가 even인데 start bit 부터 parity bit 까지 1의 개수가 odd라면 전체는 even이 되어야하므로 parity =1 )

(c) Effect of timing error
- reiceiver와 transmitter의 smapling 속도가 다르면 wrong bit error

 

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

* start bit 가 나올때마다 receiver가 resynchronize 시작하여 중앙(제자리)에서 data를 수신할 수 있게끔 한다

---

 

Synchronous Transmission

• 시작, 끝 bit 없이 전송 /  Block of data is transmitted in a steady stream without start and stop bits
• 시작점, 끝점을 가리키는 게 있어야함 / Need to indicate start and end of block

• Use preamble and postamble bit patterns → 시작과 끝을 알려준다
 e.g. series of SYN characters
 e.g. block of 01111110 pattern

• 더 효율적 / More efficient (lower overhead) than asynchronous for large blocks of data
• e.g. HDLC (bit oriented) LAN (character oriented)

 

<character oriented>

 

<bit oriented>

 

Types of Errors

• 송신과 수신 사이 비트가 변동될 때 에러 발생

• Single bit error
 One bit altered (하나만 변동)
 Adjacent bits not affected (주변 비트에 영향 X)
 Caused by white noise

• Burst error (of length B )
 길이 B에 에러가 연속적으로 있음 / Contiguous(연속된) sequence of B bits in which the first and last bits and any number of intermediate bits are received in error
 data rate 가 높을때 더 영향이 크다 / Effects are greater at higher data rates
 Caused by impulse noise or by fading in a mobile wireless environment

 

Error Detection

• Regardless of design, you will have errors, resulting in the change of one or more bits in a transmitted frame
• Frames
   Data transmitted as one or more contiguous sequences of bits
• frame이 에러 없이 전달될 확률은 single bit 에러가 날 확률이 높을수록 감소한다 / The probability that a frame arrives with no bit errors decreases when the probability of a single bit error increases
• frame이 길어질수록 bit 수가 많아지므로 error 발생 확률 높아진다
The probability that a frame arrives with no bit errors decreases with increasing frame length
   The longer the frame, the more bits it has and the higher the probability that one of these is in error

 

Error Detection

- 목적 : P2↓  P3↑

Pb	• Probability that a bit is received in error; also known as the bit error rate (BER) • 에러가 날 확률
P1	• Probability that a frame arrives with no bit errors • P1 = (1 - Pb ) F where F is the number of bits per frame • 1 - Pb= 한 비트가 오류가 없을 확률
P2	• Probability that, with an error-detecting algorithm in use, a frame arrives with one or more undetected errors • P2 = 1 – P1 when no error-detecting algorithm is used • 에러를 발견하지 못할 확률
P3	• Probability that, with an error-detecting algorithm in use, a frame arrives with one or more detected bit errors but no undetected bit errors • P3 = 0 when no error-detecting algorithm is used • 에러 발견할 확률

 

Parity Check

• 가장 간단한 오류 감지 체계는 데이터 블록의 끝에 parity bit를 추가하는 것이다.

• receiver에 의해 code는 다시 계산되고 확인된다
• Value of parity bit is selected so that character has even (even parity) or odd (odd parity) number of 1s
- 잘도착하면 p 없이 다음 계층으로 전달 ( 필요없으므로)
• Typically, even parity for synchronous and odd parity for asynchronous transmission
• 짝수개가 error가 나면 error를 발견하지 못한다 
• Implemented by using exclusive-OR

 

(c) single bit error 가 발생하면 error detect 도 가능하고 correct까지 가능하다
(d) 같은 col, row 에 짝수개의 error가 발생하면 error detect를 하지 못한다

 

The Internet Checksum

• Error detecting code used in many Internet standard protocols, including IP, TCP, and UDP

• Ones-complement operation (1의 보수)
 Replace 0 digits with 1 digits and 1 digits with 0 digits ( 0 → 1 , 1 → 0 )

• Ones-complement addition (1의 보수 덧셈)
 The two numbers are treated as unsigned binary integers and added
 If there is a carry out of the leftmost bit, add 1 to the sum (end-around carry)

 

Example : Consider a header that consists of 10 octets, with the checksum in the last two octets: 00 01 F2 03 F4 F5 F6 F7 00 00

00 01 F2 03 F4 F5 F6 F7 00 00 여기서 마지막 00 00 자리가 error detection을 위해 사용되는checksum field 이다

(a) sender
- 앞에서 2개씩 더해준다 (checksum field 제외)
- 다 더해서 나온 결과에 1의 보수로 바꿔준다

DDF2 -> 1101 1101 1111 0010 -> 0010 0010 0000 1101 -> 220D

(b) receiver
- 마찬가지로 다 더해준다
- 더해서 나온 결과에 sender에서 한 1의 보수를 더해준다

DDF2 + 220D = FFFF

FFFF는 모든 값이 1이므로 ERROR 없음

 

The Internet Checksum

• Provide greater error-detection capability than parity scheme ( P2↓  P3↑)
• Considerably less effective than CRC 
• 인터넷 프로토콜 채택 이유: 효율성
 Implemented in software
 Assume that at the lower link level, a strong errordetection code is used (ex: CRC)
 Internet checksum is simply an additional end-to-end check for errors

 

Cyclic Redundancy Check (CRC)

• One of the most common and powerful check
• k비트 블록의 경우, transmitter는 (n-k) bit sequence, FCS(프레임 검사 시퀀스)를 만든다
• 미리 정해진 숫자(p)로 정확히 나눌 수 있는 n비트 프레임 전송
Transmit n-bit frame which is exactly divisible by some predetermined number (p)

• Receiver divides the frame by that number
 나머지가 없으면 no error 

• Implementation methods:
 Modulo 2 arithmetic
 Polynomials
 Digital logic

CRC - Implementation (Modulo 2 Arithmetic)

 Binary addition with no carries (XOR)
 Append (n- k ) 0’s at the end of data Divide the result by P and the remainder is FCS

ex) D=110101 , P=1101 , F(FCS)=?

 

 

CRC - Implementation (Polynomials)

 Express all values as polynomials in a dummy variable X, with binary coefficients
 CRC-12: transmission of streams of 6-bit characters
CRC-16 (CRC-ANSI): for 8-bit characters in US
CRC-CCITT: for 8-bit characters in Europe
CRC-32 (IEEE-802): Point-to-point synchronous transmission, IEEE 802 LAN

ex) D= 110101 -> D(x) = x^5 + x^4 + x^2 + 1
ex) P= 1011 -> P(x) = x^3 + x^1 + 1

 

CRC - Implementation (Digital Logic)

 Number of shift registers: length of FCS
 Number of XOR gates: (number of 1’s in P ) – 1
 Insert XOR gate before the i -th register where i is the bit position whose value is 1
 At the receiver, the same logic is used

 

Error Correction

• 발견된 오류를 수정하려면 일반적으로 데이터 블록을 다시 전송해야 한다

• 무선(wireless) application에 적합하지 않음
 높은 비트 오류율 Bit error rate is high
 많은 재전송을 유발 Cause lots of retransmissions
 propagation이 프레임 전송 시간과 비교하여 매우 길 수 있다
Propagation delay can be very long (satellite) compared with frame transmission time
 오류 프레임과 많은 후속 프레임이 재전송될 수 있다
May result in retransmission of frame in error plus many subsequent frames

• Need to correct errors on basis of bits received

 

Error Correction Process Diagram

 

• Each k- bit block is mapped into an n- bit block (n >k) called codeword, using forward error correction (FEC) encoder
• Codeword is sent (subject to impairments)
• Received bit string is similar to transmitted but may contain errors

• Received codeword is passed to FEC decoder
 If no errors, original data block output
 Some error patterns can be detected and corrected
 Some error patterns can be detected but not corrected
 Some (rare) error patterns are not detected
 Results in incorrect data output from FEC decoder

 

Working of Error Correction

• Add redundancy(중복성) to transmitted message
• 특정 수준의 오류율에도 불구하고 원본 메시지를 추론할 수 있다.
Can deduce original message, even in face of certain level of error rate

• E.g. block error correction code
 In general, add (n – k )- bits to end of block
 > Gives n - bit block (codeword)
 > All of original k- bits are included in codeword > 그대로 남아있음
 일부 FEC는 k-비트 입력을 n-비트 codeword에 매핑하여 원래 k-비트가 나타나지 않도록 한다
Some FEC map k- bit input into n- bit codeword such that original k- bits do not appear  > 완전히 사라짐

* single bit error : 에러 어디서 났는지 찾을 수 있음 & correct 가능
* single이 아니면 detect는 가능하지만 correct는 불가능

 

Line Configuration

• Topology
 Physical arrangement of stations on medium
 Point-to-point: two stations
 Multipoint: computer and terminals, LAN

• Duplex
 Half duplex (무전기)
 > Only one station may transmit at a time
 >Two-way alternate; one-lane, two-way bridge
 > Requires one data path
 Full duplex
 > Simultaneous transmission and reception between two stations
 > Two-way simultaneous; two-lane, two-way bridge
 > Requires two data paths

 

Traditional Configurations