編碼隨機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增益/損失

回答

相關問題