bm算法应用

❶ bm算法求出的视差图是什么类型值

preFilterType：预处理滤波器的类型，主要是用于降低亮度失真（photometric distortions）、消除噪声和增强纹理等, 有两种可选类型：CV_STEREO_BM_NORMALIZED_RESPONSE（归一化响应） 或者 CV_STEREO_BM_XSOBEL（水平方向Sobel算子，默认类型）, 该参数为 int 型；
preFilterSize：预处理滤波器窗口大小，容许范围是[5,255]，一般应该在 5x5..21x21 之间，参数必须为奇数值。

❷ 指出BM算法与KMP算法的区别

KMP算法和BM算法，它们分别是前缀匹配和后缀匹配的经典算法。
1、因为路由表中的每个表项都指定了一个网络，所以一个目的地址可能与多个表项匹配。最明确的一个表项，即子网掩码最长的一个，就叫做最长前缀匹配。
2、之所以这样称呼它，是因为这个表项也是路由表中，与目的地址的高位匹配得最多的表项。

❸ BM算法好后缀问题

BM算法，是Berlekemp_Massey算法吗！？

没上面那么费劲吧？

想要的话，明天把我的给你.....

说明我只是为了求出结果，并没有考虑其它的因素，所以比较简单

晕，我以为是移位寄存器里的BM算法....

❹ （近世代数）证明：M是R的极大理想，当且仅当R/M是单环。

