Method for detecting common typing errors

• US 20020120905A1
• Filed: 02/26/2001
• Published: 08/29/2002
• Est. Priority Date: 02/26/2001
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Blaum, Mario, Kabelac, William J.
• Granted Patent: US 6,748,568 B2
• Time in Patent Office: Days
• US Class Current: 714/800
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit

Abstract

A method and apparatus for detecting typing errors of critical fixed series of characters (digits) by using at least one redundant parity digit. The invention detects the most common typing errors that involve both permutations and incorrect striking of adjacent characters during data entry via a keyboard of an electronic apparatus. The method provides warning to the data input operator when incorrect data entry occurs and optionally automatically suspends entry thereof.

Claims

1. A method for verifying proper data entry into an electronic apparatus using a data entry device, the method comprising:

encoding and storing a predetermined series of n-characters from an alphabet of size M using a modulo M arithmetic encoding algorithm not requiring characters foraneous to said alphabet, whereby a resultant encoded series of characters adds at least one stored parity character to said predetermined series of n-characters;

entering an entered series of characters using said data entry device;

recomputing secondary parity character(s) from first n-characters of said entered series of characters using said encoding algorithm;

comparing said stored parity character(s) with corresponding said secondary parity character(s); and

preventing data entry if said parity character(s) comparison of said secondary parity character(s) and said stored parity character(s) are different.

2. The method in claim 1, wherein said encoding algorithm comprises:

representing each of said series of n-characters from an alphabet of size M by-an integer between 0 and M−

1;

establishing an n-integer vector u=(u₀, u₁, . . . , u<sub>n−

1</sub>), wherein each of said integers u, corresponds to a character in said alphabet of size M, and each u₁ is an integer between 0 and M−

1; and

encoding said n-integer vector u=(u₀, u₁, . . . , u<sub>n−

1</sub>) by appending to said u at least one parity-integer r, wherein r is determined by taking a residue modulo M of an inner product of vector u with a weight vector of integers modulo M w=(w₀, w₁, . . . , w<sub>n−

1</sub>).

3. The method in claim 2, wherein differences w₁−

w₁₊₁ of consecutive weight integers w₁ and w₁₊₁ in said weight vector w=(w₀, w₁, . . . , w<sub>n−

1</sub>) are invertible as integers modulo M as well as the sum w<sub>n−

1</sub>+1 of the last integer w<sub>n−

1</sub> with the integer 1.

4. The method in claim 3, wherein said M is 10, and digits in said weight vector w=(w₀, w₁, . . . w_n−

1) are selected so that said digits . . . w<sub>n−

5</sub>w<sub>n−

3</sub>w<sub>n−

1</sub> belong in the set {2, 4, 6, 8} and said digits . . . w<sub>n−

6</sub>w<sub>n−

4</sub>w<sub>n−

2</sub> belong in the set {1, 3, 7, 9}.

5. The method in claim 1, wherein said encoding algorithm comprises:

representing each of said series of n characters in an alphabet of M characters by an integer between 0 and M−

1;

establishing an n-integer vector u(u₀, u₁, . . . , u<sub>n−

1</sub>), wherein each of said integers u₁ corresponds to a character in said alphabet of size M, and each u₁ is an integer between 0 and M−

1; and

encoding said n-integer vector u=(u₀, u₁, . . . , u<sub>n−

1</sub>) by appending to said u a plurality of parity integers r₀, r₁, . . . , r<sub>L−

1</sub>, wherein each said r_j is determined by taking the residue modulo M of the inner product of vector u with a weight vector w_j=(w_j,0, w_j,1, . . . , w<sub>j,n−

1</sub>).

6. The method in claim 5, wherein the vectors w_j are chosen so that in an L×

(n+L) matrix formed by appending to an L×

n matrix whose rows are said vectors w_j the L×

L identity matrix, any L×

L matrix obtained by taking L consecutive columns in said L×

(n+L) matrix is invertible in the ring of integers modulo M.

7. The method in claim 1, wherein said encoding algorithm comprises:

choosing a first q such that said q is a prime power and q≧

M;

adding foraneous characters, if necessary, to said alphabet of M characters until a new set of q characters is obtained;

