algorithm - 具有随机 1bit 增益/损失的编码

Question

我想问一个我试图自己回答但无法想出任何解决方案的问题。

我想知道任何具有这些属性的算法(或者是否有可能至少证明一个算法是否存在)

              +-----------+
status_in --> | ALGORITHM | --> status_out
              +-----------+

1. “status_out”比原始“status_in”大 1 位或小 1 位，随机概率为 50%
2. 从“status_out”我总能回到“status_in”

如果问题的格式不正确并且可能缺少一些重要的细节，请提前道歉，但这基本上是我感兴趣的仅有的两个属性，我无法更准确地重新表述问题。

预先感谢您的帮助，如果我可以提供更多详细信息以使我的问题更清楚，请告诉我。

Answer 1

1. 如果 status_in 的所有位都被使用(如果 k 位在status_in，那么它可以有2^k个不同的值，每个不同从彼此):
   在这种情况下，很容易证明不存在这样的算法。首先请注意 status_out 有 k-1 位，因此 status_out 可能的最大值数是 2^(k-1 )。由于 2^k > 2^(k-1)，这意味着存在一些 x,y(属于 status_in)使得 f(x) = f(y)。但是，给定 f(x)，您无法分辨哪个是原始的:x 或 y。
2. 如果 status_in 的可能值不包括所有可能性，那么是。以 32 位有符号整数(大多数语言中的 int)为例，由于某些其他限制，它必须是可能的。您可以删除符号位(始终为 0)，并获得 31 位数字。由于您知道来源始终是可能的，因此添加 0 很容易。