阵列形式的零点定理 设R是一个QF环. 下述三个问题是非常重要的. 借鉴Hilbert Nullstellensatz定理的含义, 把它们总称为阵列形式的零点问题.
问题A(弱零点问题）：若I是R[X]的理想, 且I与R[X]不相等, 则是否存一个非全零阵列b, 使得 b是AnnM(I)中的元素 ? 问题B(零点问题）：下述恒等式是否成立 I=AnnR[X](AnnM(I)) (1)
Macaulay 在名着[9]中着力研究的逆系(Inverse Systems)问题与问题A, B是密切相关的. 在证明(2)式时, 他采用了dialytic arrays方法. 然而,我们认为Macaulay的方法只适合于理想 是零维时的情形. D. G. Northcott(1974)[11]给出了公式（1）的完全证明.
问题C(强零点问题）： 设R是QF环, 给定R[X]的一个多项式理想I, 是否存在一个由有限个LRA阵列生成的R[X]-子模M, 使得I=AnnR[X](M)
. 当R=F是域时, 问题C是多维线性系统理论中的一个重要研究课题. 这个问题实质上是问能否用有限个行为(behavior)数据确定整个系统. C. Heij(1992)得到了一些进展. 这个问题直到最近才由 S. Zampieri(1997)[13] 对F[X]=F[x,y]时给出了的肯定的解答. 我们发现Macaulay[9]有个论断: 对R[X]的任意理想I, Ann(I)一定是有限生成R[X]-模. 如果利用Macaulay的这个论断, 再利用Macaulay的公式（3），则问题C似乎可以轻松地解决. 然而, 经过细致地分析, 我们发现Macaulay的这个论断是不对的, 他的证明只有当$I$是零维理想时才通得过. 那么， 要使Macaulay的论断成立， 是否一定要加上$I$是零维理想这个条件吗？ 本文将解决这个问题。
定理A (弱零点定理)： 设R是QF环, I是 R[X] 的任意一个理想. 则AnnM(I)非零 当且仅当 I与R[X]不等。
定理B (零点定理): 设R是QF环, I是R[X]的任意一个理想. 则 I=Ann(Ann(I)) 定理C(强零点定理)： 设R是QF环, I是R[X]的任意一个理想. 则存在M的一个有限生成R[X]-子模M, 使得I=AnnR[X](M).
问题D： 设 M是任意一个由有限个R上的LRA生成的M的R[X]-子模, 是否存在R[X]的一个理想I, 使得M=AnnM(I)? 当R是一个域时, Macaulay([9],p71)用 dialytic方法证明了这个‘定理’. 然而，我们认为，这个证明也只能在 是有限生成R-模时才能通过. 实际上,我们将证明： 定理D: 设R是一个QF环, M是M的有限生成R[X]-子模, 则M是R[X]的某理想的零化阵列模, 当且仅当M是有限生成R-模. 定理E: 设R 是一个有限域,M=<a,…b> 是M的有限生成R[X]-子模, 其中a,…, b是阵列. 则存在R[X]的理想I使得M=Ann(I) 当且仅当每个LRS阵列a,b最终周期的(即：不计初始的有限项外是周期的）.三、零化阵列模的结构与Nechaev问题

问题E： 设I是 R[X]的一个理想, 给出I恰是某个LRA阵列的特征理想的判别准则, 即给出充要条件.
当n=1且R是一个唯一因子分解整环(简记为UFD)时, 问题就不简单.当n=1且R是一个有零因子的环时，问题更难以处理。当R为Potential整环时, 即要求R和R[[x]]都是UFD时, Fitzpatrick 和 Norton(1995)[7]证明R[x]中的理想I恰是一个LRS的特征理想的充分必要条件是I是由一个首一多项式生成的主理想。我们要在R是一般的UFD上给出R上LRS的特征理想的刻画。 问题F：设R是QF环, 给定R[X]的一个理想I. 问在什么条件下，AnnM(I)是一个循环R[X]-模. 我们得到下面简明的解析判别公式。 定理F：设F是一个域，F[X]的零维理想I是F上一个LRA阵列的特征理想，当且仅当
dimF (I:rad(I))/I =dimR F[X]/rad(I).
上述判别公式中的数值是容易用Grobner基理论中常规的算法计算, 所有这些计算须对I进行准素分解.
当R是Artin局部主理想环且$I$是准素理想时, Nechaev[10]给出了Ann(I)恰是一个R上的一个LRS生成的循环模的判别准则， 该判别需用到对I的准素分解。他在该文中提出了如下三个未解决的问题. Nechaev公开问题1: 设R是局部Artin主理想环, I 是R[x]的理想, 给出一个判别零化序列模Ann(I)是循环R[x]-模的准则, 且要求该判别只与理想I(或I的生成元)有关, 而不依赖于I的准素分解的. Nechaev公开问题2: 当R是任意QF环时, 对R[x]的任意一个理想I，建立规范生成系(简记CGS)(Canonical Generator System)的概念, 以便能够方便地判别理想I的代表元的归属问题, 即：对任意f(x) in R[x], 能否有算法方便地判别f(x) in I与否. Nechaev公开问题3:} 在Nechaev问题2相同的条件下, 给出构造性的方法求出R[x]-模Ann(I)的生成元系并进一步给出循环性的判别. 我们利用定理F的结果和方法，解决了Nechaev公开问题1。上述三个Nechaev问题中，真正有实在意义和难度的是Nechaev问题1。因为, 我们证明了 定理G： Nechaev的CGS恰是极小Grobner 基.
因此, 只要QF环R拥有如下两个附加条件：
a. R中的元素能够用计算机可接受的形式表示出,
b. 能用计算机实现“+", “x"运算和求解系数在R上线性方程.
则我们可以借助环上的Grobner基理论, 解决Nechaev问题2, 并用解决Nechaev问题1的同样方法解决Nechaev问题3.
四、理想的零化阵列模的基构造
当R是有限域, R[X]=R[x,y]是两个变元的多项式环时, 文献[8]通过刻划I的约化Grobner基的标准型, 给出了类似于(2)式中一维LRS的基的具有漂亮组合性质的二维LRA基.
我们采用与[8]中不同的方法, 对任意n和任意零维理想I, 求出Ann(I)的生成元组. 我们的工作是基于Grobner基理论和一些基本的同调代数知识. 实际上, 我们利用如下的对偶定理。
定理H: 设I是R[X]的任意理想, 则Ann(I)与Hom(R[X]/I,R) 是R[X]-模同构

五、Galois环上的阵列

八十年代以来, Nechaev[10], Kurakin, Kuzmin等对环上的LRS和LRA作了大量的研究. 有关的综述报告参见Mikhalev & Nechaev(1996) [15]. 进入九十年代, 由于Calderbank等[6]关于Galois环上的代数编码理论的突破性进展， 由于剩余类环Z/(m)环上的编码成功地应用于编码与调制相结合体制, 因而Galois环上的编码问题，在国际信息论学术界引起了极大的兴趣和研究热潮.
A. A. Nechaev 的论文[10]是研究交换环上LRS的一篇重要文献. 该文主要做了两项工作. 1). 在R上线性递归序列的有限生成子模格与单变元多项式环R[x]中的首一理想格之间建立了Galois对应. 2). 在更特殊的Artin主理想环上, 对R[x]中的理想I, 给出I的零化线性递归序列R-模Ann_R(I)是循环R[x]-模的判别准则. 应该注意的是, [10]中给出的循环模的判别准则是基于构造Ann(I)的R-模生成元组, 然后根据这些生成元之间的复杂关系, 给出Ann(I)是循环R[x]-模的判别准则, 而且他的判别准则涉及到对理想的准素分解. 求对多项式理想的准素分解的算法一直是一个困难的问题, 尽管可以用Grobner 理论给予解决, 但是这些算法依然是很复杂的.

六、 LRA的综合问题
如何有效地求解综合问题一直是信息论, 系统论, 控制论和密码学等许多学科中活跃的重要研究课题. 域上有限序列最小特征多项式的综合问题是由Berlekamp(1968)[17]和Massey(1969)解决的. 他们给出的着名的B-M算法已成为工业标准. B-M算法的计算复杂性是O(m2), 其中 是序列的长度. 而用常规的解线性方程组的方法的复杂性是O(m3). BM算法解决KeyEquation的求解。
在R=Z/(m)剩余类环, 且n=1时, Reed 和 Sloane(1985)[12]给出了BM算法的推广. KeyEquation缺乏代数的结构性. 作者(1993)[3]提出用齐次关键方程HKeyEquation代替KeyEquation的新方法, 这样不但有极好的代数结构性质, 具有更广的适用性. 我们已证明, 求KeyEquation的解与求HKeyEquation的解是等价的[3]. HKeyEquation容易推广到对LRA的综合, 且可以用于代数几何码的译码. 基于我们齐次化方法的同样思路, 周锦君等(1996)[14]将HKeyEquation推广用于求解剩余类环上的阵列的综合. 最近, J. Althaler & A. Dur (1996)[5]也开始使用齐次化方法研究序列的综合，但他们用逆幂级数表示序列，而相应的特征多项式是常规的多项式， 因此序列和特征多项式不在同一个环中，无法直接利用Grobner基理论和Syzygy的计算。 实际上，他们给出的综合算法必须要借助已有叠代算法. 通过齐次化方法, 我们(1993[3])已证明LRA的综合算法与Grobner基有很好的联系. 本文将进一步揭示综合算法的每一步与Grobner基有精密联系.

七、 主要结果

我们简要列举本文得到的主要新结果.
设R是局部Artin主理想环（或更广的Quasi-Frobeniou环), 是R的极大理想， F=R/m是域, R[X]多元多项式环, I,J 是R[X]的任意理想. M,N是R上的某些阵列构成的R[X]-模. 则：
1． (弱零点定理)：Ann(I)=0当且仅当I=R[X].
2. (零点定理)： Ann(Ann(I))=I.
3. (强零点定理)：存在有限个阵列生成的R[X]-模M, 使得 I=Ann(M).
4. Ann(I)是有限个阵列生成的R[X]-模, 当且仅当, I是零维理想, 当且仅当
Ann(I)是有限个阵列生成的R-模.
5. 有限个阵列生成的R[X]-模M是R[X]的某理想的零化阵列模当且仅当M 是有限生成R-
模.当R是域, I 是R[X]的零维理想. 则存在阵列a使得I=Ann(a) 当且仅当
dimF (I:rad(I))/I =dimR F[X]/rad(I).
6. 解决Nechaev 的3个Open问题
7. Ann(Ann(M))=M 当且仅当M是有限生成R-模. 这样既推广了Macaulay的逆系定理, 又指出Macaulay的原逆系定理的不确切之处, 并给出了逆系定理成立的充要条件.
8. 当R是主理想局部环时, 给出R[x]的理想I的Grobner基的标准型, 和计算I的Grobner基的快速算法, 并给出对I准素分解的基于Grobner基理论的算法.
9. 给出阵列的代数表示和计算Ann(I) 的 R-模基的新方法.
10. 揭示序列综合的Belerkamp-Massey 与Grobner 基之间的紧密联系
11. 当R是UFD, I是R[x]的理想. 则I是某个LRS序列的特征理想当且仅当I是由首一多项式生成的主理想. 从而推广了Fitzpatrick 的结果.

