Essays/Check Sums

From J Wiki
Jump to: navigation, search

A check sum is a function on a vector-valued argument that provides a check on the correctness and/or uniqueness of the argument. This essay presents check sum computations for various codes.


Parity

The parity bit of a boolean vector v is ~:/v .

CRC

The CRC (cyclic redundancy check) can be computed using the foreign 128!:3 . For a well-chosen polynomial x (or for the monad 128!:3 ) it is highly improbable that (x 128!:3 y) = x 128!:3 y1 when y and y1 are not the same.

   crc=: 128!:3
   crc 'assiduously avoid any and all asinine alliterations'
1439575093
   crc 'assiduously avoid any and all asinine alliteratioms'
2128838646
   crc 'assiduously avoid any and all asinine alliteration'
_1000314142

SEDOL

A SEDOL is a 7-character alphanumeric string. The last character is a check digit computed as follows:

  • The digits 0-9 have values 0 to 9.
  • Letters have value 9 + their ordinal position in the alphabet. (e.g. A=10 and M=22).
  • A weighted sum of the values is computed, using weights 1 3 1 7 3 9
  • The check digit is the 10's complement of the weighted sum modulo 10.
sa =: '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
scd=: (841$'0987654321') {~ 1 3 1 7 3 9 +/ .*~ sa i. ]

   scd '026349'  NB. BAE Systems
4

The maximum weighted sum is 840 = 1 3 1 7 3 9 +/ .* #sa . If w is a weighted sum, the check digit is:

(-10|w) { '0123456789'
(10|w) { '0987654321'
w { 841 $ '0987654321'

CUSIP

A CUSIP is a 9-character alphanumeric string. The last character is a check digit computed as follows:

  • The digits 0-9 have values 0 to 9.
  • Letters have value 9 + their ordinal position in the alphabet. (e.g. A=10 and M=22).
  • Every other value is multipled by 2.
  • Values are converted to a string of single digits (43 becomes 4 3).
  • The check digit is the 10's complement of the sum of the digits.
ca =: '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
d1 =: [: +/"1 (+/"1 ] 10 10 #:   i.#ca) {~ ca i. 0 2 4 6 {"1 ]
d2 =: [: +/"1 (+/"1 ] 10 10 #: 2*i.#ca) {~ ca i. 1 3 5 7 {"1 ]
ccd=: (101$'0987654321') {~ d1 + d2

   ccd '93114210'  NB. Wal-Mart
3
   ccd '912827XN'  NB. US Treasury Note
7


   d=: +/"1 ] 10 10 #: 1 2 */ i.#ca
   $d
2 36
   >./"1 d
11 14
   +/ 8 $ >./"1 d
100
   +/ 8 $ >./"1 +/"1 ] 10 10 #: 1 2 */ i.#ca
100

The columns of d are the sums of digits for each character of the alphabet ca , with 0{d for characters in even positions and 1{d for characters in odd positions. 11 is the maximum sum-of-digits for the even characters and 14 is the maximum for the odd ones. The maximum total for sums-of-digits for an 8-character CUSIP is therefore 100 . If t is a total for sums-of-digits, the check digit is:

(-10|t) { '0123456789'
(10|t) { '0987654321'
t { 101 $ ''0987654321'

UPC

A UPC is a 12-digit string. The last digit is a check digit computed as follows:

  • A weighted sum of the first 11 digits is computed using weights 11$3 1 .
  • The check digit is the 10's complement of the sum.
ua =: '0123456789'
ucd=: (208$'0987654321') {~ (11$3 1) +/ .*~ ua i. ]

   ucd '03600029145'
2
   ucd '06038365031'
5

The maximum weighted sum is 207 = (11$3 1) +/ .* 9 . If w is a weighted sum, the check digit is:

(-10|w) { '0123456789'
(10|w) { '0987654321'
w { 208 $ '0987654321'

ISBN-10

A ISBN-10 is a 10-digit string. The last digit is a check digit computed as follows:

  • A weighted sum of the first 9 digits is computed using weights 10-i.9 .
  • The check digit is the 11's complement of the sum, with an X denoting the value 10 .
i10a =: '0123456789'
i10cd=: (487$'0X987654321') {~ (10-i.9) +/ .* i10a i. ]

   i10cd '030640615'
2

The maximum weighted sum is 486 = (10-i.9) +/ .* 9 . If w is a weighted sum, the check digit is:

(-11|w) { '0123456789X'
(11|w) { '0X987654321'
w { 487 $ '0X987654321'

ISBN-13

A ISBN-13 is a 13-digit string. The last digit is a check digit computed as follows:

  • A weighted sum of the first 12 digits is computed using weights 12$1 3 .
  • The check digit is the 10's complement of the sum.
i13a =: '0123456789'
i13cd=: (217$'0987654321') {~ (12$1 3) +/ .* i13a i. ]

   i13cd '978030640615'
7

The maximum weighted sum is 216 = (12$1 3) +/ .* 9 . If w is a weighted sum, the check digit is:

(-10|w) { '0123456789'
(10|w) { '0987654321'
w { 217 $ '0987654321'

Collected Definitions

parity=: ~:/

crc   =: 128!:3

NB. SEDOL
sa    =: '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
scd   =: (841$'0987654321') {~ 1 3 1 7 3 9 +/ .*~ sa i. ]

NB. CUSIP
ca    =: '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
d1    =: [: +/"1 (+/"1 ] 10 10 #:   i.#ca) {~ ca i. 0 2 4 6 {"1 ]
d2    =: [: +/"1 (+/"1 ] 10 10 #: 2*i.#ca) {~ ca i. 1 3 5 7 {"1 ]
ccd   =: (101$'0987654321') {~ d1 + d2

NB. UPC
ua    =: '0123456789'
ucd   =: (208$'0987654321') {~ (11$3 1) +/ .*~ ua i. ]

NB. ISBN-10
i10a  =: '0123456789'
i10cd =: (487$'0X987654321') {~ (10-i.9) +/ .* i10a i. ]

NB. ISBN-13
i13a  =: '0123456789'
i13cd =: (217$'0987654321') {~ (12$1 3) +/ .* i13a i. ]