알고리즘 구조

QR 코드 오류 정정의 원리: Reed-Solomon 수학 알아보기

QR 코드가 찢어지거나, 커피 얼룩이 묻거나, 일부가 번지거나, 가운데를 회사 로고가 가려도 어떻게 문제없이 스캔되는지 궁금했던 적 있나요? 비밀은 Reed-Solomon 다항식 오류 정정에 있어요.

같은 주소를 오류 정정 수준 L, M, Q, H로 만든 QR 코드 네 개. 각 수준이 복원할 수 있는 손상 정도를 보여 주기 위해 면적의 7, 15, 25, 30퍼센트를 검게 칠했다

1. Reed-Solomon 오류 정정이란?

1960년 수학자 어빙 S. 리드(Irving S. Reed)와 귀스타브 솔로몬(Gustave Solomon)이 고안한 Reed-Solomon(RS) 오류 정정은 비이진 순환 오류 정정 알고리즘으로, 우주 통신(NASA 보이저), CD/DVD 광디스크, 위성 TV, 그리고 QR 코드 표준인 ISO/IEC 18004에 널리 쓰여요.

단순한 패리티 비트나 CRC 체크섬처럼 오류를 감지하기만 하는 것이 아니라, Reed-Solomon 부호는 중복 패리티 블록을 수학적으로 생성해 전송을 다시 요청하지 않고도 손상된 바이트 모듈의 정확한 위치를 찾아내고 원래 데이터를 복원할 수 있어요.

2. QR 코드의 네 가지 오류 정정 레벨

ISO/IEC 18004 표준은 선택 가능한 네 가지 오류 정정 코드(ECC) 레벨을 정해 두었어요. 각 레벨은 코드를 읽을 수 없게 되기 전까지 지워지거나 가려져도 되는 전체 코드워드의 비율을 나타내요.

ECC 레벨 복원 용량 모듈 밀도 권장 용도
L 레벨(낮음) 데이터의 ~7% 가장 낮은 밀도(사각형 수 최소) 디지털 화면, QR을 작게 유지해야 하는 대용량 데이터.
M 레벨(중간) 데이터의 ~15% 균형 잡힌 표준 일반 URL, 포장, 전단지, 마케팅 인쇄물의 기본값.
Q 레벨(4분위) 데이터의 ~25% 다소 높은 밀도 맞춤 로고에 가장 적합, 테이블 텐트, 마모되기 쉬운 환경.
H 레벨(높음) 데이터의 ~30% 가장 높은 밀도(사각형 수 최대) 옥외 광고판, 산업용 태그, 물리적 손상이 심한 환경.

3. 로고 삽입이 오류 정정을 활용하는 방식

QR 코드 가운데에 로고나 아이콘을 넣으면 스캐너의 광학 센서는 로고를 표면 손상이나 누락된 모듈로 해석해요.

오류 정정 Q 레벨은 손상된 데이터를 최대 25%까지, H 레벨은 최대 30%까지 복원할 수 있기 때문에, Reed-Solomon 디코더가 로고 아래에 가려진 모듈을 수학적으로 계산해 몇 밀리초 만에 원래 URL을 복원해요.

로고 QR 코드의 황금률:

  • 최대 면적: 로고가 QR 코드 전체 면적의 20~25%를 넘지 않게 하세요.
  • 세 모서리의 위치 찾기 패턴 보호: 왼쪽 위, 오른쪽 위, 왼쪽 아래 모서리의 큰 사각형 눈 세 개를 로고가 가리거나 닿지 않게 하세요.
  • 흰색 여백 사용: 주변 QR 모듈이 로고 그래픽과 섞이지 않도록 로고 둘레에 항상 흰색 보호 여백을 두세요.
  • Q 또는 H 레벨로 자동 전환: qr-code.love는 맞춤 로고를 업로드하면 오류 정정 레벨을 Q 또는 H로 자동으로 올려요.

4. 갈루아 체 GF(256)에서의 수학적 처리 과정

브라우저에서 실행되는 인코더는 원소가 256개인 유한체, 즉 GF(28) 또는 GF(256)에서 연산해요. 모든 바이트는 이 체의 원소이며, 곱셈은 다음 원시 다항식을 법으로 정의돼요.

