Como construir esse xor generalizado sem precisar de um vetor extra?

Operador - Diferença simétrica generalizada

Se você pegar o xor binário e generalizá-lo para outras radições, poderá fazê-lo pelo valor absoluto da diferença de cada elemento em um vetor radix. No entanto, isso não tem as mesmas propriedades que o diferencial binário simétrico. A razão é que, jogando fora o "sinal" da diferença, somos incapazes de reconstruir uma ópera e, dado o resultado e o outro, como podemos no xor binário. Então perdemos a bela propriedade

ABA = B

No entanto, mantemos outras propriedades agradáveis, como

A0 = A

AA = 0

Existe uma maneira de manter essa propriedade. No entanto, tanto quanto posso dizer, envolve a emissão de 3 vetores para qualquer resultado. O primeiro vetor é a diferença simétrica usual, os outros dois vetores são vetores binários de comprimento igual ao primeiro que registram o sinal do resultado, um desses vetores para cada ordem dos operandos, sendo o complemento binário do outro. Dessa maneira, um operando original pode ser recuperado, dado o resultado e o outro opernad, E que outros operandos "assinam" o vetor.

Por exemplo :

Digamos que temos 2 vetores de base 10 correspondentes aos números 1137 e 9284, qual é o xor desses dois números na base 10?

        7  3  1  1              4  8  2  9


        4  8  2  9              7  3  1  1

Signed
Result  3 -5 -1 -8             -3  5  1  8

Sign
Vector  0  1  1  1              1  0  0  0

Symmetric
Difference              3 5 1 8

Recupere 1137 dados 8153 e 9284

Minha pergunta é: existe uma construção melhor da diferença simétrica generalizada em qualquer raiz> 2, de modo que não precisamos 'lembrar o sinal'?

discrete-mathematics xor Cris Stringfellow
fonte

Respostas:

A definição mais comum de xoré $a\oplus b=(a+b)\bmod 2$ , nos vértices aplicados a todas as coordenadas separadamente, é claro. No caso da base 10, é necessário introduzir duas operações: e . (Observe que no caso da base 2 eles coincidem). Agora você tem $a\oplus b=(a+b)\bmod 10$ $a\ominus b=(a-b)\bmod 10$

c = uma ⊖ b para codificação e uma = c \oplus b para decodificação.

$c=a\ominus b \quad\text{for coding}\quad\text{and}\quad a=c\oplus b \quad\text{for decoding.}$

Na verdade, você pode usar para ambas as operações, um pouco mais inteligente: $\ominus$

c = b ⊖ uma para codificação e uma = b ⊖ c para decodificação.

$c=b\ominus a \quad\text{for coding}\quad\text{and}\quad a=b\ominus c \quad\text{for decoding.}$

Isso funciona porque . $a=b\ominus c=(b-c)\bmod 10=(b-(b\ominus a))\bmod 10$ $= (b-(b-a)\bmod 10)\bmod 10=a\bmod 10=a$

yo '
fonte

Eu gosto disso. Isso é ótimo. Muito melhor. Você pode elaborar um pouco do seu pensamento sobre como você derivou esse operador combinado dos dois operadores, como "por que 5 funcionam?" Também há algo possível para bases estranhas como ternário?

precisa

@Cris Acabei de descobrir que qualquer número funciona nesse caso, portanto

0

$0$ também;) veja a edição.

yo '

então o que você está dizendo é que o subtraction mod da base funciona como xor em qualquer base?

precisa

Sim. No sentido de criptografia / codificação, sim. Apenas tenha cuidado para que

⊖

$\ominus$ não é simétrico. Ainda assim, dado

b

$b$ é um código fixo e define

f_{b} (x) = b ⊖ x

$f_b(x)=b\ominus x$ , nós temos isso

f_{b}

$f_b$ é uma involução, ou seja,

f_{b} (f_{b} (x)) = x

$f_b(f_b(x))=x$ para todos

x

$x$ . (Bem,

f_{b}

$f_b$ definido desta forma será uma involução é qualquer grupo abeliano, então por que não

Z_{10}

$\mathbb Z_{10}$ ?)

yo '

@tohecz Alguma idéia se é possível fazer isso para o número inteiro? Por exemplo, existe uma operação sucinta f (7311, 4829) = 3518?

user16859