秋田
大学
大学院理工学研究科研

究

報

第 39 号告Online edition ISSN 2432-4116
Print edition  ISSN 2432-4108

秋田大学大学院理工学研究科

研究報告第号
平成年月目   次

研究報告
色を制御可能な有機ＥＬ照明を用いた空間に関する主観評価実験         

1

１２平均律を用いた一般化調和解析による打楽器音の音高抽出の試み               田中元志  7田中元志，齊藤勝俊

短報

解説
３段 Clos スイッチ網の性能改善に関する研究（その 1）－研究の背景とスコープ－                    

小原 仁，Koloko LABSON

9

原始語の集合と文脈自由言語について                             新屋良磨

15

秋田大学 大学院理工学研究科

編集委員会
数理・電気電子情報学専攻 電気電子工学コース
田 中 元 志（委員長）

命 科 学 専 攻
生 命 科 学 コ ー ス
生




物

質

科

田 村   拓

学

専

攻

材 料 理 工 学 コ ー ス仁 野 章 弘
数 理 ・ 電 気 電 子 情 報 学 専 攻

人 間 情 報 工 学 コ ー ス
システムデザイン工学専攻

創 造 生 産 工 学 コ ー ス

共 同 ラ イ フ サ イ ク ルデ ザ イ ン 工 学 専 攻内 海 富 博髙 橋   護髙 橋   護物 質 科 学 専 攻
応 用 化 学 コ ー ス
数理・電気電子情報学専攻

数 理 科 学 コ ー ス加 藤 貴 宏三 角 樹 弘システムデザイン工学専攻

機 械 工 学 コ ー ス
システムデザイン工学専攻

土 木 環 境 工 学 コ ー ス

附属革新材料研究センター杉 山   渉日 野   智山 田   学

1

秋田大学大学院理工学研究科研究報告，第39号，2018年11月

研究報告



色を制御可能な有機ＥＬ照明を用いた空間に関する主観評価実験田中元志 ，齊藤勝俊

Subjective Evaluation Tests on Comfortableness of Living Space
by Color Controllable OLED Lighting System
Motoshi Tanaka** and Katsutoshi Saito***

Abstract
In order to create a novel comfortable space with a lighting system, a system with color tunable OLED (Organic Light-Emitting Diode) modules was produced, and the effect of color light in a living space was discussed bysubjective evaluation tests. A smart lighting system consisted of the lighting, audio device of forest sound, andaroma diffuser was prepared for experiments at an institution for the aged people. The effect of addition of soundand aroma, color of the lighting, and circadian rhythm light was subjectively evaluated. Results indicated that subjects would feel better by the addition of sound and aroma to the color lighting, and warm colors and green (inte rmediate) colors were preferred.

１．はじめに

空間のデザインにおいて，これから注目される要ヒト（人間）がより快適に過ごせる空間の創造が素として光（照明），音，香りが挙げられる．これら

求められている．これまでは，温度・湿度を調整すを組み合わせることで，快適性をさらに向上させる(1)

ることで空間の快適性が実現されてきた ．また，建ことが期待できる．音や香りの単独の効果について

築技術やインテリアにより空間の質感を向上させては，それぞれ検討されている (9)~(11)．しかし，照明のいる．照明の照度と色温度については，オフィスや

色や，それに音，香りを組み合わせた場合について

店舗内の快適性から検討されている(2),(3)．また，住宅

照明の快適性の検討についても，構築する照度，色のリラックス効果や快適性に関する検討は見当たらない．
本研究では，照明による新しい快適空間の構築を

温度，壁面の色彩，光源面積といった要因から検討(4),(5)．色の効果などについての検討も目的に，有機 EL パネル複数枚を用いたカラー照明装

報告されている ．しかし，省エネルギーで天井に配置を試作し，それを用いた空間の快適性について検が行われている(6)

置する照明器具が多く，快適性を実現するための照討した．本稿では，照明に音と香りを加えた場合，

明機器は少ない．近年，有機 EL（OLED）が着目さ

照明の色を変えた場合，色を時間で変化させた場合れており，それを用いた照明の開発も望まれている．

について行った主観評価実験（それぞれを Exp. I，II，筆者らは，ヒトが快適に暮らすための新しい照明

III）の結果について述べる．なお，全ての実験にお器具および環境構築の検討として，色を制御可能ないて，被験者に実験内容を説明し，同意を得て実験

有機 EL パネル 1 枚からなるポータブル照明を試作し， を行った．
色温度と配置について主観評価実験を行った (7),(8)．夜

就寝前などの「部屋を暗くして過ごす」場合を対象

２．有機 㻱㻸 パネルを用いた照明システム

とした場合では，暖色系の照明が好まれ，高い位置

調光・調色型の有機 EL 照明モジュール（パイオニ

で，床照明から奥に 1 m 程度に配置したときに，「居ア㻌 OLE-D1414G）を複数個用いて，下記のカラー照(7)

心地良さ」の評価値が高かった ．
2018 年 7 月 20 日受理

秋田大学大学院理工学研究科数理・電気電子情報学専
攻，Department of Mathematical Science and ElectricalElectronic-Computer Engineering, Graduate School ofEngineering Science, Akita University
サイカツ建設，Saikatu Inc.

明を試作した．モジュールの発光部（有機 EL パネル）の大きさは 12.3×12.3 cm2 である．Fig.1 に点灯時の写真を示す．
(1) カラー照明 A：パネル 24 枚（Exp. I，III で使用）
(2) カラー照明 B：パネル 6 枚（Exp. II で使用）
無線 LAN を利用し，Web ページ経由で色をコント2

田中元志・齊藤勝俊

(a) Placement of experimental apparatus and subjects(a) OLED lighting A
Fig.1(b) OLED lighting B

Color lightings for the experiments.



ロールできるように構築した．そのサーバとして，
Raspberry Pi3 を用いた．Web ページ上で所望の色（RGB の各値）を指定する仕様である．また，これらの照明では，パネルからの光を和らげるため，前面に障子風のワーロンシート（厚さ 0.2 mm）を配置(b) Picture

した．被験者らの感想から，見る照明の色の印象は

Fig.2

Experimental conditions.

Table 1

Questionnaire in Exp. Ia-Ic.

設定色の印象と若干異なるようである．なお，本照明システムは，あきた快適空間創造コンソーシアムと共同で開発・試作したものである．

条件


３．照明・音・香りによる空間に関する実験スマート照明システム
カラー照明装置 A，森の音を発生する音響機器，

評価課題（質問）

L

照明があると気分はどちらに変化しますか？㻌

L+S

森の音があると気分はどちらに変化しますか？㻌

L+S+A

香りがあると気分はどちらに変化しますか？㻌

アロマ発生器（ディフューザー）からなるスマート
照明システムを構成した．音響機器には，4 個のスピ

Table 2ーカで音空間を演出するハイレゾ音源システム

Five-grade scale.

評価値㻌

KooNe（JVC ケンウッド）(9)を用いた．香りには，ア評価語㻌

プリトリップ製のアロマを用いた．このアロマは，

2

とてもよい㻌

被験者 32 名による主観評価結果を基に，リラックス

1

よい㻌

効果と空気清浄化を意識して，ひば，レモン，ベル

0

変わらない㻌

ガモット，真正ラベンダー，ユーカリ・ラディアータ

-1

わるい㻌

-2

とてもわるい㻌の植物性精油が配合されたものである．
このスマート照明システムを，老人福祉施設のコ
ミニティケア大内（由利本荘市）のオープンスペー

スに設置した (12) ．照明，スピーカ，アロマ発生器，および被験者の配置を Fig.2(a)に示す．(b)は実験時のれに森の音を流した場合（L+S），さらにアロマを焚様子（写真）である．

いた場合（L+S+A）と条件を追加していき，それぞ実験方法

れについて Table 2 に示す 5 段階の評価語から選択さ2016 年 8 月，10 月，2017 年 1 月に各 1 回，計 3 回の主観評価実験を行った（それぞれ Exp. Ia, Ib, Ic）．
(7)

せた．
また，1 月の実験では，照明の色に対する好みも調

カラー照明の色温度を，これまでの実験条件 に合わ査した．森の音と香りがある状態で，水色，曙色なせて 2000 K（暖色）と 6000 K（寒色）とした．被験

ど計 7 色を提示して（カラー照明の色を変えて），好者には，Table 1 に示すように，何も提示しない状態

みの程度を 7 段階（評価値 3：とても好き，0：ふつを基準として，カラー照明を提示した場合（L），そう，-3：とても嫌い）で評価させた．なお，このアン

3

2

2

1

1

MOS

MOS

色を制御可能な有機ＥＬ照明を用いた空間に関する主観評価実験

0
-1
-2

-1

L2 (2000 K)
L6 (6000 K)

L

L+S
Condition

0

L+S+A

-2



(a) Exp. Ia in August (45 subjects)

Age: 10～29
Age: 30～49
Age: 50～79

L2

L2+S

Fig.4

L2+S+A
L6
Condition

L6+S

L6+S+A

Comparison by age in Exp. Ia.

2

2
1

0
-1
-2

MOS

MOS

1

L2
L6

L

0
-1

L+S
Condition

L+S+A

-2

(b) Exp. Ib in October (22 subjects)

Female
Male

L2

Fig.5

2

L2+S

L2+S+A
L6
Condition

L6+S

L6+S+A

Comparison by gender in Exp. Ia.



MOS

1

評価の傾向に大きな違いは見られなかった．分散分

0
-1
-2

析を行った結果，有意な差は得られなかった．しかし，いずれの条件においても，MOS は 0（変わらな

L2
L6

L

い）より大きい値となった．カラー照明のみの場合
L+S
Condition

L+S+A(c) Exp. Ic in January (20 subjects)
Fig.3

MOS (Mean Opinion Score) when adding

forest sound (S) and aroma (A) to color lighting

では，差は得られなかったが，これまでの結果 (7)と同様に，暖色の方が好まれる傾向が確認された．また，
カラー照明に音，香りが加わることで，被験者は気分がよくなる方向に向かうことが示唆される．
被験者数が多い第 1 回の結果について，年代（年齢）と性別による違いを比較した．年代を 3 つ分け(L) in order.


て比較した結果を Fig.4 に示す．年代による大きな違

ケート時のみ，市販のアロマ（エアアロマ arobalance）

いは見られないが，50 代以上（9 名）では香りの効を用いた．

果が小さい傾向が見られた．性別による比較を Fig.5

被験者は 10～80 代の健康な学生，職員，施設利用に示す．男女による大きな違いは見られなかった．

者などであり，第 1 回が 45 名（女性 14 名，男性 31

森の音と香りがある状態で，照明の色を変えて点名），第 2 回が 23 名（女性 2 名，男性 21 名），第 3灯したときの好みについて主観評価させた結果（第 3

回が 23 名（女性 5 名，男性 18 名）であった．

回に実施）を Fig.6 に示す．ばらつきが大きく，多重 評価結果と検討

比較検定では差は見られなかったが，いずれの色に

平均評価値（MOS：Mean Opinion Score）と標準偏おいても MOS は 0 （ふつう）以上であり，よい評価

差を Fig.3 に示す．(a)が第 1 回 (12)，(b)が第 2 回 (12)，となった．鮮緑の MOS が最も大きく，緑系（中間色）(c)が第 3 回の結果であり，L2 は照明の色温度が 2000が好まれる傾向が示唆される．水色の MOS が小さか

K，L6 は 6000 K の場合である．第 2，3 回の被験者

