JPH0460381B2 - - Google Patents

Description

【発明の詳細な説明】 〔発明の技術分野〕 本発明は、データ伝送方法及び装置に関し、更
に詳細には、内容誘導トランザクシヨンオーバラ
ツプ多重アクセス通信方法及び装置に関する。な
お内容誘導とはデータ自身の持つ辞書編集的大き
さにしたがうということを意味する。また、上記
辞書編集的に大きい、小さいとは、アルフアベツ
トその他の記号並びに数字等にあらかじめ決めて
おいた順番で大きいか小さいかを意味する。

〔従来技術〕

現在、様々な種類の多重アクセスチヤネル通信
装置があるが、これら装置は、便宜上、２つの種
類すなわち時分割多重アクセス（TDMA）装置
とキヤリヤ検出多重アクセス（CSMA）装置と
に分類されている。たとえば発明者Hopkins他に
よる米国特許第4161786号、Lowe、Jr.による米
国特許第4199662号、または、White他による米
国特許第4199661号に記載されたような時分割多
重アクセス装置では、伝送チヤネルの容量は、時
間スロツトに分割され、この間に、指定された送
信器は通信ネツトワークで情報を伝送することが
できる。各送信器は、その情報を送信する機会を
有するように、特定の時間スロツトを割り当てら
れている。発明者Eswaran他による米国特許第
4292623号、発明者Herzogによる米国特許第
4199663号、または発明者Spracklen他による米
国特許第4337465号に示すようなキヤリヤ検出多
重アクセス装置では、各送信器は、通信チヤネル
が動作していない時を検出し、所定の期間後に、
その情報を送信する。通常、ウエイテイング期間
は、送信器の割当優先順位により決まる。各送信
器の優先順位は固定していてもよいが、発明者
Burke他による米国特許第4232294号では、各送
信器の優先順位は循環しているので各送信器は所
定の時には最高位の送信優先順位を有している。
衝突が生じた場合、すなわち、２つの異なる送信
器が同時に送信しようとする場合、送信器は送信
を中止し、それぞれの遅延時間だけ待つた後、チ
ヤネルに送信する。送信がうまく開始した場合、
送信器は通信が終了するまで情報を送信する。発
明者Hopkins他による米国特許は、時分割多重ア
クセス装置及びキヤリヤ検出多重アクセス装置を
内蔵した交互デユアルモード通信装置を開示して
いる。

1980年10月発行の「オートメーシヨン及びリモ
ートコントロール」のVol.41，No.10，Part2.
P1463〜1469に記載の、T.N.Zakharova，V.S.
Podlazov及びG.G.Stetsyuraによる“共通チヤネ
ルへの分散優先順位アクセス用高速アルゴリズ
ム”は、チヤネルアクセス問題を解決する優れた
アルゴリズムを示している。このアルゴリズムで
は、各送信器は、優先順位コードを割当てられて
おり、チヤネルがアイドルになつた時送信される
予定の情報を有する全送信器は、１ジエネレーシ
ヨンを構成している。従つて、優先順位コードは
通信チヤネルに送られる。各ジエネレーシヨンの
送信器は、優先順位により選択され、これらは、
減少していく優先順位の順位でチヤネルに対して
アクセスできる。この方法を用いれば、ジエネレ
ーシヨンの各送信器は、次のシンクロポーズのジ
エネレーシヨン及び次のジエネレーシヨンの発生
前に、チヤネルに対してアクセスできる。この方
法は、各ジエネレーシヨンにおいて送信が同時に
行なわれることを阻止し、そのジエネレーシヨン
における各送信器がその優先順位に無関係に情報
を送信する機会があるようにしている。

時分割多重アクセス装置に関する問題点は、特
定の送信器が、割当られた時間スロツト間に送信
すべき情報を有していない場合がしばしばあり、
また他の送信器がこれらの割当時間スロツト間の
期間に２つまたはそれ以上のメツセージを生じる
ということである。従つて、いくつかの送信時間
スロツトが無駄になり、一方、共通送信ラインに
対するアクセスを待つている間、他のメツセージ
は遅延する。この問題点は、少ないすなわち適当
なロードなら、キヤリヤ検出多重アクセス装置に
より部分的に克服することができる。しかし、多
重のメツセージ通信量では、共通送信ラインに対
する同時アクセスの確率は、急に上昇し、関係し
た送信器の優先順位の相違を解決するには多大な
時間を費してしまう。

〔発明の概要〕

本発明の内容誘導（コンテント・インデユース
ド・）トランザクシヨン・オーバラツプ通信装置
はこれら問題を解決するものである。

本発明は、複数の送信器から受信器へ単一の通
信チヤネルでデータを伝送する内容誘導トランザ
クシヨン・オーバラツプ通信装置を提供する。各
送信器は、送信されるマルチプルビツトデータワ
ードを記憶するデータレジスタと、データワード
のビツト数を記憶するワードバウンダリレジスタ
と、ビツトポジシヨンレジスタとを有している。
伝送は、各送信器がデータレジスタに記憶された
最上位ビツトを伝送することで開始される。ビツ
トは、チヤネル状態が、伝送されるビツトの論理
合計であるようなオーバラツプ方法でチヤネルに
より伝送される。ゼロビツトを有限信号レベルと
して伝送し、１ビツトをヌル信号レベルとして伝
送するシングル−フエーズ表示を使用すれば、複
合チヤネル状態は０または１である。

続いて、各送信器は、通信チヤネルの状態とそ
れらの伝送ビツトとを比較し、これらが同じであ
るかどうかを決定する。通信チヤネルの状態が伝
送ビツトと同じであると、ワードバウンダリレジ
スタとビツトポジシヨンレジスタをデイクレメン
トする。一方、通信チヤネルの状態がその伝送ビ
ツトと異なる送信器は残りのビツトの伝送を中止
して、通信チヤネルをモニタし、通信チヤネルに
伝送されるごとにワードバウンダリレジスタをデ
イクレメントし続ける。ビツトポジシヨンレジス
タはそのまま保持する。伝送を中止した送信器以
外の送信器は最高位のビツトワードを伝送した
後、次の高位のビツトワードを伝送して同様の動
作を行う。同様に通信チヤネルの状態と伝送ビツ
トとが異なる送信器は伝送を中止し、ビツトポジ
シヨンレジスタをその値のままに保持してワード
バウンダリレジスタをデイクレメントし続ける。
以下同様に繰り返す。ワードバウンダリレジスタ
が零までデイクレメントされて一つの送信器のデ
ータワードの伝送を終了する。

