2023 중등임용 기술 디지털논리회로 전공B 7번 CRC 오류 검출과 FCS 기출문제 풀이
2023학년도 중등교사 임용시험 · 기술
다음은 데이터 링크 계층(data link layer)의 기능 중 오류 검출(error detection)에 대해 교수와 학생이 나눈 대화이다. <조건>을 고려하여 <작성 방법>에 따라 순서대로 서술하시오.
㈌, ㈍, ㈎에 해당하는 비트열
교수 : 순환 중복 검사(CRC: Cyclic Redundancy Check)는 전송 데이터의 오류를 검출하는 방식 중 하나입니다.
학생 : 그럼 CRC로 오류를 검출하기 위해 데이터 송신 측에서는 무엇을 보내나요?
교수 : 송신 측에서는 데이터와 FCS(Frame Check Sequence)로 구성된 프레임을 전송합니다. 이때 전송 데이터를 생성 다항식으로 나누어 FCS를 구하고, 이를 전송 데이터에 추가하여 전송하게 됩니다. 예를 들어, 데이터 비트열 110010을 송신할 때, 생성 다항식이 G(x) = x³ + x + 1인 경우 제수(divisor)는 ㈌이/가 됩니다. 이 제수로 데이터 비트열을 나누면 ㈍(이)라는 FCS를 구할 수 있습니다. 결과적으로 송신 측에서는 110010과 ㈍을/를 결합한 프레임을 전송하게 됩니다. 또 다른 예로, 동일한 비트열을 전송할 때 생성 다항식이 G(x) = x⁴ + x + 1이라면 ㈎(이)라는 FCS를 구할 수 있습니다.
학생 : 수신 측에서는 프레임을 수신한 후 무엇을 하나요?
교수 : 수신 측 검사기에서는 수신 프레임에 ㈏ 오류가 있는지를 확인합니다.
◦ CRC 계산에서 사용하는 연산은 아래의 모듈로-2(modulo-2) 연산을 사용할 것. (단, 모듈로-2 연산은 XOR 연산과 동일함.)
0 ⊕ 0 = 0 0 ⊕ 1 = 1 1 ⊕ 0 = 1 1 ⊕ 1 = 0
◦ 비트열의 왼쪽 첫 번째 비트를 MSB(Most Significant Bit)로 가정할 것.
◦ 괄호 안의 ㈌, ㈍, ㈎에 해당하는 비트열을 순서대로 제시할 것.
◦ 밑줄 친 ㈏의 확인 방법을 서술할 것.
모범답안과 해설 보기
㈌ 1011 ㈍ 101 ㈎ 1001
① 먼저 생성 다항식을 비트열로 옮깁니다. 최고차항부터 상수항까지 모든 차수를 빠짐없이 늘어놓고 항이 있으면 1, 없으면 0을 적습니다. G(x) = x³ + x + 1은 x³, x², x¹, x⁰ 자리에 각각 1, 0, 1, 1이 오므로 제수는 1011이고, 이것이 ㈌입니다. x² 항이 없다는 이유로 자리를 빼먹고 111로 적는 것이 가장 흔한 실수입니다.
② 다음은 데이터 뒤에 0을 몇 개 붙일지 정하는 일입니다. FCS의 길이는 제수의 비트 수보다 하나 적고, 이는 곧 생성 다항식의 최고 차수와 같습니다. G(x)의 최고 차수가 3이므로 0을 세 개 붙여 110010000을 만든 뒤 1011로 나눕니다.
| 생성 다항식 G(x) | 제수 | 붙이는 0 | FCS |
|---|---|---|---|
| x³ + x + 1 | 1011 ( ㈌ ) | 3개 | 101 ( ㈍ ) |
| x⁴ + x + 1 | 10011 | 4개 | 1001 ( ㈎ ) |
③ 나눗셈은 보통의 뺄셈이 아니라 XOR로 합니다. 자리 내림이 없으므로 자리마다 같으면 0, 다르면 1을 적으면 됩니다. 마지막에 남은 세 자리 101이 FCS이고, 이것이 ㈍입니다. 송신 프레임은 데이터에 FCS를 이어 붙인 110010101이 됩니다.
㈍ 110010000 ÷ 1011 (모듈로-2)
110010000
1011
─────────
11110000
1011
────────
1000000
1011
───────
011000
1011
─────
1110
1011
────
101④ ㈎은 제수만 바뀔 뿐 방법이 같습니다. G(x) = x⁴ + x + 1은 x⁴, x³, x², x¹, x⁰ 자리에 1, 0, 0, 1, 1이 오므로 제수가 10011이고, 최고 차수가 4이므로 0을 네 개 붙여 1100100000을 나눕니다.
㈎ 1100100000 ÷ 10011 (모듈로-2)
1100100000
10011
──────────
101000000
10011
─────────
01110000
10011
───────
111100
10011
──────
11010
10011
─────
1001⑤ 남은 네 자리 1001이 FCS이고, 이것이 ㈎입니다. 제수가 한 자리 길어지면 FCS도 한 자리 길어진다는 점을 두 계산을 나란히 놓고 확인해 두면 좋습니다.
검산 110010101 ÷ 1011 → 나머지 000
110010101
1011
─────────
11110101
1011
────────
1000101
1011
───────
011101
1011
─────
1011
1011
────
000키워드데이터통신오류검출CRC생성다항식모듈로2나눗셈
수신 프레임의 오류 확인 방법
모범답안과 해설 보기
수신한 프레임 전체(데이터 + FCS)를 송신 측이 쓴 것과 같은 제수로 모듈로-2 나눗셈한다. 그 나머지가 0이면 오류가 없는 것으로, 0이 아니면 오류가 있는 것으로 판정한다.
① 나머지가 0이 되는 까닭은 송신 측이 프레임을 그렇게 만들었기 때문입니다. 데이터 뒤에 0을 붙인 수를 제수로 나누어 나머지를 구한 뒤, 그 나머지를 붙인 자리에 채워 넣었으므로 프레임은 제수로 나누어 떨어지는 수가 됩니다. 전송 중에 비트가 하나도 바뀌지 않았다면 수신 측에서도 나머지가 0으로 나옵니다.
② 수신 측은 FCS를 따로 떼어 다시 계산해 견줄 필요가 없습니다. 데이터와 FCS를 이어 붙인 채로 한 번 나누어 나머지만 보면 되므로 검사기 구조가 단순해집니다. 실제 하드웨어에서는 이 나눗셈을 시프트 레지스터와 XOR 게이트로 구현합니다.
③ 다만 CRC는 오류를 찾아낼 뿐 고치지는 못합니다. 오류가 있음을 알면 재전송을 요청해야 합니다. 또한 바뀐 비트의 형태가 우연히 제수의 배수와 같아지면 나머지가 0으로 나와 오류를 놓칠 수 있는데, 생성 다항식을 잘 고르면 이런 경우가 매우 드물어집니다.
모듈로-2 나눗셈에서 몫은 쓰지 않습니다. 필요한 것은 나머지뿐입니다.
키워드데이터통신FCS나머지검사재전송요청검출한계
댓글
댓글 쓰기