오류 검출과 교정(Error Detection and Correction)

Error Detection and Correction

1. Types of Errors

• The term of single bit error means that only 1 bit of given data is changed
• The term burst error means 2 or more bits in the data have changed

2. Block coding

• Divided message into block, each of k-bits, called dataword
• Add r redundant bits to each block to make the length n=k+r
• The resulting n-bit blocks are called codeword

Block codeing

3. Hamming distance

• The Hamming distance between two word is the number of differences between the corresponding bits. d(00000, 01101) = 3
• The minimum Hamming distance is the smallest Hamming distance beetween all possible pairs of codewords.
  • C = {0000,1010,0101,1111}
    d(0000,1010) = 2, d(0000,0101) = 2, d(0000,1111) = 4, d(1010,0101) = 4,
    d(1010,1111) = 2, d(0101,1111) = 2
  • therefore, d min = 2

4. Parity-Check code

• k-bit dataword is changed to n-bit codeword where n = k + 1
• The extra bit, called parity bit, is selected to make the total number of 1s in the codeword even

5. CRC (Cycling Redundancy Check)

• used in networks such as LAN or WAN

아래의 동작방식을 보면 바로 이해가 될거에요

임의의 나누는 수를 선정합니다.
Divisor : 11101

임의의 데이터 워드를 선정합니다.
Data word : 1011111001

나누는 수의 길이가 5 이므로 0을 4 번 패딩합니다.

CRC 연산을 진행합니다
10111110010000 ⊕ 11101 = 1010110010000
1010110010000 ⊕ 11101 = 100010010000
100010010000 ⊕ 11101 = 11000010000
11000010000 ⊕ 11101 = 0101010000
MSB가 0 이므로 연산을 넘어갑니다.
101010000 ⊕ 11101 = 10000000
10000000 ⊕ 11101 = 1101000
1101000 ⊕ 11101 = 011100
MSB가 0 이므로 연산을 넘어갑니다.
11100 ⊕ 11101 = 0001

CRC는 0001 입니다.

수신자는 코드워드를 수신합니다.

같은 방식으로 나누어 오류를 검출합니다.

CRC 연산을 진행합니다
10111110010001 ⊕ 11101 = 1010110010001
1010110010001 ⊕ 11101 = 100010010001
100010010001 ⊕ 11101 = 11000010001
11000010001 ⊕ 11101 = 0101010001
MSB가 0 이므로 연산을 넘어갑니다.
101010001 ⊕ 11101 = 10000001
10000001 ⊕ 11101 = 1101001
1101001 ⊕ 11101 = 011101
MSB가 0 이므로 연산을 넘어갑니다.
11101 ⊕ 11101 = 0000

나머지 : 0000

나머지가 0 입니다. 에러가 발생하지 않았습니다.

 

6. Checksum

Sender

1. The message is divided intol 6-bit words
2. The value of the checksum word is initially set to zero.
3. AII words includine the checksum are added using one's complement addition.
4. The sum is complemented and becomes thechecksum.
5. The checksum is sent with the data.

Receiver

1. The message and the checksum are received
2. The message is divided intol 6-bit words.
3. AII words are added using one's complement addition.
4. The sum is complemented and becomes the new checksum.
5. If the value of the checksum is 0. the message is accepted ;otherwlse, it is rected.

 

임의의 난수 5개를 생성합니다. [21, 50, 30, 44, 31]

비트의 길이가 모두 6 이하입니다. Checksum의 길이는 6 입니다.

값을 모두 더합니다.
합계 : 176
이진값 : 10110000

6 비트 Checksum을 생성합니다.
Checksum : 110010
Checksum에 보수를 취합니다. 001101

해당 값을 위의 데이터와 함께 전송합니다. [21, 50, 30, 44, 31, 13]

수신측은 전달받은 데이터를 모두 더합니다.
합계 : 189
이진값 : 10111101

6 비트로 만듭니다. 111111
보수를 취합니다. 000000

Calculated Checksum이 0입니다. 오류가 발생하지 않았습니다.