Orbitality

Computers today have ridiculous computational power. Not only do modern processors have high clock speeds, they often have multiple cores (multiprocessor architecture). Every one of the cores on a processor is also optimized to perform multiple operations at once (vector instructions) and to intelligently order execution order (instruction level parallelism). The net effect of these features makes processors too fast.

There is a problem getting information to the processor quick enough. Most processors can chug along enormous amounts of computation, but they can only compute if they have the data in front of them. Processor manufacturers try to always keep the processor busy by providing blazingly fast memory directly on the processor: this is not system memory (RAM). However, when the data you’re working with does not fit in the one or two megabytes of processor cache — the processor has to sit and bite its thumbs while waiting for data to come in from the sloth like system memory. This causes slowdowns in some DSP (Digital Signal Processing) algorithms when relatively large amounts of data are moved around. I spent three weeks at Drexel University researching the effects of certain design choices (programming language, compiler optimizations, iterative versus recursive control, loop unrolling) on the performance of the Walsh Hadamard Transform (WHT).

All that the fancy name of the WHT means is that you’re multiplying a vector (a single column matrix) by another matrix to get a resultant vector. Simple multiplication: (Walsh Matrix) * (Data) = Output. This is the bottom line. If you desire more detail, take a look at the poster.

The most illustrative example of slowdown caused by moving data is between iterative and recursive algorithms. In a perfect, theoretical world both iterative (going straight down a list) and recursive (splitting the list into smaller parts, then doing it) methods would work exactly alike. They’re both performing the same amount of work, just in a different order. Both algorithms perform in O (n log n) time: this means it will take n log n operations (and time) for n operations. The graph below was normalized to an n log n scale. This means that both algorithms should be straight, horizontal lines and should be as high as the theoretical maximum number of operations that the processor can perform: in our case it was 8 billion operations per second (8 GFLOPS). Reality is a bit different.

The higher the points on the graph, the quicker the processor is working. Ideally you would want the processor to be crunching data as fast as it theoretically can (eight billion operations per second) but the memory access bottlenecks processor speed. The upward slope for small amounts of data suggests that the processor does not get “warmed up” quickly enough. It wastes time doing housekeeping chores in anticipation that there will be lots of processing to do, which significantly slows down speed.

The most important trend in the graph is the huge decrease in performance at a transform size of 2^19. What’s curious is that 2^19 corresponds to a memory usage of one megabyte, which fits in the processor L2 cache (2 megabytes in our case). What’s even more interesting is that 2^20 corresponds to a size of 2 megabytes, which no longer fits in the processor’s 2 megabyte cache memory. Suspense rises even more as you realize that one of the algorithms (both of them should’ve been IDENTICAL!) suffers a lot more from running out of cache memory, but is faster initially. This suggests that the iterative (blue) algorithm is efficient at utilizing the cache: it stores the entire matrix in on-processor memory, and does not have to wait for system RAM. The recursive method, on the other hand, works only on small chunks of the data and does not benefit from the processor cache as much — but is not much affected by its absence, either.

So how do you combine the best of both worlds — the quickness of the iterative algorithm for small transforms, and the resilience to cache misses (when you run out of processor cache and need to use system RAM) of the recursive algorithm? This is something that the SPIRAL project that is based in Carnegie Mellon University is researching. They’ve already developed a method that combines the properties of both the iterative and recursive algorithms that does not suffer from cache limits.

If you’re interested in finding out more, take a look at my poster.

High school students often go to summer camps — they spend several weeks in the wilderness or in some foreign country enjoying themselves. More determined (read: masochistic) kids go to nerd camps; instead of tanning on the beach, they’ll tan under the fluorescent lights of college classrooms. Both former and latter programs cost a pretty penny (about a thousand dollars a week), though, and the determined and thrifty student hunts for an elusive kind of summer camp: one that’s free.

There are a handful of camps that offer free admission, gathering money from a sponsoring university or from corporate and private donors. One of the most prestigous of such camps is RSI (Research Science Institute) that is hosted at (not by) MIT. Approximetaly 2000 rising juniors apply every year, and only 75 are accepted. You are twice as more likely to get into Princeton, Harvard, or MIT than RSI. The students that are accepted spend six weeks working with university faculty on research projects, completely free of charge. I was rejected from RSI.