❺ 面试必备——BM字符串查找算法

字符串的一种基本操作是子字符串查找：给定一端长度为N的文本字符串text和一个长度为M(M<N)的模式字符串pattern，在文本字符串中查找和该模式字符串相同的子字符串。在这互联网时代，字符串查找的需求在很多情景都需要，如在文本编辑器或浏览器查找某个单词、在通信内容中截取感兴趣的模式文本等等。

子字符串查找最简单的实现肯定是暴力查找：

可以看到，暴力查找的最坏时间复杂度为O(N*M)，实际应用中往往文本字符串很长（成万上亿个字符），而模式字符串很短，这样暴力算法的时间复杂度是无法接受的。

为了改进查找时间，人们发明了很多字符串查找算法，而今天的主角 BM算法 （Bob Boyer和J Strother Moore发明，简称BM算法）就是其中的一种。

不同于暴力查找算法的逐个字符对比，BM算法充分使用 预处理模式字符串 的信息来尽可能跳过更多的字符。在暴力算法中，比较一个字符串都是从首字母开始，逐个比较下去。一旦发现有不同的字符，就需要从头开始进行下一次比较，就需要将字串中的所有字符一一比较。BM算法的核心思路在于，文本字符串从左到右检索，模式字符串从右到左检索，当模式字符串的一个字符pattern[j]和文本字符串的字符text[i+j]不匹配时，那么在模式字符串中查找字符text[i+j]是否存在索引k，使得pattern[k] == text[i+j]，k若存在， k应该为满足条件的最右索引 。此时存在三种情景：

