Fast error-correcting of embedded interaction codes
First Claim
Patent Images
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,
σ
x is the cyclic shift of m, and M is a subset of {circumflex over (M)} by(a) randomly selecting n bits b(0) from the set of bits b so as to leave remaining bits b(0),(b) determining a number of differing bits d(0) where d(0) is the number of different bits between ([b(0)]t,[ b(0)]t) and [r(0)]t(M(0), M(0)),(c) if the number of different bits d(0) is not zero, changing J bits of the n bits b(0) with J bits of b(0) to obtain n bits b(1) from the set of bits b so as to leave remaining bits b(0) and bits b(1) are different from bits b(0);
(d) updating r according to the following formula;
[r(1)]t=[r(0)]t[e(0)]tEl−
n[PRJ(0)]−
1Ekt[M(0)]−
1 (e) determining a number of differing bits d(1) where
d(1)=HammingWeight([e(0)]t +EJ P(0))+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 Assignments
0 Petitions
Accused Products
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.
-
Citations
6 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,
σ
x is the cyclic shift of m, and M is a subset of {circumflex over (M)} by(a) randomly selecting n bits b(0) from the set of bits b so as to leave remaining bits b (0),(b) determining a number of differing bits d(0) where d(0) is the number of different bits between ([b(0)]t,[ b (0)]t) and [r(0)]t(M(0),M (0)),(c) if the number of different bits d(0) is not zero, changing J bits of the n bits b(0) with J bits of b (0) to obtain n bits b(1) from the set of bits b so as to leave remaining bitsb (0) and bits b(1) are different from bits b(0);(d) updating r according to the following formula;
[r(1)]t=[r(0)]t[e(0)]tEl−
n[PRJ (0)]−
1Ekt[M(0)]−
1(e) determining a number of differing bits d(1) where
d(1)=HammingWeight([e(0)]t +EJ P(0))+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. - View Dependent Claims (2, 3, 4, 5, 6)
-
Specification