Error 는 보내고 받음에 있어서 비트가 변해버리는걸 Error 라고 한다.
Single Bit Error , Burst Error(연속적으로 발생하는 Error) 라고 한다.
위 그림을 보면 이해할수 있을것이다.
Error Detection
Error Control 을 한다는건 Error Detection 한 후 Error Correction 한다는 것이다.
Error Control = Error Detection + Error Correction
어찌됐든 어떻게 디자인하던지 전송된 Frame 에서 하나 이상의 Bit가 변경된다.
그래서 Frame 전송시 고려해야하는 사항들이 밑의 그림이다.
- Frame 이 Bit Erorr 없이 도착할 확률
- 수신한 bit 에 Error 가 없을 확률
- Error Detecting 중 Frame에 하나 이상의 Undetected Error 있는 확률
- Error Detecting 중 Frame에 하나이상의 Detected Error 있고, Undetected Error 있는 확률
Error Detection Process
Transmitter 에서 보내는 Data 외에도 추가적인 정보를 보낸다.
그래서 Receiver 쪽에서는 추가적인 정보를 활용해서 Error 가 있는지 없는지를 알수 있는 것이다.
Parity Check
가장 간단한 Error Detecting Scheme
-> Parity bit 를 Data 끝에 추가하는것이다.
Even Parity 란 1의 개수를 Even 하게 만드는 Parity 이고
Odd Parity 란 1의 개수를 Odd 하게 만드는 Parity 이다.
만약 송신이 10110 인데 수신이 10100 이라하면 수신한 Data 의 1의 개수가 Even 하지 않기 때문에 Error Detecting 이 가능한것이다.
이떄 Error 가 발생하는 Bit의 수가 짝수개라면 Error Detecting 이 불가하다.
Two Dimensional Even Parity Scheme
Row 와 Column 을 모두 활용해서 Error Detecting 을 한다.
Row,Column 을 모두 다 봐야하고, Row 에서 확인 못한걸 Column에서 볼수 있따.
The Internet CheckSum
Error 가 있는지 없는지 확인하는 Code 이다.
CRC 는 하드웨어 Network 카드에서 만들어서 보낸다. 그 외에는 소프트웨어로 처리
Example of Internet Checksum
16bit 씩 잘라서 다 더하는것이다.
Carry 가 생기면 그 캐리마저 더해주면 되는것이다.
다 더한것의 결과에 1의 보수를 취해준다.
그리고 이 결과를 Frame Check Sequence 라고 한다.
Cyclic Redundancy Check(CRC)
가장 Powrful 한 Error Detecting Codes 이다.
Transmitter 가 Data 에 (N-K) bit 를 붙인다.
Receiber 는 Frame 을 약속한 Divisor 로 나눈다.
나머지가 없다면 Error 가 없는것으로 확인.
CRC Process
Modulo 2 arithmetic, Polynomials , Digital Logic
Division in CRC encoder
보내고자 하는 Data 를 송,수신측이 모두 알고있는 Divisor 로 나눈다.
Dividend 에는 (Divisor bit -1) 개의 0을 붙여준다
ex) Divisor 가 4bit 임으로 Dividend 에는 3개의 0을 붙여준다.
이말은 Data Shifting 을 해준다는 말.
그렇게 Division 을 하다 Remainder 를 보내고자하는 데이터의 뒤에 붙여주는것이다.
여기서는 110 이 remainder 로 나왔는데
보내고자하는 데이터 1001 에 110 을 붙여 1001110 이 CodeWord 가 되는것이다.
하지만 만약 나머지가 0이 되지않는다면 Error 이다.
Division in CRC Decoder
그럼 만약 1001110 을 가지고 송,수신측이 미리 알고있던 1011 이라는 Divisor 로 Division 을 하게 된다면 다시 원래의 값인 0000 이 나와야 정상일것이다.
하지만 만약 Corrupted 값인 1000110 을 가지고 1011 인 Divisor 로 Division 을 한다면 zero 가 나오지 않아서 오류 인것이다.
Divison Example
그래서 만약 1010001101 이라는 데이터를 보낼려 하는 예시를 보자
송,수신 둘다 알고있는 110101 Divisor 를 가지고 Encoding 을 해야한다.
먼저 Divisor 의 bit가 6bit 이기에 보내고자 하는 Data 에 5개의 0 을 붙여준다.
그리고 Divison 을 하남는 Bit 가 N-1 Bit 가 된다면 종료한다.
나머지가 어떤 값이라도 생기면 Error 이다
Polynomial to represent a binary word
이진수 표현을 다항식으로 표현한다.
1000011 이면 x 의 6제곱 + x + 1 을 뜻한다.
Standard Polynomials
네트워크의 종류,상태에 따라 선택해서 사용
Circut with Shift Registers for Dividing by the Polynomial
Input을 먼저 다 Output 으로 내보낸다
그리고 Switch 연산 후 첫 Bit 를 Output 으로 전송한다.
Foward Error Correction
그전에는 Error Detecting 에 대해 배웠다, 그리고 Error Correction 에 대해 배운다.
첫번째로는 retransmission 으로 다시 보내는 것이 있다.
다시 보내는 재전송 기법인데 무선에서는 적합하지 않다.
또 오류일 가능성이 높고, 재전송하는데도 시간이 오래 걸린다.
그래서 수신한 Bit 를 가지고 Correction 하는 방법을 찾아야함.
자신이 어디가 오류인지만 알면 그부분만 바꾸면 되기 때문
Codeword란 K<N 일떄 K bit 가 N bit 로 바뀌는것을 말한다.
만약 K 가 4 bit 이고 N 이 5bit 라면 32개를 매핑해서 전송하는것.
Block Code Principles
Hamming distance
만약 v1 이 1011 이고 v2 가 1001 이라하면 동일한 인덱스에서 다른 bit 수를 말한다.
여기선 다른 비트수가 1개 이기 때문에 hamming distance 는 1 이다.
Redundancy of the code
얼만큼의 Bit 가 추가 되었는가를 뜻한다.
Code rate
전체 Bit 중 data bits의 비율이다.
Example
k 가 2 이고 n 이 5 일때 예시이다.
Codeword 는 Valid 한 pattern 이다.
이건 Invalid 한 code 들이다.
Using XOR
Excluxive Or 를 사용하는 방법이다.
R 을 전체를 XOR 한 결과라 하자.
그러면
Pi 는 전체에서 Pi를 뺴고 R 을 넣은뒤 전체 XOR 한 결과와 같을것이다.
10개를 보냈는데 각각을 XOR로 보낸다.
10개중 하나가 못왔더라도 그 Pi를 제외한 모든 값을 XOR 하면 된다.
Interleaving
한개 한개를 Data chunk 라고 한다.
그리고 Chunk 가 모여있는걸 Packet 이라 한다.
이 Packet 들이모여 Packet 단위로 보내진다.
만약 전송되다가 Packet 이 사라지면 데이터 손실이 크다
예시로 Video 였다면 잘보여지다가 뚝 끊기도 다시 보여질것이다.
그래서 Row로 묶기보단 Col 로 묶어서 데이터 손실을 최소화 하는 방식이다.
Compounding high and low resolution packet
Error 또는 packet loss가 발생하더라도 데이터 손실을 최소화하기 위해 High resolution, Low resolution 2개의 data를 packet에 나누어 전송하는 방법이다.
-> 각각의 packet은 이전 packet에 전송되었던 정보의 Low-resolution 정보를 함께 전송한다.
-> packet loss 경우 저화질 정보라도 전송이 가능하다.
( 태곤 감사)
Convolutional Codes
viterbi algorithm
n 이 2 이고 k 가 1 이고 M 이 2 인 Encoder 이다.
State Diagram
Tree Diagram
Trellis
솔직히 뒷부분 Colvolutional 모르겠음 애들이랑 같이 얘기해봐야할듯.
