Fast error-correcting of embedded interaction codes

• US 20090027241A1
• Filed: 05/31/2005
• Published: 01/29/2009
• 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
• Granted Patent: US 7,729,539 B2
• Time in Patent Office: Days
• US Class Current: 341/94
• 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 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;

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 is the cyclic shift of m, 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 differing 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 differing bits d⁽¹⁾ where

d⁽¹⁾=HammingWeight([e⁽⁰⁾]^t +E_J P⁽⁰⁾)+J,

(f) repeating (a)˜

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

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

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⁽⁰⁾:

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

(b) determining a number of differing 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, flipping J bits of the n bits b⁽⁰⁾ to obtain n bits b⁽¹⁾;

(d) update r according to the following formula;

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

1</sup>

(e) determining a number of differing bits d⁽¹⁾ where

d⁽¹⁾=HammingWeight([e⁽⁰⁾]^t+E_JP⁽⁰⁾)+J,

(f) repeating (a)˜

(d) for some estimated times in order to ensure a high probability of successful decoding;

(g) 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 recited in claim 1, where the n bits of b⁽⁰⁾ are selected by Gaussian elimination.

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

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

determining a position of bits s in an m-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 recited in claim 1, farther comprising:

solving multiple-dimension m-arrays simultaneously.