Browsed by
Tag: coding theory

Mailbox Answers: Calculating New Parity After an Overwrite

Mailbox Answers: Calculating New Parity After an Overwrite

I recently did some work for Mr. Howard Marks, an independent analyst and founder of Deep Storage on the subject of data protection and data loss. He e-mailed me with a question regarding calculating the new parity for a stripe of data on a storage system. 

Let us consider the case of a 10+1 RAID 5 set with a strip size of 64KB. When an application performs a 4KB write the system must:

  1. Read the 64KB strip that contains the 4KB to be overwritten into a memory buffer
  2. Modify the memory buffer with the data to be written
  3. Read however much other data as would be needed to recalculate the parity strip for this stripe
  4. Write the new data and new parity strip (Min 1 4KB write, 1 64KB write)

When we casually talk about this condition we say the RAID controller would need to read all 10 data strips in the stripe so it can XOR all ten together as part of step 4. I, however have been thinking about XOR and think that rather than requiring N+1 total I/Os I can get it down to three. 

If P, the parity strip, already contains

D_1 \oplus D_2 \oplus D_3 \oplus D_4 \oplus D_5 \oplus D_6 \oplus D_7 \oplus D_8 \oplus D_9 \oplus D_{10}

and we’re overwriting part of D_4 couldn’t I [do the following]:

  1. Read the existing D_4 into a variable D'_4.
  2. Modify the data into D_4.
  3. Calculate the changes as D_4\oplus D_{4}' into variable C
  4. Read the parity strip P
  5. Calculate new parity strip as P=P \oplus C

In short, the answer is yes. We’re going to prove that here, because I think this is a great exercise to really show off the power of XOR. We’ve explored the operation here and began our discussion of coding theory by looking at maximum likelihood decoding. Let’s take a brief review of the XOR (or mod 2) operation:

XOR is just modulo 2 addition

Let’s call generic binary words D_{j}. That is, each D_{j} is simply a string of 1s and 0s of whatever length l we feel like setting. So a binary word D_{j} = d_{1}^{(j)}d_{2}^{(j)}\ldots d_{l}^{(j)} consists of binary bits given by the lowercase1 d_{i}.  XOR operation works bit-by-bit, and will be denoted by \oplus:

\begin{aligned}D_{j} \oplus D_{k} &= (d_{1}^{(j)}d_{2}^{(j)}\ldots d_{l}^{(j)})\oplus d_{1}^{(k)}d_{2}^{(k)}\ldots d_{l}^{(k)}\\&= (d_{1}^{(j)} \oplus d_{1}^{(k)})(d_{2}^{(j)}\oplus d_{2}^{(k)})\ldots (d_{l}^{(j)}\oplus d_{l}^{(k)})\end{aligned}

For a quick numerical example, suppose D_{j} = 1011 and D_{k} = 0010. Then

D_{j} \oplus D_{k} = 1011 \oplus 0010 = (1\oplus 0)(0\oplus 0)(1\oplus 1)(1\oplus 0)

Remember, too, that XOR is addition modulo 2, so we add the bits together, then divide by 2 and take the remainder. So, in particular, 1\oplus 1 = 0 because 1+1 leaves a remainder of 0 when divided by 2. So,

D_{j} \oplus D_{k} = 1001

Back to the question

Mr. Marks’ question can be stated mathematically in the following way (and I’m going to generalize it to any finite amount of words of any length XORed together, because that’s what mathematicians do):

Suppose P = D_{1} \oplus D_{2} \oplus \ldots \oplus D_{j} \oplus \ldots \oplus D_{K} for some K, and one word (say D_{j}) is modified to give D_{j}'. Let C be the binary word that represents the changes between D_{j} and D_{j}'. That is,

C = D_{j} \oplus D_{j}'

(Note: XOR as an operation to identify differences in binary words is one of the more elegant features. If all the bits in two words are the same, then bitwise XORing would always give the binary word of all 0s. Only when two bits are different is their XOR result a 1.) Call P' the new XOR sum with D_{j}' substituted for D_{j}. So