establishing a primitive element a in the finite field GF(q);

representing one of the q characters in said extended set of characters by 0 and the remaining characters by the q−

1 powers a) of a^j wherein j runs from 0 to q−

2;

establishing an n-character vector u=(u₀, u₁, . . . , u<sub>n−

1</sub>), wherein each character u₁ is either 0 or a power of a dependent upon said representation; and

encoding said n-character vector u=(u₀, u₁,. . , u<sub>n−

1</sub>) by appending to said u a plurality of parity characters r₀, r₁, . . . , r<sub>L−

1</sub>, wherein each said r_j is determined by taking an inner product of vector u with a weight vector w_j=(w_j,0, w_j,1, . . . , w<sub>j,n−

1</sub>) wherein said characters w_j,i are powers of said primitive element “

a”

according to said representation.

8. The method in claim 7, wherein consecutive characters w_0,1 and w_0,1+1 in first of said weight vectors w₀=(w_0,0, w_0,1, . . . , w_0,n−

1) are different and a last character w<sub>0, n−

1</sub>, is different from a character corresponding to −

1 in GF(q).

9. The method in claim 7, wherein said vectors w_j are chosen so that in an L×

(n+L) matrix composed by appending to an L×

n matrix whose rows are said vectors w_j the L×

L identity matrix, any L×

L matrix obtained by taking L consecutive columns in said L×

(n+L) matrix is invertible in the field GF(q).

10. The method in claim 1, further comprising providing a warning when said comparison of said parity character(s) are different.

11. The method in claim 10, wherein said warning can be deactivated.

12. The method in claim 10, wherein said warning suspends data entry.

13. The method in claim 1, wherein said fixed series of characters comprise numerical digits.

14. The method in claim 1, wherein said fixed series of characters comprise alphabetical letters, alphanumeric signs, and symbols;

whereby said characters are entered through said data entry device.

15. The method in claim 1, wherein said method is used for detecting improper entry of a social security number.

17. The apparatus in claim 16, wherein said apparatus implements said encoding algorithm and generates said at least one parity character(s) by:

representing each of said series of n-characters from an alphabet of size M by an integer between 0 and M−

1;

establishing an n-integer vector u=(u₀, u₁, . . . , u<sub>n−

1</sub>), wherein each of said integers u₁ corresponds to a character in said alphabet of size M, and each u₁ is an integer between 0 and M−

1; and

encoding said n-integer vector u=(u₀, u₁, . . . , u<sub>n−

1</sub>) by appending to said u at least one parity-integer r, wherein r is determined by taking a residue modulo M of an inner product of vector u with a weight vector of integers modulo M, w=(w₀, w₁, . . . , w<sub>n−

1</sub>).

18. The apparatus in claim 17, wherein differences w₁−

w₁₊₁ of consecutive weight integers w₁ and w₁₊₁ in said weight vector w=(w₀, w₁, . . . , w<sub>n−

1</sub>) are invertible as integers modulo M as well as the sum w<sub>n−

1</sub>+1 of the last integer w<sub>n−

1</sub> with the integer 1.

19. The apparatus in claim 18, wherein said M is 10, and digits in said weight vector w=(w₀, w₁, . . . , w_n−

1) are selected so that said digits . . . w<sub>n−

5</sub>w<sub>n−

3</sub>w<sub>n−

1</sub> belong in the set {2,4,6, 8} and said digits . . . w<sub>n−

6</sub>w<sub>n−

4</sub>w<sub>n−

2</sub> belong in the set { 1, 3, 7, 9}.

20. The apparatus in claim 16, wherein said encoding algorithm where multiple parity characters are generated comprises:

representing each of said series of n characters in an alphabet of M characters by an integer between 0 and M−

1;

establishing an n-integer vector u=(u₀, u₁, . . . , u<sub>n−

1</sub>) wherein each of said integers u, corresponds to a character in said alphabet of size M, and each u₁ is an integer between 0 and M−

1; and

encoding said n-integer vector u=(u₀, u₁, . . . , u<sub>n−

1</sub>) by appending to said u a plurality of parity integers r₀, r₁, . . . , r<sub>L−

