Fast error-correcting of embedded interaction codes

• US 7,729,539 B2
• Filed: 05/31/2005
• Issued: 06/01/2010
• Est. Priority Date: 05/31/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Qiang, Wang, Jian, Lin, Zhouchen
• Primary Examiner(s): Chang; Jon
• Application Number:
  US11/142,844
• Publication Number:
  US 20090027241A1
• Time in Patent Office: 1,827 Days
• Field of Search: 382/181, 382/291, 714/781, 714/755, 714/758, 715/230, 715/232, 715/233
• US Class Current: 382/181
• CPC Class Codes: G06V 10/17 using hand-held instruments
• CPC Class Codes: G06V 10/19 by sensing codes defining pattern positions
• CPC Class Codes: H03M 13/00 Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes error detection or error correction for analogue/digital, digital/analogue or code conversion H03M1/00 – H03M11/00; specially adapted for digital computers G06F11/08; for information storage based on relative movement between record carrier and transducer G11B, e.g. G11B20/18; for static stores G11C
• CPC Class Codes: H03M 13/03 Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
• CPC Class Codes: H03M 13/47 Error detection, forward error correction or error protection, not provided for in groups H03M13/01 - H03M13/37
• CPC Class Codes: H03M 13/611 Specific encoding aspects, e.g. encoding by means of decoding

Abstract

A fast decoding technique for decoding a position of a bit in a pattern provided on a media surface that can generate large amounts of solution candidates quickly by switching or flipping bits and utilizing a recursion scheme. The fast decoding technique may be employed to simultaneously decode multiple dimensions of a pattern on the media surface.

Claims

1. A method, preformed by a computer having a memory and a processor, of determining a position of a bit s in a pattern formed from a binary sequence array m of order n, comprising:

capturing an image of a portion of the pattern such that the captured image includes at least n bits b of the array m;

with a processor, solving for r where b=rM,

$\hat{M}=\left(\begin{array}{c}{m}^t\\ \mathrm{\sigma <br><br>}<br><br>\left(m^t\right)\\ \mathrm{⋮<br><br>}\\ {\mathrm{\sigma <br><br>}}^{n-1}<br><br>\left(m^t\right)\end{array}\right),$

 

σ

^x (m^t)_is the x^th_cyclic shift of m^t, and M is a subset of {circumflex over (M)} by;

(a) randomly selecting n bits b⁽⁰⁾ from the set of bits b so as to leave remaining bits b⁽⁰⁾,

(b) determining a number of different bits d⁽⁰⁾ where d⁽⁰⁾ is the number of different bits between ([b⁽⁰⁾]^t,[ b⁽⁰⁾]^t) and [r⁽⁰⁾]^t(M⁽⁰⁾, M⁽⁰⁾),

(c) if the number of different bits d⁽⁰⁾ is not zero, changing J bits of the n bits b⁽⁰⁾ with J bits of b⁽⁰⁾ to obtain n bits b⁽¹⁾ from the set of bits b so as to leave remaining bits b⁽¹⁾ and bits b⁽¹⁾ are different from bits b⁽⁰⁾,

(d) updating r according to the following formula;

[r⁽¹⁾]^t=[r⁽⁰⁾]^t+[e⁽⁰⁾]^tE<sub>l−

n</sub>[P_RJ⁽⁰⁾]<sup>−

1</sup>E_k^t[M⁽⁰⁾]<sup>−

1</sup>,

(e) determining a number of different bits d⁽¹⁾ where d⁽¹⁾=HammingWeight([e⁽⁰⁾]^t+E_jP⁽⁰⁾)+J,

(f) repeating (a)˜

(d) an estimated number of times in order to ensure a high probability of successful decoding, and

(g) outputting r that corresponds to the smallest value of d; and

with a processor, employing a discrete logarithm technique to obtain the location of s in r.

2. The method recited in claim 1, further comprising:

obtaining bits b⁽¹⁾ from bits b⁽⁰⁾ by flipping J bits in b⁽⁰⁾ by;

(h) randomly selecting n bits b⁽⁰⁾ from the set of bits b so as to leave remaining bits b⁽⁰⁾,

(i) determining a number of different bits d⁽⁰⁾ where d⁽⁰⁾ is the number of different bits between ([b⁽⁰⁾]^t,[ b⁽⁰⁾]^t) and [r⁽⁰⁾]^t(M⁽⁰⁾, M⁽⁰⁾),

