February 2011 Archives

I've been studying up to take my Amateur Radio License exam, and was kind of intrigued to read about the different ways ham operators send digital data.  It got me to thinking that it might be fun to try some modulation/demodulation trickery on my own, just to see what I could do with very little effort.  In the spirit of ham radio, and because the FCC doesn't allow coded transmissions on Amateur Radio (you can modulate data, but you have to make it public how you're doing it), I present a strategy I'm calling Harmonic Relative Amplitude Modulation 8.  I suppose you could call it HRAM8 if you wanted.  I haven't researched to see if anyone else is modulating signals this way; it's entirely possible this isn't even my idea.  But it's a nice way to learn about generating complex waves and demodulating them with Fast Fourier Transforms in Java.

First a few design principles.  I wanted to do something very simple that anyone could implement easily.  I also wanted it to sound pleasing to the ear, having lived through far too many years of annoying fax and modem communications.  I wanted it to be reasonably robust, though it needn't be perfect.  And I wanted to keep the bandwidth under 1kHz, while maximizing throughput.

I came up with a strategy in which I assign a base frequency and base amplitude, and associate the base frequency and its harmonics with bits 0-7 of a byte.  If a bit is set to 1, its amplitude is 4 times the base amplitude, otherwise its amplitude is the base amplitude.

I opted not to use a clock of any kind, deciding instead to simply observe when bit patterns change.  This proved to be problematic, given words like "mucopolysaccharides" which have repeating characters.  On the first repeat, the "clock" is lost.

In keeping with my design principles, I opted for a simple and easy solution: I added a parity bit.  The parity mode switches between even parity and odd parity with every character; even numbered characters get even parity and odd numbered characters get odd parity.  So even if characters repeat, the bit pattern will change by at least 1 bit every time.  I'm not currently testing the parity bit to report errors; that is yet to come.

Each byte is modulated long enough to ensure proper transformation with FFT, which turns out to be two times the base frequency.  In my present naive demodulation strategy, I simple scroll through the sample data at half the width of a single character, looking for bit patterns to change.  When receiving a random signal off-air, this probably would not be adequate and a better strategy would need to be devised to be sure demodulation began at the start of a new character.  I'm also thinking of having a "sync character" after every 32-byte frame, so if things go out of sync, they won't do it for more than 32 bytes.

I'm using the excellent JTransforms library for Java to do the FFT along with a fairly slow sample rate and small FFT window size to make the FFT computations very quick.  Fortunately the harmonics are spaced out well enough that this relatively low fidelity is adequate.

Without further ado, how about some code?

package net.spatula.sandbox;

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.nio.ByteBuffer;
import java.nio.ShortBuffer;

import javax.sound.sampled.AudioFormat;
import javax.sound.sampled.AudioInputStream;
import javax.sound.sampled.AudioSystem;
import javax.sound.sampled.DataLine;
import javax.sound.sampled.LineUnavailableException;
import javax.sound.sampled.SourceDataLine;

import edu.emory.mathcs.jtransforms.fft.FloatFFT_1D;

public class Sandbox {
	private static final int NUMBER_OF_CHANNELS = 1;
	private static final int BITS_PER_SAMPLE = 16;
	private static final int BIT_SET_MULTIPLIER = 4;
	private static final int BITS_PER_WORD = 8;
	private static final int SAMPLE_RATE = 8000; // 44100 if you want a really nice, clean sin wave, but then you must change FFT_SIZE to at least 16384 too
	private static final int BYTES_PER_SAMPLE = 2;
	private static final int BASE_FREQUENCY = 110;
	private static final int FRAME_SIZE = 32;
	private static final int SAMPLES_PER_CHARACTER = SAMPLE_RATE / BASE_FREQUENCY * 2;
	private static final double BASE_AMPLITUDE = 4095;
	private static final int FFT_SIZE = 4096; // 16384 if you use 44100 as the sample rate. FFT happens faster with smaller sizes.

	public void modulate(String string) throws LineUnavailableException, IOException {

		byte[] buffer = new byte[FRAME_SIZE * SAMPLES_PER_CHARACTER * BYTES_PER_SAMPLE];
		ByteBuffer byteBuffer = ByteBuffer.wrap(buffer);
		ShortBuffer shortBuffer = byteBuffer.asShortBuffer();

		for (int i = 0; i < string.length() && i < FRAME_SIZE; i++)
		{
			byte byteToModulate = (byte) string.charAt(i);

			modulateByte(shortBuffer, byteToModulate, i % 2 == 0);
		}

		playByteArray(buffer);

		demodulateSampleBuffer(shortBuffer);
	}

	private void modulateByte(ShortBuffer shortBuffer, byte byteToModulate, boolean even) {
		for (int sampleCount = 0; sampleCount < SAMPLES_PER_CHARACTER; sampleCount++)
		{
			double time = (double) sampleCount / (double) SAMPLE_RATE;
			double sampleValue = 0;
			int oneBits = 0;

			// sum the signals for each bit
			for (int bitNumber = 0; bitNumber < BITS_PER_WORD; bitNumber++)
			{
				boolean bitSet = ((byteToModulate & (byte) (Math.pow(2, bitNumber))) != 0);
				if (bitSet)
				{
					oneBits++;
				}
				sampleValue += Math.sin(2 * Math.PI * BASE_FREQUENCY * (bitNumber + 1) * time) * BASE_AMPLITUDE * (bitSet ? BIT_SET_MULTIPLIER : 1);
			}

			// add in the parity bit
			boolean setParity = ((even && (oneBits % 2 != 0)) || (!even && (oneBits % 2 == 0)));
			sampleValue += Math.sin(2 * Math.PI * BASE_FREQUENCY * (BITS_PER_WORD + 1) * time) * BASE_AMPLITUDE * (setParity ? BIT_SET_MULTIPLIER : 1);

			// average the signals
			sampleValue /= (BITS_PER_WORD + 1);
			shortBuffer.put((short) sampleValue);
		}
	}

	private void playByteArray(byte[] buffer) throws LineUnavailableException, IOException {
		InputStream is = new ByteArrayInputStream(buffer);
		AudioFormat audioFormat = new AudioFormat(SAMPLE_RATE, BITS_PER_SAMPLE, NUMBER_OF_CHANNELS, true, true);
		AudioInputStream ais = new AudioInputStream(is, audioFormat, buffer.length / audioFormat.getFrameSize());
		DataLine.Info dataLineInfo = new DataLine.Info(SourceDataLine.class, audioFormat);
		SourceDataLine sourceDataLine = (SourceDataLine) AudioSystem.getLine(dataLineInfo);

		sourceDataLine.open();
		sourceDataLine.start();

		byte[] playBuffer = new byte[buffer.length];
		int bytesRead;
		while ((bytesRead = ais.read(playBuffer, 0, playBuffer.length)) != -1)
		{
			sourceDataLine.write(playBuffer, 0, bytesRead);
		}
		sourceDataLine.drain();
		sourceDataLine.stop();
		sourceDataLine.close();
	}

	private void demodulateSampleBuffer(ShortBuffer shortBuffer) {
		DemodulatedCharacter lastChar = null;
		for (int i = 0; i < shortBuffer.capacity(); i += SAMPLES_PER_CHARACTER / 2)
		{
			DemodulatedCharacter nextChar = demodulateCharacter(shortBuffer, i, SAMPLES_PER_CHARACTER / 2);
			if (!nextChar.equals(lastChar))
			{
				lastChar = nextChar;
				System.out.print(nextChar);
			}
		}
		System.out.println();
	}

	private DemodulatedCharacter demodulateCharacter(ShortBuffer shortBuffer, int offset, int length) {
		float[] floatArray = new float[FFT_SIZE * 2];
		for (int i = offset; i < shortBuffer.capacity() && i < offset + length; i++)
		{
			floatArray[i - offset] = shortBuffer.get(i);
		}

		FloatFFT_1D fft = new FloatFFT_1D(FFT_SIZE);
		fft.realForward(floatArray);

		int multiplier = (int) (BASE_FREQUENCY / ((float) SAMPLE_RATE / (float) FFT_SIZE));

		long maxPower = findMaxPower(floatArray, multiplier);

		int value = 0;
		for (int i = 0; i < BITS_PER_WORD; i++)
		{
			int index = (i + 1) * multiplier;
			long power = computePowerAtIndex(floatArray, index);
			if (power > (maxPower / (BIT_SET_MULTIPLIER / 2)))
			{
				value += Math.pow(2, i);
			}
		}

		DemodulatedCharacter character = new DemodulatedCharacter();
		character.setData((char) value);

		long parityPower = computePowerAtIndex(floatArray, (BITS_PER_WORD + 1) * multiplier);
		if (parityPower > (maxPower / (BIT_SET_MULTIPLIER / 2)))
		{
			character.setParity(true);
		}

		return character;

	}

	private long findMaxPower(float[] floatArray, int multiplier) {
		long maxPower = 0;
		for (int i = 0; i < BITS_PER_WORD; i++)
		{
			int index = (i + 1) * multiplier;
			long power = computePowerAtIndex(floatArray, index);
			if (power > maxPower)
			{
				maxPower = power;
			}
		}
		return maxPower;
	}

	private long computePowerAtIndex(float[] floatArray, int index) {
		return (long) Math.sqrt(Math.pow(floatArray[index * 2], 2) + Math.pow(floatArray[index * 2 + 1], 2));
	}

	private static class DemodulatedCharacter {
		private char data;
		private boolean parity;

		public char getData() {
			return data;
		}

		public void setData(char data) {
			this.data = data;
		}

		public boolean isParity() {
			return parity;
		}

		public void setParity(boolean parity) {
			this.parity = parity;
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + data;
			result = prime * result + (parity ? 1231 : 1237);
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			DemodulatedCharacter other = (DemodulatedCharacter) obj;
			if (data != other.data)
				return false;
			if (parity != other.parity)
				return false;
			return true;
		}

		@Override
		public String toString() {
			return String.valueOf(getData());
		}
	}

	/**
	 * @param args
	 * @throws LineUnavailableException
	 * @throws IOException
	 */
	public static void main(String[] args) throws LineUnavailableException, IOException {

		new Sandbox().modulate(args[0]);
	}

}