use*_*060 1 compression forwarderrorcorrection delta-row-compression
假设有一个1024位的数组全部为零:
示例:[0,0,0,0,0,0,0,...]
然后我用完全随机位置的那些覆盖20个零:
示例:[0,1,0,0,0,0,0,...]
假设我有一个完美的编码器,那么编码这20个随机放置位的位置所需的理论最小位数是多少？
我知道有通信理论方程会告诉我这个,但我想仔细检查我的计算.
更难的红利问题:向我展示一种算法的代码,该算法实现接近此最小限制的编码.
额外奖励:如果位翻转字节级别而不是位级别怎么办？例如整个字节翻转.结果相同？
ceiling(log2(1024选20))= 139位
其他答案说143位,我们知道正好有 20位.这是一个具体的编码,以显示使用该知识的一种方法:使用算术编码,连续发送1024'0'或'1'符号中的每一个.第一个符号在20/1024的概率为'1'时加权; 但每个后来的符号加权不同.如果第一个符号为'0',则在下一个符号上使用20/1023; 但如果它是'1',请使用19/1023.以同样的方式继续到最后.只要我们告诉它正确的概率,算术编码就可以完成大约139位的所有艰苦工作.
关于"奖金奖励":错误更正不在原始问题中.您可以在首次找到最佳编码之前对错误纠正代码进行分层,假设没有错误,如上所述(这通常是解决问题的好方法).你不会失去任何编码效率,虽然我认为你可能会失去稳健性 - 例如,如果你得到的错误超过你的ECC可以纠正的错误,那么这个消息会不会像垃圾邮件一样出现还是会更优雅地降级？