当前位置：文江博客话题详情

错误检测和纠错算法

发布于 2024-12-03 01:33:29 字数 431 浏览 1 评论 0原文

假设我们有一个来自数据传输介质的数据块，具有以下属性：

总块大小为8 字节。
数据传输不可靠，因此可能存在多个位错误。
数据传输是循环的并且块的开始是未知的。例如，代码 0123456789ABCDEF 与 3456789ABCDEF012 (0123456789ABCDEF << 12) 和 02468ACF13579BDE (0123456789ABCDEF << 1) 相同。接收端应由代码本身确定开头。

对于这种情况最好的错误检测和纠错算法是什么？当然，它始终是每个块的有用数据量和成功验证（纠正）概率之间的折衷。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

裸钻 2024-12-10 01:33:29

这是一个尝试，其中一些想法来自 http://en.wikipedia.org/wiki/Frame_Relay。

每个 64 位块都以固定标头 01110 开始。如果您有更多标头信息（例如序列号或交替位标志、校验和...），您可以安排位模式 01110 永远不会出现。对于任意数据，将任何出现的 0111 替换为 01111 - 这意味着有效数据速率现在取决于基础数据。让该层的数据提供者确保数据几乎是随机的，例如通过应用 http:// en.wikipedia.org/wiki/Randomizer。我认为这里的总数据丢失约为 6 位，这符合描述 0..63 移位所需的 6 位。

在接收器中，查找 01110 来标记块的真正开始。如果您没有看到确切的一种这样的模式，那么您就知道该块已经出现了乱码。我认为至少需要两位错误才能破坏现有的 01110 并产生假的。

导致块未对齐的乱码看起来不像典型的位乱码，因此 CRC 错误率计算不会立即应用。我会在每个块中包含一个非 CRC 校验和 - 也许是计算出 mod 31 或 mod 961 的检查，以避免禁止的 5 位模式 01110，尽管根据与此相邻的内容，您可能需要更加严格。未检测到错误的几率约为 31 分之一或 961 分之一，与多项式 CRC 不同，对所有单个错误没有特别保证。

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

评论后-

编辑

好，通过一条连续传输的消息，您的带宽更少，但相对更多的CPU。我想到两件事：

1) 给定任何类型的校验和或对消息的其他约束，您可以通过例如考虑所有单位错误、翻转接收到的消息的一些位并查看校验和现在是否有效来实现一些有限的纠错。

2) 可以通过仅查看消息上传递的 5 位窗口来检查消息是否符合上面建议的位填充方案。我认为即使您需要调整它才能在环绕时正常工作，这也是正确的。这意味着消息可以通过易于处理的大小的 BDD 进行检查（Knuth 4A 第 7.1.4 节）。这意味着您可以计算符合位填充方案的 64 位消息的数量，并在消息编号和消息（同一部分）之间进行高效转换。因此，您可以使用此方案，而无需对要发送的数据进行底层随机化或最坏情况假设，只需将其视为 0..N 范围内的数字的编码（其中 N 将通过 BDD 计算）和64 位消息。事实上，不太优雅的是，我认为您可以使用具有 5 位状态的动态编程来代替 BDD。

Here is an attempt with some ideas pinched from http://en.wikipedia.org/wiki/Frame_Relay.

Start off each 64-bit chunk with a fixed header of 01110. Where you have more header info (e.g. sequence number or alternating bit flag, checksum...) you can probably arrange that the bit-pattern 01110 never appears. For arbitrary data, replace any occurrence of 0111 with 01111 - meaning that the effective data rate now depends on the underlying data. Have the provider of data to this layer make sure the data is pretty much random, e.g. by applying a http://en.wikipedia.org/wiki/Randomizer. I think your total data loss here is about 6 bits, which fits with the 6 bits necessary to describe a shift of 0..63.

In the receiver, look for 01110 to mark the true start of the chunk. If you do not see exactly one such pattern, you know that the chunk has been garbled. I think it takes at least a two-bit error to both destroy an existing 01110 and produce a fake one.

