받는 쪽 시계가 보내는 쪽보다 조금 빠르거나 느릴 때, 몇 번째 비트에서 처음 틀리는지와 무엇을 잘못 받는지 계산하는 연습이다. 푸는 틀을 먼저 익히고, 문제 다섯 개를 차례로 푼다. 답은 문제마다 - 답 아래에 있다.

푸는 틀

받는 쪽은 신호가 바뀌는 순간 말고는 칸 경계를 볼 수 없다. 그래서 자기 시계로 “비트 하나가 이만큼 이어진다”고 믿는 폭마다 칸 한가운데라고 생각하는 시각에 높이를 읽는다. 시계가 틀리면 그 읽는 시각이 칸마다 조금씩 밀린다. 밀린 양이 반 칸을 넘는 순간 옆 칸을 읽는다.

1. 단위를 맞춘다. 보내는 쪽 비트 폭을 1로 놓는다. 받는 쪽이 믿는 비트 폭을 \(w\)라 한다. 속도로 주어지면 보내는 속도 \(R_s\)를 받는 쪽이 믿는 속도 \(R_r\)로 나눈다.

\[w = \frac{R_s}{R_r}\]

\(w < 1\)이면 받는 쪽 시계가 빠르고, \(w > 1\)이면 느리다. 빠른 비율은 \(\varepsilon = 1 - w\), 느린 비율은 \(\delta = w - 1\)이다. 예: 1 Mbps를 1.03 Mbps로 믿으면 \(w = 1/1.03 \approx 0.971\)이고 \(\varepsilon \approx 0.029\)다. 0.03이 아니다.

2. 읽는 시각과 읽는 칸을 적는다. 읽기 번호와 칸 번호를 0부터 센다. \(k\)번째 읽기는 시각 \(t_k\)에 하고, 그때 지나가는 보낸 칸은 \(t_k\)의 정수 부분이다.

\[t_k = \left(k + \tfrac12\right) w, \qquad \text{읽는 칸} = \lfloor t_k \rfloor\]

\(\lfloor x \rfloor\)는 \(x\)를 넘지 않는 가장 큰 정수다. 예: \(\lfloor 4.95 \rfloor = 4\).

3. 첫 오류 위치를 식으로 찾는다. 칸 \(k\)의 진짜 한가운데는 \(k + \tfrac12\)다. 받는 쪽은 그보다 \((k + \tfrac12)\varepsilon\)만큼 일찍(빠른 시계) 또는 \((k + \tfrac12)\delta\)만큼 늦게(느린 시계) 읽는다. 이 차이가 반 칸을 넘으면 옆 칸을 읽는다1.

받는 쪽 시계 처음 틀리는 \(k\) 틀리는 모양
빠름 (\(w = 1 - \varepsilon\)) \((k + \tfrac12)\varepsilon > \tfrac12\), 곧 \(k > \dfrac{1}{2\varepsilon} - \dfrac12\) 같은 칸을 두 번 읽음 (비트가 하나 늘어남)
느림 (\(w = 1 + \delta\)) \((k + \tfrac12)\delta \ge \tfrac12\), 곧 \(k \ge \dfrac{1}{2\delta} - \dfrac12\) 칸 하나를 건너뜀 (비트가 하나 빠짐)

부등호가 다른 것은 칸 경계가 왼쪽 칸이 아니라 오른쪽 칸에 들어가기 때문이다. 시각이 정확히 정수 \(m\)이면 칸 \(m\)을 읽는다2.

4. 다시 맞추기가 있으면 같은 높이가 이어지는 길이만 본다. NRZ의 받는 쪽은 신호가 바뀌는 순간을 칸 경계로 다시 잡는다(클럭 복구). 그러면 밀린 양이 0으로 돌아가고, 같은 높이가 \(L\)칸 이어지는 동안만 다시 쌓인다. 빠른 시계에서 틀리지 않는 가장 긴 \(L\)은 대략 다음과 같다.

\[L \le \frac{1}{2\varepsilon} - \frac12\]

5. 끝까지 읽은 결과를 적는다. 받는 쪽은 신호가 이어지는 동안 계속 읽는다. 빠른 시계는 같은 시간에 더 많이 읽어 비트가 늘고, 느린 시계는 덜 읽어 비트가 준다3.

