How big could a bar code be if a bar code be big?

From: David Mertz <voting-project_at_gnosis_dot_cx>
Date: Fri Apr 30 2004 - 20:58:44 CDT

On Apr 30, 2004, at 9:23 PM, Alan Dechert wrote:
> I'm not sure of these calculations and I'm not sure compression could
> not be
> used effectively.

Compression as such is really just not workable. It just can't work to
have the barcode be of indeterminate size (and possibly longer than
usable). However, rather than -compression- we can use more optimal
encodings of contests, thereby obtaining theoretical best sizes. It is
not difficult to create an optimal encoding for each contest type.

I created a tool to calculate the precise entropy (information content)
in any election ballot. I'll attach that rather than inline it. The
tool is used as:

   $ ./election-entropy.py < demo-election.data
   Election summary for OVC demo ballot (write-ins count as candidate)

   269995136716800 distinct votes are possible
   Optimal encoding is approximately 48 bits
   Contests at bit-boundaries, approx 53 bits

The bit boundary thing is not that complicated, but it's worth noting.
Most contests will use a fractional number of bits to encode. For
example, a single-selection contest with 9 options (candidates) has
3.17 bits of entropy. While it *is* possible to encode every total
vote combination in an optimal way, it's likely to be MUCH easier--and
less bug-prone--just to, e.g. devote a whole 4 bits to that 9-way race.
  But bit boundaries add to the representation size, versus theoretical
optimum.

The data file used to generate the above numbers is composed to
describe the demo ballot. It should be very straightforward to create
a new data file that describes actual past elections:

   # Election summary for OVC demo ballot (write-ins count as candidate)
   single 8 # Prez, 7 candidates plus write-in
   single 8 # Senator
   single 3 # Representative
   single 3 # Treasurer
   single 4 # AG
   single 3 # Edu Commis
   single 4 # State Senate
   single 3 # Assembly
   single 2 # Transportation initiative
   single 2 # health care
   single 2 # term limit
   multi 3 10 # Cat Catcher
   ranked 8 8 # County Commissioner

Encoding the big binary number as decimal is simple enough. We don't
lose anything in the encoding--or at least not more than a fraction of
one decimal digit (i.e. round up to number of digits).

==================================================================
= The content of this message, with the exception of any external
= quotations under fair use, are released to the Public Domain
==================================================================

Received on Fri Apr 30 23:17:28 2004

This archive was generated by hypermail 2.1.8 : Fri Apr 30 2004 - 23:17:29 CDT