P(x) = x8 + x4 + x3 + x2 + 1   (16진수로 0x11D)

데이터 바이트는 다항식 D(x)의 계수로 취급돼요. 엔진은 이를 xE로 곱하는데, 여기서 E는 해당 레벨에 필요한 오류 정정 코드워드의 개수예요. 그런 다음 그 결과를 해당 레벨의 고정된 생성 다항식 G(x)로 나눠요. 이 나눗셈의 나머지가 패리티이며, E바이트의 패리티가 데이터 뒤에 이어서 심볼에 배치돼요.

5. ISO의 8가지 마스크 패턴 & 벌점 계산

오류 정정 코드워드를 계산한 뒤 이진 바이트를 그대로 격자에 배치하면, 우연히 온통 검거나 온통 흰 모듈 덩어리가 생기거나 카메라 센서를 헷갈리게 하는 가짜 '위치 찾기 패턴' 모양이 만들어질 수 있어요.

이를 해결하려고 ISO/IEC 18004 표준은 격자 전체에 수학적인 XOR 마스크 패턴 후보 8개를 적용해요. 엔진은 마스크를 적용한 각 후보를 엄격한 벌점 공식으로 평가해요.

  • 벌점 1(인접 모듈의 연속): 같은 색 모듈이 5개 이상 연속되면 3점에 다섯 개를 넘는 모듈마다 1점을 더해요.
  • 벌점 2(2x2 모듈 블록): 한 가지 색으로 채워진 2x2 정사각형마다 벌점 3점을 더해요.
  • 벌점 3(가짜 위치 찾기 패턴): 1:1:3:1:1 비율과 일치하는 모듈 배열마다 벌점 40점을 더해요.
  • 벌점 4(어두운/밝은 모듈 비율 불균형): 50/50 균형에서 벗어난 정도에 비례해 벌점을 더해요.

누적 벌점이 가장 낮은 마스크 패턴이 선택되고, 그 정보는 위치 찾기 패턴 주변의 형식 정보 비트에 인코딩돼요.

6. 실제 환경에서의 손상 내성

날씨나 마모에 노출되는 인쇄물이라면 알맞은 오류 정정 레벨을 고르는 것이 아주 중요해요.

환경 조건 권장 ECC 흔한 손상 위험
옥외 광고판 & 금속 표지판 H 레벨(30%) 자외선 변색, 빗물 자국, 녹, 새 배설물.
식당 테이블 텐트 & 메뉴판 Q 레벨(25%) 음식물 흘림, 손가락 자국, 알코올 소독제.
제품 포장 & 라벨 M 레벨(15%) 가벼운 표면 마찰과 취급 중 긁힘.
디지털 화면 & TV 방송 L 레벨(7%) 물리적 마모 없음. 픽셀 수를 최소화하는 것이 우선.

7. 버전별 데이터 코드워드와 오류 정정 코드워드

버전마다 8비트짜리 코드워드의 개수가 정해져 있고, 레벨에 따라 그중 몇 개가 내 데이터를 담고 몇 개가 복원용 데이터를 담을지 결정돼요. 처음 세 버전은 다음과 같아요.

버전합계L(데이터 + EC)MQH
12619 + 716 + 1013 + 139 + 17
24434 + 1028 + 1622 + 2216 + 28
37055 + 1544 + 2634 + 3626 + 44

데이터 코드워드가 모두 실제 데이터인 것은 아니에요. 처음 몇 비트에는 모드 표시자와 문자 수가 들어가는데, 바이트 모드에서는 버전 9까지 12비트, 버전 10부터는 20비트를 차지해요. 그래서 L 레벨의 버전 1 심볼에는 19바이트가 아니라 17바이트의 데이터만 들어가요.

H 레벨에서는 버전 1부터 복원용 데이터가 실제 데이터보다 많아요. 로고 옵션이 레벨을 올릴 때 바로 이런 거래를 하는 셈이에요. 담을 수 있는 바이트 수는 줄어들지만, 그 대신 일부가 가려져도 여전히 읽히는 심볼을 얻어요.

출처 및 더 읽을거리

오류 정정 QR 코드 만들기

원하는 Reed-Solomon 레벨(L, M, Q, H)을 고르고, 서버 기록 없이 브랜드 로고를 넣어 보세요.

올인원 생성기 열기