JPH0137050B2 - - Google Patents

Description

【発明の詳細な説明】 産業上の利用分野 本発明はデジタル通信やデジタル記録等で採用
される有限体GF（2ⁿ）上の誤り訂正符号の符号処
理に必要な乗算を行うのに用いることができる
MOD（2ⁿ−１）（ｎは２以上の整数）の加算回路
に関するものである。

従来例の構成とその問題点 近年、デジタル通信やデジタル記録等で有限体
GF（2ⁿ）上の誤り訂正符号が広く用いられてお
り、その誤り訂正符号の訂正や検出などの符号処
理を行うにはGF（2ⁿ）上の乗算が必要である。

GF（2ⁿ）上の乗算の１つの手法として、乗数、
被乗数をaⁱ、a^j（ａ：GF（2ⁿ）上の生成元、ｉ、ｊ
は０以上2ⁿ−１未満の整数）としたときに、まず
ｉ、ｊを求めて、ｋ≡ｉ＋ｊ（MOD（2ⁿ−１））、
０≦ｋ＜2ⁿ−１により、乗算結果aⁱ×a^j＝a^kを求
める方法がある。その際、aⁱ、a^jからｉ、ｊを求
めるには、aⁱのベクタ表現をアドレス入力とし、
ｉをデータ出力とするテーブルROMを用いれば
よいし、ｋからa^kを求めるには、ｋをアドレス入
力とし、a^kのベクタ表現をデータ出力とするよう
なテーブルROMを用いればよい。従つて残る問
題は、MOD（2ⁿ−１）の加算回路をいかに構成す
るかということである。

以下図面を参照しながら従来のMOD（2ⁿ−１）
の加算回路について説明する。第１図は従来の
MOD（2ⁿ−１）の加算回路のブロツク図であり、
１０はキヤリ入力端子のないｎビツトのバイナリ
加算回路（Ａとする）であり、２０はキヤリ入力
端子のあるｎビツトのバイナリ加算器（Ｂとす
る）である。Ａのキヤリ出力ＣはＢのキヤリ入力
端子に入力され、加算数Ｘ＝x₀、x₁、……、
x_o-1）（以下、Ｖ＝（v₀、v₁、……、v_o-1）と書く
と、数Ｖをバイナリ表現したときの名けたを下け
たから書いたときにv₀、v₁、……V_o-1となるもの
とする。）と被加算数Ｙ＝（y₀、y₁、……、y_o-1）
とがＡに入力され、Ａの加算出力がＢに加算数と
して入力され、Ｂの被加算数としては（０、０、
……、０）（すなわちｎビツト分の０）が入力さ
れているように構成している。

以上のように構成されたMOD（2ⁿ−１）の加算
回路についてその動作を以下に説明する。前記の
MOD（2ⁿ−１）の加算回路の出力Ｚ＝（z₀、z₁、
……、z_o-1）はその構成から考えて、Ｚ≡Ｘ＋Ｙ
＋Ｃ（MOD2ⁿ）（一般にＵ≡Ｖ＋Ｗ（MOD（Ｍ））
と書くとＶとＷとをMOD（Ｍ）で加算した結果
がＵになるということを意味する。）となる。Ｓ
≡Ｘ＋Ｙ（MOD（2ⁿ−１）、０≦Ｓ＜2ⁿ−１とする
と、2ⁿ−１＞Ｘ＋Ｙ≧０のときにはＣ＝０となる
からＺ＝Ｓ＝Ｘ＋Ｙとなり、Ｘ＋Ｙ≧2ⁿのときに
はＣ＝１となるからＺ＝Ｓ＝（Ｘ＋Ｙ＋１）−2ⁿ＝
Ｘ＋Ｙ−（2ⁿ−１）となる。従つてＸ＋Ｙ＝2ⁿ−
１以外のときには、この加算回路の出力Ｚが加算
数、被加算数Ｘ、ＹのMOD（2ⁿ−１）の加算結果
となる。

しかしながら、上記のような構成においては、
キヤリの伝搬が２つの加算器にまたがつているの
で演算速度が遅いという問題点を有していた。

発明の目的 本発明の目的は、高速なMOD（2ⁿ−１）の加算
回路を提供することである。

発明の構成 本発明のMOD（2ⁿ−１）の加算回路は、キヤリ
入力端子を有しないかまたは“０”をキヤリ入力
とするｎ（ｎ：正の整数）ビツトのバイナリ加算
器（第１の加算器）と、“１”をキヤリ入力とす
るｎビツトのバイナリ加算器（第２の加算器）
と、セレクタによつて構成され、前記セレクタに
より、第２の加算器のキヤリ出力が“０”のとき
には第１の加算器の加算結果を選択し、第２の加
算器のキヤリ出力が“１”のときには第２の加算
器の加算結果を選択するように構成したものであ
り、これにより高速にMOD（2ⁿ−１）の加算がで
きるものである。