문제

문제 1 · 10% 빠른 시계, 다시 맞추지 않음

110000000011(12비트)을 NRZ로 보낸다. 받는 쪽은 비트 폭을 0.9로 믿고, 칸 경계를 다시 맞추지 않는다. (가) 몇 번째 읽기에서 처음 틀리는가? (나) 받는 쪽이 받은 비트열은?

답

사용 개념. NRZ와 클럭 복구
풀이 전략. 보내는 쪽 비트 폭은 1이고, 받는 쪽이 믿는 폭은 \(w = 0.9\)다. 그래서 받는 쪽 시계가 10% 빠르다(\(\varepsilon = 0.1\)). 먼저 식으로 첫 오류 위치를 구하고, 표를 만들어 확인한다.
① 첫 오류 위치(식). \((k + \tfrac12) \times 0.1 > \tfrac12\)에서 \(k + \tfrac12 > 5\), 곧 \(k > 4.5\)다. 처음 만족하는 정수는 \(k = 5\), 즉 6번째 읽기다.
② 읽는 시각과 칸(표). \(t_k = (k + \tfrac12) \times 0.9\)를 계산한다.

  • \(k\) = 0, 1, 2, 3, 4: 시각 0.45, 1.35, 2.25, 3.15, 4.05 → 칸 0, 1, 2, 3, 4
  • \(k\) = 5: 시각 4.95 → 칸 4 (한 번 더)
  • \(k\) = 6~12: 시각 5.85, 6.75, 7.65, 8.55, 9.45, 10.35, 11.25 → 칸 5~11
    \(k = 4\)와 \(k = 5\)가 둘 다 칸 4를 읽는다. ①의 결과와 같다.
    ③ 받은 비트열. 신호는 시각 12에 끝난다. \(t_{12} = 11.25 < 12\)이고 \(t_{13} = 12.15 \ge 12\)이므로 13번 읽는다. 칸 4의 0을 두 번 읽어 0이 하나 늘었다. 보낸 110000000011(0이 8개)이 받은 1100000000011(0이 9개)이 된다.
    그림
    위쪽은 보낸 신호에 받는 쪽이 읽는 순간(세로선)을 겹친 것이다. 주황 세로선 두 개가 칠한 칸 4 안에 함께 떨어진다. 아래 막대는 읽을 때마다 칸 한가운데보다 일찍 읽은 양이다. 한 번에 0.1칸씩 자라다가 여섯째 막대(시각 4.95, 0.55칸)에서 처음 점선(반 칸)을 넘는다.
    흔한 실수. 받는 쪽이 12번만 읽는다고 보고 110000000001이라고 답하는 것이다. 빠른 시계는 같은 시간에 더 많이 읽는다. 마지막 1이 사라지는 것이 아니라 0이 하나 늘어난다3.

문제 2 · 같은 시계로 다시 맞추면

문제 1과 같은 시계(비트 폭 0.9)인데, 이번에는 신호가 바뀔 때마다 그 순간을 칸 경계로 다시 잡는다. (가) 받은 비트열은? (나) 이 시계로 틀리지 않으려면 같은 높이가 최대 몇 칸까지 이어져도 되는가?

답

