Tuesday, April 23, 2013

A sphere in binary 11-space

In my discrete math class this week, did an example of a code that encodes three bits to eleven bits and can correct all two-bit errors.   This particular code was not meant to be particularly optimal, but for one particular example I ran with 3,000,000 bits, the number of errors was roughly 1/4 of what was predicted by the probabilities, given that two bit errors can be corrected.  There were 38 failures instead of a predicted 155.   This is no mystery since the packing of spheres in {0,1}^11 wasn't expected to be all that tight, and three bit errors can often be corrected.  

The encoding function is 
         (a, b, c) ----> (a, b, c, a + b, a + c, b + c, a + b + c, a + b, a + c, b + c, a + b + c)

To get an visualize the situation, I create the graph below.   The vertices are some of the points in the code space: the sphere of radius three centered around one of the code words.   The color coding is
  • Yellow:   the code word - I used the zero word, but the space is symmetric everywhere.
  • Blue:   points one unit from the code word
  • Green:  points two units from the code word
  • Brown:  points three units from the code word and further that three units from all other code words.
  • Red:  points three units from the code word but also three units from another code word.
So all but the Red points, if received, will correct to the most likely transmitted word.   Only the Red ones are questionable and there is no most likely correction.

Monday, April 22, 2013

The Economic Impact of Applied Discrete Structures.

I've been starting to collect data to document the economic impact of Applied Discrete Structures.  In a class using our text, the cost to a student ranges from $0, if  he/she uses the pdf, to $30 a hard copy of purchased.   A rough estimate of the percentage students that buy a hard copy is 15%.   Prior to using our text at UMass Lowell, we used a text that cost $160 new, and around $120 used.   So a very conservative estimate of the impact on student costs would be $120 times the number of students enrolled in discrete math classes using our book.  Here are the estimated student savings, also with very conservative estimates for enrollments starting Fall 2011 through the Spring 2013 semester:

UMass Lowell:   300 students have saved a collective $36,000
Other Colleges:   75  students have saved a collective $9,000

That's $45,000 that students have saved in the first couple of years that the book has been available.   We're hoping that with increased exposure on open source textbook websites, we can dramatically increase the impact outside of UMass Lowell.

So far we are listed on the following sites: