编码随机1bit增益/损失

我想问一个问题，我试图回答自己，但不能提出任何解决方案。编码随机1bit增益/损失

我想知道的任何算法（或者，如果有可能，至少要证明一个人是否或不存在），这些特性

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

“status_out”是1位大或从“status_out”比原来的“status_in”小1个比特用随机50％的几率
我随时可以回去“status_in”

对不起提前如果这个问题没有很好形成d可能缺少一些重要的细节，但这些基本上是我感兴趣的仅有的两个属性，我不能更精确地改写问题。

非常感谢您的帮助，请让我知道是否有更多的细节可以让我的问题更清楚。

来源

2016-09-16 J. Cassini

“status_in”的所有连接都可能吗？换句话说，如果'status_in'包含'k'位，那么它有没有'2^k'个可能的值？（如果是的话，很容易证明这种算法是不存在的，否则，一个简单的例子就是从一个整数中去掉一个符号位，它必须是正数） – amit

你是什么意思？“我总是可以回到”status_in“ “？ –

@ YvesDaoust基本上是“一对一映射”，还是说它是“可逆的”？这可能是合适的术语。在将算法应用于status_in并且我处于新状态status_out之后，我可以返回。例如“y = x + 1”是“可逆的”，而“y = x^2”则不是。 –

如果使用的status_in所有位（如果存在k位 status_in，那么它可以具有2^k不同的值，从彼此每个不同）：
在这种情况下，很容易显示没有这样的算法。请注意0具有k-1位，因此status_out可能的最大值为2^(k-1)。由于2^k > 2^(k-1)，这意味着有一些x,y（的status_in），例如f(x) = f(y)。但是，如果给出f(x)，则无法确定哪些是原件：x或y。
如果status_in的可能值不包括所有可能性，那么是的。以32位有符号整数（大多数语言中的int）为例，由于其他限制，必须是可能的。您可以删除符号位（始终为0），并获得一个31位数字。既然你知道源始终是可能的，加入0很容易。

来源

2016-09-16 07:43:10 amit

'如果status_in的可能值不包括所有可能性，那么是'。因此，保存一个你需要的数据**至少有一半的数值未被使用。 – MrSmith42

是的，我对任何'2^k' status_in感兴趣。然而1）我**不**试图将所有'2^k'压缩成'2 ^（k-1）'，你的答案似乎暗示了我认同的东西显然是不可能的。我只是想知道，对于任何status_in，status_in'2^k'输入的一半是否可以用'2 ^（k-1）'位编码，而另一半可以用'2 ^（k-1） 2）你的例子是关于*总是删除1位*，这是**不是**我感兴趣的。另外，你的意思是“s/possible/positive”吗？ –

从左到右，一半的时间你都在擦除一点信息，所以通过Landauer's principle你从左到右的过程会导致系统环境中的熵增加。

对于过程是可逆的，从'status_out'恢复'status_in'，你需要有一种从环境中提取熵的方法，即永动机。

来源

2016-09-16 08:21:53

什么？我认为这有点切题，并且与这个问题无关。 “可逆”意味着一对一的映射，比如'y = x + 1'。就这样。此外，“从左到右”并不完全是“删除一些信息”，而是“删除或添加一些信息”。 –

我会忽略在您的问题中使用“随机”一词，并假设您询问确定性算法。因此，当你说50％时，我会认为正好是的一半可能的输入是短一点，而正好是的一半长一点。我还假设您通过某种方式知道输入和输出消息的位长，以便代码可以共享公共前缀。即输出的位串不一定是自行终止的。另外我会假设你不需要编码一个零位长度的输入。至少有一位输入。然而，允许零位输出。

答案是肯定的，如果status_in是单个固定位数。答案是否定的，如果status_in可以是任意位数。

所以如果status_in是ķ比特，然后把它们的一半可以在k-1个比特进行编码，使用所有可能的k-1个位串。另一半可以用可用的四分之一的位串进行编码。这是可逆的。

然而，如果status_in可以是任何数目的位，我们碰到的ķ和K + 2个比特的映射之间的冲突。为了对k位进行编码，我们使用位值的四分之一的位值。然而，为了编码k + 2比特，我们使用全部的比特值。所以没有足够的比特值k + 1。编码1位和3位时首先看到这一点。 1位值之一编码为零位，其他编码为2位。但是，当编码3位时，3位值中的4位编码为可能的2位值的全部，但我们已经使用了1位值中的一位。所以它不能完成。

来源

2016-09-16 15:19:28

编码随机1bit增益/损失

回答

相关问题