Cardinal Peak

More on Patents

I had intended to give the indemnification issue a rest.  But then the following caught my attention this morning:

One big difference between patents and other kinds of intellectual property, like copyrights and trademarks, is that patent-holders who want to sue someone for infringement don’t have to show that their patents or their products were actually copied by the defendant. In fact, the issue of copying is legally irrelevant when determining whether or not someone infringed a patent. (It is relevant to willfulness—more on that below.) The flip side of that rule is that a defendant company can have a really nice story about they did their own research, invention, and development—but it doesn’t matter one bit, legally speaking. Such “independent invention” stories are no defense.

“No one seems to know whether patent infringement defendants are in fact unscrupulous copyists or independent developers,” writes Lemley. So he and his partner went on a hunt looking for copycats in patent disputes. How much copying did they find? Not much at all.

(Joe Mullin’s whole post is excellent; thanks to Brad Feld for calling attention to it.)

Which underscores my earlier point: Patent lawsuits don’t usually arise because of unethical behavior on the part of the engineering team. And therefore offering indemnity protection against these kinds of cases is not a financial risk that we can or should bear.

I’m not primarily out to agitate for reform of the patent system, but I agree with calls for adding an independent innovation defense. Such a reform would help swing the effect of the patent system back toward its original intention, which was to encourage innovation.

Howdy Pierce is a managing partner of Cardinal Peak with a technical background in multimedia systems, software engineering and operating systems.

Providing Indemnification for Patent Infringement

Cardinal Peak recently had an unfortunate “first”: We chose to walk away from a promising engineering engagement because we couldn’t reach agreement with our customer about an indemnification clause.

Let me give a little background before diving into the issue. “Indemnification” technically is the legal obligation to compensate a business partner for losses that the partner might suffer during the performance of a contract.

To give an example, it’s common for professional services providers such as Cardinal Peak to indemnify our customer in the event of a lawsuit alleging that we copied a third party’s source code into the product we engineered for the customer. In this case, if the third party were to sue the customer for copyright infringement, then Cardinal Peak will be responsible for both the costs of the legal defense, plus the costs of any settlement that would arise. You can read a little more background (albeit with a testing-oriented slant) here.

Not to suggest that we take any financial risk lightly, but we are generally okay with providing this type of indemnity protection to our customers, because we control our own actions and we’re confident we won’t behave unprofessionally.

In this case, however, our customer insisted we provide indemnification in the case where we were to unwittingly infringe a third party’s patent. In my view, this is a very risky form of indemnification to offer.

I am aware of too many examples where existing patents cover relatively obvious methods of solving some particular problem. (A portion of our services business involves expert services work in support of patent litigation—so we’re all too familiar with the ugly details, although we can’t speak publically about the cases we’ve worked on.) It seems all too possible that, without any foreknowledge of an existing patent, a competent engineer might independently hit on an already-patented method for solving a problem. And if this were to be the case, the amount of money required to mount even a trivial defense would put a small firm like Cardinal Peak out of business.

There’s also a quirk of the US patent system that is worth pointing out: To my understanding, it is not even theoretically possible to guarantee a priori that you don’t infringe a patent. Even with a complete patent search and the best legal advice, under our system, the only way you can determine infringement is through a jury trial.

So really there’s no way for a firm like Cardinal Peak to be absolutely, 100% certain we don’t infringe a patent.

One way to look at this is that there is inherent financial risk in releasing any high-tech product. The form of risk that first comes to mind is when a high-tech company invests a lot of money in developing a product, just to see it flop when it comes to market.

But market failure isn’t the only form of risk in product development: Liability for unwitting patent infringement is another. (Unfortunately, it seems to be a growing risk!) Just like market risk, patent infringement liability is a risk that should be borne by the company that also stands to reap the rewards from a successful product—and that’s usually not the provider of your engineering services. After all, rarely will the service provider own the intellectual property that results from their work for hire.

I’m not suggesting that Cardinal Peak would never offer indemnification for unwittingly infringing someone’s patent. But there would have to be some upside. It is a risky move for us, and we would want to see some extra return that justifies taking that risk, whether that would be in the form of royalty participation in the product, or IP ownership of whatever is developed.

What do you think? This is an issue that my partners and I continue to discuss, so we welcome your comments.

