Re: Proposed Electronic Ballot Image Format for the Demo

From: Alan Dechert <adechert_at_earthlink_dot_net>
Date: Sat Aug 23 2003 - 18:25:09 CDT

Arthur wrote:

> The "Y" below is for ballot type. For example, for primary races by
> party, the "Y" represents the party.
I had something different in mind -- but this is not very important at this

> I don't understand why the ballot selections are fixed length.
> Shouldn't it depend on the length of the ballot? ....
The ballot we are using for the demo has 116 bits, 45 candidates, and 13
contests altogether.

I don't think we want to get into how various length ballots will be
handled. There are all sorts of rules about column headings, spliting
contests over columns, spliting contests over pages, spacing, font sizes,
and so on that become important when formatting the ballot, and become very
tricky if you're trying to handle this programatically. We want to stay out
of the mine field -- the demo could take several times longer to produce
with very little value added to it.

> Also, two digit codes for ballot contests may not be enough. If you
> use 2 hexadecimal characters (0-F), you support 256 choices in the
> same space.
Again, we are using a normal sized ballot in our demo. We have 13 contests.

That's pretty normal. Some elections have more, some less. The October
election in CA has only 4 or 5 contests. I never heard of an election with
more than 100 contests. You may be correct about allowing for the
possibility, but this issue is not a large concern for the demo. We are not
designing the production system.

There is more than enough stuff to demo here. I have listed 22 things:

Programatic handling of ballot formating is essential for the larger study
but is way beyond the scope of the demo ... whatever can be done along these
lines without great effort could be included but I would give it a very low

Maybe besides talking about what needs to be in the demo, we should also
characterize the importance of the various requirements we are including.

Most of the 22 things I listed are *must have* requirements. Number 7 is
about 500 times more important than most of the others. Let's keep things
in perspective.

If we prioritize these as


I would say that all of the 22 are MUST HAVE with a few exceptions:

4, 9, 11, 16, 17, 18, 19, and 20, might go down as HIGHLY DESIRABLE.

21 is NICE TO HAVE and it's trivial to do so we might as well do it.

Demo-ing programatic ballot forming is somewhere between WOULDN'T HURT TO
HAVE and DON'T CARE. Given how much it will cost the project, forget it.

> As far as ballot vote coding is concerned, here is a proposal:
Your proposal sounds good, although I haven't studied it in any detail and
can't say I fully understand it. I'm just an artist, remember -- not a
computer scientist.

All I really want to know is how many 7-bit characters will be needed to
encode bits for this ballot:
which amounts to a 116 bit string. My half-assed scheme needs ten 7-bit
characters. Your more scientific scheme takes less, I gather. If so, I
favor it.


Alan D.

> Assume the races on any given ballot are in fixed order.
> Assume all zeros is invalid
> Assume the number 1 means no vote selected.
> Assume the highest number (I'll define this later) means that there
> is a write-in vote for this race. The write-in votes are in the same
> order as the races themselves, for those races for this ballot for
> which there is a write-in vote.
> This means that if there are 6 declared candidates, then the
> encodings are 1 (no vote), 2-7 (the candidates in a defined order),
> and 8 (write-in).
> Numbers are in binary coded octal, transformed to make them
> self-delimiting. See my paper in
> (Arthur M. Keller and Jeffrey
> D. Ullman, "A Version Numbering Scheme with a Useful Lexicographical
> Order," appeared in Int. Conf. on Data Engineering , Taipei, Taiwan,
> March 1995. Also a Postscript file), which includes a discussion on a
> self-delimiting number scheme. With 3 bits (it's octal, remember?),
> you can code up to 3 choices, and with 6 bits you can code up to 19
> choices. And 9 bits can code up to 147 choices. (If you want, you
> can have more short codes, but at the risk of making the longer codes
> even longer.)
> An advantage of a self-delimiting variable-length codes is that it
> makes it harder to compare votes, particularly if there are many
> votes.
> We could use binary coded hexadecimal instead. Then 4 bits code 7
> choices, 8 bits code 71 choices, and 12 bits code 1095 choices.
> It's best to stick with one coding scheme and not switch for each race.
> Now, calculate the maximum number of bits possible for any ballot and
> add 9 bits (or some number that isn't equal to one bar-code character
> and is "big enough."
> Now suppose that the maximum number of bits in a race is 500 bits
> (not counting the extra 9 bits) and suppose some ballot is 300 bits
> long. Then you have 200 bits extra. Since you don't want to make
> "short" ballots or "long" ballots stand out, except for write-ins,
> you can place the 300 bits starting anywhere between bits 1 and 201.
> The 9-bit (or whatever) prefix tells you where the 300 bits start.
> So choose a pseudo-random number between 1 and 201. The "extra" 200
> bits are placed at the beginning and/or the end of the ballot, and
> they are pseudo-randomly chosen bits. Now it is impossible for the
> human to compare ballots by eyeballing them. Yet it is extremely
> easy to code and decode.
> Now suppose we use a barcode that has 7-bit characters. Then adjust
> the "maximum" number of bits to be 7 more (1 more character) than
> the original maximum number of bits rounded up to the next multiple
> of 7. This way, every ballot has the possibility for *some*
> shifting, even if it is a maximum length ballot.
> Now, I suggest that we use 3-bit (octal codes) as they will work best
> for this scheme for yes/no propositions that have 3 choices (the
> write-in choice is invalid, but the "no-vote" choice *is* valid), and
> those choices proliferate the ballot, at least in California.

= The content of this message, with the exception of any external
= quotations under fair use, are released to the Public Domain
Received on Sun Aug 31 23:17:14 2003

This archive was generated by hypermail 2.1.8 : Sun Aug 31 2003 - 23:17:18 CDT