29 Apr Algebra behind the scenes : Reed-Solomon Algorithm
You must have seen QR codes displayed in Paytm stickers. One can scan these codes to make payment to the merchant easily via Paytm. Such QR codes are used for making super fast transactions via the newly introduced BHIM app (Bharat Interface for Money) and UPI apps (Unified Payments Interface). The advantage of a QR code is that it has abolished the requirement of entering account details, IFS code, branch name etc. in order to carry out online money transfers. A QR code consists of black squares arranged in a square grid on a white background, which can be read by an imaging device such as a camera, and processed using Reed–Solomon error correction until the image can be appropriately interpreted. The required data is then extracted from patterns that are present in both horizontal and vertical components of the image. The Reed-Solomon error correction algorithm makes sure that even if the QR code is slightly damaged due to wear and tear, a certain percentage of error can be detected and the correct information hidden in the code can be extracted safely. This algorithm uses a lot of algebra. A poster presentation on this algebra was made by my students Rahul Paul and Rajarshee Rohan Suklabaidya of B.Sc 2nd Semester, Mathematics Honours, Gurucharan College, at the College week multi-disciplinary exhibition. Later, Rahul Paul presented an improved version of the presentation in the National Conference on Recent Trends in Mathematical Sciences at Assam University and was adjudged the best poster award. Here, I present a glimpse of the algebra behind the Reed Solomon codes.
The pre-requisites include an introduction to modular arithmetic and polynomials over finite fields, which are usually taught in the first year of an under-graduate course in mathematics in most Indian Universities. This methodology can be followed in explaining Reed-Solomon codes with the intention of improving the teaching-learning process in an abstract algebra class.
- If is a prime number, then the set together with the operations and is a finite field. is the remainder when is divided by . is the remainder when is divided by .
- An expression of the form where and , is called a polynomial of degree over the finite field . For example, is a polynomial over .
- Finite differences : The first forward difference of a sequence is the sequence . The second order difference is . Similarly, , etc. are defined.
Let be a prime number and let . The Reed-Solomon code over the field with message symbols and code symbols is defined as : Given a message vector , where the symbols are in , let be the polynomial with coefficients given by the message symbols. Thus, is a polynomial of degree at most in one variable with coefficients from . Then, the code vector for this message is the list of the first values of the polynomial evaluated using modular arithmetic in . Let i.e. we are to create a code on symbols for a message with symbols over the finite field . Let the message vector be . Then, the message polynomial is and the code vector is computed as : for . Thus,
and so on.
Thus, the message is coded as .
The code is transmitted to the receiver and there is always a possibility of error in the transmission. Such errors are reflected in the entries of the received vector. For example,
Actual code :
Received code :
So, there are errors in the 3rd (i=2) and 5th (i=4) positions.
It has been shown that a Reed-Solomon code with message symbols and code symbols can correct at most errors. Let the actual transmitted code vector be
and the received vector be
- If there are no errors, then for all .
- If there are at most errors, then for at most values of .
- In the above example, and .
- In reality, the error positions are unknown.
Let be the error positions. Then, we construct the polynomial, say error polynomial, as
which is of degree at most . Thus, each error position is a zero of the polynomial . We consider the polynomial identity
Since is of degree and is of degree , so is of degree . We take,
where the coefficients and are unknowns. Thus, the total number of unknowns is . Now, from equation (1),
Thus, if is not an error position and if $i$ is an error position. Thus, in both cases, we have
- The equation (2) is called the key equation for the decoding algorithm.
- It is a system of linear equations in unknowns ('s and 's).
- Solving this system of equations, we can get the expressions for and .
- From eq. (1), the message polynomial is obtained by dividing by .
Since degree of , so its forward differences of order or more vanish. So, in particular
Thus, we obtain the following system of linear equations in unknowns :
where the th entry of the matrix is , where and . This can be solved to obtain the unknowns . Hence, we get . Now, the values are calculated and is obtained by Newton's forward interpolation formula :
The error polynomial is found to be . The values of are computed as . Thus, the difference table is computed modulo 7 :
Hence, by Newton's forward interpolation formula, we obtain
And hence, .
Thus, the original message has been detected as even though there were two errors in the received code.
Error correction levels in QR codes
If the number of message symbols is and the Reed-Solomon code is required to correct the errors in at most symbols, then the number of symbols in the Reed-Solomon code has to be . The ratio gives the error correction level of the Reed-Solomon code. Expressed as percentage, the error correction level in the corresponding QR code is . This percentage is denoted in the QR code as under :
Thus, we see that there is a lot of mathematics is hidden behind these black and white drawings. This gives us a glimpse of the wonderful applications of abstract algebra.
Latest posts by Debashish Sharma (see all)
- Few problems - 4 - June 21, 2017
- Algebra behind the scenes : Reed-Solomon Algorithm - April 29, 2017
- In memory of Prof. Jonathan Borwein - August 7, 2016