通过这种字符的移动方式来代替逐个比较，正是BM算法的高效的关键所在！那么我们怎么知道文本字符串的字符是否存在于模式字符串中？对的，预处理。我们在查找前，先建立一张包含文本字符串的所有字符的字母表， 这张表中记录着字母表中的每个字符在模式字符串中出现的最靠右的索引，如果在字符在模式字符串中不存在，那么值为-1。

有了这张表，我们在查找时就可以高效的移动i。构建这张表很简单：

构建好表，我们只需要按上面分析的情景，出现字符不匹配时，通过表，把i向右平移到具体位置即可。BM完整算法实现如下：

由于不匹配的情况属于大多数，所以一般情况下，BM算法的时间复杂度为O(N/M)，是线性级别的！可以说是非常高效了。但它需要额外的空间字母表大小R，所以BM算法是以空间换时间的。

至此，BM字符串查找算法已经分析完了，其实算是一种比较简单的算法，学习起来很快就能搞懂～

面试必备——KMP字符串查找算法

❻ 求字符串匹配BM算法的代码，要c或者c++的。

BM算法的C语言实现：

// 函数：int* MakeSkip(char *, int)
// 目的：根据坏字符规则做预处理，建立一张坏字符表
// 参数：
// ptrn => 模式串P
// PLen => 模式串P长度
// 返回：
// int* - 坏字符表
int* MakeSkip(char *ptrn, int pLen)
{
int i;
//为建立坏字符表，申请256个int的空间
//PS:之所以要申请256个，是因为一个字符是8位，
// 所以字符可能有2的8次方即256种不同情况
int *skip = (int*)malloc(256*sizeof(int));

if(skip == NULL)
{
fprintf(stderr, "malloc failed!");
return 0;
}

//初始化坏字符表，256个单元全部初始化为pLen
for(i = 0; i < 256; i++)
{
*(skip+i) = pLen;
}

//给表中需要赋值的单元赋值，不在模式串中出现的字符就不用再赋值了
while(pLen != 0)
{
*(skip+(unsigned char)*ptrn++) = pLen--;
}

return skip;
}

