JPH01811A - 擬似ランダムバイナリシーケンス発生器 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 本発明は擬似ランダムバイナリシーケンス発生器に関す
るものである。

擬似ランダムバイナリシーケンス発生器は既知であり、
その構成および作動はベーカーおよびパイパーの著書“
暗号システム”１９８２年ロンドン。

ノースウッド　ブック社発行に記載されている。

特にこの種の発生器は直線性フィードバックシフトレジ
スタの形態を採り、特にこの種直線性フィードバックシ
フトレジスタには“ガロア′″型又は゛′デュアル′″
型のものがある。

かかる擬似ランダムバイナリシーケンス発生器は主とし
てｎｌｉの再循環シフト　レジスタおよび１個以上の関
連する論理ゲートを、少なくとも２個のシフトレジスタ
段の出力側を結合するループ内に具える。論理ゲートを
適当に選択することにより長さが２″−１ビツトの繰返
しシーケンスを得ることができる。このｎを適当な大き
さの数とする場合にはこのシーケンスは実際上極めて長
くなり、且つ上記ビットはランダム従って“擬似ランダ
ム”であると見做すことができる。

擬似ランダムバイナリシーケンス発生器の出力が模倣さ
れる可能性を減少する必要があり、且つこれら発生器の
出力信号および数個のシフトレジスタ段の内容が知られ
ている場合でもこれらシフトレジスタ段の内容の双方の
非予知性を増大する必要がある用途は多数ある。

本発明の要旨は後述の請求の範囲から明らかである。

図面につき本発明の詳細な説明する。

第１図に示す本発明擬似ランダムバイナリシーケンス発
生器は２つの直線性フィードバックシフトレジスタＳお
よびＴを具える。シフトレジスタＳには２９個のシフト
レジスタ段Ｓ。−−−Ｓ２ａを設ケると共にシフトレジ
スタＴには３１個のシフトレジスタ段Ｔ、−−−Ｔ、、
を設ける。各シフトレジスタでは最終のシフトレジスタ
段の出力を常規作動中再循環ループの第１シフトレジス
タ役に入力として供給する。またこのループには排他的
ＯＲ回路の形態の複数の論理ゲートＧを設け、これらゲ
ートによって最終シフトレジスタ段の出力と、次のシフ
トレジスタ段に供給する関連のシフトレジスタ段の出力
とを合成する。

論理ゲートＧの位置を適宜選定してレジスタにより発生
するシーケンスの長さが最大可能な長さとなるようにす
る。従来論理ゲートの位置は次式で表わされるように多
項式の形態で示すことができる。

ｆ（Ｘ）＝１＋Ｃ，Ｘ＋Ｃ２Ｘ２＋−−−Ｃ，Ｘ’＋−
一−Ｃ，，，Ｘ”−’＋Ｘ”上式を用いることにより擬
似ランダムバイナリシーケンス発生器Ｓは次式で表すこ
とができる。

１＋Ｘ２＋Ｘ３＋Ｘ４＋ＸＳ＋Ｘ７＋Ｘ１１十に＋３十
Ｘ１４十Ｘ２０＋Ｘ２９上式から明らかなように論理ゲ
ートはシフトレジスタ段Ｓ２１　Ｓ３１　Ｓ４１　ＳＳ
Ｉ　Ｓｏｌ　５ＬＩＴ　５１３１３１４およびＳ２０へ
の入力側に位置するようになる。これがため９個の論理
ゲートが存在し、且つ各ゲートによって多項式に追加の
項を導入する。

同様にして擬似ランダムバイナリシーケンス発生器Ｔの
論理ゲートＧもシフトレジスタ段Ｔ、、　Ｔ２゜Ｔ３＋
　ＴＳ＋　Ｔ６＋　Ｌ＋　Ｔ９＋　ＴＩＯ＋　ＴＩｌ＋
　Ｔ＋５＋　ＴＩ９＋　Ｔ２３およびＴ２７への人　刃
側に位置するようになる。

このばとあいには１３個の論理ゲートが存在する。

又、第１図に示す回路にはマルチプレクサ）Ｚ、即ち選
択回路を設ける。この選択回路には５個のアドレス入力
端子Ａ、および３２個のデータ入力端子Ｂ＋　を設け、
この選択回路によりアドレス入力端子に供給されるアド
レスワードに従って出力側に供給するデータ入力端子の
１つを選択する。−般に、ｐ個のデータ入力端子が存在
する場合にはｑ個のアドレス入力端子が存在し、ここに
ｑは２ｑ≧ｐを満足する最低値とする。

