ネットワークシステムにおける基本方式

滋賀大学経済学部研究叢書第

2

2

号

ネットワークシステムにおける

基本方式

葛 山 善 基 著

滋賀大学経済学部研究叢書第

2

2

号

ネットワークシステムにおける

基本方式

葛 山 善 基 著

はじめに

本書はネットワークシステムの基本方式の研究についてまとめたものであ る。しかし，これが方式検討のすべての理論であるというものではない。本書 では，わたしがネットワークシステムの開発中に立案した方式に限り，その方 式を立案した理論的背景の違いあるいは方式の適用分野の違いにより分類し， その詳細を記述した。 理論的背景の違いにより分類してみて，コンビュータの理論であるアルゴ リズム，データ構造，オートマトンの考え方を用いて方式の立案が可能である ことが分かつた。また，方式検討においては，同じ条件で従来方式を改良する だけでなく，将来予測される新しい目標を設定することがよい方式を立案する ために重要であることが分かつた。 現在，多くのシステム技術者がコンビュータ産業で活躍しているが，真の 技術者としては，方式の立案能力を身につけてほしいと，思っている。そのため にも，システムを支える方式の立案過程を記述しておくことは重要であるが， システムの多くが企業により開発されることから方式の立案過程は非公開であ ることが多い。また，企業内においても方式を整理するよりは開発が優先され， 資料として残されることが少ない。本書が少しでもシステム技術者の方式検討 に役立てばと願う次第である。また，今後も，システム技術者により方式の分 類や検討のしかたが学問として体系立てられることを希望する。 本書の刊行するにあたり，多くの方々のご指導を賜った。ここに記して深 く謝意を表したい。

私が理論的な研究を行った博士過程において，大阪大学教授(現奈良先端 科学技術大学院大学教授) 嵩 忠雄先生には，研究の指針を与えて頂いた。 また，大阪大学教授 谷口健一先生には，研究の進め方を逐一御指導して頂い た。そして，大阪大学教授都倉信樹先生，藤井護先生，岡山大学教授岡 本卓爾先生には，研究において適切な御指導と御助言を頂いた。 また，私が本叢書に関する方式研究を行なった電電公社および

NTT

時代 において，戸田 巌本部長(現富士通常務取締役).石野福輔所長，三木哲也 所長，河岡 司部長，拝原正人部長，大阪大学教授橋本昭洋先生，奈良先端 科学技術大学院大学教授 鳥居宏次先生には，研究活動において御支援して頂 いた。また，苗村憲司所長(現慶応大学教授).藤田屋二調査役(現日本コム シス部長).伊土誠一部長，山口治男部長には，研究ならびにシステム開発の 進め方に関して逐一御指導と御助言を頂いた。そして. (敬称、省略).北爪吉 肌 細 見 輝 政 ， 田 島 孝 ， 川 野 繁 一 ， 畑 原 浩 人 ， 森 卓 郎 ， 神 宮 司 誠 ， 北 沢 了，郷古公夫，二神伸夫，伊藤実，中西通雄，各氏には本方式検討を共にし て頂いた。 また，滋賀大学教授吉田稔先生，森持豪先生には，本書の刊行を勧 められるとともに絶えず励まして頂いた。 最後になりましたが，本書刊行の機会を与えて下さった滋賀大学経済学部 ならびに日頃温かい目で見守って頂いている経済学部の諸先生方に心からお礼 申し上げます。

199 2

年

11

月 葛 山 善 基

目

次

第1章 序 論 1 第2章 アルゴリズムの考え方を用いた割り込み競合防止方式 8 2. 1 序言 8 (1)研究の経緯 8 (2 )割り込み競合防止方式の目的 1 0 ( 3 )本方式の理論的背景 1 1 2. 2 本方式の基本構成と基本動作 1 1 2. 3 本方式の詳細な説明 1 2 2. 4 図面の簡単な説明 1 6 2. 5 結言 1 9 第3章 アルゴリズムのデータ構造を利用したタブ制御方式 20 3. 1 序言 20 (1)研究の経緯 20 (2 )タブ制御方式の目的 20 (3 )本方式の理論的背景 20 3. 2 本方式の基本構成と基本動作 22 3. 3 本方式の詳細な説明 23 3. 4 図面の簡単な説明 27 3. 5 結言 28

第4章 オートマトンの考え方を用いたデータ圧縮方式 30 4. 1 序言 30 (1)研究の経緯 30 (2 )データ圧縮方式の目的 30 ( 3 )本方式の理論的背景 30 4. 2 本方式の基本構成と基本動作 3 1 4. 3 本方式の詳細な説明 3 1 4. 4 図面の簡単な説明 40 4. 5 結言 46 第5章通信のある基本プロトコル方式 47 5. 1 序言 47 (1)研究の経緯 47 (2 )転送速度および符号種別の検出方式の目的 47 (3 )本検出方式の理論的背景 47 5. 2 本検出方式の基本構成と基本動作 48 5. 3 本検出方式の詳細な説明 4 9 5. 4 図面の簡単な説明 5 1 5. 5 データ伝送速度および符号種別の識別方式 ー ・ 咽 53 5. 6 本識別方式の基本構成と基本動作 53 5. 7 本識別方式の詳細な説明 53 5. 8 図面の簡単な説明 55 5. 9 結言 57

第6章通信の応用分野のプロトコル方式(1) 59 6. 1 序言 5 9 (1)研究の経緯 59 (2 )情報通信方式の目的 5 9 (3 )本方式の理論的背景 59 6. 2 本方式の基本構成と基本動作 6 0 6. 3 本方式の詳細な説明 60 6. 4 図面の簡単な説明 63 6. 5 結言 6 6 第7章通信の応用分野のプロトコル方式 (2) 67 7. 1 序言 6 7 (1)研究の経緯 67 (2 )プロクeラムカウンタ周期方式の目的 6 7 (3 )本方式の理論的背景 6 7 7. 2 本方式の基本構成と基本動作 68 7. 3 本方式の詳細な説明 69 7. 4 図面の簡単な説明 7 2 7. 5 結言 74 第8章 データベースのある検索方式 8. 1 序言 (1)研究の経緯 に U F h U F h d 7 7 7

( 2 )検索結果画面を利用した連続検索方法の目的 76 ( 3 )本方式の理論的背景 一 76 8. 2 本方式の基本構成と基本動作 76 8. 3 本方式の詳細な説明 7 7

8

.

4

図面の簡単な説明 一 。

79

8. 5 結言 83 第9章 データベースと知識工学を利用したアラーム解析方式 84 9. 1 序言 84 (1)研究の経緯 ••••••••• 84 ( 2 )データベースと知識工学を利用したアラーム解析方式の目的 85 (3 )本方式の理論的背景 ー ー 8 5 9. 2 エキスパートシステムの特徴と監視システムでの構成 ー 85 (1)エキスパートシステムの特徴 ー ョーー ー 85 ( 2 )監視システムでの構成 ・0 ・ 86 9. 3 本方式の基本的考え方ー ー 88 9. 4 本方式の設計概念 •••••••• 89 9. 5 マッチング処理の高速化技法 。 92 9. 6 結言 94 第10章 データベースのある設計方式 ・ 0 ・

97

1 O. 1 序言

97

(1)研究の経緯 一 ・ 0 ・

97

(2

)リレーショナル型データベースの本設計方式の目的 9 8

(

3

)本方式の理論的背景 9 8

1

O

.

2

本方式の基本的考え方 9 8

1

o

.

3

諸定義 9 9

1

O

.

4

関数従属の複写

103

1

O

.

4

.

1

複写の定義

103

1

O