ったが，寒い時期（1 月）の実験であったことが要因

数が第 1 回の約半数（約 2/3 は同じ被験者）であるが，の一つとして考えられる．

4

田中元志・齊藤勝俊

Table 3

3

MOS

2

色名

1
0

-1
-2
-3

Color of OLED lighting in Exp. II.

水色

Fig.6

曙色 玉子色 柿色 鳥子色 鮮緑
Color

桜色



Preference of color lighting with forest

sound and aroma in Exp. Ic.

RGB値

照度 [lx]Mg(marigold)

R：243
G：152
B：20

9.8

Cy
(cyan)

R：0
G：161
B：233

6.8

Sm
(spearmint)

R：121
G：192
B：110

8.2

Vi
(violet)

R：70
G：14
B：68

3.7

Rd
(red)

R：255
G：0
B：0

7.4

Bl
(blue)

R：0
G：0
B：255

4.2

Ol
(olive)

R：114
G：100
B：12

5.0

Dp
(deep pink)

R：255
G：20
B：147

7.7





(a) Front view
Fig.8

Scale for opinion test (questionnaire).



照明の色は，Fig.6 の結果を基に，好きな色と嫌いそうな色を含むように，Table 3 に示す 8 色とした．
表には，各色の RGB 値 (13)と点灯時の床中央での照度を示している．各色について，カラー照明消灯（補(b) Side view
Fig.7

Placement of experimental apparatus and助灯のみ点灯）90 s 間の後に点灯 100 s 間とした．カ
ラー照明消灯時を基準にして，居心地，安らぎ（リsubjects in Exp. II.
ラックス），好みについて，Fig.8 の 7 段階評価スケー

ルを用いて比較評価させた．被験者は健康な男性 15

４．色が異なる照明を用いた空間に関する実験

名（20～38 歳）とした．

実験方法

評価結果と検討

カラー照明の色を変えた場合について主観評価実

平均評価値（MOS）と標準偏差を Fig.9 に示す．(a)験を行った（Exp. II）．秋田大学理工学部 1 号館 331

は居心地よさ，(b)は安らぎ，(c)は照明としての好み

室（シールドルーム）内に，6 畳間の空間を模して被の結果である．すべての評価項目において，MOS は，

験者の回りを高さ 1.82 m の衝立で囲った．Fig.7(a)にスペアミントの場合に最も大きく，赤が最も小さい示すように，カラー照明 B を被験者の正面中央に，結果となった．2 元配置分散分析後に Tukey-Kramer

同じ光源を持つポータブル照明(7)

2 台をその両脇に法による多重比較検定を行った．図中の**および*印配置した．また，Fig.7(b)に示すように，被験者をリは，それぞれ有意確率 p＜0.01 および p＜0.05 を示し

クライニングチェアに座らせ，被験者から奥 1 m のている．赤は情熱的，興奮などの正の印象があるが，両脇の壁に補助灯（光源 LED，進藤電気設計 jiwari

明るく，この実験では負の印象を持たれた可能性が

moonlight）を配置した．補助灯のみ点灯させたとき，考えられる．スペアミントは緑系の色であり，本結

床中央での照度は約 3.5 lx であった．なお，実験中，果からも中間色が好まれる傾向が得られた．ディ－

補助灯を常時点灯させた．

プピンクについては，安らぎにおいて MOS が小さい

5

色を制御可能な有機ＥＬ照明を用いた空間に関する主観評価実験

音（KooNe）とアロマ（アプリトリップ製）も使用し3

た．なお，アロマは，認知機能の向上を意識して (11)，2

昼用はローズマリー・カンファーとレモン，夜用はMOS

1

真正ラベンダーとオレンジ・スイートの精油が配合0された．実験期間を 2018 年 4 月～2018 年 5 月とし，

-1
-2
-3

使用前，使用後（3 週間後，および 5 週間後）に，下

**
Mg

Cy

記の項目についてアンケート調査（Table 2 をベース

Sm Vi Rd Bl Ol
Color of OLED lighting

Dp

対象（被験者）は，認知症自立度Ⅲレベル以上（主治医の意見書による）で，週 3 回以上の通い，かつ(a) Comfortableness

宿泊も利用している男女 5 名（74～88 歳）とした．

3

㻔㻝㻕㻌 使用前のアンケート項目

2

MOS

1
0
-1
**

-2
-3

Mg Cy

（悪い⇔良い）

②普段の寝つきはどうですか？

（悪い⇔良い）

③普段の目覚めはどうですか？

（悪い⇔良い）

④普段はぐっすり眠れていますか？

Sm Vi Rd Bl Ol
Color of OLED lighting（眠れない⇔眠れている）
Dp㻔㻞㻕㻌 使用後のアンケート項目
①現在の体調はどうですか？

（悪い⇔良い）

②寝つきはどうなりましたか？
（悪くなった⇔良くなった）

3③目覚めはどうでしたか？

2



1

MOS

①現在の体調はどうですか？

*(b) Relaxedness（悪くなった⇔良くなった）

④ぐっすり眠れるようになりましたか？

0



-1

（なっていない⇔そうなった）

⑤このライトは？（なくてよい㻌 ⇔あるとよい）

-2-3とした 5 段階の主観評価）を行った．アンケートの

**
Mg

Cy

Sm Vi Rd Bl Ol
Color of OLED lighting⑥このライトがあると？ （不快⇔快適）
Dp(c) LikenessFig.9

MOS of Exp. II.

評価結果と検討
使用効果（アンケート項目①～④）についての平均評価値（MOS）と標準偏差を Fig.10(a)に示す．図中の*印は 2 元配置分散分析後に Tukey-Kramer 法による多重比較検定を行った結果（p<0.05）である．項

結果となり，居心地と好みの傾向と異なった．今回

目②～④については，3 週間後，5 週間後と使用時間の実験では色によって明るさが異なったことから，が長くなるほど MOS が大きくなっている．また，使今後，輝度あるいは照度を統一した検討も必要と考用後のアンケートでは，全ての被験者においてマイえられる．

ナス評価は無かった（0 以上であった）．被験者数が少ないが，ぐっすり眠れるようになってきていると

５．サーカディアンリズム照明を用いた空間の検討

考えられる．使用感（アンケート項目⑤，⑥）につ実験方法

いての結果を図 Fig.10(b)に示す．こちらも，全ての試作したカラー照明の応用として，日の出から日被験者でマイナスの評価は無く，不快には感じなかの入りまでの時間で色温度を連続的に変化（点灯⇒ったようである．これらの結果から，サーカディア

朝日の色⇒晴天の色⇒夕日の色⇒消灯）させるサーンリズムライトに特別な必要性を感じていないが，カディアンリズムライトの利用を提案する．この機

この機能を装備した本スマート照明システムは被験能を，コミニティケア大内のオープンスペースに配者にとってよい方向に作用していることが考えられ置したスマート照明システムのカラー照明 A にインる．今後，被験者を増やした長期的な調査および検ストールして，利用者に体験させた（Exp. III）．森の討が必要である．

6

田中元志・齊藤勝俊

参考文献

2

(1) 江見明彦，米本洋幸（2010）：快適性評価 PMV，知的MOS

1システム研究会 第 113 回月例発表会，1-4 頁.
(2) 福田吉人，柿崎昌子，高見浩志，平川貴大，中島幸市，

0
-1
-2

清水亨，山本剛，錦明範（2009）：世界初全館 LED 照明

使用前
3週間後
5週間後
体調

寝つき 目覚め
評価項目*
眠り(a) Comparison before and after use
2

建屋の感性評価と色温度に対する快適性の考察，ヒューマンインターフェースシンポジウム 2009，2312.
(3)久保千穂，山羽和夫，阿山みよし（2013）：店舗照明を想定した LED 照明の照度と色温度による快適性，照明学
会誌，97 巻，2 号，77-81 頁.
(4)國嶋道子，梁瀬度子（1984）：室内構成材の雰囲気への影響に関する研究(1) ―設計計画的要因について―，人MOS

1間工学，20 巻，6 号，327-334 頁.
(5) 高橋啓介（2006）：照明の色温度と照度とが室内環境評

0価に及ぼす効果，医療福祉研究，2 号，30-36 頁.

-1
-2

3週間後
5週間後
ある・ないとよい
快・不快
評価項目(b) Impression of use
Fig.10

MOS of Exp. III.

(6) Liu, T. C.-Y., Liao, C., and Liu, S. (1995) : Theoretical Research on Color Indirect Effect, Proceedings of SPIE 2393,
Ophthalmic Technologies V; doi: 10.1117/12.209852.
(7) 田中元志，室井一輝，齊藤勝俊，込山敦司（2015）：屋
内用ポータブル照明の色温度と配置に関する一検討，電気学会 a 部門大会，17C-a1-6.
(8) 込山敦司，田中元志，齊藤勝俊（2017）：屋内用ポータ
ブル調色照明の光源色嗜好と配置に関する研究，第 80

６．まとめ
照明による新しい快適空間の構築を目的に，有機回日本建築学会東北支部研究報告会，B-25.
(9) KooNe ホームページ（2018）：http://www.koone.jp/.

EL パネルを用いたカラー照明装置を試作した．そし(10) Choy, P.T., Haddadan, G., Poyton, C.N., Einstein, R., andて，それを用いた空間の快適性について，カラー照Lavidis, N.A. (2006) : Effects of Praescent (plant derived

明の色，音と香りの有無，などの条件を変えて主観

odour) on chronic stress, Proceedings of Australian Physio-

評価実験を行った．その結果，カラー照明に音，香logical Society (Brisbane, Australia), pp.101-102.

りが加わることで，被験者は気分がよくなる方向に(11) 塩田清二（2018）：“【アロマで認知症が改善】昼はロ

向かうこと，暖色や緑系（中間色）の色が好まれる

ーズマリー、夜はラベンダーの香りで脳を刺激したら...”，

傾向が示唆された．また，日の出から日の入りまで

http://www.karadane.jp/articles/entry/news/006840/.

の時間で色温度が変化するサーカディアンリズムラ(12) 齊藤勝俊，室井一輝，松井加奈絵，田中元志（2017）：

イトを提案した．今後，脳波や心電図などの生体信

カラー照明に音と香を加えたときの快適性に関する一検号との関連についても検討していく予定である．

討，第 50 回日本生体医工学会東北支部大会，ME-3-4.
(13) 原色大辞典（2018）：https://www.colordic.org/.

謝辞
被験者として協力頂いた方々，実験に協力頂いた
本学修了生 室井一輝氏，コミュニティケア大内の小笠原孝理事長と職員の方々，ならびにあきた快適空間創造コンソーシアムの関係各位に感謝する．また，
本研究の一部は平成 27 年度および 29 年度あきた企
業応援ファンド事業の助成で行われた．




7

秋田大学大学院理工学研究科研究報告，第39号，2018年11月

短
短報
報



１２平均律を用いた一般化調和解析による打楽器音の音高抽出の試み
１２平均律を用いた一般化調和解析による打楽器音の音高抽出の試み
田中元志
田中元志
 

A PitchExtractionof ofPercussion
Sound
by by
Generalized
Harmonic
Analysis
A PitchExtraction
Percussion
Sound
Generalized
Harmonic
AnalysiswithTwelve-Tone
Equal
Temperament
with
Twelve-Tone
Equal
Temperament** **Motoshi
MotoshiTanakaTanaka

