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

Abstract

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

Description

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ａ、−Ｔ。

八、−Ｔ２ Ｂｏ　＝Ｂｔ−３２〜Ｓｓ　（夫々対応）Ｂ８〜Ｔ３１
−Ｔ３〜Ｔ２６（夫々対応）。

かようにしてシフトレジスタの出力と選択回路Ｍの人力
とを混合することにより、その状態に関する大部分が既
知であるばしいでもバイナリシーケンス発生器き作動を
予知するのは極めて困難である。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

め、同一の制御ワードは擬似ランダムバイナリシーケン
ス発生器に繰返しロードし得るが、その出力が同一のシ
ーケンスで繰返されるのを防止し、これにより安全性を
高め得るようにする。

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

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

【図面の簡単な説明】

第１．２および３図は本発明の実施例である各擬似ラン
ダムバイナリシーケンス発生器の構成を夫々示すブロッ
ク回路図、 第４図は第１．　２または３図に示す擬似ランダムバイ
ナリシーケンス発生器への人力を変更する回路を示すブ
ロック図である。 Ｍ・・・選択手段　　　　　Ｂ。−８３１・・・データ
入力端子Ａｏ−Ａ４・・・アドレス入力端子 Ｇ・・・論理ゲート Ｓ、　Ｔ・・・再循環シフトレジスタ手段１０・・・フ
レーム計数器　　１０ａ・・・出力１１・・・分周回路
　　　　　１２・・・制御ワード発生器１４・・・Ａ分
周反転回路　　１５・・・排他的ＯＲゲート１６・・・
擬似ランダムバイナリシーケンス発生器■出　願　人　
　レタ・フランセ・レプ　　フランス国エフレゼンテ・
パ・ル・ミ　　ュ　ジュエネラニストル・デ・べ・チ ー・チー　（サンドル ナチオナル　デ　エ テイユデ　デ　テレコ ミユニカシオン） ■出　願　人　　インデペンデント・プ　　イギリス国
ロンロードキャスティング　　ロムプトン　ロオーソリ
テイー ■出　願　人　　ザ・マルコニ・コンパ　　イギリス国
ミドニー・リミテッド　　　　スタンモア　ワし） ■出　願　人　　エヌ・ベー・フィリン　　オランダ国
５６２１プス・フルーイランペ　　ヴアウツウエツンフ
アプリケ ■出　願　人　　ザ・プレツシー・コン　　イギリス国
エセパニー・ピーエルシー　　フォード　バイア４− −９２１３１　　イツシーレームリノー　リュデル　レ
クレル　３８−４０ トン　ニスダブリュー３１イーワイ　ブード７０ ルセックス　エイチエイア′４エルワイーレン　レーン
　ザ　グローブ（番地ナベーアー　アイソピーフエン　
フルーネハ１ ツクス　アイジー１４エイキユー　イルカレッジ　レー
ン（番地なし）

Claims (1)

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