[네트워크프로토콜] 에러 검출 & 수정(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
1e4t6KFL
Updated: Feb. 22, 2025, 5:29 p.m.
*1
Updated: Feb. 22, 2025, 5:29 p.m.
*1
Updated: Feb. 22, 2025, 5:29 p.m.
*1
Updated: Feb. 22, 2025, 5:29 p.m.
*1
Updated: Feb. 22, 2025, 5:29 p.m.
-1 OR 2+160-160-1=0+0+0+1
Updated: Feb. 22, 2025, 5:29 p.m.
-1 OR 3+160-160-1=0+0+0+1
Updated: Feb. 22, 2025, 5:29 p.m.
*if(now()=sysdate(),sleep(15),0)
Updated: Feb. 22, 2025, 5:29 p.m.
0'XOR(
*if(now()=sysdate(),sleep(15),0))XOR'Z
Updated: Feb. 22, 2025, 5:29 p.m.
0"XOR(
*if(now()=sysdate(),sleep(15),0))XOR"Z
Updated: Feb. 22, 2025, 5:29 p.m.
(select(0)from(select(sleep(15)))v)/*'+(select(0)from(select(sleep(15)))v)+'"+(select(0)from(select(sleep(15)))v)+"*/
Updated: Feb. 22, 2025, 5:29 p.m.
-1; waitfor delay '0:0:15' --
Updated: Feb. 22, 2025, 5:29 p.m.
-1); waitfor delay '0:0:15' --
Updated: Feb. 22, 2025, 5:29 p.m.
-1 waitfor delay '0:0:15' --
Updated: Feb. 22, 2025, 5:29 p.m.
buaEcBGa'; waitfor delay '0:0:15' --
Updated: Feb. 22, 2025, 5:29 p.m.
-1 OR 884=(SELECT 884 FROM PG_SLEEP(15))--
Updated: Feb. 22, 2025, 5:29 p.m.
-1) OR 400=(SELECT 400 FROM PG_SLEEP(15))--
Updated: Feb. 22, 2025, 5:29 p.m.
-1)) OR 780=(SELECT 780 FROM PG_SLEEP(15))--
Updated: Feb. 22, 2025, 5:29 p.m.
jLCHtl7s' OR 981=(SELECT 981 FROM PG_SLEEP(15))--
Updated: Feb. 22, 2025, 5:29 p.m.
yVynIVGs') OR 225=(SELECT 225 FROM PG_SLEEP(15))--
Updated: Feb. 22, 2025, 5:29 p.m.
8W0s2UB4')) OR 456=(SELECT 456 FROM PG_SLEEP(15))--
Updated: Feb. 22, 2025, 5:29 p.m.
*DBMS_PIPE.RECEIVE_MESSAGE(CHR(99)||CHR(99)||CHR(99),15)
Updated: Feb. 22, 2025, 5:29 p.m.
'||DBMS_PIPE.RECEIVE_MESSAGE(CHR(98)||CHR(98)||CHR(98),15)||'
Updated: Feb. 22, 2025, 5:29 p.m.
'"
Updated: Feb. 22, 2025, 5:29 p.m.
����%2527%2522\'\"
Updated: Feb. 22, 2025, 5:29 p.m.
@@ZnYR8
Updated: Feb. 22, 2025, 5:29 p.m.