Abstract
Abstract
Humansoften
recognize
someone's
footsteps,
thoughthe thefootstep
soundcontains
many
noise
and andpartialtonetone
Humansoften
recognize
someone's
footsteps,
thoughfootstep
soundcontains
many
noise
partialcomponents.
Also,
the high
and andlowlowof footsteps
can cansometimes
be recognized,
which
indicates
the footsteps
havehavea acomponents.
Also,
the highof footsteps
sometimes
be recognized,
which
indicates
the footsteps
pitch.
It maybe similar
to drum
and andpercussion
sound.
In thispaper,
a pitchextractionof those
percussion
soundspitch.
It maybe similar
to drum
percussion
sound.
In thispaper,
a pitchextractionof those
percussion
soundswaswasdiscussedby GHA(Generalized
Harmonic
Analysis)
withwith
twelve-tone
equal
temperament.
AndAndeacheachpitchpitchof ofdiscussedby GHA(Generalized
Harmonic
Analysis)
twelve-tone
equal
temperament.
the thesound
waswassubjectively
evaluatedby 4bysubjects.
In results,
the thepitchpitch
felt felt
by subjects
waswasincludedin frequency
sound
subjectively
evaluated
4 subjects.
In results,
by subjects
includedin frequency
components
components
extracted
extracted
by theby GHA.
the GHA.

１．はじめに
１．はじめに
ヒトは足音で歩行者を特定できる場合があり，足ヒトは足音で歩行者を特定できる場合があり，足(1) (1)

音に関する検討が行われている
音に関する検討が行われている．歩行者を識別でき．歩行者を識別でき

周波数，𝑇𝑇
周波数，𝑇𝑇= 1/𝑓𝑓，𝑁𝑁= 1/𝑓𝑓，𝑁𝑁≥ 𝑛𝑛𝑛𝑛，𝑛𝑛は整数である．
≥ 𝑛𝑛𝑛𝑛，𝑛𝑛は整数である．

れば，見守りやセキュリティシステムへの応用が期れば，見守りやセキュリティシステムへの応用が期待できる．ヒトが足音を識別する要素の一つとして，待できる．ヒトが足音を識別する要素の一つとして，

2 2𝑛𝑛𝑛𝑛 𝑛𝑛𝑛𝑛
𝐴𝐴(𝑓𝑓)
𝐴𝐴(𝑓𝑓)= =∫ ∫
𝑥𝑥(𝑡𝑡)sin⁡𝑥𝑥(𝑡𝑡)sin⁡(2𝜋𝜋𝜋𝜋𝜋𝜋)𝑑𝑑𝑑𝑑(2𝜋𝜋𝜋𝜋𝜋𝜋)𝑑𝑑𝑑𝑑
 
𝑛𝑛𝑛𝑛 𝑛𝑛𝑛𝑛
0 0

2 2𝑛𝑛𝑛𝑛 𝑛𝑛𝑛𝑛
𝑥𝑥(𝑡𝑡)cos⁡(2𝜋𝜋𝜋𝜋𝜋𝜋)𝑑𝑑𝑑𝑑
𝐵𝐵(𝑓𝑓)
𝐵𝐵(𝑓𝑓)= =∫ ∫
𝑥𝑥(𝑡𝑡)cos⁡(2𝜋𝜋𝜋𝜋𝜋𝜋)𝑑𝑑𝑑𝑑
 
𝑛𝑛𝑛𝑛 𝑛𝑛𝑛𝑛
0 0(1)(1)
(2)(2)

音高や音色の時間的な変化が考えられる．しかし，音高や音色の時間的な変化が考えられる．しかし， ②原信号𝑥𝑥(𝑡𝑡)と，𝐴𝐴(𝑓𝑓)と𝐵𝐵(𝑓𝑓)で合成される信号の残②原信号𝑥𝑥(𝑡𝑡)と，𝐴𝐴(𝑓𝑓)と𝐵𝐵(𝑓𝑓)で合成される信号の残
足音には雑音成分が多く含まれている．筆者らは，足音には雑音成分が多く含まれている．筆者らは， 差エネルギー𝐸𝐸(𝑓𝑓)を求める．
差エネルギー𝐸𝐸(𝑓𝑓)を求める．
計算量が多いが，離散フーリエ変換に比べて周波数
計算量が多いが，離散フーリエ変換に比べて周波数分解能が高く，雑音低減特性を持つ一般化調和解析
分解能が高く，雑音低減特性を持つ一般化調和解析(2) (2)(3) (3)（GHA）（GHA）の利用を検討したの利用を検討した．その結果，いくつかの．その結果，いくつかの

𝑁𝑁

𝑁𝑁

𝐸𝐸(𝑓𝑓)
𝐸𝐸(𝑓𝑓)= ∫= 𝑒𝑒(𝑡𝑡,∫ 𝑒𝑒(𝑡𝑡,𝑓𝑓)2𝑓𝑓)𝑑𝑑𝑑𝑑2𝑑𝑑𝑑𝑑
0(3)(3)

0𝑒𝑒(𝑡𝑡,𝑒𝑒(𝑡𝑡,𝑓𝑓) =𝑓𝑓)𝑥𝑥(𝑡𝑡)= 𝑥𝑥(𝑡𝑡)− 𝐴𝐴(𝑓𝑓)− 𝐴𝐴(𝑓𝑓)sin(2𝜋𝜋𝜋𝜋𝜋𝜋)sin(2𝜋𝜋𝜋𝜋𝜋𝜋)− 𝐵𝐵(𝑓𝑓)cos⁡− 𝐵𝐵(𝑓𝑓)cos⁡(2𝜋𝜋𝜋𝜋𝜋𝜋)
(2𝜋𝜋𝜋𝜋𝜋𝜋)

③𝑓𝑓を変えて①②を繰返し，𝐸𝐸(𝑓𝑓)が最小になる周波倍音構造を持つ周波数成分を抽出できた．音高に着倍音構造を持つ周波数成分を抽出できた．音高に着 ③𝑓𝑓を変えて①②を繰返し，𝐸𝐸(𝑓𝑓)が最小になる周波
目すると，抽出周波数を目すると，抽出周波数を
12 平均律の音高に限定する
12 平均律の音高に限定する 数𝑓𝑓1数𝑓𝑓を抽出する．
1 を抽出する．
ことが考えられる．計算量の削減も期待できる．
ことが考えられる．計算量の削減も期待できる．

本研究では，足音の音高抽出の前段階の検討とし
本研究では，足音の音高抽出の前段階の検討とし④原信号から③で求めた周波数成分を取り除く．
④原信号から③で求めた周波数成分を取り除く．
𝑥𝑥 ′ (𝑡𝑡)𝑥𝑥 ′ (𝑡𝑡)= 𝑥𝑥(𝑡𝑡)= 𝑥𝑥(𝑡𝑡)− 𝑥𝑥−
𝑥𝑥1 (𝑡𝑡)(4)(4)
1 (𝑡𝑡)= 𝐴𝐴(𝑓𝑓= 𝐴𝐴(𝑓𝑓
𝑥𝑥1 (𝑡𝑡)
𝑥𝑥1 (𝑡𝑡)𝑡𝑡)𝐵𝐵(𝑓𝑓− 𝐵𝐵(𝑓𝑓
1 ) sin(2𝜋𝜋𝑓𝑓
1 ) sin(2𝜋𝜋𝑓𝑓
1 𝑡𝑡) 1−1 ) cos(2𝜋𝜋𝑓𝑓
1 ) cos(2𝜋𝜋𝑓𝑓
1 𝑡𝑡)
1 𝑡𝑡)
′ (𝑡𝑡)が′ (𝑡𝑡)が′ (𝑡𝑡)′ (𝑡𝑡)とができる打楽器音（ドラムなど）を例に，12とができる打楽器音（ドラムなど）を例に，12平均律
平均律 ⑤残差信号𝑥𝑥0（𝑥𝑥0（𝑥𝑥 ≅ 0）になるまで①～④≅ 0）になるまで①～④⑤残差信号𝑥𝑥て，噪音で，ヒトが音高の違いを比較的に感じるこて，噪音で，ヒトが音高の違いを比較的に感じるこ

を用いた
を用いた
GHA
GHA
による音高抽出を試みた．本稿では，による音高抽出を試みた．本稿では，を繰り返す．
を繰り返す．
抽出された周波数を𝑓𝑓抽出された周波数を𝑓𝑓
パワー
パワー
𝑘𝑘 とすると，
𝑘𝑘 とすると，
その解析方法と抽出結果について述べる．
その解析方法と抽出結果について述べる．

 

2 2
2 2
スペクトルは⁡𝑃𝑃(𝑓𝑓スペクトルは⁡𝑃𝑃(𝑓𝑓= 𝐴𝐴(𝑓𝑓) 𝐵𝐵(𝑓𝑓+ 𝐵𝐵(𝑓𝑓𝑘𝑘 ) =𝑘𝑘 )𝐴𝐴(𝑓𝑓𝑘𝑘 ) 𝑘𝑘+𝑘𝑘 ) で求められる．
𝑘𝑘 ) で求められる．

本研究では，12
本研究では，12平均律の音高に対応する周波数
平均律の音高に対応する周波数1212𝑅𝑅 （𝑓𝑓
𝑅𝑅 （𝑓𝑓
𝑓𝑓𝑚𝑚 =
𝑓𝑓𝑚𝑚𝑓𝑓𝑅𝑅=×𝑓𝑓𝑅𝑅 √2
× 𝑚𝑚−𝑚𝑚= 440⁡Hz）(5)(5)
√2𝑚𝑚−𝑚𝑚
𝑅𝑅 =𝑅𝑅440⁡Hz）
解析方法を以下に示す．①～⑤は，区間長𝑁𝑁で観測解析方法を以下に示す．①～⑤は，区間長𝑁𝑁で観測 のみを抽出対象とする（𝑚𝑚：音階番号，𝑚𝑚のみを抽出対象とする（𝑚𝑚：音階番号，𝑚𝑚= 69）．⑤
𝑅𝑅 =𝑅𝑅69）．⑤

２．１２平均律を用いた一般化調和解析
２．１２平均律を用いた一般化調和解析

(2) (2)された信号𝑥𝑥(𝑡𝑡)に対するされた信号𝑥𝑥(𝑡𝑡)に対する
GHA
GHA
アルゴリズムである
アルゴリズムであるの繰り返しをの繰り返しをF 回とした．大きい振幅を持つ周波数
F 回とした．大きい振幅を持つ周波数
． ．

成分が順に
F 個だけ抽出される．条件によるが，計F 個だけ抽出される．条件によるが，計①フーリエ係数𝐴𝐴(𝑓𝑓)と𝐵𝐵(𝑓𝑓)を計算する．
①フーリエ係数𝐴𝐴(𝑓𝑓)と𝐵𝐵(𝑓𝑓)を計算する．
ここで，
ここで，
𝑓𝑓は𝑓𝑓は 成分が順に

算時間は
1 毎の
Hz 毎の
GHA
に比べて
以下となった．
算時間は
1 Hz
GHA
に比べて
1/301/30
以下となった．

20182018
年 7年
月731
月日受理
31 日受理
秋田大学大学院理工学研究科数理・秋田大学大学院理工学研究科数理・
電気電子情報学専
電気電子情報学専
３．打楽器音の音高抽出の試み
３．打楽器音の音高抽出の試み
攻，Department
攻，Departmentof Mathematical
ScienceElectricalof Mathematical
Scienceand and
Electrical(4) (4)
打楽器音として，RWC
打楽器音として，RWC
研究用音楽データベース
研究用音楽データベース
Electronic-Computer
Engineering,
Graduate
Electronic-Computer
Engineering,
Graduate
SchoolSchoolof ofEngineering
Engineering
Science,
Science,
Akita
Akita
University
Universityのドラム音などのドラム音など
7 音（標本化周波数
7 音（標本化周波数
44.144.1
kHz，16
kHz，16bit bit8

