Planet Linux Australia

Syndicate content
Planet Linux Australia - http://planet.linux.org.au
Updated: 22 min 2 sec ago

David Rowe: AMBE+2 and MELPe 600 Compared to Codec 2

Sun, 2017-03-26 21:03

Yesterday I was chatting on the #freedv IRC channel, and a good question was asked: how close is Codec 2 to AMBE+2 ? Turns out – reasonably close. I also discovered, much to my surprise, that Codec 2 700C is better than MELPe 600!

Samples

Original AMBE+2 3000 AMBE+ 2400 Codec 2 3200 Codec 2 2400 Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Original MELPe 600 Codec 2 700C Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen Listen

Here are all the samples in one big tar ball.

Discussion

I don’t have a AMBE or MELPe codec handy so I used the samples from the DVSI and DSP Innovations web sites. I passed the original “DAMA” speech samples found on these sites through Codec 2 (codec2-dev SVN revision 3053) at various bit rates. Turns out the DAMA samples were the same for the AMBE and MELPe samples which was handy.

These particular samples are “kind” to codecs – I consistently get good results with them when I test with Codec 2. I’m guessing they also allow other codecs to be favorably demonstrated. During Codec 2 development I make a point of using “pathological” samples such as hts1a, cg_ref, kristoff, mmt1 that tend to break Codec 2. Some samples of AMBE and MELP using my samples on the Codec 2 page.

I usually listen to samples through a laptop speaker, as I figure it’s close to the “use case” of a PTT radio. Small speakers do mask codec artifacts, making them sound better. I also tried a powered loud speaker with the samples above. Through the loudspeaker I can hear AMBE reproducing the pitch fundamental – a bass note that can be heard on some males (e.g. 7), whereas Codec 2 is filtering that out.

I feel AMBE is a little better, Codec 2 is a bit clicky or impulsive (e.g. on sample 1). However it’s not far behind. In a digital radio application, with a small speaker and some acoustic noise about – I feel the casual listener wouldn’t discern much difference. Try replaying these samples through your smart-phone’s browser at an airport and let me know if you can tell them apart!

On the other hand, I think Codec 2 700C sounds better than MELPe 600. Codec 2 700C is more natural. To my ear MELPe has very coarse quantisation of the pitch, hence the “Mr Roboto” sing-song pitch jumps. The 700C level is a bit low, an artifact/bug to do with the post filter. Must fix that some time. As a bonus Codec 2 700C also has lower algorithmic delay, around 40ms compared to MELPe 600’s 90ms.

Curiously, Codec 2 uses just 1 voicing bit which means either voiced or unvoiced excitation in each frame. xMBE’s claim to fame (and indeed MELP) over simpler vocoders is the use of mixed excitation. Some of the spectrum is voiced (regular pitch harmonics), some unvoiced (noise like). This suggests the benefits of mixed excitation need to be re-examined.

I haven’t finished developing Codec 2. In particular Codec 2 700C is very much a “first pass”. We’ve had a big breakthrough this year with 700C and development will continue, with benefits trickling up to other modes.

However the 1300, 2400, 3200 modes have been stable for years and will continue to be supported.

Next Steps

Here is the blog post that kicked off Codec 2 – way back in 2009. Here is a video of my linux.conf.au 2012 Codec 2 talk that explains the motivations, IP issues around codecs, and a little about how Codec 2 works (slides here).

What I spoke about then is still true. Codec patents and license fees are a useless tax on business and stifle innovation. Proprietary codecs borrow as much as 95% of their algorithms from the public domain – which are then sold back to you. I have shown that open source codecs can meet and even exceed the performance of closed source codecs.

Wikipedia suggests that AMBE license fees range from USD$100k to USD$1M. For “one license fee” we can improve Codec 2 so it matches AMBE+2 in quality at 2400 and 3000 bit/s. The results will be released under the LGPL for anyone to use, modify, improve, and inspect at zero cost. Forever.

Maybe we should crowd source such a project?

Command Lines

This is how I generated the Codec 2 wave files:

~/codec2-dev/build_linux//src/c2enc 3200 9.wav - | ~/codec2-dev/build_linux/src/c2dec 3200 - - | sox -t raw -r 8000 -s -2 - 9_codec2_3200.wav

Links

DVSI AMBE sample page

DSP Innovations, MELPe samples. Can anyone provide me with TWELP samples from these guys? I couldn’t find any on the web that includes the input, uncoded source samples.

OpenSTEM: Trying an OpenSTEM unit without a subscription

Sun, 2017-03-26 17:05

We have received quite a few requests for this option, so we’ve made it possible. As we understand it, in many cases an individual teacher wants to try our materials (often on behalf of the school, as a trial) but the teacher has to fund this from their classroom budget, so we appreciate they need to limit their initial outlay.

While purchasing units with an active subscription still works out cheaper (we haven’t changed that pricing), we have tweaked our online store to now also allow the purchase of individual unit bundles, from as little as $49.50 (inc.GST) for the Understanding Our World™ HASS+Science program units. That’s a complete term bundle with teacher handbook, student workbook, assessment guide, model answers and curriculum mapping, as well as all the base resource PDFs needed for that unit! After purchase, the PDF materials can be downloaded from the site (optionally many files together in a ZIP).

We’d love to welcome you as a new customer! From experience we know that you’ll love our materials. The exact pricing difference (between subscription and non-subscription) depends on the type of bundle (term unit, year bundle, or multi-year bundle) and is indicated per item.

Try OpenSTEM today! Browse our teacher unit bundles (Foundation Year to Year 6).

This includes units for Digital Technologies, the Ginger Beer Science project, as well as for our popular Understanding Our World™ HASS+Science program.

James Morris: Linux Security Summit 2017: CFP Announcement

Sat, 2017-03-25 01:01

The 2017 Linux Security Summit CFP (Call for Participation) is now open!

See the announcement here.

The summit this year will be held in Los Angeles, USA on 14-15 September. It will be co-located with the Open Source Summit (formerly LinuxCon), and the Linux Plumbers Conference. We’ll follow essentially the same format as the 2016 event (you can find the recap here).

The CFP closes on June 5th, 2017.

sthbrx - a POWER technical blog: Erasure Coding for Programmers, Part 2

Fri, 2017-03-24 10:08

We left part 1 having explored GF(2^8) and RAID 6, and asking the question "what does all this have to do with Erasure Codes?"

Basically, the thinking goes "RAID 6 is cool, but what if, instead of two parity disks, we had an arbitrary number of parity disks?"

How would we do that? Well, let's introduce our new best friend: Coding Theory!

Say we want to transmit some data across an error-prone medium. We don't know where the errors might occur, so we add some extra information to allow us to detect and possibly correct for errors. This is a code. Codes are a largish field of engineering, but rather than show off my knowledge about systematic linear block codes, let's press on.

Today, our error-prone medium is an array of inexpensive disks. Now we make this really nice assumption about disks, namely that they are either perfectly reliable or completely missing. In other words, we consider that a disk will either be present or 'erased'. We come up with 'erasure codes' that are able to reconstruct data when it is known to be missing. (This is a slightly different problem to being able to verify and correct data that might or might not be subtly corrupted. Disks also have to deal with this problem, but it is not something erasure codes address!)

The particular code we use is a Reed-Solomon code. The specific details are unimportant, but there's a really good graphical outline of the broad concepts in sections 1 and 3 of the Jerasure paper/manual. (Don't go on to section 4.)

That should give you some background on how this works at a pretty basic mathematical level. Implementation is a matter of mapping that maths (matrix multiplication) onto hardware primitives, and making it go fast.

Scope

I'm deliberately not covering some pretty vast areas of what would be required to write your own erasure coding library from scratch. I'm not going to talk about how to compose the matricies, how to invert them, or anything like that. I'm not sure how that would be a helpful exercise - ISA-L and jerasure already exist and do that for you.

What I want to cover is an efficient implementation of the some algorithms, once you have the matricies nailed down.

I'm also going to assume your library already provides a generic multiplication function in GF(2^8). That's required to construct the matrices, so it's a pretty safe assumption.

The beginnings of an API

Let's make this a bit more concrete.

This will be heavily based on the ISA-L API but you probably want to plug into ISA-L anyway, so that shouldn't be a problem.

What I want to do is build up from very basic algorithmic components into something useful.

The first thing we want to do is to be able to is Galois Field multiplication of an entire region of bytes by an arbitrary constant.

We basically want gf_vect_mul(size_t len, <something representing the constant>, unsigned char * src, unsigned char * dest)

Simple and slow approach

The simplest way is to do something like this:

void gf_vect_mul_simple(size_t len, unsigned char c, unsigned char * src, unsigned char * dest) { size_t i; for (i=0; i<len; i++) { dest[i] = gf_mul(c, src[i]); } }

That does multiplication element by element using the library's supplied gf_mul function, which - as the name suggests - does GF(2^8) multiplication of a scalar by a scalar.

This works. The problem is that it is very, painfully, slow - in the order of a few hundred megabytes per second.

Going faster

How can we make this faster?

