Hsiao Code

개요

Hsiao Code는 메모리 시스템에서 사용하는 SECDED(Single-Error Correction, Double-Error Detection) 코드를 하드웨어 구현에 맞게 구성한 오류 정정 코드입니다. M. Y. Hsiao가 1970년에 제안한 핵심은 확장 Hamming 코드와 같은 오류 보장 수준과 검사 비트 수를 유지하면서, 패리티 검사 행렬의 열을 홀수 가중치(odd weight) 벡터로 선택하는 것입니다. 이 선택은 syndrome을 만드는 XOR 네트워크의 총 입력 수와 배선량을 줄이는 방향으로 작동합니다.

Hsiao Code의 초점은 더 많은 오류를 정정하는 데 있지 않습니다. 기본 구성은 단일 비트 오류를 정정하고 이중 비트 오류를 검출하는 SECDED이며, 데이터 폭과 검사 비트 수에 맞춰 행렬을 최적화합니다. 따라서 Hsiao Code는 DRAM 셀의 물리적 오류를 직접 처리하는 DDR5 on-die ECC와 동일한 기술이 아니라, 메모리 컨트롤러의 side-band ECC 같은 시스템 수준 ECC를 구현하는 코드 설계 선택으로 이해해야 합니다.

그림 1. Hsiao 방식은 각 열의 가중치를 낮춘 패리티 검사 행렬과 syndrome 분류를 이용해 SECDED 디코더의 조합 논리를 줄인다. 그림의 행렬 비트는 72개 열 전체가 아닌 대표 열을 나타낸다.

핵심 개념

SECDED와 코드 파라미터

이 문서에서 H는 이진 유한체 GF(2) 위의 패리티 검사 행렬이고, 수신 코드워드를 r이라고 하겠습니다.

s = H * r^T

코드워드가 유효하면 s = 0입니다. 한 비트 오류가 위치 i에서 발생하면 syndrome은 H의 i번째 열 h_i가 되고, 두 비트 오류가 i, j에서 발생하면 h_i XOR h_j가 됩니다. 따라서 모든 열이 서로 다르면 두 단일 오류가 같은 syndrome으로 합쳐지지 않습니다.

k개의 데이터 비트와 r개의 검사 비트를 사용하는 Hsiao 구성은 총 n = k + r개의 서로 다른 홀수 가중치 열을 필요로 합니다. 길이 r인 이진 벡터 중 홀수 가중치 벡터의 개수는 2^(r-1)이므로 다음 조건을 만족해야 합니다.

k + r <= 2^(r - 1)

64비트 데이터 워드의 경우 r = 8이 처음으로 조건을 만족합니다. r = 7이면 64 + 7 = 71개 열이 필요하지만 홀수 가중치 7비트 벡터는 64개뿐이고, r = 8이면 72비트 코드워드에 128개 후보가 있습니다. 이 때문에 서버 DIMM에서 익숙한 64 data + 8 check = 72 bits 구성이 Hsiao SECDED의 대표 예가 됩니다.

Odd-weight-column 행렬

Hsiao의 패리티 검사 행렬은 다음 조건을 중심으로 설계합니다.

1. 모든 열은 0이 아닌 홀수 가중치 벡터입니다.
2. 모든 열은 서로 다릅니다.
3. 구현 목적에 맞게 가능한 낮은 가중치의 열을 우선 선택합니다.

이 조건이 SECDED 분류를 가능하게 하는 이유는 다음과 같습니다.

• 단일 오류의 syndrome h_i는 홀수 가중치입니다.
• 두 개의 서로 다른 홀수 가중치 열을 XOR한 값은 0이 아닌 짝수 가중치입니다.
• 따라서 syndrome의 홀짝만 확인해도 단일 오류와 이중 오류를 1차로 구분할 수 있습니다.
• 홀수 열 세 개의 XOR는 홀수 가중치이므로 0이 될 수 없습니다. 이는 최소 거리를 4 이상으로 만드는 조건 중 하나입니다.

실제 디코더는 syndrome의 홀짝만 보지 않고, 홀수 syndrome이 H의 어느 열과 일치하는지도 확인합니다. 세 비트 이상 오류는 SECDED의 보장 범위를 벗어나므로, 일치하지 않는 syndrome이나 잘못된 다중 오류 패턴은 uncorrectable로 처리하는 정책이 필요합니다.

72,64 대표 구성의 열 선택

k = 64, r = 8인 경우 후보 열을 가중치가 낮은 순서로 선택하면 대표적인 분포는 다음과 같습니다.

이 표는 특정 상용 컨트롤러의 고정 행렬을 뜻하는 것이 아니라, Hsiao의 minimum odd-weight-column 원리를 보여주는 대표 선택입니다. 동일한 가중치 후보를 어떤 순서로 배치하고 행으로 변환하는지는 데이터 폭, 배치, 타이밍, 검증 방법에 따라 달라질 수 있습니다.

