错误检测和纠错算法

4
假设我们有一块数据,它来自具有以下属性的数据传输介质:
  • 总块大小为8字节
  • 数据传输是不可靠的,因此可能存在位数错误。
  • 数据传输是循环的,并且块的开头是未知的。例如,代码0123456789ABCDEF3456789ABCDEF012(0123456789ABCDEF << 12)和02468ACF13579BDE(0123456789ABCDEF << 1)相同。接收端应该通过代码本身确定开头。
在这种情况下,最好的差错检测和纠错算法是什么?当然,这总是在有用数据量和成功验证(纠正)概率之间进行权衡。

错误检测/纠正是由您可以承受的错误量定义的。那是1吗? - amit
我想考虑不同的方法:0位(校验和),1位,2位或更多。 - alexey
1
@Philip:“总块大小为8字节”。位粒度使这变得棘手。如果旋转对齐到字节,那么我可以想到一种方法来使用(10,9)Reed-Solomon进行检测,并且至少具有(11,9)Reed-Solomon的1位纠正。另一方面,如果数据重复发送(例如在该周期中一遍又一遍地发送),那么这本身就足够冗余,您可以仅使用简单的傅里叶变换来解决问题。 - Mysticial
你能解释一下你第三个要点的原因吗?数据是否正在重复传输?通常这可以通过起始和停止位来解决。 - Nick Johnson
是的,数据会被重复传输。因此,信号是: ...0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF0123456... 我们不知道接收端何时开始。而且它不是字节对齐的(我们可以从任何位开始)。 - alexey
显示剩余2条评论
3个回答

1

这只是对完整问题的部分回答,因为我不会回答如何确定起始点。请参考mcdowella的答案。我本来想把这个作为评论,但它太长了。

对于连续传输的消息,实际上不再需要任何纠错了。即使发生一个位翻转(或一堆位翻转),它也不太可能影响每个被传输的相同位的实例 - 特别是如果它一直重复。因此,在这个意义上,你的冗余因子是N,其中N随着广播的进行趋近于无穷大。

因此,现在重建你的64位非常容易,因为你有很多样本可以查看。假设接收器知道周期长度,你可以轮询流并计算每个位置的每个位的出现次数。

所以说,在完成100个周期后,你得到:

Bit #    0s / 1s    Interpret bit as
Bit 0:  100 /   0        0
Bit 1:    0 / 100        1
Bit 2:   99 /   1        0
Bit 3:   98 /   2        0
Bit 4:    1 /  99        1
...
Bit 63:  96 /   4        0

基于这些样本,您可以统计出正确的位值是什么。接收器继续接收周期的时间越长,您的界限就越强。因此,如果传输了足够的周期,您可以容忍任意高的错误率。

当然,这适用于任何周期长度 - 不仅仅是64位。因此,将此方法与mcdowella的方法结合使用(由于索引足迹,数据大小可能会增加)。

如果接收器不知道周期长度,则有两种方法可以找出它:

  1. 猜测长度并运行轮询。不断尝试不同的长度,直到获得非常高的相关性为止。(每个位的高置信水平)

  2. 对接收到的数据执行傅里叶变换。假设数据不是过于嘈杂,这将立即显示出周期。


很遗憾,无法等待100个样本。时间太长了。我们最多只能等待2-3个样本。 - alexey

1

这里有一个尝试,其中一些想法来自于http://en.wikipedia.org/wiki/Frame_Relay

每个64位块都以固定的头部01110开头。当您拥有更多的头部信息(例如序列号或交替位标志、校验和等),您可能可以安排使得比特模式01110从未出现。对于任意数据,请将任何0111的出现替换为01111 - 这意味着有效数据速率现在取决于底层数据。让此层的数据提供者确保数据基本上是随机的,例如通过应用http://en.wikipedia.org/wiki/Randomizer。我认为您在这里的总数据损失约为6位,这符合描述0..63的移位所需的6位。

在接收器中,查找01110以标记块的真实开始。如果您没有看到恰好一个这样的模式,则知道该块已被破坏。我认为至少需要两位错误才能同时破坏现有的01110并产生假的01110。

