Tuesday, August 3, 2010

Mathematical Tragedy- Patriot ABM Systems

On 26th July, 2010, Defense Research and Development Organization (DRDO), successfully conducted fourth consecutive Interceptor Missile test in Endo-Atmospheric regime at 15 Km altitude off ITR, Chandipur, Orissa.

Surely it was a moment of celebration for Indian scientists and a step towards indigenous Indian ABM (Anti Ballistic Missile), but I was busy in collecting
facts and figures in Math after inspired by a famous Mathematical Quote:

" If people do not believe that mathematics is simple,it is only because they do not realize how complicated life is. "
-- John Louis von eumann

The same once appeared true for MIM- 104 Patriot Surface to Air Missile, Patriot's primary mission is to serve as US Army's ABM System, The proliferation of ballistic missiles have in recent years become a major international security concern. This is also due to the widespread -- but incorrect -- perception that even conventionally-armed ballistic missiles are tremendously destructive.

This perception that ballistic missiles are inherently weapons of great destructive capability may have played a key role in the politics of the Gulf War. Iraq fired more than 80 modified Scud missiles at Israel and Saudi Arabia during the 1991 Persian Gulf War, causing 31 deaths, numerous injuries, and substantial property damage. However, with the exception of the Scud that hit a barracks in Dhahran, Saudi Arabia, and killed 28 U.S. soldiers, the number of casualties caused by these Scuds was much lower than was generally anticipated. During the war, the Patriot missile system was credited with almost complete success in intercepting the Iraqi Scud missiles, and the low casualty rate (relative to the public's expectations) seemed to confirm Patriot's success. The belief on the part of the Israeli population that they were being successfully defended by Patriot was crucial in keeping Israel out of the war.

Since the end of war, the casualties caused by the Scuds have become part of the debate over the effectiveness of the Patriot missile defense system. Several analysts have cited the relatively low casualty rate as evidence of the success of Patriot, while others have argued that the same casualty data suggests that the Patriot may not have been very successful. more to read...

Well this article, as I already promised is not about Indian or US ABM capability but to shed light on- "To err is a Man (especially, when playing with Math)"....

" If you think dogs can't count, try putting three dog biscuits in your pocket and then giving Fido only two of them. "
-- Phil Pastoret

So, the story starts on February 25, 1991, when an Iraqi Scud hit the barracks in Dhahran, Saudi Arabia, killing 28 soldiers from the US Army's 14th Quartermaster Detachment, after initial enquiry it was found that patriot's interceptor missed the scud by 600 meters, but again as usual my reaction was..How it happened?

To understand the mystery, one requires little bit knowledge of "Roundoff Error" (in Math or Computing) leading to "minute mathematical error", but I will try my best to explain:

The accident was an inaccurate calculation of the time since boot (when the system was started/installed) due to computer arithmetic errors. Specifically, the time in tenths of second as measured by the system's internal clock was multiplied by 1/10 to produce the time in seconds, i.e. PESA (Passive electronically scanned radar) radar of Patriot is required to scan the space (sky) in every 1/10th of a second, generally computer's internal clock- Quartz Clock is made up of crystals (as their oscillations are constant) which can oscillate (pizzo-electric effect), based on the number of oscillations time is calculated for example...let us suppose 100 oscillations of Quartz clock = 1 sec of UTC (Universal Coordinated Time), then it's easy to calculate 1/10th of a second = 10 oscillations. This number of oscillations of internal clock in Patriot system is multiplied by 1/10 (stored in 24-bit fixed point register) to get 1/10th of a second, since it is mandatory for patriot to scan the space in each and every 1/10th of a second.

In Patriot system 24 bit fixed point register is used to store the number- 1/10 as represented in fraction, in decimal (base-10) it is represented as 0.1 but in binary (base-2) the number represents a non-terminating expression i.e. 0.0001100110011001100110011001100....and so on, but the problem is, the register which was used to store 1/10 in binary has 24 bits of space thus digits after 24 bit positions are chopped or rounded off.

In particular, the value 1/10, which has a non-terminating binary expansion, was chopped at 24 bits after the radix point. The small chopping error, when multiplied by the large number giving the time in tenths of a second, led to a significant error. Indeed, the Patriot battery had been up around 100 hours, and an easy calculation shows that the resulting time error due to the magnified chopping error was about 0.34 seconds.

The number 1/10 equals 1/24+1/25+1/28+1/29+1/212+1/213+.... In other words, the binary expansion of 1/10 is 0.0001100110011001100110011001100.... Now the 24 bit register in the Patriot stored instead 0.00011001100110011001100 introducing an error of 0.0000000000000000000000011001100... binary, or about 0.000000095 in decimal. Multiplying by the number of tenths of a second in 100 hours gives 0.000000095×100×60×60×10 = 0.34.

A Scud travels at about 1,676 meters per second, and so travels more than half a kilometer in this time (0.34 seconds). This was far enough that the incoming Scud was outside the "Range Gate (Where the scud will next appear after last radar scan)" that the Patriot tracked. Ironically, the fact that the bad time calculation had been improved in some parts of the code, but not all, contributed to the problem, since it meant that the inaccuracies did not cancel.

Note: I have not explained fixed-point representation, as it is not handy for me to include each and everything...but little bit about it explained in the following paragraph [excerpted from the US Government Accountability Office (GAO) report]

The range gate's prediction of where the Scud will next appear is a function of the Scud's known velocity and the time of the last radar detection. Velocity is a real number that can be expressed as a whole number and a decimal (e.g., 3750.2563...miles per hour). Time is kept continuously by the system's internal clock in tenths of seconds but is expressed as an integer or whole number (e.g., 32, 33, 34...). The longer the system has been running, the larger the number representing time. To predict where the Scud will next appear, both time and velocity must be expressed as real numbers. Because of the way the Patriot computer performs its calculations and the fact that its registers are only 24 bits long, the conversion of time from an integer to a real number cannot be any more precise than 24 bits. This conversion results in a loss of precision causing a less accurate time calculation. The effect of this inaccuracy on the range gate's calculation is directly proportional to the target's velocity and the length of the system has been running. Consequently, performing the conversion after the Patriot has been running continuously for extended periods causes the range gate to shift away from the center of the target, making it less likely that the target, in this case a Scud, will be successfully intercepted.

" Pure Mathematics is the world's best game. It's more absorbing than chess, more of a gamble than poker, and lasts longer than monopoly. It's free, it can be played anywhere- Archimedes did it in a bathtub.
-- Richard J. Trudeau, Dots and Lines.