Garbles that cause chunk misalignment don't look like typical bit garbles, so CRC error rate calculations won't apply out of the box. I would include a non-CRC checksum in each chunk - perhaps a check calculated mod 31 or mod 961 so as to avoid the forbidden 5-bit pattern 01110, although depending on what abuts this you may need to be more restrictive. The chance of an error not being detected would then be about 1 in 31 or 1 in 961, with no particular guarantee about all single errors, unlike polynomial CRC.

I don't think you have enough space to do per-chunk error correction sensibly, but you could include N error correction chunks after every M ordinary chunks, using e.g. SECDED applied down the columns. You might have e.g. 57 data-bearing chunks and then 6 error correction chunks, treating each payload bit position as bearing 57 data bits and then 6 checksum bits. This should work well if errors tend to corrupt all or none of a single chunk e.g. by causing chunk realignment to fail.

after comment -

EDIT

OK, with one continuously transmitting message you have less bandwidth but relatively more cpu. Two things come to mind:

1) Given any sort of checksum or other constraint on the message you can achieve some limited error correction by e.g. considering all single bit errors, flipping a bit of the received message, and seeing if the checksum now works.

2) A message can be checked to see if complies with the bit-stuffing scheme suggested above by looking at only a 5-bit window passed over the message. I think this holds true even if you need to tweak it to work properly at the wraparound. This means that a message can be checked by a BDD of tractable size (Knuth 4A section 7.1.4). This means that you can count the number of 64-bit messages that comply with the bit-stuffing scheme and convert efficiently between message number and message (same section). So you can use this scheme without underlying randomisation or worst-case assumptions about the data to be sent, by just regarding it as an encoding of a number in the range 0..N (where N is to be computed via BDDs) and a 64-bit message. In fact, less elegantly, I think you could use dynamic programming with a 5-bit state instead of BDDs.

回复收藏 0 原文

东京女 2024-12-10 01:33:29

这只是整个问题的部分答案，因为我不会回答如何确定起点。请参阅 mcdowella 的回答。我本想将其作为评论，但它太长了。

对于连续传输的消息，实际上不再需要任何纠错。即使发生一个位翻转（或一堆翻转），也不太可能影响正在传输的同一位的每个实例 - 特别是如果它永远重复的话。因此，从这个意义上说，您的冗余因子是 N，其中随着广播的进行，N 接近无穷大。

因此，重建 64 位现在非常容易，因为您有很多样本可供查看。假设接收器知道周期长度，您只需轮询流并计算 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 的方法结合起来（由于索引足迹，数据大小可能会增加）。

如果接收器不知道周期周期，有两种方法可以计算出：

猜测长度并运行轮询。对不同的长度继续执行此操作，直到获得具有非常高相关性的长度。（每个位的置信度很高）
对接收到的数据执行傅立叶变换。假设数据的噪声不是太离谱，这将立即显示周期。

This is only a partial answer to the full question as I will not answer how to determine the start point. Refer to mcdowella's answer for that. I intended this to be a comment, but it's too long.

With a continuously transmitted message, there really is no need for any error-correction anymore. Even if a one bit-flip (or a bunch of them) occurs, it's unlikely it will affect every single instance of the same bit being transmitted - especially if it's being repeated forever. So in this sense, your redundancy factor is N where N approaches infinity as the broadcast goes on.

So reconstructing your 64-bits is now very easy since you have many samples to look at. Assuming the receiver knows the cycle length, you can just poll the stream and count how many occurrences of each bit for each of the 64 positions.

So say after 100 complete cycles, you get:

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

Based on these samples, you can statistically figure out what the correct bit values are. The longer the receivers continues to receive the cycle, the stronger your bounds are. So you can tolerate an arbitrarily high error-rate if enough cycles are transferred.

Of course this applies to any cycle length - not just 64-bits. So combine this method with mcdowella's (and the data size will probably increase due to the index-foot-print).

If the cycle period isn't known to the receiver, there are two ways to figure it out:

Guess the length and run the polling. Keep doing this for different lengths until you get a length with a very high correlation. (high confidence levels for each of the bits)
Perform a Fourier Transform on the received data. This will instantly reveal the period assuming the data isn't too ridiculously noisy.

回复收藏 0 原文

北方的韩爷 2024-12-10 01:33:29

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")

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")

回复收藏 0 原文

~没有更多了~