요약

1이 올 때마다 신호를 뒤집는 NRZI는 0이 길게 이어질 때만 박자를 잃는다. 그렇다면 보내기 전에 데이터를 0이 길게 이어지지 않는 모양으로 바꿔 두면 된다. 4B/5B는 데이터 4비트마다 정해 둔 5비트 부호로 바꾼 뒤 NRZI로 보낸다. 그러면 0은 많아야 세 개까지만 이어진다. 4비트를 보내려고 5비트를 쓰므로 효율은 80%로, 비트마다 신호를 두 번까지 바꾸는 맨체스터의 50%보다 높다.

예시로 보기

데이터에 0이 1,000개 이어지면 NRZI 신호는 1,000칸 넘게 한 번도 바뀌지 않는다. 보낼 데이터는 우리가 고를 수 없다. 사용자가 0으로 가득 찬 파일을 보내면 그대로 보내야 한다. 대신 데이터를 보내기 전에, 0이 길게 이어지지 않는 다른 비트열로 바꿔 둘 수는 있다. 받는 쪽이 다시 원래 데이터로 되돌릴 수만 있으면 된다.

표를 읽는 법

아래 ‘정의’의 표가 바꾸는 규칙 전부다. 데이터를 앞에서부터 4비트씩 자른다. 자른 4비트를 표의 “4비트 데이터” 칸에서 찾고, 같은 줄의 “5비트 부호”로 바꾼다. 표는 두 덩어리로 나뉘어 있다. 왼쪽 덩어리가 0000~0111, 오른쪽 덩어리가 1000~1111이다.

데이터 0010 0001을 보낸다. 0010은 왼쪽 덩어리의 셋째 줄에 있고, 부호는 10100이다. 0001은 둘째 줄에 있고, 부호는 01001이다. 두 부호를 차례로 이어 붙이면 10비트 1010001001이 된다. 4비트 두 개(8비트)가 5비트 두 개(10비트)로 늘었다.

이어 붙인 곳에서 0이 세 개

그림

그림의 위 줄이 이어 붙인 부호 비트 10개다. 가운데 굵은 세로선이 부호 경계다. 왼쪽 다섯 칸이 0010의 부호, 오른쪽 다섯 칸이 0001의 부호다.

칠한 세 칸이 0이 가장 길게 이어진 곳이다. 첫 부호 10100의 끝 0 두 개와, 다음 부호 01001의 앞 0 하나가 경계를 사이에 두고 붙었다. 부호 하나만 보면 0은 두 개까지만 이어지는데, 두 부호를 이으면 세 개가 된다. 이것이 가장 나쁜 경우다. 부호를 고를 때 “앞에는 0이 1개까지, 뒤에는 0이 2개까지”만 오게 했기 때문이다. 뒤 2개와 앞 1개를 더한 3개보다 길게 붙을 수 없다.

아래 줄은 이 10비트를 NRZI(처음 낮음)로 보낸 신호다. 왼쪽부터 따라간다. 1번째 칸(1)의 한가운데에서 올라간다. 2번째 칸(0)은 그대로 높다. 3번째 칸(1)의 한가운데에서 내려간다. 4~6번째 칸(0, 0, 0)은 그대로 낮다. 7번째 칸(1)의 한가운데에서 다시 올라간다. 그 뒤 8·9번째 칸(0, 0)은 높은 채로 있다가, 10번째 칸(1)의 한가운데에서 내려간다1.

칠한 곳이 신호가 바뀌지 않는 가장 긴 구간이다. 3번째 칸의 한가운데부터 7번째 칸의 한가운데까지다.

어? 0이 세 개면 3비트 폭 아닌가? NRZI는 1인 칸의 한가운데에서만 바뀐다. 그래서 평평한 구간은 언제나 “앞의 1이 뒤집힌 한가운데”에서 시작해 “다음 1이 뒤집히는 한가운데”에서 끝난다. 길이는 앞 1의 뒤 절반(반 칸), 사이의 0 세 칸, 다음 1의 앞 절반(반 칸)을 더한 \(\tfrac12 + 3 + \tfrac12 = 4\)비트 폭이다. 그림 아래의 화살표 세 개가 이 세 조각이다. 0이 \(z\)개 이어지면 평평한 길이는 \(z + 1\)비트 폭이고, 4B/5B에서는 \(z \le 3\)이니 길어야 4비트 폭이다2.