풀이 전략. 신호가 바뀌는 곳은 시각 2(1 → 0)와 10(0 → 1)뿐이다. 각 바뀌는 순간부터 읽기 번호 \(j\)를 0으로 새로 센다. 다시 맞춘 순간 \(b\) 뒤의 \(j\)번째 읽기는 \(b + (j + \tfrac12) \times 0.9\)다.
① 처음 두 칸. 시각 0부터 0.45, 1.35에 읽어 칸 0, 1의 1을 읽는다. 다음 읽기(2.25) 전인 시각 2에 신호가 바뀌어 다시 맞춘다.
② 0이 8칸 이어지는 구간. 시각 2부터 2.45, 3.35, 4.25, 5.15, 6.05, 6.95, 7.85, 8.75, 9.65에 읽는다. 6.05와 6.95가 둘 다 칸 6을 읽는다. 이 구간 안의 \(j = 5\)에서 앞당김이 \((5 + \tfrac12) \times 0.1 = 0.55\)로 반 칸을 넘기 때문이다.
③ 끝의 두 칸. 시각 10에 신호가 바뀌어 다시 맞춘다. 10.45, 11.35에 칸 10, 11을 읽는다.
(가) 답. 1100000000011. 0이 하나 늘었다. 문제 1과 같은 결과지만 틀린 자리가 칸 4에서 칸 6으로 늦어졌고, 끝의 1 두 개는 다시 맞춘 덕분에 제 박자로 읽었다.
그림
보라 삼각형이 다시 맞추는 순간이다. 아래 막대가 보라 삼각형을 지날 때마다 0으로 떨어진다. 그래도 0이 8칸 이어지는 동안 쌓인 앞당김이 일곱째 막대에서 반 칸을 넘는다.
(나) 답. 4칸. \(L \le \tfrac{1}{2 \times 0.1} - \tfrac12 = 4.5\)이므로 정수로 4다. 직접 확인하면, 0이 4칸이면 구간 안에서 2.45 … 5.15에 네 번 읽고, 다음 읽기(6.05) 전인 시각 6에 신호가 바뀌어 맞게 읽는다. 0이 5칸이면 다섯째·여섯째 읽기(6.05, 6.95)가 둘 다 칸 6에 떨어진다. 그 뒤에야 시각 7에 신호가 바뀐다4.
이 문제가 말하는 것. 다시 맞추기는 같은 높이가 이어지는 길이에 상한이 있을 때만 쓸모가 있다. NRZ는 데이터에 따라 그 길이가 끝없이 길어질 수 있다. 그래서 신호가 바뀌는 순간을 보장하는 인코딩(맨체스터, 4B/5B)이 필요하다.

문제 3 · 속도로 주어질 때

(가) 보내는 쪽은 1 Mbps로 보내는데, 받는 쪽은 1.03 Mbps로 믿는다. 신호가 한 번도 바뀌지 않으면 몇 번째 읽기에서 처음 틀리는가? 그 순간은 보내기 시작한 지 몇 μs 뒤인가? (나) 두 시계가 100 ppm(백만분의 100) 어긋나고 링크가 100 Mbps면, 신호가 바뀌지 않을 때 몇 비트, 몇 μs 만에 처음 틀리는가?

답

(가) 풀이.

  1. 단위 맞추기. 보내는 쪽 비트 폭은 \(1/(10^6) = 1\) μs다. \(w = R_s / R_r = 1/1.03 = 0.97087\)이다. 받는 쪽 시계가 빠르고, \(\varepsilon = 1 - 1/1.03 = 0.03/1.03 = 0.02913\)이다.
  2. 첫 오류. \(k > \tfrac{1}{2\varepsilon} - \tfrac12 = \tfrac{1.03}{0.06} - \tfrac12 = 17.17 - 0.5 = 16.67\)이므로 \(k = 17\), 즉 18번째 읽기다. 이때 칸 16을 한 번 더 읽는다.
  3. 시각. \(t_{17} = 17.5 \times 0.97087 = 16.99\) μs다. 보내는 쪽 시간으로 약 17 μs 만이다.
    흔한 실수. \(\varepsilon\)을 0.03으로 놓는 것이다. 이 문제는 우연히 같은 \(k\)가 나오지만, 비율이 커지면 답이 달라진다. 빠른 비율은 언제나 \(1 - w\)로 구한다.
    (나) 풀이.
  4. 100 ppm은 \(\varepsilon = 100 / 10^6 = 10^{-4}\)다.
  5. \(k > \tfrac{1}{2 \times 10^{-4}} - \tfrac12 = 5{,}000 - 0.5 = 4{,}999.5\)이므로 \(k = 5{,}000\), 즉 5,001번째 읽기에서 처음 틀린다.
  6. 100 Mbps의 비트 폭은 10 ns다. \(5{,}000.5 \times 10\) ns \(\approx 50\) μs다.
    뜻. 시계 오차가 만분의 1이어도 같은 높이가 약 5,000비트 이어지면 틀린다. 100 Mbps에서 5,000비트는 0.05 ms 만에 지나간다. 이더넷 장비의 시계는 보통 ±100 ppm 안에서 맞추도록 정해져 있다5. 그래서 시계를 잘 만드는 것만으로는 안 되고, 신호가 자주 바뀌게 하는 인코딩으로 계속 다시 맞춘다.
    그림
    가로축은 받는 쪽 시계가 빠른 비율이고, 세로축은 처음 틀리는 읽기 번호다. 두 축 모두 로그 눈금이다. 시계 오차가 10배 작아지면 첫 오류가 약 10배 늦어진다. 점선은 어림값 \(1/(2\varepsilon)\)이고, 오차가 작을수록 실제 값(파란 계단)과 거의 겹친다.

