댐 알고리즘
Damm algorithm오류 검출에서 Damm 알고리즘은 체크 디지트 알고리즘으로, 한 자릿수 오류와 인접한 모든 전이 오류를 검출한다. 그것은 2004년에 H. Michael Damm에 의해 발표되었다.[1]
장단점
힘
댐 알고리즘은 베르호프 알고리즘과 비슷하다. 또한 가장 자주 나타나는 두 가지 유형의 전사 오류, 즉 한 자릿수를 변경하고 인접한 두 자릿수(후행 체크 자릿수와 앞 자릿수의 전치 포함)의 모든 발생을 감지할 것이다.[1][2] 그러나 Damm 알고리즘은 전용으로 구성된 순열과 그것의 위치 특정 힘이 Verooff 체계에 내재되어 있지 않고 그것이 하는 이점이 있다. 또한, 운영 테이블의 모든 주요 대각선 입력이 0인 경우 반대표를 배포할 수 있다.
Damm 알고리즘은 10개의 가능한 값을 초과하여 어려움을 겪지 않기 때문에 비자리 문자(10자리 ISBN 체크 디지트 구성의 X처럼)를 사용할 필요가 있다.
선행 0을 미리 입력해도 체크 디지트에 영향을 주지 않는다.[1]
영어와 관련된 모든 음성 오류(13파운드, 40파운드, 40파운드, 19파운드)를 감지하는 완전히 반대칭적인 퀘이사 그룹이 있다. 예시에 사용된 표는 그러한 종류의 예에 기초한다.
약점
선행 0을 미리 입력해도 체크 디지트에 영향을 미치지 않으므로, 0, 01, 01, 001 등이 동일한 체크 디지트를 생성하므로 가변 길이 코드를 함께 검증해서는 안 된다.[1] 그러나 모든 체크섬 알고리즘은 이에 취약하다.
디자인
그것의 필수적인 부분은 약하게 완전한 대칭성이라는 특성과 함께 순서 10의 퀘이스트 그룹이다.[3][4][i][ii][iii] Damm은 order 10의 완전한 반대칭 퀘이시그룹을 만들기 위한 몇 가지 방법을 밝혔고 박사학위 논문에서 몇 가지 예를 들었다.[3][i] 이로써 담임은 완전 반대칭적 퀘이시그룹이 존재하지 않는다는 낡은 추측도 반증했다.[5]
quas그룹(Q, q)은 c, x, y ∈ Q에 대해 다음과 같은 함축이 있다면 완전히 대칭성이 없는 것으로 불린다.[4]
- (c ∗ x) ∗ y = (c ∗ y) x ∗ x = y
- x ∗ y = y ∗ x ⇒ x = y,
첫 번째 함축적 함축적 함축적 함축적 함축적 함축적 함축적 함축적 함축적 함축성 Damm은 완전히 대칭적인 n의 quas그룹이라는 것이 약하고 완전히 대칭적인 n의 quas그룹이라는 존재와 동일하다는 것을 증명했다. 체크 방정식이 있는 Damm 알고리즘(... (0m ) x) ∗ xm−10 ∗ ∗ ... ... ... ... ... ... ... qu qu )의 경우, 속성 x qu x = 0을 가진 약한 완전 대칭 quasigroup이 필요하다. 이러한 퀘이시그룹은 모든 0이 대각선 상에 놓일 수 있도록 기둥을 재배치함으로써 어떤 완전 대칭적인 퀘이시그룹으로부터도 구성될 수 있다. 그리고, 반면에, 어떤 약한 반대칭 퀘이시그룹으로부터 완전히 반대칭 퀘이시그룹은 첫 번째 행이 자연적으로 순서가 잡히도록 기둥을 재배치함으로써 구성될 수 있다.[3]
알고리즘.
체크 디지트를 포함하는 숫자 시퀀스의 유효성은 퀘이그룹을 통해 정의된다. 사용할 수 있는 퀘이시그룹 테이블은 Damm의 논문(98, 106, 111페이지)에서 가져갈 수 있다.[3] 각 주 대각선 입력이 0일 경우 체크 디지트 계산을 단순화하므로 유용하다.[1]
포함된 체크 디지트에 대해 번호 확인
- 중간 자릿수를 설정하고 0으로 초기화하십시오.
- 숫자를 숫자별로 처리: 숫자의 숫자를 열 인덱스로 사용하고 임시 숫자를 행 인덱스로 사용하여 테이블 항목을 선택한 다음 임시 숫자를 열 인덱스로 바꾸십시오.
- 숫자는 결과 중간 자릿수가 0인 경우에만 유효하다.[1]
체크 디짓 계산
필수 구성 요소: 테이블의 주요 대각선 항목은 0이다.
- 중간 자릿수를 설정하고 0으로 초기화하십시오.
- 숫자를 숫자별로 처리: 숫자의 숫자를 열 인덱스로 사용하고 임시 숫자를 행 인덱스로 사용하여 테이블 항목을 선택한 다음 임시 숫자를 열 인덱스로 바꾸십시오.
- 결과 중간 자릿수는 체크 디지트를 제공하고 그 숫자에 후행 디지트로 추가된다.[1]
예
다음 작업 표를 사용할 것이다.[1] 행을 재정렬하고 순열 dissertation = (1 2 9 5 4 8 6 7 3)로 항목을 변경하고 x ⋅ y = φ−1(x) ∗ y를 정의함으로써 담임 박사 논문 페이지 111의[3] 완전 대칭 quas그룹 x ∗ y에서 얻을 수 있다.
| ⋅ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0 | 0 | 3 | 1 | 7 | 5 | 9 | 8 | 6 | 4 | 2 |
| 1 | 7 | 0 | 9 | 2 | 1 | 5 | 4 | 8 | 6 | 3 |
| 2 | 4 | 2 | 0 | 6 | 8 | 7 | 1 | 3 | 5 | 9 |
| 3 | 1 | 7 | 5 | 0 | 9 | 8 | 3 | 4 | 2 | 6 |
| 4 | 6 | 1 | 2 | 3 | 0 | 4 | 5 | 9 | 7 | 8 |
| 5 | 3 | 6 | 7 | 4 | 2 | 0 | 9 | 5 | 8 | 1 |
| 6 | 5 | 8 | 6 | 9 | 7 | 2 | 0 | 1 | 3 | 4 |
| 7 | 8 | 9 | 4 | 5 | 3 | 6 | 2 | 0 | 1 | 7 |
| 8 | 9 | 4 | 3 | 8 | 6 | 1 | 7 | 2 | 0 | 5 |
| 9 | 2 | 5 | 8 | 1 | 4 | 3 | 6 | 7 | 9 | 0 |
숫자(자리 순서) 572를 선택한다고 가정합시다.
체크 디짓 계산
| 처리할 디지트 → 컬럼 인덱스 | 5 | 7 | 2 |
|---|---|---|---|
| 이전 중간 자릿수 → 행 색인 | 0 | 9 | 7 |
| 테이블 항목 → 새로운 중간 자릿수 | 9 | 7 | 4 |
결과 중간 자릿수는 4이다. 계산된 체크 디짓 입니다. 우리는 그것을 번호에 추가하고 5724를 얻는다.
포함된 체크 디지트에 대해 번호 확인
| 처리할 디지트 → 컬럼 인덱스 | 5 | 7 | 2 | 4 | |
|---|---|---|---|---|---|
| 이전 중간 자릿수 → 행 색인 | 0 | 9 | 7 | 4 | |
| 테이블 항목 → 새로운 중간 자릿수 | 9 | 7 | 4 | 0 |
결과 중간 자릿수는 0이므로 숫자가 유효하다.
그래픽 일러스트레이션
위의 예는 체크 디짓(파란색 화살표)을 생성하는 알고리즘과 체크 디짓으로 숫자 572를 검증하는 세부사항을 보여주는 것이다.
참조
- ^ a b c d e f g h Fenwick, Peter (2014). "Checksums and Error Control". In Fenwick, Peter (ed.). Introduction to Computer Data Representation. Bentham Science Publishers. pp. 191–218. doi:10.2174/9781608058822114010013. ISBN 978-1-60805-883-9.
- ^ 일반적인 오류 유형 및 빈도는 다음을 참조하십시오.
- ^ a b c d e Damm, H. Michael (2004). Total anti-symmetrische Quasigruppen (PDF) (Dr. rer. nat.) (in German). Philipps-Universität Marburg. urn:nbn:de:hebis:04-z2004-05162.
- ^ a b Damm, H. Michael (2007). "Totally anti-symmetric quasigroups for all orders n≠2,6". Discrete Mathematics. 307 (6): 715–729. doi:10.1016/j.disc.2006.05.033. ISSN 0012-365X.
- ^ Damm, H. Michael (2003). "On the Existence of Totally Anti-Symmetric Quasigroups of Order 4k + 2". Computing. 70 (4): 349–357. doi:10.1007/s00607-003-0017-3. ISSN 0010-485X. S2CID 31659430.
- ^ a b Beliavscaia Galina; Izbaş Vladimir; Şcerbacov Victor (2003). "Check character systems over quasigroups and loops" (PDF). Quasigroups and Related Systems. 10 (1): 1–28. ISSN 1561-2848.
{{cite journal}}: (도움말) 23페이지를 참조하십시오. - ^ Chen Jiannan (2009). "The NP-completeness of Completing Partial anti-symmetric Latin squares" (PDF). Proceedings of 2009 International Workshop on Information Security and Application (IWISA 2009). Academy Publisher. pp. 322–324. ISBN 978-952-5726-06-0. 324페이지를 참조하십시오.
- ^ Mileva, A.; Dimitrova, V. (2009). "Quasigroups constructed from complete mappings of a group (Z2n,⊕)" (PDF). Contributions, Sec. Math. Tech. Sci., MANU/MASA. XXX (1–2): 75–93. ISSN 0351-3246. 78페이지를 참조하십시오.
외부 링크
 | Wikibooks에는 다음과 같은 주제의 책이 있다. 알고리즘 구현/체크섬/댐 알고리즘 |
