JP2021128555A

JP2021128555A - 乱数発生器

Info

Publication number: JP2021128555A
Application number: JP2020022900A
Authority: JP
Inventors: 信人藤田; Nobuhito Fujita
Original assignee: Kyocera Document Solutions Inc
Current assignee: Kyocera Document Solutions Inc
Priority date: 2020-02-13
Filing date: 2020-02-13
Publication date: 2021-09-02

Abstract

【課題】回路規模が小さく低コストの乱数発生器を得る。【解決手段】所定の固定の符号ビット数Ｎと同数のビットレジスター１−１〜１ーＮが並列に配列されており、帰還回路部２は、複数のビットレジスター１−１〜１ーＮの出力値Ｙ（１）〜Ｙ（Ｎ）を入力値Ｘ（１）〜Ｘ（Ｎ）として複数のビットレジスター１−１〜１ーＮへの出力値Ｙｉ（１）〜Ｙｉ（Ｎ）を生成する。そして、帰還回路部２は、（ａ）符号ビット数Ｎの帰還漸化式に対応する複数のタップ位置にそれぞれ対応したビット幅だけ最上位ビット側へ入力値Ｘ（１）〜Ｘ（Ｎ）の一部または全部のビット列をシフトさせて得られる複数のシフトビット列の一部、および（ｂ）その複数のシフトビット列の一部の排他的論理和を、出力値Ｙｉ（１）〜Ｙｉ（Ｎ）のビット列とする。【選択図】図１

Description

本発明は、乱数発生器に関するものである。

疑似乱数（Ｍ系列符号など）を発生する回路が種々提案されている。

図４は、９ビットの疑似乱数を生成するための線形帰還シフトレジスターの一例を示す図である。図４に示す線形帰還シフトレジスターでは、９個のビットレジスターＢ１〜Ｂ９が縦列に接続されており、タップ位置＃５（ビットレジスターＢ５とビットレジスターＢ６との間）に排他的論理和回路ＸＯＲが挿入され、最下位ビットのビットレジスターＢ１の値が、タップ位置＃５（排他的論理和回路ＸＯＲ），＃９（ビットレジスターＢ９）にフィードバックされている。

図５は、線形帰還シフトレジスターにおける符号ビット数と、その符号ビット数に対応する帰還漸化式、帰還論理式、および帰還すべきタップ位置との対応関係を説明する図である。図５に示すように、要求される符号ビット数（つまり、疑似乱数のビット数）に応じた漸化式などに対応する線形帰還シフトレジスターが構成され使用される。

例えば図４に示すような線形帰還シフトレジスターでは、１つの疑似乱数を得るのに、符号ビット数と同一のクロック数だけ線形帰還シフトレジスターを動作させる必要があり、比較的時間がかかってしまう。

そのため、あるパラレル型のＭ系列符号生成器は、並列に配置されたビットレジスターと、ビットレジスターの前段においてマトリクス状の配置された複数の排他的論理和回路群を含む帰還回路部とを備え、帰還回路部に所望の帰還論理式がセットされ、すべてのビットレジスターの値が帰還回路部にフィードバックされ、１クロックごとに疑似乱数（Ｍ系列符号）が得られるように、セットされた帰還論理式に対応する帰還回路部の演算結果がビットレジスターにセットされている（例えば非特許文献１参照）。

上田直也，「パラレル型のＭ系列符号生成器」，[online]，２００８年８月１日，ＥＤＮＪａｐａｎ，[2019年10月4日検索]，インターネット<https://ednjapan.com/edn/articles/0808/01/news134.html>

しかしながら、上述のＭ系列符号生成器は、種々の符号ビット数の疑似乱数の発生に対応すべく帰還回路部が複雑な回路構成を有するため、回路規模が大きくなり回路全体のコストが高くなってしまう。

本発明は、上記の問題に鑑みてなされたものであり、回路規模が小さく低コストの乱数発生器を得ることを目的とする。

本発明に係る乱数発生器は、所定の固定の符号ビット数と同数の並列に配列されたビットレジスターと、前記複数のビットレジスターの出力値を入力値として前記複数のビットレジスターへの出力値を生成する帰還回路部とを備える。そして、前記帰還回路部は、（ａ）前記符号ビット数の帰還漸化式に対応する複数のタップ位置にそれぞれ対応したビット幅だけ最上位ビット側へ前記入力値の一部または全部のビット列をシフトさせて得られる複数のシフトビット列の一部、および（ｂ）前記複数のシフトビット列の一部の排他的論理和を、前記出力値のビット列とする。

