Monday, 29 February 2016

Proportional Representation in Ireland

I am not connected with politics or constitutional law in any way. I wrote this page really as an excuse to study up on something I found interesting. I have done my best to ensure that the content is accurate but if you do find any glaring errors please let me know and I will correct them. If you have any general comments/observations/suggestions about the page, I'd love to hear those also. Thanks.


Since achieving independence in 1921, we in Ireland have elected members to The Dail (one of our Houses of Parliament) using a system of voting called Single Transferrable Vote (article 16, section 2, subsection 6 of The Constitution). The purpose of this page is to explain exactly how this system works, to explain why many political scientists regard it as one of the fairest systems for conducting elections and to examine some of the mathematical anomalies which can arise from it.

Single Transferrable Vote

The basic idea underlying the Single Transferable Vote system of Proportional Representation is that any votes a candidate receives over and above the minimum necessary to be elected should not be wasted. Rather, the voters should be allowed to rank the candidates in order of preference, and any surplus votes a candidate has after being elected should be distributed to the remaining candidates in proportion to the next-highest preferences expressed by each voter.

Some history of the system to go here !

How It Works

The Vote

Voting is simplicity itself. The ballot paper will look something like this:-

Byrne, Gay
Independent Candidate
Haughey, Charles J.
Fine Gael
Lawler, Liam
Progressive Democrats
McGonigle, Eamonn
The All Night Party

The voter simply writes a number beside each of the candidates (or as many candidates as they wish) indicating the order of preference. The voter's favourite candidate will get a preference of 1, the second favourite will get a preference of 2 and so on.

Determination of the Quota

Once the voting is complete, the process of counting the votes begins. The first step is to determine the quota. This is the minimum number of votes which would be sufficient to elect only the desired number of candidates. It is a factor of

  • The number of votes cast
  • The number of people who are to be elected
It is calculated by taking the number of votes cast, dividing this by (1 + the number of seats to be filled), adding 1 to this result and discarding any fractional part. So in an area where 10,000 votes were cast and there are 2 seats, the quota would be 3,334 (= 10000 ÷ (1 + 2) + 1). It should be clear that with only 10,000 votes, it is possible for two candidates to obtain 3,334 votes, but not possible for three.

The First Count

During the first count, all of the first preference votes are counted. At the end of this, one of two things will have happened:-

Possibility #1: One or more of the candidates has reached the quota

These candidates are elected. The next step is to distribute their surplus votes (the number of votes they received over and above the quota). The idea is that these "spare" votes should not be wasted and should be transferrable to the voters' second choices

Possibility #2: None of the candidates has reached the quota

In this case, the candidate with the lowest number of votes after the first count and his/her votes are distributed to the voters' second preferences

Either way, the next step is to proceed to a second count for the purpose of distributing the surplus of the elected candidate or distributing the entire vote of the eliminated candidate.

The Distribution of the Surplus or The Elimination of the Lowest Ranking Candidate

Once a candidate is reaches the quota, any excess votes are distributed to the other candidates in proportion to the next preference votes of the elected candidate. A simple example: Assume that the quota is 3,334 (from our earlier example). Assume also, that candidate Charles J Haughey gets 4,000 votes on the first count. None of the other candidates reaches the quota at this stage. He is deemed to be elected and a second count begins for the purpose of redistributing Charlie's surplus.

At the end of the second count, it turns out that of those 4,000 voters who gave Charlie their first preference, 2,000 gave their second preference to Liam Lawler, 1,500 gave their second preference to Gay Byrne, 400 gave their second preference to Eamonn McGonigle and the remaining 100 didn't express a second preference at all.

Since the quota is 3,334, Charlie has 666 surplus votes to distribute (= 4,000 - 3,334). These will be distributed to the other candidates in the following proportions:-

CandidateTransfers from Charles Haughey
Liam Lawler(666 ÷ 4,000) × 2,000 = 333
Gay Byrne(666 ÷ 4,000) × 1,500 = 249
Eamonn McGonigle(666 ÷ 4,000) × 400 = 66

These transfers are added to each candidate's total from the first count. At this stage, the process begins again: If any candidate has now reached the quota, he/she is elected and another count begins for the purpose of distributing his/her surplus. If no candidate has reached the quota, the lowest candidate is eliminated and the next count will redistribute his/her vote to the next voters' next preferences.

