JPH0445016B2 - - Google Patents
Info
- Publication number
- JPH0445016B2 JPH0445016B2 JP62182446A JP18244687A JPH0445016B2 JP H0445016 B2 JPH0445016 B2 JP H0445016B2 JP 62182446 A JP62182446 A JP 62182446A JP 18244687 A JP18244687 A JP 18244687A JP H0445016 B2 JPH0445016 B2 JP H0445016B2
- Authority
- JP
- Japan
- Prior art keywords
- stage
- mrc
- remainder
- input
- rom
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Classifications
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
- H03M7/14—Conversion to or from non-weighted codes
- H03M7/18—Conversion to or from residue codes
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F11/00—Error detection; Error correction; Monitoring
- G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
- G06F11/16—Error detection or correction of the data by redundancy in hardware
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
- G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
- G06F7/729—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic using representation by a residue number system
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Physics & Mathematics (AREA)
- Mathematical Optimization (AREA)
- General Engineering & Computer Science (AREA)
- Computational Mathematics (AREA)
- Mathematical Analysis (AREA)
- Pure & Applied Mathematics (AREA)
- Quality & Reliability (AREA)
- Computing Systems (AREA)
- Mathematical Physics (AREA)
- Detection And Correction Of Errors (AREA)
- Error Detection And Correction (AREA)
- Advance Control (AREA)
- Read Only Memory (AREA)
- Complex Calculations (AREA)
Description
Ａ 産業上の利用分野
本発明は剰余数体系のデータから混合基数射影
データを得るための装置、より具体的には、誤り
検出及び訂正を行なう混合基数変換装置に関す
る。 Ｂ 従来技術 デイジタル信号処理（DPS）に対する剰余算
術（residue arithmetic）の応用に、最近、興味
が新たになつている。剰余数体系（residue
number system）（RNS）の内部でDSPの関数
を計算する事によつて、下記の利点が実現され
る。 １ 高いサンプリング周波数 ２ モジユール的インプリメンテーシヨン ３ フオールト・トレランス 剰余算術を用いたいかなるDSPのインピリメ
ンテーシヨンも、上記３つの利点を保持しなが
ら、その出力をRNSから重み付け数体系
（weighted number system）（WNS）へ翻訳す
る必要がある。 例えば、Ｔ秒のサイクル・タイムを有する多段
パイプライン式システムを考える。各Ｔ秒毎に、
新しい入力がシステムの各段に受け入れられる。
第１段への入力はシステムの入力である。各Ｔ秒
毎に、新しい出力が各段によつて形成される。最
終段の出力はシステムの出力である。ある段の出
力はその後続段への入力である。また各段自体が
複数段から成つていてもよい。 第２図は計算処理を行なうために使用し得る多
段パイプライン式システムを示す。このシステム
は、下記に概観するように、速いサイクル・タイ
ム、モジユール式インプリメンテーシヨン、及び
フオールト・トレランスという利点を達成するた
めに冗長剰余数体系算術の技術を利用する。 このシステムの入力は、ある重み付け数体系
（WNS）内で表現された１つ以上の整数である。
第１段10は入力の整数の剰余数体系（RNS）表
現を導き出し、必要な計算をこのRNS内で行な
い、そして所望の出力をRNS形式で形成する。
第１段の出力12はＮ個の剰余数の組ｋ(1)〜ｋ（Ｎ）
である。但しＮはRNSが定義されているモジユ
ラスの数である。ｋ（Ｎ）は上位の剰余数であり、
ｋ(1)は下位の剰余数である。RNSは、出力剰余
数に対して単一誤り訂正を行なう事を可能にする
ために少なくとも２つの冗長な上位のモジユラス
を含んでいる。 第２段14はＮ組のＮ−１混合基数の数字を形成
する。各組は、kiの１つの寄与を無視しながら残
りのＮ−１の剰余数に対して混合基数変換
（MRC）を行なう事によつて形成される。この
MRCにより得られたＮ−１混合基数数字はｉ番
目の射影（projection）と呼ばれる。ｋ(i)のいず
れも誤りがなければ、各々の射影は、所望のシス
テム出力の異なつたWNS表現である。誤つた剰
余数ｋ(i)が存在する時は、射影のうちただ１つだ
けが所望のシステム出力の正しいWNS表現であ
る。それはkiの寄与を無視する事によつて形成さ
れた射影である。本発明はこの第２段に係るもの
である。 第３段18は、第２段14の出力16を使用して、可
能であれば正しい出力を決定し、有用な誤り情報
を提供する。また第３段は、システム出力をより
便利なWNS表現に変換してもよい。 そのようなシステムの具体的な計算に焦点を当
てて、下記のＮ個の互いに素な整数の組に基く
RNSを考える。 ｛ｍ(1)，ｍ(2)，……，ｍ（Ｎ）｝ これらはRNSのモジユラスと呼ばれる。自然
数ｋのRNS表現は次のように書かれる。 〔ｋ(1)，ｋ(2)，……，ｋ（Ｎ）〕 ここで、ｋ(i)は剰余数と呼ばれ、ｋ
modulom(i)を表わす。 MRCはRNSからWNSへ翻訳するための有用
な技術である。整数ｋは、重み付け混合基数数字
の列によつて表現し得る。 (1)
ｋ＝N 〓i=1 ｄ(i)×ｗ(i) ここで、 (2)
Ｗ(i)＝i-1 〓j=1 ｍ(j) は、重み（ｗ(1)＝１）であり、ｄ(i)は混合基数数
字の桁である。 次に、特許請求の範囲を含む明細書中で用いら
れている主な用語、例えば、ROM、ラツチ、
MRC構造などは、剰余数体系算術の技術分野で
慣用されているものであり、以下にその意義を略
述する。 ROMij： アレイ位置（ｉ，ｊ）に配置され、時刻Ｏに入
力して２つの整数ｐ及びｑを受理し、時刻Ｔに下
記の方程式(3)を満足する整数ｒに相当する信号を
出力する機能を有する読取専用メモリを含む任意
の回路又はプログラム。ROMijの左側入力がｐ入
力であり、他方、右側入力がｑ入力である。 式(3)： ｒ＝｛（ｐ−ｑ）×ｍ(j)-1｝modulo ｍ(i) 但し、ｍ(j)-1は次式を満足するような整数。 ｛ｍ(j)-1×ｍ(j)｝modulo ｍ(i)＝１ ラツチ： 時刻Ｏに入力された整数に相当する信号を保持
し、時刻Ｔに出力する機能を有する任意の回路又
はプログラム。 MRC回路： ROMij及びラツチは、MRCを遂行するための
多段パイプライン構造を形成するようＮ列×（Ｎ
−１）段のアレイ（サイズＮのMRC構造の場合）
に配列され、所定ルールに従つて相互接続され
る。ｉ＞ｊのアレイ位置にはROMijを配置し、そ
れ以外の位置にはラツチを配置する。アレイ第１
段（最上段）に配列されたROMi1（ｉ＝２〜Ｎ）
のｐ入力には剰余数Ki（ｉ＝２〜Ｎ）が、そして
ｑ入力には剰余数K1が印加される。第１段のラ
ツチには剰余数K1が印加される。前段のROMij
の出力ｒが自段のROMijのｐ入力又はラツチ入力
となり、前段のラツチ入力が並列にROMijのｑ入
力になる。最下段のROMij及びラツチの出力が混
合基数数字を表わす。上記アレイ構造をサイズＮ
のMRC構造と呼ばれている。 第６図にはサイズＤのMRC構造が示されてい
る。第１段のパイプライン段のラツチには剰余数
I1が入力され、ROMi1（ｉ＝２，３……Ｄ）のｐ
入力には剰余数I2〜IDが入力される一方、その
ｑ入力には剰余数I1が入力されている。図中、ｉ
＞ｊならば、ROMijが、そしてそれ以外のときは
ラツチがアレイ位置に配置されている。最終段Ｄ
−１段の出力O1〜ODがサイズＤのMRC構造の
出力、即ち混合基数数字である。 第３図は、Ｎ＝４の場合のMRC構造において
剰余数Ｋ(i)から混合基数数字ｄ(i)を計算する従来
技術を示している。第４図は、第３番目の混合基
数射影（即ち、剰余数Ｋ(3)を除いた残りの剰余数
Ｋ(1)，Ｋ(2)及びＫ(4)について混合基数数字ｄ(i)を
計算するためのMRC構造）が示されている。図
示していないが、同様なMRC構造が第１番目、
第２番目及び第４番目の混合基数射影の計算のた
めに必要であり、全部で12個のROM及び12個の
ラツチが必要である。 MRC構造はRNSからWNSへの翻訳を行なう
だけではなく、誤りの検出及び訂正を行ない、な
お且つ高いサンプリング周波数の利点及びフオー
ルト・トレランス、モジユラー性というRNSの
利点を保持する。以前のように、Ｎ個のモジユラ
ス（但しその少なくとも２つは冗長である）を有
するRNSを用いると、剰余数の任意の１つにお
ける誤りを分離し、訂正する事ができる。これは
剰余数の各組からＮ個の混合基数射影を生成する
ようにMRC構造を有する事によつて達成される。
ｉ番目の混合基数射影は、Ｎ−１個の剰余数の組
からＮ−１個の混合基数数字を計算する事によつ
て得られる。ここでｉ番目の剰余数は計算から除
外される。各射影の最上位の混合基数数字を調べ
れば、誤つた剰余数を識別する事ができる。 Ｃ 発明が解決しようとする問題点 もしパイプライン式システムが各ROMサイク
ル・タイム毎に１つの出力を発生し、且つシステ
ムが平行的な誤り検出を行なうべきであれば、必
要な混合基数射影の全部が各サイクル毎に並列に
計算されなければならない。これはMRC構造を
Ｎ個並列にする事によつて達成可能である。本発
明はこの問題に対する、より経済的な解決を与え
る。 従つて、本発明の目的は、剰余数体系のデータ
から混合基数射影データを計算するための改良さ
れた装置を提供する事である。本発明によれば、
従来技術の装置よりも効率的な構造を用いて、誤
りの検出及び訂正を行なう改良された装置が提供
される。 Ｄ 問題点を解決するための手段 本発明によれば、Ｎ個のモジユラスを有する剰
余数体系で表現された入力データ信号を、出力の
混合基数射影データ信号に変換するための装置が
提供される。サイズＮ−１の通常の混合基数変換
（MRC）構造をＮ個組み合せたものより成る
ROM及びラツチの単一の配列が提供される。た
だし、上記構造の間で重複する信号路、ラツチ及
びROMは併合され、重複が除去されている。従
つて、本発明は、MRC構造が完全に並列化され
た時に存在する冗長な計算を除去している。従つ
て、剰余数体系データを用いて計算を行なう装置
内での誤りの検出及び訂正の問題に対して、より
経済的な解決法が与えられる。 本発明によれば、剰余数K1乃至KNを表わす
入力をＮ−１個のMRC構造（各MRC構造は予め
決められたアレイ位置にROMij及びラツチを有す
る）を用いて混合基数射影データに変換するため
の装置では、 上記MRC構造の各々Ｓ(z)（Ｚ＝１〜Ｎ−１）
は、Ｎ−Ｚ段及びＮ−Ｚ＋１列から成る可変サイ
ズのアレイであり（但し、第1MRC構造Ｓ(1)はＮ
−１段目を欠きＮ−２段目が最終段であり）、各
MRC構造Ｓ(z)において第Ｘ列（最右方が第１列）
及び第Ｙ段（最上段が第１段）の交点位置にはｉ
＝Ｘ＋Ｚ−１及びｊ＝Ｙ＋Ｚ−１により定義され
たROMijが配置されており、上記第1MRC構造Ｓ
(1)の入力は上記剰余数K1〜KNであり、その出
力は上記最終段からのＮ個の混合基数数字Ｓ(1)
［１］乃至Ｓ(1)［Ｎ］であり、 他のすべてのMRC構造Ｓ（ｚ）（Ｚ＝２〜Ｎ−
１）への入力は、第1MRC構造Ｓ(1)におけるＺ−
１段目へのＮ−Ｚ＋１個のｐ側入力であり、それ
らの出力は、夫々、最終段からの混合基数数字Ｓ
(z)［Ｚ］乃至Ｓ(z)［Ｎ］（Ｚ＝２〜Ｎ−１）であ
る事を特徴とする。 Ｅ 実施例 本発明は、MRC構造が完全に並列的に反復し
て設けられた時に存在する冗長な計算を除去す
る。第１図を参照しながら、本発明の実施例（Ｎ
＝４の場合）について説明する。第１図に示すよ
うに、９個だけのROM及び７個だけのラツチを
用いて第２図に示した従来と同様に４個の射影を
生成できる。この実施例は、列数及び段数が順次
に少なくなるＳ(1)，Ｓ(2)，Ｓ(3)と記述した３個の
MRC構造（一般にはＮ−１個のMRC構造）より
構成されている。Ｓ(1)は４列（一般にはＮ−１＋
１）、Ｓ(2)は３列（Ｎ−２＋１）、Ｓ(3)は２列（Ｎ
−３＋１）であり、第６図に関して説明されるよ
うに一般にはＳ(z)の列数は（Ｎ−Ｚ＋１）で表わ
される。段数について云えばＳ(1)は２段、Ｓ(2)は
２段、Ｓ(3)は１段であり、一般にはＮ−Ｚ段で表
わされる。但し、Ｓ(1)は例外的に最下段の１段が
省略される（これは、パイプラインの長さがＮ−
２段であり、従来の反復方式と同じである）。各
段及び各列の交点にROMij又はラツチが設けられ
ている。第６図に関して説明されるように、
MRC構造のＳ(z)において、列Ｘ及び段Ｙの交点
に設けられたROMijの添字ｉ及びｊは次のように
表わされる。 ｉ＝Ｘ＋Ｚ−１ ｊ＝ｙ＋Ｚ−１ 但し、Ｓ(z)内で、最右列が第１列であり最上段
が第１段である。 上式を、第１図のＳ(2)における最上段が（ｙ＝
１）の２列目（ｘ＝２）のROMに適用すると、 ｉ＝Ｘ＋Ｚ−１＝２＋２−１＝３ ｊ＝Ｙ＋Ｚ−１＝１＋２−１＝２ 従つてROMijはROM32として定義される。 同様にＳ(3)における最上段が（ｙ＝１）及び最
左列（ｘ＝２）のROMijは、 ｉ＝２＋３−１＝４ ｊ＝１＋３−１＝３ 即ち、ROM43で表わされる。 第１図のROM、ラツチの出力線の矢印の下方
に、夫々、示された数字１，２，３，４は上記
ROMijの列位置を表わすｉの数字を表わす。 ｉ＞ｊであれば、ROMを、そうでなければ、
ラツチを各交点位置に設ける。第１図のＳ構造出
力の混合基数数字は、従来の反復方式の射影に対
して、下記のように関係している。 第１の射影＝｛Ｓ(2)〔４〕，Ｓ(2)〔３〕，Ｓ(2)
〔２〕｝ 第２の射影＝｛Ｓ(3)〔４〕，Ｓ(3)〔３〕，Ｓ(1)
〔１〕｝ 第３の射影＝｛Ｓ(1)〔４〕，Ｓ(1)〔２〕，Ｓ(1)
〔１〕｝ 第４の射影＝｛Ｓ(1)〔３〕，Ｓ(1)〔２〕，Ｓ(1)
〔１〕｝ ここで(j)，〔ｉ〕は構造Ｓ(j)のｉ番目の出力を
示す。 一般に、単純な反復方式はＡ個のROM及びＡ
個のラツチを使用する。但し、 (4) Ａ＝Ｎ N-2 〓i=1 (i)＝Ｎ（Ｎ−１）（Ｎ−２）／２ 一般に本発明はＢ−１個のROMとＢ−（Ｎ−
１）個のラツチを使用する。但し、 Ｂ＝N-1 〓j=1 j 〓i=1 (i) ＝Ｎ（Ｎ−１）（Ｎ＋１）／６ 本発明により得られる利益の尺度として、与え
られたＮの値に関して必要なROMの数を比較し
てもよい。第５図はｐ対Ｎの曲線20を示す。ｐ＝
100×（１−（Ｂ−１）／Ａ） これはROMの必要な数が減少する百分率であ
る。大きなＮの場合、ｐは漸近的に67％に近付
く。 一般に、良好な実施例はＮ−２段のパイプライ
ンを有する。一般に、各段は２つの型の要素から
構成されている。即ちラツチとROMである。ラ
ツチはサイクルの開始時に入力を捕え、サイクル
の残期間中、その値を出力に保持する。ROMは
サイクルの開始時にその入力ｐ及びｑを捕え、サ
イクルの終了する前に出力ｒを発生する。
ROMijの出力は式(3)により定義される。 良好な実施例は、上述の機能を実現するために
ROMを使用する。しかし、同じ機能を与える回
路素子又はプログラムで置き換える事も可能であ
る。 第１図に描かれた良好な実施例はＮ＝４の場合
のものである。本発明の原理によれば、任意のＮ
の値に拡張する事ができる。一般的な場合（Ｎ）
について、良好な実施例を説明する。 再び、下記のＮ個の互いに素な整数モジユラス
の組を考える。 ｛ｍ（Ｎ），……，ｍ(2)，ｍ(1)｝ ここでｍ（ｉ＋１）＞ｍ(i)ｋは下記のような整数
を表わすものとする。 ｋ＜N-2 〓i=1 ｍ(i) この整数ｋは、RNS方式で、Ｎ個の剰余数に
より表現する事ができる。 ｋ（Ｎ），……，ｋ(2)，ｋ(1) ここで、ｋ(i)は値Ｋ modulo ｍ(i)を表わす。 この場合、整数ｋに関するRNS表現は２個の
冗長な剰余数字を含んでいる。この冗長性によ
り、ｋに関するRNS表現中の１つの誤つた剰余
数を検出し訂正する事ができる。 整数ｋに関するRNS表現中の誤りを検出し訂
正する１つの技術はMRCを利用する。 １組のｋ(i)から、MRCは式(1)及び式(2)に従う
ｄ(i)の組を生成する。誤つた剰余数は次のように
して検出できる。 最初に、整数ｋを表わすＮ個の剰余数の組か
ら、各々の剰余数を１つ除外する事によりＮ−１
個の数の組をＮ個形成する。各組は射影と呼ぶ。
ｋ(i)を除外する事により形成される射影をｐ(i)で
表わすものとする。各ｐ(i)にMRCを適用する。
各ｐ(i)にMRCを適用する。各ｐ(i)に関して、上
位の混合基数数字を調べる。もし全てがゼロの値
を有していれば、どのｋ(i)も誤つていない。もし
ｐ(j)以外の全てが非ゼロであれば、ｋ(j)が誤つて
おり、ｐ(j)がｋに関する正しい表現である。 一般的な場合（Ｎ）に関する良好な実施例は、
（Ｂ−１）個のROMij及び（Ｂ−Ｎ＋１）個のラ
ツチを含むＮ−２段のパイプラインである。但
し、 Ｂ＝Ｎ（Ｎ−１）（Ｎ＋１）／６ 実施例の入力は、Ｎ個の剰余数であり、出力は
（Ｎ＋２）（Ｎ−１）／２個の混合基数数字であ
る。実施例はＮ−１個のMRC構造Ｓ(1)〜Ｓ（Ｎ−
１）より構成される。Ｓ(z)の列ｘ、段ｙを占める
ROMijは次式によつて決定される。 ｉ＝ｘ＋ｚ−１及びｊ＝ｙ＋ｚ−１ Ｓ(1)の入力はｋ(1)〜ｋ（Ｎ）である。 Ｓ(1)は１段が省略されている点で特殊なケース
である。その出力は段Ｎ−２の後で与えられる。
Ｓ(1)の出力はＮ個の混合基数数字Ｓ(1)〔１〕〜Ｓ
(1)〔Ｎ〕である。 Ｓ(z)（Ｚ＝２〜Ｎ−１の場合）の入力はＳ(1)の
Ｚ−１段目へのＮ−Ｚ＋１のｐ側入力と同じであ
る。 Ｓ(z)（Ｚ＝２〜Ｎ−１の場合）の出力は、混合
基数数字Ｓ(z)［Ｚ］〜Ｓ(z)［Ｎ］である。 実施例の出力は、全ての射影の混合基数表現を
与えるのに必要且つ充分である。射影ｐ（Ｎ）の
混合基数数字はＳ(1)〔１〕〜Ｓ(1)〔Ｎ−１〕であ
る。射影ｐ（Ｎ−１）の混合基数数字は、Ｓ(1)
〔１〕〜Ｓ(1)〔Ｎ−２〕及びＳ(1)〔Ｎ〕である。 射影ｐ(i)、ｉ＜Ｎ−１、の混合基数数字はＳ(1)
〔１〕〜Ｓ(1)〔ｉ−１〕（但しｉ＞１であれば）及
びＳ（ｉ＋１）〔ｉ＋１〕〜Ｓ（ｉ＋１）〔Ｎ〕であ
る。 良好な実施例は下記のようにして構成し得る。
最初に、Ｎ個の射影の各々に関して計算されるＮ
−１の混合基数数字を決定するためにMRCが使
用される。次に各数字が、それを計算するために
必要な資源（素子）によつて表現される。これ
は、下記にＮ＝４の場合について示されている。
但し各数字は次の形式の式によつて表現される。 （入力）＞ラツチ又は（ｐ−入力）（ｑ−入力）
＞ROMij但し、「ラツチ」は「１」、及び
「ROMij」は「1ij」と表わし、また記号「＞」は
その記号の左側の項が、その記号の右側の素子
（ROM又はラツチ）への入力である事を表わす。
データを得るための装置、より具体的には、誤り
検出及び訂正を行なう混合基数変換装置に関す
る。 Ｂ 従来技術 デイジタル信号処理（DPS）に対する剰余算
術（residue arithmetic）の応用に、最近、興味
が新たになつている。剰余数体系（residue
number system）（RNS）の内部でDSPの関数
を計算する事によつて、下記の利点が実現され
る。 １ 高いサンプリング周波数 ２ モジユール的インプリメンテーシヨン ３ フオールト・トレランス 剰余算術を用いたいかなるDSPのインピリメ
ンテーシヨンも、上記３つの利点を保持しなが
ら、その出力をRNSから重み付け数体系
（weighted number system）（WNS）へ翻訳す
る必要がある。 例えば、Ｔ秒のサイクル・タイムを有する多段
パイプライン式システムを考える。各Ｔ秒毎に、
新しい入力がシステムの各段に受け入れられる。
第１段への入力はシステムの入力である。各Ｔ秒
毎に、新しい出力が各段によつて形成される。最
終段の出力はシステムの出力である。ある段の出
力はその後続段への入力である。また各段自体が
複数段から成つていてもよい。 第２図は計算処理を行なうために使用し得る多
段パイプライン式システムを示す。このシステム
は、下記に概観するように、速いサイクル・タイ
ム、モジユール式インプリメンテーシヨン、及び
フオールト・トレランスという利点を達成するた
めに冗長剰余数体系算術の技術を利用する。 このシステムの入力は、ある重み付け数体系
（WNS）内で表現された１つ以上の整数である。
第１段10は入力の整数の剰余数体系（RNS）表
現を導き出し、必要な計算をこのRNS内で行な
い、そして所望の出力をRNS形式で形成する。
第１段の出力12はＮ個の剰余数の組ｋ(1)〜ｋ（Ｎ）
である。但しＮはRNSが定義されているモジユ
ラスの数である。ｋ（Ｎ）は上位の剰余数であり、
ｋ(1)は下位の剰余数である。RNSは、出力剰余
数に対して単一誤り訂正を行なう事を可能にする
ために少なくとも２つの冗長な上位のモジユラス
を含んでいる。 第２段14はＮ組のＮ−１混合基数の数字を形成
する。各組は、kiの１つの寄与を無視しながら残
りのＮ−１の剰余数に対して混合基数変換
（MRC）を行なう事によつて形成される。この
MRCにより得られたＮ−１混合基数数字はｉ番
目の射影（projection）と呼ばれる。ｋ(i)のいず
れも誤りがなければ、各々の射影は、所望のシス
テム出力の異なつたWNS表現である。誤つた剰
余数ｋ(i)が存在する時は、射影のうちただ１つだ
けが所望のシステム出力の正しいWNS表現であ
る。それはkiの寄与を無視する事によつて形成さ
れた射影である。本発明はこの第２段に係るもの
である。 第３段18は、第２段14の出力16を使用して、可
能であれば正しい出力を決定し、有用な誤り情報
を提供する。また第３段は、システム出力をより
便利なWNS表現に変換してもよい。 そのようなシステムの具体的な計算に焦点を当
てて、下記のＮ個の互いに素な整数の組に基く
RNSを考える。 ｛ｍ(1)，ｍ(2)，……，ｍ（Ｎ）｝ これらはRNSのモジユラスと呼ばれる。自然
数ｋのRNS表現は次のように書かれる。 〔ｋ(1)，ｋ(2)，……，ｋ（Ｎ）〕 ここで、ｋ(i)は剰余数と呼ばれ、ｋ
modulom(i)を表わす。 MRCはRNSからWNSへ翻訳するための有用
な技術である。整数ｋは、重み付け混合基数数字
の列によつて表現し得る。 (1)
ｋ＝N 〓i=1 ｄ(i)×ｗ(i) ここで、 (2)
Ｗ(i)＝i-1 〓j=1 ｍ(j) は、重み（ｗ(1)＝１）であり、ｄ(i)は混合基数数
字の桁である。 次に、特許請求の範囲を含む明細書中で用いら
れている主な用語、例えば、ROM、ラツチ、
MRC構造などは、剰余数体系算術の技術分野で
慣用されているものであり、以下にその意義を略
述する。 ROMij： アレイ位置（ｉ，ｊ）に配置され、時刻Ｏに入
力して２つの整数ｐ及びｑを受理し、時刻Ｔに下
記の方程式(3)を満足する整数ｒに相当する信号を
出力する機能を有する読取専用メモリを含む任意
の回路又はプログラム。ROMijの左側入力がｐ入
力であり、他方、右側入力がｑ入力である。 式(3)： ｒ＝｛（ｐ−ｑ）×ｍ(j)-1｝modulo ｍ(i) 但し、ｍ(j)-1は次式を満足するような整数。 ｛ｍ(j)-1×ｍ(j)｝modulo ｍ(i)＝１ ラツチ： 時刻Ｏに入力された整数に相当する信号を保持
し、時刻Ｔに出力する機能を有する任意の回路又
はプログラム。 MRC回路： ROMij及びラツチは、MRCを遂行するための
多段パイプライン構造を形成するようＮ列×（Ｎ
−１）段のアレイ（サイズＮのMRC構造の場合）
に配列され、所定ルールに従つて相互接続され
る。ｉ＞ｊのアレイ位置にはROMijを配置し、そ
れ以外の位置にはラツチを配置する。アレイ第１
段（最上段）に配列されたROMi1（ｉ＝２〜Ｎ）
のｐ入力には剰余数Ki（ｉ＝２〜Ｎ）が、そして
ｑ入力には剰余数K1が印加される。第１段のラ
ツチには剰余数K1が印加される。前段のROMij
の出力ｒが自段のROMijのｐ入力又はラツチ入力
となり、前段のラツチ入力が並列にROMijのｑ入
力になる。最下段のROMij及びラツチの出力が混
合基数数字を表わす。上記アレイ構造をサイズＮ
のMRC構造と呼ばれている。 第６図にはサイズＤのMRC構造が示されてい
る。第１段のパイプライン段のラツチには剰余数
I1が入力され、ROMi1（ｉ＝２，３……Ｄ）のｐ
入力には剰余数I2〜IDが入力される一方、その
ｑ入力には剰余数I1が入力されている。図中、ｉ
＞ｊならば、ROMijが、そしてそれ以外のときは
ラツチがアレイ位置に配置されている。最終段Ｄ
−１段の出力O1〜ODがサイズＤのMRC構造の
出力、即ち混合基数数字である。 第３図は、Ｎ＝４の場合のMRC構造において
剰余数Ｋ(i)から混合基数数字ｄ(i)を計算する従来
技術を示している。第４図は、第３番目の混合基
数射影（即ち、剰余数Ｋ(3)を除いた残りの剰余数
Ｋ(1)，Ｋ(2)及びＫ(4)について混合基数数字ｄ(i)を
計算するためのMRC構造）が示されている。図
示していないが、同様なMRC構造が第１番目、
第２番目及び第４番目の混合基数射影の計算のた
めに必要であり、全部で12個のROM及び12個の
ラツチが必要である。 MRC構造はRNSからWNSへの翻訳を行なう
だけではなく、誤りの検出及び訂正を行ない、な
お且つ高いサンプリング周波数の利点及びフオー
ルト・トレランス、モジユラー性というRNSの
利点を保持する。以前のように、Ｎ個のモジユラ
ス（但しその少なくとも２つは冗長である）を有
するRNSを用いると、剰余数の任意の１つにお
ける誤りを分離し、訂正する事ができる。これは
剰余数の各組からＮ個の混合基数射影を生成する
ようにMRC構造を有する事によつて達成される。
ｉ番目の混合基数射影は、Ｎ−１個の剰余数の組
からＮ−１個の混合基数数字を計算する事によつ
て得られる。ここでｉ番目の剰余数は計算から除
外される。各射影の最上位の混合基数数字を調べ
れば、誤つた剰余数を識別する事ができる。 Ｃ 発明が解決しようとする問題点 もしパイプライン式システムが各ROMサイク
ル・タイム毎に１つの出力を発生し、且つシステ
ムが平行的な誤り検出を行なうべきであれば、必
要な混合基数射影の全部が各サイクル毎に並列に
計算されなければならない。これはMRC構造を
Ｎ個並列にする事によつて達成可能である。本発
明はこの問題に対する、より経済的な解決を与え
る。 従つて、本発明の目的は、剰余数体系のデータ
から混合基数射影データを計算するための改良さ
れた装置を提供する事である。本発明によれば、
従来技術の装置よりも効率的な構造を用いて、誤
りの検出及び訂正を行なう改良された装置が提供
される。 Ｄ 問題点を解決するための手段 本発明によれば、Ｎ個のモジユラスを有する剰
余数体系で表現された入力データ信号を、出力の
混合基数射影データ信号に変換するための装置が
提供される。サイズＮ−１の通常の混合基数変換
（MRC）構造をＮ個組み合せたものより成る
ROM及びラツチの単一の配列が提供される。た
だし、上記構造の間で重複する信号路、ラツチ及
びROMは併合され、重複が除去されている。従
つて、本発明は、MRC構造が完全に並列化され
た時に存在する冗長な計算を除去している。従つ
て、剰余数体系データを用いて計算を行なう装置
内での誤りの検出及び訂正の問題に対して、より
経済的な解決法が与えられる。 本発明によれば、剰余数K1乃至KNを表わす
入力をＮ−１個のMRC構造（各MRC構造は予め
決められたアレイ位置にROMij及びラツチを有す
る）を用いて混合基数射影データに変換するため
の装置では、 上記MRC構造の各々Ｓ(z)（Ｚ＝１〜Ｎ−１）
は、Ｎ−Ｚ段及びＮ−Ｚ＋１列から成る可変サイ
ズのアレイであり（但し、第1MRC構造Ｓ(1)はＮ
−１段目を欠きＮ−２段目が最終段であり）、各
MRC構造Ｓ(z)において第Ｘ列（最右方が第１列）
及び第Ｙ段（最上段が第１段）の交点位置にはｉ
＝Ｘ＋Ｚ−１及びｊ＝Ｙ＋Ｚ−１により定義され
たROMijが配置されており、上記第1MRC構造Ｓ
(1)の入力は上記剰余数K1〜KNであり、その出
力は上記最終段からのＮ個の混合基数数字Ｓ(1)
［１］乃至Ｓ(1)［Ｎ］であり、 他のすべてのMRC構造Ｓ（ｚ）（Ｚ＝２〜Ｎ−
１）への入力は、第1MRC構造Ｓ(1)におけるＺ−
１段目へのＮ−Ｚ＋１個のｐ側入力であり、それ
らの出力は、夫々、最終段からの混合基数数字Ｓ
(z)［Ｚ］乃至Ｓ(z)［Ｎ］（Ｚ＝２〜Ｎ−１）であ
る事を特徴とする。 Ｅ 実施例 本発明は、MRC構造が完全に並列的に反復し
て設けられた時に存在する冗長な計算を除去す
る。第１図を参照しながら、本発明の実施例（Ｎ
＝４の場合）について説明する。第１図に示すよ
うに、９個だけのROM及び７個だけのラツチを
用いて第２図に示した従来と同様に４個の射影を
生成できる。この実施例は、列数及び段数が順次
に少なくなるＳ(1)，Ｓ(2)，Ｓ(3)と記述した３個の
MRC構造（一般にはＮ−１個のMRC構造）より
構成されている。Ｓ(1)は４列（一般にはＮ−１＋
１）、Ｓ(2)は３列（Ｎ−２＋１）、Ｓ(3)は２列（Ｎ
−３＋１）であり、第６図に関して説明されるよ
うに一般にはＳ(z)の列数は（Ｎ−Ｚ＋１）で表わ
される。段数について云えばＳ(1)は２段、Ｓ(2)は
２段、Ｓ(3)は１段であり、一般にはＮ−Ｚ段で表
わされる。但し、Ｓ(1)は例外的に最下段の１段が
省略される（これは、パイプラインの長さがＮ−
２段であり、従来の反復方式と同じである）。各
段及び各列の交点にROMij又はラツチが設けられ
ている。第６図に関して説明されるように、
MRC構造のＳ(z)において、列Ｘ及び段Ｙの交点
に設けられたROMijの添字ｉ及びｊは次のように
表わされる。 ｉ＝Ｘ＋Ｚ−１ ｊ＝ｙ＋Ｚ−１ 但し、Ｓ(z)内で、最右列が第１列であり最上段
が第１段である。 上式を、第１図のＳ(2)における最上段が（ｙ＝
１）の２列目（ｘ＝２）のROMに適用すると、 ｉ＝Ｘ＋Ｚ−１＝２＋２−１＝３ ｊ＝Ｙ＋Ｚ−１＝１＋２−１＝２ 従つてROMijはROM32として定義される。 同様にＳ(3)における最上段が（ｙ＝１）及び最
左列（ｘ＝２）のROMijは、 ｉ＝２＋３−１＝４ ｊ＝１＋３−１＝３ 即ち、ROM43で表わされる。 第１図のROM、ラツチの出力線の矢印の下方
に、夫々、示された数字１，２，３，４は上記
ROMijの列位置を表わすｉの数字を表わす。 ｉ＞ｊであれば、ROMを、そうでなければ、
ラツチを各交点位置に設ける。第１図のＳ構造出
力の混合基数数字は、従来の反復方式の射影に対
して、下記のように関係している。 第１の射影＝｛Ｓ(2)〔４〕，Ｓ(2)〔３〕，Ｓ(2)
〔２〕｝ 第２の射影＝｛Ｓ(3)〔４〕，Ｓ(3)〔３〕，Ｓ(1)
〔１〕｝ 第３の射影＝｛Ｓ(1)〔４〕，Ｓ(1)〔２〕，Ｓ(1)
〔１〕｝ 第４の射影＝｛Ｓ(1)〔３〕，Ｓ(1)〔２〕，Ｓ(1)
〔１〕｝ ここで(j)，〔ｉ〕は構造Ｓ(j)のｉ番目の出力を
示す。 一般に、単純な反復方式はＡ個のROM及びＡ
個のラツチを使用する。但し、 (4) Ａ＝Ｎ N-2 〓i=1 (i)＝Ｎ（Ｎ−１）（Ｎ−２）／２ 一般に本発明はＢ−１個のROMとＢ−（Ｎ−
１）個のラツチを使用する。但し、 Ｂ＝N-1 〓j=1 j 〓i=1 (i) ＝Ｎ（Ｎ−１）（Ｎ＋１）／６ 本発明により得られる利益の尺度として、与え
られたＮの値に関して必要なROMの数を比較し
てもよい。第５図はｐ対Ｎの曲線20を示す。ｐ＝
100×（１−（Ｂ−１）／Ａ） これはROMの必要な数が減少する百分率であ
る。大きなＮの場合、ｐは漸近的に67％に近付
く。 一般に、良好な実施例はＮ−２段のパイプライ
ンを有する。一般に、各段は２つの型の要素から
構成されている。即ちラツチとROMである。ラ
ツチはサイクルの開始時に入力を捕え、サイクル
の残期間中、その値を出力に保持する。ROMは
サイクルの開始時にその入力ｐ及びｑを捕え、サ
イクルの終了する前に出力ｒを発生する。
ROMijの出力は式(3)により定義される。 良好な実施例は、上述の機能を実現するために
ROMを使用する。しかし、同じ機能を与える回
路素子又はプログラムで置き換える事も可能であ
る。 第１図に描かれた良好な実施例はＮ＝４の場合
のものである。本発明の原理によれば、任意のＮ
の値に拡張する事ができる。一般的な場合（Ｎ）
について、良好な実施例を説明する。 再び、下記のＮ個の互いに素な整数モジユラス
の組を考える。 ｛ｍ（Ｎ），……，ｍ(2)，ｍ(1)｝ ここでｍ（ｉ＋１）＞ｍ(i)ｋは下記のような整数
を表わすものとする。 ｋ＜N-2 〓i=1 ｍ(i) この整数ｋは、RNS方式で、Ｎ個の剰余数に
より表現する事ができる。 ｋ（Ｎ），……，ｋ(2)，ｋ(1) ここで、ｋ(i)は値Ｋ modulo ｍ(i)を表わす。 この場合、整数ｋに関するRNS表現は２個の
冗長な剰余数字を含んでいる。この冗長性によ
り、ｋに関するRNS表現中の１つの誤つた剰余
数を検出し訂正する事ができる。 整数ｋに関するRNS表現中の誤りを検出し訂
正する１つの技術はMRCを利用する。 １組のｋ(i)から、MRCは式(1)及び式(2)に従う
ｄ(i)の組を生成する。誤つた剰余数は次のように
して検出できる。 最初に、整数ｋを表わすＮ個の剰余数の組か
ら、各々の剰余数を１つ除外する事によりＮ−１
個の数の組をＮ個形成する。各組は射影と呼ぶ。
ｋ(i)を除外する事により形成される射影をｐ(i)で
表わすものとする。各ｐ(i)にMRCを適用する。
各ｐ(i)にMRCを適用する。各ｐ(i)に関して、上
位の混合基数数字を調べる。もし全てがゼロの値
を有していれば、どのｋ(i)も誤つていない。もし
ｐ(j)以外の全てが非ゼロであれば、ｋ(j)が誤つて
おり、ｐ(j)がｋに関する正しい表現である。 一般的な場合（Ｎ）に関する良好な実施例は、
（Ｂ−１）個のROMij及び（Ｂ−Ｎ＋１）個のラ
ツチを含むＮ−２段のパイプラインである。但
し、 Ｂ＝Ｎ（Ｎ−１）（Ｎ＋１）／６ 実施例の入力は、Ｎ個の剰余数であり、出力は
（Ｎ＋２）（Ｎ−１）／２個の混合基数数字であ
る。実施例はＮ−１個のMRC構造Ｓ(1)〜Ｓ（Ｎ−
１）より構成される。Ｓ(z)の列ｘ、段ｙを占める
ROMijは次式によつて決定される。 ｉ＝ｘ＋ｚ−１及びｊ＝ｙ＋ｚ−１ Ｓ(1)の入力はｋ(1)〜ｋ（Ｎ）である。 Ｓ(1)は１段が省略されている点で特殊なケース
である。その出力は段Ｎ−２の後で与えられる。
Ｓ(1)の出力はＮ個の混合基数数字Ｓ(1)〔１〕〜Ｓ
(1)〔Ｎ〕である。 Ｓ(z)（Ｚ＝２〜Ｎ−１の場合）の入力はＳ(1)の
Ｚ−１段目へのＮ−Ｚ＋１のｐ側入力と同じであ
る。 Ｓ(z)（Ｚ＝２〜Ｎ−１の場合）の出力は、混合
基数数字Ｓ(z)［Ｚ］〜Ｓ(z)［Ｎ］である。 実施例の出力は、全ての射影の混合基数表現を
与えるのに必要且つ充分である。射影ｐ（Ｎ）の
混合基数数字はＳ(1)〔１〕〜Ｓ(1)〔Ｎ−１〕であ
る。射影ｐ（Ｎ−１）の混合基数数字は、Ｓ(1)
〔１〕〜Ｓ(1)〔Ｎ−２〕及びＳ(1)〔Ｎ〕である。 射影ｐ(i)、ｉ＜Ｎ−１、の混合基数数字はＳ(1)
〔１〕〜Ｓ(1)〔ｉ−１〕（但しｉ＞１であれば）及
びＳ（ｉ＋１）〔ｉ＋１〕〜Ｓ（ｉ＋１）〔Ｎ〕であ
る。 良好な実施例は下記のようにして構成し得る。
最初に、Ｎ個の射影の各々に関して計算されるＮ
−１の混合基数数字を決定するためにMRCが使
用される。次に各数字が、それを計算するために
必要な資源（素子）によつて表現される。これ
は、下記にＮ＝４の場合について示されている。
但し各数字は次の形式の式によつて表現される。 （入力）＞ラツチ又は（ｐ−入力）（ｑ−入力）
＞ROMij但し、「ラツチ」は「１」、及び
「ROMij」は「1ij」と表わし、また記号「＞」は
その記号の左側の項が、その記号の右側の素子
（ROM又はラツチ）への入力である事を表わす。
【表】
次に、ユニークな部分式が識別される。それら
は、下記の表中では部分式の左側に「＊」が付け
られている。
は、下記の表中では部分式の左側に「＊」が付け
られている。
【表】
３番目に、１次の（最も内側の）ユニークな部
分式によつて示される素子を配置及び接続する事
により実施例の第１段が構成される。この例で
は、それらは、次の通りである。 k1＞１，k2k1＞b21，k3k1＞b31，k4k1＞
b41，k2＞１，k3k2＞b32，k4k2＞b42。 ４番目に、２次のユニークな部分式により示さ
れる素子を配置及び接続する事によつて実施例の
第２段が構成される。この例では、それら下記の
通りである。 （k3k1＞b31）（k2k1＞b21）＞b32，（k4k1＞
b41）（k2k1＞b21＞b42，（k4k1＞b41）（k3k1＞
b31）＞b43，（k4k2＞b42）（k3k2＞b32）＞b43。 このプロセスは、全ての（Ｎ−１）段が構成さ
れるまで継続する。最後に、パイプラインの終端
まで全ての混合基数数字を伝達するために必要な
場所にラツチが挿入される。 本発明は、数値計算、信号処理、データ暗号
化、データ通信、その他のために使われる任意の
電子的、電気機械的、光電子的、ソフトウエア的
又はその他のシステムに適用する事ができる。 Ｆ 発明の効果 本発明を用いれば、従来よりも少量のハードウ
エアを用いて、剰余数表現のデータを、混合基数
表現に変換し、且つその際に誤りの検出訂正を行
なう事ができる。
分式によつて示される素子を配置及び接続する事
により実施例の第１段が構成される。この例で
は、それらは、次の通りである。 k1＞１，k2k1＞b21，k3k1＞b31，k4k1＞
b41，k2＞１，k3k2＞b32，k4k2＞b42。 ４番目に、２次のユニークな部分式により示さ
れる素子を配置及び接続する事によつて実施例の
第２段が構成される。この例では、それら下記の
通りである。 （k3k1＞b31）（k2k1＞b21）＞b32，（k4k1＞
b41）（k2k1＞b21＞b42，（k4k1＞b41）（k3k1＞
b31）＞b43，（k4k2＞b42）（k3k2＞b32）＞b43。 このプロセスは、全ての（Ｎ−１）段が構成さ
れるまで継続する。最後に、パイプラインの終端
まで全ての混合基数数字を伝達するために必要な
場所にラツチが挿入される。 本発明は、数値計算、信号処理、データ暗号
化、データ通信、その他のために使われる任意の
電子的、電気機械的、光電子的、ソフトウエア的
又はその他のシステムに適用する事ができる。 Ｆ 発明の効果 本発明を用いれば、従来よりも少量のハードウ
エアを用いて、剰余数表現のデータを、混合基数
表現に変換し、且つその際に誤りの検出訂正を行
なう事ができる。
第１図は本発明の良好な実施例の混合基数変換
構造体の概略図、第２図は従来の多段パイプライ
ン・システムの図、第３図は従来のパイプライン
式混合基数変換構造体の図、第４図は誤り検出及
び訂正に関連して使用される従来の混合基数変換
構造体の一部の図、第５図は本発明の良好な実施
例を用いた時の、必要なROMの数の減少を示す
グラフ、第６図は一般的な混合基数変換構造体の
図である。
構造体の概略図、第２図は従来の多段パイプライ
ン・システムの図、第３図は従来のパイプライン
式混合基数変換構造体の図、第４図は誤り検出及
び訂正に関連して使用される従来の混合基数変換
構造体の一部の図、第５図は本発明の良好な実施
例を用いた時の、必要なROMの数の減少を示す
グラフ、第６図は一般的な混合基数変換構造体の
図である。
Claims (1)
- 【特許請求の範囲】 １ Ｎ個のモジユラスを用いた剰余数体系の剰余
数K1乃至KNを表わす入力信号を、各々、多段
パイプライン構造を形成するアレイ状に配置され
たROMij及びラツチから成るＮ−１個のMRC構
造Ｓ(z)（但し、Ｚ＝１〜Ｎ−１）の所定のものの
第１段に印加して変換動作を実施して最終段から
混合基数射影データ信号を得るための変換装置で
あつて、 上記各MRC構造Ｓ(z)は、Ｎ−Ｚ段及びＮ−Ｚ
＋１列から成る可変サイズのアレイであり（但
し、第1MRC構造Ｓ(1)はＮ−１段目を欠きＮ−２
段目が最終段であり）、各MRC構造Ｓ(z)において
第Ｘ列（最右方が第１列）及び第Ｙ段（最上段が
第１段）の交点位置にはｉ＝Ｘ＋Ｚ−１及びｊ＝
Ｙ＋Ｚ−１により定義されたROMijが配置され
ており、 上記第1MRC構造Ｓ(1)の入力は、上記剰余数
K1〜KNであり、その出力は上記最終段からの
Ｎ個の混合基数数字Ｓ(1)［１］乃至Ｓ(1)［Ｎ］で
あり、 他のすべてのMRC構造Ｓ(z)（Ｚ＝２〜Ｎ−１）
への入力は、第1MRC構造Ｓ(1)におけるＺ−１段
目へのＮ−Ｚ＋１個のｐ側入力であり、それらの
出力は、夫々、最終段からの混合基数数字Ｓ(z)
［Ｚ］乃至Ｓ(z)［Ｎ］（Ｚ＝２〜Ｎ−１）である事
を特徴とする上記変換装置。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US06/890,252 US4752904A (en) | 1986-07-28 | 1986-07-28 | Efficient structure for computing mixed-radix projections from residue number systems |
| US890252 | 1986-07-28 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS6336614A JPS6336614A (ja) | 1988-02-17 |
| JPH0445016B2 true JPH0445016B2 (ja) | 1992-07-23 |
Family
ID=25396456
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP62182446A Granted JPS6336614A (ja) | 1986-07-28 | 1987-07-23 | 剰余数表現のデ−タを混合基数射影デ−タに変換する装置 |
Country Status (3)
| Country | Link |
|---|---|
| US (1) | US4752904A (ja) |
| EP (1) | EP0254821A3 (ja) |
| JP (1) | JPS6336614A (ja) |
Families Citing this family (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CA1318027C (en) * | 1987-10-12 | 1993-05-18 | Jun Takayama | Method and apparatus for encoding and decoding data in residue number system |
| US4924467A (en) * | 1988-08-24 | 1990-05-08 | Unisys Corporation | System for checking duplicate logic using complementary residue codes to achieve high error coverage with a minimum of interface signals |
| US5081629A (en) * | 1989-05-08 | 1992-01-14 | Unisys Corporation | Fault isolation for multiphase clock signals supplied to dual modules which are checked by comparison using residue code generators |
| US5050120A (en) * | 1989-09-29 | 1991-09-17 | The Boeing Company | Residue addition overflow detection processor |
| US4996527A (en) * | 1989-09-29 | 1991-02-26 | The Boeing Company | Pipelined residue to mixed base converter and base extension processor |
| US4963869A (en) * | 1989-09-29 | 1990-10-16 | The Boeing Company | Parallel residue to mixed base converter |
| CN102812431A (zh) | 2010-03-22 | 2012-12-05 | Lrdc系统有限公司 | 用于识别与保护一组源数据的完整性的方法 |
| WO2018086951A1 (en) * | 2016-11-08 | 2018-05-17 | Koninklijke Philips N.V. | Electronic calculating device for converting a residue numbers system representation to a radix representation |
Family Cites Families (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4107783A (en) * | 1977-02-02 | 1978-08-15 | The Board Of Trustees Of The Leland Stanford Junior University | System for processing arithmetic information using residue arithmetic |
| US4281391A (en) * | 1979-01-15 | 1981-07-28 | Leland Stanford Junior University | Number theoretic processor |
| US4458327A (en) * | 1979-06-28 | 1984-07-03 | John Larson | Prime or relatively prime radix data processing system |
| US4418394A (en) * | 1980-08-13 | 1983-11-29 | Environmental Research Institute Of Michigan | Optical residue arithmetic computer having programmable computation module |
| US4537502A (en) * | 1982-09-30 | 1985-08-27 | The Boeing Company | Multiple discrete frequency ranging with error detection and correction |
-
1986
- 1986-07-28 US US06/890,252 patent/US4752904A/en not_active Expired - Lifetime
-
1987
- 1987-05-05 EP EP87106474A patent/EP0254821A3/en not_active Withdrawn
- 1987-07-23 JP JP62182446A patent/JPS6336614A/ja active Granted
Also Published As
| Publication number | Publication date |
|---|---|
| US4752904A (en) | 1988-06-21 |
| JPS6336614A (ja) | 1988-02-17 |
| EP0254821A2 (en) | 1988-02-03 |
| EP0254821A3 (en) | 1990-04-25 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Avizienis | Arithmetic error codes: Cost and effectiveness studies for application in digital system design | |
| US4099160A (en) | Error location apparatus and methods | |
| JPH0567981A (ja) | ユークリツドの互除回路 | |
| JPS6122826B2 (ja) | ||
| Avizienis | Arithmetic algorithms for error-coded operands | |
| JPH02500698A (ja) | データ依存処理能力を有するセルアレイ | |
| JPS6327734B2 (ja) | ||
| US5805617A (en) | Apparatus for computing error correction syndromes | |
| JPS60204125A (ja) | デコーデイング装置 | |
| JP2013070122A (ja) | 誤り訂正装置、誤り訂正方法及び演算装置 | |
| JPH0445016B2 (ja) | ||
| Zhou | A new bit-serial systolic multiplier over GF (2/sup m/) | |
| JP2000004169A (ja) | Ｃｒｃ演算方法及びｃｒｃ演算回路 | |
| GB2088600A (en) | Apparatus for sorting data words on the basis of the valuees of associated parameters | |
| JP3485075B2 (ja) | 復号回路及びその復号方法 | |
| JP3614978B2 (ja) | ガロア体の除算方法および除算装置 | |
| Tang et al. | A new single-error correction scheme based on self-diagnosis residue number arithmetic | |
| Ananda Mohan | Error Detection, Correction and Fault Tolerance in RNS-Based Designs | |
| US5031137A (en) | Two input bit-serial multiplier | |
| JPH10327080A (ja) | シンドローム計算装置 | |
| RU2309535C1 (ru) | Устройство для преобразования числа из полиномиальной системы классов вычетов в позиционный код с коррекцией ошибки | |
| JP2592681B2 (ja) | セル同期回路 | |
| TWI551059B (zh) | 用於具有不同ＧＦ（２ｍ）中ｍ值的ＢＣＨ碼之多模式秦式搜尋電路 | |
| JPH0969836A (ja) | Ｃｒｃ符号生成回路およびｃｒｃ符号生成回路設計方法 | |
| JP2665268B2 (ja) | サイクリックコードのステップ・バイ・ステップ型復号方法及び復号器 |