P' := D_{1}\oplus D_{2}\oplus \ldots \oplus D_{j}'\oplus \ldots \oplus D_{K}.

Then does P'= P \oplus C?

Numerical example

Whenever I’m seeking to prove a statement, I always “play” with an example. Now, simply finding an example that fits the statement doesn’t constitute proof. But playing with explicit numbers can often yield a way to prove the statement in general. Plus, we can deepen our understanding by really “seeing the theorem in action,” as opposed to just manipulating symbols via logic. 

Let’s just test this with a sum of 3 words to make our lives easier. Let D_{1} = 110, D_{2} = 010, and D_{3} = 101. Then

P = D_{1} \oplus D_{2} \oplus D_{3} = 110 \oplus 010 \oplus 101 = 001

Now suppose we change D_{2} to D_{2}' = 101. First, the new sum P' is given by 

P' = 110 \oplus 101 \oplus 101 = 110

Now, the change in D_{2} and D_{2}' is given by

C = 010 \oplus 101 = 111

Notice that all three positions changed. Each position that is different has a 1.Let’s see if P \oplus C = P' P \oplus C = 001 \oplus 111 = 110

Success! Now, this doesn’t mean we’re done. One example doesn’t constitute proof. We have to show this is true for any finite number of binary words of any  length. 

Time to prove this statement is true

So, let D_{1},...,D_{K} be binary words of generic length l. Choose one word D_{j} and modify it to form the new word D_{j}'. Let C = D_{j} \oplus D_{j}' denote the change vector. Then

\begin{aligned}P^{\prime}&=D_{1}\oplus D_{2}\oplus\ldots D^{\prime}_{j}\oplus\ldots D_{K}\end{aligned}

 

Now, let’s note that C = D_{j}\oplus D^{\prime}_{j} tells us which positions changed between the two. Another way to look at it is that C is the word you need to XOR with D_{j} to get to the new D^{\prime}_{j}. That is, D^{\prime}_{j} = D_{j} \oplus C.2. Now, let’s plug in the new expression for D_{j}' into P':

\begin{aligned}P^{\prime}&=D_{1}\oplus D_{2}\oplus\ldots D^{\prime}_{j}\oplus\ldots D_{K}\\&=D_{1}\oplus D_{2}\oplus\ldots (D_{j} \oplus C)\oplus\ldots D_{K}\end{aligned}

Now, we know from this post that XOR is a commutative operation. Coupled with the associative property3, we can actually rearrange the order of the XORing to put C last. 

(You’ve done this with regular arithmetic all the time. 5 + 1 + 6 + 3 can be rearranged and grouped into (6+3+1) + 5 = 10 +5 = 15. Commutativity and associativity combined allow this to happen with any operation.)

So,  

\begin{aligned}P^{\prime}&=D_{1}\oplus D_{2}\oplus\ldots D^{\prime}_{j}\oplus\ldots D_{K}\\&=D_{1}\oplus D_{2}\oplus\ldots (D_{j} \oplus C)\oplus\ldots D_{K}\\&=(D_{1}\oplus D_{2}\oplus\ldots D_{j}\oplus\ldots D_{K})\oplus C\end{aligned}

But wait, that last thing in parenthesis is exactly P. Therefore,

\begin{aligned}P^{\prime}&=D_{1}\oplus D_{2}\oplus\ldots D^{\prime}_{j}\oplus\ldots D_{K}\\&=D_{1}\oplus D_{2}\oplus\ldots (D_{j} \oplus C)\oplus\ldots D_{K}\\&=(D_{1}\oplus D_{2}\oplus\ldots D_{j}\oplus\ldots D_{K})\oplus C\\&= P \oplus C\end{aligned}

Since we showed this for any generic number of binary words added together, and allowed to binary words to be any length, we’ve proven the statement. 

Bonus: Multiple modifications