Howdy Pierce is a managing partner of Cardinal Peak with a technical background in multimedia systems, software engineering and operating systems.

Writing Defensive Code to Automatically Find Memory Leaks

In an earlier post, I suggested making all your memory allocations go through a single routine, and deletions through another. When you centralize allocation and deallocation like this, you gain a couple of benefits.

• First of all, you make the memory allocation more explicit, which will tend to make programmers more careful.
• Second, you can write “defensive code” to automatically find bugs during the development process.

I first thought hard about the concept of “defensive code” when I read the book Writing Solid Code by Steve Maguire. This book is now slightly dated, but the general concepts in it are excellent. Defensive code refers to the concept that, especially in debug code used during development, you should have validation routines that are called automatically that will call your attention to latent bugs such as memory leaks.

Once you’ve got your memory allocation and deallocations routines centralized, there are various ways you can instrument these routines during development so your code can tell you about memory allocation problems as you’re developing it.

The easiest thing to do is to keep counts of how many chunks of memory have been allocated and deleted, and monitor it over time to see if the number of currently allocated chunks matches your expectation. This is lightweight enough to implement even in the most constrained environments.

A variation is to keep a copy of the pointer in the allocation routine in some kind of registry data structure. Then you can write a routine to print out the currently allocated items. This is especially helpful if a type of item is leaked only occasionally, as it lets you see exactly what items have leaked. (I have also implemented this in conjunction with Boost smart pointers, but be aware this keeps the reference count at 1, so you have to also write code to release this pointer when the reference is 1 in your printout routine or the items are never deallocated.)

In many embedded environments, you may have the source code to the C library, or even the entire operating system available. If something like valgrind is too resource intensive or unavailable for your platform, you can look at some of the malloc debugging packages available on the net. If none meets your needs or is unavailable on your platform, you can simply modify malloc() and free() to record operations. You will want to log the address and size of each allocation and deallocation to a file or trace facility. You will also find it useful to record the addresses on the call stack, such as with GCC’s __builtin_return_address() facility. You can write a program to examine the saved allocation data and delete all the records that have matching allocation / deallocations. The results left over are malloc() calls with no matching free() calls, and double calls to free(). You can then match up the calling addresses with a symbol table, the output of nm, or the gdb list *address command to find out where these calls were made in your program.

Ben Mesander has more than 18 years of experience leading software development teams and implementing software. His strengths include Linux, C, C++, numerical methods, control systems and digital signal processing. His experience includesembedded software, scientific software and enterprise software development environments.

PhotoDialer Update

It’s been almost six months since we put the first version of PhotoDialer in Palm’s App Catalog, and three months since we started charging $1.99 for it. In that time, we’ve submitted a handful of bug-fix and feature-enhancement releases, including the 1.3 release which just hit the App Catalog today. This latest release gives you a little more control over where your contacts’ names are overlaid on their pictures and addresses feedback from our users. We’ve also recently fixed a problem where some photos would be distorted. We hope you enjoy it!

We saw with some amusement that MyAppBox.com currently has us listed as the most likely paid app to win Palm’s top prize of $100,000. Of course we’d love that, but unfortunately I have to question their data. They have estimated that we’ve had over 10,000 paid downloads, and, sadly, the real number is substantially less. Having an app in the App Catalog is not yet a path to riches, at least not if you’re trying to make money simply by selling the app.

I also wanted to address a complaint that keeps coming up. Many people have reported difficulties downloading or updating PhotoDialer. Unfortunately, the download process is handled entirely by the WebOS system software, so it’s out of our control. This problem first surfaced when the application transitioned from the beta App Catalog to being a paid app and appears to be a result of the conversion process that Palm performed.

We have reported these problems to Palm, but we’re not able to address them ourselves. This is especially frustrating, because problems downloading or updating PhotoDialer is the leading reason for customers to rate us anything but four or five stars in the App Catalog. And getting good ratings seems to be the key to continue to get people to purchase the app, which is definitely the key that will keep us investing in it.

If you are experiencing problems upgrading PhotoDialer to a more recent release, the following procedure has been shown to work around the problem. First, delete the PhotoDialer app. (To delete, hold down the orange key, and then tap on the PhotoDialer icon, and then tap “Delete” in the confirmation dialog that appears.) Second, re-install PhotoDialer from the App Catalog. You should not be charged for this, even if you originally installed PhotoDialer during the Beta period when it was free.