途中で伝送を中止した各送信器は、それらが辞
書編集的に二番目に小さいデータワードを有して
いるか否かを決定するため、各送信器はビツトポ
ジシヨンレジスタの内容によつてビツトコンペテ
イシヨンを行う。ビツトコンペテイシヨンに勝つ
た送信器は残つたデータビツトの伝送を行う。一
方、二番目に小さいデータワードを有しないため
ビツトコンペテイシヨンに負けた送信器は、勝つ
た送信器のデータワードが伝送が終了するまで待
ち、その後残つた送信器同士でビツトコンペテイ
シヨンを再開する。

このサイクルが、全送信器がデータワードの全
ビツトの伝送を終了するまで繰り返される。

本発明の内容誘導トランザクシヨン・オーバラ
ツプ通信装置の利点としては、スループツトが増
加し、安定度も向上する他、情報を重複して送信
することがなく、チヤネルがロツク−アツプする
こともなく、さらにオーバロードからの回復が速
いことが挙げられる。

〔実施例〕

以下、添付の図面に基づいて、本発明について
説明する。

本発明の内容誘導トランザクシヨン・オーバラ
ツプ通信装置は、複数の送信器が共通受信器の単
一通信チヤネルに対して多重アクセスを必要とす
る場合に生ずる多くの問題点を解決する。

第１図は、共通通信チヤネルすなわちバス３０
により受信器２０に情報を伝送する複数の送信器
１０〜１８を有する代表的な装置を示している。
各送信器１０〜１８は、受信器２０が要求した情
報を任意に伝送することができる。送信器１０〜
１８は、センサ、制御装置または他の種類の入力
装置であるか、またはマルチプルコンピユータシ
ステムのマイクロプロセツサまたはフオルト・ト
レラント・コンピユータネツトワークのコンピユ
ータ、またはこれらの組合せである。受信器は、
利用装置、またはマルチプルコンピユータシステ
ムのマスタ、または他の類似装置である。

各送信器１０〜１８は、第２図に示すように、
データレジスタ（DR）３２、ビツトポジシヨン
（BP）レジスタ３４、チヤネルステータス（CS）
レジスタ３６、及びワードバウンダリ（WB）レ
ジスタ３８を有している。データレジスタ３２
は、通信チヤネル３０を介して受信器２０に伝送
されるデータワードを保持している。データワー
ドは、データレジスタ３２から通信チヤネル３０
へシリアルに一度に１ビツトずつシフトされる。
ビツトポジシヨンレジスタ３４は、送信器がチヤ
ネルと同期した後に送信されるデータワードのビ
ツト数（ｒ）をロードされる。これは、送信器が
データビツトを有効に送信する度に減少してい
く。また、これは通信チヤネルに対するアクセス
権を決定する。チヤネルステータス（CS）レジ
スタ３６は、通信チヤネルにおける最終伝送のビ
ツト値を記憶する１ビツトレジスタであり、送信
器の受信器部分として動作する。ワードバウンダ
リ（WB）レジスタ３８は、通信チヤネルにより
送信されたビツト数のトラツクを保持しており、
１ワードを完全に伝送した時を決定するのに使用
される。上記ワードを完全に伝送するまで、ワー
ドバウンダリレジスタ３８は、そのデータ伝送を
継続するよう送信器に信号を送る。

内容誘導トランザクシヨン・オーバラツプ通信
装置は、連想（内容−アドレス可能）メモリ技術
に関して開発されたマルチプルーマツチ解決方法
に基づいている。このマルチプルーマツチ方法の
問題点は、二以上の項目が、入力サーチ基準に対
応する時に連想メモリから項目を選択する点にあ
る。この問題点は、G.G.Stetsyureによる“コン
ピユータメモリ構成の新しい原理”（Doklady
Akademiya Nauk USSR Vol.132，No.６，
PP.1291〜1294）やM.H.Lewinによる“内容−ア
ドレスされたメモリからのオーダされたリスト検
索”（RCA Review PP.215〜229，1962年６月）
における連想処理の初期研究により解決されてい
る。なお、各ビツトのセンスラインがメモリの全
ワードを通り、検知されたビツトが４つの可能状
態のうちの１つの状態にあると仮定し、これに二
進コードを使用すると、これらラインの状態は次
のとおりになる。

“０”−01 選択された全てのワードがこのビツ
ト位置に“０”を有している。

“１”−10 選択された全てのワードがこのビツ
ト位置に“１”を有している。

Ｘ −11 このビツト位置において、いくつかの
ワードが０を有し、いくつかのワードが
１を有している。

Ｚ −00 ワードは選択されていない。

第３図は、３つのビツトタグを有する連想メモ
リにおけるワードの一例を示している。マルチプ
ルマツチアルゴリズムは、これらタグの内容を使
用して、３つのビツト位置を連続的に走査するこ
とにより、各ワードを引き出している。“Ｘ”を
検出する度に、マツチしたワード、すなわちこの
位置において“０”を有するワードのサブセツト
を分離することができる。このように、このアル
ゴリズムはメモリサイズに無関係で、ｍ個のワー
ドを検索するのに2m−１個の読出しサイクルし
か必要としない。