Another much less known (and consequently less prestigious) program is hosted at Drexel University called Drexel Summer Mentorship. Drexel is a “more selective” private school in Philadelphia that has a large engineering department. Carnegie Mellon, RPI, and MIT are much more popular engineering schools with a large and talented applicant pool. Ask any aspiring engineer about Drexel and they will either scoff or raise an eyebrow; this is something that the school desperately wants to change. One of the PR tricks the university runs is called Drexel Summer Mentorship — it’s a summer camp similar to RSI in that students are assigned faculty mentors and are given research to do. Similarly, the cost of the program is almost entirely free (about 150$ dollars for three weeks). The selectivity of the program is a bit higher than payed programs (approximately 60 people applied, 30 were admitted) and the application asks for SAT scores and four 500 word essays. This program did offer me free food and research to do.

The motivation of the program is to attract students to Drexel’s engineering programs. And they do so very well — many college snobs would be surprised with Drexel’s campus and programs. One of the most powerful marketing tools of universities is to get students on campus; everyone from guidance counselors to admissions officers knows that students who visit campus are much more likely to attend that university. Drexel has done a phenomenal job at capitalizing on this: it costs approximately 100,000$ to house and feed 30 students for three weeks. However, many of the students that shared the opinion that they would either not apply at all or would apply and not attend change their opinion of the school. For the price of a fancy car, the Dean of Engineering has attracted the attention of students that have either did not even know of or were not even considering Drexel University.

When I applied to the program, I was excited about the prospect of free food. Was it good? Yeah. Was there a lot of it? Yeah.

But is anything really free?

There are commercial products that can already track three dimensional position — they’re called Inertial Measurement Units (IMU). It would be an easy matter to drop one of these into a rocket to track its flight. Unfortunately, the price of these products is prohibitive for a hobbyist: a unit that is half as functional as ours (upper limit of 10g acceleration, not enough for a rocket) costs upwards of 500 dollars. We think it is possible to build an IMU with off-the-shelf components for a reasonable price. The deciding factor will be the accuracy and validity of the results obtained. A major portion of building this device is the sourcing of components.

Sourcing Accelerometers: Most accelerometers are designed for use in laptops and cell phones. Because of this, they are designed to be small. Their size makes it extremely difficult to solder for the average hobbyist without a reflow oven (think toaster oven for microchips) or a really hot blow dryer. A company that has sponsored our efforts, Schmartboard, has developed a product that makes soldering easy.

A schmartboard contains solder and small gutters into which the tiny pins of these accelerometers drop into. From there it is a small matter of heating the junction with a regular soldering iron. The board contains drilled holes through which headers can be placed to plug the sensors into a through-hole board. From start to finish, attaching a chip to one of these boards should take no longer than five minutes. The downside of this convenience is size: compared to a standard breakout board (board without the pre-placed solder), the Schmartboard is much larger. Since we are working with size constraints (the device has fit into a rocket), it will be necessary to take a dremel to the boards to cut them down to size.

The accelerometers were sampled from Freescale, who sent us two 50g (upper accleration limit) single-axis accelerometers (MMA2202EG) and a two three-axis 10g accelerometers. Small rockets can reach upwards of 100g, so these sensors are by no means excessive. The 50g accelerometer is in a SOIC (surface outline IC) package, which means its a small DIP chip that has “gull wing” leads that don’t poke through the PC board. The smaller accelerometer is QFN (quad flat no lead) and has no protruding pins. It’s also very small, and it turns out that the chip has non standard lead pitch. Normally, QFN16 (16 leads) chips have a distance (pitch) of .65mm between pins. The chip we received has a pitch of 1mm, making it impossible to use the Schmartboard for that chip. It is possible to solder wires directly to a QFN chip provided the wires are thin enough (magnet wires). A good idea would be to glue the QFN chip to the adapter board but make the connections with magnet wire.

Sourcing Gyroscopes: A device measuring angular movement is called a gyroscope. If you calibrate one by holding the rocket still, you can use angular movement to figure out the rockets orientation. These devices have some limitations, for example, they have a maximum angular rate measured in degrees per second. If the gyroscope spins any faster than that (a typical high rate gyro has a limit of 500 degrees per second — more than a full turn a second), you will lose track of the rockets position.

