标签: error-correction

我试图在Python中实现一个Reed-Solomon编码器解码器,支持解码擦除和错误,这让我发疯.

该实现目前仅支持解码错误或仅解码,但不能同时解码两者(即使它低于2*错误+删除的理论界限<=(nk)).

从Blahut的论文(这里和这里),似乎我们只需要用擦除定位多项式初始化错误定位多项式,以隐式计算Berlekamp-Massey内的勘误定位多项式.

这种方法部分适用于我:当我有2*错误+删除<(nk)/ 2时它可以工作,但事实上在调试之后它只能起作用,因为BM计算错误定位多项式,它获得与擦除定位多项式完全相同的值(因为我们低于仅错误校正的限制),因此它被galois字段截断,我们最终得到了擦除定位多项式的正确值(至少我理解它的方式,我可能是错的).

然而,当我们超过(nk)/ 2时,例如如果n = 20且k = 11,那么我们有(nk)= 9个擦除的符号我们可以纠正,如果我们输入5个擦除然后BM就会出错.如果我们输入4个擦除+ 1个错误(我们仍然远低于界限,因为我们有2*错误+删除+ 2 + 4 = 6 <9),BM仍然出错.

我实现的Berlekamp-Massey的精确算法可以在本演示文稿中找到(第15-17页),但是在这里和这里可以找到非常相似的描述,在这里我附上了数学描述的副本:

现在,我将这个数学算法几乎完全复制到Python代码中.我想要的是扩展它以支持擦除,我尝试通过使用擦除定位器初始化错误定位器sigma:

def _berlekamp_massey(self, s, k=None, erasures_loc=None):
    '''Computes and returns the error locator polynomial (sigma) and the
    error evaluator polynomial (omega).
    If the erasures locator is specified, we will return an errors-and-erasures locator polynomial and an errors-and-erasures evaluator polynomial.
    The parameter s is the syndrome polynomial (syndromes encoded in …

我正在努力将大量扫描文档数字化,使用Tesseract 3作为我的OCR引擎.其输出的质量是平庸的,因为它通常在实际文本之前和之后产生垃圾字符,并且在文本中产生拼写错误.

对于前一个问题,似乎必须有策略来确定哪些文本实际上是文本,哪些文本不是(大部分文本都是人的名字,所以我正在寻找除了查找单词之外的解决方案字典).

对于拼写错误的问题,大多数错误源于一些错误的字母分类(例如,替换l,1并且I相互替代),似乎应该有猜测哪些单词拼写错误的方法(因为没有太多的单词)英语中间有一个"1",并猜测适当的修正是什么.

这个领域的最佳实践是什么？是否存在执行此类操作的算法的免费/开源实现？谷歌已经收到了很多论文,但并没有太多具体内容.如果没有可用的实施,那么多篇论文中的哪一篇将是一个很好的起点？

编码和初始化4字节消息到8字节是否在数学上是可行的,如果8字节中的一个完全丢弃而另一个错误重建初始4字节消息？将无法重新传输,也不会知道丢弃字节的位置.

如果使用Reed Solomon纠错,并在4"数据"字节的末尾添加4个"奇偶校验"字节,例如DDDDPPPP,并且最终得到DDDEPPP(其中E是错误)并且丢弃了奇偶校验字节,我不相信有一种方法可以重建最初的信息(虽然如果我错了,请纠正我)......

如何将初始4字节消息乘以(或执行另一个数学运算)常数,然后利用逆数学运算的属性来确定丢弃的字节.或者,对消息的结构施加一些约束,因此每隔一个字节需要是奇数而其他字节需要是偶数.

或者,也可以是4个十进制数字,而不是字节,它可以以某种方式编码成8个十进制数字,其中可以在上述相同的情况下检测和纠正错误 - 没有重传和丢弃的字节的位置是未知的.

我正在寻找任何人可能拥有的任何疯狂的想法......有什么想法吗？

编辑:

它可能有点人为,但我想解决的情况是你有一个错误的打印机,它将重要数字打印到表格上,然后邮寄给使用OCR的加工公司阅读表格.OCR不会是完美的,但它应该只有数字才能读取.有故障的打印机可能是一个更大的问题,它可能会丢弃一个整数,但没有办法知道它会丢弃哪一个,但它们将始终以正确的顺序出现,不会有任何数字交换.

表格可以改变,以便它总是在最初的四个数字和纠错数字之间打印一个空格,即1234 5678,这样就可以知道是否丢弃了1234个初始数字或者删除了5678个纠错数字,如果是使问题更容易解决.我认为它们有点类似于他们如何通过算法验证信用卡号码,但是有四位数的块.

希望这能为我正在寻找的东西提供一些澄清......

我知道使用CRC的全部意图是进行错误检测,但是我听到有人声称除了错误检测之外它还可以用来进行基本的纠错.如果是这样的话,我很好奇,如果是这样,它有多强大？我的意思是,我们通常将CRC称为能够执行x位检测,但我很好奇它是否能够执行x位校正.如果是这样,这是如何工作的？谢谢.

我有短的,可变长度的十进制数字,如:#41551,由人类手动转录.Mistyping one会导致不良结果,所以我首先想到的是使用Luhn算法来添加校验和 - #41551-3.但是,这只会检测错误,而不是纠正错误.似乎添加另一个校验位应该能够检测并纠正一位数的错误,所以给定#41515-3?(换位错误)我将能够恢复正确的错误#41551.

像Hamming代码这样的东西看起来似乎是正确的地方,但我无法弄清楚如何将它们应用于十进制,而不是二进制数据.是否有针对此用途的算法,或汉明/里德 - 所罗门等是否可以适应这种情况？

我正在寻找一种在微控制器上编码相对容易/快速的前向纠错码; 解码将在PC上完成,因此可能更复杂.

我不太了解纠错码,除了简单的汉明码,它们似乎都比我能处理的更复杂.

有什么建议？

编辑:我要简短地接受卡尔的回答......我想有两件事我没有提到:

(1)我并不严格需要纠错,这对我来说是有利的,我认为可能会有一些纠错算法,这对于最小的成本来说是一个合理的好处.汉明码可能是合适的,甚至看起来它们对我的编码应用来说可能太昂贵了.

(2)比纠错本身更大的优点是能够正确地重新同步到出错的数据包.(如果我长时间不同步,这很糟糕)所以我认为如果我保持简单,那就更好了.

我学习了汉明码以及如何使用它们来纠正1位错误并检测所有2位错误,但是如何将其扩展到纠正2位,甚至更多？

纠正所有2位错误所需的最小位数是多少？

我正在尝试设置一个在名称中执行纠错的算法.我的方法是拥有一个具有正确名称的数据库,计算每个数据库之间的编辑距离和输入的名称,然后建议最接近的5或10.

此任务与单词中的标准纠错有很大不同,因为某些名称可能会被首字母替换.例如,"Jonathan Smith"和"J. Smith"实际上相当接近并且可以很容易地被认为是相同的名称,因此如果不是0,编辑距离应该非常小.另一个挑战是,某些名称可能会以不同的方式写入相同.例如Shnaider,Schneider是由具有不同语言环境的人编写的同名版本(我猜有更好的例子).另一种情况 - 想象一下所有可能出现的错误Jawaharlal Nehru,其中大多数错误与真实姓名无关.再次,他们中的大多数可能会发音相似.

显然Lucene的纠错算法对我没有帮助,因为它没有处理上述情况.

所以我的问题是:你知道任何能够在名称中进行纠错的库吗？你能提出一些处理上述案例的算法吗？

我对c ++或java中的库感兴趣.至于算法提议,任何语言或伪代码都可以.

ECC(错误校正码)如何进行突发错误纠正(磁盘驱动器样式)？

这要么是诅咒,要么是祝福,但我的大脑常常试图在梦中解决技术问题.有时确实如此.就像昨晚一样,我的大脑要求了解如何设计ECC算法(软件程序,但最终可能是FPGA电路),以实现适合磁盘驱动器的ECC.适用于这些设备的ECC类型似乎是"突发错误检测".

据我了解,磁盘驱动器出错的原因是磁盘表面的缺陷(规格或划痕).当磁头读取数据位并经过一个窄的划痕时,电路在大约1到64位的"突发"上产生正确和错误位值的随机混合.因此,据我所知,磁盘驱动器ECC的目标是能够纠正任何一个随机错误突发中的所有错误位.

顺便说一句,我自然不会"在数学中思考",所以请不要指向数学论文!我已经花了几个小时试图阅读维基百科关于里德 - 所罗门和其他各种计划,但这些文章中的数学对我来说是完全不可理解的(除非我花了几个星期研究它们......如果我很幸运).此外,从文本中,我认为这些方案中的任何一种都不适用于磁盘驱动器(但可能是CD/DVD).

无论如何,我将描述我的大脑在睡梦中想到的是什么,并要求任何人解释这种ECC实际应该如何完成,以及传统方法有多好.我确信我的计划效率必须低于某人知道他们在做什么,甚至可能在他们醒着时设计的技术!在我醒来之前,我试图找出如何处理每个轨道的两次爆发,但是醒来时失败了.所以我也问如何实现这一目标.

我的心理图像是一个4096字节的扇区,我精神上分成512个块,每个64位(因为我习惯于考虑64位块,因为我猜测64位突发错误就足够了出于实际目的.在我的应用程序中,每个数据流肯定是4096到8192字节.

我的方法是从4096字节的数据中计算10个64位ECC代码.因此ECC我的方案将在4096字节数据的最后一个之后写入十个64位代码== 80字节,这只是2%的开销.我将这十个64位ECC代码称为"code0"到"code9",每个代码在处理每个扇区之前开始清零.而且每个64位(8字节)数据序列都会因为缺少更好的术语而称之为"块".

code9 = XOR chunks 000 to 511 == 000 to 1FF : every chunk
code8 = XOR chunks 256 to 511 == 100 to 1FF : every chunk # with bit #8 == 1
code7 = XOR chunks 128 to 255 == 080 to 0FF : every chunk # with bit #7 == 1
        and chunks 384 to 511 == 180 to 1FF
code6 = XOR chunks 064 to 127 …

我不知道要寻找什么，因为我得到的所有与“错误纠正代码”有关的东西都与您不知道错误位置的情况有关。因此，这些代码比我需要的要复杂得多，效率低下。

在下文中，请注意位等于数据包（因为仅可能丢失整个数据包，因此该位模拟非常适合）。

是否存在已考虑到您已经知道k位丢失的ECC，而仅提供给您一种在那k个位置重构数据流的方法？另外，由ECC添加的位应该是独立的（最好）。这样，如果数据包的ECC部分内部发生数据包丢失，它仍然可以重构一些原始数据（并非总是会出现k个错误，大多数情况下不会出现任何错误。因此，ECC容错自己是很重要的ECC位已添加）。

这与IMO有很大的不同。对于一个简单的缺失位，我只能使用一个XOR位。但是我不够聪明，无法将其概括为n位。

再说一次，我有n位数据流，而且我知道最多有k位丢失（我真的知道确切是哪一个，并且它们丢失了，不可能发生损坏）。现在，我需要一个编解码器，它可以以尽可能少的开销添加到数据流中来重构它们。我梦想着拥有（n + k）位来纠正n位流中的k个随机位错误:)。最重要的是，理想情况下，如果添加到n位数据流中的k个 ECC位中的任何一个遭到破坏，例如k个位中的c个位都被破坏，那么它仍然应该能够重构（kc）位错误。n位流。