Transcript Modular Arithmetic, The Codabar System, and applications

Modular Arithmetic, The Codabar
System, and applications
0011 0010 1010 1101 0001 0100 1011
1
Tomás Cometto and Daniel Stokley
Linear Systems
5/1/06
2
4
Modular Arithmetic
Mod 3
0011 0010 1010 1101 0001 0100 1011
• A way of expressing a
set of integers as their
remainder when
divided by any
positive integer n.
• In other words, all
numbers in mod n
must be contained in
the set 0 to n – 1.
+
0
1
0
0
1
1
1
2
2
2
1
2
2
4
2
0
0
1
More Mod Madness
0011 0010 1010 1101 0001 0100 1011
Numbers
Vectors
• Mod 5
• 1+ 4 + 2 + 3 + 4 + 1 +
3=?
• 18 = ?
• 3
• [3, 1, 2] • [4, 0, 1]
• = 12 + 0 + 2 = 14 = 4.
1
2
4
Codabar System
0011 0010 1010 1101 0001 0100 1011
• Every Credit and Debit card is identified by
a 16-digit number, but the bank only issues
the first 15 numbers. The last number is
calculated by this codabar system.
• Approach: take the first (issued) 15
numbers of the credit card, label the last
number d, and place these in the vector X of
length 16.
1
2
4
• The Codabar System uses the check vector C
= {2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1}, also of
length
16.0001 0100 1011
0011 0010
1010 1101
• Instead of simply solving for X•C = 0, we
introduce h, number of digits in odd positions
greater than 4 (in the original 15).
• Solve C•X + h = 0, in mod(10)
• Let’s see why Danny’s credit card gave him
problems.
1
2
4
5164846218486456
0011 0010 1010 1101 0001 0100 1011
•
•
•
•
•
•
•
•
X = {5,1,6,4,8,4,6,2,1,8,4,8,6,4,5,d}
C = {2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1}
h=6
X•C + h = 2(5+6+8+6+1+4+6+5) +
(1+4+4+2+8+8+4+d) +6 =0
= 2(41) + 37 + d = 0
= 2(1) + 7 + d =0
=9+d=0
Thus, d must be 1, not 6.
1
2
4
0011 0010 1010 1101 0001 0100 1011
•
•
1
2
4
UPCs originate with a company called the Uniform Code
Council (UCC). A manufacturer applies to the UCC for
permission to enter the UPC system. The manufacturer
pays an annual fee for the privilege.
BYG Publishing's manufacturer identification number is the
first six digits of the UPC number -- 639382. The next five
digits -- 00039 -- are the item number.
Universal Product Code (UPC)
0011 0010 1010 1101 0001 0100 1011
• UPC bar codes were originally created to help grocery
stores speed up the checkout process and keep better track
of inventory, but the system quickly spread to all other
retail products because it was so successful.
• Just like the first 15 numbers on a credit card are issued by
the bank, the first n -1 numbers of a bar code are issued by
the manufacturer, and the nth number is a check digit.
• Use check vector {3,1,3,1,3…}
• Typically, for UPCs, we don’t use h. We just solve X•C =
0.
• ISBN Codes for Library Items
1
2
4