导致块错位的乱码不像典型的比特乱码,因此 CRC 错误率计算不能直接应用。我会在每个块中包含一个非 CRC 校验和 - 可能是 mod 31 或 mod 961 计算的检查,以避免禁止的 5 位模式 01110,尽管取决于相邻的内容,您可能需要更严格。然后,未检测到错误的机会将约为 31 分之 1 或 961 分之 1,对于所有单个错误没有特定的保证,不像多项式 CRC。

我认为你没有足够的空间来合理地进行每个块的纠错,但是你可以在每个 M 个普通块后包括 N 个纠错块,例如使用沿列应用的 SECDED。您可能有例如 57 个数据承载块,然后是 6 个纠错块,将每个有效负载位位置视为承载 57 个数据位和 6 个校验和位。如果错误倾向于破坏单个块的全部或部分(例如通过导致块重新对齐失败),则这应该很好地工作。

评论后 -

编辑

好的,对于一个连续传输的消息,您的带宽较小但相对更多的 CPU。有两件事值得一提:

1) 给定任何校验和或其他消息约束条件,您可以通过考虑所有单比特错误、翻转接收到的消息的一个比特,并查看校验和是否现在有效来实现一些有限的纠错。

2) 可以通过仅查看传递到消息上的5位窗口来检查消息是否符合上述比特填充方案。我认为即使需要调整它以在环绕处正常工作,这也是正确的。这意味着可以通过可处理的大小的BDD(Knuth 4A第7.1.4节)检查消息。这意味着可以计算符合比特填充方案的64位消息数量,并有效地在消息编号和消息之间进行转换(同一节)。因此,您可以将此方案用作数字编码(其中N通过BDD计算)范围内的数字0..N和64位消息,而无需基础随机化或关于要发送的数据的最坏情况假设。事实上,不太优雅,我认为您可以使用具有5位状态的动态规划而不是BDD。


在我的情况下,有一个单一的数据块被无限传输。 - alexey

0
print("-"*25,'CHECKSUM ERROR DETECTION MECHANISM',25*'-')
print("\n",25*"-","At Sender's Side","-"*25,"\n") 
data_bits = input('Enter the Data Bits : ')
checksum_bits = int(input("Enter number of checksum bits: "))
sum="0"
sum = int(sum,2)
for i in range(0, len(data_bits), checksum_bits):
    part_i = data_bits[i: i + checksum_bits]
    print("The Data Part : ",part_i)
    part = int(part_i,2)
    sum = sum+part
binary_sum = bin(sum)
finalsum = binary_sum[2:]
if len(finalsum)==checksum_bits:
    finalsum = finalsum
else:
    finalsum = binary_sum[3:]
def Convert(string):
    list1=[]
    list1[:0]=string
    return list1
final_sum = Convert(finalsum)
def complement(s):
    for i in range (0,len(s)):
      if s[i] == '1':
       s[i] = '0'
      else:
       s[i] = '1'
complement(final_sum)
def convert(s):
    checksum = ""
    return (checksum.join(s))
checksum = convert(final_sum)
print("The Checksum Calculated is: ",checksum)
codeword = data_bits + checksum
print('The Transmitter sequence will be: ',codeword)
print("\n",25*"-","At Receiver's Side","-"*25,"\n")
data_bits1 = input('Enter the Data Bits : ')
checksum_bits1 = int(input("Enter number of checksum bits: "))
sum1="0"
sum1 = int(sum1,2)
for i in range(0, len(data_bits1), checksum_bits1):
    part = data_bits1[i: i + checksum_bits1]
    parts = int(part,2)
    print("The Data Part: ",part)
    sum1 = sum1+parts
    binarysum = bin(sum1)
    finalsum1 = binarysum[2:]
if len(finalsum1)==checksum_bits1:
    finalsum1 = finalsum1 
else:enter code here
    finalsum1 = binarysum[3:]
    final_sum1 = Convert(finalsum1)
    complement(final_sum1)
    value = convert(final_sum1)
print("The Computed Received Sequence: ",value)
if final_sum1.count('1')>0:
    print("This is an Errored Message...Please try Transmitting the Message again.")
else:
    print("The Transmitted Sequence was Received Successfully with no Error Present.")
print("\n",30*"-","DONE","-"*30,"\n")

目前你的回答不够清晰,请[编辑]以添加更多细节,帮助其他人理解它如何回答问题。你可以在帮助中心找到有关如何编写好答案的更多信息。 - Community

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接