Decoding an air conditioner control's checksum with differential cryptanalysis

Back in 2009 I wrote an Arduino library (IRRemote) to encode and decode infrared signals for remote controls. I got an email recently from someone wanting to control an air conditioner. It turns out that air conditioner remote controls are much complicated than TV remote controls: the codes are longer and include a moderately complex checksum. My reader had collected 35 signals from his air conditioner remote control, but couldn't figure out the checksum algorithm. I decided to use differential cryptanalysis to figure out the checksum, which was overkill but an interesting exercise. In case anyone else wants to decode a similar remote control, I've written up how I found the algorithm.

My IR remote library can be used with the Arduino to send and receive signals. (This is not the air conditioner remote.)

The problem is to find a checksum algorithm that when given three bytes of input (left), computes the correct one byte checksum (right).

10100001 10010011 01100011 => 01110111
10100001 10010011 01100100 => 01110001
10100001 10010011 01100101 => 01110000
10100001 10010011 01100110 => 01110010
10100001 10010011 01100111 => 01110011
10100001 10010011 01101000 => 01111001
10100001 10010011 01101001 => 01111000
10100001 10010011 01101010 => 01111010
10100001 10010011 01101011 => 01111011
10100001 10010011 01101100 => 01111110
10100001 10010011 01101101 => 01111111
10100001 10010011 01101110 => 01111100
10100001 10010011 01101111 => 01111101
10100001 10010011 01110001 => 01100100
10100001 10010011 01110010 => 01100110
10100001 10010011 01110011 => 01100111
10100001 10010011 01110100 => 01100001
10100001 10010011 01110101 => 01100000
10100001 10010011 01110111 => 01100011
10100001 10010011 01110111 => 01100011
10100001 10010011 01111000 => 01101001
10100001 10010011 01101000 => 01111001
10100001 00010011 01101000 => 11111001
10100001 00010011 01101100 => 11111110
10100001 10010011 01101100 => 01111110
10100001 10010100 01111110 => 01101011
10100001 10000010 01101100 => 01100000
10100001 10000001 01101100 => 01100011
10100001 10010011 01101100 => 01111110
10100001 10010000 01101100 => 01111100
10100001 10011000 01101100 => 01110100
10100001 10001000 01101100 => 01101100
10100001 10010000 01101100 => 01111100
10100001 10011000 01101100 => 01110100
10100010 00000010 11111111 => 01111110

The idea behind differential cryptanalysis is to look at the outputs resulting from inputs that have a small difference, to see what patterns emerge (details). Finding air conditioner checksums is kind of a trivial application of differential cryptanalysis, but using differential cryptanalysis provides a framework for approaching the problem. I wrote a simple program that found input pairs that differed in one bit and displayed the difference (i.e. xor) between the corresponding checksums. The table below shows the differences.

000000000000000000000001 : 00000001
000000000000000000000010 : 00000010
000000000000000000000010 : 00000011
000000000000000000000100 : 00000100
000000000000000000000100 : 00000110
000000000000000000000100 : 00000111
000000000000000000001000 : 00001100
000000000000000000001000 : 00001110
000000000000000000001000 : 00001111
000000000000000000010000 : 00010000
000000000000100000000000 : 00001000
000000000001000000000000 : 00011000
000000001000000000000000 : 10000000