1</sub>, wherein each said r_j is determined by taking the residue modulo M of the inner product of vector u with a weight vector w_j=(w_j,0, w_j,1, . . . , w<sub>j,n−

1</sub>).

21. The apparatus in claim 20, wherein said weight vectors w_j are selected so that in an L×

(n+L)-matrix formed by appending to an L×

n-matrix whose rows are said vectors w_j L×

L identity matrix, any L×

L matrix obtained by taking L consecutive columns in said L×

(n+L) matrix is invertible in the ring of integers modulo M.

22. The apparatus in claim 16, wherein said encoding algorithm comprises:

choosing a first q such that said q is a prime power and q≧

M;

adding foraneous characters, if necessary, to said alphabet of M characters until a new set of q characters is obtained;

establishing a primitive element a in the finite field GF(q);

representing one of the q characters in said extended set of characters by 0 and the remaining characters by the q−

1 powers a^j of a, wherein j runs from 0 to q−

2;

establishing an n-character vector u=(u₀, u₁, . . . , u<sub>n−

1</sub>), wherein each character u₁ is either 0 or a power of a dependent upon said representation; and

encoding said n-character vector u=(u₀, u₁, . . . , u<sub>n−

1</sub>) by appending to said u a plurality of parity characters r₀, r₁, . . . , r<sub>L−

1</sub>, wherein each said r_j is determined by taking an inner product of vector u with a weight vector w_j=(w_j,0, w₁. . . , w<sub>j,n−

1</sub>) wherein said characters w_j,1 are powers of said primitive element “

a”

according to said representation.

23. The apparatus in claim 22, wherein consecutive characters w_0,1 and w_0,1+1 in first of said weight vector wo=(w_0,0, w_0,1, . . . , w_0,n−

1) are different and a last character w_0,n−

is different from a character corresponding to −

1 in GF(q).

24. The apparatus in claim 22, wherein said vectors are chosen so that in said L×

(n+L)-matrix composed by appending to an L×

n matrix whose rows are said vectors w_j the L×

L identity matrix, any L×

L matrix obtained by taking L consecutive columns in said L×

(n+L) matrix is invertible in the field GF(q).

25. The apparatus in claim 16, wherein said gate device is a warning device that activates when said parity characters are different.

26. The apparatus in claim 16, wherein said gate device includes a bypass for deactivation.

27. The apparatus in claim 16, wherein said gate device includes an human perceivable output device that simultaneously activates when data entry is suspended.

29. The device in claim 28, wherein said encoding algorithm comprises:

representing each of said series of n-characters from an alphabet of size M by an integer between 0 and M−

1;

establishing an n-integer vector u=(u₀, u₁, . . . , u<sub>n−

1</sub>), wherein each of said integers u₁ corresponds to a character in said alphabet of size M, and each u₁ is an integer between 0 and M−

1; and

encoding said n-integer vector u=(u₀, u₁, . . . , u<sub>n−

1</sub>) by appending to said u at least one parity-integer r, wherein r is determined by taking a residue modulo M of an inner product of vector u with a weight vector of integers modulo M w=(w₀, w₁, . . . , w<sub>n−

1</sub>).

30. The device in claim 29, wherein differences of consecutive weight integers w₁ and w₁₊₁ in said weight vector w=(w₀, w₁, . . . , w_n−

1) are invertible as integers modulo M as well as the sum w<sub>n−

1</sub>+1 of the last integer w<sub>n−

1</sub> with the integer 1.

31. The device in claim 30, wherein said M is 10, and digits in said weight vector w=(w₀, w₁, . . . , w_n−

1) are selected so that said digits . . . w<sub>n−

5</sub>w<sub>n−

3</sub>w<sub>n−

1</sub> belong in the set {2, 4, 6 , 8} and said digits. w<sub>n−

6</sub>w<sub>n−

4</sub>w<sub>n−

2</sub> belong in the set {1, 3, 7, 9}.

32. The device in claim 28, wherein said encoding algorithm for generating multiple parity characters comprises:

representing each of said series of n characters in an alphabet of M characters by an integer between 0 and M−

1;