// 函数：int* MakeShift(char *, int)
// 目的：根据好后缀规则做预处理，建立一张好后缀表
// 参数：
// ptrn => 模式串P
// PLen => 模式串P长度
// 返回：
// int* - 好后缀表
int* MakeShift(char* ptrn,int pLen)
{
//为好后缀表申请pLen个int的空间
int *shift = (int*)malloc(pLen*sizeof(int));
int *sptr = shift + pLen - 1;//方便给好后缀表进行赋值的指标
char *pptr = ptrn + pLen - 1;//记录好后缀表边界位置的指标
char c;

if(shift == NULL)
{
fprintf(stderr,"malloc failed!");
return 0;
}

c = *(ptrn + pLen - 1);//保存模式串中最后一个字符，因为要反复用到它

*sptr = 1;//以最后一个字符为边界时，确定移动1的距离

pptr--;//边界移动到倒数第二个字符（这句是我自己加上去的，因为我总觉得不加上去会有BUG，大家试试“abcdd”的情况，即末尾两位重复的情况）

while(sptr-- != shift)//该最外层循环完成给好后缀表中每一个单元进行赋值的工作
{
char *p1 = ptrn + pLen - 2, *p2,*p3;

//该do...while循环完成以当前pptr所指的字符为边界时，要移动的距离
do{
while(p1 >= ptrn && *p1-- != c);//该空循环，寻找与最后一个字符c匹配的字符所指向的位置

p2 = ptrn + pLen - 2;
p3 = p1;

while(p3 >= ptrn && *p3-- == *p2-- && p2 >= pptr);//该空循环，判断在边界内字符匹配到了什么位置

}while(p3 >= ptrn && p2 >= pptr);

*sptr = shift + pLen - sptr + p2 - p3;//保存好后缀表中，以pptr所在字符为边界时，要移动的位置

// PS:在这里我要声明一句，*sptr = （shift + pLen - sptr） + p2 - p3;
// 大家看被我用括号括起来的部分，如果只需要计算字符串移动的距离，那么括号中的那部分是不需要的。
// 因为在字符串自左向右做匹配的时候，指标是一直向左移的，这里*sptr保存的内容，实际是指标要移动
// 距离，而不是字符串移动的距离。我想SNORT是出于性能上的考虑，才这么做的。
pptr--;//边界继续向前移动
}

return shift;
}

// 函数：int* BMSearch(char *, int , char *, int, int *, int *)
// 目的：判断文本串T中是否包含模式串P
// 参数：
// buf => 文本串T
// blen => 文本串T长度
// ptrn => 模式串P
// PLen => 模式串P长度
// skip => 坏字符表
// shift => 好后缀表
// 返回：
// int - 1表示成功（文本串包含模式串），0表示失败（文本串不包含模式串）。
int BMSearch(char *buf, int blen, char *ptrn, int plen, int *skip, int *shift)
{
int b_idx = plen;
if (plen == 0)
return 1;
while (b_idx <= blen)//计算字符串是否匹配到了尽头
{
int p_idx = plen, skip_stride, shift_stride;
while (buf[--b_idx] == ptrn[--p_idx])//开始匹配
{
if (b_idx < 0)
return 0;
if (p_idx == 0)
{
return 1;
}
}
skip_stride = skip[(unsigned char)buf[b_idx]];//根据坏字符规则计算跳跃的距离
shift_stride = shift[p_idx];//根据好后缀规则计算跳跃的距离
b_idx += (skip_stride > shift_stride) ? skip_stride : shift_stride;//取大者
}
return 0;
}

❼ bm算法考研考不考

bm算法考研考不考？考，北京航空航天大学人工智能研究院考人工智能基础综合试题含信号与系统、算法设计与分析和机器学习三门课程的内容。

❽ 关于RS码的英文论文，急啊

摘要：提出了基于欧氏算法和频谱分析相结合的RS码硬件编译码方法；利用FPGA芯片实现了GF（2 8）上最高速率为50Mbps、最大延时为640ns的流式译码方案，满足了高速率的RS编译码需求。
关键词：RS码 FPGA 伴随式 关键方程 IDFT

差错控制编码技术对改善误码率、提高通信的可靠性具重要作用。RS码既可以纠正随机错误，又可以纠正突发错误，具有很强的纠错能力，在通信系统中应用广泛。由于RS码的译码复杂度高，数字运算量大，常见的硬件及软件译码方案大多不能满足高速率的传输需求，一般适用于10Mbps以下。本文提出的欧氏算法和频谱结构分析相结合的RS硬件解码方案，适用于FPGA单片实现，速率高、延迟小、通用性强、使用灵活。笔者在FPGA芯片上实现了GF（2 8）上符号速率为50Mbps的流式解码方案，最大延时为640ns，参数可以根据需要灵活设置。

1 RS码的结构

码字长度为N=q-1(q=2i)，生成多项式为，αi∈GF(q)的RS码有最小码距δ=2t+1，能够纠正t个随机或突发错误[1]。本文列举的方案测试中采用的RS码主要参数为N=255、m0=0、t=8，其中GF（2 8）的生成多项式为g（x）=x8+x4+x3+x2+1。由于RS码的编码逻辑结构比较简单，文中仅给出仿真结果。

2 RS码的译码算法