データ入力端子にはシフトレジスタＴのシフトレジスタ
段の出力が供給され、従ってＴ１　はＢ１に接続され（
ｉ＝０．１．−−−３０）且つＴ３０　もＢ３１　に接
続される。

アドレス入力端子にはシフトレジスタＳの最初の５個の
シフトレジスタ段の出力が供給され、従って８１　はＡ
ｒ　に接続され（ｉ＝０．　Ｌ　２．３．４）、その結
果ｑ個の出力がシストレジスタＳから得られるようにな
る。

作動に当たり、２つのシフトレジスタＳおよびＴを同時
にクロック作動させる。シフトレジスタＴに保持される
擬似ランダムバイナリシーケンスの３１ビツトを選択回
路Ｍのデータ入力端子に供給する。これらビットの１個
を任意瞬時に出力として選択する。この選択したビット
はシストレジスタＳの最初の５個のシフトレジスタ段の
内容によって決まる。これがためシフトレジスタＴの内
容が既知であっても出力の数を予知するのは困難となる
。

シフトレジスタに含まれるシフトレジスタ段の総数はｑ
−ビットアドレスおよびｐデータビットのみを得るため
に必要とされるシフトレジスタ段の数よりも多く、６０
とする。シフトレジスタ段の総数をｒとすると、次式が
成立する。

ｒ＞ｐ＋ｑ これらシフトレジスタ段の出力が選択回路Ｍに供給され
ない場合に多数の“未使用”シフトレジスタ段を設ける
必要があり、且つこの数をアドレスビットの数に比べて
大きくする必要があることば明らかである。従って次式
が成立する。

ｒ≧ｐ　＋ｑ２ これら未使用シストレジスタ段を設けることによってア
ドレスワードの非予知性を増大し、従ってシフトレジス
タＴの内容が既知である場合でも擬似ランダムバイナリ
シーケンス発生器の出力を予知し得なくすることができ
る。

又、シストレジスタに使用する論理ゲートＧの数を大き
く、本例では２２とするのは明らかである。

上述したように、これら論理ゲートは各々の場合に最大
長さのシーケンスが得られるように選定する。しかし、
この目的のみのためにががる多数のゲートを必ずしも使
用する必要はない。

しかるに、論理ゲートの数を多くすればする程シフトレ
ジスタの内容を予知するのが一層困難となる。その理由
は所定のシーケンスがシフトレジスタの始端から終端に
簡単に位相されず、多数の箇所で変化し得るからである
。

これがためかかる論理ゲートの数を最小でＳとすると、
次式が得られ、これによりシフトレジスタ段の総数に対
する非予知性の程度を高めることができる。

２５　≧ｒ２ シフトレジスタ段の総数を６０とする場合には最小で１
２個の論理ゲートを設ける必要があり、この場合その各
シフトレジスタに対する最小数はシフトレジスタ段の数
にほぼ比例させるのが好適である。

通常Ｓの値はｒ／２よりも小さくする。

図面から明らかなようにスイッチＳｔ！１１．５ｌｌｉ
２．　Ｓｔ！１３およびＳＷ４を設け、これらスイッチ
によって常規作動 （ラン）状態でシフトレジスタＳおよびＴを中心として
２つの再、循環ループを形成し得るようにする。しかし
これら４個のスイッチは図示の位置からロード位置に切
換えることができ、このロード位置ではシフトレジスタ
Ｓの出力をシフトレジスタＴの入力として供給すると共
に論理ゲー）Ｇの全部にはそのシフトレジスタの出力側
が通常持続されている入力側に零値を供給する。次いで
６０個のシフトレジスタ段の全部を経てクロック作動さ
れるスイッチＳＷＩ　のロード入力端子に６０ビット初
期設定ワードを供給し得るようにする。

この再初期設定作動は被定義キューの受信によりバイナ
リシーケンス発生器の常規作動中正しく行われると共に
第４図につき後に説明するように行われる。これによっ
ても、シフトレジスタの内容が任意瞬時に既知であって
も出力を予知し得ないようにする。

初期設定ワードの受信後バイナリシーケンス発生器をそ
の出力の利用前数サイクルに亘ってクロック作動させる
必要がある。

