Error의 종류

Single bit errors, Burst errors(연속적으로 발생하는 에러)
burst error of length: 연속적으로 발생하는 error 구간

Error Detection

Error Control = Detection + Correction

어떻게 디자인하던지 상관없이 전송된 frame에서 하나 이상의 비트가 변경,
아래는 frame 전송 시 고려해야하는 사항들이다.

• 수신한 bit에 error가 있을 확률 (BER)
• frame이 bit errors 없이 도착할 확률
• error detecting 알고리즘이 사용 중인 경우, frame에 하나 이상의 undetected bit error가 있을 확률
• error detecting 알고리즘이 사용 중인 경우, frame에 하나 이상의 detected bit error가 있고, undetected bit error가 없을 확률

Error Detection 과정

보내고자 하는 data에 error detecting code를 붙여 함께 전송

Parity Check

가장 간단한 error detecting scheme: parity bit를 data 끝에 추가
Even parity: 1의 개수를 even하게 만드는 parity bit
Odd parity: 1의 개수를 odd하게 만드는 parity bit

송신 : 10110 1
수신 : 10100 1
수신한 data의 1의 개수가 even하지 않음, Error detecting!

하지만 error가 발생하는 bit의 수가 짝수개인 경우, error detecting이 불가능

Two-Dimensional Even Parity Scheme

Block-Check로, 2차원으로 error detecting

하지만 행과 열의 변화가 쌍을 이루게 되면, error detecting이 불가능

The Internet Checksum

송신 측의 checksum 계산 결과에 1의 보수를 취한 형태를 data 끝에 추가하고,
수신 측의 checksum verification 수행

error 없는 전송을 위해 transport layer로 전달
상대 transport layer에서 error를 판단할 수 있도록 error check를 위한 정보를 data에 추가
$\rarr$ CRC보다 성능은 낮지만 overhead가 없도록 하는 간단한 방법

Cyclic Redundancy Check (CRC)

가장 powerful한 error-detecting codes
transmitter가 (n-k)bit frame check sequence(FCS)를 생성하여 data 끝에 추가, 전송
수신측은 수신한 frame을 이미 정해진 값으로 divide! $\rarr$ 나머지가 없다면, NO ERROR

CRC 과정

어떻게 n-k bit를 생성하는가
Modulo 2 arithmetic, Polynomials, Digital logic

Division in CRC encoder

보내고자 하는 data를 송,수신측이 모두 알고 있는 Divisor로 나눔(XOR연산)
$\rarr$ 이때, divisor의 bit 수 - 1만큼 보내고자 하는 data를 shifting(즉 0을 붙여줌)
나머지인 Remainder를 보내고자 하는 data 뒤에 붙여줌
$\rarr$ 수신측에서 modulo 연산 시, 나머지가 0이 되지 않으면 무조건 error로 감지

A polynomial to represent a binary word

binary word를 다음과 같은 다항식 표현으로 변환할 수 있다.

Example of Polynomial Division

Standard polynomials

여러 종류가 있지만, Network 종류에 따라 사용

Circuit with Shift Registers for Dividing by the Polynomial

Input을 먼저 다 Output으로 내보낸뒤,
Switch를 변경하여 연산을 수행한 뒷 bit를 Output으로 전송

HW logic으로 가능, SW에서는 연산의 overhead가 발생하기에 간단한 방법을 사용할 필요가 있다.

Forward Error Correction

simple한 방법으로는 재전송이 있다.
하지만 이는 무선 applications에서는 적절하지 않은데,
재전송을 수행해도 또 다시 error가 발생할 가능성이 있고, 재전송의 시간이 높기 때문이다.
따라서 수신한 bits를 기반으로 errors를 correction할 방법이 필요

Codeword
transmission end에서 각 k bit data block은 FEC(Forward Error Correction) encoder를 사용하여 n bit data block으로 매핑된다. (n>k)
이때, error 발생 시 원래 data를 유추할 수 있는 value를 추가

Block Code Principles

Hamming distance

두 n-bit binary sequences에서 각 자리의 bit가 다른 경우의 수
즉, $d(1011, 1001) = 1$ (3번째 자리만 다르기 때문에 1)

Redundancy of the code

원래 data에 비해 추가적인 bit가 얼마나 추가되었는가를 보여주는 식
$(n-k)/k$ (n>k)

Code rate

전체 bits 중 data bits의 비율
$k/n$

Example

k = 2, n = 5

이때, codeword는 valid한 pattern

Invalid Codewords

위 표에서 Invalid Codeword의 경우는 error를 발생, Valid Codeword만이 error를 발생시키지 않는다.

Using XOR

XOR의 특성을 이용하는 방법도 있다.
data를 주우욱 받았을때, 중간의 한 값에 error가 있거나 제대로 수신하지 못한 경우, 다른 나머지 값들과 이들을 XOR한 결과로 빠진 값을 구할 수 있다.

Interleaving

아래의 예시에서, 각 packet은 5개의 chunks로 구성

Compounding high-and-low resolution packets

error나 loss가 발생하더라도 큰 지장이 없도록 한 data를 2개의 packet에 나누어 전송

각 packet은 이전 packet에 전송되었던 정보의 저화질(low) 정보를 함께 전송하므로, 이전의 packet이 전송되지 않았더라도 저화질 정보라도 전송이 가능

고화질만 전송하는 경우는 아예 재생이 불가할테지만, 위 방법으로 저화질도 나누어 전송하여 재생은 가능하도록 한다.

Convolutional Codes

Viterbi algorithm

Convolutional Codes: (n=2, k=1, M=2) Encoder

Trellis