There are a few things we can try: if you want to explore a whole range of different ways to do this, check out the gf-complete project. I'm going to assume we want to skip right to the end and know what is the fastest we've found.

Cast your mind back to the RAID 6 paper (PDF). I talked about in part 1. That had a way of doing an efficient multiplication in GF(2^8) using vector instructions.

To refresh your memory, we split the multiplication into two parts - low bits and high bits, looked them up separately in a lookup table, and joined them with XOR. We then discovered that on modern Power chips, we could do that in one instruction with vpermxor.

So, a very simple way to do this would be:

  • generate the table for a
  • for each 16-byte chunk of our input:
    • load the input
    • do the vpermxor with the table
    • save it out

Generating the tables is reasonably straight-forward, in theory. Recall that the tables are a * {{00},{01},...,{0f}} and a * {{00},{10},..,{f0}} - a couple of loops in C will generate them without difficulty. ISA-L has a function to do this, as does gf-complete in split-table mode, so I won't repeat them here.

So, let's recast our function to take the tables as an input rather than the constant a. Assume we're provided the two tables concatenated into one 32-byte chunk. That would give us:

void gf_vect_mul_v2(size_t len, unsigned char * table, unsigned char * src, unsigned char * dest)

Here's how you would do it in C:

void gf_vect_mul_v2(size_t len, unsigned char * table, unsigned char * src, unsigned char * dest) { vector unsigned char tbl1, tbl2, in, out; size_t i; /* Assume table, src, dest are aligned and len is a multiple of 16 */ tbl1 = vec_ld(16, table); tbl2 = vec_ld(0, table); for (i=0; i<len; i+=16) { in = vec_ld(i, (unsigned char *)src); __asm__("vpermxor %0, %1, %2, %3" : "=v"(out) : "v"(tbl1), "v"(tbl2), "v"(in) vec_st(out, i, (unsigned char *)dest); } }

There's a few quirks to iron out - making sure the table is laid out in the vector register in the way you expect, etc, but that generally works and is quite fast - my Power 8 VM does about 17-18 GB/s with non-cache-contained data with this implementation.

We can go a bit faster by doing larger chunks at a time:

for (i=0; i<vlen; i+=64) { in1 = vec_ld(i, (unsigned char *)src); in2 = vec_ld(i+16, (unsigned char *)src); in3 = vec_ld(i+32, (unsigned char *)src); in4 = vec_ld(i+48, (unsigned char *)src); __asm__("vpermxor %0, %1, %2, %3" : "=v"(out1) : "v"(tbl1), "v"(tbl2), "v"(in1)); __asm__("vpermxor %0, %1, %2, %3" : "=v"(out2) : "v"(tbl1), "v"(tbl2), "v"(in2)); __asm__("vpermxor %0, %1, %2, %3" : "=v"(out3) : "v"(tbl1), "v"(tbl2), "v"(in3)); __asm__("vpermxor %0, %1, %2, %3" : "=v"(out4) : "v"(tbl1), "v"(tbl2), "v"(in4)); vec_st(out1, i, (unsigned char *)dest); vec_st(out2, i+16, (unsigned char *)dest); vec_st(out3, i+32, (unsigned char *)dest); vec_st(out4, i+48, (unsigned char *)dest); }

This goes at about 23.5 GB/s.

We can go one step further and do the core loop in assembler - that means we control the instruction layout and so on. I tried this: it turns out that for the basic vector multiply loop, if we turn off ASLR and pin to a particular CPU, we can see a improvement of a few percent (and a decrease in variability) over C code.

Building from vector multiplication

Once you're comfortable with the core vector multiplication, you can start to build more interesting routines.

A particularly useful one on Power turned out to be the multiply and add routine: like gf_vect_mul, except that rather than overwriting the output, it loads the output and xors the product in. This is a simple extension of the gf_vect_mul function so is left as an exercise to the reader.

The next step would be to start building erasure coding proper. Recall that to get an element of our output, we take a dot product: we take the corresponding input element of each disk, multiply it with the corresponding GF(2^8) coding matrix element and sum all those products. So all we need now is a dot product algorithm.

One approach is the conventional dot product:

  • for each element
    • zero accumulator
    • for each source
      • load input[source][element]
      • do GF(2^8) multiplication
      • xor into accumulator
    • save accumulator to output[element]

The other approach is multiply and add:

  • for each source
    • for each element
      • load input[source][element]
      • do GF(2^8) multiplication
      • load output[element]
      • xor in product
      • save output[element]

The dot product approach has the advantage of fewer writes. The multiply and add approach has the advantage of better cache/prefetch performance. The approach you ultimately go with will probably depend on the characteristics of your machine and the length of data you are dealing with.

For what it's worth, ISA-L ships with only the first approach in x86 assembler, and Jerasure leans heavily towards the second approach.

Once you have a vector dot product sorted, you can build a full erasure coding setup: build your tables with your library, then do a dot product to generate each of your outputs!

In ISA-L, this is implemented something like this:

/* * ec_encode_data_simple(length of each data input, number of inputs, * number of outputs, pre-generated GF(2^8) tables, * input data pointers, output code pointers) */ void ec_encode_data_simple(int len, int k, int rows, unsigned char *g_tbls, unsigned char **data, unsigned char **coding) { while (rows) { gf_vect_dot_prod(len, k, g_tbls, data, *coding); g_tbls += k * 32; coding++; rows--; } } Going faster still

Eagle eyed readers will notice that however we generate an output, we have to read all the input elements. This means that if we're doing a code with 10 data disks and 4 coding disks, we have to read each of the 10 inputs 4 times.

We could do better if we could calculate multiple outputs for each pass through the inputs. This is a little fiddly to implement, but does lead to a speed improvement.

ISA-L is an excellent example here. Intel goes up to 6 outputs at once: the number of outputs you can do is only limited by how many vector registers you have to put the various operands and results in.

Tips and tricks
  • Benchmarking is tricky. I do the following on a bare-metal, idle machine, with ASLR off and pinned to an arbitrary hardware thread. (Code is for the fish shell)

    for x in (seq 1 50) setarch ppc64le -R taskset -c 24 erasure_code/gf_vect_mul_perf end | awk '/MB/ {sum+=$13} END {print sum/50, "MB/s"}'
  • Debugging is tricky; the more you can do in C and the less you do in assembly, the easier your life will be.

  • Vector code is notoriously alignment-sensitive - if you can't figure out why something is wrong, check alignment. (Pro-tip: ISA-L does not guarantee the alignment of the gftbls parameter, and many of the tests supply an unaligned table from the stack. For testing __attribute__((aligned(16))) is your friend!)

  • Related: GCC is moving towards assignment over vector intrinsics, at least on Power:

    vector unsigned char a; unsigned char * data; // good, also handles word-aligned data with VSX a = *(vector unsigned char *)data; // bad, requires special handling of non-16-byte aligned data a = vec_ld(0, (unsigned char *) data);
Conclusion

Hopefully by this point you're equipped to figure out how your erasure coding library of choice works, and write your own optimised implementation (or maintain an implementation written by someone else).

I've referred to a number of resources throughout this series:

If you want to go deeper, I also read the following and found them quite helpful in understanding Galois Fields and Reed-Solomon coding:

For a more rigorous mathematical approach to rings and fields, a university mathematics course may be of interest. For more on coding theory, a university course in electronics engineering may be helpful.

OpenSTEM: Guess the Artefact!

Thu, 2017-03-23 15:04

Today we are announcing a new challenge for our readers – Guess the Artefact! We post pictures of an artefact and you can guess what it is. The text will slowly reveal the answer, through a process of examination and deduction – see if you can guess what it is, before the end. We are starting this challenge with an item from our year 6 Archaeological Dig workshop. Year 6 (unit 6.3) students concentrate on Federation in their Australian History segment – so that’s your first clue! Study the image and then start reading the text below.

Our first question is what is it? Study the image and see if you can work out what it might be – it’s an dirty, damaged piece of paper. It seems to be old. Does it have a date? Ah yes, there are 3 dates – 23, 24 and 25 October, 1889, so we deduce that it must be old, dating to the end of the 19th century. We will file the exact date for later consideration. We also note references to railways. The layout of the information suggests a train ticket. So we have a late 19th century train ticket!

Now why do we have this train ticket and whose train ticket might it have been? The ticket is First Class, so this is someone who could afford to travel in style. Where were they going? The railways mentioned are Queensland Railways, Great Northern Railway, New South Wales Railways and the stops are Brisbane, Wallangara, Tenterfield and Sydney. Now we need to do some research. Queensland Railways and New South Wales Railways seem self-evident, but what is Great Northern Railway? A brief hunt reveals several possible candidates: 1) a contemporary rail operator in Victoria; 2) a line in Queensland connecting Mt Isa and Townsville and 3) an old, now unused railway in New South Wales. We can reject option 1) immediately. Option 2) is the right state, but the towns seem unrelated. That leaves option 3), which seems most likely. Looking into the NSW option in more detail we note that it ran between Sydney and Brisbane, with a stop at Wallangara to change gauge – Bingo!

Wallangara Railway Station

