3
$\begingroup$

If I have some collection of bits, -- a byte, say -- of arbitrary value then I can transform it into some other value by means of exclusive-oring it with a subset of (in this case) eight fixed values, each affecting a single bit 0x80, 0x40, ... 0x01: every possible value is represented by some combination of operations from any given starting point.

But, clearly there are other sets of eight values which achieve this. For example 0b1xxxxxxx, 0b01xxxxxx, 0b001xxxxx, 0b0001xxxx, 0b00001xxx, 0b000001xx, 0b0000001x, 0b00000001 clearly satisfy these criteria and are a relatively large set of such values (as the x's can be distinct). (Proof: use the first value to get the msb correct then the second to get the second-msb correct, etc).

However, some sets clearly do not have this property, for three bits 0b101, 0b110 and 0b011, for example, clearly do not as every operation preserves parity.

I am interested in various aspects of the above property from a practical standpoint for a numerical computational model. I am not a theoretical computer scientist, but have studied these things in the last century, so I am vaguely aware that what I need to look at may amount to groups, Galois Fields, LFSRs, etc.

Could someone point me in the right direction so that my learning can be more directed than random flailing around textbooks and wikipedia? Just some signposts as to the names of the relevant fields of study, the great theorems/problems/categories and their names, the useful techniques, etc, would be fine.

$\endgroup$
5
$\begingroup$

You have recalled the correct category, "linear-algebra".

Let us see how we can interpret xor in the terms of linear-algebra. Here is the computation rules for xor. $$0\oplus0=0$$ $$0\oplus1=1$$ $$1\oplus0=1$$ $$1\oplus1=0$$ If we consider 0 and 1 as the zero element and the unit element of the binary field $\Bbb F_2$, the simplest finite field, then we can see $\oplus$ is none other than the addition in $\Bbb F_2$. $$0+0=0$$ $$0+1=1$$ $$1+0=1$$ $$1+1=0$$

That means, if we xor a string of 3 bits to another string of 3 bits, we are actually adding two vectors $\vec a$ and $\vec b$ in the three-dimensional linear space $\Bbb F_2^3,$ $$\vec a+\vec b=\vec c$$ For example, $(0,1,0) + (1,1,0)=(1,0,0)$.

If we fix the second vector, the addition by the second vector is a linear transformation from $\Bbb F_2^3$ to $\Bbb F_2^3$. All these transformations form a 3-dimensional linear space over $\Bbb F_2$ with basis $$\{\text{addition by (1,0,0)}, \text{ addition by } (0,1,0), \text{ addition by (0,0,1)}\}.$$ Given a set of vector in $\Bbb F_2^3$, all combinations of the additions by those vectors can transform any vector to another vector if and only those vectors are linearly independent.

For example, "three bits 0b101, 0b110 and 0b011" "do not have this property" because, $(1,0,1)+(1,1,0)+(0,1,1)=(0,0,0)$ in $\Bbb F_2^3$, i.e, those three vectors are not linearly independent.


Here is a counting exercise.

(Exercise) Show the number of sets of such strings of 3 bits is $(2^3-1)*(2^3-2)*(2^3-2^2) = 168.$ In general the number of set of such string of n bits is $(2^n-1)(2^n-2)\cdots(2^n-2^{n-1}).$

$\endgroup$
  • $\begingroup$ Thank you. I am (wearily) used to the idea of (generally continuous) basis-vectors etc from other disciplines, and I'd not thought of formulating it in that way, and now that makes intuitive sense. $\endgroup$ – Dannie Jan 14 at 15:27
  • $\begingroup$ As for the counting exercise, based on your answer: in this very special field there is no need to worry about proportionality because 2n*vector = 0; -vector = +vector. So each basis vector can occur 0 or 1 times in any expression that might be null (dependency test). We have free choice in establishing the first axis (except null) so 2^n-1. In others we must ensure any combination of presence/absence of earlier established axes is non-null. As each of those is present/absent that's 2^(n-1) permutations, all distinct because of nature of xor, so that has 2^n-2^(n-1) possible values. ?qed? $\endgroup$ – Dannie Jan 14 at 15:31
  • $\begingroup$ Correct.$\quad$ $\endgroup$ – Apass.Jack Jan 14 at 15:32
3
$\begingroup$

You need the eight values to be linearly independent so they form a basis of the space $\{0,1\}^8$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.