establishing an n-integer vector u=(u₀, u₁, . . . , u<sub>n−

1</sub>), wherein each of said integers u, corresponds to a character in said alphabet of size M, and each u₁ is an integer between 0 and M−

1; and

encoding said n-integer vector u=(u₀, u₁, . . . , u<sub>n−

1</sub>) by appending to said u a plurality of parity integers r₀, r₁, . . . , r<sub>L−

1</sub>, wherein each said r₁ is determined by taking the residue modulo M of the inner product of vector u with a weight vector w_j=(w_j,0, w_j,1. . . , w<sub>j,n−

1</sub>).

33. The device in claim 32, wherein said weight vectors w_j are selected so that in an L×

(n+L) matrix formed by appending to an L×

n-matrix whose rows are said vectors w_j the L×

L identity matrix, any L×

L matrix obtained by taking L consecutive columns in said L×

(n+L) matrix is invertible in the ring of integers modulo M.

34. The device in claim 28, wherein said encoding algorithm comprises:

choosing a first q such that said q is a prime power and q≧

M;

adding foraneous characters, if necessary, to said alphabet of M characters until a new set of q characters is obtained;

establishing a primitive element a in the finite field GF(q).

representing one of the q characters in said extended set of characters by 0 and the remaining characters by the q−

1 powers a^j of a, wherein j runs from 0 to q−

2;

establishing an n-character vector u=(u₀, u₁, . . . , u<sub>n−

1</sub>), wherein each character u₁ is either 0 or a power of a dependent upon said representation; and

encoding said n-character vector u=(u₀, u₁, . . . , u<sub>n−

1</sub>) by appending to said u a plurality of parity characters r₀, r₁, . . . , r<sub>L−

1</sub>, wherein each said r_j is determined by taking an inner product of vector u with a weight vector w_j=(w_j,0, w_j,1, . . . , w<sub>j,n−

1</sub>), wherein said characters w_j,1 are powers of said primitive element “

a”

according to said representation.

35. The device in claim 34, wherein consecutive characters w_0,1 and w_0,1+1 in first of said weight vector w₀=(w_0,0, w_0,1, . . . , w_0,n−

1) are different and a last character w<sub>0,n−

1</sub> is different from a character corresponding to −

1 in GF(q).

36. The device in claim 34, wherein said vectors w_j are chosen so that in said L×

(n+L) matrix composed by appending to an L×

n matrix whose rows are said vectors w_j the L×

L identity matrix, any L×

L matrix obtained by taking L consecutive columns in said L×

(n+L) matrix is invertible in the field GF(q).

37. The device in claim 28, further comprising providing an output warning when said parity character(s) are different.

38. The device in claim 37, wherein said warning includes a bypass mode for deactivating said warning.

39. The device in claim 37, wherein said warning includes suspending data entry.

40. The device in claim 28, wherein said series of characters comprise numerical digits.

41. The device in claim 28, wherein said series of characters comprise alphabetical letters.

16. An electronic apparatus for verifying proper data entry into said apparatus using a data entry device, said apparatus comprising:

a memory that stores a predetermined series of n-characters from an alphabet of size M using a modulo M arithmetic encoding algorithm not requiring characters foraneous to said alphabet, whereby each predetermined and encoded series of n-characters adds at least one stored parity character thereto;

a data entry encoder that recomputes secondary parity character(s) using said encoding algorithm when n-characters are entered through said data entry device;

a comparator that compares said stored and secondary parity character(s); and

a gate device for disabling data entry if said parity character(s) are different.

28. A program storage device readable by a machine, tangibly embodying a program of instructions executable by said machine to perform a method for verifying proper data entry into said machine using a data entry device, said method comprising:

encoding and storing a predetermined series of n-characters from an alphabet of size M using a modulo M arithmetic encoding algorithm not requiring characters foraneous to said alphabet, whereby a resultant encoded series of characters adds at least one stored parity character to said predetermined series of n-characters;

entering an entered series of characters using said data entry device;

recomputing secondary parity character(s) from first n-characters of said entered series of characters using said encoding algorithm;

comparing said stored parity character(s) with corresponding said secondary parity character(s); and

preventing data entry if said parity character(s) comparison of said secondary parity character(s) and said stored parity character(s) are different.