第２図は第１図の擬似ランダムバイナリシーケンス発生
器の変形例を示す。本例の装置の大部分は第１図に示す
装置と同一であるため、その相違点のみを説明する。

本例でもシフトレジスタＳには２９個のシフトレジスタ
段を設けると共にシフトレジスタＴには３１個のシフト
レジスタ段を設ける。又、論理ゲートを次に示すシフト
レジスタ段の入力側に結合する。

シフトレジスタＳ−シフトレジスタ１１Ｓ２．　Ｓ３．
　Ｓｌ。

Ｓａ　＋　Ｓ　ｌ　ｌ　ｒ　Ｓｌ　６およびＳ２０シフ
トレジスタＴ−シフトレジスタ段Ｔ＋、　Ｔ２．　Ｔ３
゜Ｔ’７１　Ｔｉ４＋　ＴＩ９およびＴ２゜従って本例
では全部で６０個のシフトレジスタ段と、選択回路Ｍの
３２個のデータ入力端子及び５個のアドレス入力端子と
、１４個の論理ゲートとを設ける。

しかし、この場合各シフトレジスタのシフトレジスタ段
の数個をデータおよびアドレス入力端子の各々の数個に
夫々接続する。即ちこの接続を以下のように示す。

Ａ、−３゜ Ａｔ　Ｓｌ Ａ２−Ｔ。

Ａ３−Ｔ。

４−Ｔ２ Ｂｏ−Ｂｙ−３２〜Ｓｓ　（夫々対応）Ｂ８〜Ｔ３１−
Ｔ３〜Ｔ２６（夫々対応）かようにしてシフトレジスタ
の出力と選択回路Ｍの入力とを混合することにより、そ
の状態に関する大部分が既知であるばしいでもバイナリ
シーケンス発生器き作動を予知するのは極めて困難であ
る。

第３図は本発明擬似ランダムバイナリシーケンス発生器
の更に他の例を示す。本例では第１および２図の２個の
シフトレジスタの代わりに６１個のシフトレジスタ段Ｓ
。−５ａＯを有する単一のシフトレジスタＳを設ける。

また、２５個の論理ゲー）Ｇを次に示すシフトレジスタ
段の入力端に図示のように接続する。

シフトレジスタ段”２１　Ｓ３１　Ｓｌ、Ｓａ、　ｓ、
、　５ｌｏｔＳ１□＋　Ｓ＋ｓ＋Ｓ＋ｓ＋　ｓ、。、　
Ｓ２□＋　Ｓ２４＋　Ｓ２Ｓ＋　Ｓ２Ｓｌ　ｓ３゜。

Ｓ３３・Ｓ３４・Ｓ３７・Ｓ４０・Ｓ４３・Ｓ４４・Ｓ
４Ｓ・Ｓ５４・ＳＳＳおよびＳ６０　　これがため、５
個のアドレスビットＡ０−−−Ａ、はシフトレジスタ段
Ｓ４＋　Ｓ９１５１４１　ＳｌｓおよびＳ２４の出力側
から取出し、且つ３２個のデータビットをシフトレジス
タ段Ｓ２．〜Ｓｈｏの出力側から取出す。かようにして
単一の再循環ループによってマルチプレクサＭのデータ
およびアドレス入力側の双方に出力を供給する。

この場合には６１ビット初期設定ワードによる再初期設
定に２個のスイッチＳＷＩおよびＳＷ２を必要とするの
みである。

第３図に示す擬似ランダムバイナリシーケンス発生器で
も単一の再循環ループを用いてマルチプレクサＭにアド
レスおよびデータ入力ビットを供給し得るようにする。

この技術の従来の例によればかかる発生器は個別の回路
により記載および説明されている。しかし明細書の記載
および請求の範囲は、発生器の多項式を数学的に、又は
論理ステップにより再現して上述した発生器と同様の合
成シーケンスを発生させるコンピュータプログラムの形
態で発明の実行にひちしく適用し得ることは明らかであ
る。

擬似ランダムバイナリシーケンス発生器の出力は、直接
衛星放送信号のような条件付アクセス（即ちサブスクリ
プション）テレビジョン信号の信号成分をスクランブル
するために用いることができる。上述した再初期設定作
動によればビデオ信号をスクランブルするために新たな
コードを１０秒毎に伝送するのが好適であるが、このコ
ードは１０秒の期間中多数回繰返す。その理由は、デコ
ーダをロックする最大時間を１秒より著しく短かくする
必要があるからである。しかし、これは画像情報を同一
シーケンスの繰返しでスクランブルすることを意味する
。これは比較的危険である。その理由はスクランブルさ
れた画像の種々の部分間の相関を行い得るからである。

