베르호프 알고리즘

베르회프 알고리즘은^[1] 네덜란드 수학자 자코쿠스 베르회프가 개발한 오류 검출용 체크섬 공식으로 1969년 처음 출간됐다.^[2]^[3] 그것은 한 자리수 오류를 모두 감지하는 최초의 소수점 체크 디지트 알고리즘이었고,^[4] 두 개의 인접한 숫자를 포함하는 모든 전이 오차는 그러한 코드로는 불가능하다고 생각되었던 당시였다.

목표들

베르회프는 체크 디지트가 하나의 소수점인 10진법 코드를 찾겠다는 목표를 가지고 있었는데, 이 코드는 한 자릿수 오류와 인접 디지트의 모든 전이를 감지했다. 당시, 이러한 코드들이 존재하지^[5] 않는다는 것으로 추정되는 증거들은 예를 들어 ISBN 체크 디지트에서 베이스-11 코드를 인기 있게 만들었다.

그의 목표 또한 실용적이었고, 그는 네덜란드 우편 시스템의 실시간 데이터에 다른 코드들의 평가를 바탕으로 다른 종류의 오류에 대한 가중 점수 시스템을 사용했다. 분석 결과 오차는 여러 범주로 구분되었는데, 첫째, 오차가 몇 자리냐에 따라, 오차가 두 자릿수인 경우에는 전이(ab → ba), 쌍둥이를 (aa → cb), 점프 전이(abc → cb), 음성(1a → a0), 점프 쌍둥이를 (aba → cbc) 등이다. 추가적으로 생략 및 추가된 자리수들이 있다. 이러한 종류의 오류 중 몇몇의 빈도는 작을 수 있지만, 일부 코드는 모든 단식과 전이를 탐지하는 일차적인 목표 외에 그것들에 면역이 될 수도 있다.

특히 음성 오류는 언어적 효과를 보여주었다. 왜냐하면 네덜란드어에서는 일반적으로 숫자가 쌍으로 읽히기 때문이다. 또한 네덜란드어에서는 15와 비슷한 50개의 소리가 나지만, 80은 18처럼 들리지 않기 때문이다.

여섯 자리 숫자를 예로 들며 베르회프는 다음과 같은 오류 분류를 보고했다.

오류에 있는 숫자	분류	카운트	빈도
1	전사	9,574	79.05%
2	전이	1,237	10.21%
	쌍둥이	67	0.55%
	음성학	59	0.49%
	기타 인접	232	1.92%
	점프 전이	99	0.82%
	점프 트윈스	35	0.29%
	기타 점프 오류	43	0.36%
	기타	98	0.81%
3		169	1.40%
4		118	0.97%
5		219	1.81%
6		162	1.34%
합계		12,112

설명.

$알고리즘$ 의 일반적인 개념은 각 숫자(0~9)를 이음 $D_{5}$ D $5$ 의 요소로서 나타내는 것이다 $D_{5}$ 즉, D $D_{5}$ ${\$ 에 대한 맵 자릿수를 지정하고 $D_{5}$ 이를 조작한 후 다시 숫자로 매핑한다.

${\displaystyle {\pmatrix}0&1&2&3&4&4&5&6&7&9\e&r^{2}&r^{3}&r^{4}s&r^{3}s&r^{4}s\pmatrix}}}}}}}}}}}}$