받는 쪽은 이 4비트 폭 동안만 자기 시계로 버티면 된다. 그다음 1에서 신호가 바뀌고, 그 순간 다시 박자를 맞춘다. 데이터를 그냥 NRZI로 보냈다면 0이 몇 개 이어질지 몰라 버텨야 할 시간에 끝이 없었다. 4B/5B는 그 시간에 상한을 만든다.

검증: 16개 부호가 조건을 지킴, 두·세 부호를 어떻게 이어도 0은 최대 3개, 4~12비트 모든 열에서 되돌리기 일치, 카드 C2 — 42_4b5b_verify.py

정의

데이터를 4비트마다 5비트 부호로 바꾼다. 5비트 부호는 앞에는 0이 1개까지, 뒤에는 0이 2개까지 오도록 골랐다. 그래서 0이 4개 이상 이어질 수 없다. 5비트 부호는 NRZI로 보낸다. 효율은 80%다.

flowchart LR
  subgraph TX["보내는 쪽"]
    direction TB
    A["데이터"] --> B["4비트씩 자름"] --> C["표에서 5비트 부호로"] --> D["NRZI로 신호를 만듦"]
  end
  subgraph RX["받는 쪽"]
    direction TB
    E["NRZI 신호를 비트로"] --> F["5비트씩 자름"] --> G["표를 거꾸로 찾아 4비트로"] --> H["데이터"]
  end
  D -->|"링크"| E

받는 쪽은 보내는 쪽의 세 단계를 거꾸로 밟는다. 0이 길게 이어지지 않는 것은 링크 위를 지나는 5비트 열이다3.

4비트 데이터 5비트 부호 4비트 데이터 5비트 부호
0000 11110 1000 10010
0001 01001 1001 10011
0010 10100 1010 10110
0011 10101 1011 10111
0100 01010 1100 11010
0101 01011 1101 11011
0110 01110 1110 11100
0111 01111 1111 11101

효율은 보내는 비트 중 데이터 비트의 비율이다. \(4/5 = 80\%\)다. 맨체스터는 신호 변화 두 번에 비트 하나를 실어 \(1/2 = 50\%\)다.

숫자로 바꿔 보면 크기가 느껴진다. 데이터를 1초에 100 M비트(100 Mbps) 보내려면, 4비트마다 5비트를 보내므로 선 위로는 1초에 \(100 \times \tfrac54 = 125\) M개의 부호 비트가 지나가야 한다. NRZI는 부호 비트마다 많아야 한 번 바뀌니, 신호 변화도 1초에 많아야 125 M번이다. 같은 100 Mbps를 맨체스터로 보내면 신호가 1초에 최대 200 M번 바뀌어야 한다. 선이 감당해야 할 빠르기가 125와 200이니, 4B/5B 쪽이 열에 여섯 남짓(62.5%)만 요구한다.

5비트 열은 \(2^5 = 32\)가지다. 그중 “앞 0이 1개까지, 뒤 0이 2개까지”를 지키는 것은 21가지이고, 표는 그중 16가지를 데이터에 쓴다. 남는 부호(예: 11111)는 데이터가 아니므로, 회선이 쉬고 있다는 표시 같은 제어 신호로 쓸 수 있다2.

21가지는 앞의 0 개수와 뒤의 0 개수로 나눠 세면 나온다. 앞의 0이 “정확히 0개”이면 첫 비트가 1이고, “정확히 1개”이면 첫 두 비트가 01이다. 뒤도 같은 식이다. 끝 0이 정확히 0개면 끝이 1, 1개면 끝이 10, 2개면 끝이 100이다. 앞과 뒤를 이렇게 정하고 남는 가운데 칸은 0이든 1이든 자유다.

