Jas*_*n S 4 encoding redundancy information-theory
这是一个计算机科学/信息理论问题,而不是一个简单的编程问题,所以如果有人知道一个更好的网站发布这个,请告诉我.
假设我有一个N位数据,将在M个消息中冗余发送,其中至少M-1个消息将被成功接收.我对以每个消息更少的比特编码N比特数据的不同方式感兴趣.(这类似于RAID但是在更小的级别,其中N = 8或16或32)
示例:假设N = 16且M = 4.那么我可以使用以下算法:
1st and 3rd message: send "0" + bits 0-7
2nd and 4th message: send "1" + bits 8-15
如果我能保证4个消息中的3个消息将通过,则每个组中至少有一条消息将通过.因此,我可以用9位或更少的位来完成这项工作,可能有一种方法可以用更少的总位来做到这一点,但我不知道如何.
是否有一些简单的编码/解码算法来做这种事情？这个问题有名字吗？(如果我知道它叫什么,我可以谷歌吧!)
注意:在我的特定情况下,消息要么正确到达,要么根本没有到达(没有消息到达有错误).
(编辑:将第二部分移到另一个问题)
(不完整的答案如下.我可能会在以后添加更多.)
您可能感兴趣的术语是信道编码:向源添加冗余,以便在噪声信道上传输时使其稳健.在信息理论中,信道编码的互补问题是源编码:减少源中的冗余以使用更少的比特来表示它.(这两个问题的组合称为联合源 - 信道编码.)
您的第一个问题是要求查找频道代码.您提供的简单示例类似于重复代码,即您发送相同的消息超过两次(通常是奇数次),然后最常接收的消息被接受为原始消息.
这段代码效率低下.为了使用标准符号,设k =原始消息中的比特数,n =发送消息中的比特数.对于您的示例,k = 16且n = 36. 编码效率的度量是k/n,其中更高意味着更有效.在你的情况下,k/n = 0.44.这很低.
重复码是一种简单的块码,即,将冗余添加到每个k比特块以创建n比特的码字.其他人提到的汉明和里德 - 所罗门码也是如此.使用一些基本的线性代数,汉明码相对容易理解.
这些应该足以让您自己搜索.祝好运.