田中元志

G（196 Hz）

G#（208 Hz）

F# （185 Hz）(a) Waveform

Fig.2 Time-frequency characteristics of High Tom.
Table 1 Extracted and subjectively evaluated pitch.
候補①

候補②

候補③

主観評価㻌

スネアドラム㻌

B

C

G

D

バスドラム㻌

C

#

C

#

E

C#

ハイタム㻌

G

G

E

F#

(b) Time-frequency characteristics

ミッドタム㻌

D#

D#

C#

C#

Fig.1 Example of the result (Snare Drum).

ロータム㻌

C#

A#

A#

A#

木魚㻌

G

G

F

G#

ハンドクラップ㻌

G#

E

E

D



量子化）を用いた．GHA の解析周波数範囲を E0（41.2
Hz，𝑚𝑚 = 28）～B8（7,902 Hz，𝑚𝑚 = 119）とし，抽出す

る周波数（音高成分）の数を 10 個とした．また，解析

４．まとめ

フレーム長 100 ms，フレーム周期 20 ms とした．

解析周波数を 12 平均律の音高に対応させた GHA

解析結果の例（スネアドラム）を Fig. 1 に示す．連続の利用を提案し，打楽器音の音高抽出を試みた．今5 フレーム以上で抽出された成分の中で，ピークの振後，本方法の利用，および足音の音高抽出について

幅が最も大きい成分を音高候補①，継続時間が最も検討する予定である．最後に，実験に協力頂いた本

長い成分を候補②，倍音構造を有する基音成分（複数学卒業生 吉原駿氏，今井祥太氏，ならびに被験者の存在した場合は，ピークの振幅が最も大きい基音）を方々に感謝する．また，本研究の一部は JSPS 科研費候補③として抽出した．また，絶対音感を持たない（15K00746，18K02236）の助成で行われた．

#

楽器演奏の経験がある被験者 4 名に A～G の純音を聞かせて，打楽器音の音高を答えさせる主観評価実

参考文献

験を行った．結果を Table 1 にまとめる．表中の主観(1) 例えば，磯村太郎，野村祐基，板井陽俊，安川博（2008）：

評価は多数決による音高である．候補①～③の音高

屋内環境下における歩行足音の検出手法に関する一検討，と一致していない場合が多いが，被験者が感じた音

信学技報，SIS2007-81．

高が GHA によって抽出された音高成分の中に含ま(2) 牛山聡，東山三樹夫 ，飯塚昌弘，平田能睦（1994）：

れていた割合は約 97％であった．音高に関連する成一般調和解析による波形分析，信学技報，EA93-103．

分を抽出できていると考えられる．また，評価結果(3) 島崎興平，田中元志（2014）：一般調和解析による足音の傾向から，比較的継続時間が長い音では，短時間の特徴抽出に関する検討，平成 26 年 東北地区若手研究で振幅が大きい成分より，ある程度の振幅を持ち長者研究発表会，YS-12-A3．

く継続している成分が音高として認識されやすい可(4) Goto, M., Hashiguchi, H., Nishimura, T. and Oka, R.

能性が考えられる．例えば，Fig.2 に示すハイタムの(2003) : RWC Music Database: Music Genre Database and場合，約 10 フレーム目に大きなピークを持つ成分 G

Musical Instrument Sound Database, Proc. ISMIR2003, pp.

や G#ではなく，F#が主観評価で選ばれた．

229-330.

秋田大学大学院理工学研究科研究報告，第39号，2018年11月
秋田大学大学院理工学研究科研究報告第 39 号（2018）9解説

3 段 Clos スイッチ網の性能改善に関する研究（その 1）− 研究の背景とスコープ−小原仁**，Koloko Labson**

Improving Performances of Three-Stage Clos Switch Networks, Part I- Back Ground and Scope of the Study Hitoshi Obara** and Koloko Labson**
Abstract
Since C. Clos published his seminal work on three-stage switching networks in 1953, the Clos architecture hasoffered a most practical and efficient design solution for implementing large-scale switching networks to date.
There are a great number of published articles applying the Clos architecture to space switches, time-divisionmultiplexed switches, packet/ATM switches, optical switches, among others. However, to our knowledge, there arevery few researches aiming to improve performances of the Clos architecture itself. In this paper we give out someredundancy in the Clos architecture for the first time, e.g. idle ports left unused, and examine some techniques toenhance its performances by using the redundancy. Although this paper focuses on the back ground and scope of thestudy, we fix our research goals and briefly discuss possible techniques in this paper. Our new design principles of
the Clos networks will appear elsewhere in the near future.

１．はじめにを多段接続した Clos 網は規則的で単純な構成であり，

この解説の対象である「スイッチ」（以下，SW と回路規模が小さいという特長がある．SW 全体の入力略称）とは，例えば電話交換機のように多数の加入（出力）ポート数を N とすると，XB-SW の回路規模者の間で動的に回線を設定するための装置であり，は N 2 に比例するが，3 段 Clos 網では 3N 3/2 まで削減

通信システムに不可欠な要素である (1) ．最も初期のできる．N = 256 では 5 倍，N = 1024 では 10 倍以上SW として，入力ポートからの配線と出力ポートへのの差が生じる．また，Clos 網は既存回線の接続状態

配線を直交配置して，その交点に電磁式リレーを設によらず未接続の入出力ポートを必ず接続できる性置した機械式クロスバーSW（XB-SW）がある (2)．こ質（完全ノンブロック性）がある (8) ．さらに，Closのタイプの XB-SW は現在では使われていないが，そ網内の経路探索は簡単な論理処理（Boolean 演算）での交点に 2 入力・2 出力の光 SW を配置した光 XB-SW

実現できる (9)．

は現在も光ネットワークなどで広く使用されている(3) (4)

Clos 網は 1953 年に提案され，上記の優れた性質の．最近の例では，インターネットでパケットを宛ため，これまで多くの通信システムに用いられてき

先に振り分けるルータにもパケット蓄積用のメモリ

た．ごく一例をあげると，1960 年代の電話交換機（空が付加された SW が用いられている(5), (6)．

間分割型 SW）(10)，1980 年代のディジタル交換機（時「スイッチ網」とは，いくつかの小規模な SW を分割型 TST‑SW） (11)，1990 年代の Broadband 交換機

網状に接続して得られる大容量の SW であり，様々（ATM‑SW）(12)，2000 年代の光 SW (13)，2010 年代の(7)な拡張方法が提案されてきた ．その中でも XB-SW
2018 年 7 月 23 日受理**
秋田大学大学院理工学研究科 数理・電気電子情報学専
攻 電 気 電 子 工 学 コ ー ス ， Electrical and Electronic
Engineering Course, Department of Mathematical Scienceand Electrical-Electronic-Computer Engineering, Graduate
School of Engineering Science, Akita University

大容量ルータ (14), (15)などである．世界最大の電気電子
情報関係の学会である IEEE のデータベース (16)で検索すると，2018 年 6 月現在で論文タイトルに Clos
network または Clos switch を含むものだけで 218 件，
本文中にそれらを含むものは 6,391 件に達する．平均
して１年に約 100 件の論文が Clos 網に言及している

10

小原

仁・Koloko LABSONことになる．特筆すべきは，前述の約 6 千件の論文態とする．入力ポート i と出力ポート j を接続する場のうち約 4 千件が 2000 年以降に発表されている点で合，それらの交点に存在する単位 SW（Ci, j）のみをある．この事実は Clos 網の応用範囲が近年，ますま

バー接続に変更する．その回線を解放する場合は Ci, j

す広くなっていることを示唆している．論文タイトのバー接続をクロス接続に戻すだけでよい．一方，

ルに Clos network/switch を含む上記の論文の約 85%

ハードウェアの面では，ポート数を N とすると，単が Clos 網の応用技術であり，その他は Clos 網で 1：

位 SW の総数で定義される回路規模は N 2 と急激に増n マルチキャスト回線や多様な速度の回線を収容す

大する． XB-SW は単純な制御で高速に実行できる

る場合のノンブロック条件，あるいは特定のアルゴ

反面，回路規模が最大となる両極端の性質を有してリズムを用いて回線設定した場合にノンブロックとおり，性能バランスが非常に悪いことがわかる．

なる広義ノンブロッキング型 SW の理論検討などである．筆者らが調べた範囲では，Clos 網自身の性能を改善することを目的とした研究は一例も見つけることができなかった．筆者らの調査不足もあるが，Clos 網の完成度の高さと，前述のように Clos 網の回(b) クロス接続

路規模は XB-SW と比較して 10 分の 1 以下に削減でき，更なる性能改善のニーズは強くなかったことなどがその要因として考えられる．しかし，理論面か(c) バー接続

らの興味と後述する実用面からの要請により，その性能を改善する研究は大変有意義である．それは前(a) SW の全体構成

述の Clos 網の応用の広さを考えれば明らかであろう．
筆者らは，これまで約 10 年間に亘り XB-SW の回

図1

本解説で対象とする XB-SW の構成

路規模を最大で半減できる幾つかの新たな構成原理を提案した (17)〜(31)．本研究はその成果を Clos 網に適単位 SW の例として，光導波路上で実現されるマ

用するという最新かつ独自のアプローチをとる．以ッハ・ツェンダーSW (32)の構成原理を図 2 に示す．こ

下，第二章において本研究の基盤となる XB-SW との光 SW では電気信号（図 2 ではヒータ）によりデClos 網の概略を紹介する．第三章で回路規模を削減

バイスの屈折率（＝光の速さ）を変化させ，後段のした XB-SW の一例を紹介し，それを Clos 網に適用

方向性結合器での位相をシフトさせて SW 動作を実して得られる効果と問題点を議論する．第四章では現する．光の干渉を用いているため，原理的に波長本研究で解決すべき課題を整理し，本研究の今後の以下のサイズでは実現できない．一般的に，デバイ取り組みについて議論する．第五章はまとめである．

スの感度が小さいため作用長を大きくとる必要があ

なお，本研究のゴールは１つではなく，その過程もる．また，導波路上の配線は光信号の損失を抑える

段階的である．このため，本解説で全ての研究内容ために急な曲げを実現できない．図１では配線の曲をカバーできない．Clos 網の新たな構成原理やそのげがないように見えるが実際には図 2 のように存在制御などについては最後に紹介する今後の報告を御する．さらに，信号の干渉（クロストーク）を抑え参照願いたい．

るため配線間隔も狭くできない．電気 LSI と異なり，上記の集積度の限界のため１チップで実現できる光2.1

XB‑SW の概要

２．研究背景本研究で対象とする SW は，2 入力・2 出力の単位

SW サイズ（ポート数）は厳しく制限される．以上の理由により，光 SW の大容量化・経済化のためには単位 SW 数を減らすことが有効であることがわかる．

SW を網状に接続して得られる光 SW である．図 1(a)にその代表的な XB-SW の構成原理を示す．入力ポートと出力ポートを格子状に配置し，それらの交点に
単位 SW を設置する．単位 SW は図 1(b)と(c)のクロ
ス接続とバー接続を切り替えるため 1 ビットの制御信号を必要とするが，以下では簡単のため省略している．また，全ての単位 SW の初期状態はクロス状