앞쪽 끝 0이 0개 (…1) 끝 0이 1개 (…10) 끝 0이 2개 (…100)
앞 0이 0개 (1…) 1???1: \(2^3 = 8\) 1??10: \(2^2 = 4\) 1?100: \(2^1 = 2\)
앞 0이 1개 (01…) 01??1: \(2^2 = 4\) 01?10: \(2^1 = 2\) 01100: 1

?가 자유로운 칸이고, 자유로운 칸이 \(m\)개면 경우가 \(2^m\)가지다. 여섯 칸을 더하면 \(8 + 4 + 2 + 4 + 2 + 1 = 21\)이다. 표에 쓰지 않은 다섯 개는 01100, 01101, 10001, 11001, 11111이다.

0이 최대 3개인 이유

이어 붙인 비트열에서 0이 이어지는 구간은 두 경우뿐이다2.

  1. 한 부호 안에 있다. 5비트 안에서 앞 0은 1개까지, 뒤 0은 2개까지이고, 표의 16개 부호는 가운데에도 0이 2개를 넘지 않는다. 그래서 2개 이하다. 예: 1000의 부호 10010은 가운데에 0이 두 개 있다.
  2. 부호 경계에 걸친다. 앞 부호의 끝 0(최대 2개)과 뒤 부호의 앞 0(최대 1개)이 붙는다. 합쳐서 3개 이하다. 모든 부호에 1이 적어도 하나 있으므로, 0 구간이 부호 하나를 통째로 건너 세 부호에 걸칠 수는 없다. 예: 11110(0000) 다음 01001(0001)이면 경계에서 0이 \(1 + 1 = 2\)개 붙는다.

어느 경우든 3개 이하다. 10100 다음 01001처럼 실제로 3개가 되는 경우가 있으므로 3이 최댓값이다.

실행 추적

데이터 1011 0000을 보낸다2.

단계 하는 일 결과
1 4비트씩 자른다 1011, 0000
2 표에서 찾는다 10111, 11110
3 이어 붙인다 1011111110
4 NRZI로 보낸다(처음 낮음) 아래 그림의 아래 줄

1단계에서 8비트를 앞에서부터 4비트씩 자르면 1011과 0000이다. 2단계에서 1011은 오른쪽 덩어리의 넷째 줄이라 10111, 0000은 왼쪽 덩어리의 첫 줄이라 11110이다. 3단계에서 차례대로 이으면 10비트 1011111110이다. 원래 데이터에는 0이 네 개(0000) 이어졌지만, 보내는 비트열에는 0이 많아야 하나씩만 있다.

그림

두 줄은 같은 시간축 위에 있다. 위 줄은 데이터 8비트를 4B/5B 없이 그냥 NRZI로 보낸 것이고, 아래 줄은 4B/5B로 바꾼 부호 10비트를 NRZI로 보낸 것이다. 아래 줄의 칸이 더 좁은 것은 같은 시간에 비트를 10개 넣어야 해서다. 부호 비트 하나의 폭은 데이터 비트의 \(8/10 = 0.8\)배다.

위 줄을 보면, 1011까지는 1마다 바뀌다가 4번째 칸(1)의 한가운데에서 올라간 뒤로 0000 동안 높은 채로 멈춘다. 칠한 곳이 그 구간으로, 반 칸과 0 네 칸을 더한 4.5비트 폭이다. 데이터가 여기서 끝나지 않고 0이 더 오면 평평한 구간도 계속 길어진다. 주황 점(신호가 바뀌는 순간)은 세 개뿐이다.

아래 줄은 3번째 부호 비트부터 1이 일곱 개 이어져, 칸마다 한가운데서 뒤집힌다. 1번째 비트의 1까지 더해 주황 점이 여덟 개다. 가장 긴 평평한 곳은 앞쪽의 1 0 1에서 0 하나를 사이에 둔 구간으로, 부호 비트 2개 폭이다. 데이터의 0000이 부호 11110이 되면서 1이 네 개 생겨, 신호를 바꿀 기회를 만든 것이다1.

