Introduction

Multiplication in microcontroller units (MCUs) is a fundamental operation that underpins many computational tasks, but it can also be a performance bottleneck, especially in lower-end 8-bit MCUs lacking hardware multipliers. A typical challenge is multiplying 16-bit integers efficiently given the limited resources of these devices. In this article, we explore methods and an algorithm to speed up 16-bit multiplication on 8-bit MCUs using software-based techniques.

Basics of 16-bit Multiplication

On an 8-bit microcontroller, such as those from the AVR or PIC families, 16-bit multiplication must often be conducted in software. This typically involves combining four 8-bit multiplications to achieve a single 16-bit multiplication, due to the limited register width. A basic multiplication of two 16-bit numbers, A and B , could be represented as follows:

• $A = A_{H} \times 256 + A_{L}$ • $B = B_{H} \times 256 + B_{L}$

Where $A_H$, $A_L$, $B_H$, and $B_L$ are the high and low bytes of $A$ and $B$, respectively. The resulting multiplication operation can be broken down into smaller segments:

$$Product = (A\_H \times 256 + A\_L) \times (B\_H \times 256 + B\_L)$$

Expanding this expression gives:

$$Product = A\_H \times B\_H \times 65536 + A\_H \times B\_L \times 256 + A\_L \times B\_H \times 256 + A\_L \times B\_L$$

Each of the terms can be calculated using an 8-bit multiplication.

Optimized Algorithm

To optimize the multiplication, a strategic approach can diminish the total number of operations by reusing partial results and minimizing additions. One such optimized method is the iterative shift-and-add processing which exploits the binary decomposition of the numbers.

Faster 16-bit Multiplication Algorithm

Here is a step-by-step explanation of an efficient method to multiply two 16-bit numbers:

1. Initialize Registers: • Load the initial values of A and B into two pairs of 8-bit registers representing their high and low bytes.
2. Compute Partial Products: • Compute $A_L \times B_L$: This is the simplest multiplication as it directly contributes to the lower byte of the final product. • Compute $A_L \times B_H$ and $A_H \times B_L$: These contribute mainly to the middle segment of the resulting word. Each multiplication here will need to be left-shifted by 8 bits (equivalent to multiplying by 256). • Compute $A_H \times B_H$: This contributes to the higher byte and needs to be left-shifted by 16 bits in the final product assembly.
3. Aggregate Partial Products with Shifting: • Add the results, as shown in the following combinatorial scheme, ensuring that carries from one byte are considered in the subsequent higher byte:

$$\begin{align*} &\text{Low Byte: } (A\_L \times B\_L) \\ &\text{Middle Byte: } (A\_L \times B\_H) + (A\_H \times B\_L) + \text{carry from low byte}\\ &\text{High Byte: } (A\_H \times B\_H) + \text{carry from middle byte} \end{align*}$$

1. Optimize Carries Management: • Use assembly instructions wisely to manage carries that arise when adding 8-bit results. Adding with carry instructions (ADD /ADC in AVR assembly) efficiently manages the multi-byte aggregation.

Example Code

Below is an illustrative example in pseudocode that translates the above approach into steps suitable for a typical 8-bit AVR type MCU:

• Instruction Cycle Count: Depending on the architecture, these operations (8-bit multiplication, additions, and carries) can be significantly faster when carefully sequenced compared to calling generic multiplication routines. • Memory Use and Efficiency: This implementation is efficient in terms of memory since it mainly uses registers. This is crucial for MCUs with limited RAM. • Scalability: This method scales well for slightly larger bit-widths with the same principle applied to segments of the binary representation.