Matrix Encoder and DecoderDate: 07/22/2003 at 20:24:56 From: Jai Subject: Matrix encoder and decoder If the encoder is 2 5 I know that the decoder would be 3 -5 1 3 -1 2 Why do the 3 and 2 swap diagonally and why do the 1 and 5 stay the same but change to a negative? Date: 07/23/2003 at 01:05:57 From: Doctor Barrus Subject: Re: Matrix encoder and decoder Hey, Jai! Let's suppose that you take ANY matrix that you want to encode, with entries like this: [p q] [r s] When we multiply this matrix by the encoder (I don't know whether you're multiplying on the left or on the right. The decoder works either way, so I'll just assume you're multiplying on the right), we get the following matrix: [p q][2 5] = [2p+q 5p+3q] [r s][1 3] [2r+s 5r+3s] This is the encoded matrix. Now if we apply the decoding matrix, we'll get the following: [2p+q 5p+3q][3 -5] = [(6p+3q)-(5p+3q) (-10p-5q)+(10p+6q)] [2r+s 5r+3s][-1 2] [(6r+3s)-(5r+3s) (-10r-5s)+(10r+6s)] = [p q] [r s] So you see that the decoder matrix ALWAYS returns the original matrix, no matter what the entries are. Why does this happen? Well, basically, we're multiplying the original matrix (I'll call it M) by an encoding matrix E and a decoding matrix D: M*E*D Now since we carry out the multiplication in steps, this is how the grouping goes: (M*E)*D i.e., we're multiplying first by the encoder matrix, and then (second) by the decoder matrix. However, matrix multiplication is associative. You can't change the order in which the matrices appear on the line, but you can change how you group them (you can change where the parentheses are). So what we're doing is the same as finding the matrix M*(E*D) Now try multiplying the encoder and the decoder matrices together, all by themselves. You should get the following: [1 0] [0 1] This is called the identity matrix, because (as you've seen), when you multiply any matrix by it, you get the original matrix back (try it!). It acts for matrices the way the number 1 does for real numbers. So when you're multiplying by the encoder matrix and then the decoder matrix, the net product is pretty much just multiplying your original matrix by 1 - it's going to the same as it was originally. So how do we find pairs of matrices that have this pattern - that when you multiply them together, you get an identity matrix out? What we do is called finding the "inverse" of a matrix. We say that the decoder matrix is the inverse of the encoder matrix. In any book on matrix algebra or linear algebra you can learn a lot more about the properties of inverses, but for right now, let's stick to 2-by-2 matrices. Say your encoder matrix is [a b] [c d] One important thing is that we cannot allow ad-bc=0. If that's true, then there will be no decoder matrix for the encoder matrix. But if ad-bc is not equal to zero, we form the decoder by doing pretty much what you said: 1. Switch a and d. 2. Change the sign on both b and c. 3. Divide each entry in this changed matrix by the quantity ad-bc. (This is why it's not allowed to be 0. Notice that in the original matrix you gave, ad-bc = 2*3-1*5 = 1, so the division we had to do to get the decoder matrix is invisible.) For example, say our encoder matrix is [5 3] [1 2] Then the decoder matrix is [ 2/7 -3/7] [-1/7 5/7] Try it out and see that it, too, works. I hope this helps. Good luck! - Doctor Barrus, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/