Personal Navigation System for the
Visually Impaired 


By Charles M. LaPierre



A thesis submitted to the Faculty of Graduate Studies and Research in partial fulfillment of the requirements for the degree of:
 Master of Engineering







Department of Electronics
Faculty of Engineering
Carleton University
September 3, 1998


( Copyright
1998, Charles M. LaPierre 
The undersigned recommend to the Faculty of Graduate Studies and Research the acceptance of the thesis:

"Personal Navigation System for the
Visually Impaired"

Submitted by Charles M. LaPierre in partial fulfillment of the requirements for the degree of Master of Engineering.


					
Prof. J.P. Knight
Thesis Supervisor


					
Prof. R. Harrison
Thesis Co-Supervisor


					
Prof. J.S. Wight
Chair, Department of Electronics


Carleton University
1998

Abstract

The primary object of this thesis was to build a portable navigation system that would verbally speak to the visually impaired informing them of where they are currently located.  To this end, the system designed uses software run on a laptop computer incorporating synthesized voice, GIS map database of the city, positioning using GPS and DGPS, and an alternative navigation system to take over when a GPS position solution is unobtainable.  The alternative navigation system built uses a pedometer to determine distance travelled, and a digital compass to determine direction.  This system is accurate to a fraction of a block, and can guide the visually impaired to specific destinations and inform them when they have arrived.








Charles LaPierre using Strider to determine location
(photo taken by John Hryniuk / The Globe and Mail)



Acknowledgments

I would like to thank my supervisors John Knight for his technical insight, guidance, and patience while I was travelling to and from California and Robert Harrison for his expertise and guidance in my writing.

There have been a number of people who have offered technical assistance and I wish to thank them here: James McOrmond, Ken Morrison, Darren Dentremont, Jacques Lemieux, Dr. Walter Stockwell, an applications engineer at Precision Navigation Inc., and Roger Edwards whose insight saved me months of aggravation.

I would like to thank Arkenstone Inc. and VisuAide who has allowed me to bring my dream to those who need it most.

I would like to thank my grandmothers Bertha Perala, and Margaret LaPierre, all my aunts, uncles, and cousins, and a special thank you to my Godmother Aunt Heather, and thanks to my Uncle Pat who inspired me to become an engineer.

Finally, I would like to thanks my parents Charlie and Sheila for their loving support support, my sisters Amanda and Brandy, my talented brother Mark??? who has given me more than he will ever know, and my girlfriend Theresa Hamm who has supported and been there for me.


 



Table of Contents
Abstract	ii
Acknowledgments	iv
Table of Contents	v
List of Figures	ix
List of Tables	xi
Glossary	xii
Chapter 1: Introduction	1
1.1 Prolog	1
1.2 Motivation	2
1.3 The Needs of the Visually Impaired	2
1.4 Technical Overview	3
1.5 Master Objectives	4
1.6 Layout	4
Chapter 2: Background Research	5
2.1 Historical Overview	5
2.1.1 Navigational System for the Visually Impaired - Fourth-Year Project	6
2.1.2 Feasibility Study for Sextant	6
2.1.3 Atlas Speaks and Strider	6
2.1.4 Inertial Guidance System	7
2.2 Related Subject-matter	7
Chapter 3: Atlas Speaks	9
3.1 Layout of Atlas Speaks	9
3.1.1 Map Area	9
3.1.2 Message Window	11
3.2 Features of Atlas Speaks	11
3.2.1 Language Independence	12
3.2.2 Setting Explore Position	12
3.2.2.1 Specific Address	12
3.2.2.2 Destination	13
3.2.2.3 Point of Interest	13
3.2.3 Destinations	13
3.2.4 Routes	13
3.2.4.1 New Route	14
3.2.4.2 Find Route	14
3.2.4.3 Edit Route	15
3.2.4.4 Reverse Route	15
3.2.4.5 Route Status Window	15
3.2.5 Points of Interest	16
3.2.5.1 Nearest and Alphabetical Points of Interest	17
3.2.6 Voice Settings	17
3.2.7 Speech-Queuing	18
3.2.7.1 Example of the Functions called for the "Where am I" message	19
3.2.7.2 Speech-Queuing Features Continued	19
3.2.8 Atlas Options	23
3.2.8.1 Reset S/W Pedometer	23
3.2.8.2 Units and Measures	23
3.2.8.3 Serendipity	24
3.2.8.4 Key Announcements	24
3.3 Summary	24
Chapter 4: Strider	25
4.1 Layout of Strider	27
4.1.1 Map Window	27
4.1.2 Strider Message Window	29
4.1.2.1 GPS Status Window	29
4.1.2.2 Satellites Tracked Window	29
4.1.2.3 GPS Time Window	30
4.1.2.4 GPS Accuracy Window	30
4.1.2.5 Heading Window	30
4.1.2.6 Speed Window	30
4.1.2.7 Latitude and Longitude Window (Expert Mode)	31
4.1.2.8 Altitude Window (Expert Mode)	31
4.1.2.9 Satellite Information Window (Expert Mode)	31
4.1.2.10 Additional Information Window	31
4.2 Features of Strider	31
4.2.1 Automatic Route-Recording	31
4.2.2 Route-Following	32
4.2.3 Strider Settings	34
4.3 Strider Interface	35
4.3.1 GPS Specific DLL	36
4.3.1.1 Strider requests its position from the GPS receiver.	36
4.3.1.2 Strider requests current time from the GPS receiver.	37
4.4 Summary	38
Chapter 5: GPS, DGPS, and Backup Systems	39
5.1 GPS Failures	39
5.1.1 PDOP (Position Dilution of Precision) [6] [7]	39
5.1.2 Multipath Error	40
5.1.3 Line-of-Sight	41
5.2 DGPS increased accuracy	41
5.3 Position Accuracy	42
5.4 Possible Backup Systems	43
5.4.1 Measuring Distance Travelled using accelerometers	44
5.4.1.1 Pendulous Accelerometers	44
5.4.1.2 Pendulous Integrating Gyroscope Accelerometer	45
5.4.1.3 Liquid Level Accelerometer	45
5.4.1.4 Force Balance Accelerometer	46
5.4.1.5 Variable Capacitance Accelerometers	47
5.4.1.6 Force Balanced Capacitance Accelerometer	47
5.4.1.7 Problems with Accelerometers	48
5.4.2 Measuring distance travelled by Acceleration Threshold Switches	50
5.4.3 Measuring distance travelled through other means	50
5.4.3.1 Odometer Wheel	51
5.4.3.2 Shoe sensors	51
5.4.3.3 Pedometer	51
5.4.4 Determining Heading	52
5.4.4.1 Fluxgate Compass	52
5.4.4.2 Polarized Light [9e]	52
5.4.4.3 Dinsmore Digital Compass	53
5.4.4.4 Vector 2X Compass	53
5.5 Personal Dead Reckoning Module[13]	53
5.6 Alternative Navigation System	54
Chapter 6: Alternative Navigation System	56
6.1 Overview	56
6.1.1 Pedometer	57
6.1.2 Compass	57
6.1.3 Computer Connection	57
6.1.3.1 Switching Circuit (MUX)	58
6.1.4 Motorola HC705-K Microcontroller	59
6.1.4.1 Reasons for the Discontinuance of the HC705-K Microcontroller	60
6.2 Motorola HC705-J Microcontroller	61
6.2.1 Internal Clock	64
6.3 Programming the HC705-J Microcontroller	64
6.3.1 Program Design	64
6.3.2 Debouncing the Pedometer	66
6.3.2.1 Waiting for Fifteen Consecutive 5volt Levels	67
6.3.2.2 Using an Interrupt Timer and Monitoring the IRQ Line	67
6.3.3 Obtaining the Direction of Travel	72
6.3.3.1 Slave Mode of Operation	72
6.3.3.2 Calibrating the Compass	73
6.3.3.3 Clocking in and Storing the Compass Direction	74
6.3.4 Sending Data to the Computer	77
6.4 Computer Interface	78
6.4.1 Problems that Occurred	79
6.5 Summary	80
Chapter 7: Testing the Alternative Navigation System	81
7.1 Testing around a City Block	81
7.2 Testing Pedometer Accuracy	82
7.3 Testing ANS Indoors	83
7.4 Performance around Bridges	85
7.5 Summary	87
Chapter 8: Conclusions	89
8.1 Summary	89
8.1.1 Results	90
8.2 Claims of Originality	91
8.3 Benefits	91
8.4 Future Improvements	92
Appendix A: Popular Press Articles about this Project	95
Appendix B: Available Atlas Speak Functions	96
Appendix C: Speech-Queuing Interface Prototypes	99
Appendix D: Available Strider Functions	103
Appendix E: Keypad Keys	104
Appendix F: GPS Receiver's DLL Interface Prototypes	107
Appendix G: OEM 4000 Technical Specifications [16]	113
Appendix H: Lassen SK8 Technical Specifications [17]	114
Appendix I: Vector 2X Compass Specifications [12]	115
Appendix J: Assembly Language for the ANS	116
Appendix K: Pseudocode for Pedometer and Timer	127
Appendix L: Pseudocode for Calibration of the Compass	128
Appendix M: Pseudocode for Obtaining a Direction	129
Appendix N: Pseudocode for Transmitting Data to the Computer	130
Appendix O: Pseudocode for the Windows Test Program	131
References	132


List of Figures
Figure 1: Screen shot of Atlas Speaks	10
Figure 2: Route Window in Atlas Speaks	16
Figure 3: Speech Messaging Class Structure Example	18
Figure 4: Message being sent to Queue	20
Figure 5: Adding Message String to Queue	21
Figure 6: Finished Speaking, Start Speaking next String	22
Figure 7: Skip Speech	22
Figure 8: Block Diagram of the Strider Box	26
Figure 9: Screen shot of Strider	28
Figure 10: Route-following radial distance with GPS accuracy	33
Figure 11: Route-following DGPS accuracy with an Atlas Route	33
Figure 12: Strider Software Interface	36
Figure 13: Functional Block Diagram of the Atlas Speaks and Strider Software	38
Figure 14: Atmospheric Errors cause the Satellite Signal to be Deflected [8]	40
Figure 15: Multipath Error [8]	41
Figure 16: DGPS Correction [1]	42
Figure 17: Pendulous Accelerometer [9]	45
Figure 18: Pendulous Integrating Gyroscope Accelerometer [9a]	45
Figure 19: Liquid Level Accelerometer [9]	46
Figure 20: Force Balanced Accelerometer [9]	46
Figure 21: A Simplified Diagram of the ADXL05 Sensor at Rest [10]	48
Figure 22: ADXL05 Sensor Responding to an Externally Applied Acceleration [10]	48
Figure 23: Simplified Block Diagram of the Personal Navigation System	56
Figure 24: Electrical Representation of a Pedometer Step	57
Figure 25: Strider Box Layout and Communication	58
Figure 26: Switching Circuit using one package of NAND's	59
Figure 27: Switching Circuit equates to a MUX	59
Figure 28: Simplified Schematic Diagram with the HC705-K Microcontroller	60
Figure 29: Simplified Schematic Diagram with the HC705-J Microcontroller	61
Figure 30: Schematic Diagram of the Alternative Navigation System	63
Figure 31: State Diagram of the Alternative Navigation System	65
Figure 32: Main Program Flow Diagram	66
Figure 33: Pedometer Step Recorded after 15 Consecutive 5v Readings	67
Figure 34: 205 ms Delay before Registering a Step	68
Figure 35: Magnification of the Switch's Mechanical Bouncing and Delay Counter	68
Figure 36: Pedometer ISR Flow Diagram	70
Figure 37: Timer ISR Flow Diagram	71
Figure 38: Compass Interface	73
Figure 39: Data Clock Timing Diagram [12]	73
Figure 40: Computer Requests Data ISR Flow Diagram	78
Figure 41: ANS Tested around a City Block	82
Figure 42: Pedometer Testing - Steps Taken to Steps Recorded	83
Figure 43: Testing Indoors - Fifth Floor Mackenzie Building of Carleton University	84
Figure 44: Guidance System Test under an Overpass	86
Figure 45: Worse-Case: Total Error accumulated by the ANS	87
Figure 46: Best-Case: Total Error accumulated in ANS	88
Figure 47: Order of Steps Recorded	92


List of Tables

Table 1: Accuracy for Route-recording and Following	33
Table 2: GPS Accuracies Observed During Field Tests	43
Table 3: Off Axis Applied Accelerations [10]	49
Table 4: Part List for the Alternative Navigation System	62
Table 5: State Table for the Alternative Navigation System	65
Table 6: Compass Direction Mapped to Storage Array	76



Glossary
Accelerometer
A device to measure the acceleration externally applied to it. [Section 5.4]

Almanac
An Almanac contains ephemeris data on all the satellites, and a complete almanac is valid for thirty days, at which time a new almanac must be downloaded from the satellites for the upcoming month.  The GPS receiver automatically updates its internal almanac upon locking onto a GPS satellite. [Section 4.2.3]

Altitude
The current elevation from sea level that the GPS receiver is located. [Section 4.1.2.8]

ANS (Alternative Navigation System)
This was the system built to work in conjunction with Strider to provide seamless position tracking of a pedestrian. [Section 1.4]

Atlas Speaks
Atlas Speaks is a Microsoft Windows-based program for a personal computer that presents map data verbally through a speech synthesizer. [Section 1.1]

Azimuth
The number of degrees from north, that an object is positioned.  This is used in tracking where the satellites are positioned in the sky. [Section 4.1.2.9]

Cyclic Redundancy Check (CRC)
This is a byte added to the end of a data packet that is used to verify the data preceding it is valid. [Section 6.3.4]

Datum
A datum is a network of monuments and reference points defining a mathematical surface from which geographic computations can be made. [Section 4.3.1.1]

Dead Reckoning
A method of navigation based on a known starting position, and tracking distance travelled and direction. [Section 5.5]


Differential GPS (DGPS)
A system to precisely determine the location of the DGPS receiver.  This system uses a known stationary GPS receiver to track the same GPS signals as those picked up by adjacent receivers.  Using FM radio transmissions, the system transmits error corrections to those receivers. [Section 1.4]

Dynamically Linked Library (DLL)
A Microsoft Windows-based program linked in at run-time.  Atlas Speaks and Strider has two such DLL's, one for language (i.e. speech synthesis), and another for the GPS specific receiver. [Section 3.2.1]

ETAK Coverage Area Map (ECA)
This is the ETAK given name for a particular digital map which Atlas Speaks and Strider uses.  These ECA's are non-overlapping geographic regions which are complete counties or collections of complete counties. [Section 3.2.4.2]

Ephemeris
A mathematical model of where the satellites are positioned in the sky. [Section 5.1]

Geometric Dilution of Precision (GDOP)
A factor that modifies the error in the GPS position based on satellite configuration and timing. [Chapter 5] 

Geographical Information System (GIS)
A database containing map data.  In our case, this is a map of a city with important features associated with it such as house numbers, postal codes, types of roads etc. [Section 1.4]

Global Positioning System (GPS)
A system designed by the United States Department of Defense, using satellites to locate one's position on the earth. [Section 1.1]

Header
This is the first byte sent in a data packet, which the computer uses to synchronize itself with the data coming in.  [Section 6.3.4]

Interrupt Request (IRQ)
An IRQ is a request to service a particular hardware device or update a specific section of the program.  When an IRQ occurs the appropriate ISR will be called to service the request. [Section 6.1.4]


Interrupt Service Routine (ISR)
An ISR is a section of code that will service a particular interrupt request.  [Section 6.1.4.1]

Least Significant Bit (LSB)
The LSB is the right most bit in a binary number.  For Example 00000001, 1 is the LSB. [Section 6.3.3.3]

Line-of-sight
In order for the GPS receiver to receive signals from the satellites, it must have an unobstructed view to them.  Objects such as tall buildings and bridges can block the line-of-sight needed by the receiver to obtain a position solution. [Chapter 5]

Multipath error 
Errors caused by the interference of a signal that has reached the receiver antenna by two or more different paths.  This is usually caused by one path being bounced or reflected. [Section 5.1.2]

Packet
A grouping of data sent through the RS-232 comm port .  The Packet length in this case is 20 bytes, consisting of a header, 18 data bytes, and a CRC trailer byte. [Section 6.1.3]

Pedometer
A device used to count the number of steps a person takes. [Section 1.4]

Points of Interest
"Points of Interest" are specific locations on a map such as public buildings, monuments, parks, and landmarks. [Section 2.1.3]

Position Dilution of Precision (PDOP)
A positioning of the satellites with respect to the GPS receiver that modifies the error in the GPS position solution. [Section 4.1.2.1]

Position Solution
When the GPS receiver is tracking three or more satellites, a location or position solution can usually be calculated.  This position solution is the location of the receiver. [Section 4.1.2.2]

Request to Send (RTS)
The laptop's RS-232 port has a RTS that the computer will lower when it wants the ANS to transmit its data over the RS-232 link.


Route
A Route is a path to a specific destination made up of a number of waypoints. [Section 2.1.3]

RS-232
RS-232 is a standard defined an asynchronous serial communication method.  Data is transferred to and from the computer through a comm (communication) port that uses this RS-232 method of communication.  [Section 6.1.3]
 
Serial Data Output (SDO)
This is the data pin of the Vector 2X digital compass.  A sixteen bit binary number representing a heading in degrees is clocked-out through this pin. [Section 6.3.3.1]

Selective Availability (S/A) 
A policy adopted by the Department of Defense to introduce some intentional clock noise into the GPS satellite signals thereby degrading their accuracy for civilian users. [Chapter 4]

Signal-to-Noise Ratio (SNR)
A measure of the quality of the signal strength the GPS receiver receives from a satellite. [Section 4.1.2.9]

Serendipity
Serendipity is a name given to the automatic presentation of "Points of Interest" while traveling. [Section 3.2.8]

Strider
Strider is the Atlas Speaks program with additional hardware running on a laptop computer.  It provides position information and tracking using GPS and DGPS receivers.  This information is verbally spoken to the pedestrian through synthesized speech. [Section 1.1]

Universal Asynchronous Receiver-Transmitter (UART)
A UART is the programmed microchip that controls a computer's interface to its comm port.  It provides the computer with the RS-232 interface so that it can "talk" to and exchange data with other serial devices. [Section 6.2]

Waypoint
A Route is made up from a number of waypoints, which break up the route into smaller segments. [Section 3.1.4.1]


Chapter 1: Introduction
1.1 Prolog
Imagine yourself unable to read the street signs, and you are late for a job interview.  You frantically ask for directions but no one can help.  This is what happened to me the summer of 1992.  That was the day I decided to help the visually impaired by building a device that would tell them what street intersection they are standing at.  By December of that year I had built a device using GPS, a laptop computer and a voice synthesizer to verbally tell me what Carleton University street intersection I was standing at.  This was my fourth year project at Carleton. 
I went on to enter a number of competitions including the Ontario Engineering Competition (OEC), APEO papers night, and IEEE papers night.  Placing first in the paper nights, and winning the "Social Awareness Award" from the OEC, I received a lot of press and was interviewed by a number of Carleton papers, The Citizen, and by CJOH Midday Report channel 7.
Unknown to myself, two not-for-profit companies Arkenstone Inc., California and Visuaide 2000, Montreal, independently came up with the same design.  Visuaide was asking Industry Canada for development money to build this device, and because of the press I had received, my name was given to Visuaide since I had already built such a device.  During that summer of 1993, Visuaide hired me to do a feasibility study for Industry Canada to justify the $250 000 grant awarded.
In January of 1994, an arrangement between Arkenstone and Visuaide was done to jointly co-develop Sextant (the name of this project).  Since I had built a working prototype and being the only engineer with extensive GPS experience, I was hired by Visuaide to work in California at Arkenstone for six months.  While working at Arkenstone I was taught commercial C programming by Bruce Merritt the senior Engineer at Arkenstone.  Bruce took me under his wing, and helped me with Windows-based programming, and I helped clarify some of the intricacies of GPS.  While working at Arkenstone, I built the portable GPS system, which they used in demonstrations to potential investors. 
After this six-month period I returned to Canada, continuing with my Masters, but worked effectively full time as a consultant to Arkenstone.  In November of 1995, a patent was granted to Arkenstone, and I was included as one of the developers of the system.
For the past four years, I have been working for Arkenstone, and was central in the development of Atlas Speaks and Strider (formerly known as Sextant).  Atlas Speaks is a home-based talking map system.  Strider is the mobile position-tracking system to help guide the visually impaired through the streets of a city.  My contributions in the software development of the systems are shown in Fig. 13. 
1.2 Motivation
In our visually dominated world, those less fortunate have an incredible time just walking to the corner store to pick up some milk.  The visually impaired don't need our pity, but do need our help to give them the ability to walk independently in our cities without the fear of getting lost.  They do not want to have to rely on others around them to guide them if they are disoriented.  Many of those who are visually impaired are afraid to venture out on their own in a city to which they have never been.  For these reasons research on guiding pedestrians though the maze of city streets is being conducted, and a solution to this problem will be presented in this thesis.

This research will give the visually impaired this ability to explore new cities free from feelings of apprehension or anxiety.  Not only will this give the visually impaired the confidence and independence to travel, but is one step closer to complete independence.
1.3 The Needs of the Visually Impaired
Those without the benefit of sight must build a mental map of their surroundings.  They travel this map without ever seeing what is actually around them.  They listen for cues, and use their other senses to determine where they are.  They use tactile information from their cane to keep them on the sidewalk, and/or their seeing-eye dog to guide and keep them safe.  They are taught to count streets, and are trained how to use the cane and/or seeing-eye dog efficiently.  

In today's society of social independence, the visually impaired are severely shortchanged.  The visually impaired, like everyone else want independence without going bankrupt in the process.  In addition, information is key in today's electronic age.  The visually impaired deserve access to this information like everyone else. Maps are not available for the visually impaired, and access to maps, in a format that they can use, is essential.  They also need to be able to obtain this geographical information while travelling outside, and the system to be used must be unobtrusive, lightweight, and affordable.
1.4 Technical Overview
The system being described started as a fourth-year project1 by the author, and this led to Strider, a system the author has developed in cooperation with VisuAide2, Montreal, and Arkenstone Inc., California.  These are non-profit organizations devoted to developing tools which allow universal access to information.  Strider consists of software running on a laptop computer, an electronic GIS map of a city, a voice synthesizer, a GPS (Global Positioning System) receiver, and a DGPS (Differential Global Positioning System) receiver.  This system will track the user and inform them of where they are currently located.  As it stands, the current system has problems.  When GPS fails the user is assumed to be at their last known position, even after they have departed from that location.  In the final work represented by this thesis, an alternative system has been designed using an electronic compass to determine direction of travel, and a pedometer for measuring distance travelled.  This ANS (Alternative Navigation System) will continually track the user and when GPS fails, will become to the primary navigational system.
1.5 Master Objectives
This thesis is part of a master objective for building a complete personal guidance system, which would guide pedestrians and in particular the visually impaired though the streets of a city.  To this end, this system consists of three main components:
(1) Audible access to map information, and the tools for utilizing this information.
(2) The ability to travel outside and know one's position.
(3) An alternative guidance system as a backup when the primary guidance system fails.
1.6 Layout
The general layout of this thesis is as follows:
* Chapter 2 describes the background research that has gone into this thesis.

* Chapter 3 describes Atlas Speaks, which is the first component of the thesis.   It provides audible access to map information, and the tools to utilize it.

* Chapter 4 describes Strider the second component of the thesis, implements mobile positioning for a pedestrian.

* Chapter 5 investigates the potential flaws of Strider and offers a solution to these problems.

* Chapter 6 describes the third component of the thesis, the ANS that was built.

* Chapter 7 outlines the tests ANS underwent. 

* Chapter 8 summarizes the thesis, and presents its findings.

Chapter 2: Background Research
Considerable research has been conducted on accurately guiding those who are visually impaired through a city without the aid of another person.  Currently the visually impaired have guide dogs and white canes to help keep them safe and help guide them to their destination.  The problem with this is, the person being guided must accurately know their route in order to tell the guide dog where they wish to be taken.  This limits the visually impaired to only those routes that they have memorized so as not to get lost.  When such a person wishes to go to a new destination, they must rely on others to guide them to their destination.  They have just lost their independence, they have to rely on another person to tell them this information because they cannot see the street signs which sighted people take for granted.  The research that the author has conducted, will in no way replace the guide dogs or canes, but will add to, and work in conjunction with them.  This will give the person the ability to explore their neighborhood and feel confident that they will not get lost.  
2.1 Historical Overview
As partial fulfillment of an undergraduate program at Carleton University, a fourth-year project entitled "Navigational System for the Visually Impaired" was designed by the author.  This project showed the potential for a commercial product, and received a lot of press because of the social impact of such a device.  Some of these publications include GEO, New Scientist, and Discover; a number of articles written about this report can be found in Appendix A.  From there, this project grew, and two companies decided to build such a product, VisuAide, Montreal, and Arkenstone, California.  The project was nicknamed "Sextant", and a Feasibility Study was done to determine the best hardware solution for the product as well as any potential pitfalls.  From there the design of Sextant began at Arkenstone, and two potential products were developed, "Atlas Speaks" the talking map for a personal computer, and "Strider" the mobile talking map with GPS (Global Positioning System) positioning.
2.1.1 Navigational System for the Visually Impaired - Fourth-Year Project
In 1993 a fourth-year project by the author was done using GPS (Global Positioning System), a computer with an electronic map database, and voice synthesis to communicate to the user the street intersection at which they are currently standing.[1]  A number of awards, papers, and articles relating to this project, are referenced in Appendix A.  The objective of this fourth-year project, which is the genesis of this thesis, was to help those who are visually impaired navigate independently and accurately in an unfamiliar environment.

The main concerns addressed in the fourth-year project were the size and weight of the unit, as well as obtaining accurate digital maps of the city.  These concerns will be discussed later.
2.1.2 Feasibility Study for Sextant
In the summer of 1993, a feasibility study was conducted by the author on Sextant; formerly known as the Navigational System for the Visually Impaired.  The study focused on the hardware selection for Sextant so that it could become a viable product.  Additionally it investigated any potential problems with the design.

An important finding from the feasibility study was the need to have a secondary navigational system when GPS fails.[2]  The reasons why GPS fails, and the potential solutions will be looked at in detail in Chapter 5.
2.1.3 Atlas Speaks and Strider
Work on Atlas Speaks and Strider (formerly known as Sextant) began in 1993 and continued through 1997 at Arkenstone.  In November of 1995, a United States Patent (No. 5,470,233) was granted to the author, Arkenstone, VisuAide, and the other inventors for a "System and method for tracking a pedestrian".  

The author's personal contribution to Atlas Speaks includes the speech-queuing software, route and route finding, map overlays in the form of "Points of Interest", and making Atlas Speaks accessible through Braille.  Strider was entirely designed, prototyped, and programmed by the author.

Atlas Speaks 1.0 was released to market by Arkenstone in February of 1996.  Atlas Speaks 1.5 was released December of 1997.  Work on Strider coincided with Atlas Speaks but a product is still not available due to lack of funding, hardware problems and the absence of a reliable backup system for GPS.  Work done by the author as part of this thesis on Atlas Speaks and Strider will be covered in Chapters 3 and 4.
2.1.4 Inertial Guidance System 
In 1994 a fourth-year project at Carleton University entitled "Inertial Guidance System" was conducted by another student3.  It was based on the author's 1993 project "A Navigational System for the Visually Impaired".  A potential flaw in the navigational system occurs when a GPS position cannot be obtained, as will be outlined in Chapter 5.  This fourth-year report3 explored different ways of overcoming this deficiency, and recommended a solution to this problem.  In Chapter 5, these alternatives are discussed, and the final solution is arrived at.  This ANS has been designed, built, and tested.  This alternative system completes the product, allowing a person who is visually impaired the ability to travel outside unattended without the fear of getting lost.
2.2 Related Subject-matter
Since GPS was introduced over ten years ago, a number of applications using GPS has been developed.  GPS navigation in automobiles helps direct the driver to their destination while providing a map of their surroundings.  The system can incorporate speech for easy access to important information, especially when following a route while driving.  GuideStar from Oldsmobile and OnStar from Cadillac are two such systems[3].  Here too, GPS is not the only system that is used to track the automobile.  Integration of GPS/DGPS systems with an inertial guidance system is required for continuous tracking.  By using the odometer of the car, distance travelled can be extracted, and by using either an electronic or magnetic compass and/or turn rate gyroscope, direction can be realized[4].  The personal navigation system developed in thesis is similar to the system found in some of today's luxury vehicles, except that it is person-based, and relatively inexpensive.  


Chapter 3: Atlas Speaks
Atlas Speaks provides people with visual disabilities access to street map information that would be otherwise unavailable to them. It is a "talking map" that runs on a home computer.  It allows such people to find their way around their own neighborhood, or any city in the United States.  It will soon be available for cities in Canada.  In Fig. 13, a block diagram of the software shows how all of its components are related to each other.
3.1 Layout of Atlas Speaks
The physical layout consists of a main screen containing the map that the user is currently exploring, and a smaller bottom screen containing address specific information as well as other important information.  See Fig. 1 for the physical screen layout of Atlas Speaks.  A graphical representation of the map, as well as an audible representation, is provided for those who have low vision and use screen-enlargement technologies to access the program.  Drop-down menus are used with the aid of cursor keys to move through the menu items, and as each item is highlighted, the menu item is announced to the user.
3.1.1 Map Area
The map area displays the map that the user is currently "travelling over".  The user can travel this virtual map using the cursor keys.  The up key moves the Atlas cursor forward, right and left to turn to the next available street on the right or left accordingly, and the down key is used to "undo" the last move the user has made.  The Atlas cursor is a pie shaped icon that floats transparently over the map, but is fixed to the streets of the city.  Atlas Speaks uses maps and the map display software from ETAK Inc., a United States map company.  ETAK supplies digital maps for the entire United States, and as soon as an agreement can be reached with Statistics Canada, maps for Canada will be available for Atlas as well. The detail level of the map is scalable using the plus (+) and minus (-) keys, so that the user can either zoom into a specific block, or zoom out to see the entire city, region, state, or province.   As the user travels along the city streets and reaches the border of the screen, the map automatically pans, and the user is placed at the center of the screen at their new position. 


Figure 1: Screen shot of Atlas Speaks
3.1.2 Message Window
The message window or bottom screen contains address information as well as other important information that the user may require.  As seen in Fig. 1, Address, Heading, and Trip information is provided.  The information presented in this window can also be accessed through assigned keys.  By pressing these keys the program will announce the information contained within this window.  For example, the "a" key could be programmed to find out the current address the user is at, or the "c" key used to obtain cross street information.  The "Ins" key is pre-assigned to be the "Where am I" key, this gives address, cross street information as well as any other information the user needs.  Appendix B contains a list of all available functions from which the user can pre-program the keys.  The lower half of the message window is the ongoing audit-trail of speech that has been spoken to the user.  This is a three-line history of the latest items spoken.
3.2 Features of Atlas Speaks
It has a number of powerful features that allow the user to fully explore the current map, as well as the ability to switch maps easily.   It has the ability to create and automatically find routes to a specific destination.  The user can also add detail to the map through a "Point of Interest" file, to which they can add any number of important places they wish to annotate, and be informed of while travelling the map.  Atlas Speaks will guide the user along pre-created routes, and will inform them when they have reached a "Point of Interest". It always tells the user what it is about to do, and advises the user of any problems it encounters.  The most important features of Atlas Speaks will be outlined in this chapter.
Since Atlas Speaks is run on the user's home computer, it has the built-in option of using a number of different commercial voice synthesizers.  

Products such as Zoomtext(tm)4 or Window-Eyes(tm)5 can also be used in conjunction with it.  These products are screen enlargement and navigational programs that are needed by the visually impaired to use Windows-based programs.  Atlas Speaks also offers the ability to use a Braille display to obtain the data being spoken.  This not only accommodates those who prefer using Braille, but also those who are both visually impaired and deaf to explore city maps.
3.2.1 Language Independence
All messages and text spoken to the user are language independent.  A separate file called a DLL (Dynamically Linked Library) has all of the spoken messages contained within it.  Therefore, when Atlas Speaks is converted to another language just a single DLL needs to be translated for the new language.  It is important to note that the voice synthesizer to be used must support the language contained within the DLL.  I.e. if the message strings in the DLL are in French then the synthesizer must be able to "speak" French as well.
3.2.2 Setting Explore Position
This feature allows the user to set their "explore" position in a number of different ways:
* Specific Address
* Destination
* Point of Interest.

3.2.2.1 Specific Address
By entering any address, the user can instantly be moved to a new location, provided that the corresponding map is on the hard drive or CD-ROM.  The user can enter a street address and Atlas will search the current map looking for that address.  If the address is not found the system will inform the user, telling them what further information is needed, such as the cross street, city, and maybe even the state.
3.2.2.2 Destination
This option is used to set the current position to the active destination (covered later in this chapter).  This function is helpful when the user wants to explore the area surrounding the destination. 
3.2.2.3 Point of Interest
Setting one's position to a "Point of Interest" is useful if the user wants to explore the area around a public building or tourist attraction, but does not know the address.  This is also useful for learning more about the neighborhood surrounding personal "Points of Interest", such as shopping areas, schools, and the homes of friends and family. 
3.2.3 Destinations
In addition to allowing users to set a starting position, it also lets them set a destination.  This destination is given both a visual flag and audible announcement.  When the user arrives near their destination, it says, "arrived near destination," and then gives the name of the current destination.  Setting this destination works in the same manner as setting one's "explore" position, as in section 3.2.2. 
3.2.4 Routes
The power of Atlas Speaks is clearly shown by its ability to create, find, and edit routes.  "Routes" allows the user the ability to enter predetermined paths to a destination.  Not only can it record these paths but it also has the ability, given a destination, to find a "pedestrian" path to that destination.  A path generated for a motorized vehicle will make use of one-way streets and freeways.  Routes for a pedestrian must be chosen in such a way as to avoid freeways.  However, pedestrians can walk the wrong way along a one-way street.  Atlas-generated routes also provide turn-by-turn information when guiding the user along these routes.  For Example: "Turn at nine o'clock onto Bank Street facing northwest".  From the Atlas menu, the following route-specific options are available to the user:
* Choose and Close a Route
* New Route
* Find Route
* Edit Route
* Reverse Route
* Import and Export  Routes
* Route Directions.

3.2.4.1 New Route
When creating a new route the system starts at the current position, and asks for the name of the new route being created.  It then records all cursor movements as a part of the route.  It will place a waypoint at every intersection.  These waypoints will appear as red circles on the screen. 
3.2.4.2 Find Route
This is one of the more important features Atlas Speaks offers to those who are visually impaired.  This allows them to find a path between their current position and a destination.  Also since a "destination" may not necessarily be a specific address but can also be a "Point of Interest", this can be very handy tool in exploring new cities.  When it finds a route to a destination, the path created may not be the shortest possible one because it does not use limited-access streets while pathfinding, since such streets would be dangerous for pedestrians.  Limited-access streets are those reserved for cars only, such as on and off ramps, freeways etc.  It will even span ECA's (ETAK Coverage Area Maps) while pathfinding, if the destination is on a different map.

"Find Route" has three limitations:
1. Atlas cannot calculate routes longer than eight kilometers.  This limitation will be addressed in future revisions of Atlas Speaks.  For a long route, the user could break it up into smaller sections that are each less than eight kilometers long.

2. The "Find Route" function is also limited in areas where streets are densely packed, due to memory constraints on the user's system.

3. Atlas may also have trouble calculating routes when the only available road is a freeway.

3.2.4.3 Edit Route
"Edit route" is a useful but potentially dangerous option.  When editing a route, the user can not only rename the waypoints along the route but can also delete and add waypoints to the route.  

When Atlas creates a route the street name and cross street information constitute the name of each waypoint along the route.  Sometimes it is useful to change the information. For example, the route endpoint could be "Bob's House" instead of "35 James St.".
 
The user is also allowed to change the "Turn" information.  When Atlas follows a route it beeps at each physical turn the user must make, and informs the user that a change in direction has occurred, and that they are now on a new street.  This turn information is presented to the user as a "clock face" change in direction.  E.g., "Turn at 9 o'clock onto Sunnyside facing west."  Instead, the user may only wish to hear "Turn left onto Sunnyside."  The user can also add information to a given waypoint, to be heard upon arrival.  For example, "a mailbox is located here", or "the sidewalk is narrow here".
3.2.4.4 Reverse Route
Once the user has reached the end of the route, they may wish to travel the route from the end to the beginning without having to create a new and separate route.  Reversing the route not only renumbers the waypoints starting at the end-point and proceeding to the beginning of the route, but changes all turn information accordingly, such that the user will hear the correct turn information for the reversed route.
3.2.4.5 Route Status Window
When a route is active, as shown in Fig. 2, the bottom screen is modified to display route information to the user.  The previous, current, next, beginning and ending waypoints are all displayed as well as the user's distance and bearing to each of them.  All of the information displayed can also be obtained through key presses, and verbally spoken to the user.  It is also important to note that this information on the bottom screen is available using a Braille display connected to it.

Figure 2: Route Window in Atlas Speaks
In this example, the "Heading" type is degrees, and the units are imperial, these can be modified as will be shown later in this chapter.
3.2.5 Points of Interest
"Points of Interest", are specific locations on a given map that may have some relevance to the user.  Atlas comes with a set of pre-determined "Points of Interest", such as public buildings, monuments, parks, and landmarks.  The user may also add their own "Points of Interest", such as stores, restaurants, bus stops, or homes of friends and family.  From the menus, the following "Points of Interest" options are available:
* Load & Close Points of Interest
* Nearest and Alphabetical Points of Interest
* New Points of Interest File
* Add Point of Interest
* Import and Export Points of Interest File.

3.2.5.1 Nearest and Alphabetical Points of Interest
"Nearest Points of Interest" provides a listing of all the "Points of Interest" in the currently opened file, and displays them in order of proximity to the Atlas cursor.  Not only does it indicate how far away each point is from the cursor, but it will also tell its direction in relation to the cursor.  "Alphabetical Points of Interest" does the same thing except they are arranged in alphabetical order.  The user is allowed to scan these "Points of Interest" listening to the name, distance and bearing of each, and may select one.   Once selected the user can edit, deleted, rename, or set the "Point of Interest" as the current position, or destination.
3.2.6 Voice Settings
Atlas Speaks does not have an internal voice synthesizer.  Instead, it uses the synthesizer on the user's system.  Atlas is flexible in that it currently supports over thirty different voice synthesizers.  Each voice synthesizer is different and may not offer all the features that Atlas can modify by means of the "voice settings" menu.  Atlas queries the voice synthesizer and only allows modification to those features supported by the synthesizer.
The options available to the user include:
* Speaking voice
* Volume
* Speaking rate, pitch, and tone
* Amount of punctuation spoken
* Speech off.
The speaking voices that are offered by some synthesizers may include male, female, child, and robot voices.  The user can decide which voice is aesthetically pleasing.  Setting the rate of the speaking voice is crucial for those who are visually impaired.  The user gets accustomed to the voice and over time can understand the speech at an increased rate.  Setting the volume, pitch and tone, help to fine-tune the speech.  Punctuation level allows the user to specify how much of the punctuation is spoken from Atlas.  Usually the synthesizers offer three choices: Speak All, Speak Some, and Speak None.  The more advanced synthesizers will also add voice inflections to denote the type of punctuation passed.
3.2.7 Speech-Queuing
Atlas Speaks uses synthesized speech to communicate with the visually impaired, and therefore queuing up of messages to be spoken is essential.  Messages to be spoken are divided up into specific classes6 and subclasses.  Fig. 3 shows an example on how this class structure is organized.











Figure 3: Speech Messaging Class Structure Example
Appendix C contains a complete listing of the function prototypes for the speech-queuing software.  In this example the "Where am I" message contains three "subclasses" of messages, but four actual messages.  When the user asks Atlas "Where am I", the system will queue up all four messages, but because of this class structure the user has control over what is to be spoken.  
3.2.7.1 Example of the Functions called for the "Where am I" message
For the example in Fig. 3, the following function from Appendix C would be called:
SPEECH_priority(yes this is a newclass, not a priority, don't pause after, regular voice, don't spell out the message, CLASS A, Subclass a)
SPEECH_add(Street Address)

SPEECH_priority(not a newclass, not a priority, don't pause after, regular voice,
don't spell out message, CLASS A, Subclass b)
SPEECH_add(City)
SPEECH_add(State)

SPEECH_priority(not a newclass, not a priority, don't pause after, regular voice,
don't spell out message, CLASS A, Subclass c)
SPEECH_add(Current Heading)

3.2.7.2 Speech-Queuing Features Continued
If the user presses the "Where am I" key twice for example, the queuing software will flush the first "Where am I" messages, and only speak the last set of "Where am I" messages.  The speech-queuing software also has a unique ability to skip a message: this is the SPEECH_skip feature as given in Appendix C.  This prevents the current message from being spoken, and deletes all messages starting from the beginning of the queue, with the same class and subclass, until either a new class or subclass is found.  This next message is then spoken immediately.  One other option is the "Shutup-key", which empties the speech queue and immediately terminates the current message being spoken.  By pressing the "Shutup-Key", SPEECH_flush would be called from Appendix C.

Using the example from Fig. 3, if the user presses the skip-message-key while Atlas is speaking the "Where am I" message the following would result.  The current street address would stop speaking, and then it would start speaking the current city because the city message is not in the same subclass as the current street address.  Now if the user presses the skip-message-key again it would stop speaking the current city, skip the state message because it is the same subclass as city, and then start speaking the current heading message.

The queuing software also incorporates the concept of a "priority message".  This message is not added to the end of the queue like other messages but is placed at the head of the queue, and is the next message spoken once the current message being spoken is finished.

Some of the attributes of a message string are its class, subclass, and priority.  Refer to Appendix C: SPEECH_priority for a complete listing of a message's attributes.  A flowchart of the speech-queuing software is presented in figures 4 through 7.  The design and implementation of the speech-queuing software was completely done by the author.






Figure 4: Message being sent to Queue













Figure 5: Adding Message String to Queue














Figure 6: Finished Speaking, Start Speaking next String







Figure 7: Skip Speech
Note: this will call "Finished Speaking" from Fig. 6, because the synthesizer has finished speaking.
3.2.8 Atlas Options
Here the user can change a number of different options affecting how Atlas Speaks will behave.  These options include:
* Reset S/W (Software) Pedometer7
* Units and Measures
* Serendipity
* Key announcements.

3.2.8.1 Reset S/W Pedometer
The pedometer keeps track of the distance travelled while moving the Atlas cursor around the map.   As shown in Fig. 1, the "Leg" and "Trip" pedometers of Atlas Speaks are displayed in the Message Window.  Both a "Trip" and a "Leg" pedometer are reset upon using this feature.  The pedometer is useful to determine the distance between streets, and routes that one might wish to travel outdoors.
3.2.8.2 Units and Measures
Atlas Speaks was designed keeping in mind both the metric and imperial systems of measure.  By changing the system of measure, all units in Atlas Speaks will change accordingly.
It also offers different methods for describing directional information.  These include:
1. Clock Face
2. Degrees
3. Compass
4. Relative.
"Clock Face" and "Relative" both describe headings to a specific point or destination in relation to the actual cursor heading.  "Degrees" and "Compass" are absolute directions and are not dependent on the direction of the cursor.


"Clock Face" will present directional information in terms of the numbers on a clock.  With 12 o'clock being straight in front of the cursor, 6 o'clock being behind the cursor etc.    "Degrees" will present the direction from 0 through 359 degrees, with 0 degrees being TRUE north.  "Compass" will present directions in a format of north, south, northwest, etc.  "Relative" is a unique way of describing a specific location, as a human would describe it: ahead, behind, ahead and to the left, etc.
3.2.8.3 Serendipity
"Serendipity" is a mode in Atlas that automatically informs the user that they are approaching a "Point of Interest". Using the "Serendipity" function, Atlas can announce all "Points of Interest" within a certain distance.  This function is useful because the user does not have to constantly ask for the distance and heading to the nearest "Point of Interest".  When turned on, Atlas will announce a "Point of Interest" when it comes within the specified distance from the cursor.
3.2.8.4 Key Announcements
Atlas can provide a tremendous amount of information, and it allows for modifications to the keys that access this information.   So for example, the 'C' key can be modified to provide the current city, cross street, or both.  Refer to Appendix B for a complete listing of all available Atlas functions.  
3.3 Summary
Atlas Speaks fulfills the first part of this thesis, audible representation of map data and the tools to access this information.  Next, we must make this portable, so a person who is visually impaired can walk outside with it and get current positional information of where they are located.  This mobile Atlas will be investigated in Chapter 4 with Strider.




Chapter 4: Strider
Strider is a mobile Atlas Speaks, it runs on a portable computer that has attached to it a "Strider Box".  The Strider Box consists of a GPS receiver, DGPS (Differential Global Positioning System) receiver, and a power supply. Fig. 8 shows a block diagram of the Strider Box.  DGPS is a method for improving the accuracy of GPS. It will be discussed in Chapter 5. The laptop computer, along with the Strider Box, a hand-held keypad, and an earphone - fits into convenient carrying case, usually carried as a backpack. The user can switch between Atlas Speaks virtually exploring a map, to Strider that actually tracks the user's path outside.  Strider is an orientation tool to help navigate not a mobility tool.  It will not replace the white cane or guide dog, but it does offer new information for the visually impaired that was previously unavailable.  Along with their own personal mobility skills, and other aids such as a cane or guide dog, Strider offers the ability to explore streets and cities, which might not otherwise have been accessible. 

Strider works by using the GPS satellites to triangulate its position.  A small antenna sewn into the shoulder strap of the backpack picks up the satellite signals, and the GPS receiver decodes them.  Triangulation of the user's position occurs as soon as three or more satellites are being tracked.8  The accuracy of this location is then increased using the DGPS receiver.  The DGPS receiver has a thirteen-inch whip antenna carried inside the backpack that receives radio broadcasts from a differential corrections company.  These radio transmissions correct for the inherent accuracy degradation S/A (Selective Availability) in the GPS system, which was introduced by the U.S. Department of Defense.    Using DGPS increases the accuracy from (100 meters to less than (4 meters.  This will be covered in more detail in Chapter 5.  Once the GPS receiver has the differentially corrected position, it sends this to the Atlas Speaks software, which places the Strider cursor at the new location.  When the user switches from Atlas to Strider all information requested is then in reference to the Strider cursor instead of the Atlas cursor.  When the system is in Strider mode and position information is requested, Strider produces the exact location, rather than the virtual location previously explored with Atlas.  The author developed the device drivers for Strider, which allows it to communicate with a number of different GPS and DGPS receivers.  Fig. 13 shows a block diagram of the Atlas Speaks and Strider software.




















Figure 8: Block Diagram of the Strider Box
4.1 Layout of Strider
The physical layout of Strider consists of a main screen containing the same map area as Atlas Speaks, which the user is "physically" on, and a smaller bottom screen containing address specific information, and details of the GPS connection.  Fig. 9 shows the physical layout of Strider. Drop-down menus are used with the aid of cursor keys from the keypad to move through the menu items, allowing the user to utilize the diverse tools that Strider offers while travelling outside.
4.1.1 Map Window
The map area in Strider displays the map that the user is currently on.  A star shaped cursor follows as the user's position changes.  The GPS receiver tracks the user, and a cursor is put on the map indicating the corresponding position.  The Atlas cursor may also appear on the Strider Map if the user is currently located in the same area as the one being explored.

Figure 9: Screen shot of Strider 
4.1.2 Strider Message Window
The Strider message window contains a lot of detailed information about the GPS and DGPS receivers.  The Strider message window consists of a Novice Window, an Expert Window (which can be turned off) as well as the audit trail.  All information presented in this window is available to the user through key assignments, these are presented in Appendix D.  The GPS information presented in this window is extracted from the GPS receiver, and is the real time status of Strider.  
4.1.2.1 GPS Status Window
The status of the GPS receiver is displayed in this window.  When Strider is working correctly its status is "Tracking Position", but when Strider cannot obtain positional information this window will inform the user why it cannot provide this information.  The following are messages that can appear in this window:
* Tracking position
* No GPS time
* Error PDOP9 too high
* Acquiring satellites
* No usable satellites
* 1 usable satellite
* 2 usable satellites
* Unknown.
4.1.2.2 Satellites Tracked Window
This gives the number of satellites that the GPS receiver is currently tracking.  However, it does not indicate how many or which satellites are being used in the receiver's position solution.  As the number of satellites being tracked increases, the increased chance for obtaining correct positional information occurs.  This will be discussed further in Chapter 5.
4.1.2.3 GPS Time Window
This is a very accurate clock, which the receiver uses to synchronize itself with the satellites.  This information can be presented in the following formats: AM/PM, 24 Hour, or UTC (Co-ordinated Universal Time).
4.1.2.4 GPS Accuracy Window
The accuracy of the GPS receiver is not only based on the number of satellites currently being tracked, but the status of the DGPS receiver, and a number of other dependencies which will be covered in Chapter 5.  The following are messages that may appear in this window:
* Unknown		Bad 
* GPS 2D		Poor
* GPS 3D		Fair
* DGPS 2D		Good
* DGPS 3D		Excellent.
The user can select, through the menus, which types of messages are to be heard.  The GPS messages will be explained in the next chapter.
4.1.2.5 Heading Window
Since the current Strider configuration does not contain a compass, the "Heading" information is not the current heading the user is facing.  It is however a least-squares average of the last x number of positions.  Therefore if the user is travelling west, and then turns 90 degrees towards north, and asks Strider the direction to a specific point, this information will be based on the previous direction of travel and not the current physical heading.  This shortcoming will be examined and solved with the ANS.  The units of this heading are always in degrees.
4.1.2.6 Speed Window
The instantaneous speed of the user is presented here.  This information can be presented in a number of different formats depending upon which system the user is using, i.e. meters per second, Kilometers per hour, feet per second etc. 
4.1.2.7 Latitude and Longitude Window (Expert Mode)
The Latitude and Longitude of the current position is displayed in these windows.  This is for advanced users, who find this information interesting.  Since this information is used to place the cursor on the map, the user may obtain this information if so desired.
4.1.2.8 Altitude Window (Expert Mode)
The GPS receiver also can determine the altitude of the user if the current accuracy is a 3-D solution.  This requires at least four visible satellites.  The units of this information again depend upon the system of measure chosen by the user.
4.1.2.9 Satellite Information Window (Expert Mode)
The satellite number, signal-to-noise (SNR) ratio, elevation, and azimuth are all presented here for those advanced users who wish to know this information.  This could be useful if the accuracy suddenly dropped and the user wanted to find out the reason.
4.1.2.10 Additional Information Window
When the user has an active destination or is using "routes", additional information concerning these features will also be displayed in this message window. 
4.2 Features of Strider
All the features of Atlas Speaks are also accessible when using Strider as well as a few others.  These features are accessed through the external keypad that the user holds while traveling outdoors.  A mapping of the functions available on the keypad is presented in Appendix E.  The most important features with Strider deal with routes, and automatic messages that indicate changes in GPS accuracy.  The user has full control over what is to be automatically spoken, and Strider has built-in protection against "twitching".  I.e. if the accuracy switches constantly between two different levels, the user is not bombarded with useless information.
4.2.1 Automatic Route-Recording
This allows the user, while travelling outside, to lay down a route automatically without manually creating the route.  Strider will place waypoints along the path travelled by the user.  The user can specify the frequency of these waypoints by a set distance and/or time factor.  The software is also smart enough not to keep placing waypoints at a given point if the user hasn't moved, and is recording waypoints every x seconds.  The user, while automatically recording a route, can also place a waypoint manually.  This is useful if it is necessary to cross a street, or change directions to follow a new street.
Strider will also not record waypoints if it is no longer tracking the user's position, or if the accuracy is bad.  If the accuracy improves while recording a route, the last waypoint recorded will be re-recorded with the better accuracy and new position, thus improving the accuracy of the route.

While route-recording automatically, Strider will not allow waypoints to be bunched together if the accuracy degrades.  As shown in Table 1 there is a minimum radial distance that surrounds the user with a given accuracy.  This radial distance is the inaccuracy in the current position, and therefore the user's actual position can be anywhere inside this circle.  Consequently, it doesn't make sense to keep dropping waypoints within this radial distance because when route-following, the system would announce all of these waypoints simultaneously. 
4.2.2 Route-Following
When following routes, a number of different things can happen, depending upon how the route was created.  An Atlas-created route is very precise.  It follows the streets in a city, and the accuracy is exact.  It also has "turn" information available.  Following such a route with Strider is usually quite easy.  When following a Strider-created route, both the current accuracy of Strider and the accuracy of the waypoints when the route was created come into play.  When the route is being loaded, Strider will determine the accuracy of all the points in the route and tell the user how accurate the route is.  It will also identify any potential problems that may occur when following the route.  Strider will also automatically determine the correct radial distance between the user and the waypoint on the route before it informs them they have reached that specific waypoint.  This radial distance is based upon the accuracy of the specific waypoint and the current accuracy of Strider.  These distances are important to note and are shown in Table 1.
Table 1: Accuracy for Route-recording and Following
Accuracy
Distance (meters)
GPS
100
DGPS
4
MAP
0

Therefore, if the current accuracy is GPS and the accuracy of the waypoint on the route is also GPS the total radial distance before the waypoint is announced to the user would be 200 meters, as shown in Fig. 10.  It is also important to note here that if the route was created by Atlas, i.e. "MAP" accuracy, when following this route with Strider, only the current accuracy of Strider determines the radial distance.  For example, if the current accuracy is DGPS and the waypoint was created by Atlas, then the minimum distance the user needs to be before Strider announces that the waypoint has been reached would only be 4 meters, as shown in Fig. 11.




  



Figure 10: Route-following radial distance with GPS accuracy




Figure 11: Route-following DGPS accuracy with an Atlas Route
4.2.3 Strider Settings
Strider allows the user to turn off the "expert" message window.  The "expert" window contains technical information such as latitude, longitude, altitude, and information about the satellites being tracked.  By turning off the "expert" window, the size of the map increases accordingly. 

The GPS specific messages Strider displays can be technical in nature and a novice user would find them uninformative.  Strider offers the ability to change these messages from "expert" to "novice" messages.  For example, instead of saying that the GPS accuracy is "DGPS-3D", under "novice" messages it would say that the GPS accuracy is "excellent".  This was shown in section 4.1.2.4.

When Strider is first turned on, it must initialize itself, and start scanning for satellites before locking onto three or more satellites and positional information is obtained.  A process that can either be very quick, or a quite lengthy procedure.  Strider allows the user to set User Warnings that automatically provide the Strider status during the initialization process as well as during position tracking.  All of these warnings can either be enabled or disabled.  The following is a list of these warning messages.

GPS Almanac Bad - This informs the user that the GPS receiver currently doesn't have an up-to-date almanac of where the satellites are in orbit, which means that the time to find and track satellites will take longer.
Time to GPS Fix - This is an estimated time that Strider will take to start tracking the user's position.  This time is based upon the almanac status as well as other factors such as the number of satellites already being tracked.
Position Tracking - This informs the user when Strider is tracking its position as well as when it loses its position.  There are a number of factors affecting whether or not the GPS receiver is tracking the user's position.  These will be discussed in Chapter 5.
Satellite Configuration Error - This is one such reason why Strider may not be able track the user's position.  This will be covered in Chapter 5 as well.
Differential Correction Gained - When Strider gains DGPS corrections the accuracy improves dramatically, and the user may want to be notified when this happens so a more accurate position can be determined.
 Differential Correction Lost - Here too the user may wish to be informed when the accuracy is dramatically degraded so that address information will not taken literally when the position can be out by 100 meters.
Accuracy Improved or Degraded - When the accuracy improves or is degraded, this information can be helpful for the user to make a more informed decision on whether or not to accept at face value the positional information Strider is providing.
4.3 Strider Interface
As shown in Fig. 13, the Strider interface connects Atlas Speaks and Strider to the GPS receiver's DLL (Dynamically Linked Library).  This interface takes requests from Strider and extracts the requested information from the GPS receiver through the GPS receiver's DLL.  The GPS receiver can offer a variety of GPS specific information which can be requested such as altitude, latitude, longitude, current speed, etc.  Fig. 12 shows the flow diagrams on how this interface works.

















Figure 12: Strider Software Interface
4.3.1 GPS Specific DLL
The GPS specific DLLs all have the same Strider Interface function calls, but each has a different protocol to extract the data from its specific GPS receiver.  See Appendix F for a complete listing of the function calls to the GPS Receiver's DLL.  These functions were designed and implemented exclusively by the author.  Here are a couple examples of how this interface works as was shown in Fig. 12.
4.3.1.1 Strider requests its position from the GPS receiver.
* A function call is made to the Strider Interface (Update_Position)
* Then a call is made to the GPS Receiver's DLL (GpsPosition) (As found in Appendix F)
* The GPS DLL sends back the Latitude and Longitude
* Conversion is made from WGS8410 that the GPS receiver sends, to NAD2711 which is the datum ETAK uses for its North American Maps.
* These new Latitude and Longitude values are then sent back to Strider, and the new position is displayed.

4.3.1.2 Strider requests current time from the GPS receiver.
* A function call is made to the Strider Interface (Get_Time)
* From the Interface module a call is made to the GPS Receiver's DLL (GpsTime) (as found in Appendix F)
* The GPS DLL sends back the time as the number of seconds since midnight Saturday
* Conversion is made to the actual time based on the user settings (AM / PM, UTC (Co-ordinated Universal Time), 24 Hours)
* This is then sent back to Strider.
























Figure 13: Functional Block Diagram of the Atlas Speaks and Strider Software
The shaded areas in the above figure are the specific software modules the author personally developed. 
4.4 Summary
Strider fulfills the second objective of this thesis, the ability to walk outside and know one's position.  Chapter 5 will discuss why the Strider system, as it stands, is incomplete, and will investigate possible backup systems for Strider.

Chapter 5: GPS, DGPS, and Backup Systems
GPS is a powerful tool for locating one's position.  GPS was designed and implemented by the United States Department of Defense for military use.  They allow civilians to use the system, but at a reduced accuracy.  This reduced accuracy is called S/A (Selective Availability).  This reduces the accuracy from (5 meters to (100 meters.  There have been lengthy debates about S/A, and whether it should be turned off.  Currently this issue is being debated in the United States Congress.  A method for getting improved accuracy is called DGPS or Differentially-Corrected GPS.  This not only eliminates the S/A error but also any static errors introduced by the satellite signals entering earth's atmosphere.  Differential-correction companies offer a number of different services, from a basic service offering ( 4-meter accuracy to the premium service at (1-meter.  

The problem here is that GPS needs a direct line-of-sight to all satellites that are used in its position solution.  When satellites are blocked by tall buildings, trees, bridges, etc. GPS loses its lock on the satellites and its position is unknown.  Another type of GPS failure occurs when the satellites are positioned in such a way that an accurate position solution is unobtainable.  This is known as a PDOP (Position Dilution of Precision) error.  

When GPS loses its position for whatever reason, a backup system is needed to keep tracking the person.  Without a secondary guidance system, the user is presumed to be at the last known position. 
5.1 GPS Failures
5.1.1 PDOP (Position Dilution of Precision) [6] [7]
Dilution of precision (DOP) is a measure of the quality of the GPS data being received from the satellites.  DOP is a mathematical representation for the quality of the GPS position solution.  The main factors affecting DOP are the number of satellites being tracked and where these satellites are positioned in the sky.  The most common DOP factor is position dilution of precision (PDOP).  PDOP is an error indicator of the physical positioning the satellites have to triangulate the position being calculated.  Geometric dilution of precision (GDOP) error is another factor in the error calculation made up of PDOP and satellite timing.  A PDOP value of 1 indicates a good satellite constellation and high-quality data, PDOP values above 8 are considered poor.  The quality of the data decreases as the PDOP value increases.  This PDOP value is then multiplied by the total error inherent in the system.  The total error of the system is made up of satellite clock error, ephemeris error, receiver errors, ionospheric errors and S/A (Selective Availability).  Atmospheric error is shown in Fig. 14.  The GPS status message in Strider "PDOP too high" corresponds to those PDOP values which are above 8, and an overall accuracy greater than 100 meters.  When Strider receives PDOP values greater than 8 it can no longer track the user and the Strider accuracy becomes "BAD". 

Figure 14: Atmospheric Errors cause the Satellite Signal to be Deflected [8]
The path of the satellite signal is assumed to be a straight line. When atmospheric disturbances cause the signal to be deflected the path is no longer a straight line. As well, the Ionosphere causes the signal to be delayed.  This increases the time the signal takes to get to the GPS receiver, and thus reduces the accuracy in the position solution calculated by the receiver. 
5.1.2 Multipath Error
Multipath error occurs when the path the data takes from the satellites is not direct and is reflected to the GPS receiver.  This can be clearly seen in Fig. 15 showing the reflection of the satellite signal off mountains, a car and a building.  Since the GPS receiver makes use of the time interval between transmission of the signal and its reception at the GPS receiver, the additional reflection delay causes an error in the position calculation.




Figure 15: Multipath Error [8]
5.1.3 Line-of-Sight
When the GPS antenna does not have a direct line-of-sight to at least three satellites, a GPS position solution is unobtainable.  Experimentation has shown that on the streets of downtown Toronto, position fixes are only obtainable at street intersections because of the tall buildings on either side of the street.  In its present configuration, Strider has only GPS and DGPS receivers, so that accurate data is unavailable at locations away from intersections.  Furthermore, direction-of-travel information is severely restricted, since it is based on the last x positions received as was discussed in section 4.1.2.5.
5.2 DGPS increased accuracy
By placing a stationary GPS receiver at a known location that has been surveyed, this receiver can calculate the error in the GPS position solution and then transmit this error correction to other DGPS receivers in the area.  The DGPS receivers acquire these error correction messages and corrects the position solutions as seen in Fig. 16.  This concept works because the satellites are so far above the earth that errors measured by one receiver will be almost exactly the same for any other receiver in a given area. This correction factor not only corrects S/A but will also reduce other static errors such as ionosphere, timing, and atmospheric errors.


Figure 16: DGPS Correction [1]

With the aid of a DGPS receiver and the differential corrections from the reference receiver, the accuracy of GPS improves to less than 4 meters.  With this improved accuracy, Strider can inform the visually impaired the exact address of the house that they are currently standing in front of.  Without the DGPS accuracy, Strider could place the user a block away from the actual location.  Even with this improved accuracy, the whole system fails when the GPS receiver cannot obtain a position solution.  Therefore, a backup system for GPS must accompany Strider for this to be a viable product for the visually impaired.
5.3 Position Accuracy
The accuracy of the location given by the GPS receiver is based upon a number of factors as was previously discussed.  The GPS receiver could in fact be tracking six or more satellites but a position fix may not be obtainable because of the satellite's physical position in the sky, being blocked by a building, etc.  When the GPS receiver is using three satellites to determine a position solution, GPS-2D accuracy is obtained.  This means that no altitude information will be available and the overall positional accuracy is reduced.  When the GPS receiver is using four or more satellites to determine a position solution, GPS-3D accuracy is obtained.  The altitude of the receiver is available and an increase in the overall accuracy is achieved.  This increased accuracy is achieved because the GPS receiver can use the satellites that offer the lowest PDOP values in its position solution.  When this position is then differentially-corrected these 2D and 3D accuracies become DGPS-2D and DGPS-3D.  The differential accuracy is also dependent upon which service the user has.  Table 2 presents the different GPS accuracies that have been observed during field-testing, with a differential quality of (1-meter offered by the OEM 4000 DGPS receiver manufactured by DCI (Differential Corrections Incorporated), and using the Lassen GPS receiver manufactured by Trimble Navigation Incorporated.  See Appendices G and H for the technical specifications of the DGPS and GPS receivers respectively. 

Table 2: GPS Accuracies Observed During Field Tests
Name
Accuracy (meters)
GPS-2D
100
GPS-3D
80
DGPS-2D
3-5
DGPS-3D
1-2

5.4 Possible Backup Systems
A 1994 fourth-year project[9] by Dentremont, at Carleton University entitled "Inertial Guidance System" was conducted based on the 1993 project "A Navigational System for the Visually Impaired".  It investigates a backup system for the 1993 project.  A number of different possible solutions were looked at and rejected mainly based upon size, weight, and cost.  These possible solutions will be summarized here.  The primary findings from this 1994 project was a backup system containing either an accelerometer or a threshold switch for measuring distance travelled, and a compass for measuring direction of travel.
5.4.1 Measuring Distance Travelled using accelerometers
By integrating the acceleration of the user twice, distance travelled can be obtained using an accelerometer.  There are a number of different ways for measuring an acceleration, each of which has its own particular advantages and disadvantages.  The following summarizes the main accelerometers researched in the 1994 project[9].  The following sections 5.4.1.1 through 5.4.1.5 are based on the 1994 fourth-year project[9].
5.4.1.1 Pendulous Accelerometers
A pendulous accelerometer is based on the principle that acceleration displaces a mass m and the angle ( the mass is displaced from rest can be used to determine acceleration, see Fig. 17.  The problem here is the ability to accurately measure such a small angle ( of displacement.  A person-based accelerometer would be measuring accelerations well below a g12, and friction would cause serious degradation to the accuracy of this accelerometer.  The pendulous accelerometer has not been designed because of these reasons, but the principles behind it are used in other designs.









Figure 17: Pendulous Accelerometer [9]
A pendulum is being used to determine the acceleration being applied to it.
5.4.1.2 Pendulous Integrating Gyroscope Accelerometer
The basic principle behind this accelerometer is its utilization of torque.  The torque of the gyroscope is used to counter the torque cause by the pendulum and the acceleration applied to it, which is proportional to the acceleration of the unit.  A diagram of this accelerometer is shown in Fig. 18.  The range of accelerations it can measure is quite high and its cost is also high.











Figure 18: Pendulous Integrating Gyroscope Accelerometer [9a]

5.4.1.3 Liquid Level Accelerometer
Liquid placed in a U-tube can be used to measure the displacement difference when the liquid in the tube is subjected to an acceleration.  Under an acceleration in the x direction as shown in Fig. 19, the liquid in the U-tube will move and the difference in height from rest can be used to calculate the applied acceleration.  The difficulties with this type of accelerometer include (a) the cost of adding accurate detectors, (b) an integrator to determine the acceleration and (c) a way of canceling out the effect of the up and down motion, which is inherent while walking. 








Figure 19: Liquid Level Accelerometer [9]

5.4.1.4 Force-Rebalance Accelerometer
A force-rebalanced accelerometer uses a mass that is connected to a damper and a spring as shown in Fig. 20.  When an acceleration is applied the mass is displaced.  Using the distance the mass moved and knowing the damper and spring constants, the acceleration can be calculated.  The cost of such an accelerometer increases as the acceleration to be measured decreases, and for a person walking the accelerations in question are in the milli-g range.  These accelerometers are mainly used to measure rocket launches, and other high g acceleration applications.









Figure 20: Force-Rebalanced Accelerometer [9]
5.4.1.5 Variable Capacitance Accelerometers
Three silicon elements are bonded together to construct a capacitive device.  The three elements form a pair of air-dielectric parallel-plate capacitors.  Two electrodes form the top and bottom elements, and the middle element is a base common to the two capacitors.  The base is chemically etched to form a rigid central mass that is suspended by a thin flexible membrane.  As an acceleration is applied, the base plate is deflected resulting in an uneven change in capacitance between the two capacitors.  The supporting electronics convert this differential current to an output voltage that is proportional to the applied acceleration[9b].
5.4.1.6 Force Balanced Capacitance Accelerometer
Analog Devices has designed this accelerometer the ADXL05 on a single monolithic IC[10] that is capable of measuring accelerations in the milli-g range. "It contains a polysilicon surface micro-machined sensor and signal-conditioning circuitry which implements a force-balance control loop."[10]  "The differential-capacitor sensor consists of independent fixed plates and central plates attached to the main plate that moves in response to an applied acceleration."[10]  A capacitive divider with a common central plate is formed by the two capacitors connected  in series.  At rest the values of the two capacitors are equal, and therefore, the voltage output at their center plate is zero.  When an acceleration is applied the common central plate moves closer to one of the fixed plates resulting in a difference in separation between the two capacitors.  This creates a mismatch in the two capacitances, resulting in a signal at the central plate.  Refer to Fig. 21 and Fig. 22 for this accelerometer at rest and under an applied acceleration respectively.  The output amplitude of the signal varies directly with the amount of acceleration experienced by the sensor[10].











Figure 21: A Simplified Diagram of the ADXL05 Sensor at Rest [10]








Figure 22: ADXL05 Sensor Responding to an Externally Applied Acceleration [10]

5.4.1.7 Problems with Accelerometers
Four things would normally prevent the use of accelerometers for a person-based inertial navigational backup system.  The ADXL05 addresses three of these concerns but fails to solve all concerns.  The accelerometers discussed previously were either too large, too expensive, or were not accurate enough to measure the small accelerations which a person would experience while walking.  The ADXL05 accelerometer does solve all of these concerns.  Being silicon based it is light weight, relatively inexpensive and can accurately measure down to 5 milli-g accelerations.  The problem with this and all accelerometers is that it will not only measure the acceleration that is applied by the user when beginning to move forward but may also contain acceleration due to the earth's gravity.  If the accelerometer is not exactly horizontal, it will contain a component of the earth's gravity in its acceleration calculation.  Table 3 shows the off-axis applied accelerations which will affect the sensor.

Table 3: Off Axis Applied Accelerations [10]
(x
% of Signal at Output
0o
100
1(
99.98
2(
99.94
3(
99.86
5(
99.62
10(
98.48
30(
86.60
45(
70.71
60(
50.00
80(
17.36
85(
8.72
87(
5.25
88(
3.49
89(
1.7
90(
0

A 1-degree variation off the horizontal will result in a 0.02% reduction in the applied acceleration, but more importantly also results in a 1.7% increase in acceleration from another axis, namely the acceleration due to gravity.


For example suppose a person starts walking and the accelerometer is off 1-degree from horizontal towards the earth.  The acceleration of the person starting to walk is 200 milli-g's.  Then:
Error = [(person's acceleration) x (1-degree off axis factor) + 
(earth's gravity) x (89 degree off axis factor)] - (person's acceleration)

= [0.200 m/s2 x 0.9998 + 9.814 m/s2 x 0.017] - 0.200 m/s2 
= [0.199996 + 0.16677] - 0.200
= 0.167 m/s2 (or an error of 83%).

It can also be concluded that over time this error compounds as the accelerometer continues to be off by even a degree.  The user can be stopped with no acceleration and the accelerometer will still be influenced by the earth's acceleration.  The only way to compensate for this error is to place the accelerometer exactly horizontal using gyroscopes.  This not only would be too costly but would also increase the weight of the unit dramatically.  For this reason, the use of accelerometers for inertial navigation was abandoned, and other means for measuring distance travelled were investigated.
5.4.2 Measuring distance travelled by Acceleration Threshold Switches
An alternative to an accelerometer would be an acceleration switch.  This threshold switch would complete an electrical circuit when the switch is subjected to an acceleration.  There are a number of different designs from a mass pressing against a spring which make contact with two pins at a given acceleration, to a mercury switch making contact with a sensor at a given acceleration.  These switches are inaccurate and would only be a "guesstimate" of the actual acceleration of the user.  A variation of the acceleration threshold switch will be looked at in section 5.4.3.3.  
5.4.3 Measuring distance travelled through other means
Since we are only concerned with distance travelled, we can ignore acceleration and concentrate on measuring the physical distance the user travels.
5.4.3.1 Odometer Wheel
If the user had a wheel they dragged while they walked down the street, the wheel revolutions could be counted and the distance travelled by the user could be calculated by knowing the revolutions and the circumference of the wheel.  This is in fact how a car determines its distance travelled.  Unfortunately, this principle cannot be used since it would be inconvenient for the visually impaired to have to drag this rolling wheel while walking around.  Even if the wheel was attached to the white cane, the visually impaired do not push the cane along the street.  Instead they continuously tap the cane from side to side as they walk.
5.4.3.2 Shoe sensors
It is conceivable that if a pair of sensors were attached to the user's shoes, that these sensors could determine the number of steps the user has taken and then transmit this information to the personal navigation unit.  This method for determining number of steps taken theoretically could be very accurate.  Having a wire up the leg of the person would be unacceptable, and the amount of engineering time and cost to create a wireless system would be too expensive, not to mention making the person wear these sensors on their footwear.  
5.4.3.3 Pedometer
A variation of the acceleration threshold switch in section 5.4.2 is the pedometer.  This very simple device counts the steps a user makes as they walk.  A spring-balanced weight makes contact with a pin as the user takes a step.  This connection completes an electrical circuit that signals the navigational unit indicating a step has taken place.  A pedometer not only is accurate in counting steps a person takes while walking but also is quite inexpensive in the range of $10 to $20.  Since pedometers are inexpensive, lightweight, accurate and readably available, this is what has been chosen to measure the distance travelled in the ANS as part of this thesis.

Calibration of the user's stride length can be done without "physically" measuring it.  Since we have DGPS to track the user, the system can calibrate itself while the user walks.  For example if the user walks 10 meters as recorded by the Strider system, and the pedometer records 20 steps taken, the stride length would be 0.5 meters/step-taken.  Then when GPS fails, for each step the user takes, 0.5 meters will be associated with it.  In addition, whenever DGPS accuracy is obtained re-calibration of the stride length may occur.
5.4.4 Determining Heading
As the pedestrian takes a step, a heading must be associated with that step.  The two data components (i.e. step and direction the step was taken) are essential for pedestrian tracking.  Different methods for determining direction of travel will be discussed here, and one will be chosen as part of the ANS.  The following sections 5.4.4.1 through 5.4.4.3 are based on the 1994 fourth-year project[9].
5.4.4.1 Fluxgate Compass
A fluxgate compass is a coil of wire wrapped around a metallic bar as would be found in a transformer.  This wrapping is excited by an alternating current, which induces a voltage in a second coil.  This induced voltage can be picked off amplified and converted to an electrical signal.  The level of the voltage will be influenced by the magnetic field passing through the device.  In the north - south plane the magnetic field will have the greatest effect on the voltage, and therefore in the east - west plane the least effect on voltage.  Current consumption of the device and cost are the two main problems with this solution.[9c, 9d] 
5.4.4.2 Polarized Light [9e]
Polarized light was investigated since bees use it to navigate, and an experiment with simple Polaroid's was inconclusive.[9]  It appeared that considerable development and expensive photo sensors would be needed, and it was unlikely that the resolution that could be obtained would be accurate enough for this application.  Using polarized light would also only work during the day, and outside.  This is considered unacceptable and was not investigated any further.
5.4.4.3 Dinsmore Digital Compass
  This compass uses a freely pivoting magnet and "Hall-effect" sensors to determine the position of the magnetic bar.  Four such sensors are used, positioned equally around the magnet, and they can determine the four main directions (north, south, east and west) in which the magnetic bar is pointing.[9]  When the magnet is positioned between sensors, this too can be determined thus giving additional four positions (northeast, southeast, southwest, and northwest).  Therefore, only eight directions can be accurately determined, i.e. a 45-degree resolution.  An analog version of this compass is available producing a sin/cosine output that offers a higher degree of accuracy but its cost is comparable with the digital Vector 2X Compass covered next.
5.4.4.4 Vector 2X Compass
The Vector 2X compass made by Precision Navigation Incorporated uses an inductive magnetometer to determine the direction the compass is pointing.  This technology uses two inductive coils aligned perpendicular to each other to measure the X and Y components of the earth's magnetic field.  These two components can then be used to determine the earth's magnetic north compared with that of the compass's reading.  The Vector 2X compass determines magnetic north to be the direction for which the X-axis field is at its maximum and the Y-axis field is at zero.  Simple trigonometry can then be used to determine with a high degree of accuracy the direction of the compass.  The Vector 2X compass is lightweight, small, consumes very little power, and has a 1-degree resolution with 2-degree accuracy.  The unit cost for this compass is $50 U.S., and can be digitally connected to a microprocessor very easily.  This compass was incorporated in the personal guidance system for determining direction of travel.  Specifications for the Vector 2X Compass can be found in Appendix I.
5.5 Personal Dead Reckoning Module[13]
Point Research Corporation of Santa Ana, California has developed a lightweight miniature Dead Reckoning Module (DRM) for drift-free navigation by personnel on foot.  The DRM has been built for military use.  It uses a solid-state 3-dimensional compass and an electronic pedometer.  The pager-sized module also includes a barometric altimeter and a temperature sensor.  GPS can be connected to this module, and when GPS is available, the module will blend the data with the "Dead Reckoning" data using a Kalman filter.[13]  It provides continuous navigation solution through many buildings, in canyons, or other areas where the GPS signal is compromised.  The electronic pedometer is implemented using tri-axial accelerometers.  The 3-dimensional compass uses a tri-axial arrangement of magnetometers providing a three dimensional vector of the earth's magnetic field relative to the platform.[13]

Since this was built for military use, the system is very expensive but is extremely rugged and quite accurate with an error of approximately 2% of the distance travelled when GPS is unavailable.  Ideally, this would be perfect for this ANS except it costs $2 500 US per unit, this is an unacceptable expense for a alternative to GPS.  Point Research Corp. is planning to make a civilian model of the DRM, which will reduce the price but may still be too expensive for this particular application.
5.6 Alternative Navigation System
The ANS (Alternative Navigation System) chosen consists of a mechanical pedometer for determining distance travelled and the Vector 2X compass for determining the direction of travel.  A Motorola microcontroller coordinates and collects the data from the pedometer and compass, and transmits this information to the laptop computer.

The alternate guidance system must be accurate, lightweight, small, and affordable since this will be used by the visually impaired.  The cost of the components chosen will total less than $100, the size and weight of these devices are also acceptable.  Weighing less than a couple hundred grams and all components could fit of a circuit board approximately 5cm x 5cm.  The accuracy of the system is acceptable, as will be shown in Chapter 7.

It is important to point out here that essentially the same idea of using a pedometer and compass as an alternative to GPS, has been developed for military use, as was shown in section 5.5.  The system proposed here might be less accurate but costs under $100 where as the personal dead reckoning system for military use costs $2 500.


Chapter 6: Alternative Navigation System
As was shown in Chapter 5, GPS navigation is not perfect, even with DGPS correction the system cannot always track a pedestrian.  A reliable backup for the primary navigational system must be incorporated into the design.  To this end, research on a practical and accurate system has been conducted, and is presented here.
6.1 Overview
A revised diagram of the Strider Box, showing the incorporation of the ANS is presented in Fig. 23.  As was described in Chapter 5, the pedometer and digital compass were chosen because they are inexpensive, lightweight, accurate and readably available.  The switching circuit was added because the computer that will be used may not have enough ports to handle the GPS, DGPS, voice synthesizer and the ANS.














Figure 23: Simplified Block Diagram of the Personal Navigation System
6.1.1 Pedometer
When the pedometer makes contact with the spring, which is connected to +5 volts, the voltage at the microcontroller will fluctuate due to the bouncing inherent with mechanical switches.  This is shown in Fig. 24.  Debouncing of this switch will be done through software. 










Figure 24: Electrical Representation of a Pedometer Step
6.1.2 Compass
The Vector 2X digital compass by Precision Navigation Inc. is connected to the I/O (Input / Output) pins of the microcontroller, and the clocking of the data stream from the compass is done through software.  The data being clocked in is a 16-bit Binary number that ranges from 0 through decimal 359, indicating the direction in degrees the compass is facing.
6.1.3 Computer Connection
As it stands Strider has a laptop computer with a voice synthesizer plugged into it, a keypad for access to the system, and a Strider Box (with GPS and DGPS contained within).  The Strider Box is plugged into the laptop's RS-232 comm port, and the voice synthesizer, depending upon the type, can plug into the PCMCIA slot, parallel port, second RS-232 port (if available), or could be software driven.  The ANS must not take up an additional port because we do not know which port the voice synthesizer will use.  Therefore, the system must be connected in series with the Strider Box and the laptop computer.  A first attempt at the new Strider Box layout and packet communication is shown in Fig. 25.











Figure 25: Strider Box Layout and Communication

The original idea of a buffer for combining GPS and ANS packets as shown in Fig. 25 was abandoned once the microcontroller was chosen.  The idea of filtering and integrating the two packet streams was examined but because the laptop computer through software could combine the two data streams, this seemed to be the best solution. The new design integrates the two packet streams with a physical switching circuit as was shown in Fig. 23.
6.1.3.1 Switching Circuit (MUX)
The switching circuit is a four 2-input NAND-gate configuration with a single control line, and two controllable data lines.  When the computer signals the ANS to send its data, the microcontroller will toggle the control line of the switching circuit.  This prevents the GPS receiver from transmitting, and allows the ANS to transmit its data over the same RS-232 connection.  Fig. 26 shows the NAND gate configuration, which was implemented, and Fig. 27 shows what this circuit equates to with a MUX.







Figure 26: Switching Circuit using one package of NAND's





Figure 27: Switching Circuit equates to a MUX
6.1.4 Motorola HC705-K Microcontroller
Initially the Motorola HC705-K series microcontroller was used in the ANS because it was readily available, and since it contained an EPROM that could be reprogrammed a number of times during the debugging and testing phase of development. This microcontroller was very limited: With only 512 bytes of ROM, and 32 bytes of RAM which included stack space, programming it was very difficult.  The HC705-K had one IRQ (Interrupt Request) line, and ten programmable I/O lines.  A simplified schematic diagram showing the original design is shown here in Fig. 28.













Figure 28: Simplified Schematic Diagram with the HC705-K Microcontroller

6.1.4.1 Reasons for the Discontinuance of the HC705-K Microcontroller
Problems arose due to the memory constraints of the HC705-K microcontroller.  Since there were only 512 bytes of ROM space and only 32 bytes of RAM, trying to keep the program within these limits was difficult, and eventually impossible. The memory required to store the steps in a given direction took 18 bytes of RAM, with a resolution of twenty degrees, i.e. 360(degrees) / 20(degree resolution) = 18.  In addition, 5 bytes of RAM was taken up for the ISR (Interrupt Service Routine), which only left 9 bytes of RAM for the entire program.  To improve memory usage, variables were used more than once, and all eight bits of the variables were used to keep state.  There was a trade off with RAM and ROM, as RAM efficiency increased the amount of ROM space used also increased, and before long there was no memory left.  There were also problems with the number of interrupts for this microcontroller.  With only one interrupt, steps were missed while either sending data to the computer, or receiving data from the compass.  
Due to all of the EPROM erasing and reprogramming, one of the pins broke off the microcontroller, and instead of trying to repair it, it was decided to move up to the next series of this microcontroller.  The HC705-J series microcontroller was chosen with 1024 bytes of ROM and 64 bytes of RAM, and up to five IRQs.  In addition, since it is the same brand of microcontroller, all of the code written for the HC705-K microcontroller would run on the HC705-J microcontroller.
6.2 Motorola HC705-J Microcontroller
The schematic diagram shown in Fig. 28 was revised with the new microcontroller.  A simplified schematic diagram is shown in Fig. 29.  Additional features were added because of the increased number of I/O and IRQ lines.  The microcontroller now has complete control over the compass, as well as an interrupt-driven switch for calibrating the compass externally.  Both the computer request line and pedometer are now interrupt-driven.  Neither the HC705-K nor the HC705-J microcontroller contain a UART (Universal Asynchronous Receiver-Transmitter), so all data sent to the computer had to be manually clocked out through software, details on this will be described in section 6.3.4.












Figure 29: Simplified Schematic Diagram with the HC705-J Microcontroller 

A complete schematic diagram is shown next in Fig. 30. Table 4 contains the component values for the schematic diagram.
Table 4: Parts List for the Alternative Navigation System
Component
Value
Component
Value
VIN
+12 volts
C1
27 pF
XTAL
4.00 MHz
C2
27 pF
Bat1
3.6 volt
C3
10 (F
T1
LM340T5
C4
0.01 (F
D1
1N4148
C5
10 (F
D2
1N4148
C6
10 (F
D3
1N4148
C7
10 (F
R1
5 K(
C8
10 (F
R2
5 K(
C9
10 (F

The ANS currently runs on 5 volts, and draws 9mA.  This results in a power consumption of 45mW.









Figure 30: Schematic Diagram of the Alternative Navigation System

There are still a few shortcomings with the HC705-J microcontroller.  With only an 8-bit signed accumulator and X-register; many temporary variables had to be used.  When an interrupt occurs, polling of the IRQ line and Ports A0 through A3 had to be done to determine which IRQ line caused the interrupt.  The internal timer of the microcontroller cannot be reset, it is either on or off, and when it is turned on it doesn't reset itself.  Therefore, if the timer is set to cause a software interrupt every 8.2 ms, when the timer is first turned on the first interrupt could happen any time from 0 through 8.2 ms. 
6.2.1 Internal Clock
The internal clock of the microcontroller is set by the on-chip oscillator.  This oscillator is set by the external crystal oscillator or fosc at 4.00 MHz, as shown in Fig. 30. The frequency fosc of the external oscillator is divided by two to produce the internal operating frequency fop at 2.00 MHz.[14]
6.3 Programming the HC705-J Microcontroller
Due to the limited memory space for both program and variables, programming the microcontroller was not an easy task.  The programming language used was assembly with the instruction set and technical specifications of the chip given in the HC05 MC68HC705J1A Technical Data manual.[14]  The complete documented assembly code for the ANS can be found in Appendix J.
6.3.1 Program Design
The main program of the ANS is quite simple.  First the program goes through an initialization phase where all variables are set, all I/O ports are initialized, and the external devices are enabled.  Next, the processor waits for something to happen.

When a step occurs, the pedometer causes an interrupt and the program will debounce and registers the step taken.  Next, the program signals the compass to send the current direction the compass is facing.  Once the data from the compass is ready to be sent, the compass signals the microcontroller that it can start retrieving the data.  Once the data from the compass is in the microcontroller, the number of steps taken since the last direction obtained is stored in a vector, indexed via the direction of travel.  

Periodically the computer will signal the microcontroller to send its data.  The microcontroller will then stop the GPS receiver from transmitting over the same data line, send its data to the computer, re-enable the GPS receiver to transmit, clear the data array, and the process starts all over again.  Table 5 shows the state table of the ANS and its corresponding state diagram is in Fig. 31.  Fig. 32 has the flow diagram of the main program.


Table 5: State Table for the Alternative Navigation System

State
Meaning
0
Idle, nothing happening
1
Step occurring
2
Step occurred waiting for direction
3
Waiting for direction and new step occurring 












Figure 31: State Diagram of the Alternative Navigation System






















Figure 32: Main Program Flow Diagram
6.3.2 Debouncing the Pedometer
The first attempt at debouncing the pedometer through software seemed to work when testing was done with an ideal switch but when the actual pedometer was used, multiple steps were recorded for each step taken.
6.3.2.1 Waiting for Fifteen Consecutive 5volt Levels
The first attempt used was, after the interrupt occurred, to wait in a loop until polling of the IRQ line resulted in fifteen consecutive 5volt readings indicating that the step had occurred.  This is shown in Fig. 33. 











Figure 33: Pedometer Step Recorded after 15 Consecutive 5v Readings

In theory during the mechanical bouncing phase of a step, the counter would be continuously reset, until the voltage stays at the 5volt level for fifteen consecutive polls of the IRQ line.  This would indicate that a step had taken place.  There are a number of flaws with this method for debouncing the pedometer.  By continuously looping until fifteen consecutive 5volt readings are recorded, a potential endless loop may occur.  In addition, what is to say that fifteen polls during the mechanical bouncing phase could not result in all being at the 5volt level, and multiple step detections could result during this phase.  This method for debouncing the pedometer was rejected because multiple step detections did occur for a single step taken, and a new method for debouncing the circuit was implemented.
6.3.2.2 Using an Interrupt Timer and Monitoring the IRQ Line
A different approach to debouncing the pedometer uses the internal timer of the microcontroller to wait a specific number of milliseconds after the completion of a step before registering the step as a valid one.  Once the onset of a step occurs the internal interrupt timer is enabled, and it will cause an interrupt every 8.2 ms.  During this interrupt the ISR (Interrupt Service Routine) will check to see if the Pedometer has bounced, and if so will reset the total time to wait back to zero.  Once the entire 205 ms has elapsed the step is then registered.  The total time waited after the step has occurred is set at 205 ms, or twenty-five 8.2 ms timer interrupts.  This is shown in Fig. 34.  Fig. 35 shows a magnified view of the mechanical bouncing and its affect on the 205 ms counter.








 

Figure 34: 205 ms Delay before Registering a Step











Figure 35: Magnification of the Switch's Mechanical Bouncing and Delay Counter
As seen in Fig. 35, the delay counter can start increasing during the mechanical bouncing phase.  This is why there is a delay of 205 ms before registering the step as valid.  Otherwise, by reducing the delay time, multiple step detections could occur for the same step caused by this mechanical bouncing of the switch.  This 205 ms delay before registering a step was found by trial and error.  An initial value of 100 ms was chosen, and during field tests, it was found that for every step taken one to three steps were registered.  Doubling this initial delay time resulted in a one-to-one mapping of steps taken to steps recorded.  Using a debounce timer of 205 ms results in accurately recording up to four steps per second by the user.  If the user is taking more than four steps per second, the device is not being used in the manner it was intended.
This new method for debouncing the pedometer was successful, and for each step taken, only one step was recorded.  Pseudocode for both the Pedometer's and Timer's ISR can be found in Appendix K, and Figures 36 and 37 show the flowcharts of these routines.















Figure 36: Pedometer ISR Flow Diagram










































Figure 37: Timer ISR Flow Diagram
6.3.3 Obtaining the Direction of Travel
The Vector 2X compass is configured in a Slave mode of operation.  In Slave mode, the microcontroller generates the data clock.  With the M/S pin open, as shown in Fig. 30, Slave mode is enabled.  Clocking of the data does not have to be uniform in this mode, which means clocking in of the direction can be interrupted to record a new step, or send data to the computer.  Appendix I offers the Vector 2X Compass's technical specifications.
6.3.3.1 Slave Mode of Operation
In Slave mode, the microcontroller signals the compass for data by lowering the P/C pin (Poll / Continuous) for at least 10 ms. A 10 ms pulse indicates the polling method, by holding low P/C, the compass will continuously send its direction.  Upon pulsing P/C the EOC (End OF Conversion) line goes from high to low, and will return high when the compass has the new direction calculated and the data is ready to be clocked out.  Once the EOC line returns high, a minimum of 10 ms must be waited before lowering the SS (Slave Select) line, which stays low until the completion of the data retrieval process.  By lowering the SS line, SDO (Serial Data Output) switches from a tri-state mode to an output.  In Slave mode, SCLK (Serial Clock Input) is an input, and the clock is generated externally by the microcontroller.  Sixteen complete clock cycles must be generated (i.e. sixteen falling and rising edges) for the compass heading to be acquired through SDO.  Data is valid on the rising edge of the each clock cycle, and the maximum frequency of SCLK is 1 MHz.  The data can be in either in BCD (Binary Coded Decimal) or Binary format.  It was decided to use Binary as the data format.  Using a 16-bit Binary number to represent a decimal number ranging from 0 through 359 degrees, implies that the first 7 bits are all zeros.  Fig. 38 shows the basic compass schematic diagram, and Fig. 39 illustrates the timing diagram of the compass in Slave mode.










Figure 38: Compass Interface












Figure 39: Data Clock Timing Diagram [12]
6.3.3.2 Calibrating the Compass
Calibration of the compass must be done each time power to the compass is lost.  This is why the backup Battery BAT1 in Fig. 30 was added, to ensure that the compass has power even after the device is turned off.  The current drawn for the purpose of keeping the internal memory of the compass valid is less than 1 mA, and BAT1 will last for at least six months.  An external switch SW1 as shown in Fig. 30 was added to manually calibrate the compass.  By pressing the switch the compass will take a reading of the magnetic fields applied to the compass, next the user turns 180 degrees and presses the switch again.  The compass will then record this new magnetic field, and based upon the field strengths of the two magnetic fields, it will determine which direction is north, and store this in its internal memory.  This method for calibrating the compass can be in error, if another magnetic field is presently acting upon the compass during the calibration phase.  In this case the compass will "think" north is in the direction of the secondary applied magnetic field.  Unfortunately, this is the only method for calibration.  Additional software can be added to try to minimize this effect.  With the aid of GPS and DGPS to determine direction of travel, the compass direction can be verified, and be re-calibrated if necessary.  The pseudocode for the calibration of the compass can be found in Appendix L.
6.3.3.3 Clocking in and Storing the Compass Direction
For each step taken, the compass is polled and a direction is requested.  If multiple steps occur before the direction is obtained all steps are assumed to be in the direction finally obtained from the compass, and is stored accordingly.  The compass can only be polled once per direction, by toggling the P/C line for at least 10 ms, and cannot be polled again until the direction requested has been completely clocked out of SDO.  The time to completely clock out the data from the compass varies because pedometer bouncing and other interrupts are still enabled.  Consequently, if multiple steps occur while a direction is being obtained, all those steps are assumed to be in the same direction as the initial step.  Once the compass has signaled the microcontroller that a direction is valid and ready to be sent, the program reads in the first eight bits of the direction into the accumulator, since the accumulator can only store eight bits.  It then tests the LSB (Least Significant Bit) of the accumulator to see if the direction that will be obtained is in the order of 256 through 359 degrees.  This information is stored and the next eight bits are read into the accumulator.  The accumulator now has a binary number between 0 through 255 decimal, but with the information stored about the LSB from the first eight data bits known, we have a direction ranging from 0 through 359 degrees. 

Currently the storage array holds eighteen data elements and for directions ranging from 0 through 359 degrees this results in a twenty-degree resolution. When a step is taken, and the corresponding direction is obtained, the step taken is indexed into the storage array offset by the direction.  For example, if one step is taken and the direction obtained from the compass equals 260 degrees, the corresponding storage array position would be 260 / 20 = 13.  This resolution of twenty degrees can be brought to a resolution of ten degrees without increasing the size of the storage array.  This is accomplished by using the array elements for two different directions and the sign of the number indicates the direction of the step.  Positive numbers are used to indicate directions ranging from 0 through 179 degrees, and negative numbers to indicate directions from 180 through 359 degrees.  For example, if a step is taken at 90 degrees, +1 is added to array element 9, and if a step is taken at 270 degrees -1 is added to array element 9.  This is because if a person takes a step east, then turns around and takes a step west, the net result is 0, or in fact they essentially have not moved.  Table 6 shows the mapping from the 9 bits of relevant data received from the compass into the eighteen-element storage array.  The maximum number of steps that can be recorded in any direction therefore is reduced.  Originally 255 steps (unsigned) could be recorded, now 127 steps in the forward direction (i.e. 0 through 179 degrees) and 128 steps in the reverse direction (i.e. 180 through 359 degrees) can be recorded.  These limits are of no concern since the array will be cleared after the data is sent to the computer, which is done every couple of seconds.  Appendix M has the pseudocode for the obtaining the direction from the compass.

Table 6: Compass Direction Mapped to Storage Array
Degrees
Dec
Signed 8-bit
Hex

8-bit
Binary
Array
Position
Direction
0
0
0
0 0000 0000
0
+
1
1
1
0 0000 0001
0
+
2
2
2
0 0000 0010
0
+
...
...
...
...


9
9
9
0 0000 1001
0
+
10
10
A
0 0000 1010
1
+
11
11
B
0 0000 1011
1
+
...
...
...
...


126
126
7E
0 0111 1110
12
+
127
127
7F
0 0111 1111
12
+
128
-128
80
0 1000 0000
12
+
129
-127
81
0 1000 0001
12
+
130
-126
82
0 1000 0010
13
+
...
...
...
...


178
-78
B2
0 1011 0010
17
+
179
-77
B3
0 1011 0011
17
+
180
-76
B4
0 1011 0100
0
-
181
-75
B5
0 1011 0101
0
-
...
...
...
...


252
-4
FC
0 1111 1100
7
-
253
-3
FD
0 1111 1101
7
-
254
-2
FE
0 1111 1110
7
-
255
-1
FF
0 1111 1111
7
-
256
0
0
1 0000 0000
7
-
257
1
1
1 0000 0001
7
-
258
2
2
1 0000 0010
7
-
259
3
3
1 0000 0011
7
-
260
4
4
1 0000 0100
8
-
...
...
...
...


355
99
63
1 0110 0011
17
-
356
100
64
1 0110 0100
17
-
357
101
65
1 0110 0101
17
-
358
102
66
1 0110 0110
17
-
359
103
67
1 0110 0111
17
-

Directions + indicate (0 - 179 degrees), Directions - indicate (180-359 degrees) 
6.3.4 Sending Data to the Computer
Without the aid of a separate UART, all data sent to the computer had to be precisely clocked out.  With the aid of a Motorola Application Note on the HC05 Serial Communication Techniques [14], a data module was written to send data to a serial port at 9600 baud, 8 bit, no parity, and 1 stop bit.  Strider uses the same baud rate and port settings to communicate with the GPS receiver.  This will simplify integration of the ANS with Strider.  
The computer will periodically signal the microcontroller to send its data by raising the RTS (Request to Send) line, which causes an interrupt in the microcontroller.  When the interrupt occurs, the program turns off all other interrupts because timing is critical for clocking out the data to the computer.  The GPS receiver is then prevented from transmitting and the microcontroller has control over the RS-232 connection to the computer.  First the header is sent (AA Hex) or (10101010 Binary), next the 18 bytes of the storage array, and finally the CRC (Cyclic Redundancy Check) byte.  The CRC byte is calculated by simply adding up all the data bytes sent including the header.  With an 8-bit signed accumulator and limited mathematical operations there was not much else that could be done in tandem while sending the data to the computer.  Preprocessing of the CRC value was considered but due to the limited memory and speed of this microcontroller it was felt that anything more would reduce system performance.  Besides, currently the CRC value is only used by the computer to verify that the data is correct, and if it does not match the CRC value generated, the data is ignored and lost.  A method for re-transmitting the data if the CRC check fails must still be done.  Appendix N has the pseudocode for sending the ANS data to the computer, and Fig. 40 has the flow diagram for this routine.

















Figure 40: Computer Requests Data ISR Flow Diagram
6.4 Computer Interface
For testing the ANS, a small C-language windows program was designed.  Every two seconds the program will signal the ANS by raising RTS (Request to Send) line to send its data and then read in the data from the serial port.  After verifying the CRC value it would process the data and draw on the screen the steps taken in the appropriate direction.  The program acts like an "etch-a-sketch", with north being the top of the screen.  The program can also save the data obtained to disk, and later redraw an old path travelled.  This provided the testing necessary to verify that the ANS works.   Test results will be presented in Chapter 7.  See Appendix O for the pseudocode of this test program.

6.4.1 Problems that Occurred
The cable that was used connecting the computer to the ANS was a null modem cable that only had three wires.  So when the RTS line was raised through software, nothing happened, and it was assumed that there was a problem with the windows programming environment.  After a lot of time was spent looking for software problems, finally the cause of the problem was discovered and corrected.

The program was compiled and tested on a Pentium 200 machine, and timing was a problem.  The computer would raise the RTS line, start reading in the data from its buffered UART chip, but before all of the data could be sent to the computer, it would empty the buffer.  The packet length would be less than the twenty bytes expected and would fail, and therefore the program would lower the RTS line, and the data would be lost.  This problem was overcome by raising the RTS line for 40 ms, which is more than enough time for the microcontroller to send its 20 bytes of data at 9600 baud.  Then the computer would read in the entire packet, which solved the timing problem.

After the program was running correctly on the Pentium 200, field tests outside were done on a laptop computer.  The computer is a 33 MHz 486 laptop, which introduced another timing problem.  The processing speed of the laptop was too slow to handle the messages generated to draw the steps on the screen, and would occasionally miss some messages.  Instead of asynchronously posting the windows messages, messages were synchronized with a windows "SendMessage" command, which solved the problem.  

6.5 Summary
This ANS completes the third requirement of this thesis, a reliable and accurate alternative for when GPS fails.  This system will accurately track a user as they travel, providing the instantaneous direction and number of steps taken in the given direction of travel.  Calibration of steps taken, to distance travelled, can be done "on-the-fly" through software, using when available, the GPS and DGPS solutions.  This system can be easily integrated with Strider to complete the personal guidance system as set forth by this thesis.  The next chapter provides the results of testing the ANS.

Chapter 7: Testing the Alternative Navigation System
A number of tests have been conducted on the ANS, from outdoor testing around the streets of Ottawa, verification of steps taken to steps recorded, and indoor testing around the halls of the Mackenzie Building. 
7.1 Testing around a City Block
The first tests done were to determine whether the ANS could track a user around a city block.  As can be seen from Fig. 41, the system closely tracks the user around the city block with only slight errors in direction.  These errors can be corrected by increasing the resolution of the degrees recorded from the compass.  Currently the compass offers one-degree resolution with two-degree accuracy, but the ANS maps this to ten degrees.  The ANS would need an array of 90 bytes to store this higher resolution and by doing so would increase the overall accuracy of the system.  Unfortunately, this means changing the microcontroller again, which is something that should be done when this system becomes a product, as will be discussed in Chapter 8.









Figure 41: ANS Tested around a City Block
7.2 Testing Pedometer Accuracy
The ability of the system to accurately record the correct number of steps taken is very important to accurately track a pedestrian.  In Fig. 42 a test was conducted that shows that the pedometer accurately recorded the number of steps taken with an error of 1%.  One hundred steps were taken, 50 going northeast, and then another 50 going southwest.  The actual steps recorded were 51 going northeast, and 50 going southwest.  Therefore, after 100 actual steps taken, 101 steps were recorded.  The numbers at the top of the screen show the actual number of steps taken in a particular direction.  From left to right, each number represents the number of steps taken from 0 degrees to 350 degrees, with a step size of 10 degrees between numbers.  Therefore, in Fig. 42, the first 10 represents 10 steps taken at 40 degrees from north, the number 16 beside it represents 16 steps at 50 degrees from north etc.  The error in direction again is caused by the two-degree accuracy from the compass mapped to ten degrees by the microcontroller.  Over twenty tests were conducted which verified the recording of steps taken with the error ranging between 0% and 2%.  
  


Figure 42: Pedometer Testing - Steps Taken to Steps Recorded
7.3 Testing ANS Indoors
Tests were done to make sure the ANS would work indoors.  It was thought that the walls inside would cause the compass direction to be inaccurate.  Fig. 43 shows the path travelled on the fifth floor of the Carleton University Mackenzie Building, starting at the northwest corner and travelling clockwise around the quadrant.  As can be seen in the figure, the system is not perfect.  A complete square route was travelled with the ending and starting points being identical.  The route ANS tracked was not completely square and the starting point and ending point did not match up. A number of factors may have caused this result, from human error with uneven step size, to the compass being affected by secondary magnetic fields indoors.  Either way, the tracking ability this system provides, is more than adequate for the purpose intended.  As shown in the diagram a spike in direction occurred near the mechanical room due to the magnetic fields present near this room.



Figure 43: Testing Indoors - Fifth Floor Mackenzie Building of Carleton University
7.4 Performance around Bridges
Bridges and underpasses will cause the Vector 2X compass to exhibit inaccurate heading information because of the steel in these structures, which produce magnetic fields.  These magnetic fields will affect the compass and the true heading of the compass will be skewed.  Once the bridge or underpass has been cleared the compass will again operate normally and the true heading of the compass will be restored.  For small bridges and underpasses, this error in direction is acceptable.  In Fig. 44, a route was travelled which went under a bridge, which contained large steel beams.13  As can be seen from that figure, when the compass was under the overpass the direction obtained was incorrect, but once clear of the overpass the true direction of travel was restored.


Figure 44: Guidance System Test under an Overpass
Distance from A-Flora St. to B-Strathcona St. is 420 meters.
Section A through B is collinear, but the bridge effected the compass reading.

7.5 Summary
The tests conducted here shows that the ANS is not perfect but that it can accurately track a pedestrian in and out of doors, and it has limited success around bridges.  The ANS as it currently stands has a 2% error of steps taken to steps recorded, and due to memory constraints has a 10( error in direction.  Assuming city blocks of 100 meters each, after one block with both a 2% error in steps taken and a 10( error in direction the ANS will have the following cumulative error as shown in Fig. 45.









Figure 45: Worst-Case: Total Error accumulated by the ANS

A denotes the starting point, and B is the actual location of the pedestrian after travelling a block (100.0 m).  Point C denotes where the ANS "thinks" the pedestrian is located.

After one block, travelling 10 degrees off the correct heading, and having a step recording error of 2% the cumulative error is 17.7 meters.  Comparing this with the GPS having an accuracy of (100 meters, the number of blocks without a GPS signal would have to be greater than five before the ANS's accuracy would be worse than that of the GPS system.  It is also important to note that this is a worst-case scenario, and once the microcontroller is changed and two-degree accuracy in direction is achieved, the overall accuracy of the ANS will improve dramatically.  This can be seen in Fig.46.









Figure 46: Best-Case: Total Error accumulated in ANS

After a block, there is only an error of 4.1 meters, or a 4% error.  This is comparable to DGPS accuracy with an error of (4 meters.  Therefore, the ANS can accurately track a pedestrian, with the revised microcontroller and improved accuracy, for a block before its accuracy is worse than DGPS accuracy.










Chapter 8: Conclusions
8.1 Summary
The master objective was to build a portable and affordable personal navigation system for the visually impaired, specifically a system to guide the visually impaired through the streets of a city.  This has been achieved during the course of this thesis, through a set of objectives.  Each objective and the tasks performed to meet that objective can be stated as follows:  

1. Audible access to map information, and the tools for utilizing this information.  This objective was met as described:
* Atlas Speaks allows the visually impaired to virtually explore a city map.  It offers a variety of tools to extract information from the map, as well as to add important locations to the map. It also has the ability to find a route to a specific destination.  Speech synthesis is the primary output device but it will also present information through a Braille display.  The user interacts with Atlas using the keyboard and an audible menu system.

2. The ability to travel outside and know one's position.  This objective was met as follows:
* Strider is the mobile version of Atlas Speaks.  Using a laptop computer, GPS and DGPS to locate position, Strider can accurately track the visually impaired as they travel outside.  With GPS accuracy, the error in the position reported by Strider is (100 meters, but with DGPS accuracy, this error improves to less than (4 meters.  With this improved accuracy, Strider can inform the user about the house numbers they are passing, as well as guide them along predetermined routes. 

3. An alternative system for the primary guidance system when it fails.  This alternative system was designed and implemented as follows:
* An alternative navigation system is needed when the GPS position is no longer obtainable.  When there is no GPS position, this ANS can take over, starting at the last location obtained by these receivers.  The ANS consists of a pedometer for counting the number of steps taken, and a digital compass for determining the direction of these steps.  Calibration of the pedometer steps can be done through software while the system is tracking the user, using the GPS and DGPS systems.  The ANS continuously monitors the user's direction of travel, steps taken, and will send this information to the computer running the Strider software upon request.  Strider will then convert this information into a change in the latitude and longitude position, used by the map software to locate the user.
8.1.1 Results
The results from Chapter 7 clearly show the potential of the ANS.  These results surpassed the expectations of the author.  As the system currently stands it can accurately track a pedestrian over 500 meters, before the inaccuracy is greater than that of the GPS system.  The ANS can be modified and an improved accuracy can be obtained.  This improved accuracy can accurately track up to 100 meters, before its inaccuracy is greater than DGPS, and over 2 500 meters with GPS equivalent accuracy.

With DGPS equivalent accuracy for 100 meters, the ANS can be used in more situations than originally designed.   Instead of the ANS just tracking the user once the GPS position is lost, the overall accuracy of the entire system can be improved by continuously using the ANS.  A number of different scenarios are presented here which improve the overall accuracy and performance of the personal navigation system:
* Strider currently determines direction of travel based upon the last x positions recorded, averaging these positions to determine direction.  With the ANS's compass, instantaneous heading information can be obtained.

* If Strider loses DGPS, the accuracy of the user's position suddenly jumps from (4 meters to (100 meters.  When this happens instead of  "jumping" to the GPS position, the ANS can track the user for a block with the equivalent accuracy of DGPS.  Theoretically, the ANS can track the user until the DGPS position solution is re-acquired.  The user would have control over how long the ANS would track the user when GPS positioning is available, and could at any time revert back to GPS positioning if desired.

* Usually the GPS receiver takes between one to three minutes to acquire three or more satellites and position solutions once turned on.  However, if its internal almanac is not up-to-date or if the battery-backup fails, this delay can be up to ten minutes.  Since the user would know the starting location, the ANS could track the user from this location until the GPS receiver obtains a position solution.

* For short trips, the ANS could be used exclusively.  All that would be needed is the starting location and the ANS could track the user.  Periodically the user could update the system if the exact location is known.  This can also be used to extend battery life of the Personal Navigation System.

* Routes can be created for the visually impaired for use the inside buildings.  The ANS could be used exclusively in this case, and Strider could direct the user to specific locations within the building.

 8.2 Claims of Originality
The author started this entire project at Carleton University, September 1992, with a fourth-year project entitled "A Navigational System for the Visually Impaired".[1]   This project received a lot of press, which is referenced in Appendix A.  As part of the ongoing development of this project, the author worked at VisuAide and at Arkenstone.  From the initial conceptualization through proof of concept, design, programming, and testing, the authors contributions were essential to the development of this product.  While working at Arkenstone on Atlas Speaks and Strider, a patent was granted to the developers, which includes the author, for this project.  The shaded portions in Fig. 13 (p 38) show the specific software modules developed by the author.  The design, implementation, de-bugging, and testing of the ANS was entirely done by the author.
8.3 Benefits
With the aid of this Personal Navigation System, the visually impaired can travel outdoors, with the confidence of not getting lost, and the freedom and independence of doing so without relying on others.  With the additions of the ANS, the product is complete.  The ANS brings reliability and an improved overall accuracy to this system.  The cost of adding this system to Strider is negligible, (less than $100).

This Personal Navigation System will track the visually impaired and using synthesized speech present the street address of the current location to the user.  Not only can it track the user, but it can also find a route to a specific destination, and then guide the user to this destination.

With "Points of Interest", additional detail can be added to the map making the map more personal by offering custom information.  With a "Points of Interest" file open the user can be informed, while travelling, of specific locations as they are approached.  For example, if the "Points of Interest" were bus stops, the user could ask for the nearest "Point of Interest", or in this case the nearest bus stop, and be directed to the stop.  Upon arrival at the bus stop, the user would be informed.
8.4 Future Improvements
The ANS currently offers only a ten-degree resolution in direction travelled, due to memory constraints.  By upgrading the microcontroller to one that has more memory, the two-degree accuracy offered by the compass can be realized.  In addition, a separate buffered UART should be incorporated as well as CRC checking and recovery of data.

Due to the limited memory space, the current design does not keep track of the order in which each step was taken and its corresponding direction.  For example, if a step were taken north, then east, then north, and finally another step east, either of the following two diagrams could be displayed:





Figure 47: Order of Steps Recorded

In Fig. 47, the figure on the left will be displayed if all four steps are taken before the data is sent to the computer.  The figure on the right will be displayed if after each step taken the data is sent to the computer.  The user ends up at the same place, but multiple paths could be generated to get the user to this location as shown by the figures.  This depends on when the data is sent to the computer.  By saving the data in chronological order, the exact path the user travels will always be recorded no matter how frequently the data is sent to the computer.

The integration of the ANS to Strider must also be completed.  The time needed to integrate it with Strider is estimated to be less than six months, since the original design incorporated provisions to include it with Strider from the onset.  A switching circuit was incorporated so that both the alternative and GPS systems could be connected on the same serial cable.  Slight modifications to the device-dependent GPS DLL module will have to be made to receive and signal the ANS to transmit its data.  Additional software will have to be written in the "Strider Interface" module (as shown in Fig. 13).  This software will convert the steps and directions the ANS reports into a change in the latitude and longitude, which Atlas Speaks uses to display the Strider cursor and the current position solution of the system.

While Strider is tracking the user using the GPS system, the length of the user's stride can be determined "on the fly".  This stride length can be averaged over a period of time, and stored.  This step-size can be continuously updated, so a current step-size will be used to convert the steps taken into a change in position.  Therefore, no manual calibration of the user's step-size will have to be made.

Calibration of the compass's heading information must still be done at least once, so that the compass "knows" where north is.  On the prototype board, a switch is used to calibrate the compass.  The switch is pressed and the board is turned 180( and it is pressed again.  When the compass has not been calibrated it will either give a direction that is an invalid heading or always give the same direction, no matter which direction the compass is facing.  In either case software can be designed to recognize this invalid compass state, and to signal Strider that the compass must be calibrated.  Strider can inform the user that the compass in the ANS must be calibrated and then proceed to instruct the user on how to calibrate the compass.  Instead of physically having to press a switch on the board to calibrate the compass, the calibration process could be done through software, and the user could press a key on the keypad to signal the compass to start its calibration process.  Then Strider could tell the user to turn 180( and press the key on the keypad again.   This will complete the process, and the user can proceed normally.

There is still one factor preventing this Personal Navigation System from becoming totally accepted and used in the visually impaired community.  That is the size and weight of the system, with the laptop computer being the main contributor to this problem.  Miniaturization is necessary and an embedded system would be ideal, but the cost of miniaturization may be too much of a financial strain for the visually impaired to bear.  One option is to use a palm top computer if it will have enough ports available to support both the speech synthesizer as well as the Strider Box.

Appendix A: Popular Press Articles about this Project

Hum, Peter. "Out of mind, into 'sight'", The Ottawa Citizen. (31 March 1993), pp. A1-A2. 

Kingsmill, Suzanna. "... in Ottawa, the blind can find their way round town ...", New Scientist. Vol.139, No.1880.  (3 July 1993), pg.18.

"Better Than a Cane", Discover. Vol.14, No.10. (October 1993), (no author cited) pp.20-21.

St.Pierre, Denis. "New device helps blind get around", The Sudbury Star. (11 October 1993), pg.A1.

"Augen vom Himmel", GEO. Nr.11. (November 1993), (no author cited) pg.200.

Guly, Christopher. "He's Got Eyes in the Back of his Pack", The Financial Post Magazine. No.3070, (June 1994), pg.12.

Gooderham, Mary. "Orbiting beacons show blind the way", The Globe And Mail. No.45,222, (29 November 1994), pg.A1, pg.A7.

Hoffman, Perry. "Tech firms gear products for disabled", Ottawa Business Journal. Vol.3, No.41. (15 June 1997), pg.4.





Appendix B: Available Atlas Speak Functions
The following is from the Atlas Speaks User's Manual[15] 
Announce Serendipity Points of Interest announces all Points of Interest inside the Serendipity range.  Serendipity does not need to be turned on for this key announcement to work.
ECA Name announces the drive, path and name of the map on which the current explore position is located.  A typical announcement would be c:\Atlas\maps\s\sof_ca.
City announces the city in which the Atlas cursor position is located.
Destination description announces the "name" or address of the destination currently activated.  Atlas will say  "unavailable" if no destination is active.
Destination heading and distance announces the heading and distance from the current position to the selected destination.  The heading is given in the selected heading units and the distance is calculated according to the Metric or Imperial Units setting.  Atlas will say "unavailable" if no destination is active.
DOS Date and Time gives the exact date and time being used by DOS.  
Heading announces the current heading in degrees.  The units cannot be changed and only a number is announced.
Intersecting Street Information announces the current position, usually an intersection.  If the cursor is not at an intersection, Atlas will announce the nearest address.
Intersection Ahead calculates the nearest intersection in front of the current position.  Atlas will announce this intersection and give its heading and distance. 
Intersection Behind calculates the nearest intersection behind the current position.  Atlas will announce this intersection and give its heading and distance. 
Intersection to Left calculates the nearest intersection to the left.  Atlas will announce this intersection and give its heading and distance.
Intersection to Right calculates the nearest intersection to the right.  Atlas will announce this intersection and give its heading and distance.
Latitude announces the latitude of the current explore position.
Longitude announces the longitude of the current explore position.
Major Intersections lists the 10 major intersections closest to the current explore position.  Atlas lists each intersection with its name, heading and distance.
Nearest Address announces the number and street name of the address nearest the current position.
Nearest Intersection Description gives a description of the nearest intersection to the current explore position.
Nearest Point of Interest Description announces the name of the closest Point of Interest to the current explore position.  Atlas will say nothing if there is no Points of Interest file open.
Nearest Point of Interest Heading and Distance announces the heading and distance from the current explore position to the nearest Point of Interest.  Atlas will say nothing if there is no Points of Interest file open.
Pedometer Last Leg Travelled announces the pedometer reading of the last segment of the route.  Usually this is the distance from the previous intersection.
Pedometer Total Distance Travelled announces the pedometer reading since the last time the pedometer was reset to zero.  This is usually the distance since the last set Explore Position or opened a route.
Route Beginning Description gives a description of the first waypoint in the open route.  This waypoint is usually an address or intersection.  If no route is active, Atlas says nothing. 
Route Beginning Heading and Distance announces the heading and distance from the current position to the beginning of the open route.  If no route is active, Atlas says nothing. 
Route Endpoint Description gives a description of the last waypoint in the current route.  This waypoint is usually an address or intersection. If no route is active, Atlas says nothing. 
Route Endpoint Heading and Distance announces how far it is to the end of the route that is currently in use and in what direction this point is.  If no route is active, Atlas says nothing. 
Route In Use announces the name of the route currently in use.
Route Status announces the following information about the active route: the nearest waypoint by cross streets, the direction of travel (forward or reverse), the distance travelled from the start of the route, and the distance remaining to the end of the route.
State announces the state (or province in Canada) in which the current position is located.
Street Classification announces what type of street currently being travelled.  The following is a list of all the classifications Atlas uses: 
Major Freeway
Minor Freeway
Limited Access (any road that is only accessible at certain points.  It can be a freeway, expressway, etc.)
Arterial (an urban road that connects high-volume highways)
Collector (a road that collects traffic from light-duty roads, and feeds arterials and highways)
Major Residential
Minor Residential
Low-speed Ramp (an entrance to or exit from a freeway that requires a driver to slow down -- a cloverleaf)
High-speed Ramp (an entrance to or exit from a freeway that does not require a driver to slow down -- a ramp connecting one freeway to another)
Unknown (a street without classification at the time of publication) 
Street Name and Direction announces the current street and compass direction.  This unit of direction cannot be changed.
Text label lets the user add text to a key; this is important in some cases where the next information presented will just be a number, which should be qualified.
Waypoint Description Nearest gives a description of the nearest or current waypoint.  This waypoint is usually located at the current position. 
Waypoint Description Next gives a description of the next waypoint.  This is usually an address or intersection.
Waypoint Description Previous gives a description of the previous waypoint.  This is usually the address or intersection just left.
Waypoint Heading and Distance Nearest announces the heading and distance to the nearest or current waypoint.  If this waypoint is located at the current position, Atlas says nothing.  
Waypoint Heading and Distance Next announces the heading and distance to the next waypoint.
Waypoint Heading and Distance Previous announces the heading and distance to the previous waypoint.
Waypoint Number Nearest announces the chronological number assigned to the nearest or current waypoint.  This waypoint is usually located at the current position. 
Waypoint Number Next announces the chronological number assigned to the next waypoint.
Waypoint Number Previous announces the chronological number assigned to the previous waypoint.
Zip code announces the zip code in which the current position is located.

Appendix C: Speech-Queuing Interface Prototypes

AUDIT_clear
	Parameters
void AUDIT_clear (void)
	none
Return Codes
none
Functionality
Deletes entire Audit trail.

AUDIT_retrieve
	Parameters
void AUDIT_retrieve (char *auditstr)
* Pointer for the last text item in audit trail
Return Codes
none
Functionality
Returns a pointer to the last item stored in the audit trail, then deletes that item from the audit trail.

SPEECH_add
	Parameters
BOOL SPEECH_add(char *pText)
* Text to be spoken
	Return Codes
* TRUE - text successfully added to queue
* FALSE - Unable to add text to queue
1.      There is no text to add.
2.      Speech is turned off and this is not a priority item.
3.      An error occurred while allocating memory
	Functionality
SPEECH_add  This will add the text item to the queue, with the parameters set up by SPEECH_priority.      
If the current class being spoken is the same as the class to be added and there is nothing in the queue, then the current message being spoken will be terminated and the item to be added to the queue will be spoken immediately.
All text added to the queue through SPEECH_add will be added to the audit trail.

SPEECH_empty
	Parameters
BOOL SPEECH_empty (void)
	None
Return Codes
* TRUE - the speech queue is empty
* FALSE - the speech queue is not empty
Functionality
Determines whether or not the speech queue has text remaining in the queue to be spoken.

SPEECH_flush
	Parameters
void SPEECH_flush (BOOL justemptyQ)
* With justemptyQ being TRUE only the queue is cleared
* With justemptyQ being FALSE the queue is cleared and the synthesizer is signalled to stop speaking immediately.
Return Codes
none
Functionality
Empties the speech queue, and may stops the synthesizer from speaking 

SPEECH_NA_add
	Parameters
BOOL SPEECH_NA_add(char *pText)
* Text to be spoken
	Return Codes
* TRUE - text successfully added to queue
* FALSE - Unable to add text to queue
1.      There is no text to add.
2.      Speech is turned off and this is not a priority item.
3.      An error occurred while allocating memory
	Functionality
Same as SPEECH_add except the text won't be added to the audit trail

SPEECH_next
	Parameters
BOOL SPEECH_next (void)
	none
Return Codes
Returns whether or not the voice synthesizer was currently speaking.
Functionality
Stops the synthesizer from speaking and then speaks the next item in the queue.


SPEECH_pause
	Parameters
void SPEECH_pause (BOOL flag)
* If flag is TRUE speech is paused
* If flag is FALSE speech is resumed.
Return Codes
	none
Functionality
Pauses speech depending upon the flag.  When speech is resumed, SPEECH_next is automatically called

SPEECH_priority
	Parameters 
void SPEECH_priority(BOOL newclass, BOOL priority, BOOL pauseafter, int nVoice,                             
	BOOL spell, char cclass, char subclass)
* Newclass - is this a new class of text, otherwise use previous class.
* Priority item
* Should the voice synthesizer pause after this text has been spoken
* The voice the synthesizer will use to speak this text
* Should the voice synthesizer spell out the text?
* The class of the text.
* The subclass within the class of text to be spoken.
Return Codes
none
	Functionality
Sets the parameters of the next text item that will be added to the queue.

SPEECH_skip
	Parameters
void SPEECH_skip (BOOL shutup)
* Stop the synthesizer from speaking immediately
Return Codes
none
Functionality
This routine may terminate the current message being spoken.  The current message being spoken has associated with it a subclass, if the next thing in the queue to be spoken has the same subclass it will be removed from the queue.  This will continue until either the next subclass in the queue is different from the subclass that was skipped or a new class is at the head of the queue.  At which time the current item at the head of the queue will be spoken.



SPEECH_speaking
	Parameters
BOOL SPEECH_speaking (void)
	None
Return Codes
* TRUE - the voice synthesizer is currently speaking
* FALSE - the speech synthesizer is not currently speaking
Functionality
Determines whether or not the synthesizer is currently speaking.

 WhatWasThat
	Parameters
void WhatWasThat(void)
	none
Return Codes
none
Functionality
Speaks the last message that was spoken.  If this routine is called four times in a row, the message is spelled out to the user.





Appendix D: Available Strider Functions
In Strider mode, the Atlas functions in Appendix B are also available as well as the following functions:

Altitude announces the altitude of the user.
Explore Position Heading and Distance informs them of the Atlas cursors position in relation to their real-time GPS location.
GPS Status announces the status of the GPS receiver.
Number of Satellites being tracked announces the number of satellites the GPS receiver is currently tracking.
GPS Accuracy announces the accuracy of the GPS receiver
GPS Time announces the exact time that is synchronized with the satellites atomic clocks.
Latitude gives the Latitude of the user.
Longitude gives the Longitude of the user.
Speed announces the instantaneous speed at which the user is travelling.

When the user is using the GPS Expert Window, they also have access to Satellite information:

Satellite x's Number announces the actual number the DOD uses to keep track of a particular satellite.
Satellite x's SNR announces the signal-to-noise ratio the GPS receiver is receiving from this satellite. 
Satellite x's Altitude announces the altitude above sea level where the satellite is in the sky.
Satellite x's Azimuth announces the number of degrees from north where the satellite is located in the sky.

Where the number x can refer to any satellite from number 1 through number 6.



Appendix E: Keypad Keys



MENU

Atlas / Strider
Toggle

VOICE SETTINGS


HELP
Num
Lock

/

*

-
MAJOR
INTER-SECTIONS


MOVE FORWARD


ROUTE
STATUS



ESCAPE
7
Home

8


9
PgUp




ROTATE LEFT



SELECT


ROTATE RIGHT

+
4


5

6




KEY DESCRIBER


UNDO LAST MOVE


SPEECH REVIEW



SPEAK
1
End

2


3
PgDn



WHERE
AM I?





SKIP TEXT

ENTER
0



Ins

.
Del



The Seventeen-Key Keypad [15]

The following is from the Atlas User's Manual[15]

Atlas Key	Keypad Name	Atlas Function
Menu	Num Lock	Activates the menus that allow the user to choose different options and change Atlas's settings.  

Atlas / Strider Toggle	Back Slash (/)	Switches between Atlas Speaks and Strider.

Voice Settings	Asterisk Key (*)	Change the Voice Settings, including voice rate, tone, speed and selection.

Help	Minus (-)	This is a context-sensitive help key, which will display help information for example on menu items, if pressed while in the menus. 

Major	Home (7)	Describes the current location,
Intersections		relative to the ten nearest major intersections.

Move Forward	Up Arrow (8)	Moves the Atlas cursor forward in the current direction.  Also moves the cursor up in Menus.

Route Status 	Page Up (9)	When using a Route file, this indicates the nearest waypoint ahead, and calculates the distance travelled and the distance needed to complete the Route.

Escape	Plus (+)	Exits the current activity, gets out of Help or backs out of the current menu list.  

Rotate Left	Left Arrow (4)	Rotates the Atlas cursor to the next street to the left of the current position.  In a menu, it can be used like the Escape key.

Select	(5)	Selects the current choice in a Menu or dialog box.


Rotate Right	Right Arrow (6)	Rotates the Atlas cursor to the next street to the right of the current position.  In a menu, it can be used like the Enter key.

Key Describer	End (1)	Describes the function of the other keys.  Press this key and the other keys become inactive; then press any key and it describes its function.  Press the Describer key again to return the keypad to normal operation.

Undo Last	Down Arrow (2)	When traveling on the map, this
Move		allows the user to undo the last movement forward, up to ten steps back.  Also moves the menu cursor down in a Menu.

Speech Review	Page Down (3)	Allows the user to enter and move about in the Speech Review buffer when Atlas is giving directional data, such as Major Intersections, Route Status, or 'Where Am I?' information.

Speak	Enter	Starts and stops speech while in a Menu or when Atlas is giving location or status information.  

Where Am I?	Insert (0)	Describes the current location in terms of the intersection nearest to the Atlas cursor using the street (or streets) in front and behind, and the streets to the left and right.  It uses the clock format to indicate directions relative to the cursor.  Also gives the actual address of the current location.

Skip Text	Delete (.)	When Atlas is giving status or location information, this key allows the user to skip the current text information and move on to the next entry in the list.

 Appendix F: GPS Receiver's DLL Interface Prototypes
StartGps
	Parameters
int FAR PASCAL _loadds StartGps(double old_lat, double old_lon,GpsCommParms com_p, GpsCommParms dgps_param,LPCSTR library,INIINFO ini_info,double UserLat,double UserLon, Environment Env)
* Previous GPS Latitude (double) [degrees]
* Previous GPS Longitude (double) [degrees]
* GPS receivers comm port parameters (GpsCommParms)
* DGPS receivers comm port parameters (GpsCommParms)
* GPS DLL's language specific string library (LPCSTR)
* Information on a third parties GPS DLL INI file which we are interfacing with. (INIINFO)
* A user specific Latitude offset (double) [degrees]
* A user specific Longitude offset (double) [degrees]
* Receivers INI specific Environment settings (Environment)
	Return Codes
* ERR_LANGUAGE_DLL - Was unable to load the gps language specifice DLL.
* ERR_INITALIZED - StartGPS was previously called
* ERR_REGISTER_WINDOW - Third party DLL unable to launch (eg: goldcards tgpsdll.dll)
* ERR_MALLOC_COMM_BUF - Unable to set buffer size for comm port communication
* ERR_OPEN_COMM_PORT - could not take control of the comm port set in the GPS comm port settings
* ERR_NO_GPS - No GPS receiver found
	Functionality
StartGps firstly initializes all internal variables, sets up the comm ports for the GPS & DGPS receivers for communication.  Then opens up the language specific DLL.  
StopGps
Parameters
void FAR PASCAL _loadds StopGps( void)
* none
Returns
* nothing
Functionality
StopGps shuts down the comm port, closes language library, closes any window which was opened for a specific GPS receiver, and resets the DLL to un-initialized.
GpsID
Parameters
int FAR PASCAL _loadds GpsID (void)
* none
Returns
* TRUE or FALSE (int)
	Functionality
GpsID returns TRUE if we are communicating with the GPS receiver.  (I.e. We got at least 3 messages from the receiver.)  Otherwise it returns FALSE
PollGps
Parameters
void FAR PASCAL _loadds PollGps (void)
* none
Returns
* nothing
	Functionality
PollGps sends GPS specific codes to the GPS receiver, so that the receiver will return the specified data, used in HandleGps.  This routine should be called once a second.
HandleGps 
Parameters
void FAR PASCAL _loadds HandleGps (void)
* none
Returns
* nothing
	Functionality
HandleGps gets the information from the GPS receiver which was asked for via PollGps, this should be called right after PollGps.  All packets from the receiver are processed here and the appropriate data is processed and saved. 
GpsPosition
Parameters
int FAR PASCAL _loadds GpsPosition( double *lat, double *lon, int Modify)
* Latitude (double *) [degrees]
* Longitude (double *) [degrees]
* Modify (int) [TRUE / FALSE]
Returns
* Sets Latitude & Longitude
* GPS_SAME - Latitude & Longitude has not changed since the previous call to this function.
* GPS_DIFFERENT - Latitude & Longitude has changed since the previous call to this function.
Functionality
GpsPosition returns the Latitude / Longitude, and the return code is GPS_DIFFERENT if there has been a change in position since the last time you called this routine.  If Modify is TRUE the old position will be replaced by the current position.
GpsAccuracy
Parameters
int FAR PASCAL _loadds GpsAccuracy( char *accuracy,int detail ,int *Valid_Position, int Modify)
* Current GPS Accuracy (char *) [LANGUAGE SPECIFIC]
* Detail Level (int) [EXPERT / NOVICE]
* Valid Position fix (int *) [TRUE / FALSE]
* Modify old accuracy (int) [TRUE / FALSE]
Returns
* Sets accuracy with a character string containing the accuracy of the GPS receiver, which will depend apon what detail is set to.
* GPS_SAME - The accuracy has not changed since the previous call to this function.
* GPS_DIFFERENT - The accuracy has changed since the previous call to this function.
	Functionality
GpsAccuracy sets accuracy to a text string of what the GPS accuracy is and is dependent apon detail. If detail is set to Expert then accuracy will be set to (GPS-2D, GPS-3D, DGPS-2D,DGPS-3D).  If detail is set to Novice then accuracy will be set to (POOR, FAIR, GOOD, EXCELLENT).  These character strings are in the G_(language).DLL for example G_AMERIC.DLL.  If Modify is TRUE the old accuracy will be replaced by the current accuracy.  
NOTE:  The return code GPS_SAME or GPS_DIFFERENT depends upon the accuracy not the string sent back through accuracy.  So if you call GpsAccuracy with detail set to Novice for the first time it will return GPS_DIFFERENT and accuracy will be set to "FAIR", and if you call it again with detail set to EXPERT it will return GPS_SAME and accuracy will be set to "GPS 3D".  The accuracy hasn't changed but the definition of what accuracy is has.
GpsStatus
Parameters
int FAR PASCAL _loadds GpsStatus(char far *status, int Modify)
* Current GPS status (char *) [Language Specific]
* Modify old status with new status [TRUE / FALSE]
Returns
* Sets status with a character string containing the status of the GPS receiver.
* GPS_SAME - The status has not changed since the previous call to this function.
* GPS_DIFFERENT - The status has changed since the previous call to this function.
Functionality
GpsStatus sets status to a text string of what the GPS status is.  These character strings are in the G_(language).DLL for example G_SA_001.DLL, where 001 is the country code for the language contained within.  If Modify is TRUE the oldstatus will be replaced by the current status.  The type of messages sent back through status depends upon what the receiver is doing, ie (Position Fixes, acquiring satellites, Downloading Almanac, 1 usable satellites, etc.)
GpsStatusAcc
Parameters
int FAR PASCAL _loadds GpsStatusAcc( int far *stat, int far *acc)
* Current GPS status (int *) 
* Current GPS accuracy (int *)
Returns
* stat will be set to the current non-language specific status
* acc will be set to the current non-language specific accuracy
* Currently they always return GPS_DIFFERENT.  (April 19, 1996)
Functionality
This function is similar to both GpsStatus and GpsAccuracy but returns a numerical representation of the GPS status and accuracy, definitions found in strider.h.
GpsSatellites
Parameters
int FAR PASCAL _loadds GpsSatellites(Satellites *sats, int Modify)
* Sats structure to put current viewed satellites (Satellites *) 
* Modify old structure with new satellite information  [TRUE / FALSE]
Returns
* a filled in Satellite structure with the updated satellite information (ID, SNR, Azimuth, and Elevation)  & the # of satellites tracked.
* GPS_SAME - The satellite info has not changed since the previous call to this function.
* GPS_DIFFERENT - The satellite info has changed since the previous call to this function.
Functionality
GpsSatellites returns a structure of the # satellites being tracked, their ID's, Signal to Noise ratio (SNR), Elevation, and Azimuth (if these are available from the specific receiver).  If these are not available a hard coded N/A will be in these variables.
	ID
The satellites ID is the number associated with that particular satellite given to it by the US DoD.  This is a number between  1-32.
	SNR
The satellites SNR determines how strong a signal we are receiving from a given satellite, and therefore how accurate of a position fix we are getting from this satellite.  SNR can range between 0 and 25, where an SNR below 0 represents a satellite we were tracking but lost and in this case SNR for this satellite will be LOST.  The satellite information are returned in order of the satellites SNR.
	Elevation
The satellites Elevation is measured in degrees from sea level, where 90 degrees is straight overhead.
	Azimuth
The satellites Azimuth is measured in degrees from true north, this means if you are facing north and the Azimuth is 0 the satellite is right in front of you.
GpsErrors
Parameters
int FAR PASCAL _loadds GpsErrors(Errors *err)
* err structure to put any GPS error messages(Errors *) 
Returns
* a filled in Error structure with the updated GPS error information if any.
* GPS_SAME - No Errors have occurred
* GPS_DIFFERENT - A GPS Error has occurred.
Functionality
returns a structure of the different types of GPS errors Possible Errors are : Antenna fault, Battery backup, Clock Fault, Almanac Bad
GpsTime
Parameters
int FAR PASCAL _loadds GpsTime (double *time)
* The GPS time in seconds since Sunday (double *) 
Returns
* the number of seconds since midnight Saturday in GMT
* GPS_SAME - Current time is the same as the last time this function was called.
* GPS_DIFFERENT - GPS time has changed.
Functionality
GpsTime returns the GPS time as the # of seconds since Sunday in GMT time, it will returns 0 if no time is available.
	Units
time is the number of seconds since midnight Saturday in GMT time.

GpsDate
Parameters
int FAR PASCAL _loadds GpsDate (Dates *date)
* date structure to put the current date in(Dates *) 
Returns
* a filled in Dates structure with the updated GPS date.
* GPS_SAME - date has not changed since the last function call.
* GPS_DIFFERENT - date has changed.
Functionality
GpsDate sets a Dates structure with the current date information provided by the GPS receiver.
NOTE: This date is based apon GMT time, therefore checks must be made to make sure the correct date will be displayed depending upon the Time Zone the person is in.

GpsHSpeed
Parameters
int FAR PASCAL _loadds GpsHSpeed (double *hspeed)
* hspeed is the current GPS horizontal speed in meters/second (double *) 
Returns
* the GPS heading (horizontal) speed in meters/second
* GPS_SAME - no change in hspeed
* GPS_DIFFERENT - new GPS speed.
	Functionality
GpsHSpeed returns the current GPS Heading Speed.  (ie how fast we are travelling). In (meters / second) this can be changed in Strider to what the user wants as indicated in the INI file.
	Units
hspeed is the horizontal or heading speed of the GPS receiver in meters per second.

GpsHeading
Parameters
int FAR PASCAL _loadds GpsHeading (double *heading)
* heading is the current GPS heading in degrees (double *) 
Returns
* the GPS heading in degrees
* GPS_SAME - no change in heading
* GPS_DIFFERENT - new GPS direction.
	Functionality
GpsHeading returns the current GPS Heading, this is instantaneous, and may be inaccurate.
	Units
		heading is in degrees from true north.

GpsAltitude
Parameters
int FAR PASCAL _loadds GpsAltitude(double *alt)
* alt is the current GPS altitude in meters (double *) 
Returns
* the GPS alitude in Meters
* GPS_SAME - no change in altitude
* GPS_DIFFERENT - New altitude information.
	Functionality
GpsAltitude returns the current GPS Altitude in Meters.
NOTE : if we are in D/GPS 2D this value is very inaccurate.
	Units
alt is in meters above sea level.

GpsGetName
Parameters
void FAR PASCAL _loadds GpsGetName(char *name)
* name is the name of the GPS receiver & DLL (char *) [LANGUAGE INDEPENDENT] 
Returns
* the name of the GPS receiver's DLL set in name

GpsRevision
Parameters
void FAR PASCAL _loadds GpsRevision(Revisions *Rev)
* Rev Contains the version information for the DLL & the GPS receivers version information  & DGPS receivers version information.  (Revisions *) [LANGUAGE Specific] 
Returns
* the version of the GPS receiver's DLL 
* the GPS receiver's Navigation version information
* the GPS receiver Signal processor's version information
* the GPS receiver's third parties DLL version information
* the DGPS receiver's version information
Functionality
GpsRevision returns the version information of the DLL and the GPS receiver connected to it, which is provided by the GPS if available.  The Format of the DLL's version information is X.x.Yy, Date, where X is the Major revision, and x is the minor revision of gpsdll.c (the common GPS routines.  Y is the major revision and y is a letter denoting the minor revision of the GPS specific DLL routines found in (tsip.c taip.c allstar.c goldcard.c etc.).  The date is the last day gpsdll.c was modified.

Appendix G: OEM 4000 Technical Specifications [16]


OEM 4000 Specifications
Frequency range 87.0 - 108.0 MHz steps 
Sensitivity <-90dBm for RDS locking at 4Khz inj on 97% of the frequencies 
RDS detection around 1V (0dBV, -107dBm) 
Strong Signals <-10dBm typ 
Adjacent channel >74 dB at 400 kHz 
Antenna input impedance 50 ohms; other values an option 
Oscillator leakage -60 dBm 
Antenna connector SMB 

Power Supply: 	Voltage +5V DC, Supply current 95 mA, Connection through the 6 pin connector 

Data I/O: 	Serial port (main) RS232 or TTL 

Processor System:Serial I/O 1200-9600 baud N,8,1 
Signaling LEDs 1 red, 1 green 
Signal indication 40 dB dynamic 
Quick Scanning Algorithm 

DGPS functions:	Output: RTCM SC-104 Version 2, 1200-19200 baud, 8 data bits; 1 stop bit, no parity 
Type 1 every 2 seconds
Type 2 every 1 to 5 minutes or on change of ephemeris
Type 9 optionally replaces Type 1 message 

DGPS Channel Search Mode:	Band Scan (BS) 
User Defined List Scan (UDLS), Country Code filter option 

Mechanical Characteristics:	Size: 86.1 x 54.1 mm (credit card) 
Height: 17.1 mm with connectors, 11.1 mm without connector 
Weight: 40 g 

Environmental Features:		Temperature: 	Operating -30C to +70C, Storage -50C to +70C 
Vibration: 	0.08g/Hz: 5Hz - 20Hz
0.05g/Hz: 20Hz - 100Hz
03dB/octave: 100Hz - 900Hz 
Altitude: 	-400 to +18000 meters MSL 
Humidity: 	5 - 95% at 60C
Appendix H: Lassen SK8 Technical Specifications [17]
[18]
Performance Specifications
  General:	L1 frequency, C/A code (SPS), 8-channel, continuous tracking receiver, 32 correlators 
  Update rate:	TSIP @ 1 Hz; NMEA @ 1 Hz 
  Accuracy:	Position: 25 m CEP (50%) without SA, Velocity: 0.1 m/sec without SA 
Time: ±500 nano-seconds (nominal) 
  DGPS accuracy:	 Position: 2 m CEP (50%),Velocity: 0.05 m/s, Time: ±500 nano-seconds (nominal) 
  Acquisition: 	Cold start: <2 minutes (90%), Warm start: <45 seconds (90%) 
  (typical)	Hot start: <20 seconds (90%) 
Cold start requires no initialization. 
Warm start implies last position, time and almanac are saved by back-up power. 
Hot start implies ephemeris also saved. 
  Reacquisition after signal loss: < 2 seconds (90%) 
  Dynamics:	Altitude: -1000 m to +18,000 m, Velocity: 515 m/sec maximum 
Acceleration: 4g (39.2 m/sec 2 ), Motional Jerk: 20m/sec3 

  Environmental Specifications
  Operating temp:		-10°C to +60°C (standard), 40°C to +85°C (optional) 
  Storage temp:		-55°C to +100°C 
  Vibration:		0.008g2/Hz 5 Hz to 20 Hz, 0.05g2/Hz 20 Hz to 100 Hz
-3dB/octave 100 Hz to 900 Hz 
  Operating  humidity: 	5% to 95% R.H. non-condensing @ +60°C 
  Altitude:		-400 m to +18,000 m 

  Physical Characteristics
  Prime power:			+5 volts DC, ±5% 
  Power consumption  (nominal):	GPS board only: 150 ma, 0.75 watts, With antenna: 175 ma, 0.88 watts 
  Back-up power:			+3.2 to +5 volts DC 2 micro-amp @ +3.5 volts, +25°C (nominal) 
  Serial ports/1PPS:		CMOS TTL levels 
  Protocols:			TSIP @ 9600 baud, 8-O-1, NMEA 0183 v2.1 @ 4800 baud, 8-N-1 
RTCM SC-104 @ 4800 baud, 8-None-1 
  NMEA messages:		GGA, VTG, GLL, ZDA, GSV, GSA and 
RMC messages selectable by TSIP command; 
selection stored in non volatile memory 
  Antenna power:			5V at 25mA available Short circuit protection Feedline fault detection 
  Dimensions:			3.25" L x 1.25" W x 0.40" H (82.6 mm x 31.2 mm x 10.2 mm) 
without connectors 
3.29" L x 1.30" W x 0.52" H (83.6 mm x 33.0 mm x 13.2 mm) 
with connectors and optional shield 
  Weight:			0.7 oz. (19.6 g) without optional shield 
1.3 oz. (36.4 g) with optional shield 
  Connectors:			RF:SMB; I/O:8-pin(2x4), 0.100"header

Appendix I: Vector 2X Compass Specifications [12]

* 2(accuracy, 1( resolution
* 3.8 cm x 3.3 cm x 1.0 cm
* 8.5 grams
* single-sided 5 volt (regulated) supply
* < 10mA draw and <1mA in power down mode
* Low resolution output is 5 Hertz; high resolution output is 2.5 Hertz
* Input voltage on all I/O ports: -0.3 to VDD to +0.3 volts
* Output voltage on all I/O ports: -0.3 to VDD to +0.3 volts
* Output ports can source or sink 5mA
* 3-wire serial output format (Motorola SPI and National Micro-wire-compatible
* Hard iron calibration
* Raw uncalibrated output option
* Pin-selectable Binary-Coded Decimal or Binary output format
* Polled or continuous mode options
* Master or slave capability for data clock generation
* Operating temperature range: -20( C to 70( C.

Appendix J: Assembly Language for the ANS
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;               Alternative Navigation System
;
; This program will poll a pedometer, check the bearing on the step taken, store it,
; and when the computer signals transmit this data to the computer.
;
; By: Charles LaPierre 195138
; Masters Thesis Electrical Engineering
; Original Date: Dec 12, 1997  K Series
; Date: Feb. 24, 1998   J Series modifications
; Date: Mar. 21, 1998   compass modifications for signed 8-bit accumulator
; Date: Apr. 01, 1998   new debounce routine with internal Timer Interrupts
; Date: Apr. 08, 1998   fixes to pedometer & calibrate compass
; ROM used   : 573 bytes
; Stack used : 10  bytes (ISR)
;            : 2   bytes (delay_loop Subroutine)
; RAM used   : 32  bytes
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;                     Definitions
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;Compass

eoc_compass     equ 0   ;port B pin 0 connects the EOC pin from the compass
clock_compass   equ 1   ;port B pin 1 connects the SCLK pin from the compass
data_compass    equ 2   ;port B pin 2 connects the SD0 pin from the compass
poll_compass    equ 3   ;port B pin 3 connects the P/C pin from the compass
cal_compass     equ 4   ;port B pin 4 connects the CAL pin from the compass
power_compass   equ 5   ;port B pin 5 connects the VCC pin from the compass
sw1_cal_compass equ 1   ;port A pin 1 connects to SW1 to initiate compass calibration
reset_compass   equ 6   ;port A pin 6 connects the RESET pin from the compass
select_compass  equ 7   ;port A pin 7 connects the SS pin from the compass
compass_port_B  equ $01 ;port B's location (Compass is on Port B)
compass_port_A  equ $00 ;port A's location (reset & select are on Port A)


;Serial Communication
send_data       equ 0   ;port A pin 0 Computer requests Data
data_serial     equ 4   ;port A pin 4 Sends serial communication to the comp.
control_serial  equ 5   ;port A pin 5 controls GPS/Backup to the serial port
serial_port     equ $00 ;port A's location (Serial communication is on Port A)

;MASK Options MOR

MORaddr         equ $7F1;location of MOR's address
MOR_options     equ $24 ;SOSCD  = 0 Short Oscillator delay disabled
                        ;EPMSEC = 0 access to EPROM array
                        ;OSCRES = 1 crystal oscillation configuration
                        ;SWAIT  = 0 STOP
                        ;SWPDI  = 0 enable pulldown transistors
                        ;PIRQ   = 1 Port A's pins 0-3 are IRQ's
                        ;Level  = 0 Negative edge triggered Interrupt
                        ;COPEN  = 0 Cop disabled

;TIMER Options

Timer_addr      equ $08 ;location of Timer Status & Control Register
Enable_Timer    equ 4   ;Real Time Interrupt Enabled
Reset_T_Flag    equ 2   ;Real Time Interrupt Flag Reset
                        ;Set RT0=0 & RT1 to 1, so that we get an interrupt
                        ;every 32.8ms

;Port A configuration
PORTA_dataReg   equ $00 ;Port A's Data Register
PullDown_A      equ $10 ;port A's Pulldown Register
DDRA            equ $04 ;port A's Data Direction Register
DDRA_options    equ $F0 ;pin 7 1 - SS       output
                        ;pin 6 1 - RESET    output
                        ;pin 5 1 - Control  output
                        ;pin 4 1 - Output   output
                        ;pin 3 0 - NC       input
                        ;pin 2 0 - NC       input
                        ;pin 1 0 - SW1      input
                        ;pin 0 0 - Computer input
PORTA_INIT      equ $C0 ;Must set the proper state before we
                        ;set port A pins as output
                        ;pin 7    1 -SS
                        ;pin 6    1 -RESET
                        ;pin 5    0 -Control
                        ;pin 4    0 -Data output
                        ;pins 3-0 0 -these are inputs
;Port B configuration

PORTB_dataReg   equ $01 ;Port B's Data Register
PullDown_B      equ $11 ;Port B's Pulldown Register
DDRB            equ $05 ;port B's Data Direction Register
DDRB_options    equ $3A ;pin 5 1 - VCC compass  output
                        ;pin 4 1 - CAL compass  output
                        ;pin 3 1 - PC compass   output
                        ;pin 2 0 - SD0 compass  input
                        ;pin 1 1 - SCLK compass output
                        ;pin 0 0 - EOC compass  input
PORTB_INIT      equ $1A ;Must set the proper state before we
                        ;set port B pins as output
                        ;pin 5 0 -VCC initially 0
                        ;pin 4 1 -CAL compass
                        ;pin 3 1 -PC compass
                        ;pin 2 0 -SD0 input Don't care
                        ;pin 1 1 -SCLK compass
                        ;pin 0 0 -EOC input Don't care

;state configuration
state_lb        equ 0 ;1'st bit
state_hb        equ 1 ;2'th bit

;degree data
eighth          equ 0 ;1'st bit
ninth           equ 1 ;2'nd bit
neg_step        equ 2 ;3'rd bit (negative step taken)

;ISR
IRQ_Status      equ $0A ;location of IRQ Status/control Reg.
IRQ_dis_en      equ 7   ;enable / disable interrupts
IRQ_clear       equ 1   ;clear interrupt flag
isrtemp_lb      equ 0   ;mask bit
isrtemp_hb      equ 1   ;mask bit

;Directions Storage Array
dir_used        equ $11  ;Uses 18 memory locations to store directions
dir_res         equ $0A  ;each 10 degree resolution

;Delay Timings
                         
delay_eoc       equ $16  ;delay to wait after EOC goes high (indicating valid data)
delay_cal       equ $30  ;delay to calibrate compass (~ 200ms)
delay_data      equ $08  ;delay to retrieve data from compass
delay_pc        equ $16  ;delay to hold PC low. for compass
delay_power     equ $01  ;delay long enough for pins to be set high.
delay_inner     equ $FF  ;inner loop 255 times
delay_half_sec  equ $70  ;delay for ~ 1/2 a second for calibration & testing

;Program locations

RAMStart        equ $00C0 ;Start of on chip RAM
ROMStart        equ $0300 ;Start of on chip EPROM
ROMEnd          equ $07CF ;End of on chip EPROM
Vectors         equ $07F8 ;Start of Reset/Interrupt vectors
COPR            equ $07F0 ;COP's Reset Register location



;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;                    RAM
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;Ram used 33 bytes
                ORG RAMStart

state           RMB 1 ;Internal State of the machine
                      ;0-Nothing
                      ;1-Step occurring
                      ;2-Waiting for direction (i.e. step already occurred)
                      ;3-Step occurring & Waiting for direction

step_count      RMB 1 ;# of steps occurred while waiting for a direction (max 127)
char_send       RMB 1 ;Current character sending out serial port
CRC             RMB 1 ;CRC control
temp            RMB 1 ;temp storage variable used as a mask and a counter
degrees         RMB 1 ;bit 0 is 8'th bit test, bit 1 is 9'th bit test, bit 2 is
                      ;negative step taken
indexoffset     RMB 1 ;shifting the directions offset because of signed problems.

directions      RMB dir_used+1 ;18 element array for storing the # of steps in any
                               ;direction with 10 degree resolution
tempa           RMB 1 ;temp storage place to store A reg.
tempx           RMB 1 ;temp storage place to store X reg.
tempisrx        RMB 1 ;temp storage place in ISR to store X reg.
tempisr         RMB 1 ;temp storage signifying which data type being sent
delay_outer     RMB 1 ;outer loop delay timing
stepcomp        RMB 1 ;step occurred while sending to the computer
cal_check       RMB 1 ;debouncing of calibration switch
ped_timer       RMB 1 ;After x * (8.2 ms) uninterrupted interrupts a step occurred.
ped_timing      RMB 1 ;pedometer debounce timing (default 205ms, can range 106ms-xxxms)
ped_debounce    RMB 1 ;non 0 if an interrupt from pedometer occurs during the
                      ;205 ms  This is our debouncing of the switch.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;                              MAIN PROGRAM
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Main program
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

            ORG ROMStart

; Initalize the RAM, and set the Ports & interrupts
; uses 69 bytes
start       RSP                 ;Reset Stack Pointer
            CLRA                ;clear the accumulator
            CLRX                ;clear the x reg
            CLI                 ;clear interrupt mask
;portA
            LDA #PORTA_INIT     ;Initialize Port A's Data register
            STA PORTA_dataReg   ;set the Port's data reg. before changing the DDRA
            CLRA                ;set all output pins to have pulldowns
            STA Pulldown_A
            LDA #DDRA_options   ;port A's Input / Output pins
            STA DDRA            ;store in the DDRA the ports options
;portB
            LDA #PORTB_INIT     ;Initialize Port B's Data register
            STA PORTB_dataReg   ;set the Port's data reg. before changing the DDRB
            CLRA ;set all output pins to have pulldowns on port B
            STA PullDown_B
            LDA #DDRB_options   ;port B's Input / Output pins
            STA DDRB            ;store in the DDRB the ports options
;timer
            BCLR 0,Timer_addr   ;set RT0 to 0 for the 8.2ms interrupt
            BCLR 1,Timer_addr   ;Set RT1 to 0 for the 8.2ms interrupt
            BCLR Enable_Timer,Timer_addr;disable interrupts until a step occurs
            BSET Reset_T_Flag,Timer_addr;clear the interrupt flag for the timer

;ram
            LDX #RAMStart       ;location of RAM
clear_ram   CLR 0,X             ;clear the RAM
            INCX                ;go to next RAM location
            BNE clear_ram       ;(Since RAM is from C0-FF once inc past FF we get 00
                                ;in the X reg.)
;power up compass with CAL,PC,Reset,and SS high so as to not hang the compass.
            BSET cal_compass,compass_port_B;
            BSET poll_compass,compass_port_B;
            BSET reset_compass,compass_port_A;
            BSET select_compass,compass_port_A;
            LDX #delay_power    ;wait a min time for pins to go high
            STX delay_outer     ;set outer loop delay
            JSR delay_loop      ;may not need this.
            BSET power_compass,compass_port_B;turn on the power to compass

            LDA #$19            ;(25dec  25*8.2ms = 205ms)
            STA ped_timing      ;debounce timing is default at 205ms

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;                           main program loop                             ;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;6 bytes
main        BRSET state_hb,state,compass ;are we waiting for a direction
                            ;is state == 2 || state == 3
                            ;exit poll compass if we are not
                            ;waiting for a direction
main_end    JMP main

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;                             delay_loop                                 ;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; delays for compass timing etc.
; 14 bytes used
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
delay_loop  LDX delay_outer ;outer loop timing (memory location)
delay_i     LDA #delay_inner;inner loop 255
delay_j     NOP             ;2cycles
            NOP             ;2cycles
            TSTA            ;3cycles
            DECA            ;3cycles
            BNE delay_j     ;3cycles
            DECX            ;3cycles
            BNE delay_i     ;3cycles
            RTS             ;return from Subroutine


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;                         poll compass                                   ;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; poll compass uses 106 bytes
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

compass     BRCLR eoc_compass,compass_port_B,main_end ;Is EOC high
                            ;indicating a direction is available
            LDA #delay_eoc  ;timing delay for valid data
            STA delay_outer
            JSR delay_loop  ;must wait a min. of 10ms before
                            ;getting data from compass
            BCLR select_compass,compass_port_A ;lower SS
            JMP get_dir     ;reads in high/low byte & sets neg dir. if high byte
fin_dir     BSET select_compass,compass_port_A ;raise SS
            BRSET ninth,degrees,deg256_360;degrees is between 256-360
            BRSET eighth,degrees,deg128_255;degrees is between 128 and 255
deg0_127    BCLR neg_step,degrees ;we have a positive step
            LDX #$00        ;no offset (0 - 127 degrees) (positive direction)
            STX indexoffset ;store the 0
            JMP store_dir   ;store the direction

deg128_255  CMP #$34        ;52 dec are we between 0 & 51
            BHS deg180_255  ;or between 52 & 127
deg128_179  BCLR neg_step,degrees ;we have a positive step
            ADD #$08        ;shift the dec # between 8 & 59 degrees
            LDX #$0C        ;index offset is 12dec so degree range jumps to
                            ;128 degrees to 179 degrees (positive direction)
            STX indexoffset ;store the offset
            JMP store_dir   ;store the new direction

deg180_255  BSET neg_step,degrees ;we have a negative step
            SUB #$34        ;52 dec shift the dec # between 0 & 75 degrees
                            ;(but in the negative direction)
            LDX #$00        ;no offset
            STX indexoffset ;store the offset
            JMP store_dir   ;store the direction

deg256_360  BSET neg_step,degrees ;we have a negative step
            ADD #$06        ;add six to the degrees for axis shifting
                            ;degrees is 6 & 109
            LDX #$07        ;index offset shift so new degrees is shifted from
                            ;76 - 179 degrees (but in negative direction)
            STX indexoffset ;store the offset
            JMP store_dir   ;store the direction



store_dir   CLRX            ;acc has a number between (0 & 180) and test bit 7 tells
                            ;us if its + or -
                            ;we need to do a divide by multiple subtracts of 10
div_loop    CMP #dir_res    ;is the # in the accumulator <10
            BLO found_spot  ;we found the position in the indexed array of directions
            INCX            ;move to next array position
            SUB #dir_res    ;reduce the direction by 10 degrees to find offset into
                            ;array
            JMP div_loop    ;loop until acc <10
found_spot  TXA             ;get the current index
            ADD indexoffset ;add the offset to index
            TAX             ;store in the x reg.
            LDA step_count  ;get step count

            BRCLR neg_step,degrees,pos_dir ;we have a positive direction
            NEGA            ;make the steps negative which indicates a negative dir.
pos_dir     ADD directions,X;add the current directions (steps) to the current steps
                            ;in that direction
                            ;step_count = step_count + directions[x] (where x=0-17)
            STA directions,X;store new steps in direction array
            CLR step_count  ;clear the step count
            BCLR state_hb,state ;state=state-2
                            ;waiting for direction goes to nothing & waiting for
                            ;direction & step goes to waiting for step
            JMP main_end    ;finished poll_compass

;;;;;;;;;
;get_dir;
;;;;;;;;;
;71 bytes
;the clocking is not even, but the compass can handle it.

get_dir     CLRA            ;char_storage location
            STA degrees     ;clear the degrees
            LDX #delay_data ;timing for outloop
            STX delay_outer
            LDX #$10        ;loop counter
byte_loop   STA tempa
            STX tempx
            JSR delay_loop
delay_comp1 BCLR clock_compass,compass_port_B ;[5]lower clock
            JSR delay_loop
delay_comp2 LDA tempa
            LDX tempx
            BSET clock_compass,compass_port_B ;[5]raise clock
            BRSET data_compass,compass_port_B,byte_high ;[5]get bit
byte_low    CLC             ;[2]clear the carry for shift
            JMP rotate      ;[2]low byte finished
byte_high   SEC             ;[2]set the carry for shift
            JMP rotate      ;[2]timing
rotate      ROLA            ;[3]rotate in the data bytes
            CPX #$08        ;[2]are we on the 1'st bit in Low byte
            BEQ test_eight  ;[3]check for bit being set
            CPX #$09        ;[2]are we on the 8'th bit in High byte
            BEQ test_nine   ;[3]check for high bit being negative
            DECX            ;[3]loop = loop -1
            BNE byte_loop   ;[3]loop until we get all bytes
            JMP fin_dir     ;jump to the high byte read
test_nine   DECX            ;[3]loop-1
            TSTA            ;[3]check to see if we have a negative direction
            BEQ byte_loop   ;[3]we have a + direction, get next byte
            BSET ninth,degrees;[5]we have a 1 in the ninth spot.
            CLRA            ;[3]clear the accumulator
            JMP byte_loop   ;[2]
test_eight  DECX            ;[3]loop-1
            BRCLR data_compass,compass_port_B,eight_not
                            ;[5]check to see if we have a 1 from the 8'th bit in
            BSET eighth,degrees;[5]we have a 1 in the eighth spot
eight_not   CLRA            ;[3]clear the accumulator
            JMP byte_loop   ;[2]


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;                    Interrupt Service Routines
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; ISR uses 256 bytes
; ISR uses 5 bytes of stack space
;
; IRQ line tied to the Pedometer
; PA0 line tied to the computer request data (RTS)
; PA1 line tied to the calibrate compass switch SW1
; PA2 line used for debugging debounce routine sets timing to 106.6ms
; PA3 line used to increment debounce timing by 8.2ms each time in.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


;28 bytes
ISR         BCLR IRQ_dis_en,IRQ_Status ;disable interrupts
            BRSET send_data,serial_port,Send_JMP;did the computer cause interrupt?
            BRSET sw1_cal_compass,compass_port_A,Reset_Comp;did SW1 cause interrupt?
            BIL Pedometer   ;pedometer cause interrupt
            BRSET 2,compass_port_A,Set_106ms;reset debounce routine to 106.6ms
            BRSET 3,compass_port_A,Inc_deb;add 8.2ms to debounce routine
ISR_fin     BSET IRQ_clear,IRQ_Status ;clear current interrupts
            BSET IRQ_dis_en,IRQ_Status ;re-enable interrupts
            RTI             ;return from ISR


;;;;;;;;;;;
;Pedometer;
;;;;;;;;;;;
;18 bytes
Pedometer   BRCLR Enable_Timer,Timer_addr,start_timer;first hit of pedometer
                            ;enable the timer to debounce pedometer
            INC ped_debounce;only 106ms+ of uninterrupted steps is considered a step
            JMP ISR_fin     ;finished here

start_timer BSET state_lb,state ;change state was 0 goto 1, was 2 goto 3;
            BSET Enable_Timer,Timer_addr;enable the timer interrupt
            CLR ped_debounce;clear the debounce routine
            JMP ISR_fin     ;finished


;;;;;;;;;;;;;;;;;;;
;calibrate compass;
;;;;;;;;;;;;;;;;;;;
;69 bytes
Reset_Comp  LDA cal_check   ;did we already calibrate
            BNE ISR_fin     ;debouncing possible here
            LDA #delay_cal  ;outer loop delay for calibrating the compass
            STA delay_outer
            BCLR reset_compass,compass_port_A;reset the compass
            JSR delay_loop  ;delay 1
            BSET reset_compass,compass_port_A;toggle line
            JSR delay_loop  ;delay 2
            BCLR cal_compass,compass_port_B;calibrate compass
            JSR delay_loop  ;delay 3
            BSET cal_compass,compass_port_B;finished calibrating part A
wait_switch BRSET sw1_cal_compass,compass_port_A,wait_switch;wait for user
                            ;release the switch
            LDA #delay_half_sec; wait 1/2 a second before testing
            STA delay_outer
            JSR delay_loop  ;delay 4
wait_180    BRCLR sw1_cal_compass,compass_port_A,wait_180;wait for user to
                            ;turn 180 degrees and pulse the switch again
            BCLR cal_compass,compass_port_B;calibrate compass

            LDA #delay_cal  ;outer loop delay for calibrating the compass
            STA delay_outer
            JSR delay_loop  ;delay 5
            BSET cal_compass,compass_port_B;finished calibrating part B
reset_fin   BRSET sw1_cal_compass,compass_port_A,reset_fin;wait till switch is released
            LDA #delay_half_sec; wait 1/2 a second for bouncing to settle
            STA delay_outer
            JSR delay_loop  ;delay 6
            BSET IRQ_clear,IRQ_Status;clear current interrupts because
                            ;calibrating the compass caused more interrupts.
            INC cal_check   ;just a check to make sure we don't go in twice
                            ;this gets reset after the computer asks for the
                            ;data.
            JMP ISR_fin     ;Done

;jump point
;2 bytes
Send_JMP  JMP Send_Comp; out of rang for branch.

;;;;;;;;;;;;;;;;;;;;;;;;;
;Reset debounce to 106.6ms;
;;;;;;;;;;;;;;;;;;;;;;;;;
;16 bytes
;This routine will reset the debounce timing to 106.6ms
Set_106ms   LDA #$0D        ;0D=13dec (13 * 8.2ms = 106.6ms)
            STA ped_timing  ;set the new debounce time interval to 124ms
wait_106    BRSET 2,compass_port_A,wait_106;wait for user to exit
            LDA #delay_half_sec; wait 1/2 a second for bouncing to settle
            STA delay_outer
            JSR delay_loop  ;delay 6
            JMP ISR_fin     ;Done


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;Increment debounce by 8.2ms;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;30 bytes
;This routine will keep looping and each time SW1 (CAL Compass) is pushed an
;extra 8.2ms is added onto the debounce timing for the pedometer.
;exits by user releasing PA3
Inc_deb     BRSET sw1_cal_compass,compass_port_A,add_ms;use cal compass switch
            BRSET 3,compass_port_A,Inc_deb;wait until user releases PA3
            LDA #delay_half_sec; wait 1/2 a second for bouncing to settle
            STA delay_outer
            JSR delay_loop  ;delay
            JMP ISR_fin     ;Done

add_ms      INC ped_timing  ;increments by 8.2ms
wait_sw1    BRSET sw1_cal_compass,compass_port_A,wait_sw1;wait for user
            LDA #delay_half_sec; wait 1/2 a second for bouncing to settle
            STA delay_outer
            JSR delay_loop  ;delay
            JMP Inc_deb     ;loop back

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;step occurred while sending data to the computer
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;5 bytes
step_w_comp  BCLR 0,stepcomp ;clear the step flag
             JMP Pedometer   ;get the step which happened in the send routine

;;;;;;;;;;;;;;;;;;;;;;;
;Send Data to Computer;
;;;;;;;;;;;;;;;;;;;;;;;
;114 bytes
Send_Comp   BSET control_serial,serial_port ; stop GPS from transmitting
            CLR tempisrx    ;used in CRC check so it must be set to 0
            CLR CRC         ;clear the CRC value
            BSET isrtemp_lb,tempisr ;Mask bits 01 = header  being sent
            BCLR isrtemp_hb,tempisr ;
            LDA #$AA        ;header=10101010
            JMP send_byte   ;send the header
end_header  LDA #$10        ;[2] 16 dec. delay loop to keep timing from header to body
                            ;character sent (172 between successive char)
                            ;(28 of which has or will be wasted getting to body char
                            ; & executing the JMP command)
                            ;144 cycles to waist
keep_t_h0   TSTA            ;3-|
            DECA            ;3 |loop 16*9=144 (144+28=172)
            BNE keep_t_h0   ;3-|
            NOP             ;[2] part of 28
            NOP             ;[2] part of 28
            LDX #dir_used   ;[2]loop through all directions
            BCLR isrtemp_lb,tempisr;[5]tempisr=xxxx xx10
            BSET isrtemp_hb,tempisr;[5]10=body bytes being sent
send_dir    LDA directions,X;[4]get the current loop_count steps Acc = directions[x]
            STX tempisrx    ;[4]we need the X reg to transmit the data
            JMP send_byte   ;[2]send the data byte
end_byte    LDX tempisrx    ;[3]get the current loop count
            DECX            ;[3]count=count-1
            BMI send_crc    ;[3]finished sending all characters

            LDA #$09        ;[2]9dec.delay loop to keep timing for body data
                            ;characters sent (172 between successive char)
                            ;19 of which has or will be wasted getting to body char
                            ;172-19=153 cycles to waist in delay loop
keep_t_d0   BIL step_d0     ;                               3--|
            BCLR 1,stepcomp ;do nothing timing filler       5| |loop
            BRA dec_aa      ;                               3| |17*9
step_d0     BSET 0,stepcomp ;signal that a step occurred    5 :|=153
            BRA dec_aa      ;                               3 :|
dec_aa      DECA            ;                               3  |
            BNE keep_t_d0   ;                               3--|
            TSTA            ;[3]
            TSTA            ;[3]
            JMP send_dir    ;[2]send next direction
                            ;now calc. & send CRC
send_crc    BCLR isrtemp_lb,tempisr;[5]temp=xXXx xx00
            BCLR isrtemp_hb,tempisr;[5]00=CRC being sent
            LDA #$08        ;[2]8dec.delay loop to keep timing from body to CRC
                            ;character sent (172 between successive char)
                            ;(38 of which has or will be wasted getting to CRC char.
                            ;172-36=136 cycles to waist
keep_t_crc  BIL step_crc    ;                               3--|
            BCLR 1,stepcomp ;do nothing timing filler       5| |loop
            BRA dec_aaa     ;                               3| |17*8
step_crc    BSET 0,stepcomp ;signal that a step occurred    5 :|=136
            BRA dec_aaa     ;                               3 :|
dec_aaa     DECA            ;                               3  |
            BNE keep_t_crc  ;                               3--|
            NOP                         ;[2]
            NOP                         ;[2]
            TSTA                        ;[3]extra delay part of 36 cycles
            TSTA            ;[3]needed this extra delay (part of the 32cycles)
            LDA CRC         ;[3]get CRC
            JMP send_byte   ;[2]send CRC
end_crc     LDX #dir_used   ;[2]17 dec. Clear the directions array
clear_loop  CLR directions,X;[6]directions[x]=0 |
            DECX            ;[3]x=x-1           |(12x18=216)
            BPL clear_loop  ;[3]loop till X=-1  |
end_send    BCLR control_serial,serial_port ; allow GPS to resume transmitting
            BRSET 0,stepcomp,step_w_comp;signal that a step occurred jump to pedometer
            CLR cal_check ;allow the compass to be re-calibrated again
            JMP ISR_fin     ;Done


;;;;;;;;;;;
;Send_byte;
;;;;;;;;;;;
;66 bytes

send_byte   STA char_send   ;save the character             4 |
            ADD CRC         ;add current char to the CRC    3 |
            NOP             ;timing                         3 |entering
            STA CRC         ;save new CRC value             4 |send_byte
            LDX #9          ;8 data bits                    2 |=18 cycles
            CLC             ;clear carry start bit          2 |
put_data_b  BCC send_0      ;if carry is a 0 send a 0       3----------|
            BSET data_serial,serial_port ;send a 1          5:         |
            BRA delay1bit   ;skip sending a 0               3:         |
send_0      BCLR data_serial,serial_port ;send a 0          5|         |
            BRA delay1bit   ;put here to keep timing                   |
                            ;constant between bits send     3|         |
delay1bit   LDA #$0A        ;10dec.                         2          |Main
delay_send  BIL step_data   ;                               3--|       |bit
            BCLR 1,stepcomp ;do nothing timing filler       5| |loop   |sending
            BRA dec_a       ;                               3| |17*10  |loop
step_data   BSET 0,stepcomp ;signal that a step occurred    5 :|       |
            BRA dec_a       ;                               3 :|       |
dec_a       DECA            ;                               3  |=170   |38+170
            BNE delay_send  ;                               3--|       |=208 cycles
            NOP             ;                               2          |between bits
            TSTA            ;                               3          |
            TSTA            ;                               3          |Therefore
            TSTA            ;                               3          |before JMP
            TSTA            ;                               3          |to routine
            ROR char_send   ;send next bit of character     5          |208-36=172
                            ;                                          |36=10exiting
            DECX            ;loop through all bits of the              |+26entering
                            ;character                      3          |must be used
            BNE put_data_b  ;end loop                       3----------|between
send_stop   TSTA            ;delay 3 cycles due to not        |         header & body
                            ;doing a BCC as when sending      |         & CRC
                            ;data                           3 |leaving  |
            BSET data_serial,serial_port ;send stop bit     5 |send_byte|-send stop
            BRSET isrtemp_lb,tempisr,wait_head; 01= header  5 |--header =5 cycles
            BRSET isrtemp_hb,tempisr,end_byte ;10= send_char5 |--body   =10 cycles**
            JMP end_crc     ;00=CRC called this routine     2 |--crc    =12 cycles
wait_head   TSTA            ;[3] keep timing the same         |5+3 = 8
            JMP end_header  ;[2] adds 5 cycles to header      |2   = 10 cycles**
                            ;timing == body timing...
                            ;crc doesn't matter since were done at that point

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;                    TIMER Interrupt Service Routine
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; ISR uses 51 bytes
; ISR uses 5 bytes of stack space
;
; This timing routine is called every 8.2ms after the initial step occurs from
; the pedometer.  While the pedometer is bouncing, this routine keeps resetting
; until the pedometer is bounce free for 124+ms(default is 205 ms)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

TIMER       BSET Reset_T_Flag,Timer_addr;clear the interrupt flag
            LDA ped_debounce;did an interrupt occur during this 8.2 ms?
            BEQ inc_timer   ;add 1 to the timing routine
            CLR ped_debounce;clear the debounce flag
            CLR ped_timer   ;start the 100ms over again.
            RTI             ;keep doing this until we get x ms of no bounces
inc_timer   INC ped_timer   ;add 1 to the timer until we have x or (8.2 ms * x)
            LDA ped_timer   ;get # of times into this routine
            CMP ped_timing  ;is this the xth time in?
            BEQ step_taken  ;123ms+ of no bounces from pedometer, therefor step taken
            RTI             ;<x times in here.
step_taken  BCLR Enable_Timer,Timer_addr;disable timer interrupt
            CLR ped_timer   ;reset timer counter to 0
            INC step_count  ;steps taken ++
            BRSET state_hb,state,ped_state;if we have state=3
                            ;state not 1 ie. already polled compass just exit
                            ;poll the compass to get direction for state
            BCLR poll_compass,compass_port_B ;lower P/C
            LDX #delay_pc   ;wait at least 10ms before raising PC
            STX delay_outer
            JSR delay_loop
            BSET poll_compass,compass_port_B ;raise P/C
ped_state   BSET state_hb,state ;xxxx xx1x
            BCLR state_lb,state ;xxxx xxx0
                            ;change state to wait for compass
                            ;state 1 or 3 becomes 2 (Waiting for direction)
fin_ped     RTI


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;                    Vectors
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

            ORG Vectors
            FDB TIMER       ;timer interrupt routine
            FDB ISR         ;IRQ vector
            FDB start       ;SWI (not used)
            FDB start       ;Reset vector

Appendix K: Pseudocode for Pedometer and Timer
Pedometer's ISR
The program enters this ISR on a negative edge of the IRQ line, and during the bouncing phase it will enter this routine a number of times and each time setting the bounce flag.

Pedometer_ISR
	IF (pedometer timer is not enabled)
Enable timer
Clear bounce_occurred flag
IF (state equals idle)
Set state to step_occuring
		ELSE
			Set state to step_occuring_waiting_for_direction
		ENDIF
	ELSE
Set bounce_occurred flag
	ENDIF
RETURN

Timer's ISR
Once the timer is enabled, the program enters this ISR every 8.2 ms until the timer is disabled which occurs after 205 ms of non-bouncing from the pedometer.

Timer_ISR
	IF (bounce_occurred)
		reset 205 ms counter
clear the bounce_occurred flag
	ELSE
		Add 1 to the 205 ms counter
		IF (205 ms counter equals 25)
			disable interrupt timer
			reset 205 ms counter
			register the step
			IF (state equals step_occurring)
			signal compass a new direction is needed
		ENDIF
			change state to step_occurred_waiting_for_direction
		ENDIF
ENDIF
RETURN
Appendix L: Pseudocode for Calibration of the Compass

The program enters this routine when the compass calibration switch SW1 is pressed.
Calibrate_Compass
	Debounce the switch 
	Reset the compass
Pulse the compass calibration line for at least 10 ms
Wait until the switch is pressed again
Pulse compass calibration line for at least 10 ms
Debounce the switch
RETURN

Appendix M: Pseudocode for Obtaining a Direction

The program continuously enters this routine checking to see if a direction needs to be obtained.
Poll_Compass
	IF (state equals waiting_for_direction)
IF (EOC is HIGH)
Clock in the first 8-bits of data from the compass
Save the LSB
Clock in the last 8-bits of data from the compass
Determine index into array based upon the data received
Determine if the steps are in the forward or reverse direction
IF (direction is positive (i.e. 0 - 179 degrees))
	Add the current Step_Count 
to the newly indexed array element
ELSE
	Subtract the current Step_Count 
from newly indexed array element
			ENDIF
Clear the Step_Count
Change state to indicate not waiting_for_direction
		ENDIF
	ENDIF
	RETURN




Appendix N: Pseudocode for Transmitting Data to the Computer
Send_Data_ISR
Disable interrupts
Disable the GPS from transmitting
Set CRC equal to the Header
Send Header (10101010)
Get first array element 
DO
Add data to CRC value
Send Data
Get next array element
WHILE (more data to send)
Send CRC value
Clear storage array
Enable the GPS to transmit
Enable interrupts
RETURN

Appendix O: Pseudocode for the Windows Test Program

Main Program
Initialize Window
Initialize RS-232 port from INI file settings
Start two-second TIMER
DO
IF (TIMER equals 2 seconds)
Signal microprocessor to send data
Read data from RS-232 port
IF (valid data)
	Draw steps taken on the screen
	IF (recording data)
		Save data to file
	ENDIF
ENDIF
Reset timer
ENDIF
	IF (key pressed)
		Get key pressed from keyboard
		IF (key pressed equals R)
			Start recording data
		ENDIF
		IF (key pressed equals S)
			Stop recording data
		ENDIF
		IF (key pressed equals L)
			Load prerecorded data
ENDIF
		IF (key pressed equals C)
			Clear screen and data
		ENDIF
	ENDIF
WHILE (key does not equal Q)
Close RS-232 port
Close Window
EXIT

References

[1] LaPierre, Charles. "Navigational System for the Visually Impaired", fourth year project, Department of Electronics, Carleton University, (8 April 1993).

[2] LaPierre, Charles. "Feasibility Study for Sextant", Visuaide 2000. (2 September 1993) pg.6, 24.

[3] "Cars: GPS Introduction", Roadrunning. (No author cited)  http://www.roadrunning.com/cars/gps.html

[4] Dr Mattos, Philip G., SGS-Thomson. "The integration of GPS into car navigation systems", Electronic Engineering, (Vol 69 No.850 October 1997). pp. 43-48.

 [5] Horizontal Adjustment System, Berkeley University. (No author cited) http://epoch.cs.berkeley.edu:8000/sequoia/schema/html/saif/HorizontalAdjustmentSystem.html

[6] Hurn, Jeff. "GPS A Guide to the Next Utility". Sunnyvale, CA: Trimble Navigation Ltd. (1989). pp.38-46.

[7] Wells, David. "Guide to GPS Positioning" Canadian GPS Associates, (May 1987) pp.4.22 - 4.24.
 
[8] "Rough trip through the atmosphere", "Rough trip on the ground", Trimble Navigation Limited. (No author cited) [A leader in GPS technology] http://www.trimble.com/gps/howworks/aa_hw6.htm.

[9] Dentremont, Darren. "Inertial Guidance System", fourth year project, Department of Electronics, Carleton University, (8 April 1994).

[9a] Norling, Brian. "ACCELEROMETERS: CURRENT AND EMERGING TECHNOLOGY", Kinematics Systems in Geodesy, Surveying, and Remote Sensing, (Sept. 1990) pp.70-83.

[9b] Genberg, Stewart et al, "ACCELERATION SENSORS FOR SOLID STATE ELECTRONIC SAFETY AND ARMING DEVICES", International Journal for Hybrid Microelectronics, Vol:12 Iss: 3 (Sept. 1989), pp.126-138

[9c] Peters, Timothy J., "Automobile Navigation Using a Magnetic Flux-Gate Compass", Transactions on Vehicular Technology, Vol: VT-35 No: 2 (May 1986)

[9d] Kirlin, Clyde, "Compass of the Future", IEEE PLANS'88, pp.12-14.

[9e] Shurclff, William A. and Ballard, Stanley S., "Polarized Light", D. Van Norstrand Company Inc., (1964).

[10] "Accelerometer Data Sheets Application Notes and Worldwide Sales Directory", Analog Devices. (1995 REV A.) (No author cited) pp.6-9.

[11] "HC05 MC68HC705J1A Technical Data", Motorola. (1995 Rev. 1) (No author cited)
 
[12] "Vector 2X Compass Module Application Notes", Precision Navigation, Inc. Version 1.03 (January 1996) (No author cited)

[13] Judd, Tom. "A Personal Dead Reckoning Module", Point Research Corporation, [paper presented at the Institute of Navigation's ION 97, 9/97, Kansas City, MO] http://www.pointresearch.com/ionpaper.htm

[14] George, Scott. "HC05 MCU Software-Driven Asynchronous Serial Communication Techniques Using the MC68HC705J1A", Motorola. (1995 AN1240/D).

[15] Arnold-Ince, Kasey. "Atlas Speaks User's Guide", Arkenstone Inc. (1995), p 16, pp.77-81, pp.87-89.

[16] "OEM 4000 -- High Performance, credit card size, FM receiver for Differential GPS embedded applications.", Differential Corrections Inc.. (No author cited) [A leader in DGPS technology] http://www.dgps.com/oem4000.htm. 
 
[17] "Lassen SK8 -- Performance Specification", Trimble Navigation Limited. (No author cited) [A leader in GPS technology] http://www.trimble.com/products/specs/frm_om06.htm. 
 
[18] "Lassen SK8 -- Miniature 8-channel receiver board", Trimble Navigation Limited. (No author cited) [A leader in GPS technology]
http://www.trimble.com/products/catalog/wireless/lassen.htm. 
 

1 "Navigational System for the Visually Impaired" - (1993) Carleton University
2 In 1994, VisuAide changed its name from Visuaide 2000, and became a for-profit Company.
3 " Inertial Guidance System"[7] was conducted by Darren Dentremont
4 Zoomtext(tm) (c)1997 AI Squared
5 Window-Eyes(tm) created by GW Micro Inc.
6 This is not the Object-Oriented meaning of CLASS, but is a name used to denote a group of specific messages.  
7 This pedometer is Software driven and is unrelated to the pedometer that will be added with the backup guidance system in Chapter 6.
8 Provided that the error in the system is not too great.  (covered in Chapter 5)
9 PDOP (Position Dilution of Precision) will be explained in the following Chapter.
10 WGS84 is a mathematical model of the world (World Geodetic System 1984.)[3]
11 NAD27: This value refers to an adjustment completed in 1932 of first order triangulation done in North America prior to 1927.[3]
12 One standard gravitational unit (9.814 m/s2)
13 Starting at the corner of Bank St. and Flora St. travelling southeast along Bank St., passing under the Queensway and proceeding to the corner of Bank St. and Strathcona St.
56



i