Page History
The(See see 3.1.4.2. Component features - Identifiers) includes a check-digit, which is generated using Verhoeff's dihedral check. This section explains the algorithm used and includes sample source code for generating and checking the check-digit in Java Script and Microsoft Visual Basic.
Related Links
...
Verhoeff's Dihedral Group D5 Check
The mathematical description of this technique may appear complex but in practice it can be reduced to a pair of two-dimensional arrays, a single dimensional inverse array and a simple computational procedure. These three arrays are shown in the following tables.
- The first array contains the result of "Dihedral D5" multiplication;
- The second array consists of 8 rows of which two are defined while the rest are derived by applying the following formula: F(i, j) = F(i - 1, F(1, j)) ;
The third array consists of a single row containing the inverse of the Dihedral D5 array it identifies the location of all the zero values in the first array.
24
TableAnchor _766d12f3-2bd3-4ee9-87e1-76b6e6444536__5 _766d12f3-2bd3-4ee9-87e1-76b6e6444536__5
251. Results of Dihedral D5 multiplication
0
1
2
3
4
5
6
7
8
9
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
TableAnchor _766d12f3-2bd3-4ee9-87e1-76b6e6444536__9 _766d12f3-2bd3-4ee9-87e1-76b6e6444536__9 2. The full array for Function F
0
1
2
3
4
5
6
7
8
9
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
Anchor _766d12f3-2bd3-4ee9-87e1-76b6e6444536__a _766d12f3-2bd3-4ee9-87e1-76b6e6444536__a
26Table
3. The Inverse D5 array
0
1
2
3
4
5
6
7
8
9
0
4
3
2
1
5
6
7
8
9
The identifier is checked by starting at the rightmost digit of the identifier (the check-digit itself) and proceeding to the left processing each digit as follows:
- Check = ArrayDihedralD5 ( Check, ArrayFunctionF(( Position Modulus 8), Digit ))
...
Digit = the value of the digit.
.
The final value of Check should be zero. Otherwise the check has failed.
When calculating the the thethe same process is applied with a minor variation:
Position is the position that the digit will have when
the hasthe has been appended.
The final value of Check is applied to the Inverse D5 array to find the correct.
= ArrayInverseD5 ( Check ).
.
...
Sample Java Script for computing Verhoeff's Dihedral Check
The script is presented here as part of an HTML page.
Note:
The code below can be used by copying all the lines in the above section into an HTML file and opening this with a web . From the HTML version of this guide the following link provides access to this file as an . <!DOCTYPE html SYSTEM browser.
| Info |
|---|
A live version of this web page can be accessed at http://snomed.org/verhoeff. |
| Code Block | ||
|---|---|---|
| ||
<!DOCTYPE html SYSTEM "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> |
...
<html> |
...
<head> |
...
<title>SNOMED CT Identifier Check</title> |
...
<style> |
...
body{font-family:Arial, Helvetica, sans-serif} |
...
} |
...
</style> |
...
<meta content="text/html; charset=iso-8859-1" http-equiv="Content-Type"><meta> |
...
<script type="text/javascript" language="JavaScript"> |
...
var FnF = new Array(); |
...
FnF[0] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]; |
...
FnF[1] = [1, 5, 7, 6, 2, 8, 3, 0, 9, 4]; |
...
for ( var i = 2; i < 8; i++ ) |
...
{ |
...
FnF[i] = [,,,,,,,,,]; |
...
for ( var j = 0; j < 10; j++ ) |
...
FnF[i][j] = FnF[i - 1][FnF[1][j]]; |
...
} |
...
var Dihedral = new Array( |
...
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], |
...
[1, 2, 3, 4, 0, 6, 7, 8, 9, 5], |
...
[2, 3, 4, 0, 1, 7, 8, 9, 5, 6], |
...
[3, 4, 0, 1, 2, 8, 9, 5, 6, 7], |
...
[4, 0, 1, 2, 3, 9, 5, 6, 7, 8], |
...
[5, 9, 8, 7, 6, 0, 4, 3, 2, 1], |
...
[6, 5, 9, 8, 7, 1, 0, 4, 3, 2], |
...
[7, 6, 5, 9, 8, 2, 1, 0, 4, 3], |
...
[8, 7, 6, 5, 9, 3, 2, 1, 0, 4], |
...
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0] ); |
...
var InverseD5 = new Array(0, 4, 3, 2, 1, 5, 6, 7, 8, 9 ); |
...
function VerhoeffCheck() |
...
{ |
...
var check = 0; |
...
var IdValue = document.form.numcd.value; |
...
document.getElementById("out").innerText = ""; |
...
document.getElementById("out").setAttribute("style", " :red;"); |
...
document.getElementById("component").innerText ="Invalid partition"; |
...
document.getElementById("component").setAttribute("style", " :green;"); |
...
document.getElementById("extnamespace").innerText ="No namespace"; |
...
document.getElementById("extnamespace").setAttribute("style", " :red;"); |
...
for ( var i=IdValue.length-1; i >=0; i-- ) |
...
check = Dihedral[check][FnF[(IdValue.length-i-1) % 8][IdValue.charAt |
...
(i)]]; |
...
if ( check != 0 ) { document.getElementById("out").innerText = "Check-digit ERROR"; } |
...
else if (IdValue.length < 6) {document.getElementById("out").innerText = "SCTID too short";} |
...
else if (IdValue.length > 18) {document.getElementById("out").innerText = "SCTID too long";} |
...
else {document.getElementById("out").innerText = "Check-digit OK"; |
...
document.getElementById("out").setAttribute("style", " :green;"); |
...
switch (IdValue.substr(IdValue.length-3,2)) |
...
{ |
...
case "00": |
...
document.getElementById("component").innerText ="Concept"; |
...
document.getElementById("extnamespace").innerText ="International"; |
...
break; |
...
case "01": |
...
document.getElementById("component").innerText ="Description"; |
...
document.getElementById("extnamespace").innerText ="International"; |
...
break; |
...
case "02": |
...
document.getElementById("component").innerText ="Relationship"; |
...
document.getElementById("extnamespace").innerText ="International"; |
...
break; |
...
case "03": |
...
document.getElementById("component").innerText ="Subset (RF1)"; |
...
document.getElementById("extnamespace").innerText ="International"; |
...
break; |
...
case "04": |
...
document.getElementById("component").innerText ="Cross Map Set (RF1)"; |
...
document.getElementById("extnamespace").innerText ="International"; |
...
break; |
...
case "05": |
...
document.getElementById("component").innerText ="Cross Map Target (RF1)"; |
...
document.getElementById("extnamespace").innerText ="International"; |
...
break; |
...
case "10": |
...
document.getElementById("component").innerText ="Concept"; |
...
document.getElementById("extnamespace").innerText =IdValue.substr(IdValue.length-10,7); |
...
break; |
...
case "11": |
...
document.getElementById("component").innerText ="Description"; |
...
document.getElementById("extnamespace").innerText =IdValue.substr(IdValue.length-10,7); |
...
break; |
...
case "12": |
...
document.getElementById("component").innerText ="Relationship"; |
...
document.getElementById("extnamespace").innerText =IdValue.substr(IdValue.length-10,7); |
...
break; |
...
case "13": |
...
document.getElementById("component").innerText ="Subset (RF1)"; |
...
document.getElementById("extnamespace").innerText =IdValue.substr(IdValue.length-10,7); |
...
break; |
...
case "14": |
...
document.getElementById("component").innerText ="Cross Map Set (RF1)"; |
...
document.getElementById("extnamespace").innerText =IdValue.substr(IdValue.length-10,7); |
...
break; |
...
case "15": |
...
document.getElementById("component").innerText ="Cross Map Target (RF1)"; |
...
document.getElementById("extnamespace").innerText =IdValue.substr(IdValue.length-10,7); |
...
break; |
...
default: |
...
document.getElementById("component").setAttribute("style", " :red;"); |
...
} |
...
if (document.getElementById("extnamespace").innerText=='International') {document.getElementById("extnamespace").setAttribute("style", " :green;");} |
...
else if (IdValue.length>10) {document.getElementById("extnamespace").setAttribute("style", " :green;");} |
...
else {document.getElementById("extnamespace").innerText="Invalid Namespace"; |
...
} |
...
} |
...
} |
...
function VerhoeffCompute( ) |
...
{ |
...
var IdValue = document.form.num.value; var check = 0; |
...
document.form.numcd.value= ""; |
...
for ( var i = IdValue.length-1; i >=0; i-- ) |
...
check = Dihedral[check][FnF[(IdValue.length-i) % 8][IdValue.charAt |
...
(i)]]; |
...
document.form.numcd.value = document.form.num.value + InverseD5[check]; |
...
VerhoeffCheck(); |
...
document.getElementById("out").innerText = "Computed check-digit"; |
...
} |
...
</script> |
...
</head> |
...
<body> |
...
<h1>SNOMED CT Identifier Check</h1> |
...
<form action="" name="form"> |
...
<table border="1" width="441"> |
...
<tr> |
...
<td width="212" height="25"> |
...
Partial Identifier <br/>(without check-digit) |
...
</td> |
...
<td width="115" height="25"> |
...
<input name="num" size="18"/> |
...
</td> |
...
<td width="92" height="25"> |
...
<input onclick= "VerhoeffCompute()" type="button" value="Compute"/> |
...
</td> |
...
</tr> |
...
<tr> |
...
<td width="212" height="35"> |
...
SNOMED CT Identifier |
...
</td> |
...
<td width="115" height="35"> |
...
<input name="numcd" size="18"/> |
...
</td> |
...
<td width="92" height="35"> |
...
<input onclick= "VerhoeffCheck()" type="button" value="Check"/> |
...
</td> |
...
</tr> |
...
<tr> |
...
<td width="212" height="23"> |
...
Result |
...
of check </td> |
...
<td width="115" height="23" colspan="2" id="out"> |
...
</td> </tr> |
...
<tr> |
...
<td width="212" height="23"> |
...
Component type |
...
</td> |
...
<td width="115" height="23" colspan="2" id="component"> |
...
</td> </tr> |
...
<tr> |
...
<td width="212" height="23"> |
...
Namespace |
...
</td> |
...
<td width="115" height="23" colspan="2" id="extnamespace"> |
...
</td> </tr> |
...
</table> |
...
<p style="margin-left: 0; margin-right: 0"> |
...
This Verhoeff checking part of this code was based on a webpage at: |
...
</p> |
...
<ul> |
...
<li> |
...
<a href="http://www.augustana.ab.ca/~mohrj/algorithms/checkdigit.html"> |
...
http://www.augustana.ab.ca/~mohrj/algorithms/checkdigit.html |
...
</a> |
...
</li> |
...
</ul> |
...
</form> |
...
</body> |
...
</html> |
...
Sample Visual Basic for computing Verhoeff's Dihedral
...
Check
| Code Block | ||
|---|---|---|
| ||
Option Explicit |
...
Private Dihedral(9) As Variant |
...
Private FnF(7) As Variant |
...
Private InverseD5 As Variant |
...
Public Function VerhoeffCheck(ByVal IdValue As String) As Boolean |
...
'Check the supplied value and return true or false |
...
Dim tCheck As Integer, i As Integer |
...
VerhoeffArrayInit |
...
For i = Len(IdValue) To 1 Step -1 |
...
tCheck = Dihedral(tCheck)(FnF((Len(IdValue) - i) Mod 8)(Val(Mid(IdValue, i, 1)))) |
...
Next |
...
VerhoeffCheck = tCheck = 0 |
...
End Function |
...
Public Function VerhoeffCompute(ByVal IdValue As String) As String |
...
'Compute the check digit and return the identifier complete with check-digit |
...
Dim tCheck As Integer, i As Integer |
...
VerhoeffArrayInit |
...
For i = Len(IdValue) To 1 Step -1 |
...
tCheck = Dihedral(tCheck)(FnF((Len(IdValue) - i + 1) Mod 8)(Val(Mid(IdValue, i, 1)))) |
...
Next |
...
VerhoeffCompute = IdValue & InverseD5(tCheck) |
...
End Function |
...
Private Sub VerhoeffArrayInit() |
...
'Create the arrays required |
...
Dim i As Integer, j As Integer |
...
'if already created exit here |
...
If VarType(InverseD5) >= vbArray Then Exit Sub |
...
'create the DihedralD5 array |
...
Dihedral(0) = Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9) |
...
Dihedral(1) = Array(1, 2, 3, 4, 0, 6, 7, 8, 9, 5) |
...
Dihedral(2) = Array(2, 3, 4, 0, 1, 7, 8, 9, 5, 6) |
...
Dihedral(3) = Array(3, 4, 0, 1, 2, 8, 9, 5, 6, 7) |
...
Dihedral(4) = Array(4, 0, 1, 2, 3, 9, 5, 6, 7, 8) |
...
Dihedral(5) = Array(5, 9, 8, 7, 6, 0, 4, 3, 2, 1) |
...
Dihedral(6) = Array(6, 5, 9, 8, 7, 1, 0, 4, 3, 2) |
...
Dihedral(7) = Array(7, 6, 5, 9, 8, 2, 1, 0, 4, 3) |
...
Dihedral(8) = Array(8, 7, 6, 5, 9, 3, 2, 1, 0, 4) |
...
Dihedral(9) = Array(9, 8, 7, 6, 5, 4, 3, 2, 1, 0) |
...
'create the FunctionF array |
...
FnF(0) = Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9) |
...
FnF(1) = Array(1, 5, 7, 6, 2, 8, 3, 0, 9, 4) |
...
'compute the rest of the FunctionF array |
...
For i = 2 To 7 |
...
FnF (i) = Array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0) |
...
For j = 0 To 9 |
...
FnF (i)(j) = FnF(i - 1)(FnF(1)(j)) |
...
Next |
...
Next |
...
'Create the InverseD5 array |
...
InverseD5 = Array("0", "4", "3", "2", "1", "5", "6", "7", "8", "9") |
...
End Sub
...
End Sub |
Reasons for using a check-digit
Although a user should rarely type the, experience suggests that from time to time this will happen. A user may also copy and paste an. There is a significant risk of errors in these processes and inclusion of a is ais intended to reduce the risk of such errors passing undetected. The choice of algorithm ofalgorithm has been made to maximize the detection of common typographical errors. These have been analyzed by in a paper by J. Verhoeff ("Error Detecting Decimal Codes", Mathematical Center Tract 29, The Mathematical Center, Amsterdam, 1969) and subsequently cited in Wagner and Putter, ("Error Detecting Decimal Digits", CACM, Vol 32, No. 1, January 1989). These papers give a detailed categorization of the sorts of errors humans make in dealing with decimal numbers, based on a study of 12000 errors:
...
The ISBN modulus 11 (used for numberfornumber) picks up more errors than the IBM checksum. Leaving 2% to 3% of errors undetected. However, it generates a check-sum value of 0 to 10 and thus cannot be represented as a single in singlein about 9% of cases. The ISBN convention is to use "X" to represent the value thevalue 10 but this is incompatible with an Integer (data type) representation. The number Thenumber uses this check-sum but regards and number generating a check-sum of 10 as an invalid. This approach could be applied to the but thebut this would render 9% of possible values unusable in each partition and. This would prevent a simple sequence of values from being allocated as the "item" within each. More significantly the unusable item would itemwould differ in each or eachor partition and this would prevent simple transpositions of item between itembetween partitions and. Partitions could be a useful way of distinguishing developmental and released components and revising the partition and recalculating the would thewould then be an elegant way to activate these components for a distribution version. It seems unwise to prevent future development and maintenance by using a check-sum that will prevent this.
...
Verhoeff's Check
Verhoeff's check catches all single errors, all adjacent transpositions, over 95% of twin errors, over 94% of jump transpositions and jump twin errors, and most phonetic errors. Therefore, like modulus 11, the Verhoeff check reduces the undetected error rate to 2% or 3%. Unlike modulus 11, it does this using a single decimal and decimaland without limiting the range of valid numbers.
The majority of the undetected errors with both modulus 11 and Verhoeff result from additions or omissions of digits. Any methods Anymethods is likely to miss 10% of such errors and since these comprise 10% to 20%. The Verhoeff scheme also misses four jump twin errors involving digits with a difference of 5 (i.e. 050 vs. 505, 161 vs. 616, 272 vs. 727, and 494 vs. 949).
Overview
Content Tools
Apps