Wie kann man dieses verallgemeinerte xor konstruieren, ohne einen zusätzlichen Vektor zu benötigen?

Operator - Verallgemeinerter symmetrischer Unterschied

Wenn Sie binäres xor nehmen und es auf andere Radices verallgemeinern, können Sie dies durch den absoluten Wert der Differenz jedes Elements in einem Radixvektor tun. Dies hat jedoch nicht die gleichen Eigenschaften wie das binäre symmetrische Differen. Der Grund ist, dass wir beim Wegwerfen des "Vorzeichens" des Unterschieds nicht in der Lage sind, eine Oper zu rekonstruieren und das Ergebnis und das andere zu geben, wie wir es in binärem xor können. Also verlieren wir das schöne Eigentum

ABA = B.

Wir behalten jedoch andere schöne Eigenschaften wie

A0 = A.

AA = 0

Es gibt eine Möglichkeit, diese Eigenschaft beizubehalten. Soweit ich das beurteilen kann, werden jedoch 3 Vektoren für jedes Ergebnis ausgegeben. Der erste Vektor ist die übliche symmetrische Differenz, die anderen beiden Vektoren sind Binärvektoren gleicher Länge wie der erste, die das Vorzeichen des Ergebnisses aufzeichnen, wobei ein solcher Vektor für jede Ordnung der Operanden das binäre Komplement des anderen ist. Auf diese Weise kann ein ursprünglicher Operand unter Berücksichtigung des Ergebnisses und der anderen Opernade UND des "Vorzeichen" -Vektors anderer Operanden wiederhergestellt werden.

Beispielsweise :

Angenommen, wir haben 2 Basis-10-Vektoren, die den Zahlen 1137 und 9284 entsprechen. Was ist das xor dieser beiden Zahlen in Basis 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

Stellen Sie 1137 mit 8153 und 9284 wieder her

Meine Frage ist: Gibt es eine bessere Konstruktion der verallgemeinerten symmetrischen Differenz in einem Radix> 2, so dass wir uns nicht an das Zeichen erinnern müssen?

discrete-mathematics xor Cris Stringfellow
quelle

Antworten:

Die gebräuchlichste Definition von xorist , auf Scheitelpunkten, die natürlich separat auf jede Koordinate angewendet werden. Im Fall der Basis 10 müssen Sie zwei Operationen einführen: und . (Beachten Sie, dass sie im Fall von Basis 2 zusammenfallen). Jetzt hast du $a\oplus b=(a+b)\bmod 2$ $a\oplus b=(a+b)\bmod 10$ $a\ominus b=(a-b)\bmod 10$

c = ein ⊖ b zur Codierung und ein = c \oplus b zum Entschlüsseln.

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

Eigentlich können Sie für beide Operationen verwenden, nur ein bisschen schlauer: $\ominus$

c = b ⊖ ein zur Codierung und ein = b ⊖ c zum Entschlüsseln.

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

Dies funktioniert, weil . $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 '
quelle

Ich mag das. Das ist toll. Viel besser. Können Sie etwas näher darauf eingehen, wie Sie diesen kombinierten Operator von den beiden Operatoren abgeleitet haben, z. B. "Warum funktioniert 5?" Gibt es auch etwas für ungerade Basen wie ternäre möglich?

Cris Stringfellow

@Cris Ich habe gerade festgestellt, dass in diesem Fall eine beliebige Zahl funktioniert, daher auch ;) siehe die Bearbeitung.

0

$0$

Was Sie also sagen, ist, dass der Subtraktions-Mod der Basis in jeder Basis als xor funktioniert?

Cris Stringfellow

Ja. Im Sinne von Kryptographie / Codierung ja. Achten Sie nur darauf, dass nicht symmetrisch ist. Dennoch gegeben ist ein fester Code und definieren , haben wir , dass eine Involution, dh für alle . (Nun, das auf diese Weise definiert wird, ist eine Involution, eine beliebige abelsche Gruppe. Warum also nicht in ?)

⊖

$\ominus$

b

$b$

f_{b} (x) = b ⊖ x

$f_b(x)=b\ominus x$

f_{b}

$f_b$

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

$f_b(f_b(x))=x$

x

$x$

f_{b}

$f_b$

Z_{10}

$\mathbb Z_{10}$

@tohecz Irgendeine Idee, ob es möglich ist, dies für die gesamte Anzahl zu tun? Gibt es eine prägnante Operation f (7311, 4829) = 3518?

user16859