문제 4 · 느린 시계

1111111111110000(1이 12개, 0이 4개)을 NRZ로 보낸다. 받는 쪽은 비트 폭을 1.05로 믿고(5% 느림), 다시 맞추지 않는다. (가) 몇 번째 읽기에서 처음 틀리고, 어떻게 틀리는가? (나) 받은 비트열은?

답

풀이 전략. 느린 시계는 칸 한가운데보다 늦게 읽는다. 늦어진 양 \((k + \tfrac12)\delta\)가 반 칸에 닿으면 다음 칸으로 넘어가 칸 하나를 건너뛴다.
① 첫 오류(식). \(\delta = 0.05\). \((k + \tfrac12) \times 0.05 \ge \tfrac12\)에서 \(k \ge 9.5\), 곧 \(k = 10\), 11번째 읽기다.
② 확인. \(t_9 = 9.5 \times 1.05 = 9.975\)는 칸 9 안이다. \(t_{10} = 10.5 \times 1.05 = 11.025\)는 칸 11 안이다. 칸 10은 아무도 읽지 않는다.
③ 받은 비트열. \(t_k < 16\)인 \(k\)는 0~14로 15번 읽는다. 읽는 칸은 0~9, 11, 12, 13, 14, 15다. 칸 10의 1이 빠져 111111111110000(1이 11개)이 된다.
그림
보라로 칠한 칸 10 안에는 세로선이 하나도 없다. 아래 막대는 칸 한가운데보다 늦게 읽은 양이다. 열한째 막대(시각 11.025)에서 처음 점선을 넘는다.
빠른 시계와의 차이. 빠르면 비트가 늘고(같은 칸 두 번), 느리면 비트가 준다(칸 건너뜀). 읽는 간격이 1보다 짧으면 두 읽기 사이에 칸 경계가 많아야 하나라서 건너뛸 수 없다. 1보다 길면 칸 경계 두 개를 넘을 수 있다1.

문제 5 · 인코딩마다 버틸 수 있는 시계 오차

받는 쪽 시계가 1% 빠르고, 보낼 데이터는 0이 1,000개 이어진 것이다. NRZ, NRZI, 맨체스터, 4B/5B(+NRZI)로 보낼 때 각각 받는 쪽이 틀리는가? 신호가 바뀔 때마다 다시 맞춘다고 한다.

답

풀이 전략. 다시 맞춘 뒤 신호가 평평하게 이어지는 가장 긴 길이를 \(F\)(비트 폭 단위)라 하면, 그동안 쌓이는 어긋남은 약 \(F\varepsilon\)이다. \(F\varepsilon\)이 반 칸을 넘지 않으면 틀리지 않는다. 그래서 각 방식의 가장 긴 평평한 길이부터 구한다6.

  • NRZ. 1,000칸 내내 낮다. \(F = 1{,}000\), \(F \times 1\% = 10\)칸 → 틀림. 51번째 읽기에서 처음.
  • NRZI. 0은 뒤집지 않으므로 1,000칸 내내 평평하다. \(F = 1{,}000\) → 틀림. NRZ와 같다.
  • 맨체스터. 칸마다 가운데서 올라간다. \(F = 1\), \(F \times 1\% = 0.01\)칸 → 맞게 읽음.
  • 4B/5B. 0000이 11110이 되어 부호마다 1이 넷이라 자주 뒤집힌다. 어떤 데이터든 \(F \le 4\)(부호 비트), \(4 \times 1\% = 0.04\)칸 → 맞게 읽음.
    정리.
  • NRZ와 NRZI는 0이 이어지면 다시 맞출 단서가 없다. 그래서 문제 3과 같은 식으로 \(k > \tfrac{1}{0.02} - \tfrac12 = 49.5\), 곧 51번째 읽기에서 처음 틀린다.
  • 맨체스터는 어떤 데이터든 한 칸 안에서 반드시 바뀌므로 어긋남이 쌓일 틈이 없다. 대신 신호를 두 배 빨리 바꿔야 한다(효율 50%).
  • 4B/5B는 0이 3개 넘게 이어지지 않도록 부호를 골라서, 평평한 길이가 부호 비트 4칸을 넘지 않는다. 1% 시계로는 넉넉하고, 어림으로는 \(4\varepsilon < \tfrac12\), 곧 시계 오차가 12.5%보다 작으면 버틴다(효율 80%)6.
    시험 답안(키워드). “NRZ·NRZI: 0 연속 → 신호 변화 없음 → 클럭 복구 불가 → 1% 오차면 약 50비트 만에 오류. 맨체스터: 비트마다 변화 → 항상 복구. 4B/5B: 0 최대 3개 → 평평한 길이 4칸 이하 → 복구.”

