The engineer and the librarian

27.11.2020 23:01

An engineer walks into a library and steps to the reference desk. "Good morning, sir. How may I help you today?" asks the friendly librarian. "I'm an engineer. I'm looking for some references on the types of bridge constructions. Could you find something for me please?" he says. "Of course sir, I know exactly what you are looking for. It will be just a moment."

True to his word, the librarian quickly returns with a stack of books. "Will you be taking these to the study room or checking them out sir?" The engineer picks the top book from the stack in surprise and shows it to the librarian. "This is a children's picture book. Don't you think I'm a bit too old for this?" The librarian isn't thrown off by the question. "It has large letters and is very easy to read. Even many middle-aged readers find large print books more pleasant to read" he answers. "That's very considerate of you, but thankfully my vision is fine so far." says the engineer. "I'm not sure you understand what I'm looking for. How does this even relate to bridges?" The librarian takes the book and opens it. There's a drawing of a family of ducks crossing a bridge over a stream. "See, it's right here on the first page? The topic you were looking for. Is there anything else you need?"

The engineer is confused for a moment, but decides to drop the matter. He puts the picture book aside and takes the next one from the stack. It's a pocket dictionary. "I'm not sure how this one will help me either." asks the engineer. The helpful librarian has an answer at hand "Compared to the other books I found this one easily fits in your pocket. You can carry it around and read it on the go. I find many people like to read on the bus for instance." He opens the dictionary and shows it to the engineer. "You will find the definition of bridge under "B" right here."

"Ah, I think I see where the problem is. I'm more interested in books that have more content specifically about bridges. Format isn't that important." says the engineer. "I understand, sir. I'm sure the next book I found for you is the right one." answers the librarian and hands him another book from his stack. The glossy hardback cover promises a suspenseful crime novel. "This looks like fiction". "Indeed it is sir. This is one of our most popular books and from a best selling author. I'm sure you'll enjoy reading it." the ever friendly librarian replies. "Well, yes. But I want to learn about bridges you see, not read murder mysteries." says the engineer. The librarian looks at him in confusion "I'm not seeing the problem here sir. Most of the story revolves around a murder on the Brooklyn bridge. That is the topic you asked me for, isn't it? Most people that check out this book are happy with it".

The engineer rubs his forehead in frustration. "Maybe you're right. I wasn't clear enough that I was looking for non-fiction" he says to the librarian. "Is that a newspaper you are holding now?" "Indeed it is sir. It's from our selection of periodicals. Compared to these other texts that were all published at least several months ago this one is very fresh, just printed and delivered to us this morning. There's a news article on a local bridge renovation project on the third page I'm sure you'll find informative. It's always good to keep up-to-date on the topic of interest, don't you think?"

"Not really what I was looking for." says the engineer. "It's so unfortunate that you removed the dedicated engineering section you had here" he adds and points to the now empty desk down the hall way. The librarian looks at him and explains. "Not at all sir. We find that most people who visit our library find it less confusing if all kinds of literature are available from one desk." The engineer thinks about it for a second. "Did you bring any books from the engineering section in that stack?". The librarian smiles back. "Sorry sir, we are a modern library and no longer shelve books based on classification." He hands him another book. "However I believe this one is indeed on an engineering topic". The engineer sighs after taking one look and hands it back "This is a book on ship building. I'm interested in bridges." The librarian remains undeterred "Ah yes, but I'm sure you'll find this book useful if you take a second look. If you want to cross a body of water, a ship will do it as well as a bridge."

They go through the rest of the stack of books without any success. The engineer stresses that he is only interested in bridges and asks the librarian to fetch him another stack of books. And another. Ever more random books get picked up by the librarian and they get no closer to the topic the engineer was interested in. At last, the engineer gives up. He thanks the librarian for his help, but silently vows not go visit this library again. He tries his luck in the other library in town. The second librarian is a bit less friendly and less forthcoming with his explanations of why he thinks the books he found were something the engineer would like. He also turns out to be no more capable of finding a useful book on the topic than his colleague. Running out of options, the engineer returns home, disappointed that he has not found any literature to help him work on his problem.

Later that week he borrows a book from a friend of a friend. The book has a worn out cover and the paper is yellow at the edges. It has been published 50 years ago. The print is small and sometimes uneven. Back-and-white figures look like they have been drawn by hand. The text is dry and sometimes hard to understand. But on page 218 it has a chapter that helps him solve the problem he has been working on.

Posted by | Categories: Ideas | Comments »

Open Science and Open Source

08.01.2016 15:58

Last week at the 32th Chaos Communication Congress in Hamburg I went to the Open Science workshop. For two hours I participated in a lively debate among a very diverse group of people interested in this topic, from computer security researchers, high energy physicists to social scientists and psychologists. We talked and shared ideas on publishing and open access to scientific papers, modern ways of collaboration in academia, viable alternatives to impact factor and so on. It was interesting to hear how things work in other fields of research and how differences in culture affect how open and accessible their work ends up.

Image by Nicolas Wöhrl

There are some assorted notes from the workshop at the OKFN site. On the topic of publishing source code, I wanted to share some thoughts I had during my recent return to study of cyclostationary signal theory. Since it was kind of an ad-hoc idea at the time, I probably did not express my self very clearly, so here's a bit more detailed account of what I tried to say with some back story.

I was frustrated previously about how papers on that topic are very vague about exact implementation details and do not publish their source code. It later turned out that in fact, some of them do - kind of. I found a number of papers that more or less vaguely referenced autofam.m as their way of estimating the spectral correlation density, which is the key element I was interested in. While the papers themselves did not provide links to the contents of this file, Google does find a few unattributed copies floating around the Internet.

I went through this file with a fine toothpick since all theoretical deliberations I read about this method (FAM stands for FFT Accumulation Method, by the way) still left me with several questions regarding how it is actually implemented in practice. I found the missing pieces of the puzzle I was looking for, but I also found what I'm pretty certain are bugs in the code: something that looks like an off-by-one error due to Matlab's unusual 1-based indexing and a suspicious for-loop that attempts to write several different values into the same matrix element. I don't know how much these problems would affect the results the papers were publishing or, of course, even whether the authors were using the same exact code I was looking at. The question of bugs does however suggest an interesting problem with sharing source code in the scientific context.