Palm continues to communicate that they are working to address the problem properly on their side, so here’s hoping for a proper resolution soon.

Chad Scates has significant experience managing software development teams and developing GUI-intensive applications in cross-platform environments.

Delta Sigma Converters: Filtering, Decimation, and Simulations

In my first post on ΔΣ converters I presented an intuitive way to derive the modulator portion of the converter. Now we need to look at what comes after the modulator—namely, the digital filter and the decimator. The high-level structure of the converter looks like this:

The analog input voltage, v(t), is assumed to be scaled so that its range is in the interval [-1, 1]. The output of the modulator is a sequence of uniform width pulses with a magnitude of either ‑1 or 1. These pulses are generated at an “oversampled” rate—in other words, at a rate greater than the Nyquist rate. The oversampling is by some significant factor, for example, 64. Let the highest frequency present in the signal be B; the Nyquist rate is then 2B, and the output rate of the modulator for an oversampling factor of 64 is 128B.

We wish to reduce the sample rate to the Nyquist rate while extracting the signal v(t) from the pulses. We do this by lowpass filtering the pulse train to a bandwidth of B and then sampling the filter’s output at the rate 2B. Consider a FIR LPF filter. Because the pulse sequence only has 1s and -1s in it, the FIR filter can be implemented with additions and subtractions only. Furthermore, although the 1s and -1s are shifted into the filter at the oversampled rate, the filter’s output only needs to be computed at the Nyquist rate, which is nice from a computational perspective because we only need to compute the samples we’re going to keep!

To make this all clear, let’s trace the flow of a simple input signal through the system in both the time and frequency domain. For this example, I’ll let B be 4KHz, which corresponds to telephone quality audio. Let’s assume an oversampling factor of 64. Then pulses are output from the modulator at the rate 2 × 4000 × 64 = 512 kilobits/sec (bearing in mind that we convert the sequence of -1s and 1s into an equivalent sequence of 0s and 1s, so each pulse is captured as a single bit). As an input signal we’ll use the sum of two cosines, one at the low end of the pass band and one at the high end (730 Hz and 3.765 KHz respectively). Both cosines have the same amplitude, 0.5, so their sum is within the [-1,1] range required. The input signal looks like this:

The spectrum of this signal computed over a 4-second interval is shown below. Here the x-axis is in KHz and the y-axis is in dB relative to the highest power frequency in the signal.

As expected, the input signal has two well-defined peaks.

The sequence of pulses output from the ΔΣ modulator when this signal is input looks like this:

In intervals where the input signal is large, many 1s are output, while in intervals where the input signal is close to zero, 1s and -1s occur with a nearly equal frequency. Since we propose to recover the input signal by lowpass filtering this pulse stream, it is interesting to look at the spectrum of the pulse stream. In the range of 0 to 15 KHz it looks like this:

The original signal spectrum is clearly visible, but there is lots of noise above 4 KHz. In fact, if we plot all the way out to 256 KHz (1/2 the oversampled rate of 512 KHz) we see the following:

The 1-bit sampling has introduced a huge amount of quantization noise, and it increases with frequency. Were we to subsample the signal at an 8 KHz rate without first lowpass filtering, all of this noise would alias into the 4 KHz band we care about! To do the lowpass filtering I used a 1000-tap FIR filter in my simulation; I wanted to show the effect of a very good filter. After filtering, the spectrum looks like this:

Most of the out-of-band quantization noise has now been eliminated. After subsampling the signal by a factor of 64, we are down to the Nyquist rate. Any quantization noise remaining after the LPF has now been aliased into our frequency band of interest. The spectrum of the Nyquist sampled signal over the range 0 to 4 KHz is shown below; the two cosine signals have been converted with very little distortion.

As a final note, it’s worth showing the spectrum of the modulator’s output pulse train when the oversampling factor is only 4 instead of 64. As seen below (the graph covers the range 0 to 15 KHz), there is a lot more in-band noise (i.e. in the range 0 – 4 KHz) than occurs with 64x oversampling. Not surprisingly, higher sampling rates lead to better performance!