図2

マッハ・ツェンダ型 2×2 光スイッチ素子

３段Closスイッチ網の性能改善に関する研究（その１）－研究の背景とスコープ－

2.2

11

さて， Clos 網の回路規模は，なぜ XB-SW より格

Clos-SW の概要

前 節 で 述べ た よ うに ，１ チ ッ プ で実 現 で きる 光

段に小さくなるのだろうか．図 1 に示すように

XB-SW のサイズは小さく，N = 16～64 程度である．

XB-SW の行と列の単位 SW やリンクは特定の入出力

このため，複数の XB-SW を網状に接続して SW サイ

ポートで独占的に使用されており，その利用効率はズを拡張する方法が多数提案されてきた (33)．例えば，

非常に小さいことがわかる．一方，Clos 網では一対

図１の XB-SW を 1 チップで実現し，それを縦・横・の入出力ポート間の経路は中間 SW と同じ数だけ存

斜め方向に 2 次元的に拡張する方法が考えられるが，在し，かつ，それらのルート上の単位 SW やリンク

チップ数が 2 乗で増大するため現実的でない．このは複数の入出力ポートで共有されている．すなわち，限界を打破するため，小規模な XB-SW を 3 段接続す

単位 SW やリンクなどのリソースの「共有度」を上る方法が C. Clos によって提案された (8)．その一例をげることが SW 効率改善の鍵となることがわかる．

図 3 に示す．四角のブロックは図 1 に示した XB-SW

ただし，リソースの共有は制御の複雑さとトレード

で，その左側が入力ポートであり，右側が出力ポーオフとなることに注意する必要がある (17)．

トを表す．
図 3 において 1 段目の r 個の XB-SW（I1～Ir）を入力 SW と呼ぶ．その SW サイズは入力が n 本，出力３．本研究のアプローチ
3.1

XB-SW の冗長性が m 本であり，以下では n×m と表記する．全体の本研究の目的は Clos 網の性能改善であるが，筆者

SW サイズ N は N = n r となる． 2 段目の m 個の r×r

らのような浅学菲才の研究者が直接，図 3 の構成を

XB-SW（M1～Mm）を中間 SW と呼び，3 段目の r 個

考えてもすぐに行き詰ることは明らかである．本研の m×n XB-SW（O1～Or）を出力 SW と呼ぶ．図 3

究では「急がば回れ」という先人の知恵に学び， Clos

は（N, n, r , m）=（12, 4, 3, 4）に相当する構成である．

網を構成している XB-SW に注目する．第一章で述べ

なお，XB-SW 相互を結ぶ線をリンクと呼ぶ．

たように，筆者らは XB-SW の冗長性に注目して新た

図 3 において，全ての入力と出力が接続できるためには m  n である必要性は明らかである．実際，mな構成法を提案してきたことが背景にある．
図 1 を見ると，上端と右端にあるそれぞれ N 本の= n では新しい回線を設定するために既存の回線のポートは未使用状態となっている．筆者らは，その接続経路の変更が必要となる再配置ノンブロック型

冗長性を除去することで回路規模を N 2 から N (N－1)となる (33)．m   2n－n /F2r-1

では広義ノンブロックに削減でき，さらに，光信号の coupling/splitting 損失，m  2n－1 では完全ノンブロック型となを許容すれば N (N－1)/2 にまで半減できることを明る．ここで，xは x を超えない最大の整数を表す floor

らかにした (27) ,(28)．ただし，その代償として光信号の

型となり

(34)

関数，Fk は k 番目の Fibonacci 数である．なお，m = n

損失が増えるほか，配線が複雑化するなどの新たなの条件で SW 規模が最小となるのは n = m = r = ξܰの場合である．本研究では実用性の面から完全ノン問題が生じる．そこで， XB-SW の冗長性を「排除」

ブロックな SW を対象とし，以下では簡単のため m =転換する．すなわち，上記の XB-SW の空ポートを追

2n と仮定する．

加の入出力ポートとして利用することを考える．

するのではなく，それを「活用」する方向に発想を

図4

XB-SW の空ポートを利用した SW 構成例

最も単純には図 1 の XB-SW を図 4 に示すように 2
図3

3 段 Clos 網の構成例

つの三角 SW として利用する方法が考えられる (35)．

12

小原

仁・Koloko LABSON

図 4 では 3×3 の XB-SW の上端の空ポートを追加の入力ポート 1’，2’，3’とし，右端の空ポートを追加の出力ポート 1’，2’，3’に割り当てる．XB-SW の対角線上にある単位 SW はバー状態に固定される．このように追加の入出力ポートを付与した XB-SW を拡
張 XB-SW（Augmented XB-SW）と呼ぶ (30),(31)．
参考までに，図 4 に含まれる三角 SW は XB-SW の性質から次のように容易に導かれる (18),(33) ．図 1 のXB-SW の最初の列において，左端から入力される N(a) ブロック発生例
図5(b) 再配置によるブロック解消

三角 SW におけるブロックと再配置の例

本の光信号の中から出力ポート 1 宛てのものが抜き出され，2 列目に向かう信号は N−1 本に減少する．

では，図 4 の拡張方法の何が悪かったのだろうか．

図 4 では 1 列目で入力 1 が出力 1 と接続された後，その答えはこれまでの議論から明らかである．図 4

その空席を埋めるように入力 2 と 3 が下方にシフト

では，１つの XB-SW を互いに排他的な 2 つの三角する．以下，同様に 1 つの列を通過する度に信号のSW に分断しており，本研究で志向すべきリソースの総数は 1 個ずつ「だるま落とし」のように減ってい「共有」が全く考慮されていない．とすれば，そのく．よって，縦方向の単位 SW 数が１列ごとに１個解決方法も自ずと明らかである．何らかの「共有」

ずつ減少する三角 SW が得られる．この性質を応用

機構を導入すればよい．筆者らが最初に思いついた

すると新たな SW 構成が得られるが，その詳細につ新たな拡張 XB-SW の例 (29)を図 6 に示す． XB-SW の

いては筆者らの論文
3.2

(30)

を参照されたい．

Clos 網への応用

行と列の単位 SW がそれぞれ 2 つの入力と出力で共有されている．また，従来の XB-SW（図 1 と図 3）と異なり，図 6 では同一行および列の入出力ポート

図 4 の拡張 XB-SW を図 2 の Clos 網の中間 SW にの信号の伝送方向が反対（双方向）となっている．

適用すると，中間段における XB-SW 数を半分に減ら

ただし，この構成では次に述べる「干渉」と「制約」

すことができる．大まかに見積もると，全体の 3 分という二つの副作用が新たな問題となる．

の 1 を占める中間段の SW 規模を半分にできるので，
SW 全体としては約 6 分の 1 の削減が見込まれる．さらに，入力 SW と出力 SW にも適用範囲を広げると，最大で 2 分の 1 の削減が見込まれる．この効果は Clos
網の回路規模が XB-SW の 10 分の 1 以下に削減できることに比べて，実に僅かなものである．しかし，一般的に，あるシステム全体の回路規模の 6 分の 1
〜2 分の 1 を削減できるとしたら，それは無視できな
い効果ではないだろうか．
上記の議論で本研究の目的である Clos 網の性能改

図6

リソース共有を図った拡張 XB-SW の例

善がすぐにでも達成できそうだと思われるかも知れない．しかし，現実はそれほど単純ではない．図 4

図 6 において，入力 1 から出力 3 と入力 1’から出において，入力 1 から出力 1 の接続と入力 3 から出

力 1’へ同時に回線設定をすると行内でブロックが発

力 3 の接続を入れ替えるケースを考える．それらの 2

生する．同様に，入力 3’から出力 1’と入力 1 から出

つの新たな接続は，既存の接続（この場合は入力 2

力 1 へ同時に回線を設定すると列内でブロックが発から出力 2）でブロックされる（図 5a）．ただし，そ生する．ある工夫によって行内のブロックは避けるの既存の回線の経路（入力 2 から出力 2）を再配置すことはできるが (37)，列内のブロックは解消できない．

ると新たな接続を実現できる（図 5b）．すなわち，三しかし，その詳細は割愛するが，図 5 の拡張 XB-SW

角 SW は再配置ノンブロックとなる．さらに不幸なでは最悪ケースの再配置数を 1 にまで削減すること

ことに，N×N 三角 SW で再配置すべき回線数は最悪ができる (37)．この結果は，SW 制御の複雑さを O(N)の場合 N−2 となり，2 つの回線を交換する際に既存から O(1)に低減させたことに相当し，図 6 の構成がの全ての回線が影響を受けるため実用的ではない．

それほど筋の悪いものではないことを暗示している．

13

３段Closスイッチ網の性能改善に関する研究（その１）－研究の背景とスコープ－

次に，双方向化の影響について考える．一般的に，

ルが上がれば SW 制御が複雑になり，その制御時間受動素子で構成される光 SW では信号の伝送方向はが問題になる．現状把握のため，Clos 網の制御の高任意である．例えば，導波路上に作成された光 SW

速化に関する従来の研究をリサーチしたところ，少は入出力ポートを反対に使用しても，元の特性とほ数の論文しか存在しないことが判明した．本解説で(38)． はスペースの制限から Clos 網の構成に焦点を当てた

一方で，例えば MEMS タイプの光 SW では，その動が，Clos 網の制御の高速化も本研究の主要なゴール

作原理から信号の伝送方向が限定されており，図 6の一つとして既に検討を開始した (39)．最初のステッのような双方向化が適用できない．以上の議論より，

プとして最も単純な構成（n = 2）とし，その後，一図 6 の構成は内部ブロックが避けられず，全ての光

般的な条件（n  3）に拡張する予定である．

ぼ同等の性能を示すことが実験的に示されている

SW に適用できないなどの問題がある．
４．研究のスコープと進め方
以上の研究背景と経緯をベースに本研究の３つの課題と今後の進め方を簡単に述べる（図 7 を参照）．
最初に，今後の研究で，どのような SW 構成を検討対象とすべきだろうか．これまで紹介した SW 構
成には未解決の問題が残されている．しかし，その先の展望が全くない訳ではない．図 6 の拡張 XB-SW
ではブロックを完全に解消できないが，それは 1 つ

図7

本研究の課題と従来技術との関連の拡張 XB-SW を従来の 2 つの XB-SW として最大限度まで利用しているためである．ならば，1 つの拡張

５．まとめ

XB-SW を，例えば 1.5 個の従来の XB-SW として収

本解説では，最初にスイッチ網の代表例である 3

容率を下げて使うことでブロックを回避できないだ

段 Clos 網について，近年，その応用範囲がますますろうか．この例では，2 つの拡張 XB-SW に 3 つの従広がっているものの，それ自身の性能改善の研究例

来の XB-SW を埋め込むことに相当する．この考え方がほとんどないことを示した．次に，筆者らによるは共有化のレベルを 1 段階上げることを意味する．

最新かつ独自のアプローチとして，XB-SW の冗長性

本質的な解決方法ではないかも知れないが，最初のを活用した拡張 XB-SW を用いる性能改善の方法をステップとして現実的なアプローチと思われる．

紹介した．最後に，本研究で解決すべき３つの課題

次に，双方向化の問題について考える．図 6 では 1として，単位 SW の共有化，リンクの単方向化，制つのリンクを直接，共有しているが，リンクの伝送

御の高速化をあげ，それぞれの研究の進め方につい方向を固定した上で双方向化することはできないだて簡単に議論した．本研究に関する成果の一部につろうか．具体的には右向きと左向き，あるいは下向

