|
From the previous example as well as the general formulation of
the Krama-maala
vikrati, it is clear that the
Krama-maala
vikrati encoding procedure
bears a strong resemblance to that of an algebraic block code.
The fact that the message symbols a1, … , am
and the resulting codeword symbols i1, …,
im come from the same "alphabet'' of words suggests
a straightforward way of representing the encoding as a rate 1/4
linear block code over a finite field. We will now formulate the
example in this framework. A finite field is a finite set of q elements on
which we can define “addition”, “subtraction”, “multiplication”,
and “division”. More formally, it is a set F of q
elements with the following properties:
-
F
is an Abelian group under “+” (the
addition operation) with additive identity element 0.
-
F –
{0} is an Abelian group under “.”
(the multiplication operation) with multiplicative identity
element 1.
- The distributive law a*(b+c)
= a*b + a*c holds for all a,b,c
Î F.
A finite field with q elements is often called a Galois field of
order q, and is denoted by
GF(q). Galois fields have many distinctive properties [5,
6], but for our purposes, we will only need to know a few key
facts:
- The order q of GF(q) must be a power of a prime,
i.e., q = pk, where p is a prime number, and k =
1,2,…
- For the case where the order q = p, the resulting
Galois field GF(p) is isometric to the set {0, 1, … ,
p - 1} with addition and multiplication being given by
their arithmetic counterparts mod p.
- GF(q) contains an additive inverse -1 corresponding
to the multiplicative identity 1.
A linear block code C is a collection of n-tuples
from GF(q) forming a subspace of the vector space GF(q)n
of n-tuples over GF(q). If the dimension of the
subspace is k, we call the ratio k/n the rate of the code
[7, 8]. Because k < n (and in fact k < n
if the codewords contain any redundancy making them useful for
error correction), we can generate the subspace of codewords in
the linear block code using the linear relation
c= mG,
where the codewords c are of the form
c = (c1, …, cn)
Î GF(q)n,
the corresponding message m to be encoded is
m = (m1, …, mk)
Î GF(q)k,
and the generator matrix G is of the form
| G = |
g1 |
g1,1 |
g1,2 |
... |
g1,n |
| g2 |
g2,1 |
g2,2 |
... |
g2,n |
| |
|
|
... |
|
| gk |
gk,1 |
gk,2 |
... |
gk,n |
Where the row vectors gj = (gj,1 gj,2,
...,gj,n) are basis vectors for the code
subspace C. Hence it follows that we can generate all gk
codewords in the subspace using the relation
| mG = (m1,...,mk) |
g1
g2
.
.
gk |
= m1g1+m2g2+...+mkgk |
for all qk message vectors m.
We can now put the Krama-maala vikrati example having
input message m = (a, b, c, d) and codeword c = (a, b, d,
d, b, c, d, c, c, d, c, b, d, d, b, a), in the form of a linear
block code by assuming the input symbols mi as
coming from a q-ary alphabet tat can be represented by a
Galois field GF(q)[1]. We then see that
generator matrix is of the form
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
G = 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1
0
0 0 0 0 0 1 0 1 1 0 1 0 0
0 0 0
0 0 1 1 0 0 1 0 0 1 0 0 1
1 0 0
In digital systems in which errors in all codeword symbols
are equally likely and the probability that a codeword symbol is
in error is less than the probability that the symbol is
correct, maximum likelihood decoding is usually accomplished
using syndrome decoding [7, 8]. In syndrome decoding, we
compute the syndrome
| s = rH = (r1,...,rn) |
h1
h2
.
.
.
hn-k |
of the received codeword r = (r1,...,rn)
(the possibly corrupted version of the true codeword c).
Here H is the parity check matrix of the code C,
made up of the row vectors h1, ..., hn-k
which are basis vector for the n-k dimensional dual
subspace C_ of the code subspace C.
The key observation in syndrome decoding is that if c
is a valid codeword, then cH = 0. Now suppose that the
received codeword ( possibly containing errors) is given by
r = c + e,
where c is the codeword
corresponding to the message m and e is the error pattern that
when added to the codeword c yields the corrupted codeword
r.
Then by linearity, we have
s = r H = (c + e)H = cH + eH = 0 + eH = eH.
So as long as the error pattern e itself is not itself a
codeword, s will be nonzero, and we will be able to detect the
presence of errors. The maximum likelihood estimate of the error
pattern e is then simply the minimum weight[2]
error pattern 
corresponding to the observed s. By adding
 to the received
codeword r, we get the maximum likelihood estimate of the
original codeword c:
and hence the corresponding estimate of the original message
m. However, as seen in the example, the
decoding done my an individual decoding the chant does not fit
this decoding framework. To start with, not all codeword symbols
are assumed to have equal probability of containing an error,
it is in fact assumed that the first symbol is never in error. Furthermore, when an individual decodes the chant, he
often knows an error has occurred before getting to the end of a
codeword. This seems to imply that there is some kind of
sequential decoding going on. Still, it can be seen that the
encoding process fits well into the framework of linear block
coding, so in the chanting of the Rig Veda Samita, we see what
is perhaps the oldest example of error control codes having a
structure very similar to that of linear block codes.
[1] This means that the alphabet size
of possible words in the chant must be a power of a prime. If it
is not, we can augment the alphabet with additional letters so
that it is. While it may seem strange to represent an alphabet
of words as a Galois field, since “addition” and
“multiplications” of chant words is probably a meaningless
concept, we do so anyway in order to represent the Krama-maala
vikrati as a linear block code.
[2] The weight of a vector or codeword
is equal to the number of nonzero elements it contains.
|