n번째 숫자를 $a_{n}$ ${\$ 로 하고 $a_{n}$ 자릿수를 $k$ $k$ 로 한다 $k$ 예를 들어(위의 표를 사용) 코드 248을 고려할 때 3 ${\$ ${3}$ 는 $r^{3}s$ $r^{3}s$ $r^{3}s$ 이고 $a_{3}$ k ${\displaystystyle k}$ 은 3이다 $k$ .

이제 순열 $f:D_{5}\to D_{5}$ : $f:D_{5}\to D_{5}$ $f:D_{5}\to D_{5}$ → $f:D_{5}\to D_{5}$ $f:D_{5}\to D_{5}$ ${\$ $D_{5}\to D_{5}}$

${\begin{pmatrix}e&r&r^{2}&r^{3}&r^{4}&s&rs&r^{2}s&r^{3}s&r^{4}s\\r&s&r^{2}s&rs&r^{2}&r^{3}s&r^{3}&e&r^{4}&sr^{4}\end{pmatrix}}$

For example (using the table above) $f(r^{3})=rs$ . Another example is $f^{2}(r^{3})=rs$ since $f(f(r^{3}))=f(rs)=r^{3}$

$D_{5}$ $D_{5}$ ${\$ 의 그룹 작업에 대한 가법 표기법을 사용하여 체크 디짓은 다음과 같은 $c$ 값 $c$ ${\displaystyle$ c $}$ 이(가) 된다 $D_{5}$

$f(a_{1})+f^{2}(a_{2})+\ldots +f^{k}(a_{n})+f^{k+1}(c)=0$

$c$ {\ $displaystyle c}$ 은(는) 역순열을 사용하여 분리할 수 있음 $c$

$c=f^{1-k}\left(-\sum _{n=1}^{k^{n}(a_{n}\right)$

$c$ 으로 c $c$ 을(를) 숫자로 다시 $c$ 매핑하십시오.^[6] 실제로 알고리즘은 기본 그룹과 순열 이론에서 이러한 테이블을 생성하는 방법을 이해할 필요 없이 단순한 룩업 테이블을 사용하여 구현된다. 다른 순열도 작용하기 때문에 이것은 알고리즘의 한 계열로 더 적절하게 간주된다. 베르회프는 위에 주어진 특정한 순열은 95.3%의 음표 오류를 검출하는 특성을 가지고 있어 특별하다고 지적한다.^[7]

알고리즘의 강점은 모든 반투과 및 전이 오류를 감지하고, 추가적으로 대부분의 트윈, 트윈 점프, 점프 전환, 음성 오류를 감지한다는 것이다.

베르호프 알고리즘의 주요 약점은 복잡성이다. 필요한 계산은 ${\displaystyle \mathbb {Z} /10\mathbb {Z} }$ / ${\displaystyle \mathbb {Z} /10\mathbb {Z} }$ Z ${\$ 이라고 하는 공식으로 쉽게 표현할 수 없다 ${\displaystyle \mathbb {Z} /10\mathbb {Z} }$ 쉬운 계산을 위해서는 조회표가 필요하다. 비슷한 코드는 담름 알고리즘으로, 비슷한 성질을 가지고 있다.

테이블 기반 알고리즘

베르회프 알고리즘은 곱셈표 d, 역표 inv, 순열표 p의 세 가지 표를 사용하여 구현할 수 있다.

$(\displaystyle d(j,k)}$ ^[8]		k
$(\displaystyle d(j,k)}$ ^[8]		0	1	2	3	4	5	6	7	8	9
j	0	0	1	2	3	4	5	6	7	8	9
	1	1	2	3	4	0	6	7	8	9	5
	2	2	3	4	0	1	7	8	9	5	6
	3	3	4	0	1	2	8	9	5	6	7
	4	4	0	1	2	3	9	5	6	7	8
	5	5	9	8	7	6	0	4	3	2	1
	6	6	5	9	8	7	1	0	4	3	2
	7	7	6	5	9	8	2	1	0	4	3
	8	8	7	6	5	9	3	2	1	0	4
	9	9	8	7	6	5	4	3	2	1	0

j	$inv(j)$
0	0
1	4
2	3
3	2
4	1
5	5
6	6
7	7
8	8
9	9

$p(pos,num)}$		숫자
$p(pos,num)}$		0	1	2	3	4	5	6	7	8	9
$pos (모드 8)$	0	0	1	2	3	4	5	6	7	8	9
	1	1	5	7	6	2	8	3	0	9	4
	2	5	8	0	3	7	9	6	1	4	2
	3	8	9	1	6	0	4	3	5	2	7
	4	9	4	5	3	1	2	6	8	7	0
	5	4	2	8	6	5	7	3	9	0	1
	6	2	7	9	3	8	0	6	4	1	5
	7	7	0	4	6	9	1	3	2	5	8

첫 번째 표인 d는 dihedral₅ 그룹 D의 곱셈을 기반으로 하며 단순히 그룹의 Cayley 테이블이다.^[6] 이 그룹은 j와 k의 일부 값, 즉 d(j,k) ≠ d(k, j)에 대해 대응적이지 않다는 점에 유의한다.

역표 inv는 숫자의 곱셈 역, 즉 d(j, inv(j) = 0을 만족하는 값을 나타낸다.

순열표 p는 숫자의 위치에 따라 각 숫자에 순열을 적용한다. 이것은 실제로 단일 순열(1 5 8 9 4 2 7 0)(3 6) 반복적으로 적용된 것이다. 즉, p(i+j,n) = p(i, p(j,n)).

Verhooff 체크섬 계산은 다음과 같이 수행된다.

오른쪽에서 왼쪽으로 가져온 숫자의 개별 숫자 중에서 배열 n을 만드십시오(가장 오른쪽 숫자는 n 등₀).
체크섬 c를 0으로 초기화하십시오.
어레이 n의 각 인덱스 i에 대해 0에서 시작하여 c를 $d(c,p(i{\bmod {8}},n_{i}))$ $d(c,p(i{\bmod {8}},n_{i}))$ $d(c,p(i{\bmod {8}},n_{i}))$ $d(c,p(i{\bmod {8}},n_{i}))$ $d(c,p(i{\bmod {8}},n_{i}))$ i $d(c,p(i{\bmod {8}},n_{i}))$ ) $d(c,p(i{\bmod {8},n_{i})$ 로 대체하십시오 $d(c,p(i{\bmod {8}},n_{i}))$

$c=0$ 번호는 c $c=0$ = $c=0$ $c=0$ 인 경우에만 유효하다 $c=0$

체크 디지트를 생성하려면 0을 추가하고 계산을 수행하십시오. 올바른 체크 디지트는 $inv(c)$ $inv(c)$ ( $inv(c)$ $inv(c)$ $inv(c)$ 입니다 $inv(c)$

예

236에 대한 체크 디짓 생성:

i	n_i	p(i,n_i)	c
0	0	0	0
1	6	3	3
2	3	3	1
3	2	1	2

c는 2이므로 체크 디지트는 inv(2), 즉 3이다.

체크 디지트 2363 확인:

i	n_i	p(i,n_i)	c
0	3	3	3
1	6	3	1
2	3	3	4
3	2	1	0

c는 0이므로 체크가 정확하다.

참조

^ Verhoeff, J. (1969). Error Detecting Decimal Codes (Tract 29). The Mathematical Centre, Amsterdam. Bibcode:1971ZaMM...51..240N. doi:10.1002/zamm.19710510323.
^ Kirtland, Joseph (2001). "5. Group Theory and the Verhoeff Check Digit Scheme". Identification Numbers and Check Digit Schemes. Mathematical Association of America. p. 153. ISBN 0-88385-720-0.
^ Salomon, David (2005). "§2.11 The Verhoeff Check Digit Method". Coding for Data and Computer Communications. Springer. pp. 56–58. ISBN 0-387-21245-0.
^ Haunsperger, Deanna; Kennedy, Stephen, eds. (2006). The Edge of the Universe: Celebrating Ten Years of Math Horizons. Mathematical Association of America. p. 38. ISBN 978-0-88385-555-3. LCCN 2005937266.
^ Sisson, Roger L. (May 1958). "An improved decimal redundancy check". Communications of the ACM. 1 (5): 10–12. doi:10.1145/368819.368854.
^ ^a ^b Gallian, Joseph A. (2010). Contemporary Abstract Algebra (7th ed.). Brooks/Cole. p. 111. ISBN 978-0-547-16509-7. LCCN 2008940386. Retrieved August 26, 2011. verhoeff check digit.
^ 베르호프 1969, 페이지 95
^ 1969년, 페이지 83

외부 링크

Verhooff 알고리즘에 대한 자세한 설명

[Verhoeff_1969-1] Verhoeff, J. (1969). Error Detecting Decimal Codes (Tract 29). The Mathematical Centre, Amsterdam. Bibcode:1971ZaMM...51..240N. doi:10.1002/zamm.19710510323.

[Kirtland_2001-2] Kirtland, Joseph (2001). "5. Group Theory and the Verhoeff Check Digit Scheme". Identification Numbers and Check Digit Schemes. Mathematical Association of America. p. 153. ISBN 0-88385-720-0.

[Salomon_2005-3] Salomon, David (2005). "§2.11 The Verhoeff Check Digit Method". Coding for Data and Computer Communications. Springer. pp. 56–58. ISBN 0-387-21245-0.

[Haunsperger_2006-4] Haunsperger, Deanna; Kennedy, Stephen, eds. (2006). The Edge of the Universe: Celebrating Ten Years of Math Horizons. Mathematical Association of America. p. 38. ISBN 978-0-88385-555-3. LCCN 2005937266.

[Sisson_1958-5] Sisson, Roger L. (May 1958). "An improved decimal redundancy check". Communications of the ACM. 1 (5): 10–12. doi:10.1145/368819.368854.

[Gallian_2010-6] Gallian, Joseph A. (2010). Contemporary Abstract Algebra (7th ed.). Brooks/Cole. p. 111. ISBN 978-0-547-16509-7. LCCN 2008940386. Retrieved August 26, 2011. verhoeff check digit.

[7] 베르호프 1969, 페이지 95

[8] 1969년, 페이지 83

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Search

베르호프 알고리즘

네임스페이스

더

목차

목표들

설명.

테이블 기반 알고리즘

예

참조

외부 링크