On the key equation
On the key equation
复制标题
DOI：
10.1109/18.412677
复制
发表时间：
1995-09
期刊：
影响因子：
--
通讯作者：
P. Fitzpatrick
中科院分区：
文献类型：
--
作者：
P. Fitzpatrick
我们考虑交替码的关键方程的所有解的集合M={（a，B）：a ∈ bh mod x2 t}，其中h是伴随式多项式.在对这些码译码时，需要寻找一个特殊的解（ω，σ）∈M，条件是ω和σ互素且满足一定的度条件。我们证明了这些条件唯一地指定（ω，σ）为M的极小元（类似于生成F[x]的理想的极小次一元多项式），并且（ω，σ）可以由M的适当的Grobner基确定.出于这一点和其他变化的关键方程（如适当的错误和擦除解码），我们推导出一个通用的算法，用于解决的同余a bg mod xn的范围内的长期订单所定义的条件所需的特定解决方案。我们的技术提供了一个统一的方法来解决这些关键方程
We consider the set M={(a, b):a≡bh mod x2t} of all solutions of the key equation for alternant codes, where h is the syndrome polynomial. In decoding these codes a particular solution (ω, σ)∈M is sought, subject to ω and σ being relatively prime and satisfying certain degree conditions. We prove that these requirements specify (ω, σ) uniquely as the minimal element of M (analogous to the monic polynomial of minimal degree generating an ideal of F[x]) with respect to a certain term order and that, as such, (ω, σ) may be determined from an appropriate Grobner basis of M. Motivated by this and other variations of the key equation (such as that appropriate to errors-and-erasures decoding) we derive a general algorithm for solving the congruence a≡bg mod xn for a range of term orders defined by the conditions on the particular solution required. Our techniques provide a unified approach to the solution of these key equations