RS译码算法一般分为三步：伴随式计算、关键方程获得和错误图样的求解。其中关键方程的获得是RS译码中最困难、最为关键的一步。

在利用伴随式求解关键方程时，BM算法和Euclidean（欧氏）算法是两种较好的选择。BM算法涉及大量的变量存储和复杂的逻辑控制，适用于软件编程而不适合硬件实现。欧氏算法数据存储量少、控制便捷，适合硬件实现。且采用欧氏算法确定关键方程所需时间与错误个数成正比，因此从处理时间上考虑，欧氏算法也是较好的选择。

在获得关键方程后，采用时域处理方法，需要大量的运算单元和控制电路，在硬件实现中是不可取的。而采用频谱结构分析方法，利用最短线性移位寄存器综合及离散傅氏逆变换进行处理，逻辑简单、耗时少，适合硬件实现。虽然在傅氏变换时需要较多的逻辑单元，但对GF（2n）在n<10的情况下，变换域译码器要比时域译码器简单得多。因而本文提出欧氏算法和频谱结构分析相结合的方案，并在实践中获得了较好的效果。

Euclidean算法[3]步骤如下：

（2）按所列方法进行迭代

3 方案流程

方案流程框图如图1所示。

3.1 伴随式S0,S1,…，S2t-1的计算

令r1,r2，…，rn为接收到的RS码字，根据系统码监督矩阵的特性，可构造如图2所示伴随式计算电路Si=（（（r1αi+r2）αi+r3）αi…+rn，从而实际伴随式序列的计算。

3.2 利用伴随式确定关键方式

Euclidean算法的难点主工在于迭代计算过程中存在的被除数多项式和除数多项式长度的不确定性，使每次计算中产生的商序列的长度不等，以及因此可能涉及到的不定长多项式的相乘和相加问题，增加了硬件设计的难度。系统采用了嵌套双循环的方法，利用'时钟产生2'控制外循，'时钟产生1'控制内循环，从而优化了算法，得到了问题的解决方案。在获得伴随式的基础上，图3电路可具体完成Euclidean算法对关键方程的求解σ（x）=σtxt+σt-1xt-1+…+σ1x+1。

3.3 利用最短线性移位寄存器综合和离散傅氏变换获取错误图样

在得到关键方程后，首先应进行错误位置（关键方程的根）的确定，这样可减小电路的规模；利用钱搜索[1]（工程上求解σ（x）根的实用方法）的方法可以简捷的确定错误位置。然后，启动最短线性移位寄存器综合和离散傅氏逆变换，经过N次（运算所在域的长度）迭代，即可求得对应各个错误位置的错误图样，如图4所示。用错误图样对接收码字进行纠错，就可得到正确的信息序列。

3.4 RS编译码在FPGA上的实现

有限域的乘法、加法运算单元和各模块的控制逻辑设计是系统成功的关键。涉及有限域的各个运算单元的运算速度制约了译码器的速度，而控制逻辑引导了译码的流程。硬件电路的软件开发工具给设计复杂电路提供了简捷思路。系统采用了QUARTUS与第三方软件相结合的方法，用VHDL语言设计了大部分功能模块。特别是在乘法器设计中，乘数确定、被乘数不定的有限域乘法器，经逻辑综合和优化设计后，运算速度可分别在6.8ns和11.6ns内完成，完全可以满足系统符号速率50Mbps的要求。应该指出，系统速度的进一步提高受到求逆运算的限制，求逆运算没有明确的数学结构（通常采用查表的方法），这是制约运算速度的瓶颈。但针对流式译码算法，上述结构已能满足要求。

4 仿真结果

4.1 编码器的仿真

仿真的时钟频率为50MHz，在EN为高电平时输入信息有效。为简单起见，采用系统码的缩短型，即信息为（00，00，…，00，02，01，02）.编码器的仿真结果如图5所示。其中，IN为输入信息，CLK为系统时钟，C为编码输出（输入和输出均为16进制）。

4.2 译码器的仿真

首先，给出系统的仿真全貌，如图6所示。其中C为接收到的RS码，SP为伴随式S15,shang为运用欧氏算法得到的商序列，SeryDA为S序列，anssd和ERTD分别对应码字可能存在的第四个错误位置和错误值，仿真中的接收码在位置（105，106，107，108，109，110，111，112）上错误均为（01）HEX。

