Bit (of data)

A bit of data (not to be con­fused with a shan­non, an ab­stract bit, or a bit of ev­i­dence) is the amount of data re­quired to sin­gle out one mes­sage from a set of two. If you want to sin­gle out one of the hands of one of your biolog­i­cal grand­par­ents (such as the left hand of your pa­ter­nal grand­mother), you can do that with three bits of data: One to sin­gle out “left hand” or “right hand”, one to sin­gle out “ma­ter­nal” or “pa­ter­nal”, and one to sin­gle out “grand­father” or “grand­mother”. In or­der for some­one to look at the data and know which hand you sin­gled out, they need to know what method you used to en­code the mes­sage into the data.

Data can be stored in phys­i­cal sys­tems which can be put into mul­ti­ple states: A coin can be used to store a sin­gle bit of data (by plac­ing it ei­ther heads or tails); a nor­mal six-sided die can be used to store a lit­tle over 2.5 bits of data. In gen­eral, a mes­sage that sin­gles out one thing from a set of \(n\) is defined to con­tain \(\log_2(n)\) bits of data.

“Bit” is a port­man­teau of “bi­nary digit”: “bi­nary” be­cause it is the amount of in­for­ma­tion re­quired to sin­gle out one mes­sage from a set of 2. The 2 is ar­bi­trary; analo­gous units of data ex­ist for ev­ery other num­ber. For ex­am­ple, a Trit is the amount of data re­quired to sin­gle out one mes­sage from a set of three, a Decit is the amount of data it takes to sin­gle out one mes­sage from a set of ten, and so on. It is easy to con­vert be­tween units, for ex­am­ple, a decit is \(\log_2(10) \approx 3.32\) bits, be­cause it takes a lit­tle over three bits to pick one thing out from a set of 10. See also the pages on con­vert­ing be­tween units of data and frac­tional bits.

Talk about how we want to define data such that two ob­jects hold twice as much.

The amount of data you can trans­mit (or store) grows ex­po­nen­tially in the num­ber of bits at your dis­posal. For ex­am­ple, con­sider a punch card that can hold ten bits of data. You can use one punch card to pick out a sin­gle thing from a set of \(2^{10}=1024.\) From two punch cards you can pick out a sin­gle thing from a set of \(2^{20}=1048576.\) The num­ber of things you can dis­t­in­guish us­ing two punch cards is 1024 times larger than the num­ber of things you can dis­t­in­guish with one punch card, and the amount of data you can en­code us­ing two punch cards is pre­cisely twice as much (20 bits) as the amount of in­for­ma­tion you can en­code us­ing one punch card (10 bits). In other words, you can sin­gle out one ob­ject from a col­lec­tion of \(n\) (or store a num­ber be­tween 1 and \(n\)) us­ing \(\log_2(n)\) bits of data. For more on why the amount of data is log­a­r­ith­mic in the num­ber of pos­si­ble mes­sages, see Data is log­a­r­ith­mic.

Add a for­mal­iza­tion sec­tion.