データ通信において、各送信器は、連想メモリ
における１ワードとして処理され、ビツトポジシ
ヨンの順次検出はシリアル伝送となる。また伝送
結果をテストすることによつて、同様に、送信器
のサブセツトを分離できる。“分散優先順位アク
セス”と呼称されている、このような多重アクセ
ス構成については、G.A.Kotyuzhanski，L.B.
Nisnevich及びG.G.Stetsyuraによる“単一チヤ
ネルデータ伝送システムにおける分散優先順位制
御（1971年Teknickeskaya KibevnetikaNo.２）
や、L.B.NisnevichおよびG.G.Stetsyuraによる
“総合伝送システムにおける分散優先順位制御”
1972年Automation and Remote Control Vol
33，No.４，P795〜798、及びT.N.Zakharova，
V.S.Podlazov及びG.G.Stetsyuraによる“共通チ
ヤネルに対する分散優先順位アクセスの高速アル
ゴリズム“1980年10月Automation and Remote
Control Vol.41，No.10，Part2，P1463〜1469に
おいて説明されている。これらにおいては、この
アルゴリズムは、種々の優先順位の送信器間での
チヤネルアクセスのコンテンシヨンを解決する分
散制御を行なうため使用されていた。

本発明の内容誘導トランザクシヨン・オーバラ
ツプ通信装置は、このアルゴリズムを別の方法で
使用している。すなわちこのアルゴリズムを、チ
ヤネルアクセス優先順位の解決のかわりに、デー
タの取得に使用している。この内容誘導トランザ
クシヨン・オーバラツプ通信装置では、集合デー
タワードを同時に伝送している。従つて各データ
ワードの情報内容は、送信中に、オーバラツプし
たトランザクシヨンから徐々に分析される。実際
には送信は、データワード集合を表わすバイナ
リ・トリーの分散プリオーダトラバーサルであ
る。

この技術は、多重アクセスチヤネル通信装置の
いくつかの領域における改良、すなわち遅延を減
少する一方、平均スループツト及び安定度を向上
する。さらに、この技術は、送信制御に対するフ
レキシビリテイを増大するという他の特性も有し
ている。内容誘導トランザクシヨン・オーバラツ
プ通信装置の特徴としては、ユーザの数の変更、
緊急メツセージ用即時優先順位、内容に基づいた
データ選択、二重情報の送信をなくすこと、バー
ストモードにおいてチヤネルロツク−アツプがな
いこと、及びオーバロードからの高速回復等があ
る。

連続データの固有冗長度を説明するため、ｍ個
のｒ−ビツトワードの集合を使用する。この集合
は、その連続表示としてｍ×ｒビツトを必要とし
ている。全可能ｒ−ビツトメツセージのカージナ
リテイは、2^mrである。どのような順列でも、ワ
ードの同じ集合は、データ到着の時間シーケンス
に無関係な受信器に関して同じ情報値を有してい
る。これは、有効な種類のメツセージがｍ！倍小
さいということを意味している。従つて、このよ
うなワードの集合の情報内容（Ｉ）は次のとおり
になる。

＝log〔2^mr／ｍ！〕 (1) この対数の底は２である。

ここでは、識別可能なワードの集合を取り扱つ
ているので、ｍは2^rより大きくはない。ｍの大き
い値としてStirlingの近似式ｍ！＝√2（ｍ／
ｅ）^mを使用すると、次のようになる。

＝mr−mlogm＝mr〔１−（logm）／ｒ〕
(2) 第３図に示すように、５個の３−ビツトタグは
５個の３ビツトワードを表わしている。これら５
個の３ビツトワードをあるシーケンスで表示する
には15ビツトを必要とする。５！すなわち120が
これらワードの異なるオーダリングであるので、
このようなシーケンスの表示は冗長度を含んでい
る。

連続データワードの冗長度を概算するため、第
４図に示したバイナリ・トリー表示について考え
てみる。トリーのブランチを０及び１に分類すれ
ば、ルートから端末ノードまでの通路はワード集
合を示している。順序を考慮しなければ、比較的
少ない付加情報を有するトリーのプリオーダトラ
バーサルにおける一組のブランチを使用して、全
体的なワード集合を得ることができる。第４図に
おいて、トリーは10個のブランチを有し、ブラン
チ４０〜５８は、集合の情報内容が、15ではなく
約10ビツトであることを意味している。

本来、プリオーダトラバーサルは、ワード集合
を表わすバイナリ・トリーを再構成するには不十
分である。プリオーダトラバーサルを一義的にデ
コード可能にするには、ワード間の境界にいくつ
かの情報を加えなければならない。たとえばバイ
ナリ、トリーの分岐点６０〜６４は、プリオーダ
トラバーサルの０及び１との結合ブランチに対し
て、オーバラツプしたＸ状態を使用していること
を示している。これは、連想メモリからの順序正
しい検索の上述アルゴリズムにおける“Ｘ”状態
の使用に相当している。従つて、プリオーダトラ
バーサルのブランチを表わしている“０”及び
“１”は、オーバラツプしたトランザクシヨン記
号“０”，“１”，“Ｘ”に割当てられる。

記号“Ｘ”は、２つの付随ブランチを有するノ
ードを通る時、“０”及び“１”が重なり合つた
結果である。１つの付随ブランチしか持たないノ
ードは、この記号形式において“０”または
“１”に相当する。ワード長が固定している場合、
このようなオーバラツプしたトランザクシヨンが
デコード可能なことを証明することは容易であ
る。なお、オーバラツプしたトランザクシヨン
（Ｑ）の記号数は、バイナリ・トリーにおけるブ
ランチ数より少ない。

トランザクシヨンにおける“Ｘ”（分岐点）の
数は、ｍ−１である。このｍはワードの総数であ
る。これは、２つのブランチを伴つたノードの
数、すなわち“Ｘ”の数と、任意のバイナリ・ト
リーに関する端末ノードの数との間の一般関係を
示している。従つて、バイナリ・トリーのブラン
チ数はＱ＋（ｍ−１）である。連想メモリからｍ
個のワードを抽出するのに必要な読出しサイクル
の数は、“Ｘ”の数とワード数の合計、すなわち
（2_n-1）である。

