Strange things happen during a pandemic shutdown. For some reason, being stuck inside, I got the urge to prepare Christmas gifts for my friends and relatives. I have built LED Christmas Trees for many years from kits and original designs. Here is the latest revision for 2020.
General Description
As shown in photo above the LED Christmas Tree consists of a green printed circuit board in the outline shape of a tree decorated with 16 LEDs. A microphone responds to ambient sound to effectively clock a microcontroller (MCU) executing different LED sequence patterns. The unit is powered by a 6VDC, 600mA AC adaptor (wall wart). Overall Dimensions: 6″Hx4″Wx2″D
Features
The ATmega328P microcontroller (MCU) in a 28L DIP package controls the LED action. The Arduino Uno uses this same MCU and indeed the firmware was developed in the Arduino environment.
- An Electret Microphone connects to the MCU Analog Comparator (AIN0/AIN1) to detect sound and animate the LEDs.
- A 16 bit Linear Feedback Shift Register (LFSR) creates a Maximal Length Pseudo Random Bit Stream (PRBS) dynamic LED sequence. This produces an eye-catching pattern as the bits shift in order around the 16 LEDs.
- If no sound is detected for 30 seconds all the LEDs turn off and the Tree enters a low-power stealth mode, ready to resume execution at the next sonic vibration.
- All through-hole component technology makes or easy assembly. Socketed integrated circuits enable firmware updates. Unit cost is $40-60 depending on quantities.
Hardware
The ATmega328P microcontroller (MCU) in a 28L DIP package controls the LED action. The Arduino Uno uses this same MCU and indeed the software was developed in the Arduino environment.
The Printed Circuit board was manufactured by ExpressPCB and designed using their FREE CAD tools. I used my home shop band saw with a fine toothed blade to cut out the Tree profile.
Microphone Circuit
As shown in the diagram below the electret microphone output is capacitively coupled to a linear op-amp IC (LM358). An LM358 op-amp is biased with 5K ohm resistors producing a voltage gain of 2x, so it mainly functions as an impedance buffer. But this is enough signal to trip the Analog Comparator (AIN0,AIN1). The circuit is shown below.
Firmware Sketch
This sketch is short and very simple, only 1900 bytes are flashed (about 4% of available program and variable space). All the LED dynamics are driven by two Interrupt Service Routines (Analog Comparator and Timer1).
Each time an Analog Interrupt occurs an interrupt counter is incremented. This value, depending on the range, decides which sequence subroutine to execute. The sequence subroutine operates like a Finite State Machine where each call advances the sequence by one clock tick. The LFSR sequence is generated algorithmically but other patterns are defined by a multi-dimensional array. The first dimension defines the sequence step while the second dimension lists the LEDs to turn off and on. A multi-dimensional array allows the programmer to create any LED sequence, in a straight forward manner, limited only by your imagination and MCU memory size.
Timer1 is the MCU’s only 16 bit timer (max. value is 65535 counts). When a timeout occurs all the LEDs are turned off. In order to achieve a 30 second timeout delay, the CPU clock was divided by 16 making the internal CPU clock frequency 1MHz. To avoid premature timeout Timer1 is reset every time an Analog Comparator interrupt occurs.
The sketch includes 5 canned LED sequences and debug compile options for using the Arduino Serial Monitor. Many debug problems required stand-alone, real-time operation without the Serial Monitor.
LFSR
A Linear Feedback Shift Register (LFSR) is a logic configuration often applied in cryptography and authentication, random number generation, logic testing, communications coding, decoding and error correction.
There are 2 main LFSR configurations. In Fibonacci LFSRs, 2 or more Q outputs are Xor’d (logic exclusive OR) to generate feedback (externally) to the first input stage (D0). The other type, named after Evariste Galois, inserts Xor’d feedback (internally) between the D-flop stages.
By taping different output stages for feedback we can create different sequences with different run lengths. With proper choice of feedback stages we can create a Maximal Length Sequence with a run length of 2^n -1 combinations.
Example: 4 bit LFSR
With feedback taps chosen from Q0, Q3, this 4 bit LFSR generates a Maximal Length PRBS of 15 combinations (2^4 – 1).
| t | D0 | D1 | D2 | D3 | feedback |
| 0 | 1 | 1 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 | 1 | 1 |
| 2 | 1 | 0 | 1 | 1 | 0 |
| 3 | 0 | 1 | 0 | 1 | 1 |
| 4 | 1 | 0 | 1 | 0 | 1 |
| 5 | 1 | 1 | 0 | 1 | 0 |
| 6 | 0 | 1 | 1 | 0 | 0 |
| 7 | 0 | 0 | 1 | 1 | 1 |
| 8 | 1 | 0 | 0 | 1 | 0 |
| 9 | 0 | 1 | 0 | 0 | 0 |
| 10 | 0 | 0 | 1 | 0 | 0 |
| 11 | 0 | 0 | 0 | 1 | 0 |
| 12 | 1 | 0 | 0 | 0 | 1 |
| 13 | 1 | 1 | 0 | 0 | 1 |
| 14 | 1 | 1 | 1 | 0 | 1 |
| 15 | 1 | 1 | 1 | 1 | Repeat |
| 16 | 0 | 1 | 1 | 1 | Repeat |
If we count the number of consecutive 1’s and 0’s we find that 1/2 are 1 bit, one-quarter are 2 bits, one-eight are 3 bits etc. up to 1/(2^n) are n bits wide. Thus the distribution nearly equals the statistical expectation value for a truly random distribution. This type of analysis is shown for our 4 bit LFSR in the Table 2 below. Some difference between Actual versus Ideal Probability Expectation is noted, however for wider LFSRs, with more states, these Expectation values are very close. This is what gives a PRBS its pseudo random quality.
| width= length | 4 15 | bits combos. | Random Prob. Expectation | |
| Bit Pattern | Run Len. | #Occur. | Actual | Ideal |
| ‘b1 | 1 | 2 | 0.25 | 0.25 |
| ‘b11 | 2 | 1 | 0.125 | 0.125 |
| ‘b111 | 3 | 1 | 0.125 | 0.0625 |
| ‘b1111 | 4 | 0 | 0 | 0.0625 |
| ‘b0 | 1 | 2 | 0.25 | 0.25 |
| ‘b00 | 2 | 1 | 0.125 | 0.125 |
| ‘b000 | 3 | 0 | 0 | 0.0625 |
| ‘b0000 | 4 | 1 | 0.125 | 0.0625 |
Stream Cipher
Suppose we want to encrypt the message ‘HI’ which is ASCII Capital ‘H’ (‘b0100 1000) and ASCII Capital ‘I’ (‘b0100 1001). This makes our Plaintext = ‘b0100100001001001.
Select a 16 bit Key from Table 1, e.g. column D0 from t = 2 to 16 i.e. Key = ‘b1011001000111101. To encode the message, Xor each bit of Plaintext with the corresponding bit of Key. Remember that Xor is like binary addition (without the carry bit).
Encrypt (Encode)
Generate Ciphertext by Xor’ng Key with Plaintext
| t | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| Key | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
| Plaintext | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| Ciphertext | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 |
Decrypt (Decode)
Restore Plaintext by Xor’ng original Key with Ciphertext
| t | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| Key | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
| Ciphertext | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 |
| Plaintext | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
Of course this is a trivial example (so you can follow along). If the key (initial state) were much wider, say 256 bits, the number of possible keys would be 1E+77. If you tried cracking the cipher by guessing 100 trillion keys per second it would still take 2.5E+47 universe lifetimes to try every possible key. Chances of success are very low.
Assembly
To perform the necessary ATmega328P programming I modified an Arduino Uno by replacing the 28 lead MCU DIP (Dual Inline Package) with a narrow 28L ZIF (Zero Insertion Force) socket, and built the Adafruit 462 Standalone AVR ISP Programmer Shield Kit to program bootloaders into raw MCU ICs.
Conclusion
This was a satisfying project because it created unique Christmas gifts for my relatives and friends. Children especially, enjoy the voice/audio interaction. No doubt my relatives will not be satisfied unless my next revision is controlled by a Smartphone App and automatically uploads data to the Cloud for real time ambient noise analysis. I kept one Tree for myself to set on my piano so I can entertain guests with a multi-media performance of Christmas Carols.
Programmers are invited to play with LED sequences, switching delays and add digital filters or other functionality.
Building this standalone MCU project extended my development skills in the Arduino environment. 10 Tree units were assembled with 100% yield.
References
- Adafruit 462 bootloader Kit: https://www.adafruit.com/product/462
- LFSR Tutorial: https://www.eetimes.com/tutorial-linear-feedback-shift-registers-lfsrs-part-1/#
- ATmegea328P Fuse Programming: http://www.martyncurrey.com/arduino-atmega-328p-fuse-settings/
- LFSR Cryptography: https://cryptography.fandom.com/wiki/Linear_feedback_shift_register
- http://www.math.wisc.edu/~edhanson/teaching/435s18/LFSR_handout.pdf