いては，今後，下記のように報告する予定である．

きと上向きの単方向リンクを混在させる形態である． ・3 段 Clos スイッチ網の性能改善に関する研究（そその背景として，次のようなアナロジーが考えられの 2）－双方向 XB-SW を適用した 3 段 Clos スイッ

る．初期の Ethernet では 1 本のバスを双方向で共有

チ網－，電気関係学会東北支部大会，2018 年 9 月

しており，その最大効率は 30%程度であった．その・3 段 Clos スイッチ網の性能改善に関する研究（そ後，単方向のバスを折り返す形態（Folded Bus）が提の 3）－FPGA を用いた 3 段 Clos スイッチ網の制案され，最終的に 2 本の単方向バスを組み合わせた

御の高速化－，電気関係学会東北支部大会，2018

双方向構成（Bidirectional Dual Bus）に進化した．バ

年9月

スの本数は 2 倍に増えたが，受信ノードで情報を終・Improving Performances of Three-Stage Clos Networks

端する場合のスループットは約 7 倍の 200%以上になPart IV -Reducing the Number of Rearrangementsった．アナロジーが常に正しい方向を示す訳ではな

Using

いが，最初のステップとして試してみる価値はある．

Idle

Ports,

IEEE

TohokuSection

Joint

Convention, Sept. 2018

最後に，SW 制御の問題について考える．現時点で

・3 段 Clos スイッチ網の性能改善に関する研究（そは新たな Clos 網の構成は不明なので，その SW 制御の 5）－3 段 Clos スイッチ網の並列制御方式，も不明である．ただし，前述のように共有化のレベ

電子情報通信学会 EMD 研究会，2018 年 10 月

14

小原

仁・Koloko LABSON

謝辞
本研究について，当初からその重要性と将来性に深い御理解を賜り，温かく見守っていただいた坂田真
人先生（秋田大学名誉教授）と根元義明先生（東北大学名誉教授）に衷心より御礼申し上げる．また，筆者らの下でスイッチ網の研究に辛抱強く取組み，
世界に誇れる研究成果をあげた（ている）研究室の学生およびスタッフに感謝する．
参考文献(1) Hui, J.Y. (1990): Switching and Traffic Theory for
Integrated Broadband Networks, Kluwer Academic
Publishers, Boston.
(2) Pearce, J. G. (1981): Telecommunications Switching,
Plenum Press, New York.
(3) Papadimitriou, G.I., Papazoglou, C., Pomportsis, A.S.
(2003): Optical Switching: Switch Fabrics, Techniques, andArchitectures, IEEE/OSA J. Lightw. Technol., vol. 21, no. 2,
pp.384-405.
(4) Spanke, R.A. (1987): Architectures for Guided-Wave
Optical Space Switching Systems, IEEE Communi. Mag.,
vol. 25, no. 5, pp.42-48.
(5) Hassen, F., Mhamdi, L. (2015): High-Capacity Clos
Network Switch for Data Center Networks, Proc. of IEEE
Int. Conf. on Communications, pp.1-7, London, UK.
(6) Hogg, S. (2014): Clos Networks: What's Old Is New Again,
Network, https://www.networkworld.com/article/2226122/
cisco-subnet/clos-networks--what-s-old-is-new-again.html(7) Marcus, M. J. (1977): The Theory of Connecting Networks
and Their Complexity: a Review, Proc. IEEE, vol. 65, no. 9,
pp.1263-1271.
(8) Clos, C.C. (1953): A Study of Non-Blocking Switching
Networks, BSTJ, vol. 32, no. 2, pp.406-424.
(9) Hwang F. (1983): Control Algorithms for Rearrangeable
Clos Networks, IEEE Trans. on Communi., vol. COM-14,
no. 3, pp.952-954.
(10) Matthews, G. A. (1966): The Pentex Electronic Telephone
Exchange’, IEEE Trans. on Communi. Tech., vol. 31, no. 8,
pp.212-216.
(11) Bruce, R.A., Gilth, P.K. (1979): No.4 ESS – Evolution of a
Digital Switching System, IEEE Trans. on Communi., vol.
COM-27, no. 7, pp.1001-1011.
(12) Liew, S.C. (1994): Multicast Routing in 3-Stage Clos ATM
Switching Networks, IEEE Trans. on Communi., vol. 42, no.
2/3/4, pp.1380-1390.
(13) Marom, D.M., Colbourne, P.D., D’errico A., Fontaine N.K.,
Ikuma Y., Proietti R., Zong L., Rivas-Moscoso, J.M.,
Tomkos, I. (2017): Survey of Photonic SwitchingArchitectures and Technologies in Support of Spatially andSpectrally Flexible Optical Networking, IEEE J. Opt.
Commun. Netw., vol. 9, no. 1, pp.1-26(14) Juniper White Paper (2015): Clos IP Fabrics withQFX5100 Switches, https://www.juniper.net/us/en/local/
pdf/whitepapers/2000565-en.pdf(15) Cisco White Paper (2016): Cisco Data Center
Spine-and-Leaf Architecture: Design Overview,https://www.cisco.com/c/en/us/products/collateral/switches/
nexus-7000-series-switches/white-paper-c11-737022.pdf(16) https://ieeexplore.ieee.org/Xplore/home.jsp(17) 小原仁，坂田真人（2007）：格子型スイッチ網の構成原理に関する一考察，秋田大学工学資源学部研究報告，
vol.28, pp.49-56. https://ci.nii.ac.jp/naid/110006481838/(18) Obara, H., Sakata, M., Nemoto Y. (2008): Bridging
Crossbar and Triangular Switches, Proc. of HPSRN, pp.
31-36, Sendai, Japan.
(19) Obara, H., Sakata, M., Nemoto Y. (2008): Torus-Embedded
Crossbar Switch with a Minimum Number of Switching
Cells, ibid., pp.119-124.
(20) Obara, H. (2008): Reduced Crossbar Switch with Minimum
Number of Switching Cells, Electron. Lett., vol.44, no.14,
pp.888-889.
(21) Obara, H. (2009): Extended Class of Pruned Crossbar
Switches, Proc. of Int. Conf. Adv. Technol. Commun., pp.
129–132, Hai Phong, Vietnam.
(22) Kai, Y., Hamada, K., Myao, Y., Obara, H. (2009): Designof Partially-Asynchronous Parallel Processing Elements for
Setting up Benes/Clos Networks in O(logN) Time, Proc. of
Photonics in Switching, pp.1-2, Pisa, Italy.
(23) 小原仁 (2014)：縮退クロスバースイッチの研究（その１），信学技法，EMD2014-13，pp.27-32.
(24) 小原仁 (2014)：縮退クロスバースイッチの研究（その２），信学技法，IN2014-27，pp.67-72.
(25) 小原仁 (2015)：縮退クロスバースイッチの研究（その３），信学技法，EMD2015-8，pp.39-44.
(26) 小原仁 (2017)：縮退クロスバースイッチの研究（その４），信学技法，OCS2017-17，pp.33-38.
(27) 小原仁 (2017)：縮退クロスバースイッチの研究（その５），信学技法，OCS2017-18，pp.39-44.
(28) Obara, H. (2015): Design of Optical Multi/Demultiplexers
Composed of Bidirectional 2 x 2 Switch Elements for
Reducing Component Count, Electron. Lett., vol.51, no.15,
pp.1182-1184.
(29) Obara, H. (2016): Strictly Non-Blocking Three-Quarter
Crossbar Switch with Simple Control, Electron. Lett.,vol.52, no.23, pp.2051-2053.
(30) Obara, H., Hashimoto, T. (2016): Augmented Crossbar
Switch: a New Design of Optical Crossbar Switch for
Improved Crosstalk Performance, Proc. of Int. Conf. on
Elect. Eng., Okinawa, Japan.
(31) Obara, H. (2018): Cascaded versus Parallel Architecturesof Two-Stage Optical Crossbar Switches with an Extra Set
of Inputs and Outputs, IET Optoelectronics, vol. 12, no.4,
pp.196-201.
(32) Hinton, H.S. (1987): Photonic Switching Using Directional
Couplers, IEEE Com. Mag., vol. 25, no. 2, pp.16-26.
(33) Kabacinski, W. (2005): Nonblocking Electronic and
Photonic Switching Fabrics, Springer, Berlin.
(34) Opferman, D.C., et al. (1971): On a Class of Rearrangeable
Switching Networks Part I: Control Algorithm, BSTJ, vol.
50, no. 5, pp.1579-1600.
(35) Chang, F.H., Guo, J.Y., Hwang, F.K., Lin, C.K. (2004):
Wide-Sense Nonblocking for Symmetric or Asymmetric3-stage Clos Networks under Various Routing Strategies,
Theoretical Computer Science, vol. 314, pp.375-386.
(36) Lea, C-T. (2005): Expanding the Switching Capabilities of
Optical Crossconnects, IEEE Trans. Communi., vol. 53, no.
11, pp.1940-1944.
(37) 橋本拓大 (2018)：空きポートを利用したクロスバース
イッチの並列構成に関する研究，平成 29 年度 秋田大学大学院理工学研究科修士論文．
(38) Tanizawa, K., Suzuki, K., Ikeda, K., Namiki S.,
Kawashima, H. (2016): Novel PILOSS Port Assignment
for Compact Polarization-Diversity Si-Wire Optical Switch,
Proc. OFC, pp.1-3, Anaheim, CA, USA.
(39) 柳普登 (2018)：FPGA を用いたハードウェア制御による三段 Clos 網の制御の高速化に関する研究，平成 29
年度 秋田大学理工学部卒業論文．

15

秋田大学大学院理工学研究科研究報告，第39号，2018年11月

解説

原始語の集合と文脈自由言語について
新屋良磨 ∗∗On Primitive Words and Context-Free Languages
Ryoma Sin’ya∗∗
Abstract
Primitive word is a word that can not be represented by any repetition of shorter words. Since every nonempty word is a repetition of the unique primitive word, primitive words play an important role in combinatorics
on words. In this article, we explain a long-standing open problem called “primitive words conjecture” which
has a deep connection with the theory of context-free languages.

1

はじめに

原始語とは「自身より短い語の繰り返し」では表されない語 (文字の有限列) のことである (正確な定義は次節にて行う)．任意の語はある原始語の繰り返しとして一意に分解することができ，そういった意味で原始語は語の世界における素数のような対象であり，定義は単純であるが非常に奥深い性質を持っている．
形式言語理論においては「ある語の集合 (言語) が特定の言語族に属するかどうか？」といった種類の問題がしばしば興味の対象となる．ここでは「特定の言語族」とは計算論的あるいは代数的な特徴づけを持った言語族
が主な興味の対象とされ，典型的な例としては Chomsky の階層における正則言語 (regular languages)，文脈自由言語 (context-free languages)，文脈依存言語 (context-sensitive languages) などの族が挙げられる．帰納的可算言語 (recursively enumerable language) まで行ってしまうと「ある語の集合が帰納的可算言語に属するかどうか？ (すなわち計算可能であるか)」は (著者の感覚からすると) 形式言語理論というよりも計算論の問いになるものと思われる．その中でも特に文脈自由言語は，代数における代数関数 (多項式系の解となる巻数) のある種の非可換化と捉えることができ，代数的言語とも呼ばれている重要な言語族である．あらゆる性質が決定可能である正則言語とは異なり，文脈自由言語は (等価性判定や普遍性判定を含む) 多くの問題が決定不能であり，計算的には困難面も持ちながらも豊かな構造理論を持っている．
本稿では原始語全体の集合と文脈自由言語に対する有名な Dömösi-Horváth-Ito 予想について述べ，これまでの研究における予想へのいくつかのアプローチや今後の課題について解説を行う．Dömösi-Horváth-Ito 予想に対する既存のアプローチは多数あるものの，本項では特に言語の母関数や測度に関連したアプローチについて取り上げる．続く 2 章では原始語と文脈自由言語の定義を行い Dömösi-Horváth-Ito 予想を定式化する．