Here is the code I used for these simulations.

Mike Perkins, Ph.D., is a managing partner of Cardinal Peak and an expert in algorithm development for video and signal processing applications.

Tools to Help Find Memory Leaks

Previously, I wrote about my “golden rule” for reducing the prevalence of memory leaks in your code. One other easy way to prevent memory leaks is to actively seek them out during the development process, instead of waiting around for them to be reported to you as bugs.

One good way to do this is to add some time to your schedule so that you can apply the available tools for finding memory leaks and other problems. Two that I have used and found valuable are Valgrind and Coverity.

Valgrind performs many checks on your code, but in my opinion the most useful ones are related to pointer usage and memory allocation.

Valgrind analyzes your program at runtime, and requires significant resources. It may be unsuitable for some embedded applications for that reason, but if you can sufficiently beef up a development system’s memory and storage to run it, or execute your code in another more resource-rich environment, you will find it useful.

The weakness of Valgrind is that since it runs at runtime, you have to be able to exercise many code paths to ensure that you are leak free. I have found that even if the usual flow of execution for an application is leak-free, it is likely that memory leaks occur in error paths.

Coverity, on the other hand, performs static analysis on your source code, as described in this paper. So it covers all your error paths. Coverity costs money, but in my opinion it is well worth it. While it can provide false positives in some cases, the value is in the actual problems it uncovers that are difficult to find with a code review. It is worth examining every item it identifies as being a potential problem. (Incidentally, I recommend this recent article, written by the founders of Coverity, which touches on the organizational difficulties in implementing any automated bug-finding tool.)

Another way to solve the memory leak issue is to replace the standard C++ pointer mechanism with a more advanced replacement. I have used both the Boehm Garbage Collector (GC) for C/C++ and the Boost library smart pointers for this. Since so much of the C library and other libraries you might be using depend on standard pointers, this is obviously not a panacea – there will always be places in your code where you will have to use a standard pointer or go around the constraints of the GC you are using. GC based approaches may not be appropriate for resource constrained environments or those where the GC’s requirement that it collect garbage might interfere with timing.

The smart pointers in the Boost library offer reference counting. While in theory reference counting requires more cycles of overhead than a GC based approach, it does offer a predictable use of CPU. Also, the freedom to create C++ objects that are deleted when the last reference to them goes away can allow much simpler designs in some cases, especially when an object is referenced by multiple threads. But be sure to configure the smart pointers to be threadsafe in this case.

Ben Mesander has more than 18 years of experience leading software development teams and implementing software. His strengths include Linux, C, C++, numerical methods, control systems and digital signal processing. His experience includes embedded software, scientific software and enterprise software development environments.

Delta Sigma Converters: Modulation

The web is filled with introductions to Delta Sigma modulation (also sometimes referred to as Sigma Delta modulation) in the context of Delta Sigma converters. Unfortunately, the ones I’ve looked at fail to intuitively motivate how the modulator works. Therefore, my goal in this post is to show how the structure of a first-order ΔΣ modulator can be simply understood. In particular, I show how its structure can be derived from a trivial 10-line C program that performs the ΔΣ modulator function.

The basic problem solved by a ΔΣ modulator is this: given a fixed input value ν that lies in the range [-1, 1], the modulator outputs a pulse train satisfying the following criteria:

• Each pulse has the same fixed width τ
• Each pulse has an amplitude of -1 or 1 only
• The time average value of the pulse train emitted converges to ν

To derive from first principles a system diagram to perform this task, I find it useful to proceed as follows: First, write down a few equations to make precise what we’re after; next, write a computer program that emits a pulse train satisfying the equations; and finally, draw a block diagram that realizes the computer program.

So let’s get started. First, a waveform f(t) has an average value on the interval [0,T] of

Let l(i) be the magnitude of the pulse of duration t emitted in the interval [iτ, (i + 1)τ]; l(i) must be 1 or ‑1. The average value of the pulse train waveform f(t) corresponding to a sequence of  pulses is given by

So we don’t need to worry about τ, which is nice! Here we have defined S(N) to be the sum of the l(i) values from 0 to N – 1, so S(1) = l(0), S(2) = l(0) + l(1), and so on.