実施例の説明 以下本発明の一実施例について図面を参照しな
がら説明する。

第２図は本発明の一実施例におけるMOD（2ⁿ−
１）の加算回路のブロツク図を示すものである。
第２図において、１はキヤリ入力として“１”が
入力されているｎビツトのバイナリ加算器（Ｅと
する）、２はキヤリ入力端子のないｎビツトのバ
イナリ加算器（Ｆとする）、３はセレクタである。
ＥとＦの両方に加算数Ｘ＝（x₀、x₁、……、x_o-1）
と被加算数Ｙ＝（y₀、y₁、……、y_o-1）とを入力
し、それぞれの加算出力、Σ＝（Σ₀、Σ₁、……、
Σ_o-1）とΣ′＝（Σ₀、Σ₁、……、Σ′_o-1）を前記セ
レ
クタに入力し、セレクタの出力Ｚ＝（z₀、z₁、…
…z_o-1）は、Ｅのキヤリ出力ＣがＣ＝０のときに
は、Ｚ＝Σ′となり、Ｃ＝１のときには、Ｚ＝Σと
なるように構成している。

以上のように構成された本実施例のMOD（2ⁿ−
１）の加算回路についてその動作を説明する。Ｅ
はΣ≡Ｘ＋Ｙ＋１（MOD2ⁿ）を出力し、ＦはΣ′≡
Ｘ＋Ｙ（MOD2ⁿ）を出力するが、Ｓ≡Ｘ＋Ｙ
（MOD（2ⁿ−１））、０≦Ｓ≦2ⁿ−１とΣ、Σ′とを
比較すると、Ｘ＋Ｙ≧2ⁿ−１のときにはＳ＝Σと
なり、2ⁿ−１＞Ｘ＋Ｙ≧０のときには、Ｓ＝Σ′と
なる。しかるにＸ＋Ｙ≧2ⁿ−１のときにはＣ＝１
になり、2ⁿ−１＞Ｘ＋Ｙ≧０のときにはＣ＝０に
なるので、上記のように構成することにより、こ
のMOD（2ⁿ−１）の加算回路の出力Ｚは、Ｚ＝Ｓ
となる。

以上のように本実施例によれば、使用する２つ
の加算器間のキヤリ伝搬をなくしたことにより、
MOD（2ⁿ−１）の加算の演算時間を短縮してい
る。なお、上の実施例ではＦの加算器をキヤリ入
力端子が存在しないとしたが、Ｆはキヤリ入力端
子を持つていてもよく、ただそのときにはキヤリ
入力は“０”でなければならない。またこの
MOD（2ⁿ−１）の加算器の入力である加算数Ｘ
か、被加算数Ｙのどちらか一方の各ビツトをすべ
て反転することにより、MOD（2ⁿ−１）の減算回
路を構成することができる。

発明の効果 以上の説明から明らかなように、本発明は使用
する２つのｎビツトのバイナリ加算器同志のキヤ
リ伝搬をなくしたことにより、演算速度が従来の
ものよりも２倍近く向上するという優れた効果が
得られる。さらに加算数か被加算数のどちらか一
方の各ビツトをすべて反転して、本発明の加算回
路に入力することにより、MOD（2ⁿ−１）の減算
回路が容易に構成できる。

【図面の簡単な説明】

第１図は従来のMOD（2ⁿ−１）の加算回路のブ
ロツク図、第２図は本発明の一実施例における
MOD（2ⁿ−１）の加算回路のブロツク図である。 １，２，１０，２０……ｎビツトバイナリ加算
器、３……セレクタ。

Claims (1)

【特許請求の範囲】
1. １ キヤリ入力端子を有しないかまたは“０”を
   キヤリ入力とするｎ（ｎ：２以上の整数）ビツト
   のバイナリの第１の加算器と、“１”をキヤリ入
   力とするｎビツトのバイナリの第２の加算器と、
   セレクタとによつて構成され、前記セレクタは前
   記第２の加算器のキヤリ出力が“０”のときには
   前記第１の加算器の加算結果を選択し、前記第２
   の加算器のキヤリ出力が“１”のときには前記第
   ２の加算器の加算結果を選択するように結線する
   とともに、第１の加算器の２つの入力端子を２つ
   の入力端子とし、前記セレクタの出力端子を出力
   端子とすることを特徴とするMOD（2ⁿ−１）の加
   算回路。