Can code-reuse cause implementation bugs to remain unseen for longer? Imagine several, seemingly independent peer-reviewed publications showed a phenomenon that was due to an implementation bug in the code they shared. It seems that discovery might easily get generally accepted as correct. Especially in a field that is mostly focused around computer simulations.

In my case, it's obvious that implementing this method from its mathematical description is not trivial and I think it's not an unreasonable assumption that authors of these papers took an existing implementation without thoroughly checking the code they were using (a code comment sends kind of a mixed signal regarding that). If the source would not be accessible and each author would have to re-implement it from scratch, the chances of them agreeing on some anomalous result would be much lower.

What I learned at the open science workshop is that in fact the code is sometimes hidden on purpose. The high-energy physics guys (unfortunately I didn't catch their names) mentioned that often different groups of students are independently working on the same research task to avoid exactly this kind of a problem. I often find it impossible to write proper tests for my own code that is doing numerical calculations and comparing multiple independent implementations sounds like a good way to gain more trust into the correctness of results - provided you have enough PhD students. Also, they added that PhD students sometimes to talk with each other, which casts some doubts on the effectiveness of the whole thing.

At the first glance, this sounds like an argument against revealing the code. However, apart from inconsistencies with previously published results, problems in implementations are likely to remain unseen forever if there is no source to inspect. These days nobody is motivated in publishing results of an re-implemented replica of an already published experiment anyway. If source is published, there are at least chances that someone will discover bugs in it by inspection. There is also no doubt that there are many other benefits in openly sharing code. If nothing else, a few lines of code can seemingly explain a detail that is lost in a hundred pages of text, like I learned in my study of FAM.

In the end, it seems the situation where you have researchers (or PhD students) secretly swapping USB drives around the water cooler and informally sharing code is the worst of both options. I don't really expect reviewers to look for off-by-one errors in Matlab code (although some might), but publishing code together with journal articles at least gives that option. It also clearly shows which publications shared some specific algorithm implementations, which should make it easier to question and review any suspicious results they might share.

Posted by | Categories: Ideas | Comments »

On animation

23.12.2015 22:02

The end of the year is getting near and I guess it's time again for some lighter topics. A year ago I was writing about my foray into drawing cartoon characters. I can't really say I advanced on that front very much. On the contrary, it seems that without regular practice I quickly revert to my old state of barely being able to draw anything beyond circuit diagrams. It's also apparent that I lack imagination to come up with anything better than some unoriginal ponies. I was however intrigued by some amateur animations I saw, which made me wonder how hard would it be to put some of my old drawings into motion. Unsurprisingly, it turned out that it is in fact hard. Over the past summer I managed to make barely a few seconds of animation that looks presentable.

I found few good tutorials on how to do animation. Most of the time I simply studied existing cartoons. Luckily, there's no shortage of content on the web you can look at frame-by-frame. For instance, by stepping through any of the existing animations of a horse trot it's easy to see what are the key frames for motion of different limbs. Which is how I came up with these frames for the walking animation.

It's like reverse engineering the way you recognize and perceive images and motion. Some of the things I learned were quite surprising: single frames often look horrible, but work perfectly good in motion. Other times, small changes between frames that make sense individually look terribly when played back. It turns out cartoon characters really only look good from a handful of angles. You can also get away with a lot of things in animation that make little physical sense. For instance, I did some exercises in calculating visual angles, angular speeds and relative sizes for the camera rotation clip you see below. They just don't make much sense even though I think it's not that apparent in the animation itself.

Of course, I don't have access to any kind of professional software, so I took what I guess you could call a software developer's approach to art.

I drew individual character cels in GIMP using a Wacom Intuos tablet, with scans of some of my old ink-and-pencil drawings as a reference. For the rotation clip I found it quite impossible to keep proportions correct without some kind of a guide, so I programmed a spherical model in Python and PIL. I imported the resulting frames into GIMP before drawing sketches over them. And then I went back to tweak the model because it looked awful and so on enough times to give me the Tetris effect.

(Click to watch Onwards! video)

Of course, drawing and coloring with a tablet saves a ton of time, because you can just copy-paste parts that do not change between frames. Still, making all the individual cels is very time consuming, which is why everything you see here is only one quarter of the full 24 frames per second. I found GIMP's Animation Playback window and the wonderful Export Layers plug-in most useful.

For backgrounds I used Inkscape, simply because it was easier to draw a bunch of straight lines with vectors instead of free-hand. Another reason was because I have yet to discover a simple method of drawing things in GIMP that do not have black outlines. I'm scared of real video editing software ever since I've used Cinelerra a few times in Kiberpipa years ago, so when ever possible, I turned to (messy) Makefiles and Python to do compositing. In the two clips you see here, the foreground cels were exported from GIMP into individual PNG files and the background was one or two large PNGs exported from Inkscape. Python scripts then used PIL to layer frames in the right order and right offsets.

In the end I couldn't escape using a video editor though. Music, credits and cross-fades were done in Kdenlive. I used FFmpeg to encode individual frames produced by my scripts into MJPEG files that I could import into Kdenlive.

(Click to watch Spin state video)

So, after this exercise, what can I say about making cartoons? I certainly have a whole new respect for people that manage to produce even ten minutes worth of content in their free time. I've spent way too many evenings fussing over details in a second of video. On that note, this is also a scarily efficient method of procrastination on more important projects. On the other hand, seeing my character moving smoothly for the first time was a feeling comparable with the proverbial first LED blink on a new microcontroller or finally figuring out a math problem I've been working on for a month.

Posted by | Categories: Ideas | Comments »

Egg carton theory

07.11.2015 21:30

Waiting in line at a grocery store is a common opportunity for random thoughts inspired by that particular locale. The other day I was buying some eggs and I saw someone in front of me opening up the cartons and inspecting them for broken eggs before taking them from the shelf. The cartons don't have seals on them, so this appears to be a pretty benign, if somewhat selfish behavior.

Having been tangentially involved in some game theory work recently at the Institute, it made me think about this in a bit more analytic way.

Let's say that the price of one egg is c=1 and that each carton contains N=10 eggs. There is some fixed probability Pbad that each egg in a carton is broken. Let's say Pbad=1/100. The probability that an egg is not broken is Pgood = 1-Pbad.

If everyone is buying cartons without inspecting their contents, then Pbad is also the probability that an egg you've bought is broken, regardless of the size of the carton. You can calculate the adjusted cost cadj of a non-broken egg to you:

In other words, for every 100 eggs you buy, you would have to buy one extra on average to make up for the broken one you unknowingly bought.

How would that change if everyone would inspect cartons before buying them? In that case, nobody would buy a carton if at least one egg is broken. These cartons would be left on the shelves and, assuming the shop doesn't reshuffle the contents of their cartons, thrown away when their best-before date passes. Of course, the shop would then raise the price of egg cartons to make up for those cartons it could not sell.

The probability that none of the eggs in the carton are broken is PN-good (assuming that egg breakings are independent events):

P_{N-good} = P_{good}^N = (1 - P_{bad})^N

The cost of a non-broken egg for you is now the same as the price you pay in the shop, since you make sure that you buy only good ones. However, the cost of an egg for the shop, and hence what you pay, is now:

c_{adj} = c \cdot \frac{1}{P_{N-good}} = c \cdot \frac{1}{(1 - P_{bad})^N} \approx 1.11

The difference with an unadjusted cost is now approximately 10 times higher. Again, this makes sense - instead of one extra egg for every 100 you buy, the shop must now buy an extra 10 to make up for the broken one and 9 good ones they threw away. In other words, 1% of broken eggs now make the final cost of an unbroken egg more than 10% higher. It doesn't seem so benign now, does it?

By the way, this is an interesting result also from the mathematical point of view. Notice, how the difference is approximately a multiple of N, even though N in the formula is in the exponent? This is the consequence of the following first order Taylor series approximation:

This approximation holds for low values of Pbad. An intuitive explanation for it would be that it ignores the cases where multiple eggs in a single carton are broken.

Anyway, you can look at this as an example where selfish behavior makes things worse for everyone in the long term. Or you can think of it as a lesson in engineering. When a failure of any single individual component causes the whole system to fail, even low probabilities can quickly add up. In any case, calculating probabilities makes time waiting in lines pass faster.

Posted by | Categories: Ideas | Comments »

Applied Tea Science

16.08.2015 21:14

What happens when you pour boiling water into a tea cup? It steams a little. There is a possibility of thoughts on the meaning of life, universe and the ungodly hour of the morning. Some unfocused staring out the window might be involved. Eventually, the tea cools and you are free to enjoy a sip of the lukewarm beverage.

But what really happens? How does the tea in your cup cool down? We could start with convection, conduction and radiation. On the other hand, we are living in the year of the Internet enabled coaster and sensors on every step. It's not unusual to hear the sentiment today that scientific theories and good old-fashioned reasoning have nothing on big data and machine learning. So let's go with that for a moment and try to answer this question.

Enter my hastily thrown-together smart tea cup. No, it doesn't take selfies. It consists of a thermocouple sensor positioned to measure the temperature of the liquid approximately at the center of the volume. It is held in place by a RFC 2322-compliant wooden peg. A Python script takes periodic temperature read-outs using a computer-connected multimeter.

The cup, which I suspect was originally meant for Irish coffee, rests on a lid from a Nutella jar. Inside the lid is a Texas Instruments SensorTag. It measures the temperature of the bottom of the cup through an infra-red thermopile sensor and also takes readings of the temperature of its PCB. Data from the SensorTag is sent over Bluetooth to an Android phone, which forwards it over the wireless LAN to a MQTT broker. From there, a second Python script records the two temperature values to a file.

The Nutella lid rests on a kitchen scale, which will be relevant a bit later. For the sake of the argument, imagine a lab assistant taking regular notes of the weight read-outs.

I left the whole setup for an hour to settle. After the readings on all sensors stopped changing, I brought some water to a boil and poured it into the cup (no actual tea was involved). A couple of hours later, I got the following result:

This is after some light-weight preprocessing of raw data: I compensated for the offset of sensors, assuming that they were all at the same room temperature before the start of the experiment. A gap in the data nicely demonstrates the current state of the Internet of things - the SensorTag application stopped responding at some point and needed a restart.

At the first glance, this is a pretty typical progress of a relaxation process. Each sensor shows a sum of exponential decays. Three characteristic time constants are visible: the shortest one is defined by the heat transfer between the water and the cold cup, τwat-cup. The second one is of the heat transfer between the cup and SensorTag's PCB, τcup-sur. The longest one is of the heat transfer between the whole thing and the ambient environment, τamb. From the graph it's possible to roughly estimate these:

\begin{array}{rcrl} \tau_{wat-cup} &\approx& 10 &\mathrm{s}\\ \tau_{cup-sur} &\approx& 200 &\mathrm{s}\\ \tau_{amb} &\approx& 3000 &\mathrm{s}\\ \end{array}

This makes sense: water and cup are in very good thermal contact and water can quickly heat up the cup. On the other hand, air surrounding the cup is a relatively good insulator and it takes a long time for the water to cool back down to the room temperature. The simplest thermal circuit model that could fit this behavior is the following:

This model allows us to express the time constants with parameters of the model, the thermal resistances and capacitances. Since the time constants differ in orders of magnitudes, the first approximation is quite simple:

\begin{array}{rcl} \tau_{wat-cup} &\approx& R_{wat-cup} \cdot (C_{wat} \parallel C_{cup}) \\ \tau_{cup-sur} &\approx& R_{cup-sur} \cdot C_{sur} \\ \tau_{amb} &\approx& (R_{wat} \parallel R_{cup} \parallel R_{sur}) \cdot (C_{wat} + C_{cup}+C_{sur}) \\ \end{array}

While estimating the model parameters from these equations would make for a satisfying mental exercise, let's instead make use of the fact that computers are ridiculously fast these days. Numpy comes with a slew of non-linear multi-variate optimization algorithms. I chose the Powell's method to minimize the integral square error between a simulation of the model and measurements for the three time series. I won't go further into this process since this post is already getting long. Drop me an email and I can share the details.

However, before blindly running the optimization, it's worth noting that we can easily determine one of the parameters, hence eliminating one of the unknown variables and making the computer's job a bit easier. If we knew the amount of water in the cup, Cwat can be calculated from water's specific heat capacity. I told you the kitchen scale would come handy.

C_{wat} = m_{wat} \cdot c_{wat} = 370 \mathrm{g} \cdot 4.2 \frac{\mathrm{Ws}}{\mathrm{gK}} = 1550 \frac{\mathrm{Ws}}{\mathrm{K}}

Given this input and a few minutes of increased fan noise, the computer arrived at the rest of the model parameters:

\begin{array}{rcr} C_{cup} &=& 168 \frac{\mathrm{Ws}}{\mathrm{K}} \\ C_{sur} &=& 923 \frac{\mathrm{Ws}}{\mathrm{K}} \\ &&\\ R_{wat} &=& 1.57\cdot 10^{10} \frac{\mathrm{K}}{\mathrm{W}} \\ R_{cup} &=& 7.12 \frac{\mathrm{K}}{\mathrm{W}} \\ R_{cup} &=& 0.990 \frac{\mathrm{K}}{\mathrm{W}} \\ &&\\ R_{wat-cup} &=& 0.0771 \frac{\mathrm{K}}{\mathrm{W}} \\ R_{cup-sur} &=& 0.723 \frac{\mathrm{K}}{\mathrm{W}} \\ \end{array}

And here are the results of the simulation, super-imposed over the measurements from the previous graph:

The simulation matches the reality quite well. One interesting deviation is the flatness of the cup temperature curve in the first few minutes of the experiment. It is obvious that the sum-of-exponential-decays that is inherent in the model can't reproduce that. What is the physical origin of that is a bit puzzling. It is probably due to the fact that neither water nor the cup is a lumped element. Convection of water is an especially inviting excuse.

How realistic are parameter values? Knowing the mass of a dry cup (395 g), we can calculate the specific heat of the cup's material from Ccup. This gives 425 J/kgK which I would say is a bit on the low side for ceramics.

The value that sticks out most is, of course, the Rwat. It appears that the model optimization arrived at the fact that water cooled exclusively through the cup and basically no heat escaped into the ambient from the water itself. This is an interesting conclusion, but one that is also most definitely wrong.

While the surface of the cup is indeed larger than the surface of water exposed to the air, a hot body of water will cool itself through evaporation. This is an incredibly efficient process. Comparing the mass of water in the cup before and after the experiment showed that 23 g of water went missing. From water's heat of vaporization we can calculate how much heat got carried away by water vapor:

\Delta Q = \Delta m_{wat} \cdot q_t = 23 \mathrm{g} \cdot 2200 \frac{\mathrm{J}}{\mathrm{g}} = 51 \mathrm{kJ}

This is in fact around 45% of the total heat exchanged during the experiment. Since evaporation rate depends on the temperature and our model is time-invariant, this likely affected the other calculated parameters as well.

One final interesting exercise that this model allows is to calculate the magnitude of heat fluxes in the system. Particularly between water and cup and towards the ambient environment:

Compared to, say, your ordinary iPhone USB charger that maxes out at around 10 watts, these values may look large. During the experiment the cup exchanged enough heat for around 5 typical smart phone battery charges. However, the laws of thermodynamics are a harsh mistress. Due to low temperature differences it would be impossible to convert this heat into electrical work with any kind of practical efficiency.

What advances has this exercise brought to the existing body of knowledge about tea cups? One interesting discovery is that pouring hot water into a cold cup contributes to an immediate temperature drop of around 10 K, which makes it necessary to adjust the volumetric mixture ratio for green tea. This phenomenon was overlooked by the little known Indonesian tea research unit, which just highlights the need for independent verification of experimental results. Another result is the aforementioned fact that the temperature of a cup's bottom is not well correlated with the temperature of water during the first few minutes. This has practical implications, since it makes it hard to accurately reason about temperature of the cup's contents solely from a sensor in the (Internet enabled or otherwise) coaster.

Posted by | Categories: Ideas | Comments »

On hunting non-deterministic bugs

26.10.2014 14:13

Bugs that don't seem to consistently manifest themselves are one of the most time consuming problems to solve in software development. In multi-tasking operating systems they are typically caused by race conditions between threads or details in memory management. They are perhaps even more common in embedded software. Programs on microcontrollers are typically interfacing with external processes that run asynchronously by their very nature. If you mix software and hardware development, unexpected software conditions may even be triggered by truly random events on improperly designed hardware.

When dealing with such bugs, first thing you need to realize is that you are in fact looking for a bug that only appears sometimes. I have seen many commits and comments by developers that have seen a bug manifest itself, wrote a quick fix and thought they have fixed a bug, since it didn't happen the second way around. These are typically changes that, after closer scrutiny, do not actually have any effect on the process they are supposedly fixing. Often this is connected with incomplete knowledge of the workings of the program or development tools. In other cases, the fact that such a change apparently fixed an application bug is blamed on bugs in compilers or other parts of the toolchain.

You can only approach non-deterministic processes with statistics. And first requirement of doing any meaningful statistics is a significant sample size. The corollary of this is that automated tests are a must when you suspect a non-deterministic bug. Checking if running a test 100 times resulted in any failures should require no more than checking a single line of terminal output. If your debugging strategy includes manually checking if a particular printf line got hit out of hundreds lines of other debugging output, you won't be able to consistently tell whether the bug happened or not after half a day of debugging, much less run a hundred repetitions and have any kind of confidence in the result.

Say you've seen a bug manifest itself in 1 run of a test out of 10. You then look at the code, find a possible problem and implement a fix. How many repetitions of the test must you run to be reasonably sure that you have actually fixed the bug and you weren't just lucky the second run around?

In the first approximation, we can assume the probability Pfail of the bug manifesting itself is:

P_{fail} = \frac{1}{n} = \frac{1}{10}

The question whether your tests passed due to sheer luck then translates to the probability of seeing zero occurrences of an event with probability Pfail after m repetitions. The number of occurrences has a binomial distribution. Given the desired probability Ptest of our the test giving the correct result, the required number of repetitions m is:

m = \frac{\log{(1 - P_{test})}}{\log{(1 - P_{fail})}} = \frac{\log{(1-P_{test})}}{\log{(1 - \frac{1}{n})}}

It turns out the ratio between m and n is more or less constant for practical values of n (e.g. >10):

\frac{m}{n} \approx -\log{(1 - P_{test})}

For instance, if you want to be 99% sure that your fix actually worked and that the test did not pass purely by chance, you need to run around 4.6 times more repetitions than those you used initially when discovering the bug.

This is not the whole story though. If you've seen a bug once in 10 runs, Pfail=0.1 is only the most likely estimate for the probability of its occurrence. It might be actually higher or lower and you've only seen one failure by chance:

If you want to also account for the uncertainty in Pfail, the derivation of m gets a bit complex. It involves using the beta distribution for the likelihood of the Pfail estimate, deriving Ptest from the law of total probability and then solving for m. The end result, however, is similarly straightforward and can be summarized in a simple table:

Ptest [%]m/n
90.02.5
99.010
99.930

Even this still assumes the bug basically behaves as a weighted coin, whose flips are independent of each other and whose probability doesn't change with time. This might or might not be a good model. It probably works well for problems in embedded systems where a bug is caused by small physical variations in signal timings. Problems with memory management or heisenbugs on the other hand can behave in a completely different way.

Assuming the analysis above works, a good rule of thumb therefore seems to be that if you discovered a bug using n repetitions of the test, checking whether it has been fixed or not should be done using at least 10·n repetitions. Of course, you can never be absolutely certain. Using factor of 10 only means that you will on average mark a bug fixed, when in fact it is not, once out of hundred debugging sessions. It's usually worth understanding why the change fixed the bug in addition to seeing the test suite pass.

Posted by | Categories: Ideas | Comments »

On ICT Seminars at IPS

05.06.2014 1:04

Today was the last day of seminars on Information and Communication Technologies for this year at the Jožef Stefan International Postgraduate School. I believe I managed to attend 77.7% of the 18 talks given by other PhD students and gave one short presentation on spectrum sensing. That should bring me above the mandatory attendance with a sufficient margin of error.

With a few exceptions, most of these talks were wrist-cuttingly boring. Considering that the final conclusion was that this year's presentations were better than usual I dread to think what previous years had to endure.

It was suggested to me that I might not understand all the finer nuances of the pedagogic process. However I still believe that if students are giving these talks to learn how to a present their research topic, more realistic feedback on their performance might be helpful. So here is mine.

I think two mistakes were prevalent:

First was gross mismatch between audience and the basic knowledge required to follow presentations. ICT field of study at this school is so broad that you will have someone parsing tweets about celebrities on one side of the classroom, someone working on protein databases in the center and someone doing motor bearing fault prediction on the other side. As an electronics engineer I had the misfortune of acquainting myself with sentiment analysis before. Still it doesn't make sense to talk to me about Segmented Discourse Representation Theory if you can't introduce it in a way that someone who has not been studying it for the past 6 months can understand.

Personally, I like best the format where presentation is roughly split into three parts: the first one can be followed by anyone with an elementary education, second one by someone familiar with the field and third one by your supervisor and colleagues from your research group. I find that I can follow such presentations with interest even when topic is completely outside of my specialties.

I realize that with the suggested 15 - 30 minute length of these ICT seminars this might not be possible. But I think it's better to drop the last third than the first. Your supervisor already knows what you are doing and will skip the talk anyway. Others can read your paper.

"Because Magic" by Egophiliac

And that brings me to the other problem I noticed. I know that it is the de facto standard that academic slides are walls of text and are expected to stand alone relatively well without the accompanying speech (as much as I like LaTeX, Beamer was a terrible invention). I also know I enjoy every talk that breaks this mold. Don't recite a table of contents of your talk at the beginning. Make slides colorful - you're not paying Springer's color print fees here. Explain the topic using examples, plots, photographs. Don't fill up slides with 10 pt text that I can't even read from the back row. Use slide notes if the slide deck must be usable as a stand-alone publication (by the way, it doesn't in these seminars - the school doesn't even publish slides on the web).

Presentations in an academic setting certainly must be on a much higher level than your usual marketing pitch with stock photos, cute kittens and a stevejobsian act, but that doesn't mean they must make me sorry I didn't rather spend the afternoon debugging some PHP code.

In conclusion, I think everyone would be better off if these seminars would be given a bit more exposure. Obviously there is a lot of interesting research being done in the offices at our Institute. But as long as presenting it is viewed strictly as a formality and there is no push towards teaching people how to talk about their work in an understandable way, it will stay behind those closed lab doors. Presenting scientific discoveries to the public can be done by postgraduate students at informal seminars as well as by big-name professors with 3-hour extravaganzas in the large auditorium.

Maybe if that would be the case, the school wouldn't need mandatory attendance and enforce one (1) mandatory insightful question per student after the talk to give an impression of an academic debate. We might even get some of that much-sought-after cooperation between departments.

Posted by | Categories: Ideas | Comments »

Universe in a cup

01.03.2014 16:42

This topic came up in an IRC channel the other day. How does the universe compare to a cup of tea? How long after the big bang did it take the universe to cool through the temperatures, characteristic of the popular hot beverage?

Fortunately both tea and the early universe are fairly well understood these days.

In the case of tea, the cup cools down approximately exponentially. Time constant depends on the thermal resistance between the drink and the ambient, its mass and specific heat. Fortunately, a dedicated research unit provides empirical data on the subject.

As far as the universe is concerned, that part of its cooling is described by the Friedmann equation for the matter-dominated era.

As you can see from the graph above, the universe took slightly longer than your five o'clock tea to cool down.

However, unlike the cup of tea, the universe at that age wasn't terribly interesting. All the fun sub-atomic business had finished long ago and darkness was filled more or less evenly with neutral hydrogen and helium.

It will take more than 100 million years for the first stars to light up and another 10-something billion years before an odd biped gets the idea of throwing a fistful of leaves into boiling water.

Posted by | Categories: Ideas | Comments »

Origin of frequency division

17.11.2013 18:35

The most basic feature of radio communication, practically since its invention, is the division of the electromagnetic spectrum between different users on the basis of different sine wave frequencies. In fact, the word radio spectrum is basically synonymous with this division and the first question about any kind of radio is usually what frequency it operates on.

After working in the Department of Communication Systems for most of the past two years, I began to wonder what is the original reason behind frequency division. It's one of those fundamental questions that sometimes pop into your head to keep your mind off more depressing topics.

Image by Spigget CC BY-SA 3.0

The classical electromagnetic field theory gives a wave equation in empty space that does not favor the sine wave over any other kind of wave function. Similarly, a wave shared between transmitters can be decomposed into multiple independent channels based on any one out of an infinite set of orthogonal function families. Again, there is no preference to the sine and cosine functions and the Fourier decomposition that is ubiquitous in radio communication theory.

In fact, a lot of recent technologies, for example third-generation GSM, sub-divide their channels using orthogonal functions other than a sine wave. However, this is done only after first filtering the radio signal based on sine wave frequencies.

Electromagnetic field in a practical, Earth-based environment however does favor a division of signals based on sine waves. One classical reason is that objects that appear in the path of radio waves only come in a certain range of sizes. Diffraction and other such phenomena are mostly based on the relationship between wavelength and obstacle size. This means that sine waves with certain frequencies will have more favorable propagation properties than others. Hence it makes sense for instance to use a frequency band that will have better propagation for longer-range applications.

Another reason why it is natural to treat electromagnetic waves as a sum of sine functions is because of quantum mechanics and the fact that the frequency determines the photon energy. Size of energy quanta determines how the field can interact with matter in its path and this again affects atmospheric path loss in different frequency bands.

While physics of radio propagation gives valid reasons why limit a transmission to a particular part of the electromagnetic spectrum, it doesn't explain why use relatively narrow band transmissions. Radio spectrum generally spans from 3 kHz to 300 GHz while most communication technologies will currently top out in the range of 100 MHz per channel.

The historic reason why frequency division was originally used is that the natural response of most electromagnetic and mechanical systems is a harmonic oscillation. Such oscillators can be conveniently used as signal filters to extract a channel in a shared medium.

Modern systems that use other kinds of orthogonal functions for multiplexing use digital processing for signal filtering. Only in recent history has digital processing been able to process signals with significant bandwidth. That left analog filters and the frequency division as the only option for multiplexing in the early days of radio. We are still long way off before 300 GHz of radio spectrum could be processed digitally.

Another problem with purely digital processing is that passive analog filters can have a much higher dynamic range compared to A/D converters or even active analog filters. The range between noise floor and coils melting or quartz crystals shattering is significantly better than the linear range of transistors. The ability to extract a weak signal in the presence of another transmission with a much higher power is crucial in radio technology where it's not unusual to see power differences well over 10 orders of magnitude. That is why even state-of-the-art software defined radios have front-end signal conditioning implemented in analog technology.

The only current technology I know that largely does away with frequency multiplex is Ultra-wideband. It is of course still frequency band limited. Partly because of propagation physics mentioned above and partly artificially, to minimize interference with other technologies that share the same frequency band. However with effective bandwidths in the range of giga-hertz it depends on frequency division much less than conventional technologies. Unfortunately I don't know the details of UWB implementation, so I don't know how it manages to overcome the dynamic range problem and other technological limitations.

Posted by | Categories: Ideas | Comments »

On the phenomenon of paddling in place

24.08.2013 22:30

I recently came across the On the Phenomenon of Bullshit Jobs article. In it the author observes that technology has made it possible to produce goods with minimal manual labor, however work hours in general have not fallen accordingly. He attributes this to invention of pointless managerial jobs that seemingly don't contribute anything of value. I don't really subscribe to the notion that this was a conscious design by some entity to keep everyone nice and busy and submissive but the article does show western society in an interesting light (and the ensuing Hacker News discussion offers some better theories of how this situation came to be).

While this topic is fertile ground for pointing fingers at various middle managers and telephone sanitizers, I think a lot of such useless work is also done right here in the engineering community that is doing the said finger pointing.

Take for instance how a lot popular technologies in the mature part of the life cycle evolve. Once some product has reached a stable point where it solves a users' problem well enough and no one in the industry has any technological advantage, things often start going downhill. Manufacturers start adding useless superficial features, like adding "revolutionary" user interfaces, all in an futile attempt to be better than the competition. Think microwaves with elaborate functions no one every uses, "feature phones" from recent history with tons of useless fluff when everyone wanted to just use them to hear the voice on the other side, and so on.

The situation in the commercial software world is often similar, except the competing product is commonly its own older version. And with the forced upgrades, planned obsolescence and user's data held in ransom through incompatible formats the software world has even more leverage to force such useless changes on those users that find the older version fits their needs perfectly fine. As the most extreme example, see almost all changes in Microsoft Office beyond circa 1995.

In the commercial world it's easy to blame the ignorant management, greedy shareholders and anomalous market pressures for this situation. But it's baffling why similar things happen with free software projects that are mainly based on voluntary work. With recent Debian upgrade this has become most apparent. Projects that have reached the point where they more or less implemented all features one would want from them started implemented trivial changes that make no sense. I'll leave GNOME for some other flamewar, but take GIMP for example: the new version changes the semantics of windows versus application, replaces traditional sliders with something I have never seen before and shuffles around keyboard shortcuts. As far as my use of this software is concerned, there is no functional improvement and any benefits are completely offset by yanking my muscle memory from under me.

There seems to be some kind of a stigma attached to applications that stop having any visible changes. But I believe that for a mature application that does its job this is a good sign. Granted though that it's not easy to discern such a properly maintained project that only accepts an occasional bugfix from an abandoned one. Unix and GNU authors of old got this right though. You don't see sed renaming s command to r on a whim, but you do still see after all these years an odd bug fix release.

So to connect this back to the initial thought. It seems that there's a notion that even once you've arrived at something that genuinely works, you have to keep paddling in place, even though just maintaining the existing state with minimal effort would have better results for everyone involved. Someone with a social science background can now try to explain whether free software projects follow this because people bring in this habit from their day jobs or there is some other (market) pressure involved.

Anyway, from the technical standpoint I would just like to conclude by saying that please, acknowledge at some point that your project has reached everything that its users want to do with it and stick to bug fixes. Understand that the user interface is an interface. You don't randomly change mature APIs without a very good reason, do you? Rather than constantly trying to marginally improve it and making everyone miserable in the process, you can then use your remaining resources on starting something excitingly new from scratch.

Posted by | Categories: Ideas | Comments »

Unreasonable effectiveness of JPEG

28.05.2013 20:41

A colleague at the Institute is working on compressive sensing and its applications in the sensing of the radio frequency spectrum. Since what ever he comes up with is ultimately meant to be implemented on VESNA and the radio hardware I'm working on, I did a bit of reading on this topic as well. And as it occasionally happens, it led me to a completely different line of thought.

The basic idea of compressive sensing is similar to lossy compression of images. You make use of the fact that images (or many other real-world signals) have a very sparse representation in some forms. For images in particular the most well known forms are discrete cosine and wavelet transforms. For instance, you can ignore all but a few percent of the largest coefficients and a photograph will be unnoticeably different from the original. That fact is exploited with great success in common image formats like JPEG.

Image by Michael Gäbler CC BY 3.0

What caught my attention though is that even after some searching around, I couldn't find any good explanation of why common images have this nice property. Every text on the topic I saw simply seemed to state that if you transform an image so-and-so, you will find out that a lot of coefficients are near zero and you can ignore them.

As Dušan says, images that make sense to humans only form a very small subset of all possible images. But it's not clear to me why this subset should be so special in this regard.

This discussion is about photographs which are ultimately two-dimensional projections of light reflected from objects around the camera. Is there some kind of a succinct physical explanation why such projections should have in the common case sparse representations in frequency domain? It must be that this somehow follows from macroscopic properties of the world around us. I don't think it has a physiological background as Wikipedia implies - mathematical definition of sparseness doesn't seem to be based on the way human eye or visual processing works.

I say common case, because that certainly doesn't hold for all photographs. I can quite simply take a photograph of a sheet of paper where I printed some random noise and that won't really compress that well.

It's interesting if you think about compressing video, most common tricks I know can be easily connected to the physical properties of the world around us. For instance, differential encoding works well because you have distinct objects and in most scenes only a few objects will move at a time. This means only a part of the image will change against an unmoving background. Storing just differences between frames will obviously be more efficient than working on individual frames. Same goes for example for motion compensation where camera movement in the first approximation just shifts the image in some direction without affecting shapes too much.

However, I see no such easy connection between the physical world and the sparseness in the frequency domain, which is arguably much more basic to compressing images and video than tricks above (after all, as far as I know most video formats still use some form of frequency domain encoding underneath all other processing).

Posted by | Categories: Ideas | Comments »

On the death of hardware

23.09.2012 19:11

A few days ago I came across this article with an eye-catching title Hardware is dead. Two arguments are made there: first that consumer electronics designed and manufactured in Asia is becoming so cheap while maintaining a reasonable level of quality that western hardware companies don't stand a chance against them. And second that this will lead to a situation where content producers will be able to subsidize the whole cost of a device, giving hardware away for free with the hope that profits from content will more than make for the loss.

The first argument is nothing new. I remember how strongly it was voiced by the dean of Faculty of economics in the last year's round table on the role of engineers in society. Yet somehow there is still electronics design and manufacture going on in Europe. I am quite confident that the cost of eastern products will further go up as soon as their environmental and social standards catch up with the west, but this is merely my mostly uneducated opinion.

I'm more worried about the second prospect. It would create an incredible situation where you can get a physical object for free, something that necessarily requires a certain amount of raw materials and work to construct per copy, while on the other hand you pay for bits that are essentially free to copy. You may muddle up the issue by saying how selling hardware has low profit margins while content allows for a high margin. Still that doesn't change the fact that for the foreseeable future the cost of rearranging electrons in the RAM of your device into the recording of the latest blockbuster will be insignificant compared to the cost of rearranging atoms to make the said device itself.

I will conveniently skip the question of fixed costs, e.g. cost of design for hardware and production for content. We're talking here about complex devices produced by the millions where the situation regarding the cost of design is probably not all that different from the cost of producing some content for mass consumption. Hardware can still be surprisingly expensive for niche products though.

Subsidizing a product from the sale of consumables is nothing new of course. It's been done for all sorts of things, from printers, mobile phones, coffee machines to paper towels. The problem invariably appears when someone else tries to make consumables compatible with yours, only cheaper since they didn't have to subsidize your device. To prevent this kind of competition this business model always depends on some kind of intellectual-property monopoly-enabling legislation. In the past there have been some pretty creative uses of such laws in this context, for example where DMCA was applied to physical objects in the case of famous Lexmark ink cartridges.

What happens in the case where consumers themselves can make the consumable you depend on for your profit? Content shown on that give-away tablet is exactly such a case. Everyone can write text, make a program, record audio or video. Not to mention that pesky copy command every computer has that is just as effective as content producer's. Suddenly one product's users also become its enemies. This leads to nonsensical solutions like DRM and walled gardens. In some markets this practice has already been generally recognized as a bad idea. In European Union for instance mobile operators can no longer lock phones they are selling to their network, which means that at least in this country you can no longer get free mobile phones. Many are still subsidized of course, but whoever is selling them has to account for the subscriber's freedom to switch to another network. As regulators in other fields realize that such practice is harmful, I'm sure other kinds of give-away hardware will fail in a similar way.

Actually, I hope hardware subsidizing will never even come up to such a level. It might be great in the short term for hackers (hey, you get a free toy which you can jailbreak) and ordinary users (hey, you get a free toy) alike. But in the long term it will do more harm than good. For most people it basically exploits a psychological trick where people are bad at accounting for future costs, meaning you are tricked into buying things you don't actually need. Not to mention the throw-away culture such practice would enable (supposedly we are working towards a sustainable economy) and the escalation in the war over general purpose computing as companies more eagerly start to fight jailbreaks.

Posted by | Categories: Ideas | Comments »

A sense of science fiction

03.09.2012 18:52

You've probably seen this vintage job advertisement for Jet Propulsion Laboratory at the height of the space race. It has done a few rounds on the web a day or two ago.

Image by fdecomite CC BY 2.0

While it was printed well over a decade before I was born I was still touched by it when I first saw it in the web browser. I have always been a fan of science fiction of all kinds and this form of art certainly played a big role in shaping my decision to pursue this meandering career in engineering and science.

Of course, I can't be sure about what the authors of the poster originally had in mind with the sense of wonder. They might have been simply thinking about curiosity and the pleasure of finding things out. Science fiction can certainly spur both, even though the answers it provides to what-ifs must usually be taken with a grain of salt. That's why the word fiction is there after all.

What started this train of thought was rather the possibility that they thought about another feeling. The one you get when you realize you're doing or witnessing something that you have already done or seen a number of times, except now it's for real and the other times were while day dreaming or exercising imagination, fueled by works of fiction.

In any case, I'm sure readers of the advertisement that actually got involved in the space program weren't disappointed in that respect, regardless of how they understood the phrase.

Thinking back, this kind of déjà-vu feeling is actually quite rare. As mundane as it might sound, my only experience of it I can currently recall happened sometime after I got a Kindle, the electronic book reader. Reading a book one evening in my bed, it dawned on me that here I have a device which has been present in the background of so many science fiction stories. I don't think I've charged its battery even once at that point, which added to the feeling of novelty. It was just there, day after day, a few shelves worth of books, casually in my hand. A device I would have placed firmly beside a light saber or a food replicator a decade and a half ago.

I guess the rarity of the feeling can be attributed to the fact that science fiction rarely manages to accurately predict future technological advances. Everyday computing, ubiquitous communications and Internet we have today were completely missed by the stories I used to read as a child. While the capabilities of devices we carry in our pockets are certainly impressive by the standards of several decades ago, they are also completely different from computers that appeared in stories.

Posted by | Categories: Ideas | Comments »

Decibels per hertz

05.04.2012 20:10

I promise this isn't turning to a series of math rants. But since I have been lately studying spectrum analyzers and similar machinery let me tell you about a small annoyance that has been bothering me in texts and datasheets covering this topic.

Often when discussing noise that has constant power spectral density over a range of frequencies the level of this noise is given in the logarithmic scale in units of decibels per hertz (for instance thermal noise is often said to be -174 dBm/Hz). This is wrong, as it implies that you need to multiply this value by bandwidth (in hertz) to get the power in dBm when in reality you need to add a logarithm of the bandwidth. Of course, everyone dealing with these equations just knows that. Logarithms turn multiplication into addition right? But then you end up with equations where the two sides of the equal sign have different units and that is just plain sloppy writing.

Here's how you properly convert a formula for Johnson-Nyquist noise into logarithmic units:

P = kT\Delta f

Apply definition of dBm:

P_{dBm} = 10\log{\frac{kT\Delta f}{1\mathrm{mW}}}

See how the value inside the logarithm has no dimension? The value in the numerator is in units of power and that cancels with the milliwatt in the denominator. If you are doing things correctly there should never be any physical unit inside a logarithm or exponential function.

To split off the bandwidth term, multiply and divide by one hertz.

P_{dBm} = 10\log{\frac{kT\Delta f\cdot 1\mathrm{Hz}}{1\mathrm{mW}\cdot 1\mathrm{Hz}}}
P_{dBm} = 10\log{\frac{kT\cdot1\mathrm{Hz}}{1\mathrm{mW}}\cdot\frac{\Delta f}{1\mathrm{Hz}}}
P_{dBm} = 10\log{\frac{kT\cdot1\mathrm{Hz}}{1\mathrm{mW}}}+10\log{\cdot\frac{\Delta f}{1\mathrm{Hz}}}

Note that you still have dimensionless values inside logarithms. There is no need to invent magic multiplication factors "because of milliwatts" or fix the units of the variables in the equation. The division by 1 Hz in the bandwidth part also nicely solves the confusion that happens when you have bandwidth defined in units other than hertz.

So how do you concisely write this value? There is no short notation that I'm aware of that conveys the proper meaning. I would simply write out that noise level is -174 dBm at 1 Hz bandwidth and leave it at that.

Now let the flames come that this is school nonsense and that real engineers with real dead-lines don't do any of this fancy dimensional analysis stuff and that back-of-the-envelope calculations just work since you just know that this here number is in watts and that there is in kilohertz.

Posted by | Categories: Ideas | Comments »

Pre-school mathematics

29.03.2012 20:02

Recently the following question has been circling the Internet and also ended up in my inbox a few times. It's yet another one of those silly exercises that ask you to continue a sequence based on a number of examples. They are a pet peeve of mine and I'll explain why I hate them here once and for all instead of replying to everyone that sent a copy my way.

The logic of this specimen is particularly broken, even putting aside the questionable statement about pre-school children being able to solve it in mere minutes. It's obvious that whoever wrote that is not familiar with the meaning of the equals sign, as 8809 isn't equal to 6. So strictly reading, this exercise gives you 21 false statements. From that it can be simply inferred that the author is looking for another false statement, so ??? can be replaced with any number not equal to 2581.

With that out of the way, let's look at what was probably meant with this notation. You are given N=21 pairs of values (xi, yi) such that:

f(x_i) = y_i \qquad i\in[0 \dots N-1]

And asked to find yN for a given xN:

f(x_N) = y_N

From a purely mathematical standpoint, this problem has an infinite number of solutions. To demonstrate, assume that f is a function that satisfies the condition set above. In that case:

f(x) + g(x)

where

g(x_i) = 0 \qquad i \in [0 \dots N-1]

also satisfies this condition. Note that g is a function that can have an arbitrary value at xN and hence this new solution will give a different value of yN.

Just to make this a little bit more practical, here's an example of a polynomial that goes through N points:

f(x) = \sum_{i=0}^{N-1} (x - a_i) \prod_{j=0; j \neq i}^{N-1} (x - x_j)
a_i = x_i - \frac{y_i}{\prod_{j=0;j \neq i}^{N-1}(x_i - x_j)}

And here is how its graph looks like if you plug in the given 21 values:

At x=2581 it gives the value of around 5.8·1073.

Note that using the formula above and N=22, you can get a polynomial that goes through the required 21 points plus the 22nd that you can choose to your liking.

This is just one example. You could construct functions that meet the requirements from trigonometric or exponential functions in a similar way.

Sure, so this is probably not the solution the author of this question was looking for. You could say that I'm overcomplicating things and that the rule that pre-school children would come up with, based on the shape of the digits the author arbitrary chose to represent these numbers in, is nicer. But there is no such thing as niceness in mathematics (see interesting number paradox).

This is the big difference between mathematics and physics. Our universe has physical laws that for some reason can often be represented in certain mathematical forms. If a liter of water has a mass of one kilogram and two liters a mass of two kilograms it's quite likely that three liters will have a mass of three kilograms and so on. But this is purely based on our experience and beliefs about our environment and not on any purely mathematical basis. Such a prediction, just like the one above and many like it, when stripped of any physical context, does not make any sense.

Posted by | Categories: Ideas | Comments »