ｍ個のｒ−ビツトワードの集合の情報内容
（）は、プリオーダトラバーサルにおけるビツ
ト数（Ｑ＋ｍ−１）より大きい。一方、これは、
全情報より少なく、この全情報はQlog3と表わす
ことができる。

Ｑ＋（ｍ−１）＜＜Qlog3 (3) 異なるｒ及びｍパラメータによるランダムワー
ド集合において行なつたシミユレーシヨンの結果
は、Ｑが、式(2)で示されるような“”の近似値
に近いことを表わしている。以下、内容誘導トラ
ンザクシヨン・オーバラツプ通信装置において、
ｒ−ビツトワードのｍ個の集合を伝送するのに必
要なビツトの数“Ａ”は、Ｑの２進デジツトにワ
ードあたりlogrビツトのオーバーヘツドを加えた
ものに等しく、次の式で示される。

Ａ＝Ｑ＋mlogr＝mr〔１−（logｍ／ｒ）／ｒ〕 (4) 式(4)における〔１−logm／ｒ）／ｒ〕は、ｍ
がｒより大きい場合、１より小さい。このような
場合、除去した冗長度が伝送オーバヘツドをオフ
セツトしているので、内容誘導トランザクシヨ
ン・オーバラツプ通信装置は、データ圧縮を行な
う。たとえば、各々16ビツトの64ワードを有して
いる場合、オーバーヘツドフアクタは、〔１−
（log64／16）／16〕＝0.88となる。従つて、この
例では、mrの積よりも12％少ないビツトでデー
タを伝送することができる。

内容誘導トランザクシヨン・オーバラツプ通信
装置の基本動作は、上述した連想メモリにおける
マルチ−マツチ分析に基づいて、各データビツト
をオーバラツプ伝送することである。ビツト伝送
に際して、内容誘導トランザクシヨン・オーバラ
ツプ通信装置は３つの状態を有している。

“０” 全送信器は、ゼロ−ビツトを送信して
いる。

“１” 全送信器は、１−ビツトを送信してい
る。

“Ｘ” いくつかの送信器はゼロ−ビツトを送
信し、いくつかの送信器は１ビツトを送信してい
る。

受信器は、実際には、これら３状態を分類する
必要がない。すなわち、Ｘが受信されると、“０”
と判断されるので、“Ｘ”と“０”と同一である
と認識できる。送信器は、“Ｘ”と“０”を区別
できる。これは、送信器が丁度送信したことを認
識し、かつ現在のチヤネル状態に対する自身のあ
り得る不一致を認めることができるという事実に
よる。従つて、伝送プロセスは、ただ２つの状態
コーデイング、すなわち“０”及び“１”を使用
して構成することができる。

これは、第５図に示すように、ゼロ−ビツト
（“０”）の伝送用パルス及び１−ビツト（“１”）
の伝送用零レベル信号として送信器の情報を表示
することによつて、可能となる。この表示は、有
限値レベル信号として表わされたチヤネル状態
“０”または“Ｘ”及び零レベルとして表わされ
たチヤネル状態“１”となる。この表示における
送信器の数は、重要ではないが、識別可能なメツ
セージの数は2mに制限されている。

送信器が、ゼロビツトを表わす有限値レベル信
号を伝送した場合、通信チヤネルは“０”または
“Ｘ”状態となり、この送信器は伝送を続けるこ
とができる。送信器が１−ビツトを表わす零レベ
ル信号を伝送した場合には、伝送を継続する前に
通信チヤネルの状態を先づ決定しなければならな
い。チヤネル状態が、零信号レベル、すなわち１
ビツトである場合、伝送された１ビツトは、受信
器によりピツクアツプされ、送信器は動作を継続
することができる。しかし、チヤネル状態が、有
限値レベル信号に示されるように“０”ビツトで
あるならば、受信器は伝送されたゼロ信号を受信
せず、送信器は、伝送された１−ビツトが通信チ
ヤネル状態とは異なることを認識する。従つて、
送信器は、通信チヤネル状態が実際は“Ｘ”状態
であることを認識し、少くとも１つの他の送信器
はゼロ−ビツトを送信している。送信器は現在の
ビツト位置を保持し、他の送信を遅延する。この
コーデイングは、伝送集合における辞書編集的最
小ワードを最初に受信器が受信するように伝送を
構成している。

チヤネル状態０，Ｘ，１は情報を運ぶ。バイ−
フエーズインプリメンテーシヨンにおける“Ｚ”
のようなセパレータ記号は、内容誘導トランザク
シヨン・オーバラツプ通信装置のシングル・フエ
ーズにおいては避けているので、特定のプロトコ
ルを導入してワード集合境界を識別しなければな
らない。

次にｎ個の送信器を有する内容誘導トランザク
シヨン・オーバラツプチヤネルについて考える。
送信器の任意数“ｍ”は、データレデイを有し、
かつ通信チヤネルに対する多重アクセスを有して
いる。各送信器は、単一のｒ−ビツトワードを送
信することができる。ｍ個の異なる送信器におけ
るｒ−ビツトワードの集合を“データ・バケツ
ト”と呼称している。アクテイブな“データ・バ
ケツト”においては、他の送信器は通信チヤネル
にすぐ送信できる状態になるが、これら送信器
は、現在のデータ・バケツトの送信が完了するま
で待たなければならない。従つて、待つている送
信器のデータは、次に続く“データ・バケツト”
の一部となる。

単一データ・バケツトの伝送について考える。
データ・バケツトがアクテイブになると、各送信
器のワードバウンダリレジスタ３８とビツトポジ
シヨンレジスタ３４（第２図）には、伝送される
ワードにおけるビツト数を表わす値“ｒ”がロー
ドされる。すると、通信チヤネル３０による伝送
は、ｍ個の各送信器により、高順位のデータビツ
トから同時に行なわれる。これら“０”ビツトの
伝送は、通信チヤネル３０の信号レベルを有限値
まで上昇させる。１ビツトの伝送は、通信チヤネ
ル３０の信号値を変化せず、そのままにしてお
く。各送信器は、この伝送の際に、通信チヤネル
に対してリスンする。送信器が０または１を伝送
し、かつチヤネル状態が伝送ビツトとは異なるこ
とを検知した送信器は、ワードバウンダリレジス
タ３８だけをデイクレメントし、ビツトポジシヨ
ン３４はそのまま保持して待機状態に入り、次の
ビツトを伝送しない。しかし、この送信器は、通
信チヤネルに対するリスンを継続し、かつ他の送
信器により伝送される各ビツトごとにそのワード
バウンダリレジスタ３８をデイクレメントする。

