- 总块大小为8字节。
- 数据传输是不可靠的,因此可能存在位数错误。
- 数据传输是循环的,并且块的开头是未知的。例如,代码0123456789ABCDEF与3456789ABCDEF012(0123456789ABCDEF << 12)和02468ACF13579BDE(0123456789ABCDEF << 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的方法结合使用(由于索引足迹,数据大小可能会增加)。
如果接收器不知道周期长度,则有两种方法可以找出它:
猜测长度并运行轮询。不断尝试不同的长度,直到获得非常高的相关性为止。(每个位的高置信水平)
对接收到的数据执行傅里叶变换。假设数据不是过于嘈杂,这将立即显示出周期。
这里有一个尝试,其中一些想法来自于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。
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")