What if we modified more than one word in our original sum P? It’s a pretty simple extension to run through the proof again with multiple modified words and show that if we have multiple C^{\prime}s, one for each modified word, we can perform the same substitution and show that the new P^{\prime} is simply the old P XORed with all of the change vectors. Alternatively, you could XOR all the change vectors first into one big change vector, then XOR that with your original P to compute the new P^{\prime}. If you want to verify it for yourself formally, simply follow the same steps we did above for one modified word. You’ll just be performing the same type of substitution multiple times to account for each modification. 

Conclusion

Mr. Marks brought this up because he was seeking a way to compute the new parity strip in a more efficient way (with fewer arithmetic steps) than simply following the definition. You can absolutely “brute force” your way to calculating the new parity strip. Companies and startups are always concerned about “scalability”. Sure, you won’t notice the time different between 10 extra things added together. But what about 10 million? 1 billion? More than that? None of those numbers are infeasible for the amount of calculations we perform on data now. In those cases, the brute force method of simply using the definition starts to cause performance problems. It was worth taking the time to “be clever” and search for a nice, elegant way that cuts down the number of operations necessary to calculate a new parity strip. It took a little upfront work, but the result speaks loudly for itself. 

 

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

A Partition by any Other Name

A Partition by any Other Name

I promise I’m actually a probability theorist, despite many of my posts being algebraic in nature. Algebra, as we’ve seen in several other posts, elegantly generalizes many things in basic arithmetic, leading to highly lucrative applications in coding theory and data protection.  Some definitions in mathematics may not have obvious “practical use”, but turn out to yield theorems and results so powerful we can use them to send image data cleanly from space. 

Read More Read More

Theory of Coding, Episode 2: Maximum-Likelihood Decoding

Theory of Coding, Episode 2: Maximum-Likelihood Decoding

The introduction to coding theory in this post will now allow us to explore some more interesting topics in coding theory, courtesy of Pinter’s A Book of Abstract Algebra. We’ll introduce the notion of a code, informations, and parity check equations. Most communication channels are noisy to some extent, which means that a transmitted codeword may have one or more errors. If the recipient of a codeword attempts to decode a message, he needs to be able to determine first if there was a possible error in the code, and then correct it. This will lead us to one method called maximum likelihood decoding.

Read More Read More

Group Theory, XOR, and Binary Codes: Introducing Coding Theory

Group Theory, XOR, and Binary Codes: Introducing Coding Theory

Binary codes and bit-wise operations are fundamental in computer science. Whatever device you are running today works because of binary codes, and the bit-wise operations AND, OR, NOT, and XOR. (A fun exercise, prove to yourself that each of these rules meets the definition of an operation. If you need a refresher, check out this post.) We can also look at binary codes and the bit-wise operations in a more algebraic way.

Let’s continue exploring abstract algebra via Pinter’s delightful algebra book. The previous post discussed operations on sets, and explored concatenation as an example. Here, we will build on this and look at a set G combined with an operation \ast that satisfies three axioms. This operation/set combination is a special algebraic object called a group, and has been studied extensively. We’ll look at a specific group to illustrate the concept: binary codes with the XOR operation.1 (Note: we also looked at modulo arithmetic on finite groups of integers here as another example of a group.)

Some quick terminology and setup

We currently (until the advent of quantum or DNA computers, or something else entirely) transmit information by coding it into binary strings – strings of 1s and 0s. We call these binary words. 100111 is a binary word, as are 001, 1, and 10110. A general binary word can have any length we want.

When we send these binary words via some communication channel, we always run the risk of errors in transmission. This means we need to devise some way to detect and correct transmission errors in binary codes. One way to do this is the XOR operation.

Let \mathbf{a} = a_{1}a_{2}\ldots a_{n} and \mathbf{b} = b_{1}b_{2}\ldots b_{n}  be binary words of length n, where a_{i},b_{i} \in \{0,1\} for i=1,...,n. We define the XOR operation, which we will denote by the symbol \oplus on each bit. For two bits a_{i}, b_{i} in a word,

a_{i}\oplus b_{i} = (a_{i} + b_{i}) \bmod 2

(Now would be a good time to review your modulo arithmetic if you’ve forgotten.)

