Page History
The (See ) includes a
Gloss | ||||
---|---|---|---|---|
|
...
...
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.
Anchor _766d12f3-2bd3-4ee9-87e1-76b6e6444536__5 _766d12f3-2bd3-4ee9-87e1-76b6e6444536__5 Table 24. Results of Dihedral D5 multiplication
Caption label | ||||
---|---|---|---|---|
| ||||
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 |
...
Caption label |
---|
...
|
...
|
...
|
...
|
...
...
...
...
...
...
...
...
...
...
...
| |||
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 |
...
Table 26. The Inverse D5 array
...
...
...
...
...
...
...
...
...
Caption label | ||||
---|---|---|---|---|
| ||||
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
Gloss | ||||
---|---|---|---|---|
|
Position is the position that the digit will have when
thethe
has been appended.Gloss PreSpace false t check-digit The final value of Check is applied to the Inverse D5 array to find the correct
.Gloss PreSpace false t check-digit
Gloss | ||||
---|---|---|---|---|
|
.
...
Sample Java Script for computing Verhoeff's Dihedral Check
...
Info |
---|
A live version of an HTML |
...
form and JavaScript is available in section 6.4.1 SNOMED CT Identifier Check. |
Code Block | ||||||||
---|---|---|---|---|---|---|---|---|
| ||||||||
<style>
p.p1 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica}
span.s1 {color: #021da7}
span.s2 {color: #f9975e}
span.s3 {color: #ff9450}
span.s4 {color: #ab4500}
span.s5 {color: #a7a400}
table {border-width: 6px; border-color: #0080ff; border-collapse: collapse; border-style: ridge;}
td {border-width: 3px; border-color: #0080ff; border-collapse: collapse; padding: 6px; border-style: ridge;}
</style>
<form action="" name="form">
<table 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> |
Code Block | ||||||||
---|---|---|---|---|---|---|---|---|
| ||||||||
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","color:red;");
|
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 "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 ]];
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 =" |
...
Invalid partition"; |
...
document.getElementById(" |
...
component"). |
...
break;
case "05":
setAttribute("style","color:green;"); document.getElementById(" |
...
extnamespace").innerText =" |
...
No namespace"; |
...
document.getElementById("extnamespace"). |
...
setAttribute(" |
...
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)";
...
style","color: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","color:green;"); switch (IdValue.substr(IdValue.length- |
...
3, |
...
break;
case "15":
2)) { case "00": document.getElementById("component").innerText =" |
...
Concept"; |
...
document.getElementById("extnamespace").innerText |
...
break;
default:
="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 =" |
...
}
}
}
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 ]];
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>
...
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","color:red;");
}
if (document.getElementById("extnamespace").innerText=='International') {document.getElementById("extnamespace").setAttribute("style","color:green;");}
else if (IdValue.length>10) {document.getElementById("extnamespace").setAttribute("style","color: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";
} |
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 = |
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
...
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
Gloss | ||||
---|---|---|---|---|
|
Gloss | ||||
---|---|---|---|---|
|
Gloss | ||||
---|---|---|---|---|
|
Gloss | ||||
---|---|---|---|---|
|
...
In the explanations above, a is not equal to b, but c can be any decimal digit.
...
c can be any decimal digit.
A brief comparison of check-digit effectiveness
...
...
The IBM Check
The check-sums used for credit cards (the IBM check) picks up the most common errors but miss some adjacent transpositions and many jump transpositions. Assuming the pattern of errors described above, on average it will miss between 4% and 5% of expected errors.
...
The ISBN Check (Modulus 11)
The ISBN modulus 11 (used for numberused for
Gloss | ||||
---|---|---|---|---|
|
Gloss | ||||
---|---|---|---|---|
|
Gloss | ||||
---|---|---|---|---|
|
Specref | ||
---|---|---|
|
|
Gloss | ||||
---|---|---|---|---|
|
Gloss | ||||
---|---|---|---|---|
|
Gloss | ||||
---|---|---|---|---|
|
Gloss | ||||
---|---|---|---|---|
|
Gloss | ||||
---|---|---|---|---|
|
Gloss | ||||
---|---|---|---|---|
|
between partitions and . Partitions could be a useful way of distinguishing developmental and released components and revising the partition and recalculating the would the
Gloss | ||||
---|---|---|---|---|
|
...
...
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
Gloss | ||||
---|---|---|---|---|
|
The majority of the undetected errors with both modulus 11 and Verhoeff result from additions or omissions of digits. Any methods Any
Gloss | ||||
---|---|---|---|---|
|