Method and apparatus for providing error correction to symbol level codes

Claim 1

A method for providing a check character for an arbitrary sequence of M information symbols selected from set of N code symbols, said method comprising the steps of: assigning a sequence of N distinct numerical character values to said M code symbols; assigning a position j for said check character within a set of M + 1 numerically labelled positions, said positions corresponding to said M information character positions and said one check character position, said check character being initially assigned a numerical character value of 0 and said positions other than position j being assigned in accordance with said arbitrary sequence of information symbols; forming the sum F o , of the character values associated with all code symbols having positions bearing an odd position number, said sum being carried out modulo N; forming the sum F e , of the character values associated with all code symbols having positions bearing an even position number, said sum being carried out modulo N; forming the check sum F o + 2 F e modulo N; forming the character value for position j, CV(j), as [(N-1)/2] · F, said multiplication being carried out modulo N, the brackets denoting the greatest integer less than or equal to the value of the numerical expression (N-1)/2; and assigning the code symbol having character value CV(j) to check position j.

Claim 2

A method for providing a check character for an arbitrary sequence of M information symbols selected from set of N code symbols, said method comprising the steps of: assigning a sequence of N distinct numerical character values to said M code symbols; assigning a position j for said check character within a set of M + 1 numerically labelled positions, said positions corresponding to said M information character positions and said one check character position, said check character being initially assigned a numerical character value of 0 and said positions other than position j being assigned in accordance with said arbitrary sequence of information symbols; forming the sum F o , of the character values associated with all code symbols having positions bearing an odd position number, said sum being carried out modulo N; forming the sum F e , of the character values associated with all code symbols having positions bearing an even position number, said sum being carried out modulo N; forming the check sum F o + 2 F e modulo N; forming the character value for position j, CV(j), as [(N-1)/2] · F, said multiplication being carried out modulo N, the brackets denoting the greatest integer less than or equal to the value of the numerical expression (N-1)/2; and assigning the code symbol having character value CV(j) to check position j.

Claim 4

The method of claims 1 or 2 in which said positions are labelled in numerical order from left to right.

Claim 5

The method of claims 1 or 2 in which positions are labelled in numerical order from right to left.

Claim 6

A method for correcting a received sequence of coded character symbols having one erasure, said method comprising the steps of: setting the initial character value of position j, CV(j), equal to 0, where j denotes the position of the erasure; forming the sum, F o , of preassigned character values associated with said character symbols, said summation being carried out for all sequence positions having an odd position number, said summation being carried out modulo N where N is the number of code symbols; forming the sum, F e , of preassigned character values associated with said character symbols, said summation being carried out for all sequence positions having an even position number, said summation being carried out modulo N; forming the check sum F as F o + 2 F e modulo N; computing the character value of the erasure position, CV(j), as -F modulo N if j is odd and as [(N-1)/2] · F modulo N if j is even, the brackets denoting the greatest integer less than or equal to the value of the numerical expression (N- 1)/2; and associating a corrected erasure position character symbol with character value CV(j) in accordance with said preassigned character value association.

Claim 7

A method for correcting a received sequence of coded character symbols having one erasure, said method comprising the steps of: setting the initial character value of position j, CV(j), equal to 0, where j denotes the position of the erasure; forming the sum, F o , of preassigned character values associated with said character symbols, said summation being carried out for all sequence positions having an odd position number, said summation being carried out modulo N where N is the number of code symbols; forming the sum, F e , of preassigned character values associated with said character symbols, said summation being carried out for all sequence positions having an even position number, said summation being carried out modulo N; forming the check sum F as F o + 2 F e modulo N; computing the character value of the erasure position, CV(j), as -F modulo N if j is odd and as [(N-1)/2] · F modulo N if j is even, the brackets denoting the greatest integer less than or equal to the value of the numerical expression (N- 1)/2; and associating a corrected erasure position character symbol with character value CV(j) in accordance with said preassigned character value association.

Claim 10

An apparatus for providing a check character for an arbitrary sequence of M information symbols selected from a set of N code symbols, said apparatus comprising: means (20) for generating a unique numerical character value, from a set of N distinct values for each of said M symbols; means (22) for forming the sum F e modulo N of said numerical character values associated with even positions within said sequence of M symbols; means (23) for forming the sum F o modulo N of said numerical character values associated with odd positions within said sequence of M symbols; means (24, 25) for forming the sum F = F o + 2 F e modulo N; means (26) for computing the character value, CV(j), as [(N-1)/2] · F modulo N, where j denotes the check position, and the brackets denote the greatest integer less than or equal to the value of the numerical expression (N-1)/2; and means (27) for generating the code symbol associated with character value CV(j).

Claim 11

An apparatus for providing a check character for an arbitrary sequence of M information symbols selected from a set of N code symbols, said apparatus comprising: means (20) for generating a unique numerical character value, from a set of N distinct values for each of said M symbols; means (22) for forming the sum F e modulo N of said numerical character values associated with even positions within said sequence of M symbols; means (23) for forming the sum F o modulo N of said numerical character values associated with odd positions within said sequence of M symbols; means (24, 25) for forming the sum F = F o + 2 F e modulo N; means (26) for computing the character value, CV(j), as [(N-1)/2] · F modulo N, where j denotes the check position, and the brackets denote the greatest integer less than or equal to the value of the numerical expression (N-1)/2; and means (27) for generating the code symbol associated with character value CV(j).

Claim 13

The apparatus of claims 8 or 9 in which j is not equal to M + 1 and said sums F o and F e are computed with position j being associated with a character value 0.

Claim 14

An apparatus for correcting a received coded sequence of character symbols having one check symbol, said apparatus comprising: means (11) for detecting the position location j of an erasure in said received sequence; means (12) for generating a unique numerical character value, from set of N distinct values, for each symbol of said received sequence of symbols, the generator producing a value of 0 for said erasure position; means (13) for forming the sum F e modulo N of said numerical character values associated with even positions within said received sequence; means (14) for forming the sum F o modulo N of said numerical character values associated with odd positions within said received sequence; means (15) for forming a check sum F as F o + 2 F e modulo N; means (16) for computing the character value associated with erasure position j, CV(j), as -F modulo N upon the condition that j is odd and as [(N-1)/2] · F modulo N upon the condition that j is even, the brackets denoting the greatest integer less than or equal to the value of the numerical expression (N-1)/2; and means (17) for generating the code symbol associated with character value CV(j).

Claim 15

An apparatus for correcting a received coded sequence of character symbols having one check symbol, said apparatus comprising: means (11) for detecting the position location j of an erasure in said received sequence; means (12) for generating a unique numerical character value, from set of N distinct values, for each symbol of said received sequence of symbols, the generator producing a value of 0 for said erasure position; means (13) for forming the sum F e modulo N of said numerical character values associated with even positions within said received sequence; means (14) for forming the sum F o modulo N of said numerical character values associated with odd positions within said received sequence; means (15) for forming a check sum F as F o + 2 F e modulo N; means (16) for computing the character value associated with erasure position j, CV(j), as -F modulo N upon the condition that j is odd and as [(N-1)/2] · F modulo N upon the condition that j is even, the brackets denoting the greatest integer less than or equal to the value of the numerical expression (N-1)/2; and means (17) for generating the code symbol associated with character value CV(j).

Claim 17

The method and apparatus of any of the preceeding claims characterised by their use in identifying silicon wafers.