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:

1. F is an Abelian group under “+” (the addition operation) with additive identity element 0.
2. F – {0} is an Abelian group under “.” (the multiplication operation) with multiplicative identity element 1.
3. 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:

1. The order q of GF(q) must be a power of a prime, i.e., q = p^k, where p is a prime number, and k = 1,2,…
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.
3. 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)ⁿ 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 = (c₁, …, c_n) Î GF(q)ⁿ,

the corresponding message m to be encoded is

m = (m₁, …, m_k) Î GF(q)^k,
 

and the generator matrix G is of the form

Where the row vectors gj = (g_j,1 g_j,2, ...,g_j,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

for all q^k 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 m_i 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

of the received codeword r = (r₁,...,r_n) (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 h₁, ..., h_n-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 estimateof 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.

Back to Top