Damm algoritması - Damm algorithm
İçinde hata tespiti , Damm algoritması a, kontrol hanesi algoritması tüm tespit Tek basamaklı hataları ve bitişik aktarılması hataların . 2004 yılında H. Michael Damm tarafından sunulmuştur.
Güçlülükler ve zayıflıklar
Güçlü
Damm algoritması, Verhoeff algoritmasına benzer . Aynı zamanda, en sık görülen iki transkripsiyon hatası türünün tüm oluşumlarını , yani tek bir rakamı değiştirerek ve iki bitişik rakamı transpoze ederek (takip eden kontrol hanesinin ve önceki rakamın transpozisyonu dahil) tüm oluşumlarını tespit edecektir . Ancak Damm algoritması, özel olarak oluşturulmuş permütasyonlar ve pozisyona özgü güçleri Verhoeff şemasının doğasında bulunan olmadan başarma avantajına sahiptir . Ayrıca, ameliyat tablosunun tüm ana köşegen girişlerinin sıfır olması şartıyla bir ters tablodan vazgeçilebilir.
Damm algoritması (olmayan bir basamaklı karakter kullanma ihtiyacı ortaya çıkan, 10 olası değerlerin sayısını aşan zarar vermez X içinde 10 basamaklı ISBN kontrol hanesi düzeni).
Baştaki sıfırlar, kontrol basamağını etkilemez.
İngiliz diliyle ilişkili tüm fonetik hataları algılayan tamamen anti-simetrik yarı gruplar vardır (13 ↔ 30, 14 ↔ 40, ..., 19 ↔ 90). Açıklayıcı örnekte kullanılan tablo, bu türden bir örneğe dayanmaktadır.
Zayıf yönler
Baştaki sıfırlar kontrol basamağını etkilemediğinden, değişken uzunluklu kodlar, örneğin 0, 01 ve 001, vb. Aynı kontrol basamağını ürettiği için birlikte doğrulanmamalıdır. Ancak, tüm sağlama toplamı algoritmaları buna karşı savunmasızdır.
Dizayn
Temel kısmı, zayıf bir şekilde tamamen anti-simetrik olma özelliğine sahip olan (yani , operasyon masasının gövdesi olarak 10 × 10 Latin kareye sahip olan) düzen 10'luk bir yarı gruptur . Damm, 10. dereceden tamamen anti-simetrik yarı gruplar oluşturmak için çeşitli yöntemler ortaya koydu ve doktora tezinde bazı örnekler verdi. Bununla Damm, 10. düzenin tamamen anti-simetrik yarı gruplarının var olmadığına dair eski bir varsayımı da çürüttü.
Bir yarı grup ( Q , ∗) , tüm c , x , y ∈ Q için aşağıdaki çıkarımlar geçerliyse, tamamen anti-simetrik olarak adlandırılır :
- ( c ∗ x ) ∗ y = ( c ∗ y ) ∗ x ⇒ x = y
- x ∗ y = y ∗ x ⇒ x = y ,
ve sadece ilk sonuç geçerliyse, zayıf tamamen anti-simetrik olarak adlandırılır. KDE'den düzenin tamamen anti-simetrik quasigroup varlığı kanıtlanmıştır n için zayıf bir tamamen anti-simetrik quasigroup varlığı eşdeğerdir n . Kontrol denklemine sahip Damm algoritması için (... ((0 ∗ x m ) ∗ x m −1 ) ∗ ...) ∗ x 0 = 0 , x ∗ x = 0 özelliğine sahip zayıf, tamamen anti-simetrik bir yarı grup gereklidir. Böyle bir yarı grup, tüm sıfırlar köşegen üzerinde olacak şekilde sütunların yeniden düzenlenmesiyle herhangi bir tamamen anti-simetrik yarı gruptan oluşturulabilir. Öte yandan, herhangi bir zayıf tamamen anti-simetrik yarı gruptan tamamen anti-simetrik bir yarı grup, sütunların ilk sıranın doğal düzende olacağı şekilde yeniden düzenlenmesiyle oluşturulabilir.
Algoritma
Bir kontrol basamağı içeren bir basamak dizisinin geçerliliği, bir quasigroup üzerinden tanımlanır. Kullanıma hazır bir quasigroup tablosu, Damm'ın tezinden alınabilir (sayfa 98, 106, 111). Her ana çapraz girişin 0 olması yararlıdır, çünkü kontrol basamağı hesaplamasını basitleştirir.
Dahil edilen kontrol basamağına göre bir sayıyı doğrulama
- Bir ara basamak ayarlayın ve 0 olarak ilklendirin.
- Sayıyı basamak basamak işleyin: Sayının basamağını sütun dizini ve ara basamağı satır dizini olarak kullanın, tablo girişini alın ve ara basamağı bununla değiştirin.
- Sayı, ancak ve ancak sonuçta ortaya çıkan ara basamak 0 değerine sahipse geçerlidir.
Kontrol basamağının hesaplanması
Ön koşul: Tablonun ana çapraz girişleri 0'dır.
- Bir ara basamak ayarlayın ve 0 olarak ilklendirin.
- Sayıyı basamak basamak işleyin: Sayının basamağını sütun dizini ve ara basamağı satır dizini olarak kullanın, tablo girişini alın ve ara basamağı bununla değiştirin.
- Ortaya çıkan ara basamak, kontrol basamağını verir ve sayıya son basamak olarak eklenir.
Misal
Aşağıdaki işlem tablosu kullanılacaktır. Sıraları yeniden düzenleyerek ve φ = (1 2 9 5 4 8 6 7 3) permütasyonu ile girişleri değiştirerek ve x ⋅ y = tanımlayarak Damm'ın doktora tezi sayfa 111'deki tamamen anti-simetrik quasigroup x ∗ y'den elde edilebilir. φ −1 ( φ ( 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 sayısını (rakam dizisi) seçtiğimizi varsayalım .
Kontrol basamağının hesaplanması
| işlenecek basamak → sütun dizini | 5 | 7 | 2 |
|---|---|---|---|
| eski ara rakam → satır dizini | 0 | 9 | 7 |
| tablo girişi → yeni ara rakam | 9 | 7 | 4 |
Ortaya çıkan ara rakam 4'tür . Bu hesaplanan kontrol basamağıdır. Numaraya ekliyoruz ve 5724 elde ediyoruz .
Dahil edilen kontrol basamağına göre bir sayıyı doğrulama
| işlenecek basamak → sütun dizini | 5 | 7 | 2 | 4 |
|---|---|---|---|---|
| eski ara rakam → satır dizini | 0 | 9 | 7 | 4 |
| tablo girişi → yeni ara rakam | 9 | 7 | 4 | 0 |
Ortaya çıkan ara basamak 0'dır , dolayısıyla sayı geçerlidir .
Grafiksel gösterim
Bu, kontrol basamağını (kırık mavi ok) üreten ve 572 sayısını kontrol basamağı ile doğrulayan algoritmanın detayını gösteren yukarıdaki örnektir .
