I’ve had this idea for a few days now that I wanted to implement where I rearrange data so that an unstable frequency doesn’t risk destroying the whole packet – especially if there are two or more sequential streams that are bad since that affects error correction. I have found that this is called interleaving and is often implemented to minimize bursts of noise from affecting the data stream.

Data	Sequential	Interleaving
Bit 0	Channel 0	Channel 0
Bit 1	Channel 1	Channel 8
Bit 2	Channel 2	Channel 1
Bit 3	Channel 3	Channel 9
Bit 4	Channel 4	Channel 2
Bit 5	Channel 5	Channel 10
Bit 6	Channel 6	Channel 3
Bit 7	Channel 7	Channel 11
Bit 8	Channel 8	Channel 4
Bit 9	Channel 9	Channel 12
Bit 10	Channel 10	Channel 5
Bit 11	Channel 11	Channel 13
Bit 12	Channel 12	Channel 6
Bit 13	Channel 13	Channel 14
Bit 14	Channel 14	Channel 7
Bit 15	Channel 15	Channel 15

So now our bits are in a pseudo random order where two failing frequencies side by side will have less effect on preventing errors from being recovered – thus adding an additional layer of error protection since I may still have enough uncorrupted information to recover without requesting the packet again.

As an example, if “noise” is affecting channels 5 and 6, it can affect both bits 5 & 6 in sequential order. With two errors, the Hamming Code for error correction couldn’t recover from the error. With interleaving, the corrupted frequencies are spread apart with Bits 10 and 3 – two separate hamming codes (7 bits long). A hamming code can recover the original data when only one bit is wrong.

It’s still sequential if you just look at the odd bits or even bits, but it’s a start to spreading out the bits to avoid the noise. I want to go a bit further into a pseudo random pattern to scatter the bits, but let’s just add in a layer of interleaving and see what effect it has.

First, let’s find a frequency that is known to have problems. Usually the low frequencies have a problem. We specifically want to find two frequencies close together that have a high failure rate.

Channels 0 and 2 have a few failures with this scheme. Being so close together, they would affect the hamming code error corrections capability of recovering. It is of particular note that Channel 2 doesn’t fail as often when I do repeated tests. Speaking/Singing into the microphone during transfer helps introduce errors in the lower frequency ranges.

Segment Duration	30ms
Minimum Frequency	80 Hz
Maximum Frequency	18,017 Hz
FFT Size	2 ^ 9
Frequency Resolution Multiplier	2 Bins
Channel Frequency Resolution Padding	2 Bins
Smoothing Time Constant	0 Audio Frames
Hamming Code Error Correction	Yes

Here is what I came up with to interleave the odd bits:

function applyInterleaving(bits) {
  const channels = getChannels();
  const channelCount = channels.length;
  // We need at least 4 channels to swap odd numbered bits
  if(channelCount < 4) return bits;
  // Determine what the center channel index is
  const centerIndex = Math.floor(channelCount / 2);
  if(centerIndex % 2 === 1) centerIndex++;

  // ensure last segment has enough bits to swap
  while(bits.length % channelCount !== 0) bits.push(0);

  // Loop through each segment
  for(let i = 0; i < bits.length; i+= channelCount) {

    // Grab the bits for the segment
    const segment = bits.slice(i, i + channelCount);

    // Loop through the odd bits up to the center channel
    for(let fromIndex = 1; fromIndex < centerIndex; fromIndex += 2) {
      // Identify the target bit to swap
      const targetIndex = (fromIndex + centerIndex);

      // remember the bits
      const bitA = segment[fromIndex];
      const bitB = segment[targetIndex];

      // swap the bits
      segment[targetIndex] = bitA;
      segment[fromIndex] = bitB;
    }

    // update the bits with the modified segment
    bits.splice(i, channelCount, ...segment);
  }
  return bits;
}

That’s all good, but now my data has a high error rate of 30%. I also need to remove the interleaving. Wait… could it be this simple? Can I just call the same function?

function removeInterleaving(bits) {
  return applyInterleaving(bits);
}

What do you know… it works! My low channels were very noisy. Two channels sitting next to each other. It can’t be good for error correction. Although the error percent rate of incoming bits was at 4.5%, the actual data that was corrected only had an error rate of 0.2%. Without periodic interlacing, I had a similar error rates at 4.2%, but it was only able to correct data to have a 2.5% error rate. Interlacing works!

