QR코드 생성 방법 (3)

처음으로   이전 페이지   다음 페이지

2.3 오류 정정 코드 계산

QR코드의 오류 정정에는 Reed-solomon 알고리즘이 사용된다.

먼저, 전 단계에서 나온 결과를 표5의 규칙에 의해 RS 블록으로 분할한다.
예제 데이터는 1-H를 사용하는데 이는 RS 블록 1이므로 분할할 필요는 없다.

그 다음에는 표3에서 g(x)를 선택한다.
예제 데이터에서 오류 정정 코드의 크기는 17이므로, 아래와 같은 g(x)를 선택하게 된다.

g(x) = x¹⁷ + α⁴³x¹⁶ + α¹³⁹x¹⁵ + α²⁰⁶x¹⁴ + α⁷⁸x¹³ + α⁴³x¹²
         + α²³⁹x¹¹ + α¹²³x¹⁰ + α²⁰⁶x⁹ + α²¹⁴x⁸ + α¹⁴⁷x⁷ + α²⁴x⁶
         + α⁹⁹x⁵ + α¹⁵⁰x⁴ + α³⁹x³ + α²⁴³x² + α¹⁶³x + α¹³⁶

위 식에서의 α는 GF(2⁸)의 원시근(Primitive Element)이다.

GF(2⁸)의 특징들은 다음과 같다.
 1. 사칙연산이 모두 지원된다.
 2. α²⁵⁵ = 1
 3. 표4를 사용하여 α의 거듭제곱을 정수로(또는 그 반대로) 변환할 수 있다.


이제 데이터 코드를 각 항의 계수로 가진 다항식 f(x)를 g(x)로 나누는 과정을 보자.


f(x) = 32x²⁵ + 65x²⁴ + 205x²³ + 69x²² + 41x²¹ + 220x²⁰ + 46x¹⁹ + 128x¹⁸ + 236x¹⁷ <--- (1)

g(x)로 나누는 방법은 다음과 같다.

f(x)의 최고차항의 계수는 32이다.
표4에서 32는 α⁵와 같으므로 g(x)에 이를 곱하자.

g(x)*(α⁵)*x⁸

= α⁵*x²⁵ + α⁵*α⁴³*x²⁴ + α⁵*α¹³⁹*x²³ + α⁵*α²⁰⁶*x²² + α⁵*α⁷⁸*x²¹ + ...

= α⁵*x²⁵ + α⁴⁸*x²⁴ + α¹⁴⁴*x²³ + α²¹¹*x²² + α⁸³*^x21 + ...

= 32x²⁵ + 70x²⁴ + 168x²³ + 178x²² + 187x²¹ + ... <--- (2)

(1)과 (2)의 베타적논리합(Exclusive Logical Sum, Excusive OR, XOR)을 계산하면 f(x)'가 나온다.

f(x)'=7x²⁴ +101x²³ +247x²²+146x²¹.....

이제 상수항이 나올 때 까지 같은 방법으로 계속 나누자. 7은 α¹⁹⁸이므로 g(x)에 이를 곱하자. g(x)*α¹⁹⁸*x⁷을 사용하면 된다.
만약 α의 지수가 255를 초과한다면, "α²⁵⁵ = 1" 임을 이용하여 지수를 줄여라.

위 작업이 종료되면 아래의 R(x)를 얻게 된다.

R(x)=42x¹⁶ +159x¹⁵ +74x¹⁴ +221x¹³ +244x¹² +169x¹¹+239x¹⁰
　　　 +150x⁹ +138x⁸ +70x⁷ +237x⁶ +85x⁵ +224x⁴ +96x³ +74x² +219x +61

(자세한 계산 과정은 표6을 참고하여라.)

이를 10진수로 나타낸 코드 데이터에 추가하면 다음과 같이 된다.

32 65 205 69 41 220 46 128 236 42 159 74 221 244 169 239 150 138 70 237 85 224 96 74 219 61

이전 페이지   다음 페이지