news aggregator

Dan Treacy: Hello world!

Planet Linux Australia - 58 min 38 sec ago

Welcome to WordPress. This is your first post. Edit or delete it, then start writing!

Binh Nguyen: Life in Yemen, Blogger2Book BASH script, and More

Planet Linux Australia - 6 hours 51 min ago
- main reasons why it's been in the news is because of recent conflict. A lot of them are saying this is a proxy war between Saudi Arabia and Iran who effectively represent different sects within Islam. Over and over again feels like people in the Middle East just want some dignity and respect from the West? Shortages across the board (food, medicine, petrol, etc...) Yemen people saying Saudi

sthbrx - a POWER technical blog: Evaluating CephFS on Power

Planet Linux Australia - Wed, 2017-03-29 00:00
Methodology

To evaluate CephFS, we will create a ppc64le virtual machine, with sufficient space to compile the software, as well as 3 sparse 1TB disks to create the object store.

We will then build & install the Ceph packages, after adding the PowerPC optimisiations to the code. This is done, as ceph-deploy will fetch prebuilt packages that do not have the performance patches if the packages are not installed.

Finally, we will use the ceph-deploy to deploy the instance. We will ceph-deploy via pip, to avoid file conflicts with the packages that we built.

For more information on what each command does, visit the following tutorial, upon which which this is based: http://palmerville.github.io/2016/04/30/single-node-ceph-install.html

Virtual Machine Config

Create a virtual machine with at least the following: - 16GB of memory - 16 CPUs - 64GB disk for the root filesystem - 3 x 1TB for the Ceph object store - Ubuntu 16.04 default install (only use the 64GB disk, leave the others unpartitioned)

Initial config
  • Enable ssh
sudo apt install openssh-server sudo apt update sudo apt upgrade sudo reboot
  • Install build tools
sudo apt install git debhelper Build Ceph mkdir $HOME/src cd $HOME/src git clone --recursive https://github.com/ceph/ceph.git # This may take a while cd ceph git checkout master git submodule update --force --init --recursive
  • Cherry-pick the Power performance patches:
git remote add kestrels https://github.com/kestrels/ceph.git git fetch --all git cherry-pick 59bed55a676ebbe3ad97d8ec005c2088553e4e11
  • Install prerequisites
./install-deps.sh sudo apt install python-requests python-flask resource-agents curl python-cherrypy python3-pip python-django python-dateutil python-djangorestframework sudo pip3 install ceph-deploy cd $HOME/src/ceph sudo dpkg-buildpackage -J$(nproc) # This will take a couple of hours (16 cpus)
  • Install the packages (note that python3-ceph-argparse will fail, but is safe to ignore)
cd $HOME/src sudo dpkg -i *.deb Create the ceph-deploy user sudo adduser ceph-deploy echo "ceph-deploy ALL = (root) NOPASSWD:ALL" | sudo tee /etc/sudoers.d/ceph-deploy sudo chmod 0440 /etc/sudoers.d/ceph-deploy Configure the ceph-deploy user environment su - ceph-deploy ssh-keygen node=`hostname` ssh-copy-id ceph-deploy@$node mkdir $HOME/ceph-cluster cd $HOME/ceph-cluster ceph-deploy new $node # If this fails, remove the bogus 127.0.1.1 entry from /etc/hosts echo 'osd pool default size = 2' >> ceph.conf echo 'osd crush chooseleaf type = 0' >> ceph.conf Complete the Ceph deployment ceph-deploy install $node ceph-deploy mon create-initial drives="vda vdb vdc" # the 1TB drives - check that these are correct for your system for drive in $drives; do ceph-deploy disk zap $node:$drive; ceph-deploy osd prepare $node:$drive; done for drive in $drives; do ceph-deploy osd activate $node:/dev/${drive}1; done ceph-deploy admin $node sudo chmod +r /etc/ceph/ceph.client.admin.keyring ceph -s # Check the state of the cluster Configure CephFS ceph-deploy mds create $node ceph osd pool create cephfs_data 128 ceph osd pool create cephfs_metadata 128 ceph fs new cephfs cephfs_metadata cephfs_data sudo systemctl status ceph\*.service ceph\*.target # Ensure the ceph-osd, ceph-mon & ceph-mds daemons are running sudo mkdir /mnt/cephfs key=`grep key ~/ceph-cluster/ceph.client.admin.keyring | cut -d ' ' -f 3` sudo mount -t ceph $node:6789:/ /mnt/cephfs -o name=admin,secret=$key References
  1. http://docs.ceph.com/docs/master/install/clone-source/
  2. http://docs.ceph.com/docs/master/install/build-ceph/
  3. http://palmerville.github.io/2016/04/30/single-node-ceph-install.html