How can we write a computer program to decide whether the next pulse to output should be a 1 or a -1? I think the first algorithm most of us would think of is the following: “keep track of the average value, S(N) / N, at each instant. If the current average is less than ν, output a 1 next; otherwise output a -1.” I will skip a formal proof that the pulse train emitted by this algorithm converges as desired, but it is intuitively reasonable that it does, because each additional output pulse moves the average up or down by a smaller amount than the previously emitted pulse, and each pulse nudges the average in the desired direction.

It’s straightforward to write a computer program that accomplishes the above. In C-like pseudo code the program looks like this:

N=1;

while (1) {

S_N = compute_current_S_N();

if ( (S_N/N) < v )

output(1);

else

output(-1);

N++;

}

This can be equivalently written as

N=1;

while (1) {

S_N = compute_current_S_N();

if( N*v – S_N > 0 )

output(1);

else

output(-1);

N++;

}

Now it’s time to draw a system diagram to implement this algorithm. Clearly it will contain some sort of feedback, because the pulse value to output next depends on the past sequence of output values. There will also be a need to compute a difference, and somehow we will need to accumulate the values S(N) and Nν. Consider the system diagram below:

Lets analyze this diagram to see if it does the right thing. I’ve labeled the input ν and the feedback line l. With respect to the feedback line, the box with a z in it means “delay by one time instant”; the indexes of l on either side of this box reflect that delay. The box with a plus sign in it is an instantaneous summer, which has been configured in this case to take the difference between its two inputs. The large box is a quantizer, and the graph within it shows the input/output transfer function q( ).The graph means that any input value greater than 0 will result in an output value of 1, while any input value less than 0 will result in an output value of ‑1. Finally, the box with a capital sigma (Σ) in it is an accumulator, also know as an integrator. Its output is the sum of all its previous inputs.

To see if this system diagram results in the required stream of pulses l(i), we need to analyze the variable y. This is most easily done by creating a table as shown below:

The quantizer is executing the “if then” portion of the computer program, and the summer and accumulator are computing the running sum needed as the argument for the if function (i.e., as the input to the quantizer). This system will do the trick!

This diagram is often written in a slightly different form to more closely model its realization in hardware as follows:

All that is going on here is that the quantizer in the first diagram is replaced with the combination of an analog-to-digital converter (ADC) and a digital-to-analog converter (DAC). The ADC outputs a 1 if its input is greater than 0 and a 0 if its input is less than zero, so a bitstream is created at the indicated point. The DAC converts the bitstream back to a sequence of -1 and 1 values. Finally, to indicate the analog nature of this modulator when used as part of a ΔΣ converter, the accumulator is replaced by an integrator:

Now, assume the ΔΣ modulator above is used as part of an analog-to-digital converter. If the input signal changes slowly relative to the rate at which bits are produced, then many bits will be generated before the signal changes significantly, and the average value the bits encode will be close to the true value. In other words, the 1s and -1s the bitstream represents have time to “average out” to an accurate representation of the input signal.  Of course, this average still has to be computed numerically after the modulator; more on that later. However, the faster the input signal changes, the fewer bits will be generated before the signal has changed significantly, and the less accurately the bitstream will represent the signal. At an intuitive level, this is why the quantization noise of ΔΣ converters increases as a function of the input frequency of the signal.

When used as part of an analog-to-digital converter, the modulator is followed by a digital filter and a decimator. The digital filter computes the averages encoded in the bitstream; the decimator reduces the sample rate from the high rate of the 1-bit ADC to the Nyquist rate associated with the final multi-bit samples. The binary representation of the decimated samples is used as the AD output bits.

Part II discusses filtering and decimation in greater detail, and presents some simulation results.

Mike Perkins, Ph.D., is a managing partner of Cardinal Peak and an expert in algorithm development for video and signal processing applications.

Ben’s Golden Rule for Preventing Memory Leaks

As an embedded software engineer, I spent the majority of my time writing code in C and C++. One somewhat-justified knock on these languages is that they both force the programmer to sweat all the details involved with memory management.

One particular bugaboo of the C/C++ engineer is the memory leak: Memory that is dynamically allocated but, because of a programming error, isn’t returned to the system when it is no longer used. On an embedded device, leaked memory will grow over time, consuming more and more of the available resources until there is no choice but to reboot the device. And that’s a Really Bad Thing.