With the hamming error codes, I need bits to swap with others at least 7 places away. This is doable with 14 channels or more. Now I’m wondering if I should change the bit swapping with each segment so that sometimes it swaps 7 places, others it can swap 12 places. This is where we get into pseudo random interlacing where the pattern changes based on the segment index being evaluated. The other option would be to stagger within the same segment, so that instead of every other bit being swapped, we could swap every 2nd and 3rd bit 8 places and 16 places over. This would address situations where a burst of noise would affect 3 or more channels. It’s all about scattering the bits across the spectrum to give error correction the best chance to recover.

I’m trying to think this through. Without error correction, interleaving isn’t useful on its own. It’s effectiveness is based on the block size of the error correction. In this case, we have a block size of 7, which protects 4 bits of data. This means that if I have no more than seven channels, interleaving doesn’t help because – where else is that bit going to go where both it and its replacement are not affected by the noise? With only 8 channels, only one bit is able to escape the block – and we hope that’s the one that was affected. So the focus is to spread out as many bits as we can across the spectrum based on the error correction block size. However… if we introduce time, more bits have a chance to escape the noise. This would cause us to group segments in our packets where the bits would be scattered within that group.

Ack, what a nightmare. I finally got it. I separated out the swapping of bits for an individual segment into its own function. I also had to include an “undo” flag so I knew which direction to move the bits.

function removeInterleaving(bits) {
  return applyInterleaving(bits, true);
}
function applyInterleaving(bits, undo = false) {
  // Not turned on
  if(!PERIODIC_INTERLEAVING) return bits;

  // Only applicable for error correction
  if(!HAMMING_ERROR_CORRECTION) return bits;

  const channels = getChannels();
  const channelCount = channels.length;

  // We need at least 1 extra channel for one bit to escape the block
  if(channelCount < ERROR_CORRECTION_BLOCK_SIZE + 1) return bits;

  const blockCount = Math.ceil(channelCount / ERROR_CORRECTION_BLOCK_SIZE);
  // need another block to swap bits with
  if(blockCount < 2) return bits;

  // ensure last segment has enough bits to swap
  while(bits.length % channelCount !== 0) bits.push(0);

  // Loop through each segment
  for(let i = 0; i < bits.length; i+= channelCount) {

    // Grab the bits for the segment
    let segment = bits.slice(i, i + channelCount);
    segment = staggerValues(segment, ERROR_CORRECTION_BLOCK_SIZE, undo);

    // update the bits with the modified segment
    bits.splice(i, channelCount, ...segment);
  }
  return bits;
}

function staggerValues(values, blockSize, undo) {
  // loop through bit indexes of a block
  for(let blockMovement = 1; blockMovement < blockSize; blockMovement++) {
    values.filter((_, i) =>
      // values to be moved to different blocks
      i % blockSize === blockMovement
    ).map((_,i,a) => {
      // bit values moved N blocks
      if(undo) i -= blockMovement; else i += blockMovement;
      i = ((i % a.length) + a.length) % a.length;
      return a[i];
    }).forEach((v, i) => {
      // replace with new values
      values[blockMovement + (i * blockSize)] = v;
    })
  };
  return values;
}

In a nut shell, I’m trying to swap the values into as many separate error correction blocks as I can. With 24 channels, it’s just over 3 blocks. The fraction of the blocks made it a bit more difficult as well. In the end, I decided to simplify things and just grab all of the numbers that I wanted to move X blocks to the right (or left to reverse the interlace). The amount of movement changes with each bit. Bit 0 doesn’t move at all. Bit 1 moves 1 block. Bit 2 moves 2 blocks, and so on. I then mapped what the new numbers would be in the shifted array. Anything that moves too far to the right or left will wrap around to the other side. Finally, I looped through each of the moved values and put the newly ordered values back into the original array in the same place that I got the original values.

