我正在发送长度为 32 位的数据位流（消息）。我想在这些消息中添加纠错码。例如 16 位“奇偶校验”位。作为第一种方法，我使用 RS(6,4) 而不是 GF(256) – 因此，数据被视为 4 个字节，并添加两个字节的纠错码。据我了解，对于这种 RS 配置，整个 6 字节消息中的一个字节可能会被更改（损坏），而 RS 解码算法仍然能够恢复原始消息。（如果两个字节被损坏，RS 解码将发出不可恢复的错误信号）。
因此，理论上，一个字节的所有 8 位都可以更改，消息仍然可以恢复。但是，在这种情况下可能出现的错误的本质是，每个位都可能以一定的概率发生变化。因此，如果只有两个位在某些随机位置更改，而不是在同一个字节内，则使用 RS(6,4)/GF(256) 将无法恢复消息。如果任何 5 位发生变化，我都想恢复。
更新
Reed Solomon 似乎不适合这里，因此：使用哪种 ECC？需要多少个奇偶校验位？
- 数据大小为32位，只有一条消息会被反复发送。
- 每个位被翻转的概率高达 15%（我们可以与 10% 进行比较）。
- 我希望能够尽快可靠地解码 32 位数据。如果第一个数据包（32 位数据 + X 位奇偶校验）损坏且无法恢复，则接收方将等待下一个数据包（完全相同的数据 + 奇偶校验）并重试。但在大多数情况下，接收第一条消息就足够了。
- 解码可能需要大量计算。
朴素算法
根据针对不同问题的答案，我想出了以下简单的算法：
- 向 32 位消息添加一些 CRC（例如 CRC-16 或 CRC-24）
- 在接收端，如果 CRC 不匹配，则迭代所有可以翻转 1,2,3,4,5 位的方式（这会产生几百万次迭代 = (48 选择 1) + (48 选择 2) + (48 选择 3) + (48 选择 4) + (48 选择 5) – 我同意这个。
这有意义吗？如果有意义的话 – 我可以纠正的最大位数是多少：
- 32位数据+CRC-16
- 32位数据+CRC-24
- 322位数据 + CRC-32
在某些时候，测试 N 个翻转位将产生与不同有效消息的冲突。这就是各种 CRC 的 N 吗？
更新2
rcgldr 评论将我引向了 BCH 代码。我将此实现移植到 C# 上，对代码字 48 位、数据 24 位、奇偶校验位 24 位和纠错容量 4 进行了一些测试。在最多 4 个错误的情况下，它可以完美运行，但当有 5 个错误时，它经常会出错 – 错误未被检测到，解码器认为它已成功解码（printf("Incomplete decoding: errors detected\n")从未达到该行）。
那么这里还有另一个问题：既然 BCH 是纠错码，这是否意味着它们无法检测超出纠错能力的错误？或者链接的实现存在缺陷？
最后：如何实现纠错和检测能力？例如：能够纠正最多 4 个错误并检测最多 7 个错误，数据长度 24 位，解码复杂度不重要。
更新 3
到目前为止，我已经从这里翻译了可用的 BCH c# 代码
C# 版本在此： https:
我仍然不知道如何创建纠错代码，以便能够纠正最多 4 个错误，同时检测我的 24 位数据 + 所需奇偶校验位的最多 7 个错误
更新 4
我使用@rcgldr 代码来运行实验 – 测试错误多于纠错能力的用例：
结果与我的直觉相符，如果代码的纠错能力=5，但有 6 个错误，则解码失败（无法解码）或在纠正 5 个错误后给出无效的代码字。（事实上，在某些罕见情况下，代码在进行 6 次纠正后会恢复有效的代码字 – 这应该是不可能的，但我猜这只是一些幸运的情况？）
- 上述结论确定吗？如果有 6 个错误，那么总会有解码错误，或者正好纠正了 6 个错误（针对某个随机代码字）？
- 如果是这样，我可以使用完全相同的代码来纠正 4 个错误并检测最多 6 个错误吗？（简单地将第 5 个错误的纠正视为检测到错误，而不是纠正）？或者有更好的方法吗？
- 如何调整此代码以适应不同的错误上限和数据长度？
更新 5 + 解决方案
接受答案中的代码可以解决问题 – 最多可纠正 4 个错误并检测最多 7 个错误。唯一的困难是它使用无符号长整型来存储和处理代码字 – 这与使用无符号乘法一起提供了出色的性能。性能对我来说不是问题，因此，为了清楚起见，我可能会重写它以使用位数组（整数数组：零和一）来表示代码字。
13
最佳答案
2
比特流纠错码有很多种，其中许多用于各种电信标准。例如，低密度奇偶校验、卷积码、Turbo 码等。许多此类代码支持“软”解码，其中每个比特的确定性级别可用于执行最大似然解码，从而增加找到正确码字的概率。
其中任何一种都更适合您的应用。许多此类代码都具有高度可配置的速率，以实现不同的稳健性水平，让您能够根据传输介质的质量精确选择要添加多少纠错。
12
-
感谢您指出 Reed Solomon 不适合我的场景。假设：消息大小增加约 50% 是可以接受的，数据大小约为 32 位，我希望能够纠正一些损坏的位，计算性能（速度）并不重要。此外，我将反复传输消息，因此我需要一些前导码来标记消息的边界，没有时钟来同步。
– -
你通过什么介质传输？无线？你考虑过使用现有协议（如 LoRA）而不是自己开发吗？无论如何，任何
2/3-rate 代码都可以为你解决问题，尽管它无法让你避免丢失前导码。
–
-
我不是通过无线电传输的。我是在音频/视频流中传输信息（眼睛/耳朵无法察觉），并希望从音频/视频录制/重播中检索原始内容的信息。从（可能质量下降的）录音中提取消息位后，我预计一些位会被更改。2/3 速率是理想的，但我很难找到 RSC 或 turbo 码的参考实现。我认为如果我在比特流中搜索已知长度的重复模式（容忍一定数量的翻转位），我可以省略前导码，因为消息将被重复。
– -
你使用的是什么语言？如果你四处搜索，会发现很多实现，尽管我不能保证任何具体实现。
– -
什么样的 2/3 速率代码可以检测并纠正 15% 的误码率，也就是每 7 位最多有 1 个坏位。
–
|
在一些罕见的情况下，代码会恢复有效的代码字，但错误比预期的多
Berlekamp Massey 解码器有时会生成比预期次数更大的多项式。可以通过检查多项式大小来防止这种情况，但如果意外的多项式是错误的，则会在 Poly2Root() 生成根时发现它。如果使用缩短的代码字（在这种情况下少于 63 位），则会检查根以查看其中是否有任何对应于超出范围的索引，这也可以防止错误更正。
8 个综合征仅适用于 4 位错误，但一些 5、6、7 位错误将被纠正（7 位非常罕见）。
Sugiyama 扩展欧几里得解码器不会生成比预期更高次数的多项式。
使用 X86 无进位乘法内在函数对 PCLMULQDQ 进行操作的示例 Visual Studio 2022 C# 代码：Pclmulqdq.CarrylessMultiply()。30 位数据，33 位奇偶校验。纠正 1 到 4 位错误并检测 5 到 7 位错误，使用 11 个综合征进行编码和检测，并使用 8 个综合征进行纠正。校正使用 Berlekamp Massey 解码器，或者如果 #define EEUCLID 使用 Sugiyama 扩展 Euclid 解码器。校正后，使用编码逻辑 ReEncode() 检查代码字是否有效，而不是重新生成和检查 11 个综合征。代码测试 63 位中 1 到 7 位的所有 628,882,431 种组合。这在我的笔记本电脑上花了将近 25 分钟（C 版本花了 17 分钟）。每 1,048,576 次循环显示 * 作为进度指示器，大约 600 *。
// bch6347.cs 63 bit codeword, GF(2^6)
// correct 4 bits, detect 7 bits
// 2024NOV04 14:45
// if EEUCLID defined use Sugiyama extended Euclid decoder
// else use Berlekamp Massey decoder
//#define EEUCLID
using System.Runtime.Intrinsics;
using System.Runtime.Intrinsics.X86;
using System.Numerics;
using static System.Runtime.InteropServices.JavaScript.JSType;
using System;
namespace xcs
{
#if EEUCLID
public class EUCLID
{
public byte size;
public byte indx;
public byte[] data;
public EUCLID() => this.data = new byte[62];
}
#endif
public class VECTOR
{
public byte size;
public byte[] data;
public VECTOR() => this.data = new byte[32];
}
public class Program
{
const byte POLY = 0x43; // GF(2^6) = x^6 + x + 1
const byte ALPHA = 0x02;
const byte NSYN = 11;
const byte NFIX = 8;
static byte[] vZeroes = new byte[32]; // zeroes
static byte[] exp64 = new byte[128]; // exp64 table
static byte[] log64 = new byte[64]; // log64 table
static byte[] minplyf = new byte[128]; // minimum polynomial flags
static byte[] minply = new byte[64]; // minimum polynomials
static byte mincnt; // # of minimum polymials
static Vector128<ulong> poly; // generator poly
static Vector128<ulong> invpoly; // 2^64 / POLY
static Vector128<ulong> msg; // message
static Vector128<ulong> par; // parities
static ulong msgorg; // original message
static ulong msgenc; // encoded message
static ulong msgerr; // received message
static ulong msgfix; // fixed message
static VECTOR vSyndromes = new VECTOR(); // syndromes
#if EEUCLID
static EUCLID ED = new EUCLID(); // for GenpErrors EE
static EUCLID ER = new EUCLID();
static EUCLID ET = new EUCLID();
#else
static VECTOR vB = new VECTOR(); // for GenpErrors BM
static VECTOR vC = new VECTOR();
static VECTOR vT = new VECTOR();
static VECTOR vBx = new VECTOR();
#endif
static VECTOR pErrors = new VECTOR(); // error locator polynomial
static VECTOR vLocators = new VECTOR(); // locators
static VECTOR vOffsets = new VECTOR(); // offsets
static byte GFAdd(byte b0, byte b1) /* add */
{
return (byte)(b0^b1);
}
static byte GFSub(byte b0, byte b1) /* subtract */
{
return (byte)(b0^b1);
}
static byte GFMpy(byte b0, byte b1) /* multiply */
{
int m2;
if(0 == b0 || 0 == b1)
return 0;
m2 = (int)log64[b0]+(int)log64[b1];
return exp64[m2];
}
static byte GFDiv(byte b0, byte b1) /* divide */
{
int m2;
if(0 == b0)
return 0;
m2 = (int)log64[b0]+63-(int)log64[b1];
return exp64[m2];
}
static byte GFPwr(byte b0, byte b1)
{
if(b1 == 0)
return 1;
if(b0 == 0)
return 0;
return exp64[(byte)((log64[b0]*(uint)b1)%63)];
}
static byte GFMpy0(byte b0, byte b1)
{
byte i;
byte product;
product = 0;
for(i = 0; i < 6; i++){
product <<= 1;
if(0x40 == (product & 0x40))
product ^= POLY;
if(0x20 == (b0 & 0x20u))
product ^= b1;
b0 <<= 1;}
return product;
}
static void InitGF()
{
int i;
byte b = 1;
for(i = 0; i < 128; i++){
exp64[i] = b;
b = GFMpy0(b, ALPHA);
}
log64[0] = 0xff;
for(i = 0; i < 63; i++){
log64[exp64[i]] = (byte) i;}
}
static int GenPoly()
{
ulong M;
ulong N;
ulong Q;
int x;
byte mpoly; /* test polynomial */
byte sum; /* sum, looking for zeroes */
byte apwr; /* alpha to power */
byte i,j;
/* find minimum and non-duplicate polynomials for m[1] -> m[NSYN] */
i = 0;
do{
apwr = GFPwr(ALPHA,++i);
for(mpoly = 0x02; mpoly <= 0x7f ; mpoly++){
sum = 0;
for(j = 0; j <= 6; j++){
if(0 != (mpoly&(1<<j)))
sum ^= GFPwr(apwr,j);
}
if(sum == 0){
if(minplyf[mpoly] != 0)
continue;
minplyf[mpoly] = 1;
minply[mincnt] = mpoly;
mincnt += 1;
break;
}
}
}while(i < NSYN);
poly = Vector128.Create((ulong)(minply[0]), 0x0000000000000000ul);
for(i = 1; i < mincnt; i++){
poly = Vector128.Create((ulong)(minply[i]), poly.GetElement<ulong>(0));
poly = Pclmulqdq.CarrylessMultiply(poly, poly, 0x01);
}
// generate 2^64 / poly
x = 63-BitOperations.LeadingZeroCount(poly.GetElement<ulong>(0));
M = 1ul<<x;
N = M>>1;
Q = 0x0ul;
for(i = 0; i < 65-x; i++){
N <<= 1;
Q <<= 1;
if(0 != (N&M)){
Q |= 1;
N ^= (poly.GetElement<ulong>(0));
}
}
invpoly = Vector128.Create(Q, 0x0000000000000000ul);
return 63-BitOperations.LeadingZeroCount(poly.GetElement<ulong>(0));
}
static void Encode()
{
par = Pclmulqdq.CarrylessMultiply(msg, invpoly, 0x00); // par[1] = quotient
par = Pclmulqdq.CarrylessMultiply(par, poly, 0x01); // par[0] = product
par ^= msg; // par[0] = remainder
msg ^= par; // msg[0] = encoded message
}
static int ReEncode()
{
par = Pclmulqdq.CarrylessMultiply(msg, invpoly, 0x00); // par[1] = quotient
par = Pclmulqdq.CarrylessMultiply(par, poly, 0x01); // par[0] = product
par ^= msg; // par[0] = remainder
if(0ul == par.GetElement<ulong>(0))
return 0;
return 1;
}
static void GenSyndromes()
{
ulong M;
byte x;
byte i, ap, s;
vSyndromes.size = NFIX;
for (i = 0; i < NFIX; i++)
{
M = msg.GetElement<ulong>(0);
ap = GFPwr(ALPHA, (byte)(i+1));
s = 0;
while (0 != M)
{
x = (byte)(63 - BitOperations.LeadingZeroCount(M));
M ^= 1ul << x;
s ^= GFPwr(ap, x);
}
vSyndromes.data[i] = s;
}
}
static int Poly2Root(ref VECTOR vDst, ref VECTOR pSrc)
{
byte bLcr; // current locator
byte bSum; // current sum
byte bV; // index to pVDst
byte i, j;
vDst.size = (byte)(pSrc.size-1);
if (vDst.size == 0)
return 0;
bV = 0;
bLcr = 1;
for (j = 0; j < 63; j++){
bSum = 0; // sum up terms
for (i = 0; i < pSrc.size; i++){
bSum = GFMpy(bSum, bLcr);
bSum = GFAdd(bSum, pSrc.data[i]);}
if (0 == bSum){ // if a root
if (bV == vDst.size){ // exit if too many roots
return 1;}
vDst.data[bV] = bLcr; // add locator */
bV++;}
bLcr = GFMpy(bLcr, ALPHA);} // set up next higher alpha
if (bV != vDst.size) // exit if not enough roots
return 1;
return 0;
}
#if EEUCLID
static int GenpErrors()
{
// class EUCLID: left side R[] is msb first | right side A[] is lsb first (reversed)
int i;
byte bME; // max errors possible
byte bQuot; // quotient
// ED = initial ED: E0.R[-1] = x^MAXERR, E0.A[0] = 1
ED.size = NFIX+2;
ED.indx = NFIX+1;
ED.data[0] = 1;
Array.Clear(ED.data, 1, NFIX);
ED.data[ED.indx] = 1;
// ER = initial ER: E1.R[0] = syndrome polynomial, E1.A[-1] = 0
ER.size = NFIX+2;
ER.indx = NFIX+1;
ER.data[0] = 0;
Array.Copy(vSyndromes.data, 0, ER.data, 1, NFIX);
Array.Reverse(ER.data, 1, NFIX);
ER.data[ER.indx] = 0;
// init bME
bME = NFIX/2;
// Euclid algorithm
while (true)
{ // while degree ER.R > max errors
while ((ER.data[0] == 0) && // shift dvsr left until msb!=0
(ER.indx != 0))
{ // or fully shifted left
ER.indx--;
Array.Copy(ER.data, 1, ER.data, 0, ER.size - 1);
ER.data[ER.size - 1] = 0;
}
if (ER.indx <= bME)
{ // if degree ER.R[] <= bME, break
break;
}
while (true)
{ // while more sub-divide steps
if (0 != ED.data[0]) // if ED.R[] msb!=0, update ED, ER
{
bQuot = GFDiv(ED.data[0], ER.data[0]); // bQuot = ED.R[msb]/ER.R[msb]
for (i = 0; i < ER.indx; i++)
{ // ED.R[]=ED.R[]-Q*ER.R[]
ED.data[i] = GFSub(ED.data[i], GFMpy(bQuot, ER.data[i]));
}
for (i = ED.indx; i < ER.size; i++)
{ // ER.A[]=ER.A[]-Q*ED.A[]
ER.data[i] = GFSub(ER.data[i], GFMpy(bQuot, ED.data[i]));
}
}
if (ED.indx == ER.indx) // if sub-steps done, break
{
break;
}
ED.indx--; // shift ED left
Array.Copy(ED.data, 1, ED.data, 0, ED.size - 1);
ED.data[ED.size - 1] = 0;
}
ET = ER; // swap ED, ER
ER = ED;
ED = ET;
}
pErrors.size = (byte)(ED.size-ED.indx); // set pErrors.size
if((ER.indx) >= pErrors.size){ // if degree ER too high
goto fail0;}
// pErrors = ED.A[] without unreversing = Lambda reversed
Array.Copy(ED.data, ED.indx, pErrors.data, 0, pErrors.size);
// Make most significant coef pErrors == 1 (divide by it)
bQuot = pErrors.data[0];
if(bQuot == 0){
goto fail0;}
for(i = 0; i < pErrors.size; i++){
pErrors.data[i] = GFDiv(pErrors.data[i], bQuot);}
// Find roots of pErrors (if fail, then set for no roots)
if(0 == Poly2Root(ref vLocators, ref pErrors)){
return 0;}
fail0:
pErrors.size = 1; // handle no root case
pErrors.data[0] = 1;
vLocators.size = 0;
return 1;
}
#else
static int GenpErrors()
{
byte i, j, n;
byte L, m;
byte b, d;
byte db;
b = 1; // discrepancy when L last updated
L = 0; // number of errors
m = 1; // # iterations since L last updated
vB.size = 1;
vB.data[0] = 1;
vC.size = 1;
vC.data[0] = 1;
for (n = 0; n < NFIX; n++){
if (0 != (n&1)){ // BCH only, if odd step, d == 0
m += 1;
continue;}
d = vSyndromes.data[n]; // calculate discrepancy
for (i = 1; i <= L; i++){
d = GFAdd(d, GFMpy(vC.data[(vC.size - 1) - i], vSyndromes.data[n - i]));}
if (d == 0){ // if 0 increment m, continue
m += 1;
continue;}
vT.size = vC.size; // vT = vC
Array.Copy(vC.data, vT.data, vC.size);
db = GFDiv(d, b); // db = (d/b)
vBx.size = (byte)(vB.size+m); // Bx = x^m B
Array.Copy(vB.data, vBx.data, vB.size);
Array.Clear(vBx.data, vB.size, m);
for (i = 0; i < vBx.size; i++){ // Bx *= db
vBx.data[i] = GFMpy(vBx.data[i], db);}
j = (byte)(vBx.size-vC.size); // right shift vBx or vC
if ((sbyte)j > 0){
Array.Copy(vC.data, 0, vC.data, j, vC.size);
Array.Clear(vC.data, 0, j);
vC.size += j;}
else if ((sbyte)j < 0) {
j = (byte)(0-j);
Array.Copy(vBx.data, 0, vBx.data, j, vBx.size);
Array.Clear(vBx.data, 0, j);
vBx.size += j;}
for (i = 0; i < vC.size; i++){ // C -= Bx
vC.data[i] = GFSub(vC.data[i], vBx.data[i]);}
if (n < 2*L){ // if L not increasing
m += 1;
continue;}
vB.size = vT.size; // B = T
Array.Copy(vT.data, vB.data, vT.size);
L = (byte)(n+1-L); // update L
b = d; // update b
m = 1;} // reset m
pErrors.size = vC.size; // pErrors = reversed VC
Array.Copy(vC.data, 0, pErrors.data, 0, vC.size);
Array.Reverse(pErrors.data, 0, vC.size);
if (0 != Poly2Root(ref vLocators, ref pErrors)){
pErrors.size = 1; // handle no root case
pErrors.data[0] = 1;
vLocators.size = 0;
return 1;}
return 0;
}
#endif
static void GenOffsets()
{
byte i;
vOffsets.size = vLocators.size;
for (i = 0; i < vLocators.size; i++)
{
vOffsets.data[i] = log64[vLocators.data[i]];
}
}
static void FixErrors()
{
byte i;
for (i = 0; i < vOffsets.size; i++)
msg = Vector128.Create(msg.GetElement<ulong>(0)^(1ul<<vOffsets.data[i]), 0x0000000000000000ul);
}
static void InitCombination(ref int[] a, int k, int n)
{
for (int i = 0; i < k; i++)
a[i] = i;
--a[k - 1];
}
static int NextCombination(ref int[] a, int k, int n)
{
int pivot = k - 1;
while (pivot >= 0 && a[pivot] == n - k + pivot)
--pivot;
if (pivot == -1)
return 0;
++a[pivot];
for (int i = pivot + 1; i < k; ++i)
a[i] = a[pivot] + i - pivot;
return 1;
}
static int Main(string[] args)
{
int[] ptn = new int[7]; // error bit indexes
int n; // number of errors to test
int i;
ulong c = 0ul;
Array.Clear(vZeroes);
InitGF();
n = GenPoly();
Console.WriteLine("# parity bits: {0:D}", n);
msgorg = 0x789abcde00000000ul; // test message
msg = Vector128.Create(msgorg, 0x0000000000000000ul);
Encode();
msgenc = msg.GetElement<ulong>(0);
for (n = 1; n <= 7; n++){ // test 1 to 7 bit error patterns
InitCombination(ref ptn, n, 63);
while (0 != NextCombination(ref ptn, n, 63)){
msgerr = msgenc;
for (i = 0; i < n; i++)
msgerr ^= 1ul<<ptn[i];
msg = Vector128.Create(msgerr, 0x0000000000000000ul);
msgfix = msgerr;
GenSyndromes(); // generate syndromes
if(0 == GenpErrors()){ // generate error location info
GenOffsets(); // convert to offsets
FixErrors(); // correct error bits
msgfix = msg.GetElement<ulong>(0);}
if (msgenc == msgfix) // if fixed continue
continue;
if (n <= 4 || 0 == ReEncode()){
Console.WriteLine("\nfailed");
return 0;}
if((++c & 0xffffful) == 0ul)
Console.Write("*");
}
}
Console.WriteLine("\npassed");
return 0;
}
}
}
15
-
感谢提供此代码。我稍后会测试它，但与此同时，我使用代码来处理 BCH，其代码字为 48 位，数据为 24 位，奇偶校验位为 24 位，纠错容量为 4。如果我引入最多 4 个错误 – 它工作正常，但出现 5 个错误时，它通常检测不到错误（未达到 printf(“Incompletecoding: errorsdetected\n”); 行）并输出错误解码的数据。这是预期的吗？如果除了纠正最多 4 个错误之外，我还希望能够检测到 5、6 和 7 个错误，该怎么办？是的，我不知道如何将 _mm_clmulepi64_si128 移植到 c#
–
-
@PanJanek 如果容量为 4，则意味着距离为 8-9 – 也就是说，代码字保证至少在 8-9 个位置上有所不同。因此，如果您翻转 5 位，那么您很有可能更接近与开始时不同的代码字，算法将朝着该代码字进行纠正。您可以纠正最多 4 个错误，或检测最多 7-8 个错误，但不能同时进行。
–
-
1@PanJanek – 我更新了我的答案。它现在具有 4 位校正 + 7 位检测的 C# 代码。
– -
1@PanJanek – 答案不够详细。你可以从下载 C 版本。
– -
1@PanJanek – 最大总大小为 63 位。NSYN/2 是检测位数，NFIX/2 是校正位数。您需要检查编码多项式的大小来确定数据位数。
–
|
–
–
–
–
–
|