I’m not going to tempt fate by declaring that my code is impervious to memory leaks. Far from it! However, I have developed an approach to dynamically allocated memory that I like to see all my teams follow. With this approach, memory leaks tend to happen much less frequently.

It really boils down to a single, simple idea, which I immodestly call Ben’s Golden Rule for Preventing Memory Leaks:

A pointer variable is either referencing dynamically allocated memory, or it is NULL.

One of the nice things about setting a pointer to NULL is that, if you happen to dereference it by mistake, your program will immediately crash. This is a good thing, because hopefully it means the bug will be rather obvious and thus caught early in the testing cycle.

Here are some simple steps to implement Ben’s golden rule:

1. Initialize all pointers to NULL. Don’t ever let a pointer hold random junk. Initialize it to NULL even if you are going to assign it in the very next line of code:

   SomeComplexObject *my_object = NULL;

   my_object = new SomeComplexObject();

2. Reset pointers to NULL immediately upon freeing them. Even at the bottom of a function where your variable is about to go out of scope, you should pedantically reset it to NULL after a call to free() or delete. This way, if someone later refactors this code, or extends it, the likelihood of a bug creeping in is much lower.

   delete my_object;

   my_object = NULL;

3. Before assigning anything to a pointer, check to see if it is NULL unless the immediate line of code above the assignment sets it to NULL:

   my_structure_t *a_struct = NULL;

   // ... lots of stuff here, including possibly code that allocates a_struct

   if (a_struct) {

   free(a_struct);

   a_struct = NULL;

   }

   // now we know it’s NULL

   a_struct = (my_structure_t *) malloc (sizeof(my_structure_t));

   In some cases, tools like Coverity may complain about redundant checks for NULL. So you will have to be flexible here; if your coding standard (or your customer!) demands that your code be free of such warnings from Coverity, you will have to remove some of the checks. However, be aware that bugs may creep in during maintenance or refactoring.

4. Be aware that several C library routines may perform “surprise allocations” by calling malloc() internally. This depends on your C library, but typical calls include things such as strdup and vasprintf. If you use such functions in your code, you will need to audit all code paths that use them to ensure that memory is freed in each path.

5. Don’t mix references to dynamically-allocated memory with references to other types of memory within the same pointer. An example of what NOT to do comes from some UI code I found, which I have obfuscated to protect the guilty party.

   char *search_key = NULL;

   // If MyCheckBox is selected, copy the search_key from the

   // MyTextEntry widget; otherwise, set it to "not_used"

   if (gtk_toggle_button_get_active(MyCheckBox))

   search_key = strdup(gtk_entry_get_text(MyTextEntry));

   else

   search_key = "not_used";

   // Ugh! At this point, the rule about whether or not you should

   // call free(search_key) are confusing. Don’t do this!

   // ... subsequent code does something with search_key ...

   free(search_key); // note, this is a bug half the time

   search_key = NULL;

6. Initialize C++ member variables that are pointers to NULL in your constructor, and in your destructor, release all member-variable pointers, and then immediately set them to NULL.

   Storage::Storage :

   mPointerToData(NULL)

   {

   }

   Storage::~Storage()

   {

   if (mPointerToData != NULL)

   delete mPointerToData;

   mPointerToData = NULL;

   }

7. In C++, use std::string instead of char *. The std::string class handles all memory management internally, and it’s fast and well-optimized.

8. Make sure you match up your [] operators.One odd bug unique to C++ programs can cause mysterious memory leaks. It is easy to allocate an array of items with new [], and then use delete, rather than delete [] to free the memory. Any time you allocate an array with new [], you must audit your code to ensure that the deletion is always done with delete [], rather than just delete. The compiler will usually let you get away with it, but at runtime you will see memory leaks and allocation arena corruption.

Finally, another helpful design tool for avoiding memory leaks is to very clearly state in the design and code comments where specific items are created, and where they are deleted. Consider making the allocations all go through a single routine, and deletions through another. In C, these can be placed in a single source file, and in C++, you can make them methods of the same object. I’ll have more to say about this in a future post.

Ben Mesander has more than 18 years of experience leading software development teams and implementing software. His strengths include Linux, C, C++, numerical methods, control systems and digital signal processing. His experience includes embedded software, scientific software and enterprise software development environments.

