Problem Sets

PARITY

In 1962, a missing hyphen destroyed a $18.5 million spacecraft.

On July 22, 1962, NASA launched Mariner 1 — America's first attempt to send a spacecraft toward Venus. The Atlas-Agena rocket lifted off from Cape Canaveral at 9:21 AM. Everything looked normal.

Then, 293 seconds into the flight, the rocket began to veer off course. The guidance system, which was supposed to keep the vehicle on a smooth trajectory toward space, had received an incorrect command. The rocket's steering went haywire. Range Safety Officer Robert E. Grey watched the data, made a decision no one wants to make, and pressed the destruct button.

The rocket exploded over the Atlantic Ocean. $18.5 million (equivalent to roughly $180 million today) vanished in a ball of fire.

The investigation revealed an almost unbearably simple cause: a single missing hyphen in the guidance code. One character. A bar (-) that should have been overbar (̅). The programmer who transcribed the mathematical equations from paper to punch cards missed this one symbol. The computer, doing exactly what it was told — nothing more, nothing less — interpreted the equation correctly, but for the wrong formula.

Mariner 1 was not the first system destroyed by a small data error, and it would not be the last. In 1996, the European Space Agency's Ariane 5 rocket self-destructed 37 seconds after launch because of an integer overflow — trying to store a 64-bit number in a 16-bit space. The rocket was worth $500 million. In 1999, NASA's Mars Climate Orbiter was lost because one team used metric units and another used imperial. The spacecraft approached Mars at the wrong altitude and disintegrated in the atmosphere. Cost: $327 million.

These are not programming errors in the way most people think of them. They are not bugs in algorithms. They are data integrity errors — the wrong data, the wrong format, the wrong unit, the wrong symbol. And they are devastating precisely because computers are so precise: they process exactly what they receive, with no common sense to catch obvious mistakes.

How do you protect against this?

The answer has been known since 1947, when a mathematician named Richard Hamming was working on the same problem at Bell Labs. Hamming was using a relay computer — a room-sized machine that processed data by physically opening and closing electrical switches. The computer ran on weekends, and if an error occurred, the entire calculation would stop. Hamming's programs would have to wait until Monday to be re-run, wasting days.

Frustrated, Hamming asked a question that would change computing forever: Can we detect errors automatically, without human intervention?

He discovered that by adding just a few extra bits — called parity bits — to any piece of data, you could detect whether an error had occurred during transmission or storage. A single bit of redundant information, calculated from the data itself, could tell you whether something had gone wrong.

Parity works like this: you count the number of 1s in a binary string. If the count is even, the parity is even. If the count is odd, the parity is odd. By storing one extra bit — the parity bit — you create a simple checksum. If a single bit flips during transmission, the parity changes, and the receiver knows something went wrong.

This idea — that a small amount of redundant information can catch errors — is now used everywhere:

• Every byte of RAM in your computer can have a parity bit that detects memory corruption
• Spacecraft like Voyager 1 and Voyager 2 use parity and more advanced error-correcting codes to communicate across billions of kilometers of space
• QR codes use parity-based error correction, which is why they still work even when partially covered
• Every WiFi packet, every Bluetooth transmission, every USB data transfer uses parity or its descendants
• The very concept of "checksums" on downloaded files is a direct descendant of Hamming's idea

The Mariner 1 disaster cost $18.5 million and delayed America's Venus exploration by years. Richard Hamming's parity system costs almost nothing — a single bit — and catches errors that would otherwise go undetected.

Specification

In a file called parity.py, implement a program that:

1. Prompts the user for a binary string (containing only 0s and 1s)
2. Counts the number of 1s in the string
3. Prints the count of 1s
4. Reports whether the string has even or odd parity

Demo

Enter a binary string: 10101
1s: 3
Error detected — odd parity

Enter a binary string: 10100
1s: 2
Valid — even parity

Enter a binary string: 00000
1s: 0
Valid — even parity

Hints