On check character systems over quasigroups and loops
In this article we study check character systems that is error detecting codes, which arise by appending a check digit an to every word a₁a₂...an₋₁ : a₁a₂...an₋₁ → a₁a₂...an₋₁an with the check formula (...((a₁ · δa₂) · δ ²a₃)...) · δ ⁿ⁻²an₋₁) · δ ⁿ⁻¹an = c, where Q(·) is a quasigroup or a loop, δ is...
Збережено в:
| Дата: | 2003 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2003
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/155694 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | On check character systems over quasigroups and loops / G.B. Belyavskaya // Algebra and Discrete Mathematics. — 2003. — Vol. 2, № 2. — С. 1–13. — Бібліогр.: 9 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-155694 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1556942019-06-18T01:28:12Z On check character systems over quasigroups and loops Belyavskaya, G.B. In this article we study check character systems that is error detecting codes, which arise by appending a check digit an to every word a₁a₂...an₋₁ : a₁a₂...an₋₁ → a₁a₂...an₋₁an with the check formula (...((a₁ · δa₂) · δ ²a₃)...) · δ ⁿ⁻²an₋₁) · δ ⁿ⁻¹an = c, where Q(·) is a quasigroup or a loop, δ is a permutation of Q, c ∈ Q. We consider detection sets for such errors as transpositions (ab → ba), jump transpositions (acb → bca), twin errors (aa → bb) and jump twin errors (aca → bcb) and an automorphism equivalence (a weak equivalence) for a check character systems over the same quasigroup (over the same loop). Such equivalent systems detect the same percentage (rate) of the considered error types. 2003 Article On check character systems over quasigroups and loops / G.B. Belyavskaya // Algebra and Discrete Mathematics. — 2003. — Vol. 2, № 2. — С. 1–13. — Бібліогр.: 9 назв. — англ. 1726-3255 2001 Mathematics Subject Classification: 20N05, 20N15, 94B60, 94B65. http://dspace.nbuv.gov.ua/handle/123456789/155694 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
In this article we study check character systems that is error detecting codes, which arise by appending a check digit an to every word a₁a₂...an₋₁ : a₁a₂...an₋₁ → a₁a₂...an₋₁an with the check formula (...((a₁ · δa₂) · δ ²a₃)...) · δ ⁿ⁻²an₋₁) · δ ⁿ⁻¹an = c, where Q(·) is a quasigroup or a loop, δ is a permutation of Q, c ∈ Q. We consider detection sets for such errors as transpositions (ab → ba), jump transpositions (acb → bca), twin errors (aa → bb) and jump twin errors (aca → bcb) and an automorphism equivalence (a weak equivalence) for a check character systems over the same quasigroup (over the same loop). Such equivalent systems detect the same percentage (rate) of the considered error types. |
| format |
Article |
| author |
Belyavskaya, G.B. |
| spellingShingle |
Belyavskaya, G.B. On check character systems over quasigroups and loops Algebra and Discrete Mathematics |
| author_facet |
Belyavskaya, G.B. |
| author_sort |
Belyavskaya, G.B. |
| title |
On check character systems over quasigroups and loops |
| title_short |
On check character systems over quasigroups and loops |
| title_full |
On check character systems over quasigroups and loops |
| title_fullStr |
On check character systems over quasigroups and loops |
| title_full_unstemmed |
On check character systems over quasigroups and loops |
| title_sort |
on check character systems over quasigroups and loops |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2003 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/155694 |
| citation_txt |
On check character systems over quasigroups and loops / G.B. Belyavskaya // Algebra and Discrete Mathematics. — 2003. — Vol. 2, № 2. — С. 1–13. — Бібліогр.: 9 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT belyavskayagb oncheckcharactersystemsoverquasigroupsandloops |
| first_indexed |
2025-07-14T07:52:44Z |
| last_indexed |
2025-07-14T07:52:44Z |
| _version_ |
1837608012308545536 |
| fulltext |
Jo
ur
na
l A
lg
eb
ra
D
is
cr
et
e
M
at
h.Algebra and Discrete Mathematics RESEARCH ARTICLE
Number 2. (2003). pp. 1–13
c© Journal “Algebra and Discrete Mathematics”
On check character systems over quasigroups
and loops
G. B. Belyavskaya
Communicated by Kashu A.I.
Abstract. In this article we study check character systems
that is error detecting codes, which arise by appending a check digit
an to every word a1a2...an−1 : a1a2...an−1 → a1a2...an−1an with
the check formula (...((a1 · δa2) · δ
2a3)...) · δ
n−2an−1) · δ
n−1an = c,
where Q(·) is a quasigroup or a loop, δ is a permutation of Q, c ∈ Q.
We consider detection sets for such errors as transpositions (ab →
ba), jump transpositions (acb → bca), twin errors (aa → bb) and
jump twin errors (aca → bcb) and an automorphism equivalence
(a weak equivalence) for a check character systems over the same
quasigroup (over the same loop). Such equivalent systems detect
the same percentage (rate) of the considered error types.
1. Introduction
A check character (or digit) system with one check character is an error
detecting code over an alphabet Q which arises by appending a check
digit an to every word a1a2 . . . an−1 ∈ Qn−1:
a1a2 . . . an−1 → a1a2 . . . an−1an.
In praxis the examples used are among others the following: the Euro-
pean Article Number (EAN) Code, the Universal Product Code (UPC),
The research described in this publication was made possible in part by Award No.
MM2-3017 of the Moldovan Research and Development Association (MRDA) and the
U.S. Civilian Research & Development Foundation for the Independent States of the
Former Soviet Union (CRDF).
2001 Mathematics Subject Classification: 20N05, 20N15, 94B60, 94B65.
Key words and phrases: quasigroup, loop, group, automorphism, check char-
acter system, code.
Jo
ur
na
l A
lg
eb
ra
D
is
cr
et
e
M
at
h.2 On check character systems over quasigroups and loops
the International Book Number (ISNB) Code, the system of the serial
numbers of German banknotes.
The control digit an+1 can calculate by different check formulas (check
equations), in particular, with the help of a quasigroup (a loop, a group)
Q(·).
The most general check formula is the following:
(. . . ((a1 · δ1a2) · δ2a3) . . .) · δn−1an = c,
where Q(·) is a quasigroup, c is a fixed element of Q, δ1, δ2, . . . , δn−1 are
some fixed permutations of Q.
Such a system is called a system over a quasigroup and always detects
all single errors (that is errors in only one component of a code word) and
can detect other errors of certain patterns arisen during transmission of
date if the quasigroup Q(·) has some properties.
The work [9] of J.Verhoeff is the first significant publication relating
to these systems with a survey the decimal codes known in the 1970s. The
statistical sampling made by J.Verhoeff shows that such errors (of human
operators) as single errors (a → b), adjacent transpositions (ab → ba),
jump transpositions (acb → bca), twin errors (aa → bb) and jump twin
errors (aca → bcb) can arise, where single errors and transpositions are
the most prevalent ones.
A.Ecker and G.Poch in [5] have given a survey of check character sys-
tems and their analysis from a mathematical point of view. In particular,
the group-theoretical background of the known systems was explained
and new codes were presented that stem from the theory quasigroups.
Studies of check character systems over groups and abelian groups
are continued by R.-H.Shulz in a number of papers. In [4] H.M.Damm
surveys the results about check character systems over groups and over
quasigroups and studies the last ones.
In the article [1] ([2]) the check character systems over arbitrary quasi-
groups (over T-quasigroups) Q(·) with the control equations
an = (. . . ((a1 · δa2) · δ
2a3) · . . .) · δ
n−2an−1 (1)
and
(. . . (((a1 · δa2) · δ
2a3) · . . .) · δ
n−2an−1) · δ
n−1an = c ∈ Q, (2)
which detect completely single errors, transpositions, jump transposi-
tions, twin errors and jump twin errors, were investigated.
In this article we continue research of check character systems with
the check formula (2) over quasigroups and loops. In particular, we con-
sider detection sets of the pointed errors and two equivalences between
Jo
ur
na
l A
lg
eb
ra
D
is
cr
et
e
M
at
h.G. B. Belyavskaya 3
permutations δ of Q from (2) (between the related systems over the same
quasigroup). Namely, we introduce an automorphism equivalence of per-
mutations for a quasigroup and a weak equivalence of permutations for
a loop. These equivalences are generalization of the respective equiv-
alence relations considered by J.Verhoeff in [9],H.M.Damm in [4] and
R.-H. Schulz in [6,7,8] for the check character systems over groups and
characterize systems over the same quasigroup (loop) detecting the same
percentage of the considered errors.
2. Check character systems over a quasigroup
In Table 2 of [6] R.-H. Schulz gives an information about detection of er-
rors by check character systems over a group Q(·) with the check formula
(2), n > 3. Namely, he reduces detection sets and a rate (percentage) of
detection of different error types for these systems. This information we
give in Table 1, where
MT ={(a, b) ∈ Q2 | a · δb 6= b · δa, a 6= b},
MJT ={(a, b, c) ∈ Q3 | ab · δ2c 6= cb · δ2a, b 6= c},
MTE ={(a, b) ∈ Q2 | a · δa 6= b · δb, a 6= b},
MJTE ={(a, b, c) ∈ Q3 | ab · δ2a 6= cb · δ2c, a 6= c}.
Table 1. Detection of errors by check character systems
over groups of order q
Error type Detection set Percentage of detection
transpositions MT |MT |/q(q − 1)
jump transpositions MJT |MJT |/q2(q − 1)
twin errors MTE |MTE |/q(q − 1)
jump twin errors MJTE |MJTE |/q2(q − 1)
Let Q(·) be an arbitrary quasigroup. In [1] the following statement (The-
orem 3) is proved.
Theorem 1 ([1]). A check character system using a quasigroup Q(·)
and coding (2) for n > 4 is able to detect all
I. single errors;
II. transpositions iff for all a, b, c, d ∈ Q with b 6= c in the quasigroup
Q(·) the inequalities (α1) b · δc 6= c · δb and (α2) ab · δc 6= ac · δb hold;
III. jump transpositions iff Q(·) has properties (β1) bc · δ2d 6= dc · δ2b
and (β2) (ab · c) · δ2d 6= (ad · c) · δ2b for all a, b, c, d ∈ Q, b 6= d;
Jo
ur
na
l A
lg
eb
ra
D
is
cr
et
e
M
at
h.4 On check character systems over quasigroups and loops
IV. twin errors iff Q(·) has properties (γ1) b · δb 6= c · δc and (γ2)
ab · δb 6= ac · δc for all a, b, c ∈ Q, b 6= c;
V jump twin errors iff in Q(·) the inequalities (σ1) bc · δ2b 6= dc · δ2d
and (σ2) (ab · c) · δ2b 6= (ad · c) · δ2d hold for all a, b, c, d ∈ Q, b 6= d.
Denote the check character system over a quasigroup Q(·) with the
check formula (2), n > 4 by S(Q(·), δ). Define for it detection sets
M δ
T , M δ
JT , M δ
TE , M δ
JTE
of transpositions, jump transpositions, twin errors, jump twin errors re-
spectively in the following way
M δ
T = U δ
1 ∪ V δ
1 , where U δ
1 = {(b, c) ∈ Q2 | b · δc 6= c · δb, b 6= c}, V δ
1 =
{(a, b, c) ∈ Q3 | ab · δc 6= ac · δb, b 6= c};
M δ
JT = U δ
2 ∪ V δ
2 , where U δ
2 = {(b, c, d) ∈ Q3 | bc · δ2d 6= dc · δ2b, b 6=
d}, V δ
2 = {(a, b, c, d) ∈ Q4 | (ab · c) · δ2d 6= (ad · c) · δ2b, b 6= d};
M δ
TE = U δ
3 ∪V δ
3 , where U δ
3 = {(b, c) ∈ Q2 | b · δb 6= c · δc, b 6= c}, V δ
3 =
{(a, b, c) ∈ Q3 | ab · δb 6= ac · δc, b 6= c};
M δ
JTE = U δ
4 ∪ V δ
4 , where U δ
4 = {(b, c, d) ∈ Q3 | bc · δ2b 6= dc · δ2d, b 6=
d}, V δ
4 = {(a, b, c, d) ∈ Q4 | (ab · c) · δ2b 6= (ad · c) · δ2d, b 6= c}.
Remark 1. If Q(·) is a quasigroup, then from (b, c) ∈ U δ
1 , (b, c, d) ∈ U δ
2 ,
(b, c) ∈ U δ
3 , (b, c, d) ∈ U δ
4 it can follow respectively that (a, b, c) ∈ V δ
1 ,
(a, b, c, d) ∈ V δ
2 , (a, b, c) ∈ V δ
3 , (a, b, c, d) ∈ V δ
4 for some a ∈ Q and
conversely. For example, if (b, c) ∈ U δ
1 (∈ U δ
3 ) and the elements b, c are
such that fb = fc = a (where fbb = b, fcc = c), then (a, b, c) ∈ V δ
1 (∈ V δ
3 )
for this element a and conversely: if (a, b, c) ∈ V δ
1 and a = fb = fc,
then (b, c) ∈ U δ
1 . When (b, c, d) ∈ U δ
2 (∈ U δ
4 ) and fb = fd = a, then
(a, b, c, d) ∈ V δ
2 (∈ V δ
4 ) and conversely.
The set U δ
i , i = 1, 2, 3, 4, points out the corresponding detected errors
in the first digits of code words, while the set V δ
i , i = 1, 2, 3, 4, defines the
detected errors in the rest positions beginning with the second position.
Generally, the sets U δ
i and V δ
i are dependent, moreover, for quasi-
groups with the left identity e the set V δ
i completely defines the set U δ
i
(by a = e) i = 1, 2, 3, 4.
Now we note that
max(|U δ
i |) = q(q − 1), max(|V δ
i |) = q2(q − 1) for i = 1, 3
and
max(|U δ
i |) = q2(q − 1), max(|V δ
i |) = q3(q − 1) for i = 2, 4,
Jo
ur
na
l A
lg
eb
ra
D
is
cr
et
e
M
at
h.G. B. Belyavskaya 5
so
max(|U δ
i | + |V δ
i |) = q(q2 − 1) for i = 1, 3
and
max(|U δ
i | + |V δ
i |) = q2(q2 − 1) for i = 2, 4.
Taking into account Remark 1 and above mentioned we can estimate
percentage (rate) rδ of detection errors for the system S(Q(·), δ) over a
quasigroup Q(·) in the following Table 2.
Table 2. Detection of errors by systems over quasigroups of order q
Error types Detection set Percentage of detection
transpositions M δ
T = U δ
1 ∪ V δ
1 rδ
1 6
(|Uδ
1
|+|V δ
1
|)
q(q2−1)
jump transpositions M δ
JT = U δ
2 ∪ V δ
2 rδ
2 6
(|Uδ
2
|+|V δ
2
|)
q2(q2−1)
twin errors M δ
TE = U δ
3 ∪ V δ
3 rδ
3 6
(|Uδ
3
|+|V δ
3
|)
q(q2−1)
jump twin errors M δ
JTE = U δ
4 ∪ V δ
4 rδ
4 6
(|Uδ
4
|+|V δ
4
|)
q2(q2−1)
Let Q(·) be a quasigroup with the left identity e (ex = x for all x ∈ Q)
or a loop with the identity e (ex = xe = x for all x ∈ Q).
In this case elements (e, b, c) from V δ
1 (from V δ
3 ), (e, b, c, d) from V δ
2
(from V δ
4 ) define the elements (b, c) of U δ
1 (of U δ
3 ), (b, c, d) of U δ
2 (of
U δ
4 ) respectively and conversely. So we obtain percentage of detection in
Table 3.
Table 3. Detection of errors by systems over quasigroups with a left
identity or over loops of order q
Error type Detection set Percentage of detection
transpositions M δ
T = V δ
1 rδ
1 = |V δ
1 |/q2(q − 1)
jump transpositions M δ
JT = V δ
2 rδ
2 = |V δ
2 |/q3(q − 1)
twin errors M δ
TE = V δ
3 rδ
3 = |V δ
3 |/q2(q − 1)
jump twin errors M δ
JTE = V δ
4 rδ
4 = |V δ
4 |/q3(q − 1)
If Q(·) is a group, then it is evident that
(b, c) ∈ U δ
1 ((b, c) ∈ U δ
3 ) iff (a, b, c) ∈ V δ
1 ((a, b, c) ∈ V δ
3 )
and
(b, c, d) ∈ U δ
2 ((b, c, d) ∈ U δ
4 ) iff (a, b, c, d) ∈ V δ
2 ((a, b, c, d) ∈ V δ
4 ),
where a is an arbitrary element of Q.
Jo
ur
na
l A
lg
eb
ra
D
is
cr
et
e
M
at
h.6 On check character systems over quasigroups and loops
Hence, the sets V δ
1 , V δ
2 , V δ
3 , V δ
4 define completely the sets U δ
1 , U δ
2 ,
U δ
3 , U δ
4 respectively and we have the rate of error detection in Table 1,
since
|V δ
i | = q|U δ
i |, i = 1, 2, 3, 4,
and
rδ
i = |V δ
i |/q2(q − 1) = |U δ
i |/q(q − 1), i = 1, 3,
rδ
i = |V δ
i |/q3(q − 1) = |U δ
i |/q2(q − 1), i = 2, 4.
By analogy with the check character systems over groups (see [6]) we
give the following
Definition 1. A permutation δ2 is called automorphism equivalent to a
permutation δ1 (δ2 ∼ δ1) for a quasigroup Q(·) if there exists an auto-
morphism α of Q(·) such that
δ2 = αδ1α
−1.
Let AutQ(·) denote the group of automorphisms of a quasigroup Q(·).
The following proposition for quasigroups repeats Proposition 6.6 of
[6] for groups.
Proposition 1. (i) Automorphism equivalence is an equivalence relation
(that is reflexive, symmetric and transitive).
(ii) If δ1 and δ2 are automorphism equivalent for a quasigroup Q(·),
then the systems S(Q(·), δ1) and S(Q(·), δ2) detect the same percentage
of transpositions (jump transpositions, twin errors, jump twin errors).
Proof. (i) Straight forward calculation.
(ii) Let α ∈ AutQ(·), δ2 = αδ1α
−1, (b, c) ∈ U δ1
1 , that is b·δ1c 6= c·δ1b,
then α(b · δ1c) 6= α(c · δ1b), αb · αδ1c 6= αc · αδ1b or αb · αδ1α
−1(αc) 6=
αc · αδ1α
−1(αb).
Hence, (αb, αc) ∈ U δ2
1 .
If (a, b, c) ∈ V δ1
1 , that is ab·δ1c 6= ac·δ1b, then (αa·αb)·αδ1α
−1(αc) 6=
(αa · αc) · αδ1α
−1(αb). Thus, (αa, αb, αc) ∈ V δ2
1 .
It is evident that if (b, c) ∈ U δ1
1 and (a, b, c) ∈ V δ1
1 , then (αb, αc) ∈ U δ2
1
and (αa, αb, αc) ∈ V δ2
1 and conversely, that is
|M δ1
T | = |M δ2
T |.
The other cases follow in a similar way.
Taking into account this proposition we can say that the systems
S(Q(·), δ1) and S(Q(·), δ2) with δ1 ∼ δ2 are automorphism equivalent
with respect to all considered error types.
Jo
ur
na
l A
lg
eb
ra
D
is
cr
et
e
M
at
h.G. B. Belyavskaya 7
3. Equivalence of check character systems over loops
Consider the system S(Q(·), δ), where Q(·) is a loop with the identity e.
The detection sets and a percentage of detection for these systems are
given in Table 3.
In [6] the following equivalence between two permutations δ1 and δ2
on Q is defined for a group Q(·).
Permutations δ1 and δ2 are called weak equivalent if there exist ele-
ments a, b ∈ Q and an automorphism α ∈ AutQ(·) such that
δ2 = Raα
−1δ1αLb, a, b ∈ Q,
where Rax = xa, Lax = ax for all x ∈ Q.
We shall generalize the weak equivalence for a loop using the concept
of a nucleus of a loop.
Recall that the left, right, middle nuclei of a loop Q(·) are respectively
the sets [3]:
Nl = {a ∈ Q| ax · y = a · xy for all x, y ∈ Q},
Nr = {a ∈ Q|x · ya = xy · a for all x, y ∈ Q},
Nm = {a ∈ Q|xa · y = x · ay for all x, y ∈ Q}.
The nucleus N of a loop is intersection of the left, right and middle nuclei:
N = Nl ∩ Nr ∩ Nm.
All these nuclei are subgroups in the loop [3]. In a group Q(·) the nucleus
N coincides with Q.
Definition 2. A permutation δ2 of a set Q is called weakly equivalent to
a permutation δ1 (δ2
w
∼ δ1) for a loop Q(·) if there exist an automorphism
α of the loop and elements p, q ∈ N such that
δ2 = Rpαδ1α
−1Lq,
where Rpx = xp, Lqx = qx, N is the nucleus of the loop.
It is evident that if δ2 ∼ δ1, then δ2
w
∼ δ1 (by p = q = e). Note, that
if p ∈ N, α ∈ AutQ(·), then αN = N and R−1
p x = Rp−1x, L−1
p x = Lp−1x
for all x ∈ Q, where p−1 is the inverse element for p in the group N (that
is p · p−1 = p−1 · p = e). Indeed, (xp−1)p = x · p−1p = xe = x for all
x ∈ Q, that is
RpRp−1x = x or R−1
p = Rp−1 ;
q(q−1x) = qq−1 · x = ex = x for all x ∈ Q. Hence, L−1
q = Lq−1 . If a
permutation δ1 of Q is such that δ1N = N , then δ2N = N also for every
permutation δ2, which is weakly equivalent to δ1. Evidently, that it is
true if δ1 ∈ AutQ(·).
Jo
ur
na
l A
lg
eb
ra
D
is
cr
et
e
M
at
h.8 On check character systems over quasigroups and loops
Proposition 2. a) Weak equivalence is an equivalence relation for a
loop.
b) If δ1
w
∼ δ2, then systems S(Q(·), δ1) and S(Q(·), δ2) over a loop Q(·)
detect the same percentage of transpositions (twin errors).
c) If, in addition, δ1 is an automorphism of the loop Q(·), then these sys-
tems detect the same percentage of transpositions (jump transpositions,
twin errors and jump twin errors).
Proof. a) It is evident that δ
w
∼ δ by p = q = e, α = ε, where ε is the
identity permutation of Q.
If δ2 = Rpαδ1α
−1Lq, that is δ2
w
∼ δ1, then
δ1 = α−1R−1
p δ2L
−1
q α = α−1Rp−1δ2Lq−1α = Rα−1p−1α−1δ2αLα−1q−1 ,
where p−1 (q−1) is the element inverse to p (q) in the group N , since
αRax = Rαaαx, αLax = Lαaαx
for all a ∈ Q and αp ∈ N if p ∈ N . Thus, δ1
w
∼ δ2.
Let δ1
w
∼ δ2
w
∼ δ3, then δ2 = Rpαδ1α
−1Lq = Rp1
βδ3β
−1Lq1
where
α, β ∈ AutQ(·), p, q, p1, q1 ∈ N .
From these equalities it follows that
δ1 = α−1Rp−1Rp1
βδ3β
−1Lq1
Lq−1α = Rα−1(p1p−1)γδ3γ
−1Lα−1(q1q−1),
where γ = α−1β ∈ AutQ(·), since RaRbx = (xb) · a = x · ba = Rbax, ba ∈
N and LaLbx = a(bx) = ab · x = Labx if a, b ∈ N . Hence, δ1
w
∼ δ3 and
the weak equivalence is an equivalence relation.
b) Let δ1 = Rpαδα−1Lq, p, q ∈ N and (a, b, c) ∈ M δ1
T = V δ1
1 , that is
ab · δ1c 6= ac · δ1b or ab · Rpαδα−1Lqc 6= ac · Rpαδα−1Lqb.
Then, taking into account that p ∈ N and ab = aq−1 · qb for all a, b ∈ Q
if q ∈ N , we obtain
ab · (αδα−1(qc) · p) 6= ac · (αδα−1(qb) · p) ⇐⇒
ab · αδα−1(qc) 6= ac · αδα−1(qb) ⇐⇒
(aq−1 · qb) · αδα−1(qc) 6= (aq−1 · qc) · αδα−1(qb) ⇐⇒
(a−1(aq−1) · α−1(qb)) · δα−1(qc) 6= (α−1(aq−1) · α−1(qc)) · δα−1(qb) ⇐⇒
āb̄ · δc̄ 6= āc̄ · δb̄, b̄ 6= c̄,
where ā = α−1(aq−1), b̄ = α−1(qb), c̄ = α−1(qc). Thus, (ā, b̄, c̄) ∈ V δ
1 =
M δ
T .
Jo
ur
na
l A
lg
eb
ra
D
is
cr
et
e
M
at
h.G. B. Belyavskaya 9
Now consider twin errors. Let (a, b, c) ∈ V δ1
3 = M δ1
TE , then
ab · Rpαδα−1Lqb 6= ac · Rpαδα−1Lqc,
ab · αδα−1(qb) 6= ac · αδα−1(qc),
(aq−1 · qb) · αδα−1(qb) 6= (aq−1 · qc) · αδα−1(qc),
(a−1(aq−1) · α−1(qb)) · δα−1(qb) 6= (α−1(aq−1) · α−1(qc)) · δα−1(qc),
or
āb̄ · δb̄ 6= āc̄ · δc̄, b̄ 6= c̄,
where ā = α−1(aq−1), b̄ = α−1(qb), c̄ = α−1(qc). Hence, (ā, b̄, c̄) ∈ V δ
3 =
M δ
TE . The inverse transformations are also correct.
c) The statement with respect to transpositions and twin errors fol-
lows from b).
Consider jump transpositions and jump twin errors if δ is an auto-
morphism of a loop Q(·).
Let (a, b, c, d) ∈ M δ1
JT = V δ1
2 , δ1 = Rpαδα−1Lq, that is (ab · c) · δ2
1d 6=
(ad · c) · δ2
1b or
(ab · c) · Rpαδα−1LqRpαδα−1Lqd 6= (ad · c) · Rpαδα−1LqRpαδα−1Lqb.
Then
(ab · c) · (αδα−1(q · (αδα−1(qd) · p)) · p) 6=
6= (ad · c) · (αδα−1(q · (αδα−1(qb) · p)) · p),
where p ∈ N, αδα−1 ∈ AutQ(·), αδα−1p ∈ N . So we have
(ab ·c) ·αδα−1(q ·(αδα−1(qd) ·p)) 6= (ad ·c) ·αδα−1(q ·(αδα−1(qb) ·p)),
(ab · c) · (αδα−1q · αδ2α−1(qd)) 6= (ad · c) · (αδα−1q · αδ2α−1(qb)).
But ab = aq−1 · qb and αδα−1q ∈ N , so
(((aq−1 · qb) · c) · αδα−1q) · αδ2α−1(qd) 6=
6= (((aq−1 · qd) · c) · αδα−1q) · αδ2α−1(qb),
(aq−1 · qb)(c · αδα−1q) · αδ2α−1(qd) 6=
6= (aq−1 · qd)(c · αδα−1q) · αδ2α−1(qb),
((α−1(aq−1) · α−1(qb)) · c̄) · δ2α−1(qd) 6=
6= ((α−1(aq−1) · α−1(qd)) · c̄) · δ2α−1(qb)
Jo
ur
na
l A
lg
eb
ra
D
is
cr
et
e
M
at
h.10 On check character systems over quasigroups and loops
or
(āb̄ · c̄) · δ2d̄ 6= (ād̄ · c̄) · δ2b̄,
where
ā = α−1(aq−1), b̄ = α−1(qb), c̄ = α−1(c · αδα−1q), d̄ = α−1(qd).
Hence, (ā, b̄, c̄, d̄) ∈ V δ
2 = M δ
JT .
It remains to consider jump twin errors. Let (a, b, c, d) ∈ V δ1
4 =
M δ1
JTE , that is (ab · c) · δ2
1b 6= (ad · c) · δ2
1d. Then
(ab · c) · Rpαδα−1LqRpαδα−1Lqb 6= (ad · c) · Rpαδα−1LqRpαδα−1Lqd.
In a similar way with jump transpositions we obtain the following
inequality
(ab · c) · αδα−1(q · αδα−1(qb)) 6= (ad · c) · αδα−1(q · αδα−1(qd)).
Carrying out the same transformations as in the case of jump transposi-
tions we get
(āb̄ · c̄) · δ2b̄ 6= (ād̄ · c̄) · δ2d̄,
where
ā = α−1(aq−1), b̄ = α−1(qb), c̄ = α−1(c · αδα−1q), d̄ = α−1(qd).
Thus, (a, b, c, d) ∈ V δ1
4 = M δ1
JTE and the proof is completed.
Note that Preposition 2 is a generalization of the analogous Proposi-
tion 6.2 of [6] proved for systems over groups.
From Proposition 2 it follows
Corollary 1. Let Q(·) be a loop (a group), N be its nucleus, p, q ∈
N (p, q ∈ Q), then
a) systems S(Q(·), ε) and S(Q(·), RpLq) detect the same percentage of
transpositions (jump transpositions, twin errors and jump twin errors);
b) systems S(Q(·), RpLq) over a loop (over a group) can not detect all
transpositions (all jump transpositions).
Proof. a) Follows from the point c) of Proposition 2 by δ1 = ε, δ2 =
RpLq.
b) According to Theorem 4 and Proposition 3 of [1] the system S(Q(·), ε)
over a loop can not detect all transpositions (all jump transpositions).
Now use a).
Remind that a loop Q(·) is called a Moufang loop if it satisfies the
identity (xy · z)y = x(y · zy).
Jo
ur
na
l A
lg
eb
ra
D
is
cr
et
e
M
at
h.G. B. Belyavskaya 11
Corollary 2. A system S(Q(·), RpLq) over a Moufang loop of odd order
with nucleus N, p, q ∈ N detects all twin errors and all jump twin errors.
Proof. It is sufficiently to note that according to Corollary 4 of [1] the
system S(Q(·), ε) over a Mounfag loop of odd order detects all twin errors
and all jump twin errors.
Example. Now we shall illustrate the results obtained above on a
(noncommutative) loop of order 8.
Let Q(·), where Q = {1, 2, ..., 8}, be a loop of order 8 with the unity
1 which has the Cayley table given in Table 4.
Table 4.Cayley table of the loop Q(·)
(·) 1 2 3 4 5 6 7 8
1 1 2 3 4 5 6 7 8
2 2 1 4 3 7 8 5 6
3 3 4 1 2 6 5 8 7
4 4 3 2 1 8 7 6 5
5 5 6 7 8 2 1 4 3
6 6 5 8 7 4 3 2 1
7 7 8 5 6 1 2 3 4
8 8 7 6 5 3 4 1 2
Computer search carried out by A.Diordiev showed that this loop has
the group of automorphisms of order 4 which consists of the following
permutations:
(12345678), (13247856), (12348765), (13246857).
We do not write the first row of permutations in the natural order. The
nucleus N contains four elements:
N = {1, 2, 3, 4}.
Among permutations δ of Q such that δ1 = 1 for this loop there exist
the set P1 of 52 permutations satisfying the condition (α2) (and (α1),
since Q(·) is a loop) of Theorem 1 for all a, b, c ∈ Q, b 6= c, and the
set P2 of 16 permutations satisfying the condition (γ2) (and (γ1)) for all
a, b, c ∈ Q, b 6= c (P1 ∪ P2 = ∅). According to Theorem 1 it means that
a system S(Q(·), δ) with δ ∈ P1 (δ ∈ P2) can detect all transpositions
(all twin errors).
There exist 16 permutations which are weakly equivalent to the per-
mutation
δ0 = (13426785) ∈ P1.
Jo
ur
na
l A
lg
eb
ra
D
is
cr
et
e
M
at
h.12 On check character systems over quasigroups and loops
These permutations have the form Rpαδ0α
−1Lq, where α ∈ AutQ(·),
p, q ∈ N (here the permutations multiply from the right to the left) and
are given below:
(13426785), (24315876), (31248567), (42137658),
(13428567), (24317658), (31246785), (42135876),
(14237865), (23148756), (32415687), (41326578),
(14238756), (23147865), (32416578), (41325687).
By Proposition 2 each system S(Q(·), δ), where δ is one of these permu-
tations detects all transpositions also.
For the permutation
δ1 = (13564278) ∈ P2
there exist 32 permutations which are weakly equivalent to it. By Propo-
sition 2 all systems S(Q(·), δ) with δ from these permutations detect all
twin errors.
For the systems S(Q(·), δ0) and S(Q(·), δ1) by computer search the
following percentage of detection of transpositions, jump transpositions,
twin errors and jump twin errors respectively was obtained:
rδ0
1 = 100, rδ0
2 = 67, rδ0
3 = 85, rδ0
4 = 67
rδ1
1 = 78, rδ1
2 = 87, rδ1
3 = 100, rδ1
4 = 87.
References
[1] G.B.Belyavskaya, V.I.Izbash, G.L.Mullen, Check character systems using quasi-
groups: I (to appear).
[2] G.B.Belyavskaya, V.I.Izbash, G.L.Mullen, Check character systems using quasi-
groups: II (to appear).
[3] V.D.Belousov, Foundation of the Theory of Quasigroups and Loops. (Russian),
Nauka, Moscow, 1967.
[4] H.M.Damm, Prufziffersysteme uber Quasigruppen, Diplomarbeit Universitat Mar-
burg, Marz, 1998.
[5] A.Ecker and G.Poch, Check character systems, Computing 37/4 (1986), pp. 277-
301.
[6] R.-H. Schulz, On check digit systems using anti-symmetric mappings, In J.Althofer
et al. editors. Numbers, Information and Complexity, Kluwer Acad. Publ. Boston
(2000), pp. 295-310.
[7] R.-H. Schulz, Equivalence of check digit systems over the dicyclic groups of order
8 and 12, In J.Blankenagel & W.Spiegel, editors, Mathematikdidaktik aus Begeis-
terung fur die Mathematik, Klett Verlag, Stuttgart (2000), pp 227-237.
Jo
ur
na
l A
lg
eb
ra
D
is
cr
et
e
M
at
h.G. B. Belyavskaya 13
[8] R.-H. Schulz, Check Character Systems and Anti-symmetric mappings, H.Alt (Ed):
Computational Discrete Mathematics, LNCS 2122 (2001), pp 136-147.
[9] J.Verhoeff, Error detecting decimal codes, Math. Center Tracts 29, Amsterdam,
1969.
Contact information
G. B. Belyavskaya Institute of Mathematics and Computer
Science, Academy of Sciences of Moldova,
str. Academiei, 5, MD-2028, Chishinau,
Moldova
E-Mail: gbel@math.md
Received by the editors: 23.04.2003
and final form in 11.07.2003.
|