Hsiao Code와 확장 Hamming Code

두 코드는 같은 데이터 폭에 대해 같은 수의 검사 비트를 사용하고 SECDED 기능을 제공할 수 있습니다. 차이는 오류 정정 능력보다 H를 하드웨어에 어떤 모양으로 배치하느냐에 있습니다.

대표적인 72 x 8 행렬의 행렬 1 개수를 단순 비교하면, 확장 Hamming은 표준 패리티 검사 행렬의 전체 패리티 행에 72개 열을 포함할 때 285개가 됩니다. 전체 패리티 비트 자체를 별도 생성 연결로 세지 않는 구현 표기에서는 284개로 나타날 수 있습니다. 위의 minimum-weight Hsiao 선택은 216개이므로 행렬 연결 수 기준 약 24% 차이지만, 실제 게이트 수나 성능이 같은 비율로 개선된다는 뜻은 아닙니다. XOR 트리 구조, 셀 라이브러리, 배선 배치, 파이프라인, 합성 제약이 최종 결과를 결정합니다.

비교/분석

ECC 코드 선택 비교

Hsiao Code는 BCH, Reed-Solomon, LDPC처럼 정정 능력을 확장하는 코드가 아닙니다. 같은 SECDED 보호를 더 짧은 XOR 경로와 적은 연결로 구현하려는 선택이며, 칩 전체 고장이나 버스트 오류에 대한 보호는 별도의 symbol-based ECC와 메모리 인터리빙이 담당합니다.

구현 비용을 보는 지표

Hsiao 행렬을 평가할 때 단순히 열 가중치의 평균만 비교해서는 안 됩니다.

낮은 열 가중치는 총 연결 수를 줄이는 데 유리하지만 모든 행의 fan-in을 자동으로 최소화하지는 않습니다. 따라서 Hsiao Code를 실제 RTL로 옮길 때에는 가중치가 같은 후보 열의 순서를 바꾸고 row balance, 논리 깊이, 배선 혼잡을 함께 평가해야 합니다.

동작 원리

패리티 검사 행렬과 systematic encoding

검사 열 가운데 단위 벡터 8개를 검사 비트에 할당하면 행렬을 다음과 같이 systematic form으로 표현할 수 있습니다.

H = [ A | I_8 ]

여기서 A는 8 x 64 데이터 부분이고 I_8은 검사 비트 부분입니다. 코드워드 c = [D | P]가 H * c^T = 0을 만족해야 하므로, 이진 연산에서는 다음과 같이 검사 비트를 계산할 수 있습니다.

P = A * D^T       (모든 연산은 GF(2)에서 XOR로 수행)

Hsiao 방식의 차이는 이 식의 기능이 아니라 A를 이루는 열을 어떤 odd-weight 후보로 선택하는지에 있습니다. 후보 열을 생성하는 개념적 알고리즘은 다음과 같습니다.

def hsiao_columns(k):
    r = 1
    while k + r > (1 << (r - 1)):
        r += 1

    candidates = [x for x in range(1, 1 << r)
                  if x.bit_count() % 2 == 1]
    candidates.sort(key=lambda x: (x.bit_count(), x))
    return r, candidates[:k + r]

이 코드는 행렬의 대표적인 최소 가중치 후보를 생성하는 설명용 코드입니다. 실제 IP에서는 여기에 행렬 rank, 중복 열, row balance, timing constraint, codeword bit mapping 검증을 추가해야 합니다.

반환된 후보 중 가중치 1인 8개 열을 검사 비트에 할당하고, 나머지 64개 열을 데이터 비트에 할당하면 H = [A | I_8] 형태가 됩니다. 후보 열의 순서와 데이터·검사 비트의 실제 위치는 서로 바꿀 수 있지만, 최종 매핑에서도 열 중복과 최소 거리 조건을 다시 확인해야 합니다.

쓰기 경로

1. 메모리 컨트롤러가 64비트 데이터 워드 D를 받습니다.
2. 선택한 Hsiao 행렬의 A 부분으로 8개의 검사 비트 P를 XOR 계산합니다.
3. 데이터와 검사 비트를 72비트 코드워드로 구성합니다.
4. 일반적인 ECC DIMM에서는 64비트 데이터 경로와 8비트 ECC 경로에 해당하는 72비트 버스로 기록합니다. 실제 DIMM은 DRAM 장치의 x4 또는 x8 폭을 여러 개 병렬로 묶어 이 폭을 구성합니다.

행렬의 각 1은 하나의 XOR 입력 연결을 뜻합니다. 그러므로 낮은 가중치 열을 선택하면 데이터 bit가 참여하는 검사식 수와 전체 연결 수를 줄일 수 있습니다. 다만 systematic 변환과 실제 핀/칩 매핑 뒤에는 행렬이 달라 보일 수 있으므로, 설계 문서에는 논리 행렬과 물리 데이터 lane 매핑을 분리해 기록해야 합니다.

읽기 경로와 syndrome 분류

1. 메모리 컨트롤러가 데이터와 검사 비트를 함께 읽어 수신 코드워드 r을 만듭니다.
2. s = H * r^T를 계산합니다.
3. s = 0이면 오류 없음으로 처리합니다.
4. s가 0이 아니고 홀수 가중치이며 H의 한 열과 일치하면 해당 bit를 반전해 1비트 오류를 정정합니다.
5. s가 0이 아니고 짝수 가중치이면 단일 오류로는 설명할 수 없으므로 정정하지 않고 UE 후보로 처리합니다. 실제 두 비트 오류에서는 두 개의 홀수 열 XOR가 이런 짝수 syndrome을 만들지만, 선택된 행렬의 모든 짝수 벡터가 반드시 실제 열 쌍으로 나타난다고 가정해서는 안 됩니다.
6. 정정 가능 오류는 CE(Correctable Error)로 기록하고, 정정 불가능 오류는 UE(Uncorrectable Error) 경로로 보냅니다.

판정표를 쓰면 다음과 같습니다.

이 분류는 최대 두 비트 오류에 대한 보장입니다. 세 비트 오류의 syndrome은 홀수일 수 있으므로 단일 오류로 오인될 가능성이 있고, 이를 항상 검출하거나 올바르게 정정한다고 말해서는 안 됩니다.

DRAM 컨트롤러와 RAS 연계

Hsiao Code를 적용한 외부 ECC는 보통 다음 RAS 흐름과 함께 동작합니다.

DRAM read -> Hsiao syndrome -> correct / classify
                    |                 |
                    v                 v
              CE counter         UE handling
                    |
                    v
             patrol scrub / retire

단일 bit 오류를 정정한 뒤 원래 위치에 정정 데이터를 다시 기록하는 patrol scrub은 같은 cache line에 오류가 누적되는 것을 줄입니다. 그러나 scrub은 코드의 정정 능력을 높이지 않으며, DRAM 칩 전체 장애를 막아 주지도 않습니다. x4 칩 단위 장애까지 견디려면 데이터 심볼 분산, lockstep, Chipkill과 같은 더 넓은 시스템 설계가 필요합니다.

On-die ECC와의 계층 차이

DDR5 on-die ECC는 DRAM 다이 내부의 셀 저장 오류를 DRAM 장치 안에서 처리하고, 외부 메모리 컨트롤러가 그 내부 syndrome을 직접 관찰하지 못하는 경우가 일반적입니다. 반면 Hsiao 기반 외부 ECC는 컨트롤러와 DIMM 사이의 데이터·ECC 비트, 패키지·버스·칩 수준 오류를 별도 코드워드로 보호합니다. 두 계층은 대체 관계가 아니라 보호 범위가 다른 조합이며, on-die ECC가 외부 side-band ECC를 대신한다고 해석하면 안 됩니다.

장단점

관련 기술

관련 문서

• ECC Error Correction: Hamming, SECDED, side-band ECC, on-die ECC의 기본 원리
• DRAM 테스트/신뢰성: ECC, scrubbing, BIST와 메모리 고장 모델
• DDR 내부 구조: DDR 채널, bank, 모듈과 ECC 데이터 경로
• NAND ECC 고급: BCH와 LDPC 등 저장장치용 강한 ECC
• Linux EDAC 문서: CE/UE, syndrome, 메모리 컨트롤러 오류 보고 계층

참고 문헌

핵심 정리

Hsiao Code는 SECDED의 오류 보장 수준을 높이는 코드가 아니라, 같은 보호 수준을 메모리 하드웨어에 더 적합한 패리티 검사 행렬로 구현하는 설계입니다. 모든 열을 서로 다른 odd-weight 벡터로 구성하면 단일 오류 syndrome은 홀수, 이중 오류 syndrome은 짝수가 되어 두 경우를 구분할 수 있습니다. 64비트 데이터의 대표 구성은 8개의 검사 비트를 사용하며, 낮은 가중치 후보를 선택하면 행렬 연결 수를 줄일 수 있지만 실제 성능은 XOR 트리와 물리 배치까지 확인해야 합니다. DRAM 칩 전체 장애와 높은 오류 정정 능력이 필요하면 Hsiao SECDED만으로 충분하지 않으므로 Chipkill, Reed-Solomon, BCH, LDPC 같은 별도 계층을 함께 설계해야 합니다.