Digital Systems: Algorithms, Microcode and Hardware
(David Naccache)
This module provides a cross section of the various scientific disciplines around which the design of embedded system revolves. We will successively address digital circuit design, microprogramming and the optimization of embedded algorithms.
Each topic will be illustrated by examples designed to be as close as possible to real-life industrial cases.
The pedagogic objectives sought are:
1. Familiarize students with machine-level design technologies: hardware and microprogramming.
2. While doing so present to the students the most common embedded algorithms (compression, arithmetic, garbage collection, error correction) that one encounters while implementing embedded systems.
The students will have to overcome the real challenges and constraints faced by embedded system designers while putting together mission-critical systems (critical paths, gate-count, low energy consumption, execution speed, RAM consumption).
- Mathematical circuits
o Multiplexer, combinatorial logic and BDDs - Binary Decision Diagrams. Registers and digital synchronous circuits.
o Lab: design a digital clock.
- Binary algebra
o Average complexity circuits. Adder, subtractor, comparator.
o Lab: design a pocket calculator.
- Electronic circuits
o Various flip-flop types, counters, PROMs, sequencers, shift registers and other components.
o Lab: enhancement of the pocket calculator with memory functions and “target value” functions.
- Arithmetic in silicon
o Adders and multipliers: serial and parallel. Optimal time/surface tradeoffs.
o Lab: enhancement of the pocket calculator with multiplication and division functions.
- The68HC05 microprocessor
o Presentation of the 68HC05 assembly programming tools. Motorola architecture. Ports, registers, memory, ALU.
o Lab: Write a floating point library in assembler.
- Embedded compression
o Shannon theory. Entropic compression. Compression using the RLE, LZW and Huffman methods.
o Lab: RLE, LZW and Huffman on the 68HC05.
- Embedded error correction
o Error control via algebraic encoding. Viterbi codes.
o Lab: Hamming and Reed-Solomon coders / decoders on the 68HC05.
- Embedded arithmetic: multiplication and modular reduction
o Multi-precision multiplication and Montgomery / Barrett reduction. Proofs of these algorithms and work factor analyses.
o Lab: Multi-precision multiplication and Montgomery / Barrett reduction on the 68HC05.
- Smart Cards. Standards, structure, programming, Javacard and non-volatile memory management policies (Garbage collection).
o Introduction to smart cards and their applications. Dissection of a CAP file.
o Lab: Embedded garbage collector by the mark & sweep method.
- Contactless cards, RFID.
o Anti-collision strategies (how a reader receiving simultaneous messages over the air manages to individuate them).
o Lab: Exhibition of results of all Lab sessions (with posters and demos) to internal and external researchers and students.