(j) if the number of different bits d⁽⁰⁾ is not zero, flipping J bits of the n bits b⁽⁰⁾ to obtain n bits b⁽¹⁾,

(k) updating r according to the following formula;

[r⁽¹⁾]^t=[r⁽⁰⁾]^tE_J[M⁽⁰⁾]<sup>−

1 ,</sup>

(l) determining a number of different bits d⁽¹⁾ where d⁽¹⁾=HammingWeight([e⁽⁰⁾]^t+E_{j P}⁽⁰⁾)+J,

(m) repeating (h)˜

(k) for some estimated times in order to ensure a high probability of successful decoding, and

(n) outputting r that corresponds to the smallest value of d; and

employing a discrete logarithm technique to obtain the location of s in r.

3. The method of claim 1, where the n bits of b⁽⁰⁾ are selected by Gaussian elimination.

4. The method of claim 1, wherein the position of the bit s in the array corresponds to a geometric position of the bit s on a writing media.

5. The method of claim 1, further comprising:

determining a position of bits s in an array having a first dimension and a second dimension; and

determining a cyclical shift between the bits s so as to identify the cyclical shift between the first dimension and the second dimension.

6. The method of claim 1, further comprising:

solving multiple-dimension arrays simultaneously.

7. A computer-readable storage medium containing instructions that, when executed by a computer having a memory and a processor, cause the computer to perform a method for determining a position of a bit s in a pattern formed from a binary sequence array m of order n, the method comprising:

capturing an image of a portion of the pattern, the image including bits b of the array m ;

solving for r where b =rM,

$\hat{M}=\left(\begin{array}{c}{m}^t\\ \mathrm{\sigma <br><br>}<br><br>\left(m^t\right)\\ \mathrm{⋮<br><br>}\\ {\mathrm{\sigma <br><br>}}^{n-1}<br><br>\left(m^t\right)\end{array}\right),$

 

σ

^x (m^t) is the x^th cyclic shift of m^t , and M is a subset of M, at least in part by;

(a) randomly selecting bits b⁽⁰⁾ from the set of bits b so as to leave remaining bits b ⁽⁰⁾,

(b) determining a number of different bits, d⁽⁰⁾, ([b⁽⁰⁾]^t,[ b⁽⁰⁾]^t) and [r⁽⁰⁾]^t(M⁽⁰⁾, M⁽⁰⁾),

(c) if the number of different bits d⁽⁰⁾ is not zero, changing J bits of b⁽⁰⁾ with J bits of b ⁽⁰⁾ to obtain b⁽¹⁾, wherein bits b⁽¹⁾ are different from bits b⁽⁰⁾,

(d) updating r according to the following formula;

[r⁽¹⁾]^t=[r⁽⁰⁾]^t[e⁽⁰⁾]^tE<sub>l−

n</sub>[P_RJ⁽⁰⁾]<sup>−

1</sup>E_k^t[M⁽⁰⁾]<sup>−

1,</sup>

(e) determining a number of different bits d⁽¹⁾ , where d⁽¹⁾=HammingWeight([e⁽⁰⁾]^t+E_JP⁽⁰⁾)+J, and

(f) outputting r corresponding to the smallest value of d; and

employing a discrete logarithm technique to obtain the location of s in the output r.

8. The computer-readable storage medium of claim 7, the method further comprising:

obtaining bits b⁽¹⁾ from bits b⁽⁰⁾ by flipping J bits in b⁽¹⁾ by;

randomly selecting bits b⁽¹⁾ from b so as to leave remaining bits b ⁽⁰⁾ ,

determining a number of different bits, d⁽⁰⁾, between, ([b⁽⁰⁾]^t,[ b⁽⁰⁾]^t) and [r⁽⁰⁾]^t(M⁽⁰⁾, M⁽⁰⁾) ,

if the number of different bits d⁽⁰⁾ is not zero, flipping J bits of b⁽⁰⁾ to obtain bits b⁽¹⁾,

updating r according to the following formula;

[r⁽¹⁾]^t=[r⁽⁰⁾]^tE_J[M⁽⁰⁾]<sup>−

1,</sup>

