Transforming a byte with a subset of a small, fixed set of values and xor into any other value

cs.stackexchange https://cs.stackexchange.com/questions/102853

  •  05-11-2019
  •  | 
  •  

Pergunta

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.

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top