.

4

.

2

複写における検索等価の条件

104

1

O

.

4

.

3

複写に伴う変更操作の変換定義

105

1

O

.

4

.

4

複写において不整合がなく等価になる必要十分条件

106

1

O

.

5

関係スキーマの併合

111

1

O

.

5

.

1

併合の定義

111

1

O

.

5

.

2

併合における検索等価の条件

112

1

O

.

5

.

3

併合に伴う変更操作の変換定義

113

1

O

.

5

.

4

併合において不整合がなく等価になる必要十分条件

114

1

O

.

6

適用例

116

1

O

.

7

結言

117

参考文献

118

第

1

章 序

論

日米特許紛争に見られるように方式を立案することが重要になってきてい る。方式とは構成と動作のことであり，新しい方式とは構成と動作に従来にな い特徴があることである。方式立案は一見思い付きのように思われているが方 式に含まれている考え方はソフトウェア(コンビュータを動作させる命令の集 まり)やそれに関連する理論と共通するところがある。本叢書では私が立案し た方式の考え方を述べるとともに，その方式を立案する上で役立つた論文や基 礎となった知識からどのように方式を立案していったかについて述べて行きた い。全体の構成として，立案した方式の理論的背景の違いにより分類し，特に 背景となる理論が特定できない場合については方式の適用分野の違いにより分 類し記述した。 本書で記述する最初の 3つの方式は理論からヒントを得て新しい方式を立 案したものであり. 1つ目はアルゴリズムから. 2つ目はデータ構造. 3つ目 はオートマトンからヒントを得たものである。次の 3つは通信における適用分 野毎のプロトコルに関するものであり，機能および性能に対する目標を設定し 実現する装置等の構造の特徴に着眼点を見付け方式を立案したものである。最 後の3つはデータベースに関するものであり，その内の2つは目標を設定し立 案したものであり，後の

1

つは実際のデータベースからヒントを得たデータベ ース設計方式を示すとともにこの正しさを証明したものである。 アルゴリズム，データ構造，オートマトン(有限状態機械)がなぜ方式立

-1-案に役立つかと言えば.これらがネットワークシステムの方式の構成や動作と よく似ていることとこれらを実現できるだけのマイクロコンビュータ等の

LS

I技術が発達してきたからである。 まず，アルゴリズムと方式との関係について述べる。アルゴリズムは機能 を実現する手順であり，方式は問題を解決する構成と動作を規定する。アルゴ ルズムと方式は一見異なるようであるが，考えるプロセスにおいてはよく似た ところがある。アルゴリズムの手順と言っても通信とか制御においては，手順 を考える時に同時に構成を考える必要がある。また，方式においては，機能を 実現する構成要素だけでなくこの構成で動く動作の手順を考える必要がある。 そのため，方式立案において，アルゴリズムの考え方を用いることがある。 次に，データ構造と方式との関係について述べる。従来，メモリは順番に 番地が付けられ数値計算の値が入れられるものであった。しかし，このメモリ にこのメモリ自身の番地(ポインターとなる)を記憶することにより，メモリ 上に番地(ポインター)のつながりの構造を記憶させることが可能となる。こ の構造をデータ構造と呼んでいる。データ構造は方式における構造と考えるこ とができ，アルゴリズムを設計する時に考えたデータ構造は方式を考える時に 役に立つ。 次に，オートマトンと方式との関係について述べる。オートマトンは最も 簡単な有限状態機械であり，よく知られているものとして自動販売機がある。 販売機はお金が投入されたときその料金を状態として記憶している。方式設計 は構成や動作を考えることであるが，新しい構成や動作を考える時に，オート マトンは方式の追加構成要素として考えやすいものである。しかし，オートマ トンそのものだけでは理論であるため，みんなが利用できる知識にすぎなく， 円 L

新しい方式にはならないが，他の方式とうまく組み合わせるとそれは新しい方 式となる。 次に，通信に関連する 3つの方式とデータベースに関連する 2つの方式を 立案したときの方法であるが，これらは新しい目標を設定し構造の特徴に着眼 し立案したものである。目標設定においては，装置の多様化，パ、ノコンの普及， 利用者の拡大等の世の中の流れを想定しなければならない。また，若眼点を見 付けるためには関連技術についてポイントを押さえた知識が必要である。 最後のデータベースの設計方式は実際に開発されたデータベース設計から ヒントを得て立案したものであり，この設計方式を示すとともにその正しさを 証明した。 次に，各章の記述についてであるが. 2章から 8章までのハードウエア方 式については基本的に，研究の経緯(従来の方式).新しい方式の目的，新し い方式の理論的背景を序言で述べた後，新しい方式の基本構成と基本動作，新 しい方式の詳細(従来方式の詳細も含む).図面の説明，結言のIJ聞に記述して L 、く。また. 9章のソフトウエア方式と 10章のデータベース設計方式とその 理論との記述形式については序言と結言は前章と合わせるようにしたが，他の 節についてはソフトウエア方式やデータベース設計方式とその理論の記述にあ った形式で記述する。この序論においては，研究の経緯，従来の方式，方式の 目的，方式の理論的背景を要約して記述しておく。 まず，最初に割り込み競合防止方式について述べる。本方式は複数の計算 機が

1

つの装置を取り合いする時に起こる競合問題を防止する方式である。

1

つの計算機内の複数プログラムが装置を取り合いする競合の場合は，競合問題 を解決する方法として装置の使用状態を表すフラグを用意し，そのフラグをセ

-3-ット(使用宣言)してから使用する。 2つ以上のプログラムが同時にセットし ないように，計算機に(装置が空いてるかの)テストと(空いていれば使用宣 言する)セッ卜の機能を同時に実行する命令を用意すればよいことがアルゴリ ズムの理論で知られている。しかし，複数のマイクロコンビュータ(マイコン) を接続し，デバイスシェアリングシステムを開発していたときには競合防止を どのように実現するかが問題となった。一般的にはテストとセットの一連の動 作は要求側で行うものであるが，通信の制御権を1命令毎に次のマイコンに移 す複数マイコンのネットワークにおける競合の問題は.

1

連の動作を受信側で 行うことにより解決した。 次にタブ制御方式について述べる。従来の端末のタプ制御方式は機械的に タプ設定位置にピンをセットする考え方でタブキーが押されるとピンの設定を 逐一調べながら移動する方式であったが，本方式では最新のサーボモーターや マイクロコンビュータの機能をうまく利用してタプ制御を高速化することを考 えた。また，この時考えついたアイデアは以前の論文(文字列のパターンマッ チング)で用いたデータ構造からヒントを得た。具体的には.文字列のパター ンマッチングにおいては文字列の記憶方式として次の同一文字の番地を記憶し ておく方式であったが，本タブ制御においては次のタブ位置を記憶してタブキ ーが押されるとサーボモーターに次のタプ位置までの距離を信号で送り一気に カーソルを移動させる方式とした。 次のデータ圧縮方式は

DCNA

仕様を策定するために

1BM

の

SNA

の通 信方式を検討していたときに考え付いたものである。

SNA

の圧縮方式は文字 が符号表の空いているところを有効利用していないことに着目してよく利用す る

13

文字については

4

ビ‘ットコードで表現する方式を提案していた。我々は