この手順は、上述のように順次送信器が伝送を
やめながら、第１のｒ−ビツトワードの伝送を完
了するまで繰返される。このワードは辞書編集的
には最小のものである。残りのｍ−１個の送信器
は、ゼロまでデイクレメントするこれらのワード
バウンダリレジスタ３８によるワードバウンダリ
の発生を確認する。各送信器のビツトポジシヨン
レジスタの内容は、それぞれが伝送を中止した値
までデイクレメントされた値にとどまつている。
その後残りのｍ−１個の各送信器は、再び伝送を
開始するが、データビツトを伝送しない。その代
りに、送信器は各ビツトポジシヨンレジスタ３４
の上位ビツトを伝送する。この伝送は、データに
関して述べたように正確に行なわれる。しかし、
各送信器が現在のチヤネルに対してリスンする
時、各送信器はこのビツト値をワードバウンダリ
レジスタ３８にシフトする。このビツトポジシヨ
ン伝送は、ビツトポジシヨンレジスタ３４の全ビ
ツトを伝送するまで継続される。なお、“ビツト
コンペテイシヨン”と呼ばれているこの動作が終
ると、ワードバウンダリレジスタにシフトされた
値は、残りの送信器のビツトポジシヨンレジスタ
の辞書編集的に最小値となる。データを伝送する
必要がある送信器は、ビツトポジシヨンレジスタ
とワードバウンダリレジスタを比較する。そし
て、２つが等しい送信器はすぐさまデータレジス
タにおける次のビツトの伝送を開始する。

ビツトコンペテイシヨンで勝つた送信器は、伝
送すべき残りのデータワードにおける最少ビツト
を有する送信器である。ビツトコンペテイシヨン
で勝つのはただ１つの送信器ではあるが、伝送す
べきワードにおける冗長度に関しては、複数の送
信器がビツトコンペテイシヨンに勝つことも可能
である。第４図のプリオーダ・トリー・トランス
バーサルでは、ビツトコンペテイシヨンの勝者
は、トリーの最終分岐点で伝送を終了した単数ま
たは複数の送信器である。データ伝送は、このブ
ランチのトラバースダウンにより再開する。ビツ
トコンペテイシヨンに勝つた送信器は、伝送を終
了した時に送られた“１”を再び伝送することは
ない。これは、受信器２０がこのビツトの値を既
に識別しているという事実によつている。特に、
ビツトコンペテイシヨンに勝つ単一のまたは複数
の送信器が送信すべきビツトをもう一つだけ有し
ているならば、その値は“１”であるため、この
ビツトを送信しない。

データ送信は、ビツトコンペテイシヨンが終了
すると再開する。送信しているか否かのいずれで
も、各送信器は、通信チヤネルのアクテイビイテ
イに関してリスンを行ない、かつ各ビツトが送信
される時ワードバウンダリレジスタをデイクレメ
ントする。ワードバウンダリレジスタ３８がゼロ
値に到達した時、次のワードバウンダリが発生し
かつ“ビツトコンペテイシヨン”を繰返す。

データ伝送とビツトコンペテイシヨンのこのイ
ンタリーブは、全送信器がそのデータワードの伝
送を完了するまで続く。この時点で、全ビツトポ
ジシヨンレジスタ３４はゼロで、送信器はビツト
コンペテイシヨンを行なわない。ｍ個の送信器
は、log（ｒ）＋“サイレンス（無音）”の１ビツト
により現在の“データ・バケツト”の伝送を確認
し、かつ次の“データ・バケツト”の伝送は、任
意の同期パターンの後に開始する。

通信チヤネルとの同期は、送信器がワードバウ
ンダリ及びビツトコンペテイシヨンを識別できる
ことを意味している。送信器がこのように一旦同
期すると、送信器は通信チヤネルへのデータ伝送
を行なえる。送信器が動的に取りつけたりまた取
りはずしたりできるならば、これらは、これらが
そろつた時、これらが自身で同期できなければな
らない。特定の同期記号を使用しない場合、同期
は所定のデータパターンの認識によつてのみ行な
うことができる。このデータパターンは、バケツ
トを伝送する際には発生することができない。こ
のパターンは、データ・バケツトの終了時に通信
チヤネルに現われるlog（ｒ）＋１＋“１”のｒビツ
トである。同期したい送信器は、合図としてこれ
を使用する。

リアルタイム用途に使用する内容誘導トランザ
クシヨン・オーバラツプ通信装置の１つの特徴
に、“アラーム”メツセージを急送するためバケ
ツト伝送に割込む能力がある。“アラーム”が生
じた場合、関連送信器は、次のビツトコンペテイ
シヨンを待つ。その後、この送信器は、コンペテ
イシヨンに勝つゼロ値を有しているビツトポジシ
ヨンレジスタ３４とコンペテイシヨンを行なう。
受信器２０と他の送信器は、特別の場合と認識
し、かつ“アラーム”を発生した送信器がｒ−ビ
ツト・ワードの全部を送信することを期待し、ま
た、“アラーム”を発生した送信器は全ｒ−ビツ
トワードを伝送する。アラーム送信器の伝送が終
了すると、通常のビツトコンペテイシヨンを再開
し、中止していた伝送を開始する。

内容誘導トランザクシヨン・オーバラツプ通信
装置用のアルゴリズムの機能は、カリフオルニア
州・サンタクララのインテルコーポレーシヨン製
の8080Aマイクロプロセツサや他のマイクロコン
ピユータのような適当な記憶及び計算能力または
比較能力を有する、プログラムマイクロプロセツ
サにおいて、使用することができる。しかし、必
要に応じて、市販されている集積回路や個々の電
子素子を使用したハードウエアにおいてもこのア
ルゴリズムを使用することができる。

通信装置において使用するアルゴリズムの詳細
は、擬似コードプログラムのリステイングの形で
以下に示されている。擬似コードは、本発明を特
定のマイクロプロセツサまたは特定の種類のマイ
クロプロセツサに供する予定ではないので、この
擬似コードはプログラムリステイングにおいて使
用され、また擬似コードリステイングは一般に、
異なる種類のコンピユータ及びコンピユータ言語
に対して使用される。従つて、普通の技術を有す
るプログラマでも、提示された擬似コードプログ
ラムリステイングを特定のコンピユータ用の実際
のプログラムリステイングに翻訳することができ
る。さらに、電子回路分野における技術者は、提
示された擬似コードプログラムを市販されている
集積回路や個別部品を使用しているハードウエア
での実施に翻訳することができる。

送信器１０〜１８の擬似コードプログラムは、
以下の表に示されており、第６図はこれに相当
するフローチヤートを示している。

表 送信器 開始 同期を待つ； DR：＝データ値； WB：＝ｒ； BP：＝ｒ； ｉに関して：ｒから１まで実行開始 もしDR〔ｉ〕＝０ ならば チヤネルへ伝送 さもなければ 開始 チヤネルをサイレントに保持； もしCS＝０ ならば ワード終了を待つ； ビツトコンペテイシヨンを実行； エンド； SBPR：＝SBPR−１； WB：＝WB−１ エンド； 第６図のフローチヤートにおいて、送信器プロ
セデユアは、ブロツク７０で示すように、データ
レジスタ３２、ビツトポジシヨンレジスタ３４、
ワードバウンダリレジスタ３８及びインデツクス
レジスタをイニシアライズすることにより開始す
る。インデツクスレジスタは、伝送すべき、デー
タレジスタのデータビツトを示すポインタであ
る。第１判断ブロツク７２は、インデツクス
“ｉ”が１より小さいかどうかを調べる。インデ
ツクス“ｉ”が１より小さいということは、伝送
すべき残つたビツトがもうないことを表わしてい
る。“ｉ”が０の場合、全データが伝送され、プ
ロセデユア終了ブロツク７４に示すように、この
送信器に関するプロセデユアは終了する。

しかし、“ｉ”がゼロではない場合には、プロ
グラムはブロツク７６に進み、伝送すべきデータ
ビツトDR（ｉ）が論理０であるかどうかを調べ
る。もし、そうであるならば、論理ゼロのデータ
ビツトはブロツク７８に示すように伝送され、ビ
ツトポジシヨンレジスタ３４、ワードバウンダリ
レジスタ３８及びインデツクスレジスタはデイク
レメントし、プロセデユアはデータレジスタ３２
の次に高いビツトにインデツクスする。

ブロツク７６において分析されたデータビツト
が論理１であるならば、送信器は、ブロツク８２
に示すようにチヤネルを“サイレント”に保持
し、かつ１ビツトの伝送はチヤネルにおけるゼロ
信号であるので、論理１のデータビツトを伝送し
ない。従つて、プロセデユアは、判断ブロツク８
４で示すように他の送信器がゼロビツトを伝送し
たかどうかを決定するようチヤネル状態（CS）
をチエツクする。他の送信器がゼロビツトを伝送
したならば、プロセデユアはブロツク８６，８８
に示すように“ワード終了を待つ”及び“ビツト
コンペテイシヨン実行”サブルーチンを呼出す。
送信器がブロツク８８で示すビツトコンペテイシ
ヨンで勝つならば、送信器は、ビツトポジシヨン
レジスタ３４とワードバウンダリレジスタ３８を
デイクレメントし、データレジスタ３２の次のビ
ツトを伝送する手順に進む。

送信器のプログラムにおいて呼出されたサブル
ーチン“ワード終了を待つ”及び“ビツトコンペ
テイシヨンの実行”は、表，において示さ
れ、これらのフローチヤートは第７図及び第８図
に示されている。表と、表のフローチヤート
を示す第７図は、サブルーチン“ワード終了を待
つ”の詳細を示し、このサブルーチンは、伝送デ
ータビツトの状態がチヤネルの状態と異なること
を検出した後、各送信器により実行される。

表 ワード終了を待つ； 開始 （WB＞０）で実行 もし、新しいビツトが伝送された ならば WB：＝WB−１ 実行終了； エンド； 第７図に示したフローチヤートにおいて、サブ
ルーチン“ワード終了を待つ”は、ワードバウン
ダリレジスタ３８の内容がブロツク９０で示すよ
うにゼロより大きいかどうかを調べることにより
開始する。もし、そうであるならば、ブロツク９
２で示すように次のクロツクサイクルを待ち、ワ
ードバウンダリレジスタ３８だけをデイクレメン
トする。ワードバウンダリレジスタ３８が０まで
デイクレメントされると、サブルーチンは、プロ
セデユア終了ブロツク９６に示すように、第６図
の送信器プロセデユアに戻る。

表と、表のフローチヤートを示す第８図
は、サブルーチン“ビツトコンペテイシヨンの実
行”の詳細を示している。このサブルーチンは、
データワードの伝送を完了していない全送信器に
より実行される。このサブルーチンは、通信チヤ
ネルに対する最終アクセスを有する送信器がその
全データワードの送信を完了した後に実行され、
かつサブルーチン“ワード終了を待つ”の後に続
く。

表 ビツトコンペテイシヨンの実行； ウオツチ，センテイング：ブール； 開始 ウオツチ：＝真； （ウオツチ）で実行 センデイング：＝真 Ｊに対して：log2（ｒ）＋１から１まで実行 開始 もしBP〔ｊ〕＝０ ならば もし、センデイングならばチヤネルに伝送 そうでないならば チヤネルをサイレントに保持する； もし、CS＝０ ならば センデイング：＝偽 CS（WB）を読み出す； 実行終了； もし、WB＝BP ならば ウオツチ：＝偽 そうでないなら ワード終了を待つ； 実行終了； 第８図に示したサブルーチン“ビツトコンペテ
イシヨンを実行”は、ブロツク９８で示すよう
に、ウオツチ・フラツグを“真”に設定すること
で開始する。サブルーチンは、ブロツク１００で
示すようにウオツチ・フラツグが“真”であるか
どうか及びポインタJ〓を所定の数log2（ｒ）＋１ま
で調べる。ウオツチ・フラツグが“真”であるな
らば、サブルーチンはセンデイングフラツグを、
ブロツク１０２に示すように“真”に設定する。
ウオツチ・フラツグが“偽”であるならば、サブ
ルーチンはプロセデユア終了ブロツク１０４に示
すように終了し、第７図の送信プロセデユアに戻
る。センデイングフラツグを“真”に設定した
後、サブルーチンは、ビツトポジシヨンレジスタ
３４の全ビツトが伝送されたかどうか、すなわち
J〓＝０であるかどうかを判断ブロツク１０６にお
いて調べる。もし、そうでないならば、サブルー
チンは、ブロツク１０８においてビツトポジシヨ
ンレジスタが論理０ビツトであるか否か、またブ
ロツク１１０においてセンデイングフラツグが
“真”であるか否かを調べる。両方とも“真”で
あるならば、サブルーチンはブロツク１１２に示
すように通信チヤネルに０ビツトを伝送する。

ビツトポジシヨンレジスタ３２のビツトが論理
０でないか、またはセンデイングフラツグが
“偽”であるならば、サブルーチンはブロツク１
１４に示すようにチヤネルを“サイレント”に保
持する。続いて、サブルーチンは、ブロツク１１
６において、チヤネル状態レジスタ３６の状態が
論理０であるかどうかを調べる。もし、そうであ
るならば、センデイングフラツグは、ブロツク１
１８に示すように“偽”に設定され、そうでない
ならば、サブルーチンは、サブルーチン“CS
（WB）を読出す”を呼出すブロツク１２０へ直
接進む。このブロツクでは、チヤネル状態をワー
ドバウンダリレジスタ３８に直接的に記録する。
さらに、サブルーチンはブロツク１２２に示すよ
うにワードバウンダリレジスタのポインタをデイ
クレメント（J〓＝J〓−１）し、ビツトポジシヨンレ
ジスタ３４の次のビツトに関してこのルーチンを
繰返す。最終ビツトが、ブロツク１０６において
J〓＝０で示すようにビツトポジシヨンレジスタか
ら読出されると、サブルーチンは、ブロツク１２
４に示すように、ワードバウンダリレジスタ３８
の内容とビツトポジシヨンレジスタ３４の内容と
を比較する。これらが等しい場合、ウオツチ・フ
ラツグは、ブロツク１２６に示すように“偽”に
設定され、サブルーチンは前述したように終了す
る。これらが等しくない場合には、サブルーチン
はブロツク８６に示すようにサブルーチン“ワー
ド終了を待つ”を再び呼び出す。

ビツトポジシヨンレジスタ３４の内容と等しい
ワードバウンダリレジスタ３８の内容に応じてウ
オツチ・フラツグを“偽”に設定することは、送
信器のデータレジスタ３２の残りのビツトが、伝
送されるべく残つた辞書編集的に最小のビツトで
あり、またこれら残りのビツトの伝送を始めるこ
とができることを意味している。

表と第９図に示したこの表のフローチヤート
は、“ビツトコンペテイシヨンを実行する”サブ
ルーチンにおいて行なわれる、サブルーチン“ワ
ードバウンダリレジスタにチヤネル状態を読出す
（CS（WB）を読出す）”の詳細を示している。

表 CSをワードバウンダリレジスタに読出す 開始 論理１ビツト左にシフト（reg）； reg〔１〕：＝CS； エンド； エンド 第９図に示したサブルーチン“チヤネル状態を
ワードバウンダリレジスタに読出す”は、ブロツ
ク１２６に示すようにワードバウンダリレジスタ
のビツトを１ビツトだけシフトし、次にブロツク
１２８に示すようにチヤネルの状態を第１ビツト
位置に読出す。さらにこのサブルーチンは、プロ
セデユア終了ブロツク１３０に示すように第９図
の“ビツトコンペテイシヨンの実行”サブルーチ
ンに戻る。

表は受信器２０の擬似コードプログラムを示
し、第１０図はこのフローチヤートを示してい
る。