本発明によれば、回路規模が小さく低コストの乱数発生器が得られる。

本発明の上記又は他の目的、特徴および優位性は、添付の図面とともに以下の詳細な説明から更に明らかになる。

図１は、本発明の実施の形態に係る乱数発生器の構成を示す回路図である。図２は、図１に示す乱数発生器において符号ビット数が９である場合の帰還回路部２の演算について説明する図である。図３は、図１に示す乱数発生器において符号ビット数が９である場合の帰還回路部２の構成例を示す回路図である。図４は、９ビットの疑似乱数を生成するための線形帰還シフトレジスターの一例を示す図である。図５は、線形帰還シフトレジスターにおける符号ビット数と、その符号ビット数に対応する帰還漸化式、帰還論理式、および帰還すべきタップ位置との対応関係を説明する図である。

以下、図に基づいて本発明の実施の形態を説明する。

図１は、本発明の実施の形態に係る乱数発生器の構成を示す回路図である。図１に示す乱数発生器は、所定の固定ビット数の疑似乱数（Ｍ系列符号など）を生成する。図１に示す乱数発生器は、所定の固定の符号ビット数Ｎと同数の並列に配列されたビットレジスター１−１〜１−Ｎ（ここではＮ＝９）と、帰還回路部２とを備える。帰還回路部２は、その複数のビットレジスター１−１〜１−Ｎの出力値Ｙ（１）〜Ｙ（Ｎ）を入力値Ｘ（１）〜Ｘ（Ｎ）として複数のビットレジスター１−１〜１−Ｎへの出力値Ｙｉ（１）〜Ｙｉ（Ｎ）を生成する。

ここでは、ビットレジスター１−ｊ（ｊ＝１，・・・，Ｎ）は、Ｄフリップフロップであり、ビットレジスター１−１〜１−Ｎは、単一のクロック信号ＣＬＫで動作する。

特に、帰還回路部２は、符号ビット数Ｎの帰還漸化式に対応する複数のタップ位置にそれぞれ対応したビット幅だけ最上位ビット側へ入力値Ｘ（ｉ）の一部または全部のビット列をシフトさせて複数のシフトビット列を生成し、その複数のシフトビット列の一部、およびその複数のシフトビット列の一部の排他的論理和を、出力値Ｙ（ｉ）のビット列とする。

図２は、図１に示す乱数発生器において符号ビット数が９である場合の帰還回路部２の演算について説明する図である。

Ｎ＝９の場合、図２に示すように、帰還のタップ位置は＃５および＃９となり、帰還回路部２は、符号ビット数Ｎの帰還漸化式に対応する複数のタップ位置＃５，＃９にそれぞれ対応したビット幅（５ビットと９ビット）だけ最上位ビット側へ入力値Ｘ（ｉ）の一部または全部のビット列をシフトさせて得られる２つのシフトビット列Ｘｓｈｉｆｔ１，Ｘｓｈｉｆｔ２の一部（ビット列Ｘｓｈｉｆｔ１のＸ（１）〜Ｘ（４））を出力値Ｙｉ（６）〜Ｙ（９）とし、そのシフトビット列の一部の排他的論理和（ビット列Ｘｓｈｉｆｔ１のＸ（５）〜Ｘ（９）とビット列Ｘｓｈｉｆｔ２のＸ（１）〜Ｘ（５）との排他的論理和、つまり、各ビットの排他的論理和）を出力値Ｙｉ（１）〜Ｙｉ（５）として、出力値Ｙｉ（１）〜Ｙｉ（９）のビット列とする。

図３は、図１に示す乱数発生器において符号ビット数が９である場合の帰還回路部２の構成例を示す回路図である。

この実施の形態では、図３に示すように、帰還回路部２は、上述の排他的論理和の演算を行い出力値Ｙｉ（ｉ）のビット列の一部を生成する排他的論理和回路部２１と、入力値Ｘ（ｉ）のビット列の一部を出力値Ｙｉ（ｉ）のビット列の残りの部分とする結線部２２とを備える。結線部２２は、１または複数の結線用の配線である。

次に、上記乱数発生器の動作について説明する。ここでは、Ｎ＝９の場合について説明する。

まず、図示せぬ初期値設定部によって所定のシードが初期値としてビットレジスター１−１〜１−９にセットされる。