-4-この13文字は少なすぎると考え4ビ‘ットで表現できる文字群を複数にする方 式を考えることにした。やり方としては，オートマトンの考え方を取り入れ送 受信する装置相互間で圧縮文字群の種別を表す状態を持たせ，この状態を同期 させながら切り換えることとした。これにより圧縮される文字群が多くなりデ ータ圧縮の効率を向上させることができた。 次に転送速度および符号種別の検出方式とデータ伝送速度および符号種別 の識別方式について述べる。それらは通信網で各種端末を接続する場合に通信 網内で各種端末の符号種別と転送速度を検出する必要があり立案したものであ る。この時に参考になったのが米国のパケット網システムであり，各種転送速 度の AS C 1 1符号端末を収容するために最初に特定文字を転送させていたこ とである。立案した方式ではこれをヒントとするとともに今後は端末の符号種 別も多様化すると予測し，目標として符号種別にも対処できる方式とした。 次の情報通信方式はテレビ会議等で同一画面を遠隔地の複数パソコン上に 効率よく表示できることを目標とし立案したものである。パソコン聞のやり取 りするデータを少なくするため，複数パ、ノコン上に同一アプリケーションプロ グラムを定行させパソコンから入力されたコマンド、やパラメータのみをすべて のパソコンに転送させることに着眼し方式を立案した。 次のプログラムカウンタ一同期方式とはオンラインソフトウェア流通シス テムを検討していたときに立案したものである。このシステムにおいてはソフ トウェア(プログラム)を販売する上で同一プログラムを遠隔地にある同一パ ソコン上で同期させ走行させる必要があった。目標として表示画面がほぼ同期 していればよいとし，着眼点として同期を取る時をパソコンが互いに長いアイ ドリング状態であるキーボードの入力待ちの時とした。これにより，本方式は

-5-同期による遅れを意識させないものとなった。 次の検索結果画面を利用したデータベースの連続検索方式は伝送路網オペ レーションシステムの開発中に立案したものである。伝送路網においては高速 の伝送路を効率よく利用するために低速の回線や伝送路が多重化装置により何 回も束ねられている。このため多重化装置は木構造に接続されている。このデ ータベースを効率よく運用するために，データベース内の多重化装置情報を装 置が接続された順番に指定しながら高速に検索する必要があり，これを目標に 設定した。これを実現するため.いつも多重化装置を2階層表示し，さらに下 位の装置を表示したい場合は現在下位の装置として表示されている装置名をマ ウスで指定することにより，下位の装置を検索するコマンドが送出される方式 とした。 次のデータベースと知識工学を利用したアラーム解析方式では，故障原因 を効率よく解析することを目標に設定した。また，故障した装置から原因アラ ームを送出するだけでなくこの装置を頂点として木構造に接続された多重化装 置からも波及アラームが送出されることに着目して本方式を立案した。具体的 には，本方式では多重化装置接続構成の変化に対応するため，多重化装置接続 構成の情報を知識情報としてデータベースに格納し，アラーム解析においては この構成情報を知識工学における木構造のフレームと考え，このフレームとア ラーム情報を高速にマッチングさせ，原因アラームを見つけ故障原因を解析す る方式を示した。 次にアクセス効率のよいリレーショナル型データベース設計方式について 述べる。従来のリレーショナル型データベースの設計手法では，テーブルが小 さくなりすぎ，関連するデータを参照する場合結合処理に時間がかかり，オン

-6-ライン定型業務に適さないという問題があった。本設計方式では.定型業務で のデータベースへのアクセス内容が固定されていることに着目し，テーブルの 複写や併合を行なってデータアクセス効率を向上させる方式を示した。さらに. 複写や併合を行う方式において不整合が起こらず検索結果が複写や併合の前と 後とで等価になるための必要十分条件を示した。

-7-第

2

章

アルゴルズムの考え方を用いた

割り込み競合防止方式

2

.

1

序 言

(1)研究の経緯 私が最初の特許を出願する2年前の1973年頃から話を進めてし、く。ち ょうどその頃，複数の CPUを持ついわゆるマルチ・コンビュータ・システム が増加していた。それにともないミニコンのネットワークに関する研究も盛ん に行われるようになって来ていた。大阪大学基礎工学部情報工学科には， 2台 のミニコン

PDP-ll/20

とこれらを結ぶインターフェース装置

(DA1

1

)からなる図

2

. 1

(イ)に示すようなデュアルシステムが導入された。こ れらA・B両システムは導入時にはそれそeれディスクオペレーテイングシステ ム (DOS)のもとで独立に動作できるだけで， Aシステムからは高速紙テー プリーダなどを，またBシステムからはラインプリンタなどを使用できなかっ た。そこで既存のDOSを改造して，コンソールを除くすべてのデバイスを両 システムから使えるようなデバイスシェアリングPシステムを開発した「文献 (1)， (2)， (3)J。 この時に問題になったのが両システムからのデバイスの取り合い(競合〉 の問題である。この問題を解決するため，各システムがそれぞれに接続された 装置を管理し，他のシステムが装置を利用したい場合は装置を管理しているシ -8

コンソ- Jレ ライン プリンタ Aシステム

c

p

u

p

d

p

-

1

1

/

2

0

Bシステム ￨コンソール￨ 高速紙テー プリーダ 図2. 1 (イ〉デバイスシェアリングシステム ステムに使用占有(ロック)の依頼を出す方式とした。このロックを実現する 方法は使用状態を示すフラグを用意し，また，そのフラグの状態を(空いてい るか)テストし(空いていれば使用宣言する)セットすることで実現できるが， このとき重要なことはテストとセットを

1

命令で実行することである。もしテ ストとセットが2つの個別の命令の場合は，フラグが空いている状態の時にテ ストした後に割り込みがかかりまた同じフラグをテストすることがあり.この 場合，両方が空いていると判断することになり

1

つの装置を

2

つのシステムが 同時に使用することになる。このことにより，例えば，ラインプリンタに2つ のシステムから交互に出力され出力結果を解読できなくなるという問題が起こ る(図2. 1 (ロ)参照)。 我々が開発したデバイスシェアリングシステムではミニコンにこの(テス

-9-フラクー Aシステム

←

l

空 比

一￨使用中

lt

Br 力 一 出 ト 一 夕 一 一 ン 一 一 ン リ 一 一イプ一 一 -フ 一 力 一 出 一 図

2

. 1

(ロ〉 競 合 の 例 トとセットとの一連の動作を行う)テストアンドセット命令が存在しなかった ため，テストとセットとの2つの命令を実行している聞は割り込みを禁止する 事により競合の問題を解決した。このようにして解決できたのもデバイスの管 理をデバイスが接続されている側で・のみ行ったからである。 (2 )割り込み競合防止方式の目的 次に， 3台以上のミニコンビュータをマイクロコンビュータを介して共通 母親に接続し，共通母線に接続されたデバイス等の資源を有効に利用するシス テムを開発することになった「文献 (4)

J

。このときにも競合が問題になっ た。この時の競合の問題は，共通母親を介してマイクロコンビュータ間で通信 を行うために通信相手バッファを占有する時に他のマイクロコンビュータと競 合することである。本方式の目的はこの競合の問題を解決することである。 n U 4 E A

(3)本方式の理論的背景 この場合も受信マイクロコンビュータ側に使用フラグを用意しそのフラグ をテストアンドセッ卜すればよいわけであるが，共通母線の使用権もアービ夕 方式で1命令毎マイクロコンビュータ闘を移動させる方式としていた。このた め，受信マイクロコンビュータ側にフラグを用意するだけでは. 1つの受信マ イクロコンビュータ

C

に

2

つの発信マイクロコンビュータ

A

. B

から使用権の テストアンドセットが(1) Aから Cへのテスト (2) Bから Cへのテスト (3) AからCへのセット (4) BからCへのセット，というように. A. B がCとの通信において図2. 1 (ロ)で示したような競合を起こしてしまうこ とになる。このときは占有したL、バッファが自分のメモリ上になく，ましてや マイクロコンビュータには相手マイクロコンビュータへのテストアンドセット 命令など用意されていなかった。 本方式のアイデアは発信側がテストとセットとをするのではなく，発信側 はデータを転送するのみで受信側でテストアンドセットし結果を発信側に返し てやることである。本方式では，発信マイクロコンビュータ上に共通母線の使 用権があるときに受信側で一連のテストアンドセットを行うため，発信側でテ ストとセットとを個別にした時に起こる競合の問題は避けることができた。

2

.

2

本方式の基本構成と基本動作「文献

(5)

J

本方式は単一バス構造のコンビュータ複数台を，各単一パスに設けられた 接続用コンビュータにより，共通ノ〈スに接続したコンビュータ複合体において， 共通パス上に設けられた選択手段によりマスタ権を得た接続用コンビュータが，

-11-他接続用コンビュータにデータ転送するときに起こる割り込み競合をハードウ ェア的に防止するものである。その基本構成は各接続用コンビュータに設けた 割り込みデータレジスタ，セマホフリップフロップ，割り込み確認フリップフ ロップ，その他制御ゲートで構成される。また，その基本動作は前記選択手段 でマスタ権を得た接続用コンビュータが，受信側の接続用コンビュータのアド レス，データを共通パス上に発信し.受信コンビュータではその制御ゲートに よりアドレスを翻訳し，自分の状態をフリップフロップを用いて発信側に知ら せる。すなわち，本方式ではセマホフリップフロップが閉塞状態のときは割り 込み不可能なことを知らせ，セマホフリップフロップが空状態のときは，セマ ホフリップフロップを反転させて他からの割り込みを防止したのち.割り込み が成功したことを発信側コンビュータに知らせるとともに.発信側コンビュー タより送られてきたデータを前記レジスタに格納する。また，これら一連の動 作を発信側コンビュータがマスタ権を得ている聞にハードウェア的に行う。

2

.

3

本方式の詳細な説明

本方式は，コンビュータ複合体において，共通パス上で‘マスタ権を持った 接続用マイクロコンビュータが，他の接続用マイクロコンビュータにデータ転 送を行う時に起こる割り込み競合(すなわち，あるマイクロコンビュータが他 のマイクロコンビュータにより割り込まれて，その一連の処理が完了する前に 別のマイクロコンビュータに割り込まれた時の割り込み)を防止するもので， 各マイクロコンビュータに設けられた割り込みデータレジスタ，セマホフリッ プフロップ，割り込み確認フリップフロップ，制御ゲートなどより構成される。 内 4 4 E A

実施例の詳細を述べる前に，本方式が適用されたシステムの構成としてミ ニコンビュータ3台，マイクロコンビュータ3台の場合について簡単に述べる。 図2. 1 (ハ)にシステム構成を示すように，本方式が適用されるシステ ムは，単一バス構造のミニコンビュータ 1-

1

.

1-2. 1-3.接続用(マ イクロ)コンビュータ 1-4.1-5.1-6を中心とするもので. 1 -

1

.

1-2.1-3が単一パス1-7.1-8.1-9を介して.1-4.1-5. 1-6により共通パス1-1

0

に接続されてシステムが構成される。 前述のように，本システムはリソースシェアを目的としており，各ミニコ ンビュータ 1-

1

.

1-2. 1-3に付属している 1/0群1-1

1

.

1-1 2. 1-13を共有させることをねらっているので，各ミニコンビュータ聞の 割り込み伝達，データ転送などが要求される。 したがってミニコンビュータ一マイクロコンビュータ間.マイクロコンビ ュータ一マイクロコンビュータ間，マイクロコンビューターミニコンビュータ 聞の割り込み伝達，データ転送が必要である。なお1-14はアービタ(選択 手段)で，共通パス上の各接続用コンビュータのマスタ権争奪を制御するもの であり各接続用コンビュータからのパス占有要求(マスタ権獲得要求)を受け て，サイクリックにマスタ権を渡す。具体的に述べると，このアービタはマス タ権をサイクリックに移動させ，マスタ権が回ってきたときに接続用コンビュ ータからの要求があればそのコンビュータにマスタ権を与え，要求がなければ 次の接続用コンビュータにマスタ権を放す。なお，マスタ権を得たコンビュー タは一転送を行ったらマスタ権を放す。また，共通パスに共有メモリを設ける ことにより，各接続用コンビュータのプログラム，データ格納を行い2台のミ ニコンビュータ聞のプロック転送時のバッファとして用いることもできる。

-13-本実施例は，接続用マイクロコンビュータ聞のデータ転送における割り込 み競合防止方式を示す。 図

2

. 2

(イ)のブロック図，図

2

. 2

(ロ)のタイムチャートに基づき その動作を説明する。共通パス1-1 0上のアービタにより，マスタ権を得た

1

台の接続用マイクロコンピュータが，他の接続用マイクロコンビュータにデ ータ転送を行うときを仮定すると，図示はしていないが.マスタ権を得たマイ クロコンビュータが，受信側マイクロコンビュータのアドレス，データ，制御 信号を送出する。 図

2

. 2

(イ〉で

2-1

はアドレスセレクタ，

2

-2

がアドレスドライノ{，

2-3

がデータドライパ，

2

-4

が割り込みデータレジスタ，

2

-

5がメモリ データレジスタ， 2 -6がセマホフリップフロップ内容送出部， 2-7が割り 込み確認フリップフロップである。

2-8

はデータレシーパで-ありアドレスド ライバ

2-2

，データドライパ

2-3

と同様に共通パスと接続用マイクロコン ビュータとの電気的結合に用いられる。 2. 2節で制御ゲートと示したのは，アドレスセレクタなどである。なお セマホフリップフロップは

2-4

に含まれている。また，図

2

. 2

(イ)は受 信マイクロコンビュータに設けられている部分のみを図示したものである。た だし， 2ー7は，図示した部分のマイクロコンビュータが発信側マイクロコン ビュータとなるときに用いられる。アドレスドライノ

¥

2-2

，データドライノ〈

2-3

も同様に用いられる。 受信側マイクロコンビュータは，送られてきたアドレス2-aを2-1に より翻訳し，送られてきたデータ

2-b

を

2-4

にセットするためのクロック

2-d

を発生するが，

2

-4

に含まれているセマホフリップフロップの内容

2

a n -- A

-c

が 0"すなわち閉塞状態のときには. 2 -6により，そのクロックは殺 され2-eは"0"で，データは2-4にセットされない。もちろん2-6か らは，さらに，発信側マイクロコンビュータの割り込み確認フリッピフロップ に 0"を送り，割り込みが不成功に終わったことを伝える。なお. 2 -5 は図示したマイクロコンビュータが共通パス上のメモリよりデータを読み込む 時のみに用いられる。 受信側マイクロコンピュータのセマホフリップフロップの内容

2-c

が " 1 "すなわち空状態の時には. 2 -1より送出された2-4へのデータセット 用クロック 2-dが2-6より 2-eとして発信側マイクロコンビュータに送 られて，発信側の割り込み確認フリップフロップをセットし，割り込みが成功 したことを発信側に伝えると同時に. 2 -6より 2-4へデータセットクロッ クとして2-eが入り，このクロックパルスにより送られてきたデータを2

-4

に取り込むとともに，セマホフリップフロップを反転させ，閉塞状態とし て，他からの割り込みを防止する。 発信側マイクロコンビュータは，その割り込み確認フリップフロップの内 容を見ることにより割り込みが成功したかどうかが分かる。なお，閉塞状態か らの脱出は，受信側マイクロコンビュータ2-1 1が2-4よりデータを取り 込むことによりなされる。さらに，詳しく述べると，非同期の2台のマイクロ コンビュータ問でデータ転送を行うために，データを割り込みデータレジスタ に送ることで受信側に割り込みをかけ，割り込み処理ルーチンで前記割り込み データレジスタの内容をマイクロコンビュータに読み込むわけである。 図2. 2 (ロ)は，前述の動作がどのようなタイミングで行われているか を示している。図2. 2 (ロ)で. 2-a. 2-bは発信側マイクロコンピュ P H U 4 E A

ータより送られてきたアドレス，データであり， 2 -cはセマホフリップフロ ップの内容， 2 -dは2-1より送出される2-6へのデータセットクロック， 2-eは2-6より送出される発信側への応答ならびに2-4に実際にデータ をセットするクロックである。 2-eで2-4にデータを取り込むとともにマ イクロコンビュータへ割り込みをかける。 なお，発信側の割り込み確認フリップフロップへは2-eが入力として入 机別途受信側マイクロコンビュータより送出される制御信号により作られた クロックが供給される。

2. 4

図面の簡単な説明

本方式において，図2. 1 (ハ〉は，本方式が適用されるシステムの構成 1・4 1・7 1・11 1・1 1-5 1・8 1・12 一ニン一

一

ζ

コ 一

1・2 1・10 1・9 1-14 1・13 図 2. 1 (ハ〉 本 方 式 が 適 用 さ れ る シ ス テ ム の 構 成 図 1・3 p n u

-クロック 割 り 込 み 確 認 フ リップフロップ

2-7

2-1 0

咽

.

受 信 側 接 続 用 マ イ コ

2-11

ン 〈発信側〉 2-5 2-4

2-3

2-8

2-e

2 - d 本 方 式 の 実 施 例 の プ ロ ッ ク 図 月 t 4EA (イ〉 2

2-1

図

2

.

2-a

アドレス

2-b

_データ 1 ..

2-c

r

態 千

II

閉 塞 状 態

2-d

2 - 4へ の デ ー タ 取 り 込 み 発 信 マ イ コ ン へ の 割 り 込 み 2-4に デ ー タ 取 り 込 み 割 り 込 み 図 2. 2 (ロ〉 本 方 式 の 実 施 例 に 対 す る タ イ ム チ ャ ー ト o o

-を示す図であり，図2. 2 (イ). (ロ)は本方式の実施例に対するブロック 図，タイムチャートであり，割り込み競合防止方式について示す。

2

.

5

結 言

本書で述べた割り込み競合防止方式はアルゴリズムにおけるテストアンド セットの動作を3台以上のコンビュータで接続したネットワークシステムのハ ードウェアで実現し競合の問題を解決した。具体的には，受信コンビュータバ ッファの競合問題をさけるため，受信側でテストアンドセットの一連の動作を 実行し結果を発信側に知らせる方式を立案した。 アルゴリズムは汎用コンビュータで‘機能を実現するときの手順であるため， システム構成が異なる方式においてアルゴリズムを直接利用することはできな い。しかし，構成と動作を変更することによりアルゴリズムを新しい方式で利 用できることがわかった。ネットワークで利用する他のアルゴリズムについて も同じ様なことが言えるであろう。

1

9

第

3

章

アルゴリズムのデータ構造を利用した

タブ制御方式

3

.

1

序 言

(1)研究の経緯 タプ制御方式はDC N A (Dendenkousya Communication NetworkArchitecture) の仮想、端末方式を検討していた時に従来の端末のタプ制御方式の考え方が最新 のサーボモーターの機能をうまく利用していないことに気付き立案したもので ある。また，この時考えついたアイデアは以前の文献(1) (文字列のパター ンマッチング)で用いたデータ構造からヒントを得た構造にある(データ構造 をうまく利用した他のアルゴリズムとしては文献 (2). (3)がある)。 従来のタプ制御方式では移動したい位置にタフフラグをセットしておき， タブキーが押されるとタプ制御装置が1文字毎夕プフラグがセットされている かどうかを確認しながらカーソルを移動させていた。しかし，当時すでにカー ソルの移動はサーボモータにより行われており，移動したい距離を入力すると カーソルを一気に移動する機構があり，またマイクロコンビュータで移動する 距離を簡単に計算できる時代であった。 (2 )タブ制御方式の目的 本方式の目的はタプ制御を高速に行う事である。 (3 )本方式の理論的背景 -20一

このときタブ設定のしかたが問題になる。文字列のパターンマッチングの 文献(1)で用いたデータ構造の考え方をからヒントを得てタプの設定方法を 決めたが，基礎となるパタンマッチングのアルゴリズムとデータ構造を簡単に 述べる。 このアルゴリズムの目的は2つの記号系列と記号聞の入れ替え規則が与え られているときに，できるだけ上手に入れ替えを行って2つの記号系列の最大 共通始系列を求めることである。 (1) 2つの記号系列に対して入れ替え可能な2つの始系列(左端から始 まる文字系列)の最大をそれぞれ求める。 (2 )それらの始系列同士で最大のマッチングを求める。 (3 )残りの物についても同じようにしてL、く。 この手続きで重要となる(1)のために以下のようなデータ構造を考えた。 まず，記号系列を左から順番に番号を付けて列べ，つぎに，同一文字を左から 順番にポインタでつないでおき，最左端の文字はその文字と対にしたポインタ FIRST(文字)でつなげておく(図 3. 1 (イ)参照)。ここで入れ替え可能 (可換)な文字ばかりの始系列の右端の文字であるためには，可換でない文字 FIRST(a) FIRST(c) FIRST(b) 図3. 1 (イ〉 パ タ ー ン マ ッ チ ン ク で 用 い た デ ー タ 構 造 4 E A 内 ' u

がその左にあってはならない。そのため，この右端の文字と可換でないどの文 字についても，その最左端のポインタ値(文字位置)はこの右端の文字の位置 を表す値より大きくなければならない。 この同一文字をつなぎ合わせることが本タプ制御方式においてつぎのタプ 位置をポインタで示すやり方を立案するときにヒントとなった。このポインタ によりいちいち次のタプ位置を確かめることなく一気に次のタプ位置に移動で きるようになった。 タプ制御方式では次のタプ位置をポインタを用いて表しているが，ポイン タ値の持たせ方でいくつかの方式を立案している。さらに，この方式では基本 構成と基本動作の記述に注意してほしい。最初の記述(イ)で基本的な考え方 を示したあと， (ロ)， (ハ)では(イ)の範囲で方式を特定した考え方にな っている。この目的は(イ)が新しい方式でなくても(ロ)あるいは(ハ)が 新しい方式となるようにしたことである。

3

.

2

本方式の基本構成と基本動作「文献

(4)

J

(イ〉本タフ布j御方式はプログラム制御形式をとり，移動体を逐次駆動して データの印字，表示などを行うデータ端末装置に関するものである。その基本 構成として，メモリ部に前記移動体の各位置ごとに番号を付け，各番地に移動 体のその位置に対する次のタプ設定位置を表す値を記憶している。また，本方 式は，基本動作としてタプ制御符号が入力した時，その時の移動体の位置に対 応した番地の内容を前記メモリーから読み出し，その内容に基づいて前記移動 体の移動距離を制御することを特徴とする。

-22-(ロ)本タプ制御方式は前記メモリ部の各番地には，その位置から見た次の タプ設定位置までの距離を記憶しておくことを特徴とする第(イ)項記載の方 式である。 (ハ)本タプ制御方式は.前記メモリ一部の各番地にその位置から見た次の タプ設定位置の番地を記憶しておくことを特徴とする第(イ)項記載の方式で ある。

3

.

3

本方式の詳細な説明

本方式は，プログラム制御形式のシリアルプリンタ・ディスプレイなどの データ端末装置におけるタプ制御方式に関するものである。 図3. 1 (ロ)にプログラム制御形シリアルプリンタの概略構成を示す。 図において， 1 1はプログラムにより各種の処理を行うマイクロコンビュータ からなる主制御部，

1

2

はメモリ部，

1

3

はキャリッジ駆動制御部，

1

4

はキ ャリッジ駆動機構，

1

5

はキャリッジ，

1

0

1

はキャリッジ位置表示レジスタ である。今，入力掠

L1

からタプ制御符号が入力されると，主制御部

11

はメ モリ部12に記録されているタプ設定位置情報を読み出し，キャリッジ15の 現在位置と次のタプ設定位置との差を求め，その値をデータ線L2を通してキ ャリッジ駆動制御部に与える。キャリッジ駆動制御部

13

はキャリッジ駆動機 構を司るもので，主制御部11より上記の値が与えられると，キャリッジ駆動 機構14を制御してその値に比例した距離だけキャリッジ15を移動させる。 ところで，従来は図3. 2に示すようなフォーマットでタプ設定位置情報 がメモリ部

12

に格納されていた。図

3

. 2

において，

2

1

がタブ設定位置情

23-報を記憶している情報を示したもので，この領域はプリンタの

1

行の印字数n

に対応したビット容量を有しており，ピット単位に

1

からnまでの番地が付け られている。ここで，例えばK番地のビットに 1"が記憶されている時. K のキャリッジ位置にタプが設定されていることを表し 0"が記憶されてい る時はタプが設定されていないことを表す。図3. 2は，現代のキャリッジ位 置がKで，キャリッジ位置Ti-，l Ti. Ti+lにタブが設定されている

ことを表している。 キャリッジの現在位置は図3. 1 (ロ〉における主制御部の 11内のキャ リッジ位置表示レジスタ101に示され，そのキャリッジ位置表示レジスタ l

o

1の値は，キャリッジ15か左端にあるとき flJであり.キャリッジ15 が右に

1

つずれる毎に十

1

されるようになっている。今，キャリッジ位置表示 レジスタ101はKを示しているとする。この時，タプ制御符号が入力される と，主制御部11は図3. 2に示されたメモリ領域21のK番地の内容をまず 読み出し，それが"0" の場合はその次のK+l番地の内容を読み出し，以下， 同様に番地を増やしていきながら初めてその内容が 1"となる番地 (Tiと する)を見付ける。 1"が見付かるとそのTiを次のタプ設定位置くKより 右にあるタプ設定位置でKに一番近いもの)とみなし，キャリッジ 15をTi の位置に移動させるために，データ掠 L2を通して値 (Ti -K)をキャリッ ジ駆動制御部13に送出する。 このように，従来のタブ制御方式は，次のタプ設定位置を見付けるために， 各キャリッジ位置に対してそこにタブが設定されているか，逐一，タプ設定位 置が記憶されているメモリ内を調べなければならず，設定位置の間隔が空いて いる時はダイナミックステップ数が増加するという欠点を持っていた。

-24-本方式は.上記の欠点を除去するため，メモリ部にキャリッジなどの移動 体の各位置に対して次のタプ設定位置を表す値を記憶しておき，タプ制御符号 が入力されてきた時，次のタプ設定位置を迅速にしかもタプ設定位置の遠近に 関係なく一定時間で知ることができるタプ制御方式である。 図3. 3は本方式の一実施例であり，メモリ部に記憶されたタブ設定位置 情報のフォーマットを示したものである。図

3

. 3

において，

3

1

および

32

はタプ設定位置情報を記憶させる領域で，それらの各番地がキャリッジの各位 置に対応するものであることは図

3

. 2

の

21

と同じである。図

3

. 2

と異な る点は，図

3

. 3

(1)においては，領域

31

の各番地に，それに対応するキ ャリッジ位置から見た次のタプ設定位置までの距離が記憶され，また，図3.

3 (2)

においては，領域

32

の各番地に，それに対応するキャリッジ位置か ら見た次のタプ設定位置の番地が記憶されていることである。なお，図3. 3 (1)および (2) とも， T i

ーし

T i， T i

+

1にタプが設定されている ことを示している。 本方式を適用した場合の図3. 1 (ロ)の動作は次の通りである。初め， メモリ部12に図3. 3 (1)の形式でタプ設定位置情報が記憶されている場 合について説明する。従来と同様に，入力線L1を通してタブ制御符号が入力 されると，主制御部11はメモリ部12をアクセスし，その時点でのキャリッ ジ位置 (Kとする)に対応する領域 31内の K番地の内容を読み出す。図 3. 3 (1)に示すように，領域31のK番地には現在のキャリッジ位置からその 次のタプ設定位置T iまでの距離 (Ti-K)が記憶されているため，主制御 部は読み出した

K

番地の内容をそのままデータ線

L2

を通してキャリッジ駆動 制御部13に与えればよい。すなわち，タプ制御符号が入力されたときにキャ F h d 円 L

リッジ位置がどこであっても，主制御部11はメモリ部 12を 1回アクセスす るだけでよく，一定の短い時間内でキャリッジ15の移動距離をキャリッジ駆 動制御部13に送出することができる。 次に，メモリ部12に図3. 3 (2)の形式でタプ設定位置情報が記憶さ れている場合について説明する。この場合もタフ制御符号が入力されると，主 制御部11はメモリ部 12をアクセスし，その時点でのキャリッジ位置 Kに対 応する領域32内のK番地の内容を読み出す。この時，領域32のK番地には， 図3. 3 (2)に示すように現在のキャリッジ位置Kからみた次のタプ設定位 置Tiが記憶されている。このため，主制御部 11はメモリ 12から読み出し た内容Tiとキャリッジ位置表示レジスタ 101の内容Kからキャリッジ 15 の移動距離 (Ti-K)を算出し，これをデータ線 L2を通してキャリッジ駆 動制御部13に送出することになる。この場合も，主制御部 11はメモリ部 1 2を1回アクセスするだけでキャリッジ15の移動距離が求められる。 これまで，シリアルプリンターにおけるキャリッジのタプ制御を例にして 本方式を説明してきたが，もちろん，これは単なる一実施例にすぎず，本方式 は水平タプ，垂直タプ，フォームフィードなどのタプ制御のいずれにも適用可 能であり，また，ディスプレイ等の図形端末装置のタプ制御にも適用可能であ ることは言うまでもない。 以上説明したように，本方式は，シリアルプリンタにおけるキャリッジ， その他，移動体の各位置に対して次のタプ設定位置を表す値を記憶しておくこ とにより，タプ制御動作を簡単にしたものである。また，このような制御をプ ログラムで行う場合，タプ制御に要するダイナミックなプログラムステップ数 を少なくすることができ，本方式はタフeの設定間隔の大小によらず一定のステ

-26-ップ数で処理できるという利点がある。

3

.

4

図面の簡単な説明

本方式における図3. 1 (ロ)はプログラム制御形シリアルプリンターの 基本構成図，図3. 2は従来のタプ制御方式の場合のメモリ部に格納されるタ プ設定位置情報を示す図，図3. 3は本方式のタプ制御方式の場合のメモリ部 に格納されるタプ設定位置情報を示す図である。 1 1は主制御部， 1 2はメモリ部， 1 3はキャリッジ駆動制御部， 1 4は キャリッジ駆動機構， 1 5はキャリッジ， 21，3

1

.

32はタプ設定位置情 報格納領域である。

1 1

ド ャ リ ッ ジ 位 置 表 示 レ ジ ス タ 主 制 御 部 図3. 1 (ロ〉 シリアルプリンタの基本構成図 円 t n d

1 2 3

一一一

T

ト

K

Ti Ti+1 n

￨ o

1 0 0 1 0 1 0

イ

ド

1 図3. 2 従 来 の タ プ 設 定 位 置 情 報 一一一Tト K Ti Ti+1 n (1 )

1 3 2

ト

ト

ト

-

-

-

ト

1 一一一Ti-1 K Ti Ti+1 n (2)

￨

ト

ト

ト

ト

ト

ト

+1

斗

卜

3

2

図3. 3 本 方 式 の タ ブ 設 定 位 置 情 報

3

.

5

結 言

本章で述べたタプ制御方式は，タプ制御テーブルを用いタプ制御の高速化 を実現したものである。 従来はタプ設定位置にフラグを立てタプキーが押されるとカーソルを移動 一部一

しながらフラグが立っているか調べていた。本方式ではタプ制御テーブルに次 のタプ位置を記憶させることにより，一気にカーソルを移動させることができ るようになった。このタフ官

l

御テーフソレはパターンマッチングアルゴリズムの データ構造からヒントを得たものである。このように効率よいアルゴリズムの ために考えたデータ構造は新しい方式を立案するときに役立つものである。

-29-第

4

章オートマトンの考え方を用いた

データ圧縮方式

4

.

1

序 言

(1)研究の経緯 当時(1978年ごろ)， 1 B Mが自社の計算機しか接続できないネット ワークアーキテクチャSN A I文献(1)

J

を開発していたことに対抗すべく， 国内

5

社(電電公社，日本電気，目立，富士通，沖電気)では，異機種計算機 ネットワークが実現できるアーキテクチャー (DC N A)の検討を行い仕様の 概要がほぼ決ってきた「文献 (2)

J

。ちょうどそのころ， 1 B MがSNAの アプリケーションプロトコルとしてデータ圧縮方式を発表してきた。我々はこ れに対抗すべくこれよりも優れたデータ圧縮方式を早急に立案し，特許として 出願する必要があった。 1 B Mのデータ圧縮方式とは， EBCDICコード (8ビ‘ットコード〉表の空 いている所を有効に利用し，特定の13文字(圧縮文字)については4ビ‘ット で表現する方式を提案していた。 (2)データ圧縮方式の目的 本方式の目的はよく利用する文字群を複数として圧縮文字の個数の増加を 図ることにより，圧縮効率を向上させることである。

(

3

)本方式の理論的背景 -30

やり方としては.送受信する相互間で圧縮文字群に対応して状態を持たせ， この状態を同期しながら切り換えることにより，データ圧縮する文字群を複数 にし，圧縮文字の個数の増加を図ることである(図4. 1 (イ)参照)。この ように，方式がすぐ立案できたのも，学生時代にオートマトンに関する研究 「文献 (3)， (4)， (5)， (6)Jを行っていたからではなし、かと思う。

4

.

2

本方式の基本構成と基本動作「文献

(7)

J

本方式は変換テーブルを用いてデータの圧縮および復元を行うデータ圧縮 方式であり，連続して出現する確率の大きい文字を任意数毎にまとめた複数の 圧縮文字群にそれぞれ対応して前記変換テーブルを設けることを特徴とする。 その基本構成としては，送信側にその変換テーブルと，転送データの各文字が 前記圧縮文字群の何れの群に属するか否かの判定手段と，前回の転送データの 文字が属している圧縮文字群を記憶する記憶手段と，その記憶手段の内容と前 記判定手段の判定結果とを比較する比較手段とを備える。また，その基本動作 では，同ーの圧縮文字群に属する連続した転送データの最初の文字を圧縮コー ドとせずに送信し，その最初の文字の次の文字から前記変換テーブルにより圧 縮コードとして送信する。一方，受信側の基本構成としては前記変換テーブル と，受信データが圧縮文字群の何れの群に属するか否かの判定手段とを備え， その基本動作ではこの判定手段の判定結果に基づいて前記変換テーブルを用い てデータの復元を行う。

4

.

3

本方式の詳細な説明

内 d

本方式はデータ送受信方式における送受信効率を向上するためにデータを 圧縮して送信するデータ圧縮方式に関するものである。 データを圧縮することにより送信効率を向上するためのデータ圧縮方式と しては既に種々提案されており. 1 B Mの一例について説明する。 図4. 1 (ロ)に示すように，入力データを送信装置11において送信変 換テーブル12を参照して圧縮可能なデータであるか否かを判定し，例えば1 文字8ビ、ットの場合.データ圧縮の対象となる文字(以下圧縮文字と呼ぶ)に ついては，その文字に対応した4ピットのコード(以下圧縮コードと呼ぶ)に 圧縮し，圧縮文字以外の文字は送信変換テーブル

12

に定められている

8

ビ、ツ トのコードに変換して送信する。但し，圧縮文字が奇数個連続する場合は，そ の最後の文字を送信変換テーブル

12

に定められている(上位

4

ピットが.

F

下位

4

ピツトが

O.

か ら c " の )

8

ピットのコードに変換して送信する。 受信装置

13

は，受信変換テーブル

14

を参照して受信データの再生を行 うものであり，上位

4

ピットおよび下位

4

ビットがともに圧縮コードであった ならば，その8ビ‘ットは2つの圧縮文字が圧縮されたものと判断し，上位4ピ ットと下位4ピットとをそれぞれに対応した圧縮文字に変換する。また，上位

4

ビ、ットおよび下位

4

ピットの両方あるいは片方が圧縮コードでない場合は， その8ビ、ットは2つの圧縮文字が圧縮されたものでないと判断してその8ピッ トを受信変換テーブル14を用いて逆変換し復元する。 図4. 2は従来の変換テーブルの一例を示したものであり，圧縮文字はF 行のO列からC列までのも.A. D. E. G. 1. L. N. O. R. S. T.

U

であって，これと対応する圧縮コードは

4

ビット

16

進数の

O.

から

C.

である。圧縮文字以外の文字のコードは変換テーブルの左側に表示されている n d q a

1 6進数を上位4ピット，上側に表示されている16進数を下位4ピットとし て計 8ビットで表される。例えばD行 8列の文字 Bをこの変換テーブルによっ て変換すると8ピットの" D 8" となる。 図4. 3は図4. 2の変換テーブルを用いてデータ圧縮を行った場合の説 明図であり，データを rREQ/MODULE/Jとすると. R. Eは圧縮文 字であるので，それに対応する 4ピットの圧縮コード 9". 3"に変換し，

Q

.

/

.

Mは圧縮文字でないので，それに対応する 2つの 16進数で表した 8 ピットのコード"CD" . " EB" . " DE"に変換し.O. D. U. Lは圧 縮文字であるのでそれに対応する4ピットの圧縮コード 8". 2". C" • " 6" に変換する。次の Eも圧縮文字であるが，前述したように圧縮文 字が奇数個連続した場合の最後の文字であるので8ピットの"F 3"に変換す る。即ち矢印で示すように，各文字が変換され，圧縮コード化された文字が多 いほど，送信データが短くなり，送信効率が向上する。 受信装置では，転送されたデータを 8ピットずつチェックし，上位 4ピ‘ッ トと下位 4ビ、ットの両方が圧縮文字か否かの判定を行って逆変換を行うもので あり，前述の送信データの場合，最初の8ピットの 9". 3" はどちらも 圧縮コードであるので 9"をRに 3"をEにそれぞれ逆変換し:復元する。 次の 8ピットの" C D"は. Dが圧縮コードでないので図 4. 2の変換テープ ルC行D列に対応する文字Qに逆変換する。以下についても同様の処理を行い， 逆変換して文字を復元する。 しかし，このような従来の方式では圧縮文字の個数が制限されているので 十分な圧縮効率を得ることはできなかった。 本方式は，このような欠点を改善したものであり，連続して出現しやすい 官 u q o

文字の群を複数個として圧縮文字の個数の増加を図り，かつ圧縮の対象となる 文字群の切り替えを識別し得るようにして，圧縮効率を向上することを目的と するものである。以下実施例について詳細に説明する。 図4. 4は本方式の実施例の送信装置のフeロック線図であり， 4 1 1は送 信装置， 4 1 2は制御回路， 413，416，422，426，428は信号 線， 4 1 4はバッファ， 4 1 5はアドレスレジスタ， 4 1 7は変換テープルメ モリ， 4 1 8から42，1 425， 427はバッファレジスタ， 423は回線 バッファ， 424は圧縮文字群状態レジスタである。 図4. 5は本方式の実施例の受信装置のフ'ロック線図であり， 4 5 1は受 信装置， 452は制御回路， 453，459は信号鰻， 454は回掠パッファ， 455はバッファレジスタ， 456，458はアドレスレジスタ， 457は圧 縮文字群状態レジスタ， 460 は変換テーブルメモリ， 4 6 1はバッファであ る。 図4. 6は本方式の実施例の変換テーブルメモリの一例を示すものであり， 圧縮文字は英語大文字:空白文字，

A

，

D

，

E

，

G

， !，

L

，

N

，

0

，

R

，

S

，

T

，

U

からなる圧縮文字群1，数字等:空白文字，数字

0

，・・・

9

， *， /からなる圧縮文字群 2，英語小文字:空白文字 a， d， e， g， i， 1， m， 0， r， s， t， Uからなる圧縮文字群3の3つの群に分かれている。 このように圧縮文字群が英語大文字，数字等，英語小文字からなる3つの 群に分かれているので，送信装置41 1が現在どの圧縮文字群を対象としてデ ータ圧縮を行っているかを判定する必要があり，また受信装置451も転送さ れてきた圧縮コードがどの圧縮文字群に属しているかを判断する必要がある。 そこで異なる圧縮群に属する最初の文字は圧縮コード化することなく送信して a q q a

圧縮文字群の識別を可能としている。 バッファ414にセットされた転送データは制御回路412より信号線4 1 3を介して転送信号がバッファ414に加えられることによりバッファ41 4からアドレスレジスタ415に転送データが8ビット即ち1文字分セットさ れる。変換テーブルメモリ 417は制御回路412から信号線416を介した 変換指示信号を受けると，アドレスバッファ415にセットされている転送デ ータを8ピットの変換コードに変換し，バッファレジスタ418に変換コード をセットする。また，それとともに転送データが圧縮文字であるか否かの情報 をバッファレジスタ419にセットし，圧縮文字であればその圧縮文字がどの 圧縮文字群に属しているかの情報をバッファレジスタ420に セ ッ ト し そ の 転送データに対応した4ピットの圧縮コード、をバッファレジスタ421にセッ トする。また，圧縮文字群状態レジスタ424には現在どの圧縮文字群を対象 として送信装置

41

1

がデータ圧縮を行っているかという圧縮文字群情報が記 樟されている。 制御回路412ではバッファレジスタ419の内容を読み込み，アドレス レジスタ415にセットされた転送データが圧縮文字であるか否かを識別し， 圧縮文字でない場合は信号線422を介して転送信号をバッファレジスタ41 8に送りバッファレジスタ418にセットされた8ピットの変換コードを回線 バッファレジスタ423に転送する。また圧縮文字の場合は，バッファレジス タ420の内容と圧縮文字群状態レジスタ424の内容とを比較し，この圧縮 文字が現在データ圧縮の対象となっている圧縮文字群に属しているか否かを判 断する。 この比較結果が不一致の場合は，圧縮文字群状態レジスタ424の内容を

-35-バッファレジスタ420の内容で書き替え，制御回路412は信号線422を 介して転送信号をバッファレジスタ418に送り，バッファレジスタ418に セットされている変換コードを回線バッファ423に転送する。この比較結果 が一致の場合は.信号線422を介してシフト信号をノ〈ッファレジスタ418 に送り，バッファレジスタ418の内容をバッファレジスタ425に移すとと もに信号線426を介してシフト信号をバッファレジスタ421に送り，バッ ファレジスタ42 1にセットされている4ピットの圧縮コードをバッファレジ スタ427に移す。次に制御回路412は信号線413を介してバッファ41 4に次の転送データを 8ビ、ット即ち一文字分セットし，この転送データについ て変換テーブルメモリ 417を用いて前述した処理と同様の処理を行う。 次に

1

文字目が圧縮文字の場合の

2

文字目の処理について以下に示す。 制御回路412でバッファレジスタ419にセットされている内容を読み込み 解読した結果が圧縮文字でない場合は，制御回路412より信号線428を介 してバッファレジスタ425にセットされている8ピットの変換コードを回緯 バッファ423に転送し，次に信号線422を介して転送信号をノ〈ッファレジ スタ418に送りバッファレジスタ418にセットされている8ピットの変換 コード‘を回線バッファ423に転送する。 転送データが圧縮文字である場合には，バッファレジスタ420にセット されている圧縮文字群の種別と圧縮文字群状態レジスタ424にセットされて いる現在データ圧縮の対象としている圧縮文字群の種別と比較する。 この比較結果が一致の場合は，制御回路412より信号線426を介して 転送信号をバッファレジスタ42，1 427に送り，バッファレジスタ42，1 427にセットされている各4ピットの圧縮コードを同時に回線バッファ 42

-36-3に転送する。この比較結果が不一致の場合は，圧縮文字群状態レジスタ 42 4の内容をノ〈ッファレジスタ420の内容で書き換え(状態遷移に対応する)， 制御回路412より信号線428を介して転送信号をバッファレジスタ425 に送り，バッファレジスタ425にセットされている8ビットの変換コードを 回線バッファ423に転送し，信号線422を介して転送信号をバッファレジ スタ418に送り，バッファレジスタ418にセットされている8ピットの変 換コードを回線バッファ423に転送する。なお，回線バッファ 423にセッ トされた転送データは，受信装置の形式あるいは伝送距離等により，適当な方 法で受信装置に伝送される。 前述のように，非圧縮文字は変換テーブルメモリ 417による8ピットの 変換コードとして送信し，圧縮文字は圧縮文字群に属する最初の文字について 8ピットの変換コードとし，それに引き継ぐ同一圧縮文字群に属する文字は4 ピットの圧縮コードとして送信するものである。例えば，図4. 6の変換テー プルを用い，転送データ rDATA*53Jを送信する場合は F2"， 1"， B" ， F1" ，"E6" ， 5"， 3" に変換されることになる。 受信装置においては，受信データが回線パッファ454にセットされ，制 御回路452は信号線453を介して転送信号を回線バッファ454に送り， 回線ノ〈ッファ 454にセットされている受信データを8ピットずつバッファレ ジスタ455にセットする。制御回路452ではバッファレジスタ455にセ ットした受信データの上位4ピット，下位4ビットをチェックし，ともに圧縮 コードであるか否かを判定する。 この判定結果がともに圧縮コードであると，制御回路452はバッファレ ジスタ455に制御信号を送机バッファレジスタ455にセットされた受信 可 t q d