Channel	Sequential Error Block	Sequential Bit	Interleaved Bit	Interleaved Error Block
0	0	0	0	0
1	0	1	8	1
2	0	2	16	2
3	0	3	3	0
4	0	4	11	1
5	0	5	19	2
6	0	6	6	0
7	1	7	7	1
8	1	8	15	2
9	1	9	23	3
10	1	10	10	1
11	1	11	18	2
12	1	12	5	0
13	1	13	13	1
14	2	14	14	2
15	2	15	22	3
16	2	16	2	0
17	2	17	17	2
18	2	18	4	0
19	2	19	12	1
20	2	20	20	2
21	3	21	21	3
22	3	22	1	0
23	3	23	9	1

For a transfer using 24 channels, the initial interlacing spread out the block of bits between 2 blocks (sometimes 3). This version spreads the bits into all 3.42 blocks for the best case scenario. If I add more channels, it will spread the bits out across more blocks.

Normally my error percent rate for the decoded bits is close to the error percent rate of the received bits. With the application of interlacing, my decoded bits have have an overall error rate reduced by 90%.

Received Errors Interleaving	Decoded Errors Interleaving	Received Errors Non-Interleaving	Decoded Errors Non-Interleaving
3.1%	0.4%	4.3%	1.6%
2.1%	0.4%	3.4%	1.1%
3.2%	0.4%	2.9%	0.7%
2.6%	0.8%	3.1%	0.5%
2.4%	0.0%	3.5%	1.7%
2.6%	0.1%	5.7%	3.0%
2.3%	0.2%	3.3%	0.6%
3.2%	0.2%	3.6%	1.3%
3.3%	0.7%	2.7%	0.2%
3.6%	0.8%	4.2%	1.8%
2.84%	0.4%	3.67%	1.25%

It’s a small sample set, and the non-interleaving average is a bit higher than interleaving with the received errors. My main focus however, is on the decoded error percentage dropping much further with interleaving. The chance of having the full data intact is much higher.

So here is the next problem I’m thinking of. Two random channels have a problem with data for the entire transfer. Just by chance, the new order to spread data across the spectrum affects two bits in in the same error checking block. All blocks using these to frequencies are fixed to the bad channels Is there something more I can do to prevent that? Maybe I can swap bits in different patterns with each segment index. What’s even worse is the thought that the channel count is not divisible by 7. The last few bits wrap around to the next segment, potentially causing a problem with more bits in the same bad frequencies.

I found something called Time-Varying Interlacing/Interleaving used to increase resistance to interference or jamming. This sounds like what I’m looking for. Most of what I’m seeing is that the frequencies themselves change (aka frequency hopping) rather than the bits being swapped with other bits being sent on different frequencies. Should I work on swapping the bits with each successive segment, or should I swap channel frequencies? I could swap the channel frequencies in the middle of a segment, or after N segments. If I do it in the middle of a segment, Each bit may be transferred over a more stable signal that improves its ability to recover alone – even without error correction. This really would be the essence of frequency hopping since rather than just swapping frequencies between channels, I could also change the underlying frequencies themselves.

Before we move on to that, I had changed the waveform to sawtooth the other day. I didn’t do any testing with various wave forms. Let’s make it changeable in the UI and do some testing. I’m going to bump up the minimum frequency to skip past frequency that causes problems. I started the frequencies at 400 Hz. The lower channel was no longer an issue, but a channel using 14,650 Hz and 14,837 Hz was often receiving the wrong data. I think it affected my test greatly.

Wave Form	Sawtooth	Sine	Square	Triangle
	0.8%	1.3%	3.6%	0.3%
	3.8%	4.4%	0.8%	1.0%
	1.6%	0.6%	1.6%	0.7%
	1.4%	0.3%	0.1%	0.9%
	2.1%	0.7%	0.7%	0.4%
	1.8%	2.5%	2.9%	0.9%
	2.5%	0.6%	2.0%	0.6%
	1.7%	1.0%	3.5%	1.4%
	1.2%	1.8%	0.6%	0.7%
	1.9%	0.9%	2.7%	2.2%
Minimum	0.8%	0.3%	0.1%	0.3%
Average	1.88%	1.41%	1.85%	0.91%
Median	1.7%	0.9%	1.6%	0.7%
Maximum	3.8%	4.4%	3.6%	2.2%

It loos like the triangle wave form may be the most optimal followed by a sine wave. I could be wrong. I’ve only ran 10 tests, and some of them had some pretty high error rates near 4%. The best run was with the square wave with a 0.1% error rate. I’ll stick with defaulting to the triangle wave moving forward.

Back to the spread of bits over time. The main thing is that I still want my bits to be spread out between the various blocks to prevent noise across sequential channels from affecting the signal. If I swap channels halfway through a segment, will that have an effect? Will the bit have a better chance at evaluating correctly? Should I swap three times during a segment so that it has 66% of “good” data if one of the channel frequencies is bad?

First off, anything less than 30ms is going to be problematic. 30ms gets us between 6 and 11 samples. Changing to swap frequencies every 10ms might work, but our lower frequencies would be affected. This would be similar to transferring at 10ms – except if we don’t capture a sample during a specific 10ms frequency change, it wouldn’t affect our overall bit duration since additional samples can be captured in the other 20ms of the full 30ms duration on other frequencies. Still – the 10ms samples are often plagued with errors at a high rate of 25 to 35%. I’m not sure if I want to go down that rabbit hole.

I think maybe the best way of doing things would be to just offset the channels by seven as each segment of bits comes in.

movement = (segmentIndex + seven) % channel count

But will this help?

Let’s come back to it later. What we’ve got now is pretty good in terms of how well it improved our capability of error correction. The main problem I see now is that specific channels tend to have errors. I don’t know why, but it would be nice if I could select the channel and exclude it from being used, and work with the remaining channels.

I already write out a list of channels. Let’s wire them up with checkboxes.

That was simple enough. Although the channel numbers on the graph don’t skip the un-checked channels. Instead they go from 0 to 17.

It was simple enough to create a function that receives a channel number and inflates it based on the excluded channel numbers.

function realChannel(id) {
  EXCLUDED_CHANNELS.sort(compareNumbers);
  for(let i = 0; i < EXCLUDED_CHANNELS.length; i++) {
    if(EXCLUDED_CHANNELS[i] <= id) id++;
  }
  return id;
}

Is that all? No. I also need to apply the fix to the selected data so that it shows the “real” channel number when I select channel 4 on the graph.

Now we are getting near perfect transfers! Now this is really cool I’ve got a baud rate of 1300 with an effective rate of 742. That’s ridiculous! That’s faster than a 1200 baud modem! That’s half the speed of my first modem in 1991. I’m just playing the signal over and over again and hiding channels that have too many errors. I’m now consistently getting error rates under 1%.

Configuration	Setting	Info	Value
Wave Form	Triangle	Baud	1,300
Segment Duration	30ms	Effective Baud	742.86
Amplitude Threshold	75	Channels	39
Minimum Frequency	461	Available Channels	51
Maximum Frequency	14,650
Last Segment Percent	60%
FFT Size	2^9
Frequency Resolution Multiplier	1
Channel Frequency Resolution Padding	1
Smoothing Time Constant	0
Periodic Interleaving	Yes
Hamming Code Error Correction	Yes
Excluded Channels	2, 4, 5, 10, 21, 23, 28, 35, 36, 38, 39, 42

I think the next thing to do is to look into compression. With such a small packet size, it may not be beneficial. Compression methods to look into would be run-length encoding (RLE), Huffman coding, or delta encoding. I’m looking for something quick and easy to implement. RLE seems to be better suited if I have multiple characters being repeated. My tests consist of 128 random printable ascii characters (97 in all) in the lower-ascii table. Although the characters aren’t repeated, the fact that there are limited number of unique characters may help. Huffman is better if words are repeated. Again – my data is randomized, so it doesn’t look like readable text, so maybe Huffman isn’t a good idea.

I started a bit more research into Huffman and saw an excellent video of how to do it with pencil and paper.

From this, it may be simpler to pull of then I had thought. At most, I would have 97 symbols. That helps. The fact that the most frequent symbol could potentially be represented by just 1 bit is exciting. I think I would need to include the symbols and frequencies themselves. If all 94 characters are used in a 128 byte data stream, I’m having doubts it may not work out. What I could do is evaluate the compression to determine if it would be beneficial. If so – send a flag indicating the stream has been compressed. Otherwise, leave as-is.

It is getting fairly late, so I think I’ll leave compression for tomorrow.