We can now transfer binary files with our little air wobbler. With 487 bytes, it’s rare that all of the bits come through perfectly. Even with error recovery and interleaving across the audio spectrum, it’s still a rare occurrence to receive everything in proper order. We currently have the ability to know if the the underlying data did not come through perfectly with cyclic redundancy checks (CRC). This lets us know that we need to try again. However – as files get larger, we are wasting more and more time retransmitting everything.

Splitting the data into multiple packets was done as a lead-in to recovery. We need to add CRC checks into individual packets. This will give us the ability to detect which packets need to be retransmitted, rather than the entire data stream – thus reducing the time to only request specific portions of the packet. In addition, it would also be ideal to include a header for the sequence of the packet itself. This way, to recover a packet, you can play an audio tape a second time with all packets, or have two way communications to request specific packets. It keeps the processing of packets fairly simple. Other quirks is that it would support sending packets out of order, and you could create multiple audio streams that only contain a small portion of total packets.

Request	Packets
Request All packets	1 to 100
Request 5, 87, 99	1, 5, 87, 99
Audio Signal 1	1 to 25
Audio Signal 2	1 and 26 to 50
Audio Signal 3	1 and 51 to 75
Audio Signal 4	1 and 76 to 100

Breaking the packets up into multiple audio signals, we can essentially create a scavenger hunt embedded into podcasts, videos, mp3 files or old school mix tapes where you need to find all of the signals to assemble the file in its entirety.

There is another part to the overall game where I would like to experiment with QR codes. In the way that the packetization works – it’s oblivious to the medium in which packets are transferred. A QR code could represent one or more packets to be scanned in. We’ll get to that later – but for now, let’s get on with adding a CRC and sequence number to our packets.

Packet Utils

During “The Great Refactor”, a utility helper was created to calculate everything I ever wanted to know about the packetization based on the configuration. Part of it was accepting bits to be converted into a packet. Those parts have been consolidated into a pack function.

I had to add a bit more changes to create a getPacketDataBitCount that’s different from getPacketEncodedBitCount since I’m adding a couple headers in addition to the data sent with each packet before it’s encoded.

export const pack = (bits) => ({
  getBits: (packetIndex) => {
    if(!canSendPacket()) return [];
  
    // How many data bits will be in our packet?
    let dataBitCount = getPacketDataBitCount();
  
    // grab our data
    const startIndex = packetIndex * dataBitCount;
    const endIndex = startIndex + dataBitCount;
    let packetBits = bits.slice(startIndex, endIndex);

    // add our headers

    // sequence number
    if(PACKET_SEQUENCE_NUMBER_BIT_COUNT !== 0) {
      packetBits.unshift(...numberToBits(packetIndex, PACKET_SEQUENCE_NUMBER_BIT_COUNT));
    }

    // CRC includes all other headers
    if(PACKET_CRC_BIT_COUNT !== 0) {
      // convert to bytes
      const bytes = bitsToBytes(packetBits);
      const crc = CRC.check(bytes, PACKET_CRC_BIT_COUNT);
      packetBits.unshift(...numberToBits(crc, PACKET_CRC_BIT_COUNT));
    }

    // encode our packet
    return encodePacket(packetBits);
  }
});

While setting up the headers, I realized that the CRC should be performed on all encoded data in the packet, including all other headers except for itself. As a result, the CRC is prepended as the first header. This means that the sequence number should not be trusted unless the entire packet is received and the CRC is valid. I think the result will be that my slowly loading GIF image will update in batches as each packet completes, rather than as each signal period completes. It’s probably for the best – especially since the sequence numbers can arrive out of order and we don’t want a corrupted transfer injecting itself into the wrong part of a file.

Packets are decoded in the StreamManager, but I think I need to dumb-down the stream manager and let the PacketUtils be responsible for telling you what the bits are in a packet, the sequence number, if it has completed, and if the data is trusted.