More research reveals that the line reached Wallangara in 1888, the year before this ticket was issued. Only after 1888 was it possible to travel from Brisbane to Sydney by rail, albeit with a compulsory stop at Wallangara. We note also that the ticket contains a meal voucher for dinner at the Railway Refreshment Rooms in Wallangara. Presumably passengers overnighted in Wallangara before continuing on to Sydney on a different train and rail gauge. Checking the dates on the ticket, we can see evidence of an overnight stop, as the next leg continues from Wallangara on the next day (24 Oct 1889). However, next we come to some important information. From Wallangara, the next leg of the journey represented by this ticket was only as far as Tenterfield. Looking on a map, we note that Tenterfield is only about 25 km away – hardly a day’s train ride, more like an hour or two at the most (steam trains averaged about 24 km/hr at the time). From this we deduce that the ticket holder wanted to stop at Tenterfield and continue their journey on the next day.

We know that we’re studying Australian Federation history, so the name Tenterfield should start to a ring a bell – what happened in Tenterfield in 1889 that was relevant to Australian Federation history? The answer, of course, is that Henry Parkes delivered his Tenterfield Oration there, and the date? 24 October, 1889! If we look into the background, we quickly discover that Henry Parkes was on his way from Brisbane back to Sydney, when he stopped in Tenterfield. He had been seeking support for Federation from the government of the colony of Queensland. He broke his journey in Tenterfield, a town representative of those towns closer to the capital of another colony than their own, which would benefit from the free trade arrangements flowing from Federation. Parkes even discussed the issue of different rail gauges as something that would be solved by Federation! We can therefore surmise that this ticket may well be the ticket of Henry Parkes, documenting his journey from Brisbane to Sydney in October, 1889, during which he stopped and delivered the Tenterfield Oration!

This artefact is therefore relevant as a source for anyone studying Federation history – as well as giving us a more personal insight into the travels of Henry Parkes in 1889, it allows us to consider aspects of life at the time:

  • the building of railway connections across Australia, in a time before motor cars were in regular use;
  • the issue of different size railway gauges in the different colonies and what practical challenges that posed for a long distance rail network;
  • the ways in which people travelled and the speed with which they could cross large distances;
  • what rail connections would have meant for small, rural towns, to mention just a few.
  • Why might the railway companies have provided meal vouchers?

These are all sidelines of inquiry, which students may be interested to pursue, and which might help them to engage with the subject matter in more detail.

In our Archaeological Dig Workshops, we not only engage students in the processes and physical activities of the dig, but we provide opportunities for them to use the artefacts to practise deduction, reasoning and research – true inquiry-based learning, imitating real-world processes and far more engaging and empowering than more traditional bookwork.

Linux Users of Victoria (LUV) Announce: LUV Main April 2017 Meeting: SageMath / Simultaneous multithreading

Wed, 2017-03-22 23:02
Start: Apr 4 2017 18:30 End: Apr 4 2017 20:30 Start: Apr 4 2017 18:30 End: Apr 4 2017 20:30 Location:  The Dan O'Connell Hotel, 225 Canning Street, Carlton VIC 3053 Link:  http://luv.asn.au/meetings/map

PLEASE NOTE NEW LOCATION

Tuesday, April 4, 2017
6:30 PM to 8:30 PM
The Dan O'Connell Hotel
225 Canning Street, Carlton VIC 3053

Speakers:

• Adetokunbo "Xero" Arogbonlo, SageMath
• Stewart Smith, Simultaneous multithreading

The Dan O'Connell Hotel, 225 Canning Street, Carlton VIC 3053

Food and drinks will be available on premises.

Before and/or after each meeting those who are interested are welcome to join other members for dinner.

Linux Users of Victoria Inc., is an incorporated association, registration number A0040056C.

April 4, 2017 - 18:30

read more

Linux Users of Victoria (LUV) Announce: LUV Beginners April Meeting: TBD

Wed, 2017-03-22 23:02
Start: Apr 15 2017 12:30 End: Apr 15 2017 16:30 Start: Apr 15 2017 12:30 End: Apr 15 2017 16:30 Location:  Infoxchange, 33 Elizabeth St. Richmond Link:  http://luv.asn.au/meetings/map

Meeting topic to be announced.

There will also be the usual casual hands-on workshop, Linux installation, configuration and assistance and advice. Bring your laptop if you need help with a particular issue. This will now occur BEFORE the talks from 12:30 to 14:00. The talks will commence at 14:00 (2pm) so there is time for people to have lunch nearby.

The meeting will be held at Infoxchange, 33 Elizabeth St. Richmond 3121 (enter via the garage on Jonas St.) Late arrivals, please call (0421) 775 358 for access to the venue.

LUV would like to acknowledge Infoxchange for the venue.

Linux Users of Victoria Inc., is an incorporated association, registration number A0040056C.

April 15, 2017 - 12:30

Gabriel Noronha: Flir ONE Issues

Wed, 2017-03-22 17:03

FLIR ONE for iOS or Android with solid orange power light

Troubleshooting steps when the FLIR ONE has a solid red/orange power light that will not turn to blinking green:

  • Perform a hard reset on the FLIR ONE by holding the power button down for 30 seconds.
  • Let the battery drain overnight and try charging it again (with another charger if possible) for a whole hour.

Binh Nguyen: Life in Brazil, Random Stuff, and More

Mon, 2017-03-20 20:36
- history seems reminiscent of other Latin American nations. Mix of European colonisation and local tribes. Was obviously used for it's natural resources but it's clear that it's economy has diversified since then. That said, clear issues with corruption and wealth inequality brazil history Brazil export treemap by product (2014) from Harvard Atlas of Economic Complexity When the Portuguese

Binh Nguyen: Pre-Cogs and Prophets 10, Random Stuff, and More

Mon, 2017-03-20 19:44
- a clear continuation of my other posts on pre-cogs/prophets: http://dtbnguyen.blogspot.com/2017/03/prophetsgenesisterraforming-mars-seek.html http://dtbnguyen.blogspot.com/2017/03/prophetspre-cogsstargate-program-8.html http://dtbnguyen.blogspot.com/2017/02/life-in-india-prophetspre-cogsstargate_82.html http://dtbnguyen.blogspot.com/2017/02/life-in-iran-examining-prophetspre-cogs.html

OpenSTEM: This Week in HASS – term 1, week 8

Mon, 2017-03-20 11:04

As we move into the final weeks of term, and the Easter holiday draws closer, our youngest students are looking at different kinds of celebrations in Australia. Students in years 1 to 3 are looking at their global family and students in years 3 to 6 are chasing Aunt Madge around the world, being introduced to Eratosthenes and examining Shadows and Light.

Foundation to Year 3

Our standalone Foundation/Prep students (Unit F.1) are studying celebrations in Australia and thinking about which is their favourite. It may well be Easter with its bunnies and chocolate eggs, which lies just around the corner now! They also get a chance to consider whether we should add any extra celebrations into our calendar in Australia. Those Foundation/Prep students in an integrated class with Year 1 students (Unit F.5), as well as Year 1 (Unit 1.1), 2 (Unit 2.1) and 3 (Unit 3.1) students are investigating where they, and other family members, were born and finding these places on the world map. Students are also examining features of the world map – including the different continents, North and South Poles, the equator and the oceans. Students also get a chance to undertake the Aunt Madge’s Suitcase Activity, in which they follow Aunt Madge around the world, learning about different countries and landmarks, as they go. Aunt Madge’s Suitcase is extremely popular with students of all ages – as it can easily be adapted to cover material at different depths. The activity encourages students to interact with the world map, whilst learning to recognise major natural and cultural landmarks in Australia and around the world.

Years 3 to 6 Aunt Madge

Students in Year 3 (Unit 3.5), who are integrated with Year 4, as well as the Year 4 (Unit 4.1), 5 (Unit 5.1) and 6 (Unit 6.1) students, have moved on to a new set of activities this week. The older students approach the Aunt Madge’s Suitcase Activity in more depth, deriving what items Aunt Madge has packed in her suitcase to match the different climates which she is visiting, as well as delving into each landmark visited in more detail. These landmarks are both natural and cultural and, although several are in Australia, examples are given from around the world, allowing teachers to choose their particular focus each time the activity is undertaken. As well as following Aunt Madge, students are introduced to Eratosthenes. Known as the ‘Father of Geography’, Eratosthenes also calculated the circumference of the Earth. There is an option for teachers to overlap with parts of the Maths curriculum here. Eratosthenes also studied the planets and used shadows and sunlight for his calculations, which provides the link for the Science activities – Shadows and Light, Sundials and Planets of the Solar System.

Next week is the last week of our first term units. By now students have completed the bulk of their work for the term, and teachers are able to assess most of the HASS areas already.

 

sthbrx - a POWER technical blog: Erasure Coding for Programmers, Part 1

Mon, 2017-03-20 10:43

Erasure coding is an increasingly popular storage technology - allowing the same level of fault tolerance as replication with a significantly reduced storage footprint.

