
BoostCommit : 
Subject: [Boostcommit] svn:boost r74340  sandbox/SOC/2011/checks/libs/checks/doc
From: pierre.talbot.6114_at_[hidden]
Date: 20110911 03:54:03
Author: trademark
Date: 20110911 03:54:02 EDT (Sun, 11 Sep 2011)
New Revision: 74340
URL: http://svn.boost.org/trac/boost/changeset/74340
Log:
Add content for the weighted sum: two statements.
Text files modified:
sandbox/SOC/2011/checks/libs/checks/doc/algorithm.qbk  31 +++++++++++++++++++++++
1 files changed, 23 insertions(+), 8 deletions()
Modified: sandbox/SOC/2011/checks/libs/checks/doc/algorithm.qbk
==============================================================================
 sandbox/SOC/2011/checks/libs/checks/doc/algorithm.qbk (original)
+++ sandbox/SOC/2011/checks/libs/checks/doc/algorithm.qbk 20110911 03:54:02 EDT (Sun, 11 Sep 2011)
@@ 22,7 +22,8 @@
The main difference with these algorithms (and the other checksum algorithms
such as CRC or cryptographic hashes) is that we don't analyse the binary
content of the number of the lexical values meaning, so "123" is equivalent to [~123].
+content of the sequence but the lexical values meaning, so "123" is equivalent to [~123].
+It also means we could skip the undesirable values.
[section:checksum_algorithm Checksum algorithms]
@@ 36,13 +37,13 @@
5 + 8 + 2 + 1 + 5 + 4 + 7 + 8 = 40
``
The check digit would be [~40] and the complete sequence [~5821547840]. The size of
+The check digit would be [~40] so the complete sequence [~5821547840]. The size of
the check digit grown with the sum.
[h5 Modular sum]
We must restrict the check digit's size so we take the remainder of the sum by a choosen
number. The modulus will impact the range of the check digit. For example, the supports
+modulus. This will impact the range of the check digit. For example, the supports
for 3 types of modulus is implemented in Boost.Checks, the following table points the
differents modulus:
@@ 50,7 +51,7 @@
[ [Modulus] [Check digit range] [Check digit size] ]
[ [10] [ 0 to 9 ] [1] ]
[ [11] [ 0 to 10 ] [1] ]
[ [97] [ 0 to 97 ] [2] ]
+[ [97] [ 0 to 96 ] [2] ]
]
The range of the modulus 11 is restrained to an unique check digit where [~10] is replaced
@@ 62,16 +63,30 @@
addition is ['commutative], so the digit order is not important. The solution is to
attribute fixed ['weight] to each position.
+The choice of the weight pattern should respect the following statments:
Some simple rules:
+# The weights must be less than the modulus. The explanation is:
+
+``
+If weight = modulus, than weight = 0.
+And if weight = modulus + 1, than weight = 1.
+Finally if weight = modulus + n, than weight = n % modulus.
+``
+
+# The weights must be coprime to the modulus. It means the greatest common divisor between
+the weight and the modulus is 1. If a and b are not coprime to the modulus, than
+it exists a number n that verify the following equation:
+
+``
+a * n % modulus = b * n % modulus
+``
+
+And this number is a common divisor between a,b and the modulus.
# The weights must be less than the modulus.
# The weights must be coprime to the modulus.
# [HS] An error in the checksum is detected if  new_checksum  checksum  != modulus.
# [HS] The assertion: "new_checksum == checksum" doesn't mean that the number is errorfree.
Digits can be compensated or the check digit altered.

The weight pattern is always a limited sequence that can be repetitive. For example: [~137]
is not repetitive on a sequence with less than 4 numbers but will on a greater sequence.
BoostCommit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk