标签: reed-solomon

我试图在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 …

我试图在极其有限的嵌入式平台上生成QR码.在一切的规范,似乎除了产生错误纠正码字相当简单.我已经看了一堆现有的实现,他们都试图实现一堆直接超越我的头的多项式数学,特别是关于Galois域.在数学复杂性和内存需求方面,我能看到的最简单的方法是在规范本身中列出的电路概念:

通过他们的描述,我相信我可以实现这一点,除了标有GF(256)加法和GF(256)乘法的部分.

他们提供这个帮助:

QR码的多项式算法应使用逐位模2算术和逐字模100011101算法计算.这是2 ^ 8的伽罗瓦域,其中100011101表示场的素数模数多项式x ^ 8 + x ^ 4 + x ^ 3 + x ^ 2 + 1.

这对我来说几乎都是希腊人.

所以我的问题是:在这种伽罗瓦域算术中执行加法和乘法的最简单方法是什么？假设两个输入数字都是8位宽,我的输出也需要是8位宽.几个实现预先计算,或硬编码在两个查找表中以帮助解决这个问题,但我不确定如何计算这些,或者我将如何在这种情况下使用它们.我宁愿不为这两个表采用512字节内存命中,但它实际上取决于替代方案.我真的需要帮助了解如何在此电路中执行单个乘法和加法运算.

我目前正在尝试让schifra库运行以进行一些测试,以便稍后在我的代码中实现它.

我目前正在查看schifra_reed_solomon_example02.cpp并尝试了解如何设置值以满足我的需求.

/* Finite Field Parameters */
   const std::size_t field_descriptor                 =   8; // GF(2^8) ok
   const std::size_t generator_polynommial_index      = 120; // what is this?
   const std::size_t generator_polynommial_root_count =  32; // polynomial up to x^32

   /* Reed Solomon Code Parameters */
   const std::size_t code_length = 255;  // amount of symbols in codeword
   const std::size_t fec_length  = 32;  // minimal distance d ?
   const std::size_t data_length = code_length - fec_length; // amount of symbols my message has

所以我试图得到的是一个RS代码,n,k,d =(128,16,113)

我将继续以下内容:

/* Finite …

我正在一个项目中，我需要将896字节的数据编码为128字节的代码字。CCSDS在pdf的第15页上定义了我项目的所有规范。 http://public.ccsds.org/publications/archive/101x0b3s.pdf 该文档中未明确指定的一些内容是J = 8，E = 16（255/223）和I = 4。

我已经多次阅读了这篇文章（以及其他许多文章），但是我似乎丝毫不了解所发生的事情。我什至尝试了在http://zxingnet.codeplex.com/SourceControl/latest#trunk/Source/lib/common/reedsolomon/GenericGF.cs中找到的代码

而且对我也不起作用。有人为此工作吗？我需要一些指导，因为磨了这么长时间后我感到迷失了。

对我来说，最好的解决方案是将信息错误地插入zxing代码中。

根据我的理解,DVB-T数据包通过两个FEC系统,即Viterbi,数据丢失高达50%,RS,数据丢失高达10%.这些被称为外部和内部编码.

我无法理解第二次RS编码的需要(在这种情况下,188字节长的MPEG-TS数据包又增加了20个字节).

更具体地说,损坏的数据包会发生什么,例如55%？维特比解码器是否修复了50%的错误,而RS的剩余5%错误是固定的？

对不起我的傻瓜.

在我的数据结构课程中，我想为我的最终项目创建一个二维码生成器。但是，我在理解其中的“格式化错误更正”部分时遇到了一些麻烦。我想使用 11 (L) 的纠错和 100（每隔一行）的掩蔽模式。由于我是一名本科生，我想尽量简单地处理版本 1 QR 代码并使用字节编码。

然后就是不明白数据输出后怎么搞出纠错框。

我正在测试此存储库中的 Reed Solomon 算法，以便在外部发生变化时恢复信息。

假设：

m = bits per symbol
k = data
r = redundance 
n = bits per block = r + k = 2^m - 1
t = error correction = (n - k) / 2

我可以使用以下参数编码和恢复信息：

m = 8
n = 255
r = 135
k = 120
t = 67

并且完美运行，我可以恢复 67 个错误。

我的假设是：

• 只有数据会被破坏，没有冗余。
• 要获得完全恢复 n = 3 * k --> r = 2 * k。
• 那么 n = 255 所以在这种情况下 r …

我正在开发一个对象存储项目，我需要了解Reed Solomon纠错算法，我已经阅读了这篇文档作为入门者以及一些论文。
1. content.sakai.rutgers.edu
2. theseus.fi
但我似乎无法理解单位矩阵的下部（红色框），它来自哪里。这个计算是如何进行的？

谁能解释一下这一点。

我在C#中有一个带有SQL Server数据库的应用程序.我在记事本中收到一些文件,一列用Reed-Solomon算法加密.

有人能告诉我如何使用Reed-Solomon算法解码/纠正SQL Server或C#中某些字符串中的错误？

谢谢!