テレビジョンフレームを計数するためには８−ビットフ
レーム計数ワード（ＦＣＮＴ）を直接衛星放送信号のよ
うなテレビジョン信号と共に伝送する。

この計数は４Ｑｎｓ毎（フレーム毎）に進段させると共
に予定数のフレーム後、例えば２５６　フレーム毎（は
ぼ１０秒）に繰返す。

次いでこのフレーム計数ワード（ＦＣＮＴ）は送信機の
擬似ランダムバイナリシーケンス発生器に入力として供
給し得ると共に受信機のデコーダの関連する発生器に供
給し得るようにする。これがためフレーム計数信号およ
び秘密制御信号の双方を送信機の擬似ランダムバイナリ
シーケンス発生器に各テレビジョンフレームの始端に供
給する。フレーム計数信号の使用によりバイナリシーケ
ンス発生器に及ぼす影響によって同一の制御ワード値の
各ローディング中に異なる出力を発生するようになる。

このことは、画像信号を異なるキーストリームで常時ス
クランブルすることを意味し、これは−層安全である。

更に各シーケンスがテレビジョンフレーム（４０ｎＳ）
毎に発生するためデコーダのビデオ情報へのアクセスを
迅速とすることができる。フレーム計数ワードは適当に
制御ワードと組合せることができる。この場合には簡単
なモジュロ−２加算を行うことができる。

上述した作動を第４図につき以下に説明する。

フレーム計数器１０によってフレーム毎に増加するいわ
ゆる８−ビットワードの形態の出力を発生する。フレー
ム計数器は歩進動作を行う度毎にその出力１０ａを分周
回路１１に供給し、これにより繰返し周期の所要の長さ
に等しい数、本例では２５６で分周を行って１０秒の繰
返し周期を得るようにする。分周回路の出力によって制
御ワード発生器１２をクロツタ動作させ、これにより異
なる長さの制御ワード例えば６０−ビット制御ワードを
発生させるようにする。

フレーム計数器の８−ビット出力を１／２分周反転回路
１４に供給し、ここで８−ビットフレーム計数ワード毎
に交互に補数がとられるようにする。

次いで反転回路１２の出力を、排他的ＯＲゲート１５で
表わされるモジュロ−２加算器に供給し、ここで各フレ
ーム計数ワードを６０−ビット制御ワードより成る１バ
イトにモジュロ−２加算する。これがため、制御ワード
の第１の８−ビットバイトを第１フレーム計数ワードに
モジュロ−２加算し、第２バイトを第２フレーム計数ワ
ードの補数に加算し、第３バイトを第３フレーム計数ワ
ードに加算し、これを最後のバイトまで繰返す。この最
後のバイトは６０−ビット制御ワードに対して４−ビッ
トのみとし、これを第８フレーム計数ワードの補数の最
下位４ビツトに加算する。排他的ＯＲゲート１５の出力
を初期設定入力として擬似ランダムバイナリシーケンス
発生器１６に供給してフレーム計数毎に、即ちフレーム
計数器１０が進段する度毎にこの発生器にロードする。

この発生器１６は上述した発生器の任意のものとし得る
が、第２図に示す発生器とするのが好適である。

従って擬似ランダムバイナリシーケンス発生器の入力側
には２種類の信号、即ち一方の信号（フレーム計数）−
が既知で、他方の信号（制御ロード）が未知であるよう
な信号を供給する。かかる状態では既知の入力と発生器
の出力との双方によっても未知入力を検知することはで
きない。これがため、同一の制御ワードは擬似ランダム
バイナリシーケンス発生器に繰返しロードし得るが、そ
の出力が同一のシーケンスで繰返されるのを防止し、こ
れにより安全性を高め得るようにする。

上述した処理はワード毎に、又は連結して行うことがで
きる。

フレーム計数はこの目的のための好適な周期的シーケン
スであるが、絶対的なシーケンスではない。例えば好適
な計数を日付／時間信号のような関連するデータ信号か
ら取出すｂ）、又はライン計数のような他の計数から得
るか或いはこれら計数の組合せから得ることができる。

【図面の簡単な説明】