3 章にて原始語の集合と無曖昧文脈自由言語の関係について考察を行い，4 章にて原始語の集合に対する著者なりの今後の課題について述べ本稿の結びとする．

2

原始語の集合と文脈自由言語

形式言語理論において，文字集合とは単に空でない有限集合のことを差し，文字集合の要素を文字と呼ぶ．以降，変数 A は常に文字集合を表す. 文字集合 A 上の語とは A に属する文字 ai を有限個並べた列：a1 a2 · · · an2018 年 8 月 10 日受理∗∗ 秋田大学大学院理工学研究科数理・電気電子情報学専攻数理科学コース，

Mathematical Science Course, Akita University Graduate School of Engineering Science.

16

新屋良磨

である．語には連接 · という演算を考えることができ，2 つの語 u = a1 · · · ai , v = b1 · · · bj の連接 u · v は uと v を並べたものを表す：

u · v ≜ a 1 · · · a i b 1 · · · bj .

(1)

語 w を n 個連接した語を w n で表す．例えば aaa = a3 で abab = (ab)2 である．語 w = a1 · · · an の長さを

|w| で表す：|w| = n．ε で長さが 0 の語 (空語) を表す．A に属する文字から作られる語全ての集合を A∗ で表す．A 上の言語とは A∗ の部分集合のことを指す．すなわち L ⊆ A∗ となる L を言語と呼ぶ．任意の 2 つの言
語 L, M の連接を以下のように語の連接を自然に拡張して定義する：
L · M ≜ {uv ∈ A∗ | u ∈ L, v ∈ M }.

(2)

言語 L に対し，Ln で言語 L の n 回の連接

L0 ≜ {ε}Ln ≜ L · Ln−1

(3)を表す．言語 L に対してその Kleene 閉包 L∗ を

L∗ =

∞
∪

Ln

(4)

n=0

で定義する．有限要素の言語を全て含み，和集合，連接および Kleene 閉包に閉じた最小の言語族を正則言語族
と呼ぶ．

2.1

原始語

定義 2.1 (原始語). A 上の語 w ∈ A∗ が原始語であるとは，w より短い語の繰り返しで表せられないこと：∗n

任意の u ∈ A について w = u ⇒ n = 1(5)ことを言う．A 上の全ての原始語の集合を QA で表す．
例えば語 abbab は原始的であるが，abbabb = (abb)2 は原始的ではない．また，語 w の長さが素数 p の場合
は ap という形の語を除いて原始的となる：
任意の素数 p について A ∩ QA = A \ {a | a ∈ A}.
p

p

p

(6)

さらに，任意の非空語 w ∈ A∗ (|w| ≥ 1) には原始語 u と自然数 n ≥ 1 のペアが一意に存在し w = un が成り

立つ．

2.2

文脈自由言語定義 2.2 (文脈自由文法). 文脈自由文法とは，文字集合 A と• 変数集合と呼ばれる A と素な有限集合 V
R→⊆ V × (V ∪ A)∗• 導出規則と呼ばれる関係 −• 初期変数と呼ばれる S ∈ V
Rから成る 4 つ組 G = (V, A, −→, S) である．
R
定義 2.3 (文脈自由言語). 文脈自由文法 G = (V, A, −→, S) が表現する言語 G を初期変数 S から導出規則

17

原始語の集合と文脈自由言語について

RR−→ の反射推移閉包 −→* によって導出される A 上の言語として定義する．
{}
R
G ≜ w ∈ A∗ | S −→* w .

(7)

言語 L が文脈自由とは，L = G となる文脈自由文法 G が存在することを言う．

文脈自由言語の典型的な例としては，A() = {(, )} 上の次の文法 GD が挙げられるだろう．
R

GD = ({S}, A = {(, )}, −→ = {(S, ε), (S, (S)S)}, S).

(8)

文法 GD によって生成される語として
R

R

R

R

R

R

R

S−
→ (S)S −→ (ε)S −→ ()(S)S −→ ()(ε)S −→ ()()(S)S −→ ()()(ε)S −→ ()()()ε = ()()()(9)などがある．直感的には D は括弧の対応がきちんと取れている語の集合である．なお，数式に用いる括弧 ()と混同しないように太字の括弧 () を用いている．D は Dyck 言語とも呼ばれ，正則言語ではないが文脈自由言語である例として代表的な言語となっている．

2.3

Dömösi-Horváth-Ito 予想