The first thing to notice is that changing one bit in the input causes a relatively small change in the output. If the checksum were something cryptographic, a single bit change would entirely change the output (so you'd see half the bits flipped on average). Thus, we know we're dealing with a simple algorithm.

The second thing to notice is the upper four bits of the checksum change simply: changing a bit in the upper four bits of an input byte changes the corresponding bit in the upper four bits of the output. This suggests that the the three bytes are simply xor'd to generate the upper four bits. In fact, my reader had already determined that the xor of the input bytes (along with 0x20) yielded the upper four bits of the checksum.

The final thing to notice is there's an unusual avalanche pattern in the lower four bits. Changing the lowest input bit changes the lowest checksum bit. Changing the second-lowest input bit changes the second-lowest checksum bit and potentially the last checksum bit. Likewise changing the fourth-lowest input bit changes the fourth-lowest checksum bit and potentially the bits to the right. And the change pattern always has 1's potentially followed by 0's, not a mixture. (1100, 1110, 1111)

What simple operation has this sort of avalanche effect? Consider adding two binary numbers. If you change a high-order bit of an input, only that bit will change in the output. If you change a low-order input bit, the low-order bit of the output will change. But maybe there will be a carry, and the next bit will change. And if there's a carry from that position, the third bit will change. Likewise, changing a bit in the middle will change that bit and potentially some of the bits to the left (due to carries). So if you change the low-order bit, the change in the output could be 0001 (no carry), or 0011, or 0111, or 1111 (all carries). This is the same pattern seen in the air conditioner checksums but backwards. This raises the possibility that the checksum is using a binary sum, but we're looking at the bits backwards.

So I made a program that reversed the bits in the input and output, and took the sum of the four bits from each byte. The output below shows the reversed input, the sum, and the 4-bit value from the correct checksum. Note that the sum and the correct value usually add up to 46 or 30 (two short of a multiple of 16). This suggested that the checksum is (-sum-2) & 0xf.

110001101100100110000101 32 14
001001101100100110000101 22 8
101001101100100110000101 30 0
011001101100100110000101 26 4
111001101100100110000101 34 12
000101101100100110000101 21 9
100101101100100110000101 29 1
010101101100100110000101 25 5
110101101100100110000101 33 13
001101101100100110000101 23 7
101101101100100110000101 31 15
011101101100100110000101 27 3
111101101100100110000101 35 11
100011101100100110000101 28 2
010011101100100110000101 24 6
110011101100100110000101 32 14
001011101100100110000101 22 8
101011101100100110000101 30 0
111011101100100110000101 34 12
111011101100100110000101 34 12
000111101100100110000101 21 9
000101101100100110000101 21 9
000101101100100010000101 21 9
001101101100100010000101 23 7
001101101100100110000101 23 7
011111100010100110000101 17 13
001101100100000110000101 15 0 *
001101101000000110000101 19 12 *
001101101100100110000101 23 7
001101100000100110000101 11 3
001101100001100110000101 12 2
001101100001000110000101 12 3 *
001101100000100110000101 11 3
001101100001100110000101 12 2
111111110100000001000101 23 7

That formula worked with three exceptions (marked with asterisks). Studying the exceptions showed that adding in byte 1 bit 3 and byte 2 bit 7 yielded the correct answer in all cases.

Conclusion

Putting this together yields the following algorithm (full code here):

inbytes = map(bitreverse, inbytes)
xorpart = (inbytes[0] ^ inbytes[1] ^ inbytes[2] ^ 0x4) & 0xf
sumpart = (inbytes[0] >> 4) + (inbytes[1] >> 4) + (inbytes[2] >> 4) +
  (inbytes[2] & 1) + ((inbytes[1] >> 3) & 1) + 1
sumpart = (-sumpart) & 0xf
result = bitreverse((sumpart << 4) | xorpart)

Is this the right formula? It gives the right checksum for all the given inputs. However, some bits never change in the input data; in particular all inputs start with "101000", so there's no way of knowing how they affect the algorithm. They could be added to the sum, for instance, replacing the constant +1. The constant 0x4 in the xor also makes me a bit suspicious. It's quite possible that the checksum formula would need to be tweaked if additional input data becomes available.

I should point out that determining the checksum formula is unnecessary for most air conditioning applications. Most users could just hard-code the checksums for the handful of commands they want to send, rather than working out the general algorithm.

Thanks to Antonio Martinez Lavin, maker of the Cuby air conditioner controller for posing this problem. If you want to use my IR library, it is on GitHub. I'm no longer actively involved with the library, so please post issues on the GitHub repository rather than on this blog post. Thanks to Rafi Kahn, who has taken over library maintenance and improvement.

Follow me on Twitter or RSS to find out about my latest blog posts.

Hands-on with the PocketBeagle: a $25 Linux computer with lots of I/O pins

The PocketBeagle is a tiny but powerful inexpensive key-fob-sized open source Linux computer. It has 44 digital I/O pins, 8 analog inputs, and supports multiple serial I/O protocols, making it very useful as a controller. In addition, its processor includes two 200-MHz microcontrollers that allow you to implement low-latency, real-time functions while still having the capabilities of a Linux system This article discusses my experience trying out different features of the PocketBeagle, along with some technical details.

The PocketBeagle is a compact Linux computer, somewhat bigger than a quarter.

You may be familiar with the BeagleBone, a credit-card sized computer. The PocketBeagle is very similar to the BeagleBone, but smaller and cheaper. Both systems use TI's 1GHz "Sitara" ARM Cortex-A8 processor, but the PocketBeagle's I/O is stripped-down with 72 header pins compared to 92 on the BeagleBone. The PocketBeagle doesn't have the BeagleBone's 4GB on-board flash; all storage is on a micro-SD card. The BeagleBone's Ethernet and HDMI ports are also dropped.

The PocketBeagle uses an interesting technology to achieve its compact size—it is built around a System-In-Package (SIP) device that has multiple dies and components in one package (see diagram below). The Octavo Systems OSD3358-SM combines the TI 3358 Sitara processor, 512MB of RAM, power management and EEPROM. 1 In the photo above, this package has a white label and dominates the circuit board.

The PocketBeagle is powered by the OSD335x, which combines a processor die, memory and other components into a single package.

Initializing the SD card

To use the PocketBeagle, you must write a Linux file system to a micro-SD card. The easiest way to do this is to download an image, write it to the SD card from your computer, and then pop the SD card into the PocketBeagle. Details are in the footnotes.2

You can also compile a kernel from scratch, set up U-boot, and build a file system on the SD card. the PocketBeagle. There's a bunch of information on this process at Digikey's PocketBeagle getting started page. This is the way to go if you want flexibility, but it's overkill if you just want to try out the PocketBeagle.

Starting up the PocketBeagle

Unlike the BeagleBone, which supports a keyboard and an HDMI output, the PocketBeagle is designed as a "headless" device that you ssh into. You can plug the PocketBeagle into your computer's USB port, and the PocketBeagle should appear as a network device: 192.168.6.2 on Mac/Linux and 192.168.7.2 on Windows (details). You should also see a flash-drive style file system appear on your computer under the name "BEAGLEBONE". If the PocketBeagle has the default Debian OS3, you can log in with:

ssh [email protected]
Password: temppwd

Connecting to the PocketBeagle's serial console

While ssh is the simplest way to connect to the PocketBeagle, if anything goes wrong with the boot or networking, you'll need to look at the serial console to debug the problem. The easiest solution is a UART Click board4, which gives you a serial connection over USB. You can then connect with "screen" or other terminal software: screen /dev/cu.usbserial\* 115200

Plugging a UART click board into the PocketBeagle gives access to the serial console.

You can also use a FTDI serial adapter such as the Adafruit FTDI Friend. (If you've worked with the BeagleBone, you may have one of these already.) You'll need three wires to hook it up to the PocketBeagle; it won't plug in directly as with the BeagleBone. Just connect ground, Rx and Tx between the PocketBeagle and the adapter (making sure to cross Rx to Tx).5

Accessing the PocketBeagle's serial console through an FTDI interface.

Pinout

The PocketBeagle has two headers that provide access to I/O functions. (These headers are different from the BeagleBone's headers, so BeagleBone "capes" won't work with the PocketBeagle.) The PocketBeagle pinout diagram (below) shows what the header pins do. The diagram may seem confusing at first, since each pin has up to three different functions shown. (Most pins actually support 8 functions, so more obscure functions have been omitted.) The diagram is color coded. Power and system pins are labeled in red. GPIO (general-purpose I/O) pins are white. USB pins are blue. Analog inputs are yellow. UART serial pins are brown. PRU microcontroller pins are cyan. Battery pins are magenta. I2C bus is purple. PWM (pulse width modulation) outputs are light green. SPI (Serial Peripheral Interface) is brown. CAN (Controller Area Network) is dark green. QEP (quadrature encoder pulse) inputs are gray.9 The dotted lines in the diagram indicate the default pin functions (except for the PRU pins, which default to GPIO).6

Pinout diagram of the PocketBeagle's headers. USB=blue, Power=yellow, GPIO=white, PRU=cyan, SPI=orange, UART=brown, and other colors are miscellaneous.

Note that the diagram shows the headers from the component side of the board, not the silkscreened side of the board. Comparing the pin diagram with the board (below), you will notice everything is flipped horizontally. E.g. GPIO 59 is on the right in the diagram and on the left below. So make sure you're using the right header!

Silkscreen labeling the PocketBeagle's header pins.

One tricky feature of the Sitara processor is that each pin has up to eight different functions. The motivation is that the chip supports a huge number of different I/O functions, so there aren't enough physical pins for every desired I/O. The solution is a pin mapping system that lets the user choose which functions are available on each pin. 7 If you need to change a pin assignment from the default, the config-pin command will modify pin mappings. (Some examples will be given below.) Pins can also be configured at boot time using a "U-Boot overlay".8

GPIO

The PocketBeagle exposes 45 GPIO (general purpose I/O) pins on the headers. The pins can be easily controlled by writing to pseudo-files. For example, the following shell code repeatedly blinks an LED connected to GPIO 11110 (which is accessed through header pin P1_33).

echo out > /sys/class/gpio/gpio111/direction
while :; do
> echo 1 > /sys/class/gpio/gpio111/value; sleep 1
> echo 0 > /sys/class/gpio/gpio111/value; sleep 1
> done

An LED connected to header P1 pin 33 can be controlled through GPIO 111.

PRU

One of the most interesting features of the PocketBeagle is its PRUs, two 32-bit RISC microcontrollers that are built into the Sitara processor chip. These microcontrollers let you perform time-critical operations (such as "bit-banging" a protocol), without worrying about context switches, interrupts, or anything else interfering with your code. At the same time, the ARM processor gives high performance and a complete Linux environment. (I've made use of the BeagleBone's PRU to interface to a vintage Xerox Alto's 3 Mb/s Ethernet.)

Although the PRUs are not as easy to use as an Arduino, they can be programmed in C, using the command line or Texas Instruments' CCS development environment. I've written about PRU programming in C before (link) and the underlying library framework (link) for the 3.8.13 kernel, but since then much has changed with the way the PRUs are accessed. The PRUs are now controlled through the remoteproc framework. In addition, a messaging library (RPMsg) makes it simpler to communicate between the PRUs and the ARM processor. A "resource_table.h" file provides setup information (such as the interrupts used).

The following code will turn the LED on (by setting a bit in control register 30), wait one cycle (5ns), turn the LED off, and wait again. Note that the PRU output is controlled by modifying a bit in register R30. This will blink the LED at 40Mhz, unaffected by any other tasks, context switches or interrupts. (For the full code and details of how to run it, see my github repository.)

void main(void)
{
  while (1) {
    __R30 = __R30 | (1<<1); // Turn on output 1
    __delay_cycles(1);
    __R30 = __R30 & ~(1<<1); // Turn off output 1
    __delay_cycles(1);
  }
}

This code uses PRU0 output 1, which is accessed through header pin P1_33 (the same pin as the earlier GPIO example). Since this pin defaults to the GPIO, it must be switched to a PRU output:11

config-pin P1_33 pruout

This LED example illustrates two key advantages of using the PRU versus controlling a GPIO pin from Linux.12 First, the PRU code can operate much faster. Second, the GPIO code will produce an uneven signal if the CPU is performing some other Linux task. If you can handle milliseconds of interruption, controlling GPIO pins from Linux is fine. But if you need exact cycle-by-cycle accuracy, the PRU is the way to go.

Networking

Unlike the BeagleBone, the PocketBeagle doesn't have a built-in Ethernet port. However, there are several options for connecting the PocketBeagle to the Internet, described in the PocketBeagle FAQ. I found the easiest was to use WiFi via a WiFi adapter plugged into USB, as shown below. An alternative is to share your host computer's Ethernet, which I found more difficult to get working.14 Finally, you can add an Ethernet interface to the PocketBeagle using the expansion headers.

A USB WiFi adapter can easily be connected to the PocketBeagle.

USB

You can easily connect USB devices to the PocketBeagle since the PocketBeagle has pins assigned for a second USB port. Plug a USB Micro-B breakout board into the Pocket Beagle as shown below, connect a USB OTG host cable and your USB port should be ready to go. Note that this USB port is a host (i.e. a USB device is connected to the PocketBeagle) opposite from the onboard USB port which works as a client (the PocketBeagle is connected as a device to another computer).

A closeup of how to plug the USB breakout board into the PocketBeagle. It is connected to pins P1_7 through P1_15.

For instance, you can plug in a flash drive. (In the picture below, note that the flash drive is almost as big as the PocketBeagle.) The lsusb command will show your device, and then you can mount it with sudo mount /dev/sda1 /mnt.

Connecting a USB device (flash drive) to the PocketBeagle.

Analog inputs

The PocketBeagle has 8 analog input pins. Six of them take an input from 0 to 1.8V, while two take an input from 0 to 3.3V. (Be careful that you don't overload the input.) The analog input value (between 0 and 4095) can be read from the file system as shown below. Change the number in voltage0 to select the input. (Inputs 5 through 7 require special handling.15)

$ cat /sys/bus/iio/devices/iio:device0/in_voltage0_raw
2510

In the photo below, I hooked up a light sensor (CdS photocell in a voltage divider) to provide a voltage to analog input 0 (header pin P1_19). The reference voltages come from header pins P1_17 (analog ground) and P1_18 (analog reference 1.8V). More light on the sensor produces a higher voltage, yielding a higher value from the input.

A photocell can be hooked up to the PocketBeagle's analog input to provide a light sensor.

I2C / SPI

The PocketBeagle supports two SPI ports and two I2C ports. These serial protocols are popular for controlling chips and other devices.

An accelerometer board (left) can be connected to the PocketBeagle's I2C port with four wires.

For example, the photo above shows a cheap I2C accelerometer board connected to the PocketBeagle's SPI port. Simply wire the power, ground, SCL (clock) and SDA (data) between the accelerometer and the PocketBeagle's I2C1 port (i.e. header P2 pins 13, 15, 9, 11). Probing for I2C devices with i2cdetect will show that the device uses address 68. The device can be turned on with i2cset and the registers dumped out with i2cdump to obtain acceleration values.16

Using an I2C-based accelerometer board with the PocketBeagle.

Conclusion

The PocketBeagle is a low-cost, compact Linux computer, able to control external devices with its I/O ports and GPIO pins. Since the PocketBeagle was released recently, there isn't a whole lot of documentation on it. Hopefully this article has shown you how to get started with the PocketBeagle and use some of its features.

New (12/2017): The PocketBeagle System Reference Manual has lots of useful information, so take a look.

For more information, see the PocketBeagle FAQ and Getting Started pages. Also remember that the PocketBeagle uses the same processor and Linux kernel as the BeagleBone, so most of the information on the BeagleBone will carry over to the PocketBeagle. I've found the book Exploring BeagleBone to be especially helpful. Thanks to Robert Nelson and DigiKey for giving a PocketBeagle tutorial at Hackaday Superconference.

Follow me on Twitter or RSS to find out about my latest blog posts.

Notes and references

1. The Octavo package reminds me a bit of the Solid Logic Technology (SLT) modules that IBM used in the 1960s instead of integrated circuits. They consisted of small metal packages containing semiconductor dies and resistors connected together on a ceramic wafer, and were used in computers such as the IBM 360.

   ↩

   Two IBM SLT modules, with a penny for scale. Each module contains semiconductors (transistors or diodes) and printed resistors wired together, an alternative to integrated circuits.

2. On a Mac, I used the following procedure to write the SD card. First, download an image from beagleboard.org. I use "Stretch IoT (non-GUI) for BeagleBone and PocketBeagle via microSD card". Then unmount the SD drive and format it as FAT-32. (Replace XXX below with the right drive number; don't format your hard disk!)

   diskutil list
   diskutil umountdisk /dev/diskXXX
   sudo diskutil eraseDisk FAT32 BEAGLE MBRFormat /dev/diskXXX
   sudo diskutil unmount /dev/diskXXXs1
   

   Then write the disk image to the SD card:

   zcat /tmp/pocketbeagle.img | sudo dd of=/dev/diskXXX bs=2m
   xzcat *.xz | sudo dd of=/dev/diskXXX
   

   Writing the image took about 10 minutes with a USB to micro-SD adapter. (If it's taking hours, I recommend a different USB adapter.) When done, install the SD card in the PocketBeagle. ↩

3. I'm using Debian with kernel Linux beaglebone 4.14.0-rc8 #1 Mon Nov 6 15:46:44 UTC 2017 armv7l GNU/Linux. If you use a different kernel (such as 3.8.13), many of the software features will be different. ↩

4. One interesting feature of the PocketBeagle is its headers have the right pinout to support many mikroBUS boards. This is an open standard for small boards (similar to capes/shields), using a 16-pin connector. Hundreds of "click boards" are available for connectivity (e.g. Bluetooth, WiFi, Ethernet, NFC), sensors (e.g. pressure, temperature, proximity, accelerometer, seismic), security coprocessors, GPS, electronic paper, storage, and many more functions. The PocketBeagle doesn't officially support mikroBUS, but many boards "just work" (details). ↩

5. For the FTDI serial connection, connect Gnd to P1_22, Rx to P1_30 (UART0 Tx) and Tx to P1_32 (UART0 Rx). ↩

6. The PocketBeagle device tree file specifies the default pin mappings and names other pin mappings. But if you want to track down the actual hardware meaning of each header pin, it's complicated. The PocketBeagle schematic shows the mapping from header pins to balls on the Octavo chip package. The Octavo OSD335x documentation gives ball map to the Sitara chip. The Sitara AM335x datasheet lists the up to eight functions assigned to each pin. The Technical Reference Manual Section 9.3.1.49 describes the control register for each pin. Thus, it's possible but tedious to determine from "first principles" exactly what each PocketBeagle header pin does. ↩

7. There are a couple problems you can encounter with pin mapping. First, since not all chip pins are exposed on PocketBeagle headers, you're out of luck if you want a function that isn't wired to a header. Second, if you need two functions that both use the same pin, you're also out of luck. Fortunately there's enough redundancy that you can usually get what you need. ↩

8. The PocketBeagle uses U-Boot The U-Boot overlay is discussed here. For more information on device trees, see Introduction to the BeagleBone Black device tree. ↩

9. The Technical Reference Manual is a 5041 page document describing all the feature of the Sitara architecture and how to control them. But for specifics on the AM3358 chip used in the BeagleBone, you also need to check the 253 page datasheet. ↩

10. Note that there are two GPIO numbering schemes; either a plain number or register and number. Each GPIO register has 32 GPIOs. For example, GPIO 111 is in register 3 and also known as GPIO 3.15. (3*32+15 = 111) ↩

11. To switch P1_33 back to a GPIO, use config-pin P1_33 gpio.

    Internally, config-pin writes to a pseudo-file such as /sys/devices/platform/ocp/ocp:P1_33_pinmux/state to cause the kernel to change the pin's configuration. ↩

12. You can control GPIO pins from a PRU. However, there will be several cycles of latency as the control signal is delivered from the PRU to the GPIO. A PRU pin on the other hand can be read or written immediately. ↩

13. WiFi on the PocketBeagle is easy to set up using a command line program called connmanctl. Instructions on configuring WiFi with connmanctl are here and also are listed in the /etc/network/interfaces file. (Don't edit that file.) When I started up connmanctl, it gave an error about VPN connections; I ignored the error. I tested WiFi with a Mini USB WiFi module and an Ourlink USB WiFi module. ↩

14. Sharing an Internet connection with the PocketBeagle isn't as simple as I'd like. To share with Windows, I followed the instructions here and here. (Note that BeagleBone instructions should work for the PocketBeagle.) I haven't had much luck with MacOS. In any case, I recommend connecting to the serial console first since there's a good chance you'll lose any SSH connection while reconfiguring the networking. ↩

15. Analog input pins 5 and 6 are shared with a GPIO pin via a voltage divider. To use one of these inputs, you must configure the shared GPIO as an input with no pullup/down so it won't affect the analog value. In addition, the input voltage is divided by 2 (so these pins can support up to 3.3V instead of 1.8V).

    # Analog input 5 (P2_35)
    $ config-pin P2_35 gpio
    $ echo in > /sys/class/gpio/gpio86/direction
    $ cat /sys/bus/iio/devices/iio:device0/in_voltage5_raw
    # Analog input 6 (P1_2)
    $ config-pin P1_2 gpio
    $ echo in > /sys/class/gpio/gpio87/direction
    $ cat /sys/bus/iio/devices/iio:device0/in_voltage6_raw
    

    Analog input 7 (P2_36) is multiplexed by the power management IC (PMIC). It supports a maximum voltage of 1.8V. To read the value, you must first configure the PMIC:

    $ sudo i2cset -y -f 0 0x24 9 5
    $ cat /sys/bus/iio/devices/iio:device0/in_voltage7_raw
    

     ↩

16. In the accelerometer example, the board is approximately vertical with the chip's X axis pointing up. The X, Y, and Z accelerations returned by i2cdump in the screenshot were 0x42a8, 0x02dc, and 0x1348. These are signed values, scaled so 16384 is 1G. Thus, the X acceleration was approximately 1 G (due to Earth's gravity) while the other accelerations were small. These values change if the board's orientation changes or the board is accelerated. The temperature is 0xed10, which according to the formula in the register map yields 22.3°C or 72°F. The last three words are the gyroscope values, which are approximately 0 since the board isn't rotating. For more details on the accelerometer board see the register map, the datasheet and this Arduino post. ↩

Fixing the Ethernet board from a vintage Xerox Alto

A Xerox Alto system on the East coast had Ethernet problems, so the owner sent me the Ethernet board to diagnose. (After restoring our Alto, we've heard from a couple other Alto owners and try to help them out.) This blog post describes how I repaired the board and explains a bit about how the Alto's groundbreaking Ethernet worked.

The Alto was a revolutionary computer designed at Xerox PARC in 1973, introducing the GUI, high-resolution bitmapped displays and laser printers to the world. But one of its most important contributions was Ethernet, the local area network that is still heavily used today. While modern Ethernets handle up to 100 gigabits per second, the Alto's Ethernet was much slower, just 3 megabits per second over coaxial cable. Even so, the Alto used the Ethernet for file servers, email, network boot, distributed games and even voice over Ethernet.

An extender board made it easy to probe the Ethernet card in the Xerox Alto. The chassis is pulled out to access the boards. Above the chassis is the disk drive, which stores just 2.5 megabytes on a 14-inch disk pack.

The Alto's chassis slides out of the cabinet, allowing access to the circuit boards (see above). To test the Ethernet board, I plugged it into the Alto we've restored. The Ethernet board is hanging out the right side of the chassis because I used an extender board.

The board had a couple straightforward problems—a chip with a bent pin (which I straightened) and another chip with broken pins. (While some people recommend re-seating chips on old boards, this can create new problems.) The broken chip was a 74S86, a quadruple XOR gate that has been obsolete for years (if not decades). I replaced it with a 74LS86, a similar but non-obsolete chip.1

When I powered up the Alto, I didn't get anything from the Ethernet board: it was not sending or receiving successfully. This double failure was a bit surprising since malfunctions usually affect just one direction. But I quickly discovered a trivial problem: when I pulled out the Alto's cabinet to access the circuit boards, the Ethernet connector on the back came loose. After plugging the connector in, I saw that the Alto was sending packets successfully, but still wasn't receiving anything.

Oscilloscope trace from the Ethernet board. Yellow is input data, green is R-C filtered, blue is detected edges. The blue trace is a bit of a mess with runt pulses.

I started probing the Ethernet board's input circuit with the oscilloscope. The board was receiving the input okay, but a few gates later the signals looked kind of sketchy, as you can see above. The yellow trace is the input Ethernet signal. The board applies an R-C filter (green) and then the signal edges are detected (blue). While the input (yellow) is a clean signal, the green signals only go up to about 2 volts, not the expected 4-5 volts. Even worse, the blue waveform is irregular and has "runt" pulses—short irregular signals that don't go all the way up. With waveforms like this, the board wouldn't be able to process the input.

Manchester encoding and the decoding circuit

I'll take a detour to explain the Ethernet's Manchester encoding, before getting into the details of the circuitry.

The Alto's Ethernet encoded data over the coaxial cable using Manchester encoding.32 In this encoding, a 1 bit is sent as a 1 followed by a 0, while a 0 bit is sent as a 0 followed by a 1. The diagram below shows how the bits "0110" would be encoded. A key reason to use this encoding is that simplifies timing on the receiver, since it is self-clocking. Note that there is a transition in the middle of each cell that can be used as a clock. (The obvious scheme of just sending the bits directly has the problem that in a long string of 0's, it's hard to know exactly how many were transmitted.)

An example of Manchester encoding, for the bits 0110.

To decode the Ethernet signal arriving at the Alto, the first step is to extract the clock signal that indicates the timing of the bits. To extract the clock, the transitions in the middle of each bit cell must be detected. The trick is to ignore transitions at the edges of cells. The diagram below shows how the clock is extracted. First, edge pulses are generated for each transition edge of the input. Then, a clock pulse is generated for each edge pulse. The clock pulse about 75% of the width of the bit cell, and any second pulse that happens while the clock is still high is blocked. (The edge circled in red is an example of an ignored edge.) The result is the steady clock signal, synchronized to the input.4 This clock is used to latch the input signal value into a shift register, which converts the serial Ethernet stream into a word value usable by the Alto.

Extracting the clock signal from a Manchester-encoded Ethernet input. Edges are extracted from the input signal and used to trigger the clock. An edge too close to the previous (red) is dropped.

The schematic5 below shows the circuit that performs this clock extraction. There are a few tricks in this interesting semi-analog circuit. When the Ethernet input signal changes, the low-pass R-C (resistor capacitor) filter output will be slower to change. This will cause the edge detect XOR gate to go high briefly until the R-C signal catches up. Then the clock is generated by a "one-shot", a chip that generates a fixed-width pulse for each input pulse. The pulse width is set to about 75% of the bit cell width by another resistor and capacitor. The one-shot is wired to ignore any additional pulses that occur while the clock output is high.

Schematic of the clock extraction circuit in the Xerox Alto's Ethernet interface.

Since the timing in this circuit was controlled by multiple resistors and capacitors, I thought that a capacitor might have gone out of tolerance. But first I decided to do the simpler test of swapping the XOR chip with the one from our working Alto board. Surprisingly, this fixed the problem, and the Ethernet board now functioned flawlessly. Thus, while the 74LS86 has input characteristics similar to the 74S86, they weren't close enough, and substituting the more modern chip messed up the R-C filter's behavior. (If the gate draws too much input current, the capacitor won't charge as fast.) Marc dug through his collection of old chips and found another 74S86 so we could get both boards operating.

Oscilloscope trace showing the extracted clock (pink), edges of the Ethernet input (yellow) and the R-C filtered input (green).

The oscilloscope trace above shows the nice, steady clock (pink) after replacing the XOR chip. With the right XOR chip, the RC-filtered signal (green) rises to 4 volts, unlike before when it just went to 2 volts. The edge signal (yellow) is nice and even, without the "runt pulses" seen earlier.

An overview of the Ethernet board

I'll wrap up by explaining a bit about the Alto's Ethernet board (shown in the photo below). The large connector at the left plugs into the Alto's backplane, providing communication with the rest of the system. The small connector at the right connects to the Ethernet, via a transceiver. Some of the key components of the Ethernet interface are labeled on the diagram below. With this generation of chips, even a whole board of chips doesn't give you a lot of functionality so much of the Ethernet functionality is implemented in software and microcode.

The Xerox Alto's Ethernet board, showing major functional blocks.

Most of the chips are simple TTL logic, but the board uses a few interesting and obscure chips. Input and output data goes through a 16-word FIFO buffer built from four Intel 3101A RAM chips; each one holds just 16×4 bits. (The 3101 was Intel's first product.) Commands to the Ethernet board are decoded by three Intel 3205 decoder chips. Buffer chips interface between the card and the Alto's bus. Shift registers for the input and output convert between data words and serial data over the Ethernet. The CRC error checking is done by a specialized Fairchild 9401 CRC chip. Surprisingly, the Manchester encoding is implemented with a PROM-driven state machine, built from two Intel 3601 PROMs. Finally, the XOR chip is the chip that caused all the problems.5

The board has TTL inputs and outputs, so it doesn't connect directly to the Ethernet cable. Instead, a transceiver box is the interface between the Alto and the cable. In the photo below, you can see the transceiver clamped onto the coaxial cable. The transceiver converts the Alto's logic signals to the signals on the cable and injects the signals through an isolation transformer. In addition, the transceiver detects collisions if the Alto tries to send at the same time as another machine on the network.

The transceiver injects the Xerox Alto's signals into the Ethernet coaxial cable and reads signals from the cable.

You might wonder how the Alto can communicate with a modern system, since the Alto's 3 Mb/s Ethernet isn't compatible with modern Ethernet. I am building a gateway based on the BeagleBone (below) that uses the BeagleBone's microcontroller (the PRU) to "bit bang" the Ethernet signals. The BeagleBone also runs an implementation of IFS (Interim File System), the server side software to support the Alto. This is a C# implementation of IFS written by the Living Computers Museum.

I'm building an interface to the Alto's 3Mb/s Ethernet, using a BeagleBone. The cable on the right goes to the Alto's Ethernet port, while a standard Ethernet plugs into the left.

Conclusion

Bob Metcalfe invented Ethernet at Xerox PARC between 1973 and 1974, with a 3 megabit per second Ethernet for the Alto. Since then, Ethernet has become a ubiquitous standard, and has increased in speed more than 4 orders of magnitude. Unfortunately, as with many other technologies, Xerox failed to take advantage of Ethernet as a product. Instead, Bob Metcalfe left Xerox in 1979 and formed the company 3Com, which sold Ethernet products and became one of the most successful technology firms of the 1990s.

I tracked down a problem in an Alto Ethernet board—my replacement for a broken chip was almost the same, but incompatible enough to make the circuit fail. The problem showed up in the circuit that extracted the clock from the incoming Ethernet signal. This circuit illustrates some clever techniques used by the Alto designers to implement Ethernet with simple TTL chips.

The Ethernet card plugged into the Xerox Alto's chassis. The disk drive is above the chassis, with a white 14" disk pack visible inside.

The Alto I've been restoring came from YCombinator; the restoration team includes Marc Verdiell, Carl Claunch and Luca Severini. My full set of Alto posts is here and Marc's extensive videos of the restoration are here. Thanks to the Living Computers Museum+Labs for the extender card and the IFS software.

You can follow me on Twitter here for updates on the restoration.

Notes and references

1. The 7400 family of TTL chips has many subfamilies with different characteristics. The 74S components use Schottky diodes for faster performance than standard TTL. The 74LS (low-power Schottky) chips use much less power (1/8 in this case), but are slightly slower and draw slightly different input currents. ↩

2. Ethernet started with Manchester encoding and continued to use this encoding up to 10 Mb/s speed. However, Manchester encoding is somewhat inefficient since each bit can have two transitions, doubling the bandwidth requirement. 100 Mb/s Ethernet solved this by using MLT-3 encoding, which uses three voltage levels. To avoid the problem of losing the clock on a long string of 0's, each group of 4 bits is sent as a particular 5 bit pattern that eliminates long repetitive sequences. Ethernet gets progressively more complex as speed increases. At 100 Gb/s Ethernet, blocks of 64 bits are encoded with 66 bit patterns and data is split across multiple lanes. ↩

3. Manchester encoding was developed for magnetic drum storage for the University of Manchester's Mark 1 computer. The Mark 1 was an influential early computer from 1949, one of the earliest stored-program computers, also introducing index registers and Williams tube storage. ↩

4. One potential problem with the clock extraction is if you have a steady stream of bits (1111... or 0000...) the Ethernet signal will be a steady stream of transitions, and you can't tell where to start the clock. The solution is that each Ethernet transmission starts with a sync bit to get the clock started properly. ↩

5. The schematics for the Alto's Ethernet board are at Bitsavers. The Ethernet is described in more detail in the Alto Hardware Manual. ↩

Identifying the "Early IBM Computer" in a Twitter photo: a 405 Accounting Machine

The photo below of a "woman wiring an early IBM computer" has appeared on Twitter a bunch of times, and it stoked my curiosity: what was the machine in the photo? Was it really an early IBM computer? I was a bit skeptical since the machine in the photo is much smaller than IBM's first room-filling computers, and there aren't any vacuum tubes visible. I investigated this machine and it turned out to be not a computer, but an IBM 405 "Alphabetic Accounting Machine" from 1934, back in the almost forgotten pre-computer age of tabulating machines.1

A common photo on Twitter shows a woman wiring an early IBM computer.

The image is from photographer Berenice Abbott who took many scientific photographs from 1939 to 1958. She photographed everything from basic magnetic field and optics experiments to research on early television tubes, and many of these photos were used in physics textbooks. Her photos (including IBM photos) were published in the book Documenting Science. I had hoped that the book would identify the computer in the photo, but it merely said "IBM Laboratory: Wiring an early IBM computer". Surprisingly for an art book, it didn't even give a date for the photo.

The diagram below shows the back view of an IBM 403 accounting machine, which IBM introduced in 1948.2 (An accounting machine (also called a tabulator) summed up and printed records from punched cards for applications such as payroll or inventory.) Note the similarities with the Abbott photo: the thick laced wire bundles, the vertical wire bundles in the middle for the counters, and the hinged doors that swing open.

Back view of an IBM 403 accounting machine. From the IBM 402/403 Field Engineering Manual.

A second Berenice Abbott photo shows the machine from a slightly different angle.3 The "Card Feed Circuit Breaker Unit" in the upper right looks like a perfect match between the IBM 403 and the Abbott photo. The dangling cables from the counters in the middle look right, as well as the thick cable between the counters and the circuit breaker unit. The 403 diagram above shows a large printing carriage on top, while the Abbott photo just shows a base, presumably because the carriage hadn't been installed yet.

A second photo of "Woman wiring an early IBM computer" by Berenice Abbott.

Although the machine in the Abbott photo looks very similar to the IBM 403, there are a few differences if you look carefully. One clear difference is the IBM 403 had caster wheels attached directly to the frame, while the machine in the photos has stubby curved legs. In addition, the doors of the IBM 403 were hinged at a different place. In the Abbott photos, the doors are attached just to the left of the counters and to the right of the card feed circuit breaker unit. But the IBM 403 has some bulky components to the left of the counters such as the "Bijur pump" (an oil pump), and components on the right such as the drive motor. Overall, the machine in the Abbott photos has a narrower cabinet than the IBM 403. Additionally, the thick cable snaking down between the IBM 403's circuit breaker units appears to go straight down in the photos. Thus, although the machine in the photos is very similar to the IBM 403, it's not an exact match.

After more research into IBM's various accounting machines, I conclude that machine in the photos is the IBM 405, an IBM accounting machine introduced in 1934 (earlier than that 1948 IBM 403 despite the larger model number).4 The IBM 405 (below) had curved legs that match the Abbott photos. In addition, the 405 has a narrower main cabinet than the 403, with bulky additional components attached to the left and right, outside the legs. This matches the narrower cabinet in the Abbott photos. (The 403 was an improved and modernized 405, explaining the overall similarity between the two machines.)

An IBM 405 accounting machine. Photo courtesy of Columbia University Computing History.

Punched cards were a key part of data processing from 1890 until the 1970s, used for accounting, inventory, payroll and many other tasks. Typically, each 80-column punched card held one record, with data stored in fixed fields on the card. The diagram below shows a typical card with columns divided into fields such as date, vendor number, order number and amount. An accounting machine would process these cards: totaling the amounts, and generating a report with subtotals by account and department, as shown below.

Example of a punched card holding a 'unit record', and a report generated from these cards. The accounting machine can group records based on a field to produce subtotals, intermediate totals, and totals. From Manual of Operation.

Punched-card data processing was invented by Herman Hollerith for the 1890 US census, which used a simple tabulating machine to count census data, stored on punched cards. Tabulating machines steadily became more complex, becoming feature-laden "accounting machines" that could generate business reports. Businesses made heavy use of these electromechanical accounting machines and by 1944, IBM had 10,000 tabulating and accounting machines in the field.

Accounting machines were "programmed" with a removable plugboard. By switching the plugboard, an accounting machine could be rapidly reconfigured for different tasks. Each wire corresponded to one character or digit. Wires plugged into the plugboard connected columns on the input card to adders. Each column on the printer had an associated wire controlling what got printed. Other wires had control functions. (I explained the tax preparation plugboard below in detail in this article.)

Plugboard to generate a tax report on an IBM 403 accounting machine. Courtesy of Carl Claunch.

The IBM 405 was IBM's first "Alphabetic Accounting Machine," able to print text as well as numbers. It had more complexity than you might expect from the 1930s, able to generate three levels of subtotals, intermediate totals, and grand totals. It could process up to 150 cards per minute; that's remarkably fast for an electromechanical system, reading and summing more than 2 cards per second. The 405 was IBM's flagship product for many years, with IBM manufacturing 1500 of them per year. Like most IBM machines, the 405 was usually rented rather than purchased; it cost over $1000 a month (equivalent to about $15,000 per month in 2017 dollars). Renting out these machines (and selling the punch cards) was highly profitable for IBM, with the IBM 405 accounting machine called "the most lucrative of all IBM's mechanical glories".5

Amazingly, although accounting machines were designed for business purposes, they were also used for scientific computation in the 1930s and 1940s, before digital computers existed. They solved everything from differential equations and astronomy computations to nuclear bomb simulations for the Manhattan Project.6

How does an accounting machine work and what are all those parts?

Accounting machines (also called tabulators) were built from electromechanical components, rather than transistors or even vacuum tubes. The main components in accounting machines were electromechanical counters and relays. Everything was synchronized to rotating driveshafts that ran the counters, card reader and printer. In a way, accounting machines were more like cars than computers, with a motor, clutches, driveshafts, an oil pump, gears and cams.

Counters

The heart of the accounting machine was the mechanical counter, a digit wheel somewhat like an odometer. Each wheel stored one digit, with the value indicated by the rotational position of the wheel. To add a number, say 3, to the counter, a clutch was briefly activated, causing the drifeshaft to rotate the counter three more positions. Since these counters were adding 2 1/2 numbers per second, they were spinning rapidly with the clutches engaging and disengaging with precision timing. By combining multiple counters, numbers of up to 8 digits could be handled. The counter kept a running total of the numbers fed into it. Since it accumulated these numbers, the counter was known as an accumulator, a term still used in computing.

A counter unit from an IBM accounting machine. The two wheels held two digits. The electromagnets (white) engaged and disengaged the clutch so the wheel would advance the desired number of positions.

The photo above shows a board with two counters: the two wheels on the left stored two digits. The counters are more complex than you might expect, with electromechanical circuits to handle carries (including fast carry lookahead). The clutch is underneath the wheel and is engaged by the metal levers in the photo, controlled by electromagnets. A gear underneath the clutch connects the counter to the driveshaft. The electrical connections on the right control the clutch and allow the values from the counters to be read out. Since the IBM 405 had 16 accumulators, with up to 8 digits, many counters were required, resulting in the mass of counter wires in the photos.

Relays

Another key component of the accounting machine was the relay, an electromagnetic switch. The control logic of the accounting machine was implemented with hundreds of relays, which would turn on and off to direct the various components of the accounting machine. Example relay functions are switching on when punched cards are in the input hopper, selecting addition or subtraction for a counter, generating the final total when all cards are done, or printing a credit symbol for a negative balance.

The back of the IBM 403 accounting machine shows numerous relays, used to control the machine.

The relays were mounted on swing-out panels. The photo above shows an IBM 403 with the panels closed. In the Abbott photos the relay panels are opened and you can see the extensive wiring that connected the relays to the rest of the system.

Circuit breakers

The final component I'll explain is the "circuit breaker," which has nothing to do with the circuit breakers in your house. Instead, these are cam-controlled switches that turned on and off (breaking circuits) as the drive shafts rotated. Dozens of circuit breakers provided the timing signals to the accounting machine, ensuring all operations in the machine were synchronized to the drive shaft. (Every 18° of drive shaft rotation corresponded to reading one row on a punched card, moving one character position on a printer typebar, or advancing a counter wheel by one position.)

Conclusion

The woman in Abbott's photos illustrates the large, but mostly ignored role that women played in electrical manufacturing. Women formed the majority of workers in the 1920s radio manufacturing industry, and their presence in electrical manufacturing increased even more when World War II led many women to take industrial jobs. The famous ENIAC computer (1946) also illustrates this: most of the "wiremen" assembling the ENIAC computer were in fact women, probably recruited from the telephone company or radio assembly.8

The photos also provide a glimpse into the era before digital computers, when businesses used electromechanical accounting machines and tabulators for their data processing. Although you'd expect a machine from 1934 to be primitive, the IBM 405 accounting machine in the photos was an advanced piece of technology for its time, containing 55,000 parts and 75 miles of wire.5 These punched card machines were also capable of performing complex scientific tasks, even contributing to the Manhattan Project. In the 1960s, businesses gradually switched from accounting machines to stored-program business computers such as the IBM 1401. Even so, IBM continued marketing accounting machines until 1976.

Follow me on Twitter or RSS to find out about my latest blog posts.

Notes and references

1. By the "era before computers", I mean before digital electronic computers came along in the 1940s. There's a long history of computing machines, analog computers, and human computers (as shown in Hidden Figures) before digital computers came along. Two interesting books that cover this history are The First Computers—History and Architecture or The Computer: From Pascal to von Neumann. ↩

2. IBM's 402 and 403 accounting machines were the same except the 403 could print three-line addresses. This feature was called MLP (multi-line printing) and was useful for printing addresses on invoices, for instance. So when I refer to the IBM 403 accounting machine, I'm also including the IBM 402. ↩

3. I was surprised to realize that there are two different, but nearly identical photos of the woman wiring the IBM machine floating around. In first photo, the woman's right leg is straight, there's a screwdriver in front of the bench and she's wiring the left side of the machine. In the second, the woman's left leg is straight and she's wiring the middle of the machine. ↩

4. I couldn't find any manuals for the IBM 405 or photos of the back of a 405, so I can't totally nail down the identification. There's a possibility that the Abbott photos show an IBM 401 accounting machine (below), which was similar to the 405 but introduced a year earlier. The IBM 401 and IBM 405 both had the same basic shape and arrangement of components. The main difference is 405 had a full cabinet in front while the 401 was empty in the front with a bar bracing the front feet. The Abbott photos seem to show a full cabinet like the 405, rather than the open 401. Also, since the 405 was a much more popular machine than the 401—the 405 was the "flagship of IBM's product line until after World War II"—the photos are most likely the 405.

   ↩

   IBM 401 accounting machine (1933). Photo courtesy of Computer History Museum.

5. Several sources provide information on the IBM 405. One source is Computing before Computers (online) p144. IBM has a FAQ with a short overview. Columbia's Computer History page on the 405 has a longer discussion. Also see IBM's Early Computers, pages 18-22 for information on the IBM 405. Computer: Bit Slices from a Life has some hands-on stories of the IBM 405 (online). Computer: A history of the information machine page 51 has some information on the IBM 405. ↩

6. See Punched Card Methods in Scientific Computation, 1940 for details on how accounting machines were used for scientific computation. The book is by W. J. Eckert, confusingly unrelated to the ENIAC's J. Presper Eckert. The use of IBM accounting machine by the Manhattan Project is described by Feynman in Los Alamos from Below, p25; and in this page. The Manhattan Project used a 402 accounting machine, several IBM 601 multiplying punches for multiplication, and other card equipment (reference, with more details in Early Computing at Los Alamos). ↩

7. Bitsavers has manuals for the later 402/403 accounting machines. The operation of accounting machines is discussed in detail in IBM 402, 403 and 419 Accounting Machines: Manual of Operation. For a thorough discussion of how the machine works internally, see IBM 402, 403, 419 Field Engineering Manual of Instruction. For an overview of how plugboard wiring for IBM's works, see IBM Functional Wiring Principles. ↩

8. Women and Electrical and Electronics Manufacturing provides a detailed discussion of the history of women in technological manufacturing in the 20th century. The book ENIAC in Action describes how most of the wiring of the ENIAC was done by women. It also has a detailed discussion of the role of women as programmers for early computers such as the ENIAC. ↩