伴随式的计算结果：S15，S14，…，S1，S0为（FD，8D），CE，4A，51，B2，A1，CA，C4，0D，73，56，A6，F5，01），图6和图7中的sp即为S15。

这里重点给出利用伴随式计算关键方程的电路仿真结果，如图7所示。当输入伴随式结果以后，运算电路启动，在计算商序列的同时进行联接多项式的迭代运算。欧氏算法的商序列shang为：（FF，58），（37，92），（50，45），（E9，C7），（F4，B9），（5D，33），（87，8F）。当满足终止条件以后显示标志QQC，同时，给出关键方程系数如图7中（AI，AH，AG，AF，AE，AD，AC，AB，AA）即（00，19，2E，EC，A8，AD，41，E6，95），对应有限域上的表达式为：

δ（x）=α193x7+α130x6+α122x5+α144x4+α252x3+α191x2+α160x+α184;有解为（α105，α106，α107，α108，α109，α110，α111），与假定错误位置完全一致。然后求解S序列，同时针对各错误位置进行IDFT，就可以得到对应的错误值。图6中anssd和ERTD表示位置108上存在的错误为（01）HEX。

图5 编码器仿真结果

系统仿真表明，译码器获得的错误位置和错误图案与实际假设的错误位置（105，106，107，108，109，110，111）和错误值（01）HEX完全一致。

基于APEX架构的可编程单芯片RS编译码硬件解决方案在中国普天集团西安蓝牙通讯设备有限公司的二次群无线扩频通信机的改造项目中得到了应用。它可用于离散译码、流式译码，在添加一级缓存的基础上，同样适用于连续译码。