determining a number of different bits d⁽¹⁾ where d⁽¹⁾=HammingWeight([e⁽⁰⁾]^t+E_JP⁽⁰⁾)+J, and

outputting r corresponding to the smallest value of d.

9. The computer-readable storage medium of claim 7 wherein the randomly selected bits b⁽⁰⁾ are selected from b by Gaussian elimination.

10. The computer-readable storage medium of claim 7 wherein the position of the bit s in the array corresponds to a geometric position of the bit s on a writing media.

11. The computer-readable storage medium of claim 7, the method further comprising:

determining a position of bits s in an array having a first dimension and a second dimension; and

determining a cyclical shift between the bits s so as to identify the cyclical shift between the first dimension and the second dimension.

12. The computer-readable storage medium of claim 7, the method further comprising:

solving multiple-dimension arrays simultaneously.

13. The computer-readable storage medium of claim 7, wherein solving for r further comprises:

repeating (a)˜

(d) to increase a probability of successful decoding.

14. A computing device having a memory and a processor for determining a position of a bit s in a pattern formed from a binary sequence array m of order n, comprising:

a component that captures an image of a portion of the pattern, the captured image including bits b of the array m ; and

a component that. with a processor, solves for r where b=rM,

$\hat{M}=\left(\begin{array}{c}{m}^t\\ \mathrm{\sigma <br><br>}<br><br>\left(m^t\right)\\ \mathrm{⋮<br><br>}\\ {\mathrm{\sigma <br><br>}}^{n-1}<br><br>\left(m^t\right)\end{array}\right),$

 

σ

^x(m^t) is the x^th cyclic shift of m^t , and M is a subset of {circumflex over (M)} by;

selecting bits b⁽⁰⁾ from bits b leaving bits b ⁽⁰⁾ ,

determining a number of different bits, d⁽⁰⁾, between ([b⁽⁰⁾]^t,[ b⁽⁰⁾]^t) and [r⁽⁰⁾]^t(M⁽⁰⁾, M⁽⁰⁾) ,

updating r according to the following formula;

[r⁽¹⁾]^t=[r⁽⁰⁾]^t[e⁽⁰⁾]^tE<sub>l−

n</sub>[P_RJ⁽⁰⁾]<sup>−

1</sup>E_k^t[M⁽⁰⁾]<sup>−

1</sup>,

determining a number of different bits d⁽¹⁾ where d⁽¹⁾=HammingWeight([e⁽⁰⁾]^t+E_JP⁽⁰⁾)+J, and

outputting r that corresponds to the smallest value of d.

15. The computing device of claim 14, further comprising:

a component that obtains bits b⁽¹⁾ from bits b⁽⁰⁾ by flipping J bits in b⁽⁰⁾ by;

randomly selecting bits b⁽⁰⁾ from the set of bits b so as to leaving bits b ⁽⁰⁾ ,

determining a number of different bits, d⁽⁰⁾, between ([b⁽⁰⁾]^t,[ b⁽⁰⁾]^t) and [r⁽⁰⁾]^t([M⁽⁰⁾, M⁽⁰⁾]) ,

if d⁽⁰⁾ is not zero, flipping J bits of bits b⁽⁰⁾ to obtain bits b⁽¹⁾, updating r according to the following formula;

[r⁽¹⁾]^t=[r⁽⁰⁾]^t=E_j[M⁽⁰⁾]<sup>−

1,</sup>

determining a number of different bits d⁽¹⁾ where d⁽¹⁾=HammingWeight([e⁽⁰⁾]^t+E_JP⁽⁰⁾)+J, and

outputting r corresponding to the smallest value of d.

16. The computing device of claim 14 wherein bits b⁽¹⁾ are selected by Gaussian elimination.

17. The computing device of claim 16 wherein the position of the bit s in the array corresponds to a geometric position of the bit s on a writing media.

18. The computing device of claim 17, further comprising:

a component that determines a position of bits s in an array having a first dimension and a second dimension; and

a component that determines a cyclical shift between the bits s so as to identify the cyclical shift between the first dimension and the second dimension.

19. The computing device of claim 18, further comprising:

a component that solves multiple-dimension arrays simultaneously.

20. The computing device of claim 19, further comprising:

a component that employs a discrete logarithm technique to obtain the location of s in the output r.