The Genetic Algorithm Framework for .Net

Please Note that the documentation and example code for the The Genetic Algorithm Framework for .Net (GAF) has been moved to a dedicated wiki at http://gaframework.org.

The Genetic Algorithm Framework for .Net (GAF) is a really simple to use free .Net assembly that can be useful in both production and educational environments. Supplied as a single PCL, Mono compatible assembly via NuGet, the product can be added to any Visual Studio or Xamarin project. For an introduction to the topic using the GAF see the associated CodeProject article for details.

6502 Cross Assembly using MacOS and Atom

Cross Assembly Using Atom

Some time back I wrote a post that used Visual Studio Code running on MacOS to cross assemble 6502 assembly code for the Applie II. Since then I have been asked about using the Atom editor. If you are not familiar with the original article, it may be appropriate to check it out before reading further.

To use Atom in the same manner as VS Code, i.e. with the same automated compile and test scripts, the standard install of Atom simply requires two packages adding. One for code highlighting and the other for running the tasks.

Code Highlighting

The following package can be added to Atom to provide code highlighting.

language-65asm

Running the Build and Test Scripts

The equivelent of the Visual Studio Tasks functionality can be obtained by adding the following package;

process-template

The configuration for this is stored in process-pallet.json. I have included an example configuration I have used to build and test project called “JTTY” using the Merlin 32 Assembler from Brutal Delux.

Hope this helps!

{
  "patterns": {
    "P1": {
      "expression": "(path):(line)"
    },
    "P2": {
      "expression": "(path)\\s+(line)",
      "path": "(?:\\/[\\w\\.\\-]+)+"
    }
  },
  "commands": [
    {
      "namespace": "process-palette",
      "action": "Build-Assemble",
      "command": "{projectPath}/build-assemble jtty",
      "arguments": [],
      "cwd": "{projectPath}",
      "inputDialogs": [],
      "env": {},
      "keystroke": "cmd-shift-b",
      "stream": true,
      "outputTarget": "panel",
      "outputBufferSize": 80000,
      "maxCompleted": 3,
      "autoShowOutput": true,
      "autoHideOutput": false,
      "scrollLockEnabled": false,
      "singular": false,
      "promptToSave": true,
      "saveOption": "all",
      "patterns": [
      "default"
      ],
      "successOutput": "{stdout}",
      "errorOutput": "{stdout}\n{stderr}",
      "fatalOutput": "Failed to execute : {fullCommand}\n{stdout}\n{stderr}",
      "startMessage": null,
      "successMessage": "Executed : {fullCommand}",
      "errorMessage": "Executed : {fullCommand}\nReturned with code {exitStatus}\n{stderr}",
      "fatalMessage": "Failed to execute : {fullCommand}\n{stdout}\n{stderr}",
      "menus": [
        "Processes",
        "Project"
      ],
      "notifyOnStart": false,
      "notifyOnSuccess": true,
      "notifyOnError": true,
      "input": null
    },
    {
      "namespace": "process-palette",
      "action": "Build-Test",
      "command": "{projectPath}/build-test jtty 0x8000",
      "arguments": [],
      "cwd": "{projectPath}",
      "inputDialogs": [],
      "env": {},
      "keystroke": "cmd-shift-t",
      "stream": true,
      "outputTarget": "panel",
      "outputBufferSize": 80000,
      "maxCompleted": 3,
      "autoShowOutput": true,
      "autoHideOutput": false,
      "scrollLockEnabled": false,
      "singular": false,
      "promptToSave": true,
      "saveOption": "all",
      "patterns": [
      "default"
      ],
      "successOutput": "{stdout}",
      "errorOutput": "{stdout}\n{stderr}",
      "fatalOutput": "Failed to execute : {fullCommand}\n{stdout}\n{stderr}",
      "startMessage": null,
      "successMessage": "Executed : {fullCommand}",
      "errorMessage": "Executed : {fullCommand}\nReturned with code {exitStatus}\n{stderr}",
      "fatalMessage": "Failed to execute : {fullCommand}\n{stdout}\n{stderr}",
      "menus": [
        "Processes",
        "Project"
      ],
      "notifyOnStart": false,
      "notifyOnSuccess": true,
      "notifyOnError": true,
      "input": null
    }
  ]
}

6502 Cross Assembly for the Apple II using MacOS

Cross Assembly Using Visual Studio Code

VS Code

Apple II development with VS Code


Sometime back I decided to undertake some 6502 assembly language programming to run on my Apple II+ and IIe. Until recently, I had been using Merlin Pro in an Emulator on my MacBook and on the IIe itself. This has worked fine for me previously, however, as my project has grown and the number of source files has increased it is starting to become a little tedious. Therefore, I decided to investigate cross-compiling on my MacBook with automatic deployment to the emulator.

My aim was to develop a simple workflow that would allow me to edit the code on my Mac and provide an automatic means to assemble, deploy and run it in the emulator. The steps I needed to consider were;

  • assemble the code
  • transfer the assembled binary file to a suitable 140k disk image
  • lauch an Apple II emulator with the disk image ‘inserted’
  • run the software in the emulator