The catch to these sensors is their price. They’re much more expensive than accelerometers, and most of them measure one axis per chip (a company called Invensense has a dual-axis gyro, though). Our rocket needs only two axis since we don’t care if the rocket is spinning around its main axis (it’s a rod). Of all the companies we’ve asked for samples of gyroscopes (Invensense, Honeywell), none have obliged due to the high price of the devices. Many companies offered gyroscopes in packages that we had no hope of soldering (BGA, LGA… are you serious?).

Without the gyroscopes, using acceleration to determine position is very inaccurate. The only hope is the rockets intense upward thrust: the rocket barely moves any direction but up. Ideally, the rocket will fly straight up and we will only need the upward linear acceleration to determine its altitude. The two horizontal axis would read zero (they’re perpendicular to the ground — gravity has no effect on them), and the vertical measurement would be valid. The further the horizontal acceleration readings stray from zero, the more inaccurate the vertical readings will be.

Imagine taking a curvy path instead of a straight one when your eyes are closed. If you take the curvy path, you will no doubt get lost. If you go straight, you will probably make your target. You will know that you’re walking in both cases, but you will only know your position if you were walking straight. If the rocket travels straight, our tracking device will be accurate. If it doesn’t go straight up, the results won’t be very valid.

Heuristics without Gyroscopes

One option we’ve considered was using the horizontal accelerometer readings to determine the tilt of the rocket. A horizontal acceleration (read: gravity) reading will be zero since it is perpendicular to the gravity of the earth. As the rocket tilts to the side, the horizontal (X, Z) readings will become positive: the earths gravity will begin affecting them. When the rocket falls over completely to the right, one of the horizontal readings will become 1 (1g — earth’s gravity). Since these readings vary with the tilt of the rocket, it would be possible to bypass the gyroscopes to determine the rockets position. But these readings are only valid when the rocket is not accelerating. This is the trick the Wii Remote (wiimote) uses to determine it’s position (along with other heuristics involving arm length and room size). But on a rocket, any declination from vertical will not only change the horizontal readings due to tilt, but also due to the fact that the rocket is moving sideways!

Complete inertial guidance needs six degrees of freedom (DOF). On a rocket, you can get by with five degrees of freedom: you don’t care if the rocket is spinning like a top. Without gyroscopes, we’ll only be able to track the rocket in one dimension: up. That’s one degree of freedom. We’ll be able to determine the rockets speed at any point in time, velocity, maximum height, deployment of parachute, burnout, thrust of the motor, and other factors. But all these variable will be determined with questionable accuracy: the rocket will never be moving only up.

Sourcing Pressure Sensors: a secondary method of determining apogee is by measuring the pressure at the apex of the rockets flight. Since the flight computer will be stored in the nose cone of the rocket, the expulsion of the parachute will expose the pressure sensor to the atmosphere. There is a relationship between pressure and altitude:

There are three main types of pressure sensors: absolute, gauge, and differential. Absolute pressure is a measurement of the air pressure relative to zero. An absolute sensor has two chambers — one with a vacuum and one exposed to the atmosphere. A diaphragm will bend towards the vacuum in proportion to the atmospheric pressure. At sea level, this sensor will read 101.325 kPa.

A differential sensor has two chambers exposed to the atmosphere. This type of sensor is used in pneumatic devices: one chamber measures the pressure of one gas, while the other chamber measures a second pressure. The difference in pressures between the two liquid will bend a diaphragm slightly, causing a change in the output voltage of the pressure sensor.

A gauge sensor measures pressure relative to atmosphere: one chamber is sealed with 1 atmosphere of pressure and the other is exposed to whatever you’re measuring. This is the type of sensor that you would use for tire pressure: it would ignore the 1 atmosphere (101.325 kPa,760 torr) of ambient pressure.

In all our wisdom, we have sampled a differential sensor from Freescale. We can mount the chip because it is in M-Pak packaging, which is the proprietary name for a 4-pin SOIC package. Sadly, this sensor will always read zero since it will be measuring the difference between pressures on the two sides of the chip. Imagine our surprise if this chip had made it into the payload.

In an attempt to salvage the chip, we tried to convert it to a gauge sensor. A trick that you can use to convert a differential sensor to a gauge sensor is to superglue one of the chambers shut: you have sealed that chambers with one atmosphere of pressure. The reading on the other chamber will then be relative to atmospheric pressure. We didn’t read the documentation on the chip before obtaining it, and it turns out that the full scale range of the sensor is 25mV: we’d need to use an amplifier if we wanted to detect the change in pressure. The chip also had a maximum pressure of 10 kPa, which made it completely useless.

It is therefore important to source an absolute pressure sensor when making a barometer or altimeter. Even more important is the perusal of documentation before ordering parts.

Sourcing Microprocessors and Memory: 3 kilobytes of telemetry per second of flight are recorded (that’s equivalent to typing 20 pages of Hamlet a second), and that data needs to be saved. A microcontroller that reads the data from the sensors has only paltry onboard memory, so an external chip is necessary. Microchip (one of the big microprocessor companies) manufactures EEPROM (electrically erasable memory) memory that can be accessed with I2C, SPI, and their proprietary one-wire interface. They also manufacture a range of microcontrollers, ranging from 8-bit all the way up to 32-bit. Their microcontrollers are fascinating to play with and they send samples, oftentimes no questions asked.

You can program their controllers with cheap tools that you can either make, or purchase (we use the PicKit1 which programs most of their processors and only costs 30$). The compilers for the PIC controllers are terrifying. You have a wide array of language choices when programming PICs: you can program in assembly, you can program in assembly (disguised as C), or you can program in assembly (disguised as BASIC). The language you choose is irrelevant: there’s no escaping that you will need to know bitwise operations, low-level timer interrupts, registers, and many other pedantic concepts relevant to 1970s computing. The only satisfactory compiler is CCS C compiler (which manages much of the low-level stuff), but it’s quite expensive.

We have several 1 megabit (128 kilobyte, 6 minutes of flight time) memory chips and processors. When selecting a processor, it is important to get the right amount of discrete I/O pins (two pins of RS-232, four pins for accelerometers, one pin for pressure sensor..) and enough ADC (analog-to-digital converter) channels.

Sourcing Odds and Ends: By looking around it’s possible to sample many different items. Schmartboard provided us with an RS-232 module, which will simplify sending data from the flight computer to a laptop. You’d be surprised at what you can sample if you search around: many companies are glad to send you battery holders, displays, analog and digital components… There are some internet resources with listings of companies that will send samples to students.

Tracking the flight path of a rocket is tricky business. You cannot easily measure the velocity or displacement of the rocket. Wind speed and radar are silly things to measure on a rocket smaller than a big sandwich. All that is left to measure is instantaneous acceleration. If you know how fast you are accelerating in a given direction, you can use some simple calculus (or even addition) to determine your position. This technique is called dead reckoning. There are devices that can measure acceleration called accelerometers. These chips are becoming very popular: cell phones (iPhone), laptops (Lenovo) and other devices are using accelerometers to protect hard drives and rotate screen orientation. The human body detects linear acceleration with otolithic organs — layers of viscous gel in your inner ear. When you accelerate in some direction, the gel is slightly displaced and the change is detected by tiny hairs called kinocilia.

But linear acceleration isn’t enough. Your body, for example, also measures your rotation in space. Even with your eyes closed you can tell if you are lying sideway or are upside down. When your sense of orientation fails (when you’re dizzy), you get very confused about where you’re moving. It is similarly impossible (or at least very inaccurate) to determine position from acceleration alone on a rocket. A device that can measure this is called a gyrometer.
Your semicircular canal in your inner ear is filled with liquid; it senses your orientation (yaw, roll, and pitch) with tiny hairs. A gyrometer is an electrical analog: a tiny “tuning fork” is slightly bent when the device spins, causing a change in capacitance that can be detected. Not only is it imperative to track acceleration, we have to measure the rotational position of the rocket as well.

The funny thing about all these sensors is that they’re ratiometric. They don’t output the rockets speed in miles per hour or tilt in degrees. Instead, analog sensors output a higher voltage for a higher speed and gyrometers function analogously for tilt. It is therefore necessary to calibrate these sensors to 1g (9.8 meters/second/second) for accelerometers and standstill (parallel to ground) for the gyrometers. The linearity of the output of these signals is also not perfect: it is reasonable to expect that the output voltage would scale in a 1:1 ratio as speed increases, but this is not the case. All of these factors lead to a device that is of suspect accuracy and the results of which need to be verifiable.

There are three easy methods to double-check the data from these sensors. Air pressure is very high at the surface of the planet (imagine a two kilometer column of air above you) and drops as you travel away from the earth. Unfortunately this decrease is not linear, but the US Air Force has developed a formula that can approximate height based on atmospheric pressure. Atmospheric air pressure sensors are easily obtained and can also be included in the payload. Two other ways can confirm the apogee of the rocket: by measuring the angle the rocket makes relative to the ground, and by timing the time the rocket spends in the air.

The data from these sensors needs to be saved in flight and retrieved after landing. Therefore, a microcontroller will be needed to save these results. Rockets travel quickly and it will be necessary to poll the sensors often. An arbitrary starting figure is 50Hz (50 times per second). Since the sensors output analog data (a change in voltage) as opposed to digital (a change in pulse frequency), a microcontroller with an analog digital converter (ADC) will be needed. The PIC16F684 was conveniently on hand and has an ADC with a resolution of 10 bits — each voltage reading can be converted into a number from 0 to 1024. If there are three accelerations and two rotations (the spin of the rocket is irrelevant since it is a rod) plus a pressure reading, the controller will need to save six figures fifty times per second.

The rocket will track six 10 bit values fifty times per second. That means for each second of flight 3000 bits will be saved (about 3 kilobytes). On a computer, a 3000 letter document takes up 3 kilobytes. Microcontrollers feature paltry onboard memory, so an Electrically Erasable Programmable Read Only Memory chip is required. A one megabit module was available on hand, which is enough for about six minutes of flight time. To detect a launch, the controller will wait for a +5g impulse from the accelerometers to begin writing to EEPROM (it will keep a buffer of ten seconds prior to launch). Some optimizations can be made to the data that is saved: the 10 bit ADC is not very accurate and the last two bits can be discarded. Similarly, the pressure reading is not relevant until the nose cone is released (or else you’ll be recording the somewhat pressurized rocket tube).

The data on the memory needs to be uploaded to a computer. The microcontroller will need to interface with another circuit that will upload information to the computer. A two pin header will exist on the payload controller which will upload the flight data via an I2C (two wire) protocol. The “ground control” circuit will upload the results via an RS-232 (serial) interface. A software program will read the results which will be analyzed in Excel or Matlab using a Kalman Filter, an algorithm that smooths out noisy readings.

Some small features should include LEDs that signify recording state and proper orientation (if all accelerometers are reading proper values for a rocket perpendicular to the ground).

After the collapse of the Soviet Union, capitalist governments worldwide breathed a sigh of collective relief. No more opposing ideologies, no more space races, and no more competition.

Sputnik, in its intimidating shiny exterior, encourages young scientists no longer. Fervor for science is now motivated by desire for personal success. Patriotism and pride are replaced with the less romantic drive to get more money.

It is plainly apparent that there is not much interest in doing science and engineering (which is not the same as taking a class). There are few students that go home and whip out their chemistry sets and soldering irons.

Encouraging Creativity

Science and engineering is not about reading textbooks. It’s not about solving word problems. It’s not about going to class.

It is about playing in the sandbox. It is about building stuff. Most importantly, it’s about being creative. Science and engineering is like painting or writing novels, except you use a soldering iron as a pencil and brush.

My high school created a program where seniors (12th grade) can work on independent projects. They can make a play, start a band, or intern at a company.This is a trend in many schools across the country: schools are integrating “real world” learning into their curriculum. I’m participating in said program, and we’ll find out if it succeeds in teaching relevant stuff.

Building Rockets

I’m building rockets this year. I found a book at the school library on Amateur Rocketry. On the first page there is an insert that lists who took out the book and when. When do you think was the last time someone read that book?

April, 1983.

Nobody is interested in going to Mars anymore. I guess the Martians will be satisfied after all.
Anybody can build a rocket out of a kit: but its more fun to build it from scratch. What’s even more interesting is tracking the the flight path of the rocket. If your grandfather listened to Sputnik over the radio, he would probably track the altitude of his rocket with a stopwatch or by measuring the angle it made relative to the ground. But in the age of silicon, it is so much more appropriate to build an electronic payload.

So here’s what I’m doing. I’m building an altimeter using three accelerometers and a pressure sensor for verification. The accelerometers will provide three axes of acceleration data: X, Y, Z. The pressure sensor will provide the apogee (pressure is lower at a higher altitude). All this data will be stored by a PIC microcontroller onto a small EEPROM memory chip. Upon landing, the device will be recovered and stored data will be analyzed.

This data is useful in designing a rocket that will fly higher.

When I was a kid, my mom always tried to feed me oatmeal. The brand of the concoction, to my six-year-old joy, was called Hercules. “Eat it — you’ll be strong like bear!” she said, and I obliged. Who doesn’t want to be like Hercules or a bear?

In all their might, neither Hercules nor a big Bear could develop software. That doesn’t stop us from attributing their characteristics to styles of development. Big dynamic production website? Big, polished game? Sure! Throw twenty men at it and it’s no problem. But what if there’s only one man you can throw at a software project — your very own self? Will you be a Hercules of programming?

The one-man team is versatile. Without anyone telling you what to do and how to do it, you’re completely free to do what you want and do it the way you want it. And the way you want to do things is by cheating. Steal, lie, pillage — you’re Hercules, and no one can stop you. You’ll never match the manpower of big companies, so you’ll just have to steal code to get your way.

Open source makes it VERY CONVENIENT to steal. It’s even legal, completely ethical, but most importantly — encouraged! Take open source software, like Joomla: it’s a content management system that works out of the box without any configuration. You don’t even need to write a line of code to set up a basic dynamic website.

I see many developers writing custom code when they don’t have to. It’s much easier to use an out of the box solution, then customize it, rather than writing EVERYTHING FROM SCRATCH! Before you write a single line of code in your next project: stop, drop, and roll. Break your site down into simple component parts. If you’re developing a video game in DirectX, look for libraries that manage the low level stuff (like Allegro that functions as a wrapper for OpenGL and DirectX). Then use the basic code and modify it to your needs. Development time will drop. Try looking for a “Rails” type of solution (Ruby on Rails, PHP on Trax and similar).

There is something to say about originality. In an essay on the English language, George Orwell remarked that idioms and phrases were regurgitated. There was no freshness, and language became stale and boring. In development, every line of code you don’t write is a line of originality that could have been revolutionary. It’s a scary future if all new code was simply a rehashing of old modules. It’s a fine line to walk between quick prototyping and prototypical code.

I guess it breaks down into one of those computer repair jokes.

Fast, Cheap, Quality: Pick two.

You can tell a lot about a person by looking at his trash. Empty pizza boxes and beer cans? He likes to relax after work. Box from a new HDTV? He likes to watch movies.
I live in a small suburban town. There are pizza boxes in our trash. There are even more beer cans. We like to drive to school and work, and a pedestrian draws many a curious stare.

But the trash of many households is changing on a massive scale. Newspapers are bundled. Plastic bottles are in blue recycling bags. There is a garbage revolution going on in dumpsters!

But not enough people recycle. Our town has a youth commission — a group of students that are passionate about community service. This year the project was to encourage the town to recycle.

Any modern community activism program needs a digital component. Its just so much more convenient to sign a pledge online than to drive (and hypocritically pollute). The concept of the “Going Green” website is very interesting. Residents who sign a green pledge have their houses light up green (with google maps and geocoding). There’s also a very spiff “green meter” made using OpenFlashChart.

One piece of literature that was the basis of the project was “Community Based Social Marketing” by Doug McKenzie-Mohr. It’s an almost disturbing book that details marketing (which are borderline propaganda) tactics that are useful in coercing people to recycle. One of the concepts he discusses is conformity — when a resident sees the whole map littered with green houses, he feels that he’s the only one that isn’t recycling. The green meter is a very visual indicator of how many people (that aren’t you) are recycling. Were it for anything but recycling, these tactics would even seem a bit shady. But I guess shady works, because the site worked up 40 pledges during launch week.

Ironically, the web server that’s hosting the website today dumps around a ton of carbon dioxide into the atmosphere annually. Maybe the forty people that have signed the green pledge so far can redeem my recycling vows? Maybe not.

I guess I’m taking a shorter shower today.