...

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__5Table 1. 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

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	8	7	6	5	9	3	2	1	0	4

...

9

8

7

6

5

4

3

2

1

0

...

0

...

1

...

2

...

3

...

4

...

5

...

6

...

7

...

8

...

9

...

0

...

0

...

1

...

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 3. The Inverse D5 array

...

0

...

1

...

2

...

3

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 ))

...

Info
A live version of an HTML form and JavaScript is available in section 5.4.1. SNOMED CT Identifier Check.

Sample Visual Basic for computing Verhoeff's Dihedral Check

Code Block

language	vbxml
theme	Eclipse
title	Visual Basic HTML Code for Check-Digit ComputationForm Calling the JavaScript below
collapse	true

<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)&nbsp; </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&nbsp; </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

language	js
theme	Eclipse
title	Java Script Code for SCTID Validation and Check-Digit Computation
collapse	true

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;");
	document.getElementById("component").innerText ="Invalid partition";
	document.getElementById("component").setAttribute("style","color:green;");
	document.getElementById("extnamespace").innerText ="No namespace";
	document.getElementById("extnamespace").setAttribute("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,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","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

language	vb
theme	Eclipse
title	Visual Basic Code for Check-Digit Computation
collapse	true

Option Explicit
Private Dihedral(9) 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

...

In the explanations above, a is not equal to b, but c can be any decimal digit.

...

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 fornumberfor

Gloss

t	UK NHS

number) 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 singlein as a single

Gloss

t	check-digit

in about 9% of cases. The ISBN convention is to use "X" to represent thevalue the

Gloss

t	check-digit

value 10 but this is incompatible with an Integer (data type) representation. Thenumber integer representation. The

Gloss

t	UK NHS

number uses this check-sum but regards and number generating a check-sum of 10 as an invalid identifier. This approach could be applied to thebut the

Gloss

t	SCTID

but this would render 9% of possible values unusable in each partition and

Gloss

t	namespace

. This would prevent a simple sequence of values from being allocated as the "item" within each item identifier within any

Gloss

t	namespace

. More significantly the unusable itemwould differ in eachor unusable item identifier would differ in each

Gloss

t	namespace

or partition and this would prevent simple transpositions of itembetween partitions and. item identifiers between partitions and

Gloss

t	namespaces

.

Partitions could be a useful way of distinguishing developmental and released components and revising the partition and recalculating thewould the

Gloss

t	check-digit

would 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 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 decimaland decimal

Gloss

t	check-digit

and 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. Anymethods Any

Gloss

t	check-digit

method 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).

Search

Versions Compared

Old Version 8

New Version 9

Key

Sample Visual Basic for computing Verhoeff's Dihedral Check

Sample Visual Basic for computing Verhoeff's Dihedral Check

A brief comparison of check-digit effectiveness

The IBM Check

The ISBN Check (Modulus 11)

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

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

Search

Page History

Versions Compared

Old Version 8

New Version 9

Key

Sample Visual Basic for computing Verhoeff's Dihedral Check

Sample Visual Basic for computing Verhoeff's Dihedral Check

A brief comparison of check-digit effectiveness

The IBM Check

The ISBN Check (Modulus 11)

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