Donna Benjamin: Making Views in Drupal 7 and Drupal 8

Planet Linux Australia - Tue, 2017-03-28 13:03
Tuesday, March 28, 2017 - 10:53

This talk was written for DrupalGov Canberra 2017.

Download a PDF of the slides.

Or view below on slideshare.

 

Making views - DrupalGov Canberra 2017 from Donna Benjamin AttachmentSize Making Views in Drupal 7 and Drupal 84.46 MB

BlueHackers: Busyness: A Modern Health Crisis | LinkedIn

Planet Linux Australia - Tue, 2017-03-28 12:35

Benjamin Cardullo writes about an issue that we really have to take (more) seriously.  Particularly with mobile devices enabling us to be “connected” 24/7, being busy (or available) all of that time is not a good thing at all.

How do we measure professional success? Is it by the location of our office or the size of our paycheck? Is it measured by the dimensions of our home or the speed of our car? Ten years ago, those would have been the most prominent answers; however, today when someone is really pulling out the big guns, when they really want to show you how important they are, they’ll tell you all about their busy day and how they never had a moment to themselves.

Read the full article: https://www.linkedin.com/pulse/busyness-modern-health-crisis-benjamin-cardullo

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

Planet Linux Australia - Tue, 2017-03-28 11:09

The last week of our first unit – time to wrap up, round off, finish up any work not yet done and to perhaps get a preliminary taste of what’s to come in future units. Easter holidays are just around the corner. Our youngest students are having a final discussion about celebrations; slightly older students are finishing off their quest for Aunt Madge, by looking at landmarks and the older students are considering democracy in Australia, compared to its early beginnings in Ancient Greece.

Foundation to Year 3

Foundation/Prep (units F.1 and F.6) students are finishing off their discussions about celebrations, just in time for the Easter holidays, by looking at celebrations around the world. Teachers may wish to focus on how other countries celebrate Easter, with passion plays, processions and special meals. Students in Years 1 (unit 1.1), 2 (unit 2.1) and 3 (unit 3.1) are finishing off their Aunt Madge activity, looking at landmarks in Australia and around the world. There is the option for teachers to concentrate on Australian landmarks in this lesson, setting the stage for some local history studies in the next unit, next term.

Years 3 to 6 Ancient Greek pottery with votes scratched into the surface

Older students in Years 3 (unit 3.5), 4 (unit 4.1), 5 (unit 5.1) and 6 (unit 6.1) start looking ahead and laying the foundations for later studies on the Australian system of government and democracy, by comparing democracy as it arose in Ancient Greece, with the modern Australian democratic system. Our word for democracy comes from the Ancient Greek words demos (people) and kratia (power). Students move on from their discussion of Eratosthenes to looking at the Ancient Greek democratic system, which was to lay the groundwork for modern democratic systems around the world. Discussing Ancient Greek democracy leads students to consider the rights and responsibilities of being a citizen, at both the local and international levels. Students also consider who could and could not vote and what this meant for different groups. They can also touch on the ancient practise of ostracism, which can lead to ethical debates around fair election practises. By considering these fundamental concepts, students are better able to relate the ideas around modern democracy to their own lives.

 

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

Planet Linux Australia - 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

Planet Linux Australia - 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

Planet Linux Australia - 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

Planet Linux Australia - 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!

Planet Linux Australia - 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

Planet Linux Australia - 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

Planet Linux Australia - 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

Planet Linux Australia - 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

Planet Linux Australia - 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

Planet Linux Australia - 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

Planet Linux Australia - 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

Planet Linux Australia - 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

Planet Linux Australia - 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

Planet Linux 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