변형해 볼 것

  • 문제 1을 \(w = 15/16\)으로 바꾸면 9번째 읽기에서 처음 틀린다. NRZ와 클럭 복구의 예와 같은 결과다.
  • 문제 2에서 시계를 2% 빠르게 하면 같은 높이가 몇 칸까지 버티는가? (\(\tfrac{1}{0.04} - \tfrac12 = 24.5\)이므로 24칸)
  • 문제 4를 다시 맞추기가 있는 경우로 바꾸면 1이 12칸 이어지는 동안 틀리는가? (느린 시계는 \((L - \tfrac12)\delta < \tfrac12\)여야 마지막 칸을 제 칸에서 읽는다. \(\delta = 0.05\)면 \(L < 10.5\)라서 10칸까지 버티고 12칸은 틀린다)
검증: 문제 1~4의 읽는 시각과 칸, 받은 비트열, 첫 오류 위치를 분수로 계산해 확인했다. 다시 맞추기에서 버티는 길이 4칸은 0이 1~11칸 이어지는 경우를 모두 돌려 확인했다. 개념 문서의 결과(\(w = 15/16\)이면 9번째, 1%면 51번째)와도 같다 — 40_clock-drift-practice_plot.py

  1. NRZ와 클럭 복구의 ‘정의’와 ‘증명’. 읽는 칸 \(\lfloor (k + \tfrac12)w \rfloor\), 빠른 시계의 첫 중복 조건, 빠른 시계는 칸을 건너뛰지 않는다는 증명 ↩ ↩2

  2. 느린 시계의 첫 건너뜀 조건과 경계(시각이 정수일 때 오른쪽 칸을 읽음)는 개념 문서의 빠른 시계 증명을 같은 방법으로 뒤집은 것이다. ↩

  3. 이 연습은 받는 쪽이 신호가 끝날 때까지 읽는다고 본다. 그래서 빠른 시계는 비트가 늘어난다. NRZ와 클럭 복구의 예는 보낸 비트와 자리별로 비교하려고 읽는 횟수를 16번으로 고정했다. 그래서 거기서는 마지막 0을 “아무도 읽지 않는다”고 적었다. 두 계산은 첫 오류 위치가 같다. ↩ ↩2

  4. 다시 맞추기의 상한 \(L \le \tfrac{1}{2\varepsilon} - \tfrac12\)은 같은 높이 구간 안의 첫 중복 읽기가 다음 신호 변화보다 먼저 오는지로 얻은 어림식이다. \(\varepsilon = 0.1\)과 \(1/16\)에서 실제 읽기와 맞는 것을 코드로 확인했다. ↩

  5. 이더넷 송신 클럭의 허용 오차 ±100 ppm은 IEEE 802.3의 규정이다. ↩

  6. “가장 긴 평평한 길이 × 시계 오차 < 반 칸”은 NRZI·맨체스터처럼 칸 한가운데서 신호가 바뀌는 방식까지 한 줄로 비교하려는 어림이다. 정확한 값은 받는 쪽이 신호 변화를 어디에 맞추는지에 따라 반 칸쯤 달라진다. 4B/5B의 가장 긴 평평한 길이 4칸은 4B/5B 문서의 계산이다. ↩ ↩2