ある時点でのビットレジスター１−１〜１−９の出力値Ｙ（１）〜Ｙ（９）（つまり、９ビットの疑似乱数）が、帰還回路部２にフィードバックされる。

その時点で、帰還回路部２は、図２および図３に示すようにして、次の時点のビットレジスター１−１〜１−９の出力値Ｙ（１）〜Ｙ（９）となる帰還回路部２の出力値Ｙｉ（１）〜Ｙ（９）（つまり、次のクロックでビットレジスター１−１〜１−９にセットされる値）を、ビットレジスター１−１〜１−９に出力する。

そしてクロック信号ＣＬＫにおける次のクロック（立上りまたは立下り）で、ビットレジスター１−１〜１−９が保持し出力する値Ｙ（１）〜Ｙ（９）が、帰還回路部２の出力値Ｙｉ（１）〜Ｙｉ（９）で更新される。

以後、クロック信号ＣＬＫにおける１クロックごとに、ビットレジスター１−１〜１−９の出力値Ｙ（１）〜Ｙ（９）が、帰還回路部２の出力値Ｙｉ（１）〜Ｙｉ（９）で更新され、１クロックごとに、９ビットの疑似乱数がビットレジスター１−１〜１−９の出力値Ｙ（１）〜Ｙ（９）として順次出力される。

以上のように、上記実施の形態によれば、所定の固定の符号ビット数Ｎと同数のビットレジスター１−１〜１ーＮが並列に配列されており、帰還回路部２は、複数のビットレジスター１−１〜１ーＮの出力値Ｙ（１）〜Ｙ（Ｎ）を入力値Ｘ（１）〜Ｘ（Ｎ）として複数のビットレジスター１−１〜１ーＮへの出力値Ｙｉ（１）〜Ｙｉ（Ｎ）を生成する。そして、帰還回路部２は、（ａ）符号ビット数Ｎの帰還漸化式に対応する複数のタップ位置にそれぞれ対応したビット幅だけ最上位ビット側へ入力値Ｘ（１）〜Ｘ（Ｎ）の一部または全部のビット列をシフトさせて得られる複数のシフトビット列の一部、および（ｂ）その複数のシフトビット列の一部の排他的論理和を、出力値Ｙｉ（１）〜Ｙｉ（Ｎ）のビット列とする。

これにより、１クロックごとに疑似乱数を生成可能であって、回路規模が小さく低コストの乱数発生器が得られる。そして、このようにして生成される疑似乱数は、所定の画像処理に要求されるノイズとして使用されたり、暗号鍵の生成に使用されたり、確率モデルによる解析やシミュレーションに使用されたりする。

なお、上述の実施の形態に対する様々な変更および修正については、当業者には明らかである。そのような変更および修正は、その主題の趣旨および範囲から離れることなく、かつ、意図された利点を弱めることなく行われてもよい。つまり、そのような変更および修正が請求の範囲に含まれることを意図している。

例えば、上記実施の形態に係る乱数発生器はハードウェアで構成されているが、同様の演算を行うプログラムを実行するコンピューター（つまり、ソフトウェア）で実現されてもよい。

また、上記実施の形態では、符号ビット数Ｎが９である場合を例示しているが、他の符号ビット数でもよく、他の符号ビット数の場合も同様に乱数発生器を構成できる。

本発明は、例えば、乱数発生器に適用可能である。

１−１〜１−９ビットレジスター
２帰還回路部
２１排他的論理和回路部
２２結線部

Claims

所定の固定の符号ビット数と同数の並列に配列されたビットレジスターと、
前記複数のビットレジスターの出力値を入力値として前記複数のビットレジスターへの出力値を生成する帰還回路部とを備え、
前記帰還回路部は、（ａ）前記符号ビット数の帰還漸化式に対応する複数のタップ位置にそれぞれ対応したビット幅だけ最上位ビット側へ前記入力値の一部または全部のビット列をシフトさせて得られる複数のシフトビット列の一部、および（ｂ）前記複数のシフトビット列の一部の排他的論理和を、前記出力値のビット列とすること、
を特徴とする乱数発生器。
前記帰還回路部は、前記排他的論理和の演算を行い前記出力値のビット列の一部を生成する排他的論理和回路部と、前記入力値のビット列の一部を前記出力値のビット列の残りの部分とする結線部とを備えることを特徴とする請求項１記載の乱数発生器。