第１，２および３図は本発明の実施例である各擬似ラン
ダムバイナリシーケンス発生器の構成を夫々示すブロッ
ク回路図、 第４図は第１．２または３図に示す擬似ランダムバイナ
リシーケンス発生器への入力を変更する回路を示すブロ
ック図である。 Ｍ・・・選択手段　　　　　Ｂ。−８３１・・・データ
入力端子Ａｏ＝Ａａ・・・アドレス入力端子 Ｇ・・・論理ゲート Ｓ、Ｔ・・・再循環シフトレジスタ手段１０・・・フレ
ーム計数器　　１０ａ・・・出力１１・・・分周回路　
　　　　１２・・・制御ワード発生器１４・・・Ａ分周
反転回路　　１５・・・排他的ＯＲゲート１６・・・擬
似ランダムバイナリシーケンス発生器Ｆｌｏ、４

Claims (1)

1. 【特許請求の範囲】 １、ｐ個のデータ入力端子及びｑ個のアドレス入力端子
   （２ｑ≧ｐ）を有しアドレス入力ワードに従ってデータ
   入力ビットの１つを任意瞬時に選択して装置の出力を発
   生する選択手段と、複数の論理ゲートを有する１つの再
   循環ループを含み、該ループの選択したシフトレジスタ
   段の出力を論理的に組合して擬似ランダムシーケンスを
   発生する再循環シフトレジスタ手段とを具える擬似ラン
   ダムバイナリーシーケンス発生器において、前記ループ
   のシフトレジスタ段の数個の出力端子を前記選択手段の
   データ入力端子に接続すると共に同一のループのシフト
   レジスタ段の他の出力端子を選択手段のアドレス入力端
   子に接続する手段を具えるようにしたことを特徴とする
   擬似ランダムバイナリシーケンス発生器。 ２、再循環シフトレジスタ手段は、２つの再循環ループ
   を具え、各ループには前記選択手段のデータ入力端子の
   各々を接続すると共に選択手段のアドレス入力端子の各
   々を接続するようにしたことを特徴とする請求の範囲第
   １項記載の擬似ランダムバイナリシーケンス発生器。 ３、再初期設定ワードをシフトレジスタ手段に正しくロ
   ードする手段を具えることを特徴とする請求の範囲第１
   項又は第２項記載の擬似ランダムバイナリシーケンス発
   生器。 ４、前記ローディング手段は、周期計数ワードを発生す
   る手段と、制御ワードを発生する手段と、前記計数ワー
   ド及び制御ワードを組合わせる手段とを具え、再初期設
   定ワードをシフトレジスタ手段に正しくロードして再初
   期設定ワードをその都度変更するようにしたことを特徴
   とする請求の範囲第３項記載の擬似ランダムバイナリシ
   ーケンス発生器。 ５、組合せ手段は、交互の計数ワードの補数をとる回路
   を具えることを特徴とする請求の範囲第４項記載の擬似
   ランダムバイナリシーケンス発生器。 ６、組合せ手段は、各計数ワードを制御ワードの選択さ
   れたビットに加算するモジュロー２加算手段を具えるこ
   とを特徴とする請求の範囲第４項又は第５項記載の擬似
   ランダムバイナリシーケンス発生器。 ７、発生器の出力側に接続されテレビジョン信号の少な
   くとも１成分を処理する手段を設けたことを特徴とする
   請求の範囲第４項、第５項又は第６項記載の擬似ランダ
   ムバイナリシーケンス発生器。 ８、周期的な計数ワードを順次の連続ビデオフレームの
   計数により形成されたフレーム計数ワードとすることを
   特徴とする請求の範囲第７項記載の擬似ランダムバイナ
   リシーケンス発生器。 ９、再初期設定ワードのローディング後に動作して発生
   器の出力の利用前複数のクロック周期にわたりシフトレ
   ジスタ手段をクロック作動させる手段を更に具えること
   を特徴とする請求の範囲第３項〜第８項の何れかの項記
   載の擬似ランダムバイナリシーケンス発生器。 １０、再循環シフトレジスタ手段を通常の作動状態で２
   つの再循環ループに配列し、作動時のローディング手段
   によって２つのループのシフトレジスタ手段を単一のシ
   フトレジスタに接続するようにしたことを特徴とする請
   求の範囲第３項〜第９項の何れかの項記載の擬似ランダ
   ムバイナリシーケンス発生器。