表 Ｖ 受信器； DR：ｒビツトレジスタ； WB：log2（ｒ）＋１ビツトレジスタ； CS：１ビツトレジスタ； エンド−オブ−バケツト：ブール； 開始 エンド−オブ−バケツト：＝偽； WB：＝ｒ； 同期を待つ； （エンド−オブ−バケツト）まで実行； （WB＞０）で実行； 開始 CS（DR）読出す WB：＝WB−１ エンド ストア（DR） ｉに対して：＝１からlog2（ｒ）＋１まで実行 CS（WB）読出す； もし、WB＝（全部１） ならば エンド−オブ−バケツト：＝真 そうでなければ 論理WBビツト（DR）右にシフト １ビツト（DR）左へシフト DR〔１〕：＝１ 実行終了； エンド 受信器プロセデユアは、ブロツク１３２により
示すように、受信器のワードバウンダリレジスタ
をイニシアライズし、エンド−オブ−バケツトフ
ラツグを“偽”に設定することにより開始され
る。さらに、受信器は、ブロツク１３４で示すよ
うに同期を待つ。同期信号は、一連の全部１であ
る。これは、現在のバケツトにおける最終データ
ビツトを送信した後、ビツトコンペテイシヨンサ
ブルーチンにおいて送信器により伝送される零レ
ベルである。続いて、プロセデユアは、判断ブロ
ツク１３６に示すように、エンド−オブ−バケツ
トフラツグが偽であるか否かを調べる。もし、そ
うであるならば、プログラムは、判断ブロツク１
３８において、受信器のワードバウンダリレジス
タが空であるか否かを調べる。もし、受信器のワ
ードバウンダリレジスタが空でないならば、チヤ
ネル状態は、受信器のデータレジスタに読出さ
れ、受信器のワードバウンダリレジスタは、ブロ
ツク１４０で示すようにデイクレメントされる。
さらに、プログラムは進行し、受信器のワードバ
ウンダリレジスタの内容を繰り返して分析し、受
信器のワードバウンダリレジスタがゼロまでデイ
クレメントされ、全データワードが受信されるま
で受信器のデータレジスタにチヤネル状態を記憶
する。続いて、受信器は、ブロツク１４２に示す
ように受信器のデータレジスタに読出されたデー
タワードを記憶する。さらに、受信器は、ブロツ
ク１４４で示すように、受信器のワードバウンダ
リレジスタのポインタ“”を１に先ず設定する
ことにより、送信器により行なわれるビツトコン
ペテイシヨンをモニタする。次に、判断ブロツク
１４６で示すように、ビツトコンペテイシヨンが
終了したか否か、すなわち＞log2（ｒ）＋１であ
るか否かを調べる。もし、ビツトコンペテイシヨ
ンがなお継続しているならば、受信器は、ブロツ
ク１４８，１５０に示すように、チヤネル状態を
受信器のワードバウンダリレジスタに読出し、か
つ“”をインクリメントする。ビツトコンペテ
イシヨンが終了した時、すなわち判断ブロツク１
４６において示すように＞log2（ｒ）＋１の場
合、受信器はブロツク１５２に示すように、受信
器のワードバウンダリレジスタの内容が全部１
で、バケツトが終了したかどうかを調べる。も
し、そうであるならば、エンド−オブ−バケツト
フラツグは“真”に設定され、プロセデユアは、
ブロツク１５８で示すように終了する。もし、そ
うでないならば、受信器のデータレジスタの内容
は、ブロツク１５６に示すように、受信器のワー
ドバウンダリレジスタに記憶された数値に相当す
る数のビツトを右にシフトさせる。さらに続い
て、データは１ビツト左にシフトされ、かつブロ
ツク１５７に示すように、レジスタの下位ビツト
を１に設定する。プロセデユアは、上述したよう
に、送信器により伝送された次のデータビツトシ
ーケンスを記録するように戻る。さらに、このプ
ロセデユアは、全送信器がデータワードの送信を
終了するまで繰返され、エンド−オブ−バケツト
コードを、ブロツク１５２において検出する。

なお、本発明はハードウエア装置やここで示し
たような任意プロセデユアに限定されない。また
本発明は、本発明の思想範囲内で、擬似コードリ
ステイングに示されたプロセデユアを改変した
り、またはコーデイング技術を使用することもで
きる。

【図面の簡単な説明】

第１図は多重アクセス通信装置のブロツク図、
第２図は内容誘導トランザクシヨン・オーバラツ
プ通信装置における送信器の構成要素を示したブ
ロツク図、第３図は３−ビツト（ワード）タグの
集合の例を示し、第４図は第３図の３−ビツト
（ワード）タグの集合のバイナリ・トリー表示で
あり、第５図は通信チヤネルに伝送される０ビツ
ト及び１ビツト信号を示し、第６図は送信器の動
作のフローチヤートで、第７図はサブルーチン
「ワード終了を待つ」のフローチヤート、第８図
はサブルーチン「ビツトコンペテイシヨンの実
行」のフローチヤート、第９図はサブルーチン
「チヤネル状態をワードバウンダリレジスタに読
み出す」のフローチヤート、第１０図は受信器の
動作のフローチヤートを示している。 １０，１２，１４，１６，１８……送信器、２
０……受信器、３０……バス、３２……データレ
ジスタ、３４……ビツトポジシヨンレジスタ、３
６……チヤネルステータスレジスタ、３８……ワ
ードバウンダリレジスタ。

Claims (1)

1. 【特許請求の範囲】 １ 送信するデータを表す複数のビツトからなる
   データワードを記憶するデータレジスタと、その
   データワードのビツト数を記憶するワードバウン
   ダリレジスタとビツトポジシヨンレジスタとを少
   なくとも有する複数の送信器から、それぞれの前
   記データレジスタへ記憶されたデータワードを単
   一の通信チヤネルで受信器へデータを伝送する方
   法であつて、 (A) 各送信器が上記通信チヤネルにそれぞれのデ
   ータレジスタの最上位ビツトを送り出し、 (B) 通信チヤネルの状態が送り出したデータのビ
   ツトと同じかどうかを検査し、 (C) 通信チヤネルの状態が送り出したデータのビ
   ツトと同じ送信器は前記データレジスタの次の
   上位ビツトを送り出し、通信チヤネルの状態が
   送り出したデータのビツトの状態と異なる送信
   器はその後の送り出しを中止して待機し、 (D) 全ての送信器の前記ワードバウンダリレジス
   タをデクレメントし、次の上位ビツトを送り出
   す送信器の前記ビツトポジシヨンをデクレメン
   トするとともに、送信を中止した送信器のビツ
   トポジシヨンをそのまま状態に保持させ、 (E) 上記(A)ないし(D)の動作を、一つの送信器が送
   信終了するまで繰り返し、 (F) 前記送信を継続していた送信器のデータを全
   て送信し終わつた後、送信を中止していた全て
   の送信器からビツトポジシヨンレジスタのビツ
   トを順次送り出していずれの送信器のものが辞
   書編集的に最も小さいかを決定するビツトコン
   ペテイシヨンを行い、 (G) 上記ビツトコンペテイシヨンでビツトポジシ
   ヨンレジスタの内容が辞書編集的に最も小さい
   各送信器が上記(A)ないし(E)の動作を行い、 (I) その後さらに上記(F)及び（Ｇ）を繰り返す ことを特徴とするデータ伝送方法。