Increasingly, erasure coding is available 'out of the box' on storage solutions such as Ceph and OpenStack Swift. Normally, you'd just pull in a library like ISA-L or jerasure, and set some config options, and you'd be done.

This post is not about that. This post is about how I went from knowing nothing about erasure coding to writing POWER optimised routines to make it go fast. (These are in the process of being polished for upstream at the moment.) If you want to understand how erasure coding works under the hood - and in particular if you're interested in writing optimised routines to make it run quickly in your platform - this is for you.

What are erasure codes anyway?

I think the easiest way to begin thinking about erasure codes is "RAID 6 on steroids". RAID 6 allows you to have up to 255 data disks and 2 parity disks (called P and Q), thus allowing you to tolerate the failure of up to 2 arbitrary disks without data loss.

Erasure codes allow you to have k data disks and m 'parity' or coding disks. You then have a total of m + k disks, and you can tolerate the failure of up to m without losing data.

The downside of erasure coding is that computing what to put on those parity disks is CPU intensive. Lets look at what we put on them.

RAID 6

RAID 6 is the easiest way to get started on understanding erasure codes for a number of reasons. H Peter Anvin's paper on RAID 6 in the Linux kernel is an excellent start, but does dive in a bit quickly to the underlying mathematics. So before reading that, read on!

Rings and Fields

As programmers we're pretty comfortable with modular arithmetic - the idea that if you have:

unsigned char a = 255; a++;

the new value of a will be 0, not 256.

This is an example of an algebraic structure called a ring.

Rings obey certain laws. For our purposes, we'll consider the following incomplete and somewhat simplified list:

  • There is an addition operation.
  • There is an additive identity (normally called 0), such that 'a + 0 = a'.
  • Every element has an additive inverse, that is, for every element 'a', there is an element -a such that 'a + (-a) = 0'
  • There is a multiplication operation.
  • There is a multiplicative identity (normally called 1), such that 'a * 1 = a'.

These operations aren't necessarily addition or multiplication as we might expect from the integers or real numbers. For example, in our modular arithmetic example, we have 'wrap around'. (There are also certain rules the addition and multiplication rules must satisfy - we are glossing over them here.)

One thing a ring doesn't have a 'multiplicative inverse'. The multiplicative inverse of some non-zero element of the ring (call it a), is the value b such that a * b = 1. (Often instead of b we write 'a^-1', but that looks bad in plain text, so we shall stick to b for now.)

We do have some inverses in 'mod 256': the inverse of 3 is 171 as 3 * 171 = 513, and 513 = 1 mod 256, but there is no b such that 2 * b = 1 mod 256.

If every non-zero element of our ring had a multiplicative inverse, we would have what is called a field.

Now, let's look at a the integers modulo 2, that is, 0 and 1.

We have this for addition:

+ 0 1 0 0 1 1 1 0

Eagle-eyed readers will notice that this is the same as XOR.

For multiplication:

* 0 1 0 0 0 1 0 1

As we said, a field is a ring where every non-zero element has a multiplicative inverse. As we can see, the integers modulo 2 shown above is a field: it's a ring, and 1 is its own multiplicative inverse.

So this is all well and good, but you can't really do very much in a field with 2 elements. This is sad, so we make bigger fields. For this application, we consider the Galois Field with 256 elements - GF(2^8). This field has some surprising and useful properties.

Remember how we said that integers modulo 256 weren't a field because they didn't have multiplicative inverses? I also just said that GF(2^8) also has 256 elements, but is a field - i.e., it does have inverses! How does that work?

Consider an element in GF(2^8). There are 2 ways to look at an element in GF(2^8). The first is to consider it as an 8-bit number. So, for example, let's take 100. We can express that as as an 8 bit binary number: 0b01100100.

We can write that more explicitly as a sum of powers of 2:

0 * 2^7 + 1 * 2^6 + 1 * 2^5 + 0 * 2^4 + 0 * 2^3 + 1 * 2^2 + 0 * 2 + 0 * 1 = 2^6 + 2^5 + 2^2

Now the other way we can look at elements in GF(2^8) is to replace the '2's with 'x's, and consider them as polynomials. Each of our bits then represents the coefficient of a term of a polynomial, that is:

0 x^7 + 1 x^6 + 1 x^5 + 0 x^4 + 0 x^3 + 1 x^2 + 0 x + 0 * 1

or more simply

x^6 + x^5 + x^2

Now, and this is important: each of the coefficients are elements of the integers modulo 2: x + x = 2x = 0 as 2 mod 2 = 0. There is no concept of 'carrying' in this addition.

Let's try: what's 100 + 79 in GF(2^8)?

100 = 0b01100100 => x^6 + x^5 + x^2 79 = 0b01001111 => x^6 + x^3 + x^2 + x + 1 100 + 79 => 0 + x^5 + x^3 + 0 + x + 1 = 0b00101011 = 43

So, 100 + 79 = 43 in GF(2^8)

You may notice we could have done that much more efficiently: we can add numbers in GF(2^8) by just XORing their binary representations together. Subtraction, amusingly, is the same as addition: 0 + x = x = 0 - x, as -1 is congruent to 1 modulo 2.

So at this point you might be wanting to explore a few additions yourself. Fortuantely there's a lovely tool that will allow you to do that:

sudo apt install gf-complete-tools gf_add $A $B 8

This will give you A + B in GF(2^8).

> gf_add 100 79 8 43

Excellent!

So, hold on to your hats, as this is where things get really weird. In modular arithmetic example, we considered the elements of our ring to be numbers, and we performed our addition and multiplication modulo 256. In GF(2^8), we consider our elements as polynomials and we perform our addition and multiplication modulo a polynomial. There is one conventional polynomial used in applications:

0x11d => 0b1 0001 1101 => x^8 + x^4 + x^3 + x^2 + 1

It is possible to use other polynomials if they satisfy particular requirements, but for our applications we don't need to worry as we will always use 0x11d. I am not going to attempt to explain anything about this polynomial - take it as an article of faith.

So when we multiply two numbers, we multiply their polynomial representations. Then, to find out what that is modulo 0x11d, we do polynomial long division by 0x11d, and take the remainder.

Some examples will help.

Let's multiply 100 by 3.

100 = 0b01100100 => x^6 + x^5 + x^2 3 = 0b00000011 => x + 1 (x^6 + x^5 + x^2)(x + 1) = x^7 + x^6 + x^3 + x^6 + x^5 + x^2 = x^7 + x^5 + x^3 + x^2

Notice that some of the terms have disappeared: x^6 + x^6 = 0.

The degree (the largest power of a term) is 7. 7 is less than the degree of 0x11d, which is 8, so we don't need to do anything: the remainder modulo 0x11d is simply x^7 + x^5 + x^3 + x^2.

In binary form, that is 0b10101100 = 172, so 100 * 3 = 172 in GF(2^8).

Fortunately gf-complete-tools also allows us to check multiplications:

> gf_mult 100 3 8 172

Excellent!

Now let's see what happens if we multiply by a larger number. Let's multiply 100 by 5.

100 = 0b01100100 => x^6 + x^5 + x^2 5 = 0b00000101 => x^2 + 1 (x^6 + x^5 + x^2)(x^2 + 1) = x^8 + x^7 + x^4 + x^6 + x^5 + x^2 = x^8 + x^7 + x^6 + x^5 + x^4 + x^2

Here we have an x^8 term, so we have a degree of 8. This means will get a different remainder when we divide by our polynomial. We do this with polynomial long division, which you will hopefully remember if you did some solid algebra in high school.

1 --------------------------------------------- x^8 + x^4 + x^3 + x^2 + 1 | x^8 + x^7 + x^6 + x^5 + x^4 + x^2 - x^8 + x^4 + x^3 + x^2 + 1 ------------------------------------------- = x^7 + x^6 + x^5 + x^3 + 1

So we have that our original polynomial (x^8 + x^4 + x^3 + x^2 + 1) is congruent to (x^7 + x^6 + x^5 + x^3 + 1) modulo the polynomial 0x11d. Looking at the binary representation of that new polynomial, we have 0b11101001 = 233.

Sure enough:

> gf_mult 100 5 8 233

Just to solidify the polynomial long division a bit, let's try a slightly larger example, 100 * 9:

100 = 0b01100100 => x^6 + x^5 + x^2 9 = 0b00001001 => x^3 + 1 (x^6 + x^5 + x^2)(x^3 + 1) = x^9 + x^8 + x^5 + x^6 + x^5 + x^2 = x^9 + x^8 + x^6 + x^2

Doing long division to reduce our result:

x ----------------------------------- x^8 + x^4 + x^3 + x^2 + 1 | x^9 + x^8 + x^6 + x^2 - x^9 + x^5 + x^4 + x^3 + x ------------------------------------------------- = x^8 + x^6 + x^5 + x^4 + x^3 + x^2 + x

We still have a polynomial of degree 8, so we can do another step:

x + 1 ----------------------------------- x^8 + x^4 + x^3 + x^2 + 1 | x^9 + x^8 + x^6 + x^2 - x^9 + x^5 + x^4 + x^3 + x ------------------------------------------------- = x^8 + x^6 + x^5 + x^4 + x^3 + x^2 + x - x^8 + x^4 + x^3 + x^2 + 1 ----------------------------------------------- = x^6 + x^5 + x + 1