The StreamManager is smart enough to know if a packet has completed, but it needs to change how data is managed in memory. Currently it’s holding all of the ones and zeros of the encoded data stream in memory as arrays. Once I can get the packetization unpacked using the packet headers, I can change the bit arrays into byte arrays as each packet completes. I have a hunch that the issue with shorter signal durations is related to the bulk of data being stored in memory as a transfer continues. Storing one byte rather than many bits may be more optimal.

Packet Data Length

Just as I had to affix a data length to the packetization as a whole, I’m realizing that I have to affix a data length to the individual packet as well. With fixed packet sizes, I was getting a bunch of zero’s added onto the tail-end of my data transfer to complete the packetization. Packets have a similar problem. Each sampling period has a fixed set of bits. A packet may not use every bit in the sampling period for the last sample – although interleaving still applies. It’s easy enough to cut off those bits and call it a day. Next is error correction. I already know the max number of error correction blocks that can fit within a packet.

Last is – the last packet. I need to be able to cut off the unwanted bits to say “these specific bits represent the data”. This is problematic since I don’t want to read the first packet every time I decode a packet to get the entire data length. I want the packet to know how much original data is being sent. This means we have another header to add to our packets.

For a packets of 32 bytes, CRC-8, and sequence numbers, we have the following structure:

Header	Bits	Value
CRC-8	8 bits	0 to 255
Sequence Number	16 bits	0 to 65,535
Data Length	5 bits	0 to 31
Data	0 to 224	0 to 28 bytes

Since a packet is unable to change size, the amount of bytes available for the data changes as you add more headers, or change the size of existing headers. We tally up the bits used by the header, figure out how many bits are available in a packet and subtract that from the header bits.

// headerBitCount = 8 + 16 + 5 = 29
const headerBitCount = PACKET_CRC_BIT_COUNT
  + PACKET_SEQUENCE__NUMBER_BIT_COUNT
  + PACKET_SIZE_BIT_COUNT;

// packetByteCount = 2 ** 5 = 32 bytes;
// packetBitCount = packetByteCount * 8 = 256 bits
const packetBitCount = (2 ** PACKET_SIZE_BIT_COUNT) * 8;

// availableBitCount = 256 - 29 = 227
let availableBitCount = packetBitCount - headerBitCount;

We have 227 available bits in our packet outside of the header. The problem here is that we have a only 3 bits of our last byte. We could move ahead and utilize every bit possible, but it gets really messy when trying to track what parts of a file didn’t transfer correctly on the bit level. Our final step is to reduce our bit count to support whole bytes.

// availableByteCount = Math.floor(227 / 8 = 28.375) = 28
const availableByteCount = Math.floor(availableBitCount / 8);

// availableBitCount = 28 * 8 = 224
availableBitCount = availableByteCount * 8;

Since the packetization is configurable, we can play around with the values. If we change our CRC from CRC-8 to CRC-16, we add an extra 8 bits to our header, reduce our available bytes for data by one. If we keep the CRC check as 8 bits, but increase our packet sizes to 64 bytes, our header only increases by 1 bit, but we can pack more than twice the amount of data bytes (60 bytes) into a single packet.

There is a tradeoff between increasing the packet size and the time it takes for a successful transfer of all packets in a noisy environment with a high risk of corrupted packets. An increase in packet size reduces the amount of overhead transferred via headers and lets us broadcast the initial transfer a file in a shorter period of time. The reduction of packet sizes lets us request smaller portions of data in less time. We want to spend as little time as possible for the initial transmission and the re-transmission of failed packets.

Some of the things you may also look at is the packet utilization. For a packet without error correction, this is what we have available:

Packet Size	32 bytes	Utilization	64 bytes	Utilization
Header Bits	29	11.3%	30	5.9%
Data Bits	224	87.5%	480	93.8%
Unused Bits	3	1.1%	2	0.4%
Total Bits	256	100%	512	100%