原始語と文脈自由言語の定義がそろったので，本稿で解説する Dömösi-Horváth-Ito 予想を以下に述べよう．
予想 (Dömösi-Horváth-Ito). A が 2 つ以上の文字を含む (#A ≥ 2) とき，全ての原始語の集合 QA は文脈自由ではない．

この予想のように「ある言語がある言語族に属さない」という形の命題を否定命題と呼ぶ．形式言語理論には否定命題の一般的な証明技法がそれぞれの言語族についていくつか種類がある．続く 3 章では母関数を用いた証明技法 (Chomsky-Schützenberger の定理) を，最後の 4 章では繰り返し構造を用いた証明技法 (ポンピン
グ補題) と測度を用いた証明技法を紹介する．
予想の初出である Dömösi, Horváth, Ito らの 1991 年の論文 (4) から，原始語と文脈自由言語に関する研究が続けられているが現時点で未解決である．
補足 2.1. A が単一の文字 a のみ含む場合 (A = {a}) は，定義より

Q{a} = {a}(10)となってしまうため，これは明らかに文脈自由言語 (文法 G = ({S}, {a}, {(S, a)}, S) の言語) となる．

w が原始語であるかどうかの判定は，素朴に w の全ての真の接頭辞 (w = uv (|u|, |v| ≥ 1) となる u) に対してその繰り返しが w と一致するかどうかを判定すれば良い．そのため w が QA に属するかどうかの判定は線形領域で計算可能であるため，QA が文脈依存言語であることは自明である．
3

原始語と無曖昧文脈自由言語

原始語の集合が文脈自由言語かどうかについてはまだ未解決であるが，文脈自由言語よりも表現力の弱い言語クラスである無曖昧文脈自由言語ではないことが知られている (文献 (5) の 8.3 章を参照せよ)．本節では，既存の証明とは少し違った形で (不完全ではあるが) 原始語の集合が無曖昧文脈自由でないことを示すためのア
イディアを解説したいと思う．まずは無曖昧文脈自由言語の定義 (およびそれに必要な諸定義) から述べよう．

18

新屋良磨

無曖昧文脈自由言語と Chomsky-Schützenberger の定理

3.1

R

R

R

定義 3.1 (最左導出). 文脈自由文法 G = (V, A, −→, S) 導出規則 −→ は次の最左導出規則 −−→⊆ (V ∪ A)∗ ×left(V ∪ A)∗ に自然に拡張することができる．

−−→≜ {(uXw, uvw)u|∈ A∗ , v, w ∈ (V ∪ A)∗ X ∈ V such that X −
→ v}.
R

R

left

(11)

R

u −−→* v となる場合に G は u から v を最左導出すると言う．
left

R→) が無曖昧であるとは，任意の w ∈ G に
定義 3.2 (文脈自由文法と曖昧性). 文脈自由文法 G = (V, A, R, −R→* w となる最左導出が唯一存在することである．すなわち任意の w ∈ G に対してついて S −
R

R

R

R

R

left

left

left

left

left

S −−→ w1 −−→ w2 −−→ · · · −−→ wn −−→ w(12)となる n ∈ N と w1 , · · · , wn ∈ (V ∪ A)∗ が唯一存在することを言う．

文脈自由言語 L が無曖昧であるとは，L = G となる無曖昧な文脈自由文法 G が存在することを言う．文

脈自由言語 L が本質的に曖昧であるとは，L = G となる無曖昧な文脈自由文法 G が存在しないことを言う．
例えば前節で紹介した Dyck 言語を生成する文法

GD = ({S}, {(, )}, {(S, ε), ((S)S)}, S)(13)

は無曖昧である (実際には機能法などを用いて示す) が，同じく Dyck 言語を生成する次の文法
R

GD′ = ({S}, {(, )}, −→ = {(S, ε), (S, SS), (S, (S))}, S)(14)

は曖昧である．なぜなら，GD′ においては例えば () という語に対して
R

R

R

R

left

left

left

left

S −−→ SS −−→ (S)S −−→ (ε)S −−→ (ε)ε = (),
R

R

R

R

left

left

left

left

S −−→ SS −−→ εS −−→ ε(S) −−→ ε(ε) = ()

(15)
(16)

という異なる 2 つの最左導出列が存在するためである．
「ある言語が無曖昧文脈自由言語でない」という否定命題を示すための強力な道具として，言語の数え上げ関数に対する次の古典的な Chomsky-Schützenberger の定理がある．
定義 3.3 (数え上げ関数と母関数). 言語 L について，その数え上げ関数 ΓL : N → N とは

ΓL (n) ≜ #{w ∈ L | |w| = n} = #(L ∩ An )(17)で定義される関数である．言語 L について∑ΓL (n)z nn≥0で定義される 1 変数の有理数係数級数を L の母関数と呼ぶ．
定理 3.1 (Chomsky-Schützenberger(3)). 無曖昧文脈自由言語の母関数は代数関数．

(18)

19

原始語の集合と文脈自由言語についてここで言う代数関数とは，ある有理数係数 2 変数多項式 P (x, y) の根

P (x, F ) = 0(19)となる F = F (x) のことを表す．

Dyck 言語を用いて Chomsky-Schützenberger 定理の具体例を見てみよう．Dyck 言語は無曖昧な文法
R

GD = ({S}, {(, )}, −→ = {(S, ε), (S, (S)S)}, S)(20)で表現されるため，Dyck 言語の数え上げ関数は定理より代数関数になるはずである．Dyck 言語 D = GD の最初の数項を計算してみると

ΓD (0) = #{ε} = 1,

(21)

ΓD (2) = #{()} = 1,

(22)

ΓD (4) = #{(())()()} = 2,

(23)

ΓD (6) = #{((())), (()()), (())(), ()(()), ()()()} = 5,(24)

ΓD (8) = #{(((()))), ((()())), ((())()), ((()))(), (()(())), (()()()), (()())(),(25)(())(()), (())()(), ()((())), ()(()()), ()(())(), ()()(()), ()()()()} = 14.
となるが，D の母関数は代数関数

FD (z) =1−√

1 − 4z 2
2z 2

(26)

として表すことができる．実際，FD (z) を z = 0 で Tyalor 展開するとFD (z) =1−√

1 − 4z 2= 1 + z 2 + 2z 4 + 5z 6 + 14z 8 + · · ·
2z 2

(27)

となり，z n の係数と ΓD (n) の値が一致していることがわかる．無曖昧文脈自由言語と代数関数の関わりについて，より詳しくは文献 (7) を参照いただきたい．

3.2

原始語の集合の本質的曖昧性

本稿の序章で述べたとおり，原始語は語の世界における “素数” のような対象である．最初に原始語の集合

QA について次の性質
任意の素数 p について A ∩ QA = A \ {a | a ∈ A}.
p

p

p

(28)

が成り立つことを述べた．この性質を元に，QA に少し変更を加えて素数との結びつきをより顕著にしてみよう．QA と 1 文字の 2 回以上の繰り返しからなる文字列集合 {an | a ∈ A, n ≥ 2} の和の補集合 Q′A ：Q′A ≜ A∗ \ (QA ∪ {an | a ∈ A, n ≥ 2})(29)について考えてみる．任意の合成数 n = xy(x, y ≥ 1) に対して長さが n の非原始語 (|w| = x となる w に対して wy ) は存在し，素数 p に対しては性質 (28) から QA ∪ {an | a ∈ A, n ≥ 2} が長さ p の全ての語を含むため，

20

新屋良磨

Q′A の数え上げ関数は
ΓQ′ (n) = 0
A

n = 1 または n は素数

⇔

(30)

という性質を満たすことがわかる．つまり Q′A の数え上げ関数の零点の集合は (1 を含むことを除いて) 素数全体と一致するのである．
級数 F (z) =∑∞n=0 cn znにおいて，係数 cn が 0 となる n を F の消失点と呼び，消失点全体の集合を Z (F )と置くことにしよう．ある種の関数のクラスにおいては，その Taylor 展開 F (z) の消失点の集合 Z (F ) が等差数列の有限和となることが知られている．

定義 3.4 (周期的集合). 自然数 c, d ≥ 0 について {cn + d | n ≥ 0} の形でかける自然数の集合を等差数列と呼ぶ．自然数の等差数列の有限和を周期的集合と呼ぶ．

補足 3.1. 上の定義では，公差 c = 0 の場合も許しているため 1 点集合 {d} は等差数列となり，よって任意の有限集合は周期的集合となる．

定理 3.2 (Skolem-Mahler-Lech (文献 (1) を参照せよ)). 有理関数 f (z) の Taylor 展開の消失点の集合 Z (f )は周期的集合．

上述した Chomsky-Schützenberger の定理から，無曖昧文脈自由言語の母関数は代数関数となる．無曖昧文脈自由言語は正則言語との和において閉じているため，もしも QA が無曖昧文脈自由言語であれば

Q′A = QA ∪ {an | a ∈ A, n ≥ 2} も ({an | a ∈ A, n ≥ 2} が正則言語であり，無曖昧文脈自由言語は正
則言語との非交和について閉じているため) 無曖昧文脈自由言語となり，代数関数は差において閉じている
ため Q′A の母関数も代数関数となるはずである．一方 Q′A の消失点の集合は素数全体であるため周期的集合にはならない (素数は無限個あり，さらに素数の集合は無限長の等差数列を含まないため)．そのため，上述した Skolem-Mahler-Lech の定理の言明 (有理関数の消失点は周期的集合) を代数関数にまで一般化することができれば，Q′A の母関数の消失点に関する上記の考察から QA の本質的な曖昧性を示すことができる．
Skolem-Mahler-Lech の定理の一般化については，代数関数を含む広い関数クラス (ホロノミック関数) につ
いて Bell ら (2) が技術的な条件付きで一般化について成功している．完全な一般化については今後の課題である．

4

関連研究と課題

前節では原子語の集合の無曖昧性についての解説を行った．しかし，肝心の予想である「原子語の集合が文
脈自由言語ではない」は未解決である．文脈自由言語の母関数は一般に超越関数になり得るため (文献 (7) を参照せよ)，無曖昧文脈自由言語における Chomsky-Schützenberger の定理のような「否定命題に対する強力な道具」が欠けていることが，予想の解決を困難にしている原因の 1 つである．
また，予想の解決を困難にしている他の原因としてに原子語の集合が「非常に大きい」ことが挙げられる．ここで言う「非常に大きい」の意味は後で説明するが，直感的には「とても多くの語を含む」と考えてもらいた
い．文脈自由言語の否定命題に用いられる道具としては次の有名なポンピング補題がある．
補題 4.1 (ポンピング補題). 任意の文脈自由言語 L に対して，ある自然数 p ≥ 1 が存在し，|u| ≥ p となる任意の u ∈ A∗ は u = vwxyz と次の条件を満たす v, w, x, y, z ∈ A∗ に分解できる：(1)|w| + |y| ≥ 1(2)|wxy| ≤ p(3) 任意の自然数 i ≥ 0 について vwi xy i z ∈ L(31)

ポンピング補題の性質上，否定命題の対象となる言語にはあまり語が含まれていないことが好ましい．
なぜなら言語 L が非常に多くの語を含む (= 大きい) 場合，ポンピング補題の言明で保証されるべき条件(xy i z ∈ L for all i ≥ 0) が成立しやすくなるためである．実際，原始語の集合はポンピング補題で要求される性質を満たすため，ポンピング補題を用いて予想を示すことはできないのである．ポンピング補題にはさまざま

原始語の集合と文脈自由言語について

21

な拡張があるが，QA はことごとくそれらの補題をかいくぐるのである (詳しくは文献 (5) の 4 章を参照せよ)．
さて，ここで本節冒頭で述べた「QA は非常に大きい」の意味を説明することにしよう．言語 L の “大きさ”を測る尺度として「ランダムに選んだ語が L に属する確率」を表す# (L ∩ An )n→∞
# (An )µ(L) = lim(32)を用いることはしばしばある (µ(L) を「言語 L の測度」と呼ぶ)．原始語の集合 QA については性質 (28) が成り立つため，

lim supn→∞# (QA ∩ An )=1
# (An )

(33)

であることが簡単に示せるが，実際にはより詳細な解析を行うことで µ(QA ) = 1 を示すことができる．そう
いった意味で QA は「非常に大きい」のである．その他にも，(an (n ̸= 2) という形の 1 つの文字の繰り返しを除く) 全ての語は 2 つの原始語の連接に分解できる，つまりQ2A = A∗ \ {an | n ̸= 2, a ∈ A}

(34)が成り立つということもわかって (文献 (6)) おり，そういった意味でも QA は大きな集合と言える．
ポンピング補題のような否定命題に対する既存の道具では，予想を解決することはこれらの理由で困難だと思われる．今後の課題として，QA のような大きな言語においても有用な，否定命題に対する道具を開発する必要があると著者は考えている．著者はこれまで正則言語における研究を行っており，測度 1 の言語 (= 非常に大きい言語) に対する次の形の否定命題の道具を開発した：
定理 4.1 (文献 (7) を参照せよ). A 上の正則言語 L に対して，次の条件は同値：

1. L は測度 1 (µ(L) = 1)
2. ある語 w ∈ A∗ が存在して A∗ wA∗ ⊆ L
例えばこの定理によって Dyck 言語や回文の集合，さらには「素数の 1 進数表記の集合 {ap | p は素数 }」(及びこれらの補集合の言語) が正則言語ではないことが簡単に示せる (文献 (8))．
文脈自由言語は正則言語にくらべはるかに難しい構造を持っているため，正則言語の理論や道具を文脈自由言語の世界に輸入することは容易ではないが，先に述べた「大きい言語に対する文脈自由言語の否定命題のための道具」を開発するためには測度 1 の文脈自由言語に対する定理 4.1 の拡張について研究を進めていくことは重要であり，著者の課題である．
参考文献(1) Bell, J. (2005): A generalised Skolem-Mahler-Lech theorem for aﬃne varieties, Journal of the
London Mathematical Society , Volume 73, Issue 2, pp. 367–379.
(2) Bell, J., Burris, N. S., and Yeats, K. (2012): On the set of zero coeﬃcients of a function satisfying
a linear diﬀerential equation, Mathematical Proceedings of the Cambridge Philosophical Society,
Volume 153, Issue 2, pp. 235–247.
(3) Chomsky, N. and Shützenberger, M. (1963): The Algebraic Theory of Context-Free Languages,
Studies in Logic and the Foundations of Mathematics, Volume 35, pp. 118–161.
(4) Dömösi, P., Horváth, S., and Ito, M. (1991): On the connection between formal languages andprimitive words, Proc. First Session on Scientific Communication (University of Oradea, Romania), pp. 59–67.
(5) Dömösi, P., Horváth, S., and Ito, M. (2014): Context-Free Languages and Primitive Words, World

22

新屋良磨

Scientific Publishing Company Pte Limited.
(6) Reis, C. M. and Shyr, H. (1978): Some Properties of Disjunctive Languages on a Free Monoid,
Information and Control, Volume 37, Issue 3, pp. 334–344.
(7) 新屋良磨 (2017): オートマトン理論再考, コンピュータソフトウェア, 34 巻, 3 号, pp. 3–35.
(8) 新屋良磨 (2017): 言語の測度に基づく非正規性の証明技法, コンピュータソフトウェア, 34 巻, 1 号, pp.
119–124.





EDITORIAL COMMITTEE
Motoshi TANAKA (Chairperson)
Electrical and Electronic Engineering Course,
Dept. of Mathematical Science and Electrical-Electronic-Computer Engineering
Taku TAMURALife Science Course, Dept. of Life Science

Takahiro KATO
Applied Chemistry Course, Dept. of Materials Science

Akihiro NINO
Materials Science and Engineering Course,
Dept. of Materials Science

Tatsuhiro MISUMI
Mathematical Science Course, Dept. of Mathematical
Science and Electrical-Electronic-Computer Engineering

Tomihiro UTSUMI
Human-Centered Computing Course, Dept. of Mathematical
Science and Electrical-Electronic-Computer Engineering

Wataru SUGIYAMA
Mechanical Engineering Course,
Dept. of Systems Design Engineering

Mamoru TAKAHASHI
Creative Engineering Course,
Dept. of Systems Design Engineering

Satoru HINO
Civil and Environmental Engineering Course,
Dept. of Systems Design Engineering

Mamoru TAKAHASHI
Dept. of Cooperative Major in Life Cycle Design
Engineering

Manabu YAMADA
Research Center of Advanced Materials for BreakthroughTechnology

SCIENTIFIC AND TECHNICAL REPORTS
OF
GRADUATE SCHOOL OF ENGINEERING SCIENCE, AKITA UNIVERSITY
No.39
November 2018

Contents
Original Paper
Subjective Evaluation Tests on Comfortableness of Living Space by Color Controllable OLED Lighting System························································································· Motoshi TANAKA, Katsutoshi SAITO

1

Short Note
A Pitch Extraction of Percussion Sound by Generalized Harmonic Analysis with Twelve-Tone Equal Temperament·················································································································· Motoshi TANAKA

7

Reviews
Improving Performances of Three-Stage Clos Switch Networks, Part I - Back Ground and Scope of the Study       ···························································································· Hitoshi OBARA, Koloko LABSON9On Primitive Words and Context-Free Languages···················································································································· Ryoma SHIN’YA

Graduate School of Engineering Science, Akita University
Akita, Japan15

平 成 30 年 11 月 27 日
平 成 30 年 11 月 30 日
編集兼
発行者

印

印刷
発行

秋田大学大学院理工学研究科〒010-8502 秋田市手形学園町１番１号
電話（018）889-2305

刷 有限会社三浦印

刷〒010-0925 秋田市旭南三丁目７番５号
電話（018）862-2792（非売品）

平成30年11月発行

秋田大学大学院理工学研究科〒010-8502 秋 田 市 手 形 学 園 町 1 - 1
http://www.riko.akita-u.ac.jp/