伯利坎普-韦尔奇算法(英语:Berlekamp-Welch algorithm)是一种用于高效地解码BCH码与里德-所罗门码的算法,其名取自埃尔温·伯利坎普与劳埃德·韦尔奇。伯利坎普-韦尔奇算法的优点在于这一算法仅需利用矩阵运算。这一算法的时间复杂度为
。
伯利坎普-韦尔奇算法通常被用于解码里德-所罗门码。假使在有限体
上有
个数字
,利用RS码编为
次多项式
。如果已知传输信道会错误传输
个值,那么RS码可以传输
上的
个点
。因此,解码者的问题在于要辨认出哪
个点是错误的。令解码者接收到的点值为
,可以看出对于且仅对于所有正确传输的点
,
。
伯利坎普-韦尔奇算法引入了错误辨认多项式的概念,也即多项式
,其中
的值为所有
个错误传输的点的
值(均未知)。由于
当且仅当
对应一个错误传输的点,可以看出对于所有
值,
,其中
对于所有i均为已知常量。令
,可以看出左侧为一个
次的多项式,右侧为一个
次的多项式,但其最高次系数为1。因此,整个线性系统有
个方程式与
个未知数,可以用线性代数的方法解出,并可以由
解出原始的编码多项式并读出编码值
。