복잡도

4비트마다 표를 한 번 찾으므로 시간은 \(O(n)\)이다. 표는 16칸이라 하드웨어에서도 작은 회로로 만든다. 보내는 비트는 데이터의 \(5/4\)배다.

활용

  • FDDI(100 Mbps 광 링 네트워크)가 4B/5B와 NRZI를 함께 쓴다. 100 Mbps 이더넷(100BASE-TX)도 4B/5B를 쓰지만, 그 뒤에 NRZI 대신 세 단계 신호(MLT-3)로 보낸다.
  • 4B/5B 혼자서는 클럭 복구를 하지 못한다. 0이 이어지는 것만 막는다. 1에서 신호를 바꾸는 NRZI와 짝을 이뤄야 박자 단서가 생긴다.
  • 흔한 실수: “4B/5B는 맨체스터보다 효율이 1.6배”를 “속도가 1.6배”로 읽는 것. 같은 신호 변화 속도에서 실을 수 있는 데이터가 \(0.8 / 0.5 = 1.6\)배라는 뜻이다.

연결

확인 문제

C1 4B/5B가 5비트 부호를 고른 조건과, 그 결과 이어 붙인 비트열에서 0이 최대 몇 개까지 이어지는지 쓰라. 효율은?

답: 앞에는 0이 1개까지, 뒤에는 0이 2개까지 오는 부호만 골랐다. 그래서 이어 붙여도 0은 최대 3개 이어진다(뒤 2개 + 앞 1개). 효율은 \(4/5 = 80\%\)다.

C2 데이터 0000 0000을 4B/5B로 바꾼 비트열을 쓰라. NRZ로 그냥 보낼 때와 비교해 무엇이 달라졌나?

답: 11110 11110. NRZ로 그냥 보내면 신호가 8비트 내내 낮은 채로 평평하다. 4B/5B로 바꾸면 1이 여덟 개 생겨 NRZI 신호가 자주 바뀐다. 평평한 구간은 가운데 0 하나 근처(2비트 폭)뿐이다.

C3 표의 부호를 어떤 순서로 이어 붙여도 0이 4개 이상 이어지지 않는 이유를 대라.

답: 0 구간은 한 부호 안에 있거나 두 부호의 경계에 걸친다. 부호 안에서는 2개 이하다. 경계에서는 앞 부호의 끝 0(2개 이하)과 뒤 부호의 앞 0(1개 이하)이 붙어 3개 이하다. 모든 부호에 1이 있어서 0 구간이 부호 하나를 통째로 넘어갈 수 없다.

C4 4B/5B를 NRZI와 함께 쓰는 이유를 한 문장으로 쓰라.

답: NRZI는 1마다 신호를 바꿔 1이 이어져도 박자를 지키지만 0이 이어지면 박자를 잃으므로, 4B/5B로 0이 3개 넘게 이어지지 않게 미리 바꿔 NRZI의 약점을 막는다.

  1. 42_4b5b_plot.py로 그렸고, 그림 1의 부호 1010001001, 경계에 걸친 0 세 개(4~6번째 비트), NRZI(처음 낮음)의 가장 긴 평평한 구간(3번째 칸 한가운데~7번째 칸 한가운데, 4비트 폭), 그림 2의 부호 1011111110, 위 줄의 평평한 구간 4.5비트 폭과 변화 3번, 아래 줄의 가장 긴 평평 2비트 폭과 변화 8번을 같은 코드로 확인했다. ↩ ↩2

  2. 검증 코드로 모든 경우를 확인했다. 남는 부호를 제어 신호로 쓰는 것은 Peterson & Davie, Computer Networks: A Systems Approach, 2.2절의 설명이다(11111은 회선이 쉬는 동안 보낸다). ↩ ↩2 ↩3 ↩4

  3. 받는 쪽 단계는 보내는 쪽을 거꾸로 한 것이고, 검증 코드의 되돌리기로 확인했다. ↩