There are some subtleties that arise in the distribution of quota which lead to a small element of randomness.  It can happen in three different circumstances, the most common of which is where voters haven't ranked all of the candidates (i.e. haven't written any number down against some candidates).  In that case, there may be excess votes available to be distributed (e.g. Charlie's surplus of 666) but some of those votes might not indicate a next preference.  Its probably not useful to delve into this in too much detail here: there is a very interesting analysis of this here, including an example (the Sligo-Leitrim constituency in the 1982 general election) where this randomness actually made a difference.

Interestingly, during Ireland's brief and ill-fated dalliance with electronic voting in 2002, the same random mechanism had to be built into the (electronic) counting system, even though a computer could have performed the count using a more accurate (but impractical for a manual count) system.

The Final Result

The final result is arrived at either when either:-

  • The desired number of candidates have reached the quota
  • The number of candidates remaining after the elimination of the lowest-scoring candidate at the end of a count equals the number of unfilled seats

This can happen because voters may not rank all of the candidates on the ballot paper. In our earlier example, the 100 voters who did not express a second preference will not have made any contribution to the second (or any subsequent) count.

But Is It Democratic...?

This system is regarded as among the fairest systems of the electoral systems in use in the world today. However, it is not without its imperfections. These are discussed in some length in put book reference here in considerable detail.

Wednesday, 14 January 2015

Fake MAX3232 RS232 line drivers ?

This is my second post about the plague of knock-off ICs.

The job was simple: I needed an RS232 interface on a Raspberry Pi so that I could use it to log console output from a misbehaving router (don't ask).  I could have picked up one of the millions of USB-to-RS232 converters on eBay (and run the gauntlet of FTDI's clone-bricking updates). However, I have read mixed reports of the stability of the drivers for these adapters in the Raspberry Pi kernel. Besides, there actually is a UART baked into the Pi SoC. The problem is that it only works at 3.3V logic levels so it can't be connected directly to a device that uses RS232 voltages. That's OK...I just picked up one of these and wired it to the appropriate GPIO pins on the Raspberry Pi's I/O connector

Its a simple device.  It converts between logic-levels (this version does either 5V or 3.3V)  on the pin-header and and RS232 voltage levels on the DB9 connector.  All that's on it is a MAX3232 line-driver and four ceramic capacitors (used by a charge-pump in the IC to generate RS232 voltages). It looks like the circuit (such as it is) is lifted directly from the IC's datasheet.

Simple, eh? No.  It worked just fine talking to a PC, but when I connected it to a Cisco 1841 router, very strange things happened.

When I sent a character from the Raspberry Pi to the router (I think I might have just hit carriage-return), this absolute explosion of characters was the result

Wow...what's going on here !  Out with the oscilloscope.  Here is an 'A' being sent from the Pi to the router:-

The blue trace is the Pi's TX line and the yellow trace is the Pi's RX line.  So far so good.  However, a few moments (about 68ms, to be exact) later, this happens:-

As far as I can see, what is happening is that when the Cisco echos back the character it received (yellow trace), there is crosstalk onto its RX (blue), so the router is seeing an "echo" of its own character (but corrupted).  The router echos that character back also, sees another "phantom" character on its RX etc etc.

As I mentioned, Raspberry Pi talking to a PC works just fine.  Sure enough, looking at that on the oscilloscope...

...there are little "spikes" evident on the Raspberry Pi TX line, but nothing like as bad and apparently not enough to cause a problem.

So the question was, where (and how) was the crosstalk happening ?  A few possibilities:-

  • Within the router itself (highly unlikely, or the router wouldn't work with a PC either and would be basically useless)
  • Within the console cable (that was my first theory when  was using a patch-cable, but I replaced that with a flat-8 cable which keeps the RX and TX lines separated by a few mm and that made no difference)
  • On the adapter board somewhere (most likely, but why, then, did I see hardly any crosstalk at all with the RPi talking to a PC or to a switch ?)

To test the theory that the crosstalk was happening on the adapter board, I disconnected the RX from the router from the TX line on the adapter board and used to oscilloscope to watch (a) the (now-disconnected) RX line from the router and (b) the TX line on adapter board separately.

Bingo !!  The line from the router was clean as a whistle (thus exonerating both the router and the console cable) but the TX line from the adapter (which shouldn't be generating any signal at all) was worse than ever:-

Yellow is the signal coming up from the router (console messages during the router boot sequence); blue is the output from the line-driver module (which should be completely flat).

I think it is a question of voltage.  The router uses a relatively high voltage on its TX line...around +/-10V.  Still perfectly within the RS232 specifications (which allows for  +/-12V) but higher than either a Cisco switch I tested or the PC use (both about +/-6V).  It looks like the higher voltage breaks down the line-driver.  Sure enough, conducting the same experiment with a switch instead of a router...

So it looks like the MAX3232 line-driver doesn't like +/- 10V on the RS232 side.  It should - according to the data-sheet it should be good for +/- 25V:-

I did one more test to confirm the theory: I put a couple of back-to-back 3.3V zener diodes in between the router TX and the adapter RX.  This has the effect of dropping the voltage that the adapter sees by about 4V.

Sure enough, the problem goes away (I didn't bother saving an oscilloscope trace but - trust me - it was perfect: no signal at all leaking onto the adapter TX). Its really looking like its the voltage that is causing the problem.

So at what voltage does the problem kick in? If I feed a square wave to the RX pin on RS232 side while watching what appears on the TX pin (nothing should) and gradually crank up the voltage, we should be able to find out.  In each of the screen-captures below, the yellow traces is the signal being fed to the RX pin and the blue trace is what is coming out of the TX pin.

Starting with 19.2V peak-to-peak...

No problem so far.  Increasing to 19.4V peak-to-peak...

...and 19.6V peak-to-peak... now we would probably be seeing problems.  Increasing the voltage to 20.6V peak-to-peak...

...and we would definitely be seeing problems.

If a real MAX3232 IC (mis)behaves like this, I'll eat my hat.  I have looked closely at the IC on the adapter and - to my untrained eye - it looks fine (decent enough quality moulding, quality of laser etching looks OK) but I'm willing to bet that these are fakes.

I would really love to get a known-genuine MAX3232 IC from a reputable supplier and use it to replace the suspect one on the adapter, but they only seem to be available in quantities of 2500 (at about €1 each).  Sorry, but I'm just not that interested.  However, if someone wants to send me a few genuine MAX3232s (you will need to pinkie-swear that they are definitely the real thing) I'll be happy to do the test and report the results here.

PS: An interesting thing I learnt in the course of doing this project is that the Raspberry Pi (the Raspbian image, anyway) runs a serial console on its built-in UART. A serial terminal emulator connected at 115,200 baud will receive a login prompt through which you can log in to the Raspberry Pi.  You never know when that will come in handy.

Tuesday, 13 January 2015

Spot the Chinese knock-off.

The IC on the top is the genuine article (its an LED driver). It costs about €10 (+VAT) from a reputable supplier in small quantities (down from nearly €20 a couple of years ago). The IC on the bottom came from eBay. I got ten of them for €3.09. Not €3.09 each...€3.09 for all ten.

Although you can't see it (because the quality of the laser etching is terrible and I couldn't get it to photograph), it has the Maxim logo (rough around the edges if you look closely), the same part number and at a glance looks like the real deal. Its only when you compare them side-by-side that you notice that the knock-off is physically smaller (that's not an optical actually is smaller), has poorer quality legs, poorer plastic encasing and the laser etching is nothing like as good. More pertinently, at first it didn't work in the circuit I put it into where the real one did (although, to be fair, I was playing a tiny bit fast-and-loose with the power-supply decoupling: once I fixed that, the knock-off worked just fine).

If you can't trust randomly-selected eBay sellers in the Orient who can you trust? It makes me wonder if that €30 Rolex I got is real.

Monday, 12 January 2015

Where does Blogger store pictures?

They say that a picture tells a thousand words.  Imagine my dismay, then, when I noticed that all of the pictures from my recent blog posts (all the ones I had created since switching to Blogger, actually) had vanished.  Thousands and thousands of my bons mots lost to the Internet.  Not since the burning of the library in Alexandria has such a misfortune been visited upon the store of human knowledge.

Thankfully, I had copies of most of the missing pictures and they have been restored to their rightful place, but I'm still not completely sure what happened. It turns out that photos you upload directly to Blogspot are actually stored in Google Plus (used to be on Picasa).  It is possible that I did a bit of a clear-out of my Google Plus photos at some point and accidentally deleted them.  I don't remember doing it, but its the kind of thing I would do.

Anyway, this blog post is part warning, part experiment.  Here is a pretty picture:-

It is one of the first pictures I took with my Nikon D50 when I got it almost 10 years ago. Its a fantastic camera and is still my weapon of choice when I need the best possible image quality. It still beats the socks off any other camera I have for image quality and speed (but not portability!).

However, none of that is of any interest to you, the reader.  What is interesting is that I am going to go looking to see where in Google's universe it winds up.  I am also shortly going to delete the picture in Google+ to see what happens.  I'll update this post with my findings.

UPDATE 13/Jan/2015: OK...I have just deleted the picture using the "Photos" app on my Android phone.  So far, no ill-effects on this blog entry, but lets see what happens

UPDATE #2: It didn't happen straight away, but a little while (perhaps an hour) after I deleted the photo from my phone, it also disappeared from the blog. Im rather proud of the photo, so here's another copy of it.

Tuesday, 2 December 2014

Repair of an LED Lenser flashlight

My trusty little LED Lenser flashlight stopped working rather suddenly.  I thought the batteries had failed because (a) nothing that over-engineered could possibly break and (b) there was evidence of crusty white "stuff" inside the battery compartment that looked a little like a battery might have leaked.  Strangely, though, all of batteries measured a little over 1.4V each but there was no voltage present at the terminals of the battery holder.  Oh oh.  It turns out the problem was the little switch in the end-cap.    Here it is desoldered from the top of the battery-pack:-

Although it felt fine mechanically, it was open-circuit all the time.  

Apparently, LED Lenser don't supply parts and I couldn't find a suitable replacement in any of the usual electronic parts suppliers but I couldn't bring myself to write off such a beautiful piece of (over-)engineering.  Time to see if it could be bodged.

I had an el-cheapo (but actually rather nice) 9-LED flashlight that I picked up at a conference a few years ago.  

It had a latching end-cap switch that "felt" pretty similar.  Could it be made to fit ?  It turns out, the switch from it is an awful lot bigger...

On the other hand, its about the right height so perhaps it could be made to fit. With a little bit of help from a grinding wheel, it fitted...barely.

Solder the wires onto the top of the battery-pack...

...and its back to life !!

Its certainly not as water-tight as it was the day it left the factory in Germany (the end-cap doesn't screw down all the way) but on the other hand I never go swimming with it and it isn't gone to a land-fill, so I'm happy.  

Now I just need to figure out what do to with the remains of the el-cheapo 9-LED flashlight that I trashed for this repair - I can't bring myself to throw that out either.

Saturday, 11 October 2014

The Great Crash, 1929

I have just finished reading "The Great Crash, 1929" by John Kenneth Galbraith.  Although written in 1954 about events in America in 1929, an awful lot of it seems very familiar: only the dates and locations have changed.  Its all there: lax monetary policy; rampant credit-fueled speculation (in stocks rather than property) driving prices to stratospheric levels; people investing in assets with little or no idea what those assets actually were (how many people bought apartments in Bulgaria off the plans could actually find Bulgaria on a map, I wonder ?); incompetent regulators asleep at the wheel; a parade of self-appointed experts loudly proclaiming that the upward trend would go on for ever (remember when the term "new paradigm" was briefly in vogue ?) and those who sounded any note of dissent were pilloried and practically accused of treason; predictions of a "soft landing" when it started to become apparent that the end of the boom was in sight.  Its a fascinating read and quite entertaining, despite the subject matter. The last paragraph of the last chapter sums it up well:

"But now, as throughout history, financial capacity and political perspicacity are inversely correlated. Long-run salvation by men of business has never been highly regarded if it means disturbance of orderly life and convenience in the present. So inaction will be advocated in the present even though it means deep trouble in the future."  

Thursday, 18 September 2014

Fun with Python SpiDev

I have been having a little fun trying to get a Raspberry Pi talking to a Winbond SPI W25Q80BV 1MB flash chip (PDF).   The Python SpiDev library is rather poorly documented and doesn't actually seem to do what it is supposed to do.

For starters, it offers two similar functions for transferring data over the SPI bus, called "xfer" and "xfer2".  Both take a single parameter which is a list of bytes to transfer.  According to the documentation, the difference is that for "xfer"...
"CS will be released and reactivated between blocks. delay specifies delay in ┬Ásec between blocks."
and for "xfer2"...
"Perform SPI transaction. CS will be held active between blocks."
Its not completely obvious what a "block" is in this context. I can only guess (and hope) that it might mean between two consecutive invocations of the "xfer2" function (I can't think of anything else useful that it could mean). Also, the reference to "delay" in the description of "xfer" is the only reference to a parameter, attribute or anything else called "delay" anywhere in the documentation.

Anyway, no matter how much I tried, I couldn't see any difference between the behaviour of "xfer" and "xfer2".  Time to break out the logic analyser.  Looking at two successive calls to "xfer"...

root@alarmpi:~# python
Python 2.7.3 (default, Mar 18 2014, 05:13:23) 
[GCC 4.6.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import spidev
>>> spi = spidev.SpiDev()
>>> spi.xfer([0x90,0,0,0,0])
[0, 0, 0, 0, 239]
>>> spi.xfer([0x90,0,0,0,0])
[0, 0, 0, 0, 239]

I pasted the commands in, so the two calls to "spi.xfer" happened very close together in time.

As you would expect, the ENABLE (a.k.a. /CS) line goes low at the beginning of each transfer and high again as soon as the transfer completes.  No problems there...that's what the documentation says is supposed to happen.  Here's what one of the transactions looks like close up:-

Now to try the same test using "xfer2" instead of "xfer".  As I interpret the documentation, the /CS line should stay low between transfers, so that two consecutive calls to "xfer2" would actually look like a single SPI bus transaction, albeit with a bit of a hiatus in the middle.  However, that is not what happens.

If there's a difference there, I'm not seeing it.

Apparently I'm not the first one to ponder this mystery: here and here.

Which brings me to the mysterious "delay" parameter.  It turns out that the "xfer" and "xfer2" functions both take three additional parameters (determined by studying the SpiDev source code).

spi.xfer([values], speed_hz, delay_usecs, bits_per_word)

You can set "speed_hz" to 0 and it will default to the maximum supported speed.  "delay_usecs" goes into a 16-bit unsigned integer, so it looks like the longest you can stretch the /CS hold delay by is 65.5ms.  Worth a shot:-

>>> spi.xfer2([0x90,0,0,0,0], 0, 65535)
spi.xfer2([0x90,0,0,0,0], 0, 65535)
[0, 0, 0, 0, 239]
>>> spi.xfer2([0x90,0,0,0,0], 0, 65535)
[0, 0, 0, 0, 239]

It definitely did something: /CS now stays low for 26ms after the transaction is complete.  Its not the 65.5ms we were expecting, though.  

I determined experimentally that the delay used is actually modulo 40,000us.  Any value up to 40,000 works as it should...any value higher than 40,000 has 40,000 subtracted from it.  This is true whether I use "xfer" or "xfer2": I still can't find any difference in behaviour between the two.  

Returning to the SpiDev module source code, the lack of any behavioural difference between "xfer" and "xfer2" isn't surprising: it turns out that both of them actually make exactly the same IOCTL call to the SPI kernel module with a spi_ioc_transfer structure populated in exactly the same way.  That structure does actually contain a member called "cs_change" which is described as:-

@cs_change: True to deselect device before starting the next transfer
...which sounds exactly like it should be the difference between "xfer" and "xfer2".  However, neither method actually sets this structure member either way.  So it looks like the value for this parameter that is passed to the kernel is what ever random value is in memory when the space for the structure is allocated. It seems like it should be easy to fix so I will try modifying the source code to correct this problem.  But not tonight...that's an update for another day.

What I really wanted to do but (apparently) can't is to read continuously from the SPI flash IC.  All I should have to do is send it a "read" command and a start address, and then just keep reading from it in one big, 1,048,576-byte long transaction and it should happily return the entire flash contents in sequence.  This works fine on an Arduino: I set up the "read" operation and then just keep feeding it values (it doesn't matter what I send...its the value that the flash IC returns that I'm interested in) with the /CS pin held low.  However, with "xfer2" not working as it should, there seems to be no way to spread a single SPI bus transaction among multiple method calls.  Even if "xfer2" did work its not ideal.  There is a "readbytes" function which would be more appropriate because it doesn't require me to send it in a list of values to transmit (which will all be ignored anyway).  However, there is no "readbytes2" (working or otherwise) which would allow the /CS to be held low between successive calls.