Then for two words \mathbf{a} and \mathbf{b}, the XOR operation is done bit-wise (component by component). That is,

\mathbf{a} \oplus \mathbf{b} = (a_{1}\oplus b_{1})(a_{2}\oplus b_{2})\ldots (a_{n}\oplus b_{n})

As a quick example,

110010 \oplus 110001 = 000011

Notice that the result of the XOR operation shows us the positions in which \mathbf{a} and \mathbf{b} differ. Another way to look at it is if \mathbf{a} was transmitted, and \mathbf{b} was received, there was an error in the last two positions. We can call the result of XORing two binary words the error pattern.

Showing Binary Words with the XOR operation is a group

Now we’ll look at the set of all binary words of length n, called \mathbb{B}^{n} coupled with the operation XOR.2 We want to show that this set along with the XOR operation forms an algebraic structure called a group. A group is one of the most basic algebraic structures we can study. We will be exploring all sorts of things we can do and build with groups in future posts, so first we need to define a group.

What’s a group?

From Pinter (1982)

A group is a set G coupled with an operation \ast, denoted \langle G, \ast \rangle that satisfies the following three axioms:

(G1: Associativity of the operation) The operation \ast is associative. (See the previous post for a review of associativity.)

(G2: Existence of an identity element) There is an identity element inside the set G that we will call e such that for every element g \in G, e\ast g = g\ast e =g

(G3: Existence of an inverse for every element) For every element g \in G, there is a corresponding element g^{-1} \in G such that g\ast g^{-1} = g^{-1}\ast g = e

 

All three properties were discussed in the previous post. It’s important to note that a group is a set and an operation. If we change one, then we either have a different group, or we lose the group classification. Real numbers under addition are a group, as are nonzero real numbers under multiplication, but those are two different groups. (This will be important when we get to rings and fields.) Integers under addition are also a group, but a different one than real numbers under addition.

Let’s prove \langle\mathbb{B}^{n}, \oplus \rangle is a group.

Showing a set and operation is a group is pretty algorithmic, in a sense. We just have to show that all three axioms are satisfied.3

(G1): Associativity

This one will be a bit tedious. We have to show associativity for words of any length n. But fear not. Since XOR of words is done bit wise, we can exploit that and first show associativity for binary words of length 1, then “scale it up”, if you will.

In this case, for words of length 1, we just have to brute-force it. We have to show that for any a,b,c \in \mathbb{B}^{1}, that

(a\oplus b) \oplus c = a \oplus (b \oplus c)

So,

\begin{aligned} 1\oplus (1\oplus 1) = 1 \oplus 0 = 1 &\text{ and } (1 \oplus 1) \oplus 1 = 0 \oplus 1 = 1\\ 1\oplus (1 \oplus 0) = 1\oplus 1 = 0 &\text{ and } (1\oplus 1) \oplus 0 = 0 \oplus 0 = 0\\ &\vdots\end{aligned}

Continue in this fashion until you have tried all combinations. (It does work out.)

Now that we have that this is true for words of length 1, we just use the definition of XOR operation on words of length 1 to “scale up” to words of length n. Since the operation is done component-wise, and it is associative on each component, it is associative on the whole word. We’ll show this formally now:

Let \mathbb{a,b,c} \in \mathbb{B}^{n}. So \mathbf{a} = a_{1}a_{2}\ldots a_{n}, \mathbf{b} = b_{1}b_{2}\ldots b_{n}, and \mathbf{c} = c_{1}c_{2}\ldots c_{n}. Then

\begin{aligned}\mathbf{a}\oplus (\mathbf{b} \oplus \mathbf{c}) &= a_{1}a_{2}\ldots a_{n}\oplus [(b_{1}\oplus c_{1})(b_{2}\oplus c_{2})\ldots (b_{n}\oplus c_{n})]\\ &= (a_{1} \oplus (b_{1} \oplus c_{1}))(a_{2} \oplus (b_{2} \oplus c_{2}))\ldots (a_{n} \oplus (b_{n} \oplus c_{n}))\\&= ((a_{1} \oplus b_{1})\oplus c_{1})((a_{2}\oplus b_{2})\oplus c_{2})\ldots ((a_{n}\oplus b_{n})\oplus c_{n})\\&= (\mathbf{a} \oplus \mathbf{b})\oplus \mathbf{c}\end{aligned}