Error correction is another story all together. It works with nibbles (4 bits) and injects 3 parity bits to restore only one of the four bits that failed. This creates blocks of 7 bits – or in other terms, blocks of 14 bits for every 8 bits of a byte. Rather than being able to transmit 28 bytes of data within our 32 byte packets, the bytes are significantly reduced. With 256 bits, we can only fit in 36 error correcting blocks of 7 bits each. That only gives us 144 bits to work with. We still use the same 29 bits for the header, leaving us 115 for data. Again, we have 3 unused bits that can’t be used to send a partial byte, leaving us with the capability of transferring only 14 bytes in all. Error Correction adds a great cost of overhead to ensure that our data can be repaired by the receiving party. In such environments prone to noise, it’s become quite necessary.

Packet 32 Bytes	CRC-8	Utilization	Error Correction + CRC-8	Utilization
Header Bits	29	11.3%	56 (50.75*)	22% (19.9%*)
Data Bits	224	87.5%	203	79.6%
Unused Bits	3	1.1%	4 (9.25*)	1.6% (3.6%*)
Data Bytes	28	87.5%	14	43.8%

With CRC, we have the option to ditch the high overhead of error correction and request failing packets. Due to having an unstable environment in terms of noise, CRC alone doesn’t help when you find yourself requesting almost every packet simply because a single bit got corrupted.

The encoding with interleaving bits does not have an impact on overhead on packets. Interleaving doesn’t require any headers to provide any additional information. It’s simply a way to fragment your bytes/blocks of data so that your bits are not sent close to each other on the audio spectrum, and thus become less susceptible to noise on multiple frequencies close to each other.

From my observations so far, interleaving is only beneficial when paired with error correction. Interleaving is currently being done at a lower level on sending and receiving during a sample period since the issue is directly tied to sound waves. With a longer sample period, it could be possible to alternate the interleaving pattern multiple times so that even without error correction, the frequency hopping of individual bit states would help influence the winning bit state. I’ll have to come back to that later…

I added the packet length and created an unpack function as well. I intentionally set the packet size as the last header so that it can be applied to the remaining bits.

export const pack = (bits) => ({
  getBits: (packetIndex) => {
    if(!canSendPacket()) return [];
  
    // How many data bits will be in our packet?
    let dataBitCount = getPacketDataBitCount();
  
    // grab our data
    const startIndex = packetIndex * dataBitCount;
    const endIndex = startIndex + dataBitCount;
    let packetBits = bits.slice(startIndex, endIndex);

    // add our headers

    // data byte count
    let byteCount = Math.ceil(packetBits.length / 8);
    packetBits.unshift(...numberToBits(byteCount, PACKET_SIZE_BITS));

    // sequence number
    if(PACKET_SEQUENCE_NUMBER_BIT_COUNT !== 0) {
      packetBits.unshift(...numberToBits(packetIndex, PACKET_SEQUENCE_NUMBER_BIT_COUNT));
    }

    // CRC includes all other headers
    if(PACKET_CRC_BIT_COUNT !== 0) {
      // convert to bytes
      const bytes = bitsToBytes(packetBits);
      const crc = CRC.check(bytes, PACKET_CRC_BIT_COUNT);
      packetBits.unshift(...numberToBits(crc, PACKET_CRC_BIT_COUNT));
    }

    // encode our packet
    return encodePacket(packetBits);
  }
});

