네트워크프로토콜

[네트워크프로토콜] 에러 검출 & 수정(1)

by VICENTE97P4

March 29, 2022, 6:21 p.m.

data는 전송 중에 깨질 수 있습니다.

저번에 배웠던 attenuation, noise, distortion이 원인이 될 수 있죠.

text의 경우는 에러 검사가 필요합니다. 왜냐하면 인간 입장에서 바로 보이니까, 민감하게 반응하는 편이기 때문이죠.

하지만 audio, video 등과 같은 multimedia는 error가 있어도 사람이 잘 인지하지 못합니다.

이 error를 방지하기 위해서 channel coding을 하는데, 이는 data에 redundancy를 추가하는 것입니다.

거기에 error가 있는지 검출하고 수정까지 할 수 있습니다.

Single bit error

data 1bit에 error가 생겨서 0 -> 1 또는 1 -> 0이 되는 경우입니다.

* 코딩이론에 대해 먼저 알아봅시다.

코딩 방식에는 두 가지가 있습니다.

source coding: 압축할 때 많이 사용하는 방식입니다. MPEG, JPEG에 사용됩니다.

audio, video는 중복이 많아서 압축할 것이 많습니다.

channel coding: 에러 검출, 수정에 많이 사용합니다.

error detection -> parity, checksum, CRC 등의 방법이 있습니다.

error correction -> convolutional(전화에 많이 씁니다.), RS(audio, video 저장용으로 씁니다.)

체널 에러의 특성을 보고 channel coding 방식을 선택해야 합니다.

- single bit error가 많은 경우: 유선에서 많이 발생합니다.

BER(bit error rate)가 twisted pair(전화선)에서는 10^-6, 광케이블에서는 10^-9입니다.

전화선에서 error가 훨씬 자주 발생함을 알 수 있습니다.

- burst error가 많은 경우: 무선에서 많이 발생합니다.

burst error는 2개 이상의 error가 한번에 발생하는 경우를 말합니다.

무선이 유선보다 에러에 취약함을 알 수 있습니다.

송신측에서는 generator에서 redundancy를 생성하고, 수신측에서 checker로 error 유무를 확인합니다.

error 유무를 확인할 때 XOR(exclusive or)을 사용합니다.

distance: 두 코드가 몇 bit만큼 다른지를 나타내는 단위입니다. 1개 다르면 1, 2개 다르면 2, 이런 방식입니다.

Block coding

이전까지는 convolutional coding이었고 이동통신에서 많이 쓰는 방식입니다.

block coding은 1bit 단위가 아닌 몇 bits씩 묶어서 처리하는 방식입니다.

data를 k bits씩 쪼갭니다. 이를 datawords라고 합니다. 정확하게는 2^k 를 datawords라고 합니다.

정보 자체는 2^k만큼 담기니까요

각각에 r bits씩 redundancy를 추가합니다.

그렇게 완성된 n bits를 codeword라고 합니다.

정확하게는 2^n을 codeword라고 합니다. 정보가 담기는 양을 따지는 겁니다.

block coding의 전송도입니다.

data word 뒤에 1bit의 parity bit를 추가하는 이분 parity의 경우에는

1bit의 error만 detection할 수 있습니다. 그 이상의 에러는 검출할 수 없고, 수정할 수도 없죠.

redundancy가 많아질 수록 error 검출 능력이 상승하고, correction도 가능해집니다.

01이라는 dataword를 전송한다고 합시다. 그럴 이때 011을 붙여서 01011을 전송했다고 합시다.

그런데 이 data가 깨져서 수신측에서 01001을 수신했다고 합시다.

그럼 table에서 가장 distance가 가까운 애를 선택합니다.

위에서부터 XOR 연산을 합니다.

그럼 distance가 가장 적은 codeword는 01011이 되니 얘를 선택하여 추출합니다.

위 예시에서 사용한 distance를 Hamming distance라고 합니다.

Hamming distance를 구하는 방법은 간단합니다. 그냥 XOR한 후 1의 개수를 새면 됩니다.

이 Hamming distance의 최소값이 detection, correction 능력을 결정합니다.

dmin = s + 1이라는 공식이 있습니다.

Hamming distance의 최소값은 detection 능력(s) + 1과 같다는 의미입니다.

dmin = 2t + 1이라는 공식도 있습니다.

Hamming distance의 최소값은 correction 능력(t)의 2배 + 1과 같다는 의미입니다.

위 두 공식을 이용하여 몇 bit까지 detection과 correction이 가능한지 알 수 있습니다.

Linear block code: 서로 다른 codeword를 XOR 했을 때 생기는 새로운 code를 의미합니다.

block code를 표기할 때 C(n, k)로 합니다. n은 총 code의 크기, k는 dataword의 크기를 의미합니다.

parity를 row 방향 뿐만 아니라 column 방향에서도 붙일 수 있습니다. 즉, 2차원 활용도 가능합니다.

이 경우에는 row에서 못 찾던 error를 column에서 찾을 수도 있습니다.

하지만 row와 column 모두 짝수 개씩 error가 발생하면 detection하지 못합니다.

Hamming code는

n = 2^m - 1 을 따릅니다.

여기서 m은 n = k + r에서 r과 같습니다.

Hamming code는 error correction까지 가능합니다.

어느 부분에서 error가 생겨쓴ㄴ지 syndrome이라는 장치에서 알 수 있습니다.

s0 = b2 + b1 + b0 + q0

s1 = b3 + b2 + b1 + q1

s2 = b1 + b0 + b3 + q2

이런 공식이 있습니다.

이 s0s1s2의 값에 따라 어디에 error가 있는지 알 수 있습니다.

Cyclic code

cyclic code는 block code의 유형입니다.

linear block 코드의 특수한 경우입니다.

CRC가 가장 많이 쓰이는 대표적인 예입니다.

Error detection 방식에는 크게 3가지가 있습니다.

- parity: 비동기 통신 때 사용합니다.(비동기는 통상 근거리에서 사용합니다.)

- CRC: data 통신 때 사용합니다.(동기식 방식이며 HW 단에서 사용합니다. L1/L2 계층)

- checksum: TCP/IP에서 사용합니다.(SW단에서 사용, L3/L4 계층)

더 자세한 이야기는 다음 포스트에 작성하겠습니다.

네트워크프로토콜 26 view 599