On the building of optimal binary trees for spelling interfaces [Elektronische Ressource] / vorgelegt von Mikhail Tregoubov

Mikhail.Tregoubov

Sujets

• Gesundheit

Informations

• Publié par: eberhard_karls_universitat_tubingen
• Publié le: 01 janvier 2005
• Nombre de lectures: 30
• Langue: Deutsch
• Poids de l'ouvrage: 1 Mo

Extrait

On the building of optimal binary trees
for Spelling Interfaces


Dissertation
der Fakultät für Informations- und Kognitionswissenschaften
der Eberhard-Karls-Universität Tübingen
zur Erlangung des Grades eines
Doktors der Naturwissenschaften
(Dr. rer. Nat.)


vorgelegt von
Dipl.-Ing. Mikhail Tregoubov, M. Sc.
aus Moskau


Tübingen
2005























Tag der mündlichen Qualifikation: 19.10.2005
Dekan: Prof. Dr. Michael Diehl
1. Berichterstatter: Prof. Dr. Wolfgang Rosenstiel
2. Berichterstatter: Prof. Dr. Niels Birbaumer

Widmung


Im Andenken an meinen Vater, Dr. Jouri Perelmouter, den besten Vater, den man sich wünschen
kann.



Danksagung


Diese Arbeit entstand neben meiner Tätigkeit als Unternehmensberater der Accenture GmbH.

Ich möchte an dieser Stelle allen danken, die mich während dieser Zeit unterstützt und somit die
Entstehung dieser Arbeit ermöglicht haben.

Besonders danke ich von meinem ganzen Herzen meinen Eltern, vor allem meinem Vater Dr. Jouri
Perelmouter, dem ich diese Arbeit widmen möchte. Es waren meine Eltern, die mich bei der
Erstellung dieser Arbeit sowie bei der Prüfungsvorbereitung stets unterstützt, ermutigt und gestärkt
haben. Sie haben wahrhaftig diese Arbeit ermöglicht.

Mein Dank gilt in ganz besonderem Maße meinem Doktorvater Herrn Professor Dr. Wolfgang
Rosenstiel. Ich möchte ihm für seine ganz hervorragende Betreuung und Unterstützung meiner
Arbeit, Begutachtung meiner Dissertation sowie für sehr nützliche fachliche Diskussionen, wertvolle
Kritik, Hilfsbereitschaft und organisatorische Hinweise danken.

Besonderer Dank gebührt auch meinem zweiten Gutachter Herrn Professor Dr. Niels Birbaumer,
der mich insbesondere in der Anfangsphase der Arbeit sehr stark unterstützt hat. Er hat diese Arbeit
mit seinen Ideen, seiner Erfahrung und vielen fruchtbaren Diskussionen immer wieder
vorangetrieben und hat stets ein offenes Ohr für alle anfallenden Probleme gehabt.

Ferner danke ich Herrn Professor Dr. Klaus-Jörn Lange für seine Hilfsbereitschaft im Hinblick auf
meine Prüfungsvorbereitung.




Stuttgart, Oktober 2005

Mikhail Tregoubov

On the building of optimal binary trees for Spelling Interface
TABLE OF CONTENTS:
ZUSAMMENFASSUNG....................................................................................................................................... 5
1. INTRODUCTION AND MOTIVATION................................................................................................. 9
1.1. MOTIVATION ........................................................................................................................................................9
1.2. PROBLEM DESCRIPTION ......................................................................................................................................11
1.3. THESIS OUTLINE .................................................................................................................................................11
2. FUNDAMENTALS............................................................................................................................. 13
2.1. GRAPHS, TREES AND DATA STRUCTURES ............................................................................................................13
2.2. OPTIMIZATION PROBLEMS, GREEDY ALGORITHMS AND GREEDY-CHOICE PROPERTY ..........................................17
2.3. HUFFMAN CODES................................................................................................................................................17
2.3.1. Prefix codes and the cost function ............................................................................................................18
2.3.2. Constructing a Huffman code ...................................................................................................................19
2.4. BRAIN-COMPUTER INTERFACES AND BINARY AUGMENTATIVE COMMUNICATION...............................................23
2.4.1. Electric brain activity ...............................................................................................................................23
2.4.2. Brain-computer interfaces ........................................................................................................................25
3. STATE OF THE ART OF BINARY SPELLING INTERFACES ........................................................ 29
3.1. OVERVIEW OF THE EXISTING BINARY SPELLING INTERFACES, THEIR PRINCIPLES AND CHARACTERISTICS ..........29
3.1.1. The P300 brain-computer interface ..........................................................................................................29
3.1.2. The visual event-related potential brain-computer interface....................................................................31
3.1.3. The EEG brain-computer interface based upon motor imagery or cognitive tasks..................................32
3.1.4. The action potential frequency (“firing rate”) brain-computer interface ................................................34
3.1.5. The μ-rhythm based brain-computer interface..........................................................................................35
3.1.6. The brain-computer interface based upon slow cortical potentials (the Thought-Translation Device or
TTD) .........................................................................................................................................................37
3.1.7. Limitations of BCI’s, comparison of the existing BCI’s and summary .....................................................43
3.2. PROBLEM DEFINITION FOR OPTIMAL BCI’S IN TERMS OF CODING AND COMMUNICATION THEORY .....................46
3.2.1. Problem definition for a non-zero error communication..........................................................................46
3.2.2. Known approaches for a non-zero error communication problem...........................................................49
4. ALGORITHMS FOR THE OPTIMAL BUILDING (SYNTHESIS) OF BINARY SI’S ......................... 55
4.1. OPTIMIZATION CRITERION..................................................................................................................................55
4.2. DECODING OF P-SEQUENCES FOR CRITERION COMPUTATION AND THE FULL-SEARCH ALGORITHM....................58
4.2.1. Algorithm for decoding of the given P-sequence ......................................................................................58
4.2.2. The Full-Search algorithm........................................................................................................................60
4.2.3. The usage of asymmetrical features of the SI’s and the inhomogeneous algorithm .................................61
4.2.4. Comparison of the Full-Search algorithm and the inhomogeneous algorithm (example) ........................64
4.3. SYNTHESIS OF OPTIMAL HOMOGENOUS SI’S, THE AUXILIARY OPTIMIZATION PROBLEM AND THE MERGING
ALGORITHM........................................................................................................................................................66
4.3.1. Necessity for an additional algorithm in case of homogeneous SI’s.........................................................66
4.3.2. The auxiliary optimization problem..........................................................................................................68
4.3.3. The merging algorithm .............................................................................................................................69
4.3.4. Comparison of the Full-Search algorithm and the merging algorithm (incl. example)............................73
4.4. COMPUTER IMPLEMENTATION ............................................................................................................................77
4.4.1. Requirements for integrated computer tool ..............................................................................................77
4.4.2. General description of the integrated computer tool TBSIO; input and output data................................79
4.4.3. Optimization criteria and methods............................................................................................................83
5. SUMMARY AND OUTLOOK ............................................................................................................ 91
5.1. SUMMARY ..........................................................................................................................................................91
5.2. OUTLOOK ...........................................................................................................................................................93
6. REFERENCES .................................................................................................................................. 95


Page 1

On the building of optimal binary trees for Spelling Interface