Totally Disjoint 3-Digit Decimal Check Digit Codes
Larry A. Dunning · 2025
Read Totally Disjoint 3-Digit Decimal Check Digit Codes by Larry A. Dunning (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-05326.txt.
Introduction
A check digit catches a mistyped number, and the best codes catch swaps and twin errors too. Larry Dunning extends a classic line of such codes. Verhoeff's 1969 designs protected two information digits with one check digit. Stacking ten disjoint versions would yield a longer code, a long-standing wish. Dunning presents three pairwise disjoint three-digit codes of that family.
His codes carry a rare bonus. The mere multiset of digits in a codeword, ignoring order, determines the whole word. That kills the cyclic errors Verhoeff wanted gone. Mix-ups between spoken forms, like eighty and eighteen style confusions, are also blocked. Small codes still hold elegant structure, and this one polishes a fifty-year-old design toward completeness.
Catalog record
| CREATOR | Larry A. Dunning |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 11 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-05326
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Totally Disjoint 3-Digit Decimal Check Digit Codes Thanks: ©The author, [email protected], grants copyright permissionsas specified in Creative Commons License CC BY-SA 4.0. (See Endnote 2) Larry A. Dunning Abstract Abstract: In 1969 J. Verhoeff provided the first examples of a decimal error detecting code using a single check digit to provide protection against all single, transposition and adjacent twin errors. The three versions of such a code that he presented are length 3-digit codes with 2 information digits. Existence of a 4-digit code would imply the existence of 10 such disjoint 3-digit codes. This paper presents 3 pairwise disjoint 3-digit codes. The codes developed herein, have the property that the knowledge of the multiset of digits included in a word is sufficient to determine the entire codeword even though their positions were unknown. Thus the codes are permutation-free, and this fulfills his desire to eliminate cyclic errors. Phonetic errors, where 2 digit pairs of the forms X0 and 1X are interchanged, are also eliminated. Index Terms: Decimal error detection, disjoint coding, transposition errors, twin errors, phonetic errors, permutation-free. I Verhoeff’s 3-digit Decimal Codes In his 1969 monograph Jacobus Verhoeff [ 7 , \Rightarrow ] presented three variations of a “curious 3-digit decimal code", derived from a block design. The arguably best of these is shown in Table \Rightarrow I . Each table entry S(r,c) gives the middle digit, s , of the codeword (rsc) throughout this paper, allowing a simpler correspondence between properties of the code table and the requirements for detecting various error types. These are detailed in Table \Rightarrow II . All three codes contained all the triple codewords of the form (xxx) , as is reflected by the main diagonal of Table \Rightarrow I , and do not detect triple errors. The code shown in Table \Rightarrow I is preferred because it catches all but 16 cyclic errors and detects phonetic errors. The 3 pairwise disjoint codes developed in Section \Rightarrow III have the permutation-free property. II Disjoint Codinng On page 19 of his seminal manuscript J. Verhoeff [ 7 , \Rightarrow ] noted that multiple pairwise-disjoint check-digit codes could be of use when multiple organizations “like different bank branches” utilize the same system of assignment for e.g. account numbers. The identification of the branch then serves as an additional check while account numbers would be unique across the system. For the three disjoint codes developed here, 100 lockers at each of three locations would have 300 uniquely numbered lockers. Table I : Verhoeff’s Irregular Code S 0 1 2 3 4 5 6 7 8 9 0 0 3 4 9 6 7 5 8 2 1 1 5 1 0 2 8 3 9 6 7 4 2 7 6 2 4 1 0 8 9 3 5 3 1 5 8 3 7 6 4 0 9 2 4 2 9 7 5 4 8 1 3 0 6 5 6 7 9 0 3 5 2 4 1 8 6 3 8 1 7 5 9 6 2 4 0 7 9 4 5 8 2 1 0 7 6 3 8 4 0 6 1 9 2 3 5 8 7 9 8 2 3 6 0 4 7 1 5 9 On page 38 Verhoeff [ 7 , \Rightarrow ] continued: It is remarkable that up to now no pure decimal codes, with a redundancy of one check digit are known, which detect all single errors, all transpositions and all twin errors. Even a 4-digit code with these properties would imply the existence of 10 pairwise-disjoint 3-digit codes. The 3 codes presented in Section \Rightarrow III fall far short, albeit with some enhanced error detection. Table II : Detection Conditions for Tables "S" of 3-digit Error Patterns Error Types All Rows All Columns Main Diagonal Single(*) \neg\;abc\leftrightarrow abd \neg\;acd\leftrightarrow bcd permutation permutation Transposition \neg\;abc\leftrightarrow acb \neg\>abc\leftrightarrow bac No 2-cycles No 2-cycles Twin \neg\;abb\leftrightarrow acc \neg\;aac\leftrightarrow bbc \leq 1 fixed point \leq 1 fixed point J. Transposition \neg\;abc\leftrightarrow cab asymmetric J. Twin \neg\;aca\leftrightarrow bcb permutation Triple \neg\;aaa\leftrightarrow bbb \leq 1 fixed point Phonetic Left \forall e:0\neq S(S(1,c),c)\implies\forall x\>\neg\;1xe\leftrightarrow x0c Phonetic Right \forall r:1\neq S(r,S(r,0))\implies\forall x\>\neg\;r1x\leftrightarrow rx0 Cyclic \forall a,b:b\neq S(S(a,b),a)\implies\forall x\>\neg\;axb\leftrightarrow xba Permutation Given codewords abc,xyz Free multiset(abc)=multiset(xyz)\implies\;abc=xyz (*) Function:S(r,c)\implies\neg\;abd\leftrightarrow acd III Disjoint Permutation-Free Decimal Codes The three codes shown in Table \Rightarrow III are pairwise disjoint and each provides protection against all the error types listed in Table \Rightarrow II . Within each code, the knowledge of the multiset of digits (with multiplicity) in a codeword is sufficient to determine the codeword. This permutation-free property implies all the properties of Table \Rightarrow II except for triple error and phonetic error detection. The codes shown do, however, each protect against all triple and phonetic errors \Rightarrow 1 . No knowledge beyond this point in the manuscript is required to use the codes. One of the three tables can suffice, if desired, as the codewords in each are a rotation of the codewords in the other two. For example, note the that code words (100), (010) and (001) are found in Table \Rightarrow III (a), (b) and (c) respectively. The subscripts annotating the codewords were used in the construction of the codes and are explained in Section \Rightarrow IV . Table III : The Disjoint Decimal Codes (a) Rotated Left S 0 1 2 3 4 5 6 7 8 9 0 2 7 4 8 0 6 3 5 1 9 1 0 8 5 1 9 3 4 6 2 7 2 9 1 7 4 5 0 2 8 3 6 3 1 9 2 5 6 4 8 3 7 0 4 6 5 8 3 1 7 9 2 0 4 5 3 0 6 2 4 9 7 1 5 8 6 8 6 3 7 2 5 0 9 4 1 7 7 3 1 0 8 2 6 4 9 5 8 5 4 0 9 3 8 1 7 6 2 9 4 2 9 6 7 1 5 0 8 3 (b) From Search S 0 1 2 3 4 5 6 7 8 9 0 1 c 3 0 l 5 9 8 4 7 r 6 2 1 5 2 c 9 7 8 4 6 r 0 1 l 3 2 8 7 3 c 6 0 1 5 2 l 4 9 r 3 7 1 r 5 4 c 2 3 l 9 6 0 8 4 0 r 4 l 6 8 5 c 2 3 9 7 1 5 2 9 7 1 3 6 c 0 4 8 r 5 l 6 6 l 8 2 r 0 1 9 7 c 5 3 4 7 9 5 4 3 r 7 l 0 1 8 c 2 6 8 4 0 1 2 6 5 r 8 l 3 9 c 7 9 3 6 8 9 l 4 r 7 2 1 5 0 c (c) Rotated Right S 0 1 2 3 4 5 6 7 8 9 0 4 0 5 9 8 1 6 3 2 7 1 8 3 1 0 4 7 9 2 6 5 2 0