블록 부호 (Block Code)

코딩 이론에서 알파벳 A와 길이(블록 크기) n이 주어지면, A에서 n개를 골라 만든 모든 시퀀스의 집합을 Aⁿ으로 나타내며, 블록 부호(블록 코드)는 이 집합에서 고른 코드워드들로 메시지를 고정 길이 블록 단위로 인코딩하는 방식입니다. 블록 크기가 n비트이면 2ⁿ개의 서로 다른 시퀀스, 즉 “블록 값”이 나올 수 있습니다. (n,k) 블록 코드는 n비트 코드워드로 최대 2^k개의 서로 다른 메시지(k비트)를 나타냅니다. 따라서 64비트 블록 암호는 보통 평문 64비트를 암호문 64비트로 인코딩하는 단순한 (64,64) 코드로 동작합니다. 그러나 입력 비트 중 16비트를 다른 용도로 예약하면 평문 48비트를 암호문 64비트로 확장하는 셈이므로 (64,48) 코드가 됩니다.

주요 용어

• 알파벳 (A): 사용할 수 있는 기호의 집합입니다. 컴퓨터에서는 보통 비트(0과 1)를 씁니다.
• 블록 크기 (n): 각 코드워드의 길이, 즉 함께 묶이는 기호의 수입니다. 8비트 묶음은 흔히 바이트라고 합니다.
• 코드워드: 부호에 속하는 각 n비트 시퀀스입니다. 예를 들어 블록 크기가 2이면 가능한 시퀀스는 00, 01, 10, 11의 4개이고, 블록 크기가 3이면 000부터 111까지 8개입니다.
• 메시지 길이 (k): 코드워드 하나가 실어 나르는 정보의 비트 수입니다. n − k비트는 오류 검출·정정이나 제어 정보 같은 다른 용도에 쓰입니다.

예: 해밍 (7,4) 부호

오류 정정 부호의 고전적인 예는 해밍 (7,4) 부호입니다. 4비트 메시지에 패리티 비트 3개를 덧붙여 7비트 코드워드를 만듭니다. 가능한 7비트 시퀀스는 2⁷ = 128개이지만, 그중 메시지 2⁴ = 16개에 대응하는 16개만 코드워드로 씁니다. 서로 다른 두 코드워드는 적어도 3비트가 다르므로(최소 거리 3), 전송 중 1비트가 뒤집혀도 수신자는 가장 가까운 코드워드를 찾아 원래 메시지를 복구할 수 있습니다.

평문에서 암호문으로: 블록 암호와의 관계

블록 암호도 블록 코드의 관점에서 볼 수 있습니다. DES·3DES 같은 64비트 블록 암호는 64비트 평문을 64비트 암호문으로 변환하는 (64,64) 코드이고, 현재 주로 쓰이는 AES는 128비트 블록을 같은 길이의 블록으로 바꾸므로 (128,128) 코드로 볼 수 있습니다.

• (입력): 64비트로 구성된 평문으로 시작합니다.
• (변환): (64,64) 블록 암호로 이 평문을 64비트 길이 그대로 암호문으로 인코딩합니다.
• (유연성): 입력 중 16비트를 오류 검출이나 제어 신호 같은 다른 용도로 예약하면 평문 48비트가 64비트 암호문으로 변환되는 (64,48) 코드가 됩니다. 메시지에 쓸 수 있는 비트는 줄지만 다른 정보를 함께 담을 수 있습니다.

장점

• 단순성: 고정 길이 블록 단위로 처리하므로 구현하고 분석하기 쉽습니다.
• 오류 감지 및 수정: 남는 n − k비트로 데이터 전송과 저장 중의 오류를 감지하고 수정할 수 있습니다.
• 다양한 응용 분야: 통신, 데이터 저장(예: 리드-솔로몬 부호를 쓰는 QR 코드와 저장 매체), 암호 등 여러 분야에서 쓰입니다.

단점

• 작은 데이터의 비효율: 데이터가 블록 크기 n보다 작으면 패딩이 필요해 비효율이 생길 수 있습니다.
• 큰 블록 크기의 복잡성: n이 커질수록 인코딩·디코딩 계산이 무거워질 수 있습니다.
• 지연 시간: 블록이 다 모여야 처리할 수 있으므로, 실시간 응용에서 블록이 크면 지연이 생깁니다.
• 중복 오버헤드: 다른 용도로 비트를 예약할수록 실제 메시지에 쓰는 비율(k/n)이 낮아집니다.