This all turned out to be rather straight forward, all that was required was to install and configure the a few software packages and add a couple of very simple bash scripts into the mix. For this post I tried two different cross assemblers each has its merits and I will leave you to decide what suits you best. Configuration details for each are shown below.

The software used was;

  • Visual Studio Code
  • Either Merlin 32 or SBASM cross assembler
  • AppleCommander
  • Virtual ][ Emulator

Software Dependencies

The SBASM cross assembler has a dependency on Python3 and Apple Commander has a dependency on Java. I suspect that most, like me, already have these installed.

Visual Studio Code

https://code.visualstudio.com/

This is a free open source package and runs on most platforms. I have used VSCode in the past for some .Net Core development, it is a great product so I thought I would use it as there is a 6502 syntax highlighting extension (BEEB VSC) that works reasonably well. It also has a task manager that is capable of running the build and test scripts (see below).

Merlin 32

Merlin 32 is a multi-pass Cross Assembler running under Windows, Linux and Mac OS X targeting 8 bit processors in the 6502 series (such as 6502 and 65c02) and the 16 bit 65c816 processor. It is compatible with Glen Bredon’s Merlin 16+ syntax, including support for Macros, Pre-processor, Logical Expressions, Conditional Operations, Variables, Loops, Local Labels etc.

The package is available from Brutal Delux. Expanding the zip file will show the platform dependent binarys and Library (Macro) folder and requires simply that the correct binary and the Library folder be added to the project folder.

To invoke the assembler I created a small bash script called build-assemble. Note that my source is located in a project sub-folder called src.

./Merlin32 -V ./Library ./src/$1.s
mv ./src/sgmail .

The script can be invoked as follows, however later I will describe how this can be handled as a VS Code Task.

./build-assemble sgmail

The parameter sgmail is the name of my main source file (sgmail.asm).

Note the move statement (mv). This is required in my case as the source files are stored in a src folder which is where the compiled binary ends up. What I wanted was for the binary to end up in the folder above ready for the next stage.

SBASM Cross Assembler

http://www.sbprojects.com/sbasm/

This is a free product although, I would ask that you support the author if you feel able to. It requires a manual install, however, it is simple process. In fact in my case I pretty much ignored the instructions and placed all of the files required within my project directory.

After downloading and unzipping the package I created a project directory for my project. The project is called SGMail so, quite naturally that was the name of my project directory. Within this directory I created a bin directory. I copied, from the SBASM package, the sbapack directory and the sbasm file to this bin directory. The headers and opcodes directories were copied from the SBASM package to the root of my project directory (SGMail).

At this point I started converting my source (.asm) files. It took me about 5 minutes using search and replace and a little tweaking, to convert all of my Merlin source files to the SBASM flavour. Only the psuedo opcodes (directives) and the ASC strings needed to be adjusted, although in my case I also adjusted the local lables as the local labels in Merlin are considered to be Macro labels in SBASM.

Note: If you come to convert any merlin ASC directives to the SBASM .AS directive, take a few minutes to understand the subtly different, but often more suitable, .AT directive.

To invoke the assembler I created a small bash script called build-assemble.

#!/bin/bash
python3 ./bin/sbasm src/$1.asm

The script can be invoked as follows, however later I will describe how this can be handled as a VS Code Task.

./build-assemble sgmail

The parameter sgmail is the name of my main source file (sgmail.asm).

AppleCommander

AppleCommander is used to update a disk image with the newly assembled binary in preparation for running in the Virtual ][ emulator.

This is installed using…

I started with a standard bootable ProDos 2.4.1 disk image called SGMail.po and created a small bash script to invoke the process of updating the disk image with the newly assembled binary file. This could be integrated with the above script, however, it would be wise to include some form of exception handling in case something fails during assembly. I chose to keep mine separate as I wanted a two tasks (assemble and test) in VS Code.

#!/bin/bash        
# Add file to disk image (delete old one first)
java -jar /Applications/AppleCommander.app/Contents/Resources/Java/AppleCommander.jar -d $1.po $1
java -jar /Applications/AppleCommander.app/Contents/Resources/Java/AppleCommander.jar -p $1.po $1 bin $2 < $1

The script can be invoked as follows, however, as previously mentioned I will describe how this can be handled as a VS Code Task.

./build-test sgmail 0x8000

The first parameter sgmail is the name of my assembled binary file. The last parameter is the address used in the ORG directive (.OR) within the code (see sample code below). ProDos needs this additional information in order that it can be associated with the file.

Virtual ][ Emulation

This is the MacOS Apple II emulator I chose to use and can be invoked using AppleScript. This is not a free product but is very reasonably priced and can be highly recommended. A small bash script is used to invoke the AppleScript which in turn invokes the emulator. Here is the bash script.

# Load Disk in Emulator and run using AppleScript
osascript "Virtual][Emulation.scpt"

I simply combined this with the above script as follows and called it build-test.

#!/bin/bash        
# Add file to disk image (delete old one first)
java -jar /Applications/AppleCommander.app/Contents/Resources/Java/AppleCommander.jar -d $1.po $1
java -jar /Applications/AppleCommander.app/Contents/Resources/Java/AppleCommander.jar -p $1.po $1 bin $2 < $1

# Load Disk in Emulator and run using AppleScript
osascript "Virtual][Emulation.scpt"

Here is the Virtual][Emulation.scpt as created in the MacOS Script Editor, naturally the paths etc are tailored for my environment.

Script Editor

Script Editor

The script launches the default machine and I have that set up as an Apple II+ as that is what I am currently targeting. The AppleScript can be tailored to launch any specific machine configuration as reqired.

VS Code Tasks

Setting up a build and test task for the build-assemble and build-test bash scripts it fairly straight forward.

I simply edited the tasks.json file (in the .vscode directory) the tasks.json file to be as follows.

{
    // See https://go.microsoft.com/fwlink/?LinkId=733558
    // for the documentation about the tasks.json format

    "version": "0.1.0",
    "command": "",
    "isShellCommand": true,
    "args": [],
    "showOutput": "always",
    "echoCommand": true,
    "suppressTaskName": true,
    "tasks":[
        {
            "taskName": "build-assemble",
            "isBuildCommand": true,
            "command": "./build-assemble",
            "isShellCommand": true,
            "args": ["sgmail"],
            "showOutput":"always"
        },
        {
            "taskName": "build-test",
            "isTestCommand": true,
            "command": "./build-test",
            "isShellCommand": true
            "args": ["sgmail", "0x8000"],
            "showOutput":"always"    
        }
    ]
}

To build (assemble) the code I use the standard VSCode shortcut shift+cmd+B. This assembles the code and reports in the internal terminal.

I created a new shortcut to run the test task shift+cmd+T. This deletes any previous binary from the disk image before adding the newly compiled one, it then launches the Virtual II emulator at 3x speed, inserts the disk, boots to ProDos and invokes the binary.

Naturally the whole process could be automated further but for me this is a very workable solution. Once I am happy with the code in the emulator, the latest disk image can be popped on to the physical machine using something like ADTPro. In my case, I simply copy it to the SD card of a Floppy EMU device.

Enjoy!

Apple IIe RAM Swap

Introduction

This post describes what I think is a fairly simple way to swap the eight soldered RAM chips found on many Apple IIe computers. There are many methods posted on the various forums about how to de-solder the existing RAM, however, I found the following approach using enamelled wire, to be very simple and effective.

Whilst this method did require some soldering skills, it did not require, the harder to obtain, de-soldering skills. Nor did the approach need any special tools apart from a simple 15 Watt soldering iron and some side cutters. Having said that I would always recommend anti-static precautions.

The aim, in my case was to add sockets to the system board so that the new RAM could be plugged in. I found that by selecting a particular socket type, the job became even more straight forward.

Before starting, disconnect the keyboard, speaker, ROM switch (if fitted) and PSU. Remove the system board, this can be done through the open lid, and retire to the bench with a mug of your favourite brew.

Removing the Existing RAM

This can be done most easily using side cutters from the top. Doing it from the top causes each successfully ‘snipped’ lead to spring away from the IC body and makes it very clear when the chip is free. DO NOT put any physical effort into removing the IC or you will most probably remove the track as well. The IC in question should fall away once all leads are cut.

Removing the IC pins is a simple matter using a soldering iron and a pair of tweezers.

If the track does become damaged, this should be faily easy to fix from the underside of the board as many of the pins form the data bus and are simply connected to each IC in turn.

Removing Solder from the Plated Holes

This, I found, was best achieved from the top of the circuit board using some 24swg enamel wire. Enamel wire can easily be found in old transformers and so on, alternatively buy a few meters, it should be worth it.

Heat the top of the hole using the soldering iron, once the solder has properly melted push the end of the length of wire through the hole and keep going for an inch or so. The wire should be pushed through with only a little force but quite quickly. If, as the wire touches the molten solder, the solder solidifies, simply try again but with an extra second or two of heat first. Snip the wire at the top and pull through from the bottom. With the enamelled wire, the solder doesnt stick to it, it is simply pushed/dragged clear of the hole. Repeat this another 127 times and your done. If the hole doesn’t seem to clear of solder, just repeat the process.

The photo of the underside of the board shows how the enamel wire pushes and drags the solder through the hole.

The Sockets

When re-socketing I found that the IC Sockets that worked the best were those where the pin can be removed from the top (see photos). This meant that as I pushed the socket gently into position, any holes that were not quite clear enough would simply push the respective pin proud of the top of the socket. This meant that the socket would sit on the board quite easily with the odd pin sticking up. A dob with the soldering iron underneath whilst pushing any protruding pins down, easily sorts this out. I suspect other socket types would have been a little trickier.

New RAM

I bought a collection of second hand RAM from Steve Buggie (ebay: buggie4vrl) who, as usual, was very helpful. I have noticed that there are several sellers claiming to be selling new stock also.

My machine had 4264 RAM but I fitted 4164 as it was what I had from Steve. The 4264 seems to be compatible with devices needing the 1×64 4164, despite the different internal organisation of memory. The IIe needs 64×1 bit so 4164 should be OK.

The RAM that was removed seemed to be 150ns (4264-15) I replaced with the faster 4124-12 and figured this would be within Apples original spec.

Testing

I tested continuity of the power and data bus connections using a digital multimeter to make sure that no tracks were damaged before popping in the new RAM and reconnecting the system board. The internal diagnostics routine of the IIe was used to check things further followed by some diagnostics software to confirm that all was well. The system now boots up and is a fully working UK Apple IIe.

Conclusion

I found this faily easy using only basic tools, and whilst I am reasonably experienced at soldering, I am no expert.

I know that the IIe is not rare, however, it is still very satisfying to return one to full health for someone to enjoy.

Removing the Bounce from a Rotary Encoder in C++

This code was developed from an idea by Oleg Mazurov and is presented here as a complete class that can be added as a tab in an Arduino sketch. The code will detect forward and reverse movement and will detect if the encoder is turned more quickly.

Hopefully the code is self explanatory with the possible exception of anti-bounce approach taken. Oleg Mazurov has described his work at www.circuitsathome.com. The scaleReduction parameter is a means to control the sensitivity of the rotaion, i.e. a setting of 8 would require 8 clockwise rotation changes before output was reported as a single clockwise rotation.

An example of using this code is shown below with the header and code files shown further below. This particular example was taken from a larger project and used a raw pointer to access the class, there is no requirement to use pointers.

/* ===========================================================================
* Rotary encoder increments for slow/fast turning
* =========================================================================*/
const uint8_t SLOW_INCREMENT = 10;
const uint8_t FAST_INCREMENT = 100;

RotaryEncoder * rotaryEncoder;
double rotValue = 0;

void setup()
{
   rotaryEncoder = new RotaryEncoder(
        ROTARY_ENCODER_SW_PIN,
        ROTARY_ENCODER_CLK_PIN,
        ROTARY_ENCODER_DT_PIN);
   rotaryEncoder->scaleReduction = 2;
}

void loop()
{

  RotaryEncoderState rData = rotaryEncoder->getState();

  int adjustment = SLOW_INCREMENT;

  if (rData.isFast) {
      adjustment = FAST_INCREMENT;
  }

  if (rData.rotation == RotaryEncoderRotationClockwise) {
     rotValue += adjustment;
  }
  else if (rData.rotation == RotaryEncoderRotationAntiClockwise) {
     rotValue -= adjustment;
  }

  if (rData.rotation != RotaryEncoderRotationStationary) {
    //... 
    //
  }
}

RotaryEncoder.h

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <arduino.h>
#include <stdint.h>

/*
 * Encoder Rotation
 */
enum RotaryEncoderRotation {
  RotaryEncoderRotationStationary,  
  RotaryEncoderRotationClockwise,
  RotaryEncoderRotationAntiClockwise
};

/*
 * Encoder State
 */
class RotaryEncoderState {

  public:
    RotaryEncoderRotation rotation;
    bool buttonPressed;
    bool isFast;
};

/*
 * Encoder
 */
class RotaryEncoder {


  public:
    RotaryEncoder (int swPin, int clkPin, int dtPin);
    RotaryEncoderState getState();
    int scaleReduction; //  e.g. a setting of 8 would require 8 clockwise rotation      
                        //  changes before output was reported as a single clockwise

  private:
    int _swPin;
    int _clkPin;
    int _dtPin;
    uint8_t history = 0;
    int clockwiseScaleCounter = 0;
    int antiClockwiseScaleCounter = 0;
    unsigned long _timeStamp = 0;
    RotaryEncoderState _previousState;
    bool isBounce();
    bool isFast();
};

RotaryEncoder.cpp

#include "RotaryEncoder.h"

const byte ENC_STATES[] PROGMEM = {0, -1, 1, 0, 1, 0, 0, -1, -1, 0, 0, 1, 0, 1, -1, 0};
const int BOUNCE_MICROS = 5000;
const long SLOW_MICROS = 80000;

RotaryEncoder::RotaryEncoder(int swPin, int clkPin, int dtPin) {

  //store the pin details
  _swPin = swPin;
  _clkPin = clkPin;
  _dtPin = dtPin;

  //configure the pins
  pinMode(_swPin, INPUT);
  digitalWrite(_swPin, HIGH);

  pinMode(_clkPin, INPUT);
  digitalWrite(_clkPin, HIGH);

  pinMode(_dtPin, INPUT);
  digitalWrite(_dtPin, HIGH);

  _timeStamp = micros();
}

RotaryEncoderState RotaryEncoder::getState()
{
  RotaryEncoderState result;

  //read the status of clk (A) and dt (B) pins
  uint8_t clk = digitalRead(_clkPin);
  uint8_t dt = digitalRead(_dtPin);

  //shift the dt over by one and combine dt and  clk
  clk <<= 1;
  uint8_t clkDt = dt | clk;

  //make room in the history for the new 2 bit combined state
  history <<= 2;

  //add the new state to the two empty low bits
  history |= ( clkDt & 0x03 );

  //based on the low four bits of the history,
  //look up the new status
  //int rotation = encStates[(history & 0x0f)];

  //this is the PROGMEM version of above but is a byte value not int
  int rotation = pgm_read_byte_near(ENC_STATES + (history & 0x0f));

  //default to Stationary
  result.rotation = RotaryEncoderRotationStationary;

  //how long has it been since last rotation
  //unsigned long elapsedTime = micros() - _timeStamp;

  //if clockwise
  if ((int8_t)rotation > 0 && !isBounce()) {

    //factor in the scale reduction
    //works like a reduction drive in a variable capacitor
    clockwiseScaleCounter++;
    antiClockwiseScaleCounter = 0;

    if (clockwiseScaleCounter > scaleReduction) {
      result.rotation = RotaryEncoderRotationClockwise;
      result.isFast = isFast();
      clockwiseScaleCounter = 0;
    }

  }

  //if anti-clockwise unsigned (byte) so 255 is -1
  if ((int8_t)rotation < 0 && !isBounce()) {

    antiClockwiseScaleCounter++;
    clockwiseScaleCounter = 0;

    //factor in the scale reduction
    //works like a reduction drive in a variable capacitor
    if (antiClockwiseScaleCounter > scaleReduction) {
      result.rotation = RotaryEncoderRotationAntiClockwise;
      result.isFast = isFast();
      antiClockwiseScaleCounter = 0;
    }

  }

  //check for a button press, note that this may not work if this function
  //is called from a CLK or DT interrupt
  result.buttonPressed = !digitalRead(_swPin);

  _previousState = result;  
  return  result;

}

bool RotaryEncoder::isBounce(){
  return micros() - _timeStamp < BOUNCE_MICROS;
}

bool RotaryEncoder::isFast(){
  bool result = micros() - _timeStamp < SLOW_MICROS;  
  _timeStamp = micros();
  return result;
}

The Genetic Algorithm Framework – Part 9

UPDATE: This article has now been integrated into the GAF documentation. The documentation can be found here.

Introduction

A question often asked of me is how to determine the encoding of data variables using a binary string, when they are all different units and different ranges of values.

This question is often followed by a question relating to how to ensure that when decoding a binary string, you only have sensible, valid, values.

The questions above can be answered by using something I refer to as normalisation.

Encoding and Decoding

The first point about binary based GAs is that you only need to decode the binary elements to the real values. There is no concept of encoding. If you are not used to GAs this seems rather odd. However, the GA creates all of the solutions based on fitness or some other random effect and is therefore responsible for creating the binary strings. The GA has no knowledge of the values or how they are encoded. All that we have to do is tell the GA how long the binary strings should be. We then, at each generation, take the GA generated binary strings and decode them into real domain values. Once we have the real values, we can evaluate the fitness of each solution and leave the GA to do its work until the next generation.

What normalisation does is simplify the decoding process.

Lets say we have three variables, x, y and z, with the following ranges;

x: -2.5 + 9.5 (range is 12 with an offset of -2.5)
y: 0 to 1000 (range is 1000 with an offset of 0)
x:-50 to 0 (range is 50 with an offset of -50)

Assuming that we are not working with integers we need to determine the resolution i.e. how many values we need between the range. For example, if we are happy with say a million values between the upper and lower values in the ranges, 20 bits per variable will suffice (2^20 = 1048576). Based on this we can determine how many bits each variable will use.

Each variable can have any appropriate number of bits, however, let’s say we use the same bit length of 20 bits for x, y and z. This gives us three values in our chromosome each with a bit length of 20, therefore, we will need a chromosome that is 60 bits long.

The GA will continually generate solutions (chromosomes) 60 bits long. In order to retrieve the real domain values from our chromosome, we use a range constant.

This is calculated as follows;

rangeConstant = range /(System.Math.Pow(2, numberOfBits) - 1);

Here is an example of the range constant approach for x, y and z.

// range constant for x
var rcx =12/(System.Math.Pow(2,20)-1);

// range constant for y
var rcy =1000/(System.Math.Pow(2,20)-1);

// range constant for z
var rcz =50/(System.Math.Pow(2,20)-1);

// when evaluating the fitness simply retrieve the 20 bit values as integers 
// from the chromosome e.g.
var x1 =Convert.ToInt32(chromosome.ToBinaryString(0, 20), 2);
var y1 =Convert.ToInt32(chromosome.ToBinaryString(20, 20), 2);
var z1 =Convert.ToInt32(chromosome.ToBinaryString(40, 20), 2);

// multiply by the appropriate range constant and adjust for any offset 
// in the range to get the real values
double x = (x1 * rcx) - 2.5;
double y = (y1 * rcy);
double y = (y1 * rcz) - 50;

This simple approach ensures that any given binary string will always decode to valid, within range, values for each of our variables. Once we have the real values, we can test for fitness and the GA will do the rest. If you are not used to GAs it can seem a little like magic, to be honest, it probably is.

Enjoy!

Creating WSPR Message in C++

During my recent dabble with a WSPR Beacon on the Arduino I created a C++ class to create the WSPR symbols given the callsign, location and power. The class is suitable for use on all platforms including an Arduino which is just as well, as that is what I wanted it for.

Thanks go to Mark VandeWettering (K6HX) for his work and to Andy Talbot (G4INT) for his help in unraveling the WSPR specification. Most of Andy’s work is reproduced in the code comments.

The code is presented as a C++ class that can be added to any C++ project or simply dropped into an Arduino sketch as a new ‘tab’. It is somewhat over commented but the aim is to try and clarify the WSPR encoding process in the context of a working example.

Error checking is sparse, therefore, please make sure that the callsign location and power are of the appropriate form.

WsprMessage.h

#ifndef WSPR_MESSAGE_H_
#define WSPR_MESSAGE_H_ 

#include &lt;stdio.h&gt;
#include &lt;ctype.h&gt;
#include &lt;string.h&gt;
#include &lt;arduino.h&gt;

#define MSG_SIZE 162

class WsprMessage {

private:

  int getCharValue(unsigned char ch);
  int calculateParity(uint32_t ch);
  unsigned char reverseAddress(unsigned char &reverseAddressIndex);
  unsigned char reverseBits(unsigned char b);
  void generateSymbols(char * callsign, char * location, int power);

public:

  WsprMessage(char * callsign, char * location, int power);
  unsigned char * symbols;
  int size = MSG_SIZE;

};

#endif

WsprMessage.cpp

#include "WsprMessage.h"

/*
162 bit synchronisation vector stored in FLASH with PROGMEM. For
non-arduino simply remove the PROGMEM keyword
*/
const unsigned char sync[] PROGMEM = {

  1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0,
  1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0,
  0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1,
  0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0,
  1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1,
  1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1,
  0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1,
  1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0,
  0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0
  };


WsprMessage::WsprMessage(char * callsign, char * location, int power) {
  generateSymbols(callsign, location, power);
}

void WsprMessage::generateSymbols(char * callsign, char * location, int power) {

  symbols = new unsigned char[MSG_SIZE];

  //=================================================================
  //call sign encoding (28 bits)
  //=================================================================

  /*
    Tidy the call sign and check for 1 or 2 letter prefix.
    Return a 6 char call sign with leading space if neccesary.

    The third character is forced to be always a number, therefore a space is
    prepended as necessary. For example, G6AML will become [sp]G6AML.
  */

  char call[6];
  for (int i = 0; i < 6; i++) call[i] = ' ';

  if (isdigit(callsign[1])) {
    for (int i = 0; i < (int)strlen(callsign); i++)
    call[1 + i] = callsign[i];
  }
  else if (isdigit(callsign[2])) {
    for (int i = 0; i < (int)strlen(callsign); i++)
    call[i] = callsign[i];
  }

  /*
    The 37 allowed characters are allocated values from 0 to 36 such that "0" - "9" give 0 - 9,
    "A" to "Z" give 10 to 35 and [space] is given the value 36. Further coding rules on
    callsigns mean that the final three characters (of the now padded out callsign) can only
    be letters or [sp] so will only take the values 10 to 36. This allows the callsign
    to be becompressed into a single integer 'N'. e.g.

    N1 = [Ch 1] The first character can take on any of the 37 values including[sp],
    N2 = N1 * 36 + [Ch 2] but the second character cannot then be a space so can have 36 values
    N3 = N2 * 10 + [Ch 3] The third character must always be a number, so only 10 values are possible.
    N4 = 27 * N3 + [Ch 4] - 10]
    N5 = 27 * N4 + [Ch 5] - 10] Characters at the end cannot be numbers,
    N6 = 27 * N5 + [Ch 6] - 10] so only 27 values are possible.
  */

  uint32_t N = getCharValue(call[0]);
  N *= 36; N += getCharValue(call[1]);
  N *= 10; N += getCharValue(call[2]);

  //the following can not be numbers so only 27 values are possible
  N *= 27; N += getCharValue(call[3]) - 10;
  N *= 27; N += getCharValue(call[4]) - 10;
  N *= 27; N += getCharValue(call[5]) - 10;

  //=================================================================
  //location encoding (15 bits)
  //=================================================================
  /*
    Designating the four locator characters as[Loc 1] to[Loc 4], the first two can each take
    on the 18 values 'A' to 'R' only so are allocated numbers from 0 - 17. The second pair
    can take only the values 0 - 9.
    Another integer M is formed from :

    M1 = (179 - 10 * [Loc 1] - [Loc 3]) * 180 + 10 * [Loc 2] + [Loc 4]

    Which gives a range of values from 'AA00' = 32220 to 'RR99' = 179, which comfortably
    fit into a 15 bit representation(215 = 32768), leaving spare codes for further
    enhancements.
  */

  uint32_t M1 = (179 - 10 * (location[0] - 'A') - (location[2] - '0')) * 180
    + (10 * (location[1] - 'A')) + (location[3] - '0');

  //=================================================================
  //power encoding (7 bits)
  //=================================================================
  /*
    Power level, [Pwr] is taken as a value from 0 - 60. Although only certain values will work
    with the WSJT / WSPR software(just those ending in 0, 3 or 7) any of the possible 61
    values will be encoded; Illegal values are labeled when decoded. Power is encoded
    into M by : M = M1 * 128 + [Pwr] + 64
  */

  uint32_t M = M1 * 128 + power + 64;

  //Summary: N has call sign (28 bits), M has location and power (22 bits) 

  //=================================================================
  //convolution encoding and interleaving
  //=================================================================
  /*
    The data is now expanded to add FEC with a convolutional
    encoder.

    The 81 bits (including the 31 trailing zeros) are  are clocked simultaneously into the
    right hand side, or least significant position, of a 32 bit shift register.
    The shift register feeds an ExclusiveOR parity generator from feedback taps described
    respectively by the 32 bit values 0xF2D05351 and 0xE4613C47.

    Parity generation starts immediately the first bit appears in the registers and continues
    until the registers are flushed by the final 31st zero being clocked into them. 

    Each of the 81 bits shifted in generates a parity bit
    from each of the generators, a total of 162 bits in all.For each bit shifted in,
    the resulting two parity bits are taken in turn, in the order the two feedback tap
    positions values are given, to give a stream of 162 output bits.

    The interleaving process is performed by taking a bit reversal of the address (array index)
    to reorder them.
  */

  int i;
  uint32_t reg = 0;
  unsigned char reverseAddressIndex = 0;

  /*
    We need to merge the source with the synchronisation bits
    so transfer these accross first as this allows us to merge,
    encode and interleave at the same time
  */
  for (i = 0; i < MSG_SIZE; i++) {

      //For non-arduino simply replace the following statement
      //the one below        
    symbols[i] = pgm_read_byte(sync + i);
    //symbols[i] = sync[i];
  }

  //move N (callsign) into the symbols byte array
  for (i = 27; i >= 0; i--) {

    //make room for the next register bit
    reg <<= 1; // same as reg = reg << 1

      //if bit 'i' of Nc (call sign) is a '1', set LSB of the register
    //with the bitwise OR operator
    if (N & ((uint32_t)1 << i)) reg |= 1;

    /*
      These next two lines add the parity data to the symbols array
      but in the interleved order using a reverse of the address
      the constant values (feedback taps) come directly from the
      specification.
    */
    symbols[reverseAddress(reverseAddressIndex)] += 2 * calculateParity(reg & 0xf2d05351L);
    symbols[reverseAddress(reverseAddressIndex)] += 2 * calculateParity(reg & 0xe4613c47L);

  }

  //the register (reg) should be maintained ready for the next loop

  //move M (location and power) into the symbols array in the same way
  //as N above
  for (i = 21; i >= 0; i--) {
    reg <<= 1;
    if (M & ((uint32_t)1 << i)) reg |= 1;
    symbols[reverseAddress(reverseAddressIndex)] += 2 * calculateParity(reg & 0xf2d05351L);
    symbols[reverseAddress(reverseAddressIndex)] += 2 * calculateParity(reg & 0xe4613c47L);
  }

  //pad with 31 zero bits
  for (i = 30; i >= 0; i--) {
    reg <<= 1;
    symbols[reverseAddress(reverseAddressIndex)] += 2 * calculateParity(reg & 0xf2d05351L);
    symbols[reverseAddress(reverseAddressIndex)] += 2 * calculateParity(reg & 0xe4613c47L);
  }

}

int WsprMessage::getCharValue(unsigned char ch)
{
  if (isdigit(ch)) return ch - '0';
  if (isalpha(ch)) return 10 + toupper(ch) - 'A';
  if (ch == ' ') return 36;

  //if we get to here then call sign is no good
  //throw exception;
  return 0;
}

unsigned char WsprMessage::reverseAddress(unsigned char &reverseAddressIndex) {

  /*
    The index of each bit within the 162 bit message is passed
    to this function and the bits are reversed.

    E.g. 1 becomes 128 2 become 64 etc. Where the reversed
    value is greater than 161 it is ignored and we move the index
    on. For example bit 3 would becom 192 when reversed, therefore
    we move on and use the value 4 for bit 3 and 5 for bit 4
    and so on. e have 255 addresses we can use to get the 162 address
    values we need.
  */
  unsigned char result = reverseBits(reverseAddressIndex++);

  while (result > 161) {
    result = reverseBits(reverseAddressIndex++);
  }
  return result;
}

unsigned char WsprMessage::reverseBits(unsigned char b) {

  /*
    This function reverses the bits in a byte. I.e. 1 becomes
    128, 2 becomes 64, 3 becomes 192 and so on.

    The left four bits are swapped with the right four bits,
    all adjacent pairs are swapped, all adjacent single bits
    are swapped.

    Thanks to http://stackoverflow.com/users/56338/sth for
    this snippet of code
  */
  b = (b & 0xF0) >> 4 | (b & 0x0F) << 4;
  b = (b & 0xCC) >> 2 | (b & 0x33) << 2;
  b = (b & 0xAA) >> 1 | (b & 0x55) << 1;

  return b;
}

int WsprMessage::calculateParity(uint32_t x)
{
  //generate XOR parity bit (returned as 0 or 1)
  int even = 0;
  while (x) {
    even = 1 - even;
    x = x & (x - 1);
  }
  return even;
}

The Genetic Algorithm Framework – Part 8

UPDATE: This article has now been integrated into the GAF documentation. The documentation can be found here.

Introduction

A piece of research completed in conjunction with the De Montfort University in 2013 demonstrated how the Genetic Algorithm Framework (GAF) could be used with a Software Defined Radio (SDR) system, to provide automatic frequency control (AFC).

The aim of AFC is to ensure that a radio system stays tuned to the desired frequency in conditions where the frequency is subject to change. The research demonstrated that a genetic algorithm (GA) can perform this task. In addition, the research showed how the GA can also handle very large changes in frequency such as the channel hopping nature of Cognitive Radio systems.

During the research, a Memory Operator was used in conjunction with an Auto-Mutate operator in order to improve the algorithm. The operator was subsequently added to the Genetic Algorithm Framework (GAF). This post describes how the can be used to improve GA performance.

How it Works

The operator maintains a ‘memory’ of solutions and ensures that the best solution in that memory is included in the GA population if it is better than the best in the population. The memory is kept up to date with good solutions during the GA run.

An Example

In an intelligent radio system such as the one described in the research cited above, a GA is used to search for and track a radio signal that is jumping around the radio spectrum (channel hopping). A GA without the memory operator needs to re-converge on the new frequency for each channel hop of the radio transmitter. Adding the memory operator tries to ensures that if a channel is reused it will be found in memory and will be added to the population causing the GA to instantly converge on the new frequency. If the current channel hasn’t been used before, the GA will try and converge in the normal manner.

If the GA landscape is constantly changing such that the GA has to re-converge on a new solution, the memory operator could be used to improve the performance. As with all of these things experimentation will determine the best usage.

The following code adds the memory operator to the GA, sets the memory capacity to 100 ‘memories’ and specifies that the memory will be updated every 10 generations. The code may be more easily understood if read in conjunction with articles GAF Part 2 and GAF Part 3

var memory = new Memory(100, 10);
ga.Operators.Add(memory);

Whispering to the World using a Raspberry Pi

Introduction

This was a quick and dirty experiment to try and turn a Raspbeerry Pi into a shortwave transmitter. The aim was transmit a digital Weak Signal Propagation message (WSPR pronounced Whisper) on the 20 metre (14Mhz) Amateur Radio band using only a Raspberry Pi, a low pass filter and a length of wire as an aerial.

WSPR (Weak Signal Propogation)

WSPR implements a protocol designed for probing potential propagation paths with low-power transmissions. Normal transmissions carry a station’s callsign, Maidenhead grid locator, and transmitter power in dBm. The protocol is such that messages can be decoded with S/N as low as -28 dB in a 2500 Hz bandwidth. Stations with internet access can automatically upload their reception reports to a central database called WSPRnet, which includes a mapping facility. A live version of the map can be seen here.

The Raspberry Pi

There are numerous examples on the Internet of transmitting signals by simply attaching an aerial to the clock O/P pin of the Pi. However, for this experiment I used the WsprryPi software.

The WsprryPi software make light work of controlling the Raspberry Pi Clock output. The software controls the radio frequency, in this case 14.097120 MHz, and then modulates this with the WSPR radio data. Full details of how this works is given here.

The Low Pass Filter

The clock output is a square wave, therefore, a low pass filter is required to reduce the harmonic transmissions. This was constructed using this GQRP Club article as a guide.

The low pass filter was built using islands on a copper clad board. There are many examples on the Internet of how to build a suitable tool to create these islands, however, I find that a standard unmodified wood drill (the type shown in the photo) works very well and keeps things very simple. Start by drilling a 3mm pilot hole and then pop the wood drill into the hole and watch the island appear as the drill turns.

A
B
C

The image here shows the completed low pass filter with its input connected to the clock output of the Pi, and its output connected to a 5 meter length of wire laid out on the patio.

Results

The WsprryPi software was used to transmit my call sign (G6AML) and my Maidenhead locator square (IO83XX). Within a very short time I was heard by DK6UG in Germany, EW1LN in Belarus and LA9JO in the north of Norway. Awesome!

WsprNet.org

Thank you to the many amateurs around the globe who have WSPR receiving stations setup. These stations send what they have heared, to a central database at WsprNet.org. The map is a great way to see how far these signals have traveled.