May 18th, 2009

Программизм

Попытка разоблачения черной магии

Некоторое время назад Витус опубликовал пост, описывающий результаты экспертизы некоего прибора для анализа алкоголя в крови (оригинал у Брюса Шнайера). К софту, использованному внутри прибора, предъявлялись следующие претензии (у Витуса они есть по-русски, скопировал от Шнайера):

2. Readings are Not Averaged Correctly: When the software takes a series of readings, it first averages the first two readings. Then, it averages the third reading with the average just computed. Then the fourth reading is averaged with the new average, and so on. There is no comment or note detailing a reason for this calculation, which would cause the first reading to have more weight than successive readings. Nonetheless, the comments say that the values should be averaged, and they are not.

3. Results Limited to Small, Discrete Values: The A/D converters measuring the IR readings and the fuel cell readings can produce values between 0 and 4095. However, the software divides the final average(s) by 256, meaning the final result can only have 16 values to represent the five-volt range (or less), or, represent the range of alcohol readings possible. This is a loss of precision in the data; of a possible twelve bits of information, only four bits are used. Further, because of an attribute in the IR calculations, the result value is further divided in half. This means that only 8 values are possible for the IR detection, and this is compared against the 16 values of the fuel cell.

4. Catastrophic Error Detection Is Disabled: An interrupt that detects that the microprocessor is trying to execute an illegal instruction is disabled, meaning that the Alcotest software could appear to run correctly while executing wild branches or invalid code for a period of time. Other interrupts ignored are the Computer Operating Property (a watchdog timer), and the Software Interrupt.

По 4 пункту ничего сказать не могу. Смотреть надо.
3 пункт сам по себе тоже не особо интересен.

Смотрим на п.2. Что видим? Сразу хочу отметить, что высказанное мной - не плод исключительно моих заключений, а результат обсуждений с друзьями, выпускником ВМК и действующим преподавателем мехмата.

Матожидание величины, полученной таким образом, совпадает с матожиданием среднего арифметического (получается формула геометрической прогрессии). Дисперсия хуже, не вопрос. Если первые измерения менее точны, то результат получится лучше в плане близости к истине, чем честное среднее арифметическое, но тут без физической модели сказать что-то трудно. Документировать это, не вопрос, стоило, но невеликий грех.

Описанный алгоритм куда сложнее среднего арифметического. Но программисты просто так обычно ничего не делают. Посмотрим, что этот алгоритм дает.

Во-первых, дает он экономию одного регистра долговременной памяти.
Во-вторых, там нет деления на произвольное число. Есть только деление пополам. То есть - сдвиг.

Честно говоря, эти соображения наводят меня на мысль, что софт просто взят с более древней версии датчика. В эту схему и пп. 3-4 тоже ложатся. И никакой идеологиичерной магии.

Прошу этот пост комментировать только с технической точки зрения.