GS诡异理论之——邻位异或编码

话说这东东比较长也比较BT，建议下载下来看
貌似改规矩了，一个UOF一个PDF

有了这个编码方法，以后偶就可以华丽丽地写一些见不得人的东东了（PIA！说过了不是情书！！），放心大胆地写吧~

邻位异或编码.uof邻位异或编码.pdf

这种编码方法是偶以前想个什么问题的时候想到的，当时没有太在意。现在仔细研究了一下，得到了下面的这一大顿乱七八糟的结果。嗯，根据这种编码方法的特点，偶将其取名为邻位异或编码。下面开始描述那一大顿乱七八糟的结果。

有如下一串信息：

a_n…a₃a₂a₁a₀

这是原始信息，其中a_n是一个分组，可以是一个二进制位，也可以是一个十六进制位。下面我们通过这样的方法对其进行编码：从高位（即左边）开始，将第一个分组与第二个分组进行异或操作，成为编码结果的第一分组，将第二分组与第三分组进行异或操作，成为编码结果的第二分组，依此类推。特别地，将原始信息的最后一个分组和第一个分组的异或值作为编码结果的最后一个分组。

上面的信息经过编码以后变成下面的样子（^为异或操作符号，为了区分每一分组，下面将每一分组用中括号括起来）

[a_n^a_n-1][a_n-1^a_n-2]…[a₂^a₁][a₁^a₀][a_n^a₀]

举例说明，就是下面的样子。

有一段信息，每一个分组是一个十六进制位，这段信息表示为：

B6EC

对于每一个位来说就是

b₃=B b₂=6 b₁=E b₀=C

现在，对这段信息进行编码，假设编码结果为 g₃g₂g₁g₀，那么我们就可以计算出每一位的值

g₃ = b₃ ^ b₂ = B ^ 6 = D

g₂ = b₂ ^ b₁ = 6 ^ E = 8

g₁ = b₁ ^ b₀ = E ^ C = 2

g₀ = b₃ ^ b₀ = B ^ C = 7

这里是对每一个十六进制数进行异或操作，其实也就是按位进行异或操作。

那么编码结果就是

D827

现在的问题是，我们能不能从编码结果D827还原得到原始信息B6EC？

答案是不能。不过，这只是在理论上的不能。在某些情况下，我们可以通过可接受的尝试次数来猜测出原始信息。下面先用自然语言给出证明（就不做严格的证明了），接着说明为什么在某些情况下能猜测出原始信息。

对于一串信息a_n…a₃a₂a₁a₀，我们需要n个分组才能将这个信息完全表示出来。对这个信息进行编码并去掉冗余之后，如果结果的分组数少于n，那么这个结果就不可能完全表示原始信息，这时候这个编码方法就是不可逆的，我们也就不能通过编码结果还原得到原始信息。

对一串原始信息信息Y = a_n…a₃a₂a₁a₀进行编码，得到的最初的编码结果G如下：

G = [a_n^a_n-1][a_n-1^a_n-2]…[a₂^a₁][a₁^a₀][a_n^a₀]

现在结果仍然有n个分组，但是我们还没有检查这个结果是否有冗余，因此现在还不能断言从这个结果可以还原出原始信息。

现在观察G的前n-1个分组，可以发现其中包含了原始信息中从a_n-1到a₁每一个分组2次，即有2个a_n-1，2个a_n-2等等，一直到2个a₁。而这前n-1个分组中，a₀和a_n仅出现了1次。现在我们把前n-1个分组进行异或操作，就如下面所表示的：

[a_n^a_n-1]^[a_n-1^a_n-2]^…^[a₂^a₁]^[a₁^a₀]

异或运算符合分配律和交换律，我们上式变形得到

a_n^[a_n-1^a_n-1]^[a_n-2^a_n-2]^…^[a₂^a₂]^[a₁^a₁]^a₀

任何数与0进行异或结果不变，相同两数进行异或结果为0，我们很容易就可以算出上式的结果

a_n^[a_n-1^a_n-1]^[a_n-2^a_n-2]^…^[a₂^a₂]^[a₁^a₁]^a₀ = a_n^a₀

到这里，我们可以看到，这个结果其实就是G的最后一个分组。所以，我们可以通过G的前n-1个分组，计算出G的最后一个分组。这就是编码结果G中的冗余。这里，G的冗余长度有1个分组，将这一个分组减去以后，G就只剩下n-1个分组，小于原始信息Y的n个分组，这样，我们就无法从G还原出Y了。证明结束。

就是因为这一个小小的冗余，导致了这个编码方法不可逆。但也却是因为这个小小的冗余，我们可以在某些情况下猜测出原始信息。