We now have a polynomial of degree less than 8 that is congruent to our original polynomial modulo 0x11d, and the binary form is 0x01100011 = 99.

> gf_mult 100 9 8 99

This process can be done more efficiently, of course - but understanding what is going on will make you much more comfortable with what is going on!

I will not try to convince you that all multiplicative inverses exist in this magic shadow land of GF(2^8), but it's important for the rest of the algorithms to work that they do exist. Trust me on this.

Back to RAID 6

Equipped with this knowledge, you are ready to take on RAID6 in the kernel (PDF) sections 1 - 2.

Pause when you get to section 3 - this snippet is a bit magic and benefits from some explanation:

Multiplication by {02} for a single byte can be implemeted using the C code:

uint8_t c, cc; cc = (c << 1) ^ ((c & 0x80) ? 0x1d : 0);

How does this work? Well:

Say you have a binary number 0bNMMM MMMM. Mutiplication by 2 gives you 0bNMMMMMMM0, which is 9 bits. Now, there are two cases to consider.

If your leading bit (N) is 0, your product doesn't have an x^8 term, so we don't need to reduce it modulo the irreducible polynomial.

If your leading bit is 1 however, your product is x^8 + something, which does need to be reduced. Fortunately, because we took an 8 bit number and multiplied it by 2, the largest term is x^8, so we only need to reduce it once. So we xor our number with our polynomial to subtract it.

We implement this by letting the top bit overflow out and then xoring the lower 8 bits with the low 8 bits of the polynomial (0x1d)

So, back to the original statement:

(c << 1) ^ ((c & 0x80) ? 0x1d : 0) | | | | > multiply by 2 | | | | | > is the high bit set - will the product have an x^8 term? | | > if so, reduce by the polynomial | > otherwise, leave alone

Hopefully that makes sense.

Key points

It's critical you understand the section on Altivec (the vperm stuff), so let's cover it in a bit more detail.

Say you want to do A * V, where A is a constant and V is an 8-bit variable. We can express V as V_a + V_b, where V_a is the top 4 bits of V, and V_b is the bottom 4 bits. A * V = A * V_a + A * V_b

We can then make lookup tables for multiplication by A.

If we did this in the most obvious way, we would need a 256 entry lookup table. But by splitting things into the top and bottom halves, we can reduce that to two 16 entry tables. For example, say A = 02.

V_a A * V_a 00 00 01 02 02 04 ... ... 0f 1e V_b A * V_b 00 00 10 20 20 40 ... ... f0 fd

We then use vperm to look up entries in these tables and vxor to combine our results.

So - and this is a key point - for each A value we wish to multiply by, we need to generate a new lookup table.

So if we wanted A = 03:

V_a A * V_a 00 00 01 03 02 06 ... ... 0f 11 V_b A * V_b 00 00 10 30 20 60 ... ... f0 0d

One final thing is that Power8 adds a vpermxor instruction, so we can reduce the entire 4 instruction sequence in the paper:

vsrb v1, v0, v14 vperm v2, v12, v12, v0 vperm v1, v13, v13, v1 vxor v1, v2, v1

to 1 vpermxor:

vpermxor v1, v12, v13, v0

Isn't POWER grand?

OK, but how does this relate to erasure codes?

I'm glad you asked.