The Cost of an Engineer-Hour

As all good project managers know, there are three dimensions to any engineering effort:

• The features of the product: What does the product do and how does it look? (For sake of simplicity, let’s include “quality” as a product feature.)
• The schedule on which the product is produced: How fast does it get to market?
• The cost of producing the product: How much money does your company have to invest in bringing the product to market?

Before we started Cardinal Peak, my partners and I had all spent many years as engineering managers inside of various companies. To me, it always seemed that I was most visibly measured on the first two dimensions: features and schedule.

To the extent that I was measured on the cost axis, the companies I worked for would normally use “number of heads” as a loose proxy for “dollars spent to bring this product to market”. But I had a lot less control over the number of heads assigned to my team than I did over the other two dimensions, and as a result I believe that perceptions of my success were influenced almost entirely by how my team met our goals in the first two dimensions.

So I guess it’s not surprising that back then I only had a vague idea about how to assign a dollar value to any engineering team’s most precious resource: the engineer-hour.

The somewhat embarrassing truth is that previously I didn’t think about dollar costs too much. I had heard from other managers that an engineer cost my company about $220,000 per year, once you accounted for all the indirect costs like benefits, IT, rent, HR and administrative support. (This specific example comes from Silicon Valley in about 1998, in a relatively high-benefit, high-support environment.)

But I couldn’t really derive the annual engineer cost from any hard data, because I wasn’t directly responsible for any of those expenditures. (I did have a degree of influence over a new hire’s starting base salary. After that, however, everything was relatively programmed: Raises were given within parameters set by the HR department and company management, as was the bonus program.)

I don’t want to make the mistake of projecting my own personal naïveté onto others! But this conversation comes up occasionally, usually from engineering managers for whom it is self-evident that the cost of internal hiring is so much lower than the cost of hiring a firm like Cardinal Peak.

So on an airplane flight recently, I pulled together this spreadsheet, which you can use to compute your own internal cost for an engineer-hour.

I have pre-filled certain cells with reasonable values for a relatively low overhead, mid-benefit engineering team located in Colorado. I’ve tried to model the compensation package given to a competent senior engineer who has 8-12 years of experience. This isn’t your team lead, but neither is it the young gal you just hired with a Master’s degree. Instead, I’m trying to model the engineer who will form the backbone of your team—the  workhorse who will show up on time, focus on work, and reliably crank out features.

Your situation may be different, so feel free to play around with the cell values to see what your own costs are.

Howdy Pierce is a managing partner of Cardinal Peak with a technical background in multimedia systems, software engineering and operating systems.

The Math Behind Analog Video Resolution

The world is moving in the direction of HDTV, but NTSC “standard def” signals are still common for many reasons and will remain so. One important reason is that cameras that output NTSC are widely available and cheap! Many applications, including a lot of security applications, simply don’t require the resolution of HDTV…and don’t want to incur the camera cost and bandwidth hit it requires.

So, what is resolution anyway, especially with regards to an analog NTSC video signal? Analog video cameras, especially in the CCTV industry, are sold using “horizontal TV lines”, or HTVL, as one of their key specifications. Unfortunately, the math behind that concept is not well understood.

To understand resolution we start with the aspect ratio. The aspect ratio of a picture is the ratio of its width to its height. Different aspect ratios are in use today for different applications. HDTV has an aspect ratio of 16:9. Standard definition TV has an aspect ratio of 4:3. In general, resolution is measured in a circle whose diameter is equivalent to a picture’s smallest dimension. The diagram below illustrates the case for NTSC:

In the above diagram, the circle has a diameter of 3 units or 1 “picture height”.

Now, imagine a uniformly spaced sequence of vertical black lines of constant width. The white space between the black lines should be the same width as the black lines themselves. Counting both black and white lines, how many lines can be physically resolved within the above circle? The answer to this question is the horizontal resolution. Before we can go further, we need some facts regarding NTSC:

First, there are 525 scan lines per picture, and the horizontal scanning frequency is

This is one of NTSC’s magic numbers. The horizontal line time is therefore approximately 1 / 15,734.26573, or 63.5556 µsec.

Second, the horizontal blanking period is 10.7 µsec. During this period a horizontal sync pulse is transmitted, as well as a chroma burst (to enable decoders to demodulate the correct color), and a reference black level. The active line time—the period during which information is actually being drawn on the visible screen—is therefore 63.5556 – 10.7, or 52.8556 µsec.

Finally, the highest broadcast luminance signal is 4.2 MHz.

Based on the above, we can compute the highest horizontal resolution that can be present in an NTSC signal as follows:

The product of the middle two parameters is the number of complete cycles present in one active line (the MHz and microseconds cancel); the factor of 2 is present because we count both the white and black lines in the horizontal resolution calculation. Multiplying by three-fourths takes into account the circle in which the horizontal resolution is defined. Bear in mind that this pattern would be displayed on an NTSC TV as grey, not as a crisp sequence of black and white lines, due to the rolloff of the various filters used to limit the video bandwidth.

In the vertical direction, resolution is limited by the number of scan lines. There are 480 scan lines in the visible area of a picture, so one would be tempted to assert that the vertical resolution is 480. However, imagine a uniformly spaced sequence of horizontal lines analogous to the vertical line pattern described above. We want this horizontal pattern to be discernible regardless of its relative relationship to the scanning lines. In other words, as the pattern is displaced vertically, the number of lines should still be easily resolved.

Imagine that we have a pattern of 480 horizontal lines, alternating black and white. When these lines are exactly midway between the scanning lines, the resulting picture will be grey. Why? Because the scanning will average the black and white inputs together for each reproduced line. So a pattern of 480 lines would not be discernible: the resolution must be less. The Kell factor measures by how much the vertical resolution is reduced relative to the number of scan lines, and it is usually assumed to be around 0.7 for a stationary pattern. This implies the following vertical resolution:

The horizontal and vertical resolutions are therefore approximately equal. This was one of the design goals of NTSC.

Note that the Kell factor is sometimes assumed to be a larger number for a pattern in motion because visual averaging will cause the eye to “ignore” the occasional grey or blurry pattern. Values as high as 0.9 are assumed for moving images.

Note further that the reason the Kell factor does not apply horizontally is that it is possible to put down the dots on a CRT so close that regardless of the horizontal phase of a 4.2 Mhz vertical line pattern, it will be resolved. However, the Kell factor does apply in the horizontal direction for a digital display such as a computer monitor or LCD panel.

In a digital SDTV system based on the CCIR 601 digital sampling standard, the luminance information is sampled at 13.5 Mhz. The number of samples per active line is therefore given by 13.5 × 52.8556 = 713.56. This number is often rounded up to 720 samples; rounding up provides some headroom on either side of the visible line to hide the edge effects of various digital processing operations such as filtering. Plus, margin is generally good in any design!

Nyquist sampling theory says that sampling at 13.5 Mhz would theoretically allow a horizontal frequency as high as 13.5 / 2 = 6.75 Mhz to be captured. However, because of the inability to implement perfect anti-aliasing filters, this cannot be achieved in practice. A reduction factor of 0.75 is appropriate, implying that the CCIR-601 sampling standard is good for horizontal frequencies as high as 0.75 × 6.75 = 5.06 Mhz. This is substantially better than old-fashioned analog NTSC broadcasts. Therefore, on a good monitor with analog component input, a CCIR-601 signal can achieve the following horizontal resolution:

For a SIF resolution picture (360×240), we are effectively sampling at 6.75 Mhz, not 13.5 Mhz, so the highest horizontal frequency that can be reproduced is 0.75 × (6.75/2) = 2.53 Mhz, which corresponds to a horizontal resolution of:

Bear in mind that to achieve this number one needs to do an excellent job of filtering.

In the case of displaying a SIF picture on a computer monitor, we can approximate the horizontal resolution by using a Kell factor in the horizontal direction. This yields the following:

In the above, the 0.7 is the Kell factor and the 0.75 is to account for the aspect ratio (remember, resolution is computed inside the circle). A value of 360 was used for purity’s sake. The MPEG world uses 352 and 704 because they are related by a factor of 2 and both are multiples of 16 (360 is not a multiple of 16). It also means there is a little less data to compress!

Mike Perkins, Ph.D., is a managing partner of Cardinal Peak and an expert in algorithm development for video and signal processing applications.