That third equality holds because we already showed that XOR was bit-wise associative. The last equality just recalls what it means to XOR two binary words. With that, we have shown associativity of the XOR operation.

(G2): Existence of an identity element

When we want to show that a group has an identity element, we must actually find a candidate and show it meets the criterion. Here is (frustratingly, sometimes), where intuition and experience tend to play the biggest role. But, as my mother always told me when I was frustrated at my middle school math homework: “Make it look like something you’ve seen before”. XOR is bitwise addition, just with a twist (add then mod out by 2). So let’s start by considering the identity element for addition: 0. We’re looking at binary words of length n, so a good candidate for our identity element e would be a string of n 0s. But does it fit?

Any word

\begin{aligned}a_{1}a_{2}\ldots a_{n} \oplus 000\ldots 0 &= (a_{1}\oplus 0)(a_{2} \oplus 0)\ldots (a_{n} \oplus 0)\\&= a_{1}a_{2}\ldots a_{n}.\end{aligned}

You can check also that 0 \oplus \mathbf{a} = \mathbf{a}, and thus our candidate is a match!4

(G3): Existence of an inverse element for every element in the set

This one is a little bit trickier. We need to be able to find any generic binary word, and show that there is another binary word such that when we XOR them together, we get the sequence of all 0s. (Computer science friends are ahead on this one.)

Think back to how we looked at the XOR operation as a form of error checking. If we XORed two words together, there was a 1 in every position in which they differ, and a 0 in every position in which they were identical.

Therefore, we come to the interesting conclusion that every element is its own inverse! If you XOR an element with itself, you will get a sequence of 0s. With our error checking interpretation, this makes perfect sense. We know the communication line transmits perfectly if we can XOR the sent and received word and get all 0s every time.

Conclusion: every element is its own inverse, and every element in the group is, well, in the group, so we have satisfied the third axiom.

Therefore, we have a group, fellow math travelers!

Bonus round: showing that \langle \mathbb{B}^{n}, \oplus \rangle is an abelian group

Notice that we are missing one property that all of you likely take for granted in regular arithmetic: being able to add and multiply in any order you like. That is, you take for granted that 2+3 = 3+2. This property is called commutativity, and groups with this bonus property are called abelian groups. Not all groups are abelian. Square matrices under matrix multiplication come to mind. However, we will show that \langle \mathbb{B}^{n}, \oplus \rangle is an abelian group.

This actually can be done quite simply by exploiting two things we already know: modulo arithmetic and bit-wise operations. We know that XOR is basically bit wise addition modulo 2. Addition is absolutely commutative, and modding out by 2 doesn’t change that, since we add in the regular ol’ way, then divide by 2 and take the remainder.

That means that XORing binary words of length 1 is commutative. Now, since XORing is done bit-wise, which we noted while proving associativity, we can use that same reasoning again (in fact, it looks almost exactly the same), to conclude that XOR is indeed a commutative operation, and thus we have an abelian group.5

Conclusion

We explored the definition of a group using a common operation and set from computer science. We needed this foundation to be able to study more. The next post in the coding theory and algebra series will take an in depth look at maximum likelihood decoding. This decoding process is a way to attempt to decode and correct errors in transmission when the communication channel is noisy (and most are, somewhat).

Abstract algebra is a powerful branch of mathematics that touches many more things than most of us realize. Now that we know binary words under the XOR operation is a group, we can start extending this and studying it as a structure, or skeleton, rather than focusing on the individual elements. The elements and operation are really just the drywall or stucco on a house. The algebraic structure is the skeleton of beams inside the house. We learn a lot more by studying the structure than the covering, which is why it is important to enter that abstract realm. We will uncover similarities in strange places, and applications we didn’t know were possible.
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.