ホーナー法
ホーナー法（ほーなーほう、英: Horner's rule）とは、最も少ない加算と乗算の演算回数でn次の多項式の評価を行うことができるアルゴリズムを言う。
ホーナー法がシンドローム計算で用いられる。シンドローム計算では受信語$${R(x)}$$について$${\alpha^j}$$を代入した値を評価するためである。
すなわち、$${R(x) = \sum_{i=0}^{n-1}R_{i}x^i}$$とすると、$${S_i = R(\alpha^i)}$$は
$$
S_i = ( \cdots (R_{n-1}\alpha^i + R_{n-2})\alpha^i + \cdots + R_1)\alpha^i + R_0
$$
これを回路実装すると
のようになる。inputには各サイクルごとに$${R_{n-1}}$$から$${R_{0}}$$まで順に入力される。サイクルでは、レジスタの値と$${R_{?}}$$が加算されたものが、さらに$${\alpha^i}$$かけられてレジスタに格納される。(図は少しおかしく、$${R_0}$$にも$${\alpha^i}$$かける回路になってしまってるので、正しくは$${S_i}$$はガロア体加算器の後の値を取得する)。
本回路を$${S_i, i=0,\cdots,2t}$$すべてで共有する場合、すべてのシンドロームを求めるのに必要なサイクル数は「入力シンボル数$${\times}$$2t」サイクルとなる。シンドローム別に回路を用意すれば2t個本回路が必要であるが、必要なサイクル数は「入力シンボル数」となり、ガロア体乗算器は片側定数となるので簡略化される。
乗算器の簡略化については