Galois Field arithmetic, and its application in RAID 6 is the basis for erasure coding. (It's also the basis for CRCs - two for the price of one!)

But, that's all to come in part 2, which will definitely be published before 7 April!

Many thanks to Sarah Axtens who reviewed the mathematical content of this post and suggested significant improvements. All errors and gross oversimplifications remain my own. Thanks also to the OzLabs crew for their feedback and comments.

David Rowe: Codec 2 700C and Short LDPC Codes

Sat, 2017-03-18 15:03

In the last blog post I evaluated FreeDV 700C over the air. This week I’ve been simulating the use of short LDPC FEC codes with Codec 2 700C over AWGN and HF channels.

In my HF Digital Voice work to date I have shied away from FEC:

  1. We didn’t have the bandwidth for the extra bits required for FEC.
  2. Modern, high performance codes tend to have large block sizes (1000’s of bits) which leads to large latency (several seconds) when applied to low bit rate speech.
  3. The error rates we are interested in (e.g. 10% raw, 1% after FEC decoder) are unusual – many codes don’t work well.

However with Codec 2 pushed down to 700 bit/s we now have enough bandwidth for a rate 1/2 code inside a standard 2kHz SSB channel. Over coffee a few weeks ago, Bill VK5DSP offered to develop some short LDPC codes for me specifically for this application. He sent me an Octave simulation of rate 1/2 and 2/3 codes of length 112 and 56 bits. Codec 2 700C has 28 bit frames so this corresponds to 4 or 2 Codec 2 700C frames, which would introduce a latencies of between 80 to 160ms – quite acceptable for Push To Talk (PTT) radio.

I re-factored Bill’s simulation code to produce ldpc_short.m. This measures BER and PER for Bill’s short LDPC codes, and also plots curves for theoretical, HF multipath channels, a Golay (24,12) code, and the current diversity scheme used in FreeDV 700C.

To check my results I compared the Golay BER and ideal HF multipath (Rayleigh Fading) channel curves to other peoples work. Always a good idea to spot check a few values and make sure they are sensible. I took a simple approach to get results in a reasonable amount of coding time (about 1 day of work in this case). This simulation runs at the symbol rate, and assumes ideal synchronisation. My other modem work (i.e experience) lets me move back and forth between this sort of simulation and real world modems, for example accounting for synchronisation losses.

Error Distribution and Packet Error Rate

I had an idea that Packet Error Rate (PER) might be important. Without FEC, bit errors are scattered randomly about. At our target 1% BER, many frames will have 1 or 2 bit errors. As discussed in the last post Codec 2 700C is sensitive to bit errors as “every bit counts”. For example one bit error in the Vector Quantiser (VQ) index (a big look up table) can throw the speech spectrum right off.

However a LDPC decoder will tend to correct all errors in a codeword, or “die trying” (i.e. fail badly). So an average output BER of say 1% will consist of a bunch of perfect frames, plus a completely trashed one every now and again. Digital voice works better with this style of error pattern than a few random errors in each codec packet. So for a given BER, a system that delivers a lower PER is better for our application. I’ve guesstimated a 10% PER target for intelligible low bit rate speech. Lets see how that works out…..

Results

Here are the BER and PER curves for an AWGN channel:

Here are the same curves for HF (multipath fading) channel:

I’ve included a Golay (24,12) block code (hard decision) and uncoded PSK for comparison to the AWGN curves, and the diversity system on the HF curves. The HF channel is modelled as two paths with 1Hz Doppler spread and a 1ms delay.

The best LDPC code reaches the 1% BER/10% PER point at 2dB Eb/No (AWGN) and 6dB (HF multipath). Comparing BER, the coding gain is 2.5 and 3dB (AWGN and HF). Comparing PER, the coding gain is 3 and 5dB (AWGN and HF).

Here is a plot of the error pattern over time using the LDPC code on a HF channel at Eb/No of 6dB:

Note the errors are confined to short bursts – isolated packets where the decoder fails. Even though the average BER is 1%, most of the speech is error free. This is a very nice error distribution for digital speech.

Speech Samples

Here are some speech samples, comparing the current diversity scheme used for FreeDV 700C to LDPC, for AWGN and LDPC channels. These were simulated by extracting the error pattern from the simulation then inserting these errors in a Codec 2 700C bit stream (see command lines section below).

AWGN Eb/No 2dB Diversity LDPC HF Eb/No 6dB Diversity LDPC

Next Steps

These results are very encouraging and suggest a gain of 2 to 5dB over FreeDV 700C, and better error distribution (lower PER). Next step is to develop FreeDV 700D – a real world implementation using the 112 data-bit rate 1/2 LDPC code. This will require 4 frames of buffering, and some sort of synchronisation to determine the 112 bit frame boundaries. Fortunately much of the C code for these LDPC codes already exists, as it was developed for the Wenet High Altitude Balloon work.

If most frames at the decoder input are now error free, we can consider more efficient (but less robust) techniques for Codec 2, such as prediction (delta coding). This will decrease the codec bit rate for a given speech quality. We could then choose to reduce our bit rate (making the system more robust for a given channel SNR), or raise speech quality while maintaining the same bit rate.

Command Lines

Generating the decoded speech, first run the Octave ldpc_short simulation to generate “error pattern file”, then subject the Codec 2 700C bit stream to these error patterns.

octave:67> ldpc_short $ ./c2enc 700C ../../raw/ve9qrp_10s.raw - | ./insert_errors - - ../../octave/awgn_2dB_ldpc.err 28 | ./c2dec 700C - - | aplay -f S16_LE -

The simulation generate .eps files as direct generation of PNG leads to font size issues. Converting EPS to PNG without transparent background:

mogrify -resize 700x600 -density 300 -flatten -format png *.eps

However I still feel the images are a bit fuzzy, especially the text. Any ideas? Here’s the eps file if some one would like to try to get a nicer PNG conversion for me! The EPS file looks great at any scaling when I render it using the Ubuntu document viewer.

Update: A friend of mine (Erich) has suggested using GIMP for the conversion. This does seem to work well and has options for text and line anti-aliasing. It would be nice to be able to generate nice PNGs directly from Octave – my best approach so far is to capture screen shots.

Links

LowSNR site Bill VK5DSP writes about his experiments in low SNR communications.

Wenet High Altitude Balloon SSDV System developed with Mark VK5QI and BIll VK5DSP that uses LDPC codes.

LPDC using Octave and the CML library

FreeDV 700C

Codec 2 700C

OpenSTEM: St Patrick’s Day 2017 – and a free resource on Irish in Australia

Sat, 2017-03-18 11:05

Happy St Patrick’s day!

And “we have a resource on that” – that is, on the Irish in Australia and the major contributions they made since the very beginning of the colonies. You can get that lovely 5 page resource PDF for free if you check out using coupon code TRYARESOURCE. It’s an option we’ve recently put in place so anyone can grab one resource of their choice to see if they like our materials and assess their quality.

Back to St Patrick, we were briefly in Ireland last year and near Dublin we drove past a ruin at the top of a hill that piqued our interest, so we stopped and had a look. It turned out to be Slane Abbey, the site where it is believed in 433 AD, the first Christian missionary to Ireland, later known as St Patrick, lit a large (Easter) celebration fire (on the Hill of Slane). With this action he (unwittingly?) contravened orders by King Laoghaire at nearby Tara. The landscape photo past the Celtic cross shows the view towards Tara. Ireland is a beautiful country, with a rich history.

Photos by Arjen Lentz & Dr Claire Reeler

OpenSTEM: Am I a Neanderthal?

Wed, 2017-03-15 11:05
Early reconstruction of Neanderthal

The whole question of how Neanderthals are related to us (modern humans) has been controversial ever since the first Neanderthal bones were found in Germany in the 19th century. Belonging to an elderly, arthritic individual (a good example of how well Neanderthals cared for each other in social groups), the bones were reconstructed to show a stooping individual, with a more ape-like gait, leading to Neanderthals being described as the “Missing Link” between apes and humans, and given the epithet “ape-man”.

Who were the Neanderthals? Modern reconstruction – Smithsonian Museum of Natural History

Neanderthals lived in the lands surrounding the Mediterranean Sea, and as far east as the Altai Mountains in Central Asia, between about 250,000 and about 30,000 years ago. They were a form of ancient human with certain physical characteristics – many of which probably helped them cope with the cold of Ice Ages. Neanderthals evolved out of an earlier ancestorHomo erectus, possibly through another species – Homo heidelbergensis. They had a larger brain than modern humans, but it was shaped slightly differently, with less development in the prefrontal cortex, which allows critical thinking and problem-solving, and larger development at the back of the skull, and in areas associated with memory in our brains. It is possible that Neanderthals had excellent memory, but poor analytical skills. They were probably not good at innovation – a skill which became vital as the Ice Age ended and the global climate warmed, sea levels rose and plant and animal habitats changed.

Neanderthals were stockier than modern humans, with shorter arms and legs, and probably stronger and all-round tougher. They had a larger rib cage, and probably bigger lungs, a bigger nose, larger eyes and little to no chin. Most of these adaptations would have helped them in Ice Age Europe and Asia – a more compact body stayed warmer more easily and was tough enough to cope with a harsh environment. Large lungs helped oxygenate the blood and there is evidence that they had more blood supply to the face – so probably had warm, ruddy cheeks. The large nose warmed up the air they breathed, before it reached their lungs, reducing the likelihood of contracting pneumonia. Neanderthals are known to have had the same range of hair colours as modern humans and fair skin, red hair and freckles may have been more common.

They made stone tools, especially those of the type called Mousterian, constructed simple dwellings and boats, made and used fire, including for cooking their food, and looked after each other in social groups. Evidence of skeletons with extensive injuries occurring well before death, shows that these individuals must have been cared for, not only whilst recovering from their injuries, but also afterwards, when they would probably not have been able to obtain food themselves. Whether or not Neanderthals intentionally buried their dead is an area of hot controversy. It was once thought that they buried their dead with flowers in the grave, but the pollen was found to have been introduced accidentally. However, claims of intentional burial are still debated from other sites.

What Happened to the Neanderthals? Abrigo do Lagar Velho

Anatomically modern humans emerged from Africa about 100,000 years ago. Recent studies of human genetics suggests that modern humans had many episodes of mixing with various lineages of human ancestors around the planet. Modern humans moved into Asia and Europe during the Ice Age, expanding further as the Ice Age ended. Modern humans overlapped with Neanderthals for about 60,000 years, before the Neanderthals disappeared. It is thought that a combination of factors led to the decline of Neanderthals. Firstly, the arrival of modern humans, followed by the end of the Ice Age, brought about a series of challenges which Neanderthals might have been unable to adapt to, as quickly as necessary. Modern humans have more problem solving and innovation capability, which might have meant that they were able to out-compete Neanderthals in a changing environment. The longest held theory is that out ancestors wiped out the Neanderthals in the first genocide in (pre)history. A find of Neanderthals in a group, across a range of ages, some from the same family group, who all died at the same time, is one of the sites, which might support this theory, although we don’t actually know who (or what) killed the group. Cut marks on their bones show that they were killed by something using stone tools. Finally, there is more and more evidence of what are called “transitional specimens”. These are individuals who have physical characteristics of both groups, and must represent inter-breeding. An example is the 4 year old child from the site of Abrigo do Lagar Velho in Portugal, which seems to have a combination of modern and Neanderthal features. The discovery of Neanderthals genes in many modern people living today is also proof that we must have interbred with Neanderthals in the past. It is thought that the genes were mixed several times, in several parts of the world.

Am I a Neanderthal?

So how do we know if we have Neanderthals genes? Neanderthal genes have some physical characteristics, but also other attributes that we can’t see. In terms of physical characteristics, Neanderthal aspects to the skull include brow ridges (ridges of bone above the eyes, under the eyebrows); a bump on the back of the head – called an occipital chignon, or bun, because it looks like a ‘bun’ hairstyle, built into the bone; a long skull (like Captain Jean-Lu Picard from Star Trek – actor Patrick Stewart); a small, or non-existent chin; a large nose; a large jaw with lots of space for wisdom teeth; wide fingers and thumbs; thick, straight hair; large eyes; red hair, fair skin and freckles! The last may seem a little surprising, but it appears that the genes for these characteristics came from Neanderthals – who had a wide range of hair colours, fair skin and, occasionally, freckles. Increased blood flow to the face also would have given Neanderthals lovely rosy cheeks!

Less obvious characteristics include resistance to certain diseases – parts of our immune systems, especially with reference to European and Asian diseases; less positively, an increased risk of other diseases, such as type 2 diabetes. Certain genes linked to depression are present, but ‘switched off’ in Neanderthals. The way that these genes link to depression, and their role in the lifestyles of early people (where they may have had benefits that are no longer relevant) are future topics for research and may help us understand more about ourselves.

Neanderthals genes are present in modern populations from Europe, Asia, Northern Africa, Australia and Oceania. So, depending on which parts of the world our ancestry is from, we may have up to 4% of our genetics from long-dead Neanderthal ancestors!

Craige McWhirter: Japanese House in Python for Minecraft

Wed, 2017-03-15 10:04

I have kids that I'm teaching to hack. They started of on Scratch (which is excellent) and are ready to move up to Python. They also happen to be mad Minecraft fans, so now they're making their way through Adventures in Minecraft.

As I used Scratch when they were, I'm also hacking in Python & Minecraft as they are. It helps if I hit the bumps and hurdles before they do, as well as have a sound handle on the problems they're solving.

Now I've branched out from the tutorial and I'm just having fun with it and leaving behind code the kids can use, hack whatever. This code is in my minecraft-tools repo (for want of a better name). It's just a collection of random tools I've written for Minecraft aren't quite up to being their own thing. I expect this will mostly be a collection of python programs to construct things inside Minecraft via CanaryMod and CanaryRaspberryJuicePlugin.

The first bit of code to be shaken out of the tree is japanese_house.py which produces a Minecraft interpretation of a classic Japanese house. Presently it only produces the single configuration that is little more than an empty shell.

I intend to add an interior fit out plus a whole bunch of optional configurations you can set at run time but for now it is what it is, as I'm going to move onto writing geodesic domes and transport | teleport rings (as per the Expanse, which will lead to eventually coding a TARDIS, that will you know, be actually bigger on the inside ;-)

David Rowe: Testing FreeDV 700C

Tue, 2017-03-14 19:06

Since releasing FreeDV 700C I’ve been “instrumenting” the FreeDV GUI program – adding some code to perform various tests of the 700C waveform, especially over the air.

With the kind help of Gerhard OE3GBB, Mark VK5QI, and Peter VK5APR, I have collected some samples and performed some tests. The goals of this work were:

  1. Compare 700C Over the Air (OTA) to simulation on an AWGN channel.
  2. Compare 700C OTA to SSB on an AWGN channel.

Instrumentation

Here is a screen shot of the latest FreeDV GUI Options screen:

I’ve added some features to the top three rows:

Test Frames Send a payload of known test bits rather than vocoder bits Channel Noise Simulate a channel using AWGN noise SNR SNR of AWGN noise Attn Carrier Attenuate just one carrier Carrier The 700C carrier (1-14) to attenuate Simulated Interference Tone Enable an interfering sine wave of specified frequency and amplitude Clipping Enable clipping of 700C tx waveform, to increase RMS power Diversity Combine for plots Scatter and Test Frame plots use combined (7 carrier) information.

To explore these options it is useful to run in full duplex mode (Tools-PTT Half Duplex unchecked) and using a loopback sound device:

$ sudo modprobe snd-aloop

More information on loopback in the FreeDV GUI README.

Clipping the 700C tx waveform reduces the Peak to Average Power ratio (PAPR) which may be result in a higher average power over the channel. However clipping distorts the waveform and add some “shoulders (i.e. noise) to the spectrum adjacent to the 700C waveform:

Several users have noticed this distortion. At this stage I’m unsure if clipping is useful or not.

The Diversity Combine option is useful to explore each of the 14 carriers separately before they are combined into 7 carriers.

Many of these options were designed to explore tx filtering. I have long wondered if any of the FreeDV carriers were receiving less power than others, for example due to ripple or a low pass response from the crystal filter. A low power carrier would have a high bit error rate, adversely affecting overall performance. Plotting the scatter diagram or bit error rate on a carrier by carrier basis can measure the effect of tx filtering – if it exists.

Some of the features above – like attenuating a single carrier – were designed to “test the test”. Much of the work I do on FreeDV (and indeed other projects) involves carefully developing software and writing “code to test the code”. For example to build the experiments described in this blog post I worked several hours day for several weeks. Not glamorous, but where the real labour lies in R&D. Careful, meticulous testing and experimentation. One percent inspiration … then code, test, test.

Comparing Analog SSB to Digital Voice

One of my goals is to develop a HF DV system that is competitive with analog SSB. So we need a way to compare analog and DV at the same SNR. So I came with the idea of a wave files of analog SSB and DV which have the same average (RMS) power. If these are fed into a SSB transmitter, then they will be received at the same SNR. I added 10 seconds of a 1000Hz sine wave at the start for good measure – this could be used to measure the actual SNR.

I developed two files:

  1. sine_analog_700c
  2. sine_analog_testframes700c

The first has the same voice signal in analog and 700C, the second uses test frames instead of encoded voice.

Interfering Carriers

One feature described above simulates an interfering carrier (like a birdie), something I have seen on the air. Here is a plot of a carrier in the middle of one of the 700C carriers, but about 10dB higher:

The upper RH plot is a rolling plot of bit errors for each carrier. You can see one carrier is really messed up – lots of bit errors. The average bit error rate is about 1%, which is where FreeDV 700C starts to become difficult to understand. These bit errors would not be randomly distributed, but would affect one part of the codec all the time. For example the pitch might be consistently wrong, or part of the speech spectrum. I found that as long as the interfering carrier is below the FreeDV carrier, the effect on bit error rate is negligible.

Take away: The tx station must tune away from any interfering carriers that poke above the FreeDV signal carriers. Placing the interfering tones between FreeDV carriers is another possibility, e.g. a 50Hz shift of the tx signal.

Results – Transmit Filtering

Simulation results suggest 700C should produce reasonable results near 0db SNR. So that’s the SNR I’m shooting for in Over The Air (OTA) testing.

Mark VK5QI sent me several minutes of test frames so I could determine if there were any carriers with dramatically different bit error rates, which would indicate the presence of some tx filtering. Here is the histogram of BERs for each carrier for Mark’s signal, which was at about 3dB SNR:

There is one bar for each I and Q QPSK bit of the 14 carriers – 28 bars total (note Diversity combination was off). After running for a few minutes, we can see a range of 5E-2 and 8E-2 (5 to 8%). In terms of AWGN modem performance, this is only about 1dB difference in SNR or Eb/No, as per the BER versus Eb/No graphs in this post on the COHPSK modem used for 700C. One carrier being pinned at say 20% BER, or a slope of increasing BER with carrier frequency – would have meant tx filtering trouble.

Peter VK5APR, sent me a high SNR signal (he lives just 4 km away). Initially I could see a X shaped scatter diagram, a possible sign of tx filtering. However this ended up being some amplitude pumping due to Fast AGC on my radio. After I disabled fast AGC, I could see a scatter diagram with 4 clear dots, and no X-shape. Check.

I performed an additional test using my IC7200 as a transmitter, and a HackRF as a receiver. The HackRF has no crystal filter and a very flat response, so any distortion would be due to the IC7200 transmit filtering. Once again – 4 clean dots on the scatter diagram and no X-shape.

So I am happy to conclude that transmit filtering does not seem to be a problem, at least of the radios tested. All performance issues are therefore likely to be caused by me and my algorithms!

Results – Low SNR testing

Peter, VK5APR, configured his station to send the analog/700C equi-power test wave files described above at very low power, such that the received SNR at my station was about 0dB. As we are so close it was reasonable to assume the channel was AWGN, indeed we could see no sign of NVIS fading and the band (40M) was devoid of DX at the 12 noon test time.

Here is the rx signal I received, and the same file run through the 700C decoder. Neither the SSB or the decoded 700C audio are pretty. However it’s fair to say we could just get a message through on both modes and that 700C is holding it’s own next to SSB. The results are close to my simulations which was the purpose of this test.

You can decode the off air signal yourself if you download the first file and replay it through the FreeDV GUI program using “Tools – Start/Stop Play File from Radio”.

Discussion

While setting up these tests, Peter and I conversed comfortably for some time over FreeDV 700C at a high SNR. This proved to me that for our audience (experienced users of HF radio) – FreeDV 700C can be used for conversational contacts. Given the 700C codec is really just a first pass – that’s a fine result.

However it’s a near thing – the 700C codec adds a lot of distortion just compressing the speech. It’s pretty bad even if the SNR is high. The comments on the Codec 2 700C blog post indicate many lay-people can’t understand speech compressed by 700C. Add any bit errors (due to low SNR or fading) and it quickly becomes hard to understand – even for experienced users. This makes 700C very sensitive to bit errors as the SNR drops. But hey – every one of those 28 bits/frame counts at 700 bit/s so it’s not surprising.

In contrast, SSB scales a bit better with SNR. However even at high SNRs, that annoying hiss is always there – which is very fatiguing. Peter and I really noticed that hiss after a few minutes back on SSB. Yuck.

SSB gets a lot of it’s low SNR “punch” from making effective use of peak power. Here is a plot of the received SSB:

It’s all noise except for the speech peaks, where the “peak SNR” is much higher than 0dB. Our brains are adept at picking out words from those peaks, integrating the received phonetic symbols (mainly vowel energy) in our squishy biological receive filters. It’s a pity we didn’t evolve to detect coherent PSK. A curse on your evolution!

In contrast – 700C allocates just as much power to the silence between words as the most important parts of speech. This suggests we could do a better job at tailoring the codec and modem to peak power, e.g. allocating more power to parts of the speech that really matter. I had a pass at Time Variable Quantisation a few years ago. A variable rate codec might be called for, tightly integrated to the modem to pack more bits/power into perceptually important parts of speech.

The results above assumed equal average power for SSB and FreeDV 700C. It’s unclear if this happens in the real world. For example we may need to “back off” FreeDV drive further than SSB; SSB may use a compressor; and the PAs we are using are generally designed for PEP rather than average power operation.

Next Steps

I’m fairly happy with the baseline COHPSK modem, it seems to be hanging on OK as long as there aren’t any co-channel birdies. The 700C codec works better than expected, has plenty of room for improvement – but it’s sensitive to bit errors. So I’m inclined to try some FEC next. Aim for error free 700C at 0dB, which I think will be superior to SSB. I’ll swap out the diversity for FEC. This will increase the raw BER, but allow me to run a serious rate 0.5 code. I’ll start just with an AWGN channel, then tackle fading channels.

Links

FreeDV 700C
Codec 2 700C

Matthew Oliver: Setting up a basic keystone for Swift + Keystone dev work

Tue, 2017-03-14 17:07

As a Swift developer, most of the development works in a Swift All In One (SAIO) environment. This environment simulates a mulinode swift cluster on one box. All the SAIO documentation points to using tempauth for authentication. Why?

Because most the time authentication isn’t the things we are working on. Swift has many moving parts, and so tempauth, which only exists for testing swift and is configured in the proxy.conf file works great.

However, there are times you need to debug or test keystone + swift integration. In this case, we tend to build up a devstack for keystone component. But if all we need is keystone, then can we just throw one up on a SAIO?… yes. So this is how I do it.

Firstly, I’m going to be assuming you have SAIO already setup. If not go do that first. not that it really matters, as we only configure the SAIO keystone component at the end. But I will be making keystone listen on localhost, so if you are doing this on anther machine, you’ll have to change that.

Further, this will set up a keystone server in the form you’d expect from a real deploy (setting up the admin and public interfaces).

 

Step 1 – Get the source, install and start keystone

Clone the sourcecode:
cd $HOME
git clone https://github.com/openstack/keystone.git

Setup a virtualenv (optional):
mkdir -p ~/venv/keystone
virtualenv ~/venv/keystone
source ~/venv/keystone/bin/activate

Install keystone:
cd $HOME/keystone
pip install -r requirements.txt
pip install -e .
cp etc/keystone.conf.sample etc/keystone.conf

Note: We are running the services from the source so config exists in source etc.

 

The fernet keys seems to assume a full /etc path, so we’ll create it. Maybe I should update this to put all config there but for now meh:
sudo mkdir -p /etc/keystone/fernet-keys/
sudo chown $USER -R /etc/keystone/

Setup the database and fernet:
keystone-manage db_sync
keystone-manage fernet_setup

Finally we can start keystone. Keystone is a wsgi application and so needs a server to pass it requests. The current keystone developer documentation seems to recommend uwsgi, so lets do that.

 

First we need uwsgi and the python plugin, one a debian/ubuntu system you:
sudo apt-get install uwsgi uwsgi-plugin-python

Then we can start keystone, by starting the admin and public wsgi servers:
uwsgi --http 127.0.0.1:35357 --wsgi-file $(which keystone-wsgi-admin) &
uwsgi --http 127.0.0.1:5000 --wsgi-file $(which keystone-wsgi-public) &

Note: Here I am just backgrounding them, you could run then in tmux or screen, or setup uwsgi to run them all the time. But that’s out of scope for this.

 

Now a netstat should show that keystone is listening on port 35357 and 5000:
$ netstat -ntlp | egrep '35357|5000'
tcp 0 0 127.0.0.1:5000 0.0.0.0:* LISTEN 26916/uwsgi
tcp 0 0 127.0.0.1:35357 0.0.0.0:* LISTEN 26841/uwsgi

Step 2 – Setting up keystone for swift

Now that we have keystone started, its time to configure it. Firstly you need the openstack client to configure it so:
pip install python-openstackclient

Next we’ll use all keystone defaults, so we only need to pick an admin password. For the sake of this how-to I’ll pick the developer documentation example of `s3cr3t`. Be sure to change this. So we can do a basic keystone bootstrap with:
keystone-manage bootstrap --bootstrap-password s3cr3t

Now we just need to set up some openstack env variables so we can use the openstack client to finish the setup. To make it easy to access I’ll dump them into a file you can source. But feel free to dump these in your bashrc or whatever:
cat > ~/keystone.env <<EOF
export OS_USERNAME=admin
export OS_PASSWORD=s3cr3t
export OS_PROJECT_NAME=admin
export OS_USER_DOMAIN_ID=default
export OS_PROJECT_DOMAIN_ID=default
export OS_IDENTITY_API_VERSION=3
export OS_AUTH_URL=http://localhost:5000/v3
EOF

source ~/keystone.env

 

Great, now  we can finish configuring keystone. Let’s first setup a service project (tennent) for our Swift cluster:
openstack project create service

Create a user for the cluster to auth as when checking user tokens and add the user to the service project, again we need to pick a password for this user so `Sekr3tPass` will do.. don’t forget to change it:
openstack user create swift --password Sekr3tPass --project service
openstack role add admin --project service --user swift

Now we will create the object-store (swift) service and add the endpoints for the service catelog:
openstack service create object-store --name swift --description "Swift Service"
openstack endpoint create swift public "http://localhost:8080/v1/AUTH_\$(tenant_id)s"
openstack endpoint create swift internal "http://localhost:8080/v1/AUTH_\$(tenant_id)s"

Note: We need to define the reseller_prefix we want to use in Swift. If you change it in Swift, make sure you update it here.

 

Now we can add roles that will match to roles in Swift, namely an operator (someone who will get a Swift account) and reseller_admins:
openstack role create SwiftOperator
openstack role create ResellerAdmin

Step 3 – Setup some keystone users to auth as.

TODO: create all the tempauth users here

 

Here, it would make sense to create the tempauth users devs are used to using, but I’ll just go create a user so you know how to do it. First create a project (tennent) for this example demo:
openstack project create --domain default --description "Demo Project" demo

Create a user:
openstack user create --domain default --password-prompt matt

We’ll also go create a basic user role:
openstack role create user

Now connect the 3 pieces together by adding user matt to the demo project with the user role:
openstack role add --project demo --user matt user

If you wanted user matt to be a swift operator (have an account) you’d:
openstack role add --project demo --user matt SwiftOperator

or even a reseller_admin:
openstack role add --project demo --user matt ResellerAdmin

If your in a virtual env, you can leave it now, because next we’re going to go back to your already setup swift to do the Swift -> Keystone part:
deactivate

Step 4 – Configure Swift

To get swift to talk to keystone we need to add 2 middlewares to the proxy pipeline. And in the case of a SAIO, remove the tempauth middleware. But before we do that we need to install the keystonemiddleware to get one of the 2 middlware’s, keystone’s authtoken:
sudo pip install keystonemiddleware

Now you want to replace your tempauth middleware in the proxy path pipeline with authtoken keystoneauth so it looks something like:
pipeline = catch_errors gatekeeper healthcheck proxy-logging cache bulk tempurl ratelimit crossdomain container_sync authtoken keystoneauth staticweb copy container-quotas account-quotas slo dlo versioned_writes proxy-logging proxy-server

Then in the same ‘proxy-server.conf’ file you need to add the paste filter sections for both of these new middlewares:
[filter:authtoken]
paste.filter_factory = keystonemiddleware.auth_token:filter_factory
auth_host = localhost
auth_port = 35357
auth_protocol = http
auth_uri = http://localhost:5000/
admin_tenant_name = service
admin_user = swift
admin_password = Sekr3tPass
delay_auth_decision = True
# cache = swift.cache
# include_service_catalog = False
[filter:keystoneauth]
use = egg:swift#keystoneauth
# reseller_prefix = AUTH
operator_roles = admin, SwiftOperator
reseller_admin_role = ResellerAdmin

Note: You need to make sure if you change the reseller_prefix here, you change it in keystone. And notice this is where you map operator_roles and reseller_admin_role in swift to that in keystone. Here anyone in with the keystone role admin or SwiftOperator are swift operators and those with the ResellerAdmin role are reseller_admins.

 

And that’s it. Now you should be able to restart your swift proxy and it’ll go off and talk to keystone.

 

You can use your Python swiftclient now to go talk, and whats better swiftclient understands the OS_* variables, so you can just source your keystone.env and talk to your cluster (to be admin) or export some new envs for the user you’ve created. If you want to use curl you can. But _much_ easier to use swiftclient.

 

Tip: You can use: swift auth to get the auth_token if you want to then use curl.

 

If you want to authenticate via curl then for v3, use: https://docs.openstack.org/developer/keystone/devref/api_curl_examples.html

 

Or for v2, I use:
url="http://localhost:5000/v2.0/tokens"
auth='{"auth": {"tenantName": "demo", "passwordCredentials": {"username": "matt", "password": ""}}}'

 

curl -s -d "$auth" -H 'Content-type: application/json' $url |python -m json.tool

 

or

curl -s -d "$auth" -H 'Content-type: application/json' $url |python -c "import sys, json; print json.load(sys.stdin)['access']['token']['id']"

To just print out the token. Although a simple swift auth would do all this for you.

James Morris: LSM mailing list archive: this time for sure!

Tue, 2017-03-14 11:01

Following various unresolved issues with existing mail archives for the Linux Security Modules mailing list, I’ve set up a new archive here.

It’s a mailman mirror of the vger list.

Sridhar Dhanapalan: How to Create a Venn Diagram with Independent Intersections in PowerPoint

Mon, 2017-03-13 23:02

A Venn diagram can be a great way to explain a business concept. This is generally not difficult to create in modern presentation software. I often use Google Slides for its collaboration abilities.

Where it becomes difficult is when you want to add a unique colour/pattern to an intersection, where the circles overlap. Generally you will either get one circle overlapping another, or if you set some transparency then the intersection will become a blend of the colours of the circles.

I could not work out how to do this in Google Slides, so on this occasion I cheated and did it in Microsoft PowerPoint instead. I then imported the resulting slide into Slides.

This worked for me in PowerPoint for Mac 2016. The process is probably the same on Windows.

Firstly, create a SmartArt Venn Diagram

Insert > SmartArt > Relationship > Basic Venn

Separate the Venn circles

SmartArt Design > Convert > Convert to Shapes

Ungroup shapes

Shape Format > Group Objects > Ungroup

Split out the intersections

Shape Format > Merge Shapes > Fragment

From there, you can select the intersection as an independent shape. You can treat each piece separately. Try giving them different colours or even moving them apart.

This can be a simple but impactful way to get your point across.