Abstract : Euclidean algorithm based on the combination of spectral analysis and RS hardware encryption; FPGA chip by GF (2 8), maximum rate of 50Mbps. 640ns delay the flow of the biggest decoding program to meet the demand for high-speed RS encryption. Keywords : RS-key equations with FPGA technology to improve IDFT error control coding error rate. improve communications with the reliability of an important role. RS random error correcting codes can also be corrected burst error correction capability is strong, widely used in communication systems. As RS decoder complexity, the number of large amount of computation. Most common hardware and software decoding program can not meet demand for high-speed transmission. Following are generally applicable to 10 Mbps. Euclidean algorithm and the proposed combination of spectral analysis RS hardware decoding program FPGA chip to achieve that rate, small delay, a strong and flexible. I realized in FPGA GF (2 8) symbols, the flow rate of 50Mbps decoding program maximum delay of 640ns, parameters can be set up based on the need for flexibility. 1 RS code word length of the structure N=q-1 (q=2i) for generating polynomial. α i ∈ GF (q) from the RS code with the smallest δ =2t+1. t random or unexpected error correction [1]. This paper listed in the test parameters for the RS code N=255, m0=0, pH7.5. which GF (2 8) for generating polynomial g (x) =x8+x4+x3+x2+1. As RS encoder logic structure is relatively simple, text only give the simulation results. 2 RS RS code decoding algorithm generally consists of three steps : With computers, The key equation solving and design errors. RS decoding is the key equation is the most difficult and most crucial step. With the use of key-solving equations, BM algorithm and Euclidean (Euclidean) algorithm is two better choices. BM algorithm involves a large number of variables to store and complex control logic applies to software programming without appropriate hardware. Euclidean algorithm for data storage less control convenient and suitable hardware. Also use the Euclidean algorithm to determine the key equation is proportional to the number of errors and the time required, from time to consider. Euclidean algorithm is a good choice. Access to the key equation, using time-domain approach requires a large amount of computational moles and control circuit the hardware is not desirable. Using spectrum analysis method, the shortest inverse linear shift register integrated and discrete Fourier transform, simple logic and less time suitable hardware. While the Fourier transform need more logic unit, but GF (2n) n <10 in the circumstances, Domain encoder decoder is much simpler than the time domain. Euclidean algorithm, and therefore this paper combine spectrum analysis program, and to gain better results in practice. Euclidean algorithm [3] The following steps : (2) 3 iterative methods listed in the program flow program flow chart shown in Figure 1. With 3.1 - S0, S1,…, S2t-1 calculated so r1, r2,…, rnΔyn to receive the RS code word, Under supervision of the character matrix code system. Construction can be calculated as shown in figure 2 with Si= circuit (((r1 - i+r2) - i+r3) - i… +rn. With so that the actual sequence of calculations. With 32,000 officially confirmed the key ways to use the Euclidean algorithm for the main difficulty lies in the iterative process of calculation and arithmetic polynomial length polynomial dividend, the uncertainty Thus, each calculation of the length of the serial range and thus may be involved in the multiplication of polynomials and the sum of variable length. increase the difficulty of hardware design. Two of the nesting cycle system using the method of 'Clock 2' control through. 'Clock 1' inner loop control, optimize the algorithm, a solution to the problem. The ceremony was accompanied by the foundation, Figure 3 circuit can be completed Euclidean algorithm specific key equations of σ (x) = σ txt+ σ t-1xt-1+… + σ 1x+1. 330 linear shift register using the shortest access to integrated and discrete Fourier transform has been key in the wrong design equation, First, should the wrong location (the root of the key equation) determined that this will rece the size of circuits; use the money to search [1] (works for σ (x) root practical method), a simple method to determine the wrong location. Then, shortest start inverse linear shift register integrated and discrete Fourier transform, through N (computational domain where the length) iteration. be all wrong location corresponding to the wrong design, as shown in figure 4. Drawing on the takeover code used for correcting mistakes. can get the correct message sequence. RS 3.4 encryption in the FPGA to achieve limited domain multiplication, Adder moles and the molar design of the control logic systems is the key to success. Operation of the various moles involved in the limited domain of the decoder speed computational speed constraints, and control logic guiding the decoding process. Hardware complexity of circuit design software development tools to provide a simple idea. QUARTUS system with a combination of third-party software. VHDL design of most functional moles. especially in the multiplier, multiplier determined. multiplicand volatile finite field multiplier, logic synthesis and optimization design, 11.6ns 6.8ns and the computational speed can be completed. Symbol rate of 50Mbps system can meet the requirements. It should be noted that further improve the system by inverse calculation speed restrictions no clear inverse calculation of the mathematical structure (look-up table method is usually used). This is a bottleneck restricting the operation speed. However, in view of flow algorithm. the structure can meet the above requirements. 4 simulation results of the simulation 4.1 encoder clock frequency of 50MHz. EN input to the generator when the information effectively. for the sake of simplicity, the use of the shortened code systems, information (00, 00…, 00,02,01,02). The simulation results shown in Figure 5 encoder. Among them, IN to input information, for the system clock CLK, C coding output (both input and output, 16-ary). Simulation 4.2 Decoder First, The simulation gives the whole picture, as illustrated in figure 6. C for receipt of the RS code, as with SP-S15. shang Euclidean algorithm for the use of the serial, SeryDA S Series, anssd ERTD corresponding code and the fourth may be wrong position and erroneous values Simulation code in the receiving position (105,106,107,108,109,110,111. 112) were wrong (01) HEX. With results like : S15, S14,…, S1. S0 (FD,8D) CE,4A,51, B2, A1, CA, C4,0D,73,56, A6, F5,01) Figure 6 and Figure 7 sp namely the S15. With the focus here is calculated by using the key to the equation circuit simulation results shown in figure 7. When the input syndrome result, the circuit operation in the calculation of serial link at the same time polynomial iteration. Euclidean algorithm serial shang : (FF,58), (37,92), (50,45). (E9, C7), (F4, B9), (5D,33), (87,8F). When shown signs QQC meet after the termination conditions, while the key equation coefficients is given in Figure 7 (AI AH AG. AF, AE, AD, AC, AB, AA) : (00,19,2E, EC, A8, AD,41, E6,95) limited domain corresponding to the formula : δ (x) = α - 122x5+ 130x6+ 193x7+ α - α 191x2+ 252x3+ 144x4+ α - α 184; 160x+ Solution (α 105, - 106, - 107, - 108, - 109, - 110, - 111). exactly the same position with the wrong assumptions. And then the S Series, IDFT against the wrong location, it could be the wrong response value. 6 anssd ERTD plan and said there is the wrong position for the 108 (01) HEX. Figure 5 encoder System Simulation results show that Decoder the wrong place and wrong patterns and the actual position of the erroneous assumption (105,106,107. 108,109,110,111) and the wrong values (01) HEX totally consistent. RS APEX structure based on a programmable chip encryption hardware solutions in China Putian Group Limited, the second group Xi'an Bluetooth wireless communication equipment spread spectrum communication mechanism has been applied to the reconstruction project. It can be used for discrete decoding, streaming decoding, in addition to the basic level cache, the same applies to successive decoding.