export const unpack = (bits) => ({
  getPacketFromBits: (packetBits, packetIndex) => {
    const unpacked = {
      crc: CRC.INVALID,
      actualCrc: CRC.INVALID,
      sequence: -1,
      bytes: [],
      size: -1
    };
    if(packetBits.length === 0) return unpacked;

    // Remove the extra bits not used by the packet
    packetBits = packetBits.slice(0, getPacketMaxBitCount());

    // Remove extra bits not used by encoding
    if(isPacketEncoded()) {
      packetBits.splice(getPacketEncodedBitCount());
      packetBits = decodePacket(packetBits);
    }

    // Process CRC header FIRST (ensures all other headers are valid)
    if(PACKET_CRC_BIT_COUNT !== 0) {
      const crcBits = packetBits.slice(0, PACKET_CRC_BIT_COUNT);
      const expectedCrc = bitsToInt(crcBits, PACKET_CRC_BIT_COUNT);
      unpacked.crc = expectedCrc;
      packetBits.splice(PACKET_CRC_BIT_COUNT);
      // check the crc is valid
      const bytes = bitsToBytes(packetBits);
      unpacked.actualCrc = CRC.check(bytes, PACKET_CRC_BIT_COUNT);
    }

    // Process sequence header
    if(PACKET_SEQUENCE_NUMBER_BIT_COUNT === 0) {
      unpacked.sequence = packetIndex;
    } else {
      const sequenceBits = packetBits.slice(0, PACKET_SEQUENCE_NUMBER_BIT_COUNT);
      const sequence = bitsToInt(sequenceBits, PACKET_SEQUENCE_NUMBER_BIT_COUNT);
      unpacked.sequence = sequence;
      packetBits.splice(PACKET_SEQUENCE_NUMBER_BIT_COUNT);
    }
    // Detect data byte count
    const sizeBits = packetBits.slice(0, PACKET_SIZE_BITS);
    unpacked.size = numberToBytes(sizeBits, PACKET_SIZE_BITS);
    packetBits.splice(PACKET_SIZE_BITS);
    packetBits.splice(unpacked.size * 8);

    // rest are data
    unpacked.bytes = bitsToBytes(packetBits);

    return unpacked;
  },
  getPacket: (packetIndex) => {
    const unpacked = {
      crc: CRC.INVALID,
      actualCrc: CRC.INVALID,
      sequence: -1,
      bytes: [],
      size: -1
    };

    if(!canSendPacket()) return unpacked;

    // Get bits associated with the packet
    const packetBitCount = getPacketSegmentCount() + BITS_PER_SEGMENT;
    const offset = packetIndex * packetBitCount;
    const packetBits = bits.slice(offset, offset + packetBitCount);

    if(packetBits.length === 0) return unpacked;

    return this.getPacketFromBits(packetBits, packetIndex);

  }
});

The next part is to wire up the stream manager to use PacketUtils and to store packets as bytes once they are received. It also needs to store a log of what packets failed the CRC checks. For dumbing down the stream manager, it sounds like it’s actually getting smarter.

Many Hours Later

I had a board meeting at the library. I changed the stream manager to convert bit samples to bytes as packets complete. I also changed the interleaving to be done by the audio receiver and audio sender. I’d rather keep that stuff fairly low level since it’s specific to those transfer protocols. Afterwards I did a lot of testing to get the signal working again and now detecting CRC, data length, and sequence for each packet.

The stream manager needs a lot of care to change all the rest of it over to use the trusted bytes instead of the old bit arrays. Progress bars currently do not work as a result. I also started pulling out all of the logic that showed the bits at various stages (interleaved, encoded, decoded, etc). It was helpful early on, but is more or less noise at the moment. Now that the CRC is in place, I can list failing packets instead.

I’m still debating on the appropriate logic for the stream managers interaction with arrays. I’m not too crazy about being unable to dynamically change the length of a typed array as more data arrives.

Since I load data as packets arrive, the image feels like it loads slower, but adds “chunks” of data at a time instead of watching the pixels being added one at a time. The only chunks that do load are from data that is correct. We no longer see oddly distorted images at a slant or garbled up. Instead we just see the scan lines with the actual data. I can also run the same signal multiple times to attempt to get some good packets, and reset the underlying data with a click of a button, rather than starting over with each new signal.

Unfortunately – all of the packets were successful with CRC checks, but